The author is a recent intern. The following code is the biggest optimization of current understanding ability. I hope it will be helpful to you; Compared with quick sort and heap sort, the author gives priority to recommend readers to use heap sort, because the code complexity of heap sort is fixed, and the more the number to be sorted, the more advantages. After I read it, you will find that the code of heap sort is better understood than quick sort, and there are fewer codes.
Each sort here has two sorting methods: recursive and non recursive (simple without comments)
1. Binary search sorting algorithm (half search)
Understanding: you can only sort the ordered arrays, both ascending and descending. Take ascending order as an example. Its usage can be as the name suggests. Each comparison is from the middle value. If it is equal to the middle value, a prompt will be returned. If it is greater than the middle value, look in the right half and repeat the middle value comparison; If it is less than, search to the left and repeat the comparison of intermediate values. If no value is found, a prompt will be returned.
public static void main(String[] args) {
int[] n = {1,2,3,4,5,6,7,8,9,10};
int number = 10;
//recursion
//System.out.println(binarySearch(n,0,n.length-1,number));
//non-recursive
System.out.println(noRecursion(n,0,n.length-1,number));
}
//recursion
static String binarySearch(int[] n,int start, int end,int number){
int index = (start+end)/2;
if (n[index] == number){
return "The value you are looking for is in"+(index+1)+"position";
}
if (start == end){
return "There's no value you're looking for";
}
if (n[index] > number){
end = index-1;
}
if (n[index] < number){
start = index+1;
}
return binarySearch(n,start,end,number);
}
//non-recursive
static String noRecursion(int[] n,int start, int end,int number){
String hint = "";
while (start <= end){
int index = (start+end)/2;
if (n[index] == number){
hint = "The value you are looking for is in"+(index+1)+"position";
break;
}
if (start == end){
hint = "There's no value you're looking for";
break;
}
if (n[index] > number){
end = index-1;
}
if (n[index] < number){
start = index+1;
}
}
return hint ;
}
2. Bubble sorting
Understanding: bubble sort is the source of quick sort. Understanding bubble sort will be of great help to quick sort. Bubble sorting can only be compared with adjacent values. For example, if you take the value at position 3, you can only compare and replace it with the value at position 1 or 2 (the comparison direction can only be one, and which direction is up to you). Here is an example of right comparison:
public static void main(String[] args) {
int[] n = {56, 7, 23, 235, 45, 321, 45, 324, 46, 23, 0};
//recursion
//bubble(n);
//non-recursive
noRecursion(n);
System.out.println("After sorting"+ Arrays.toString(n));
}
//recursion
static void bubble(int[] n){
int staus = 0;
for (int i = 0; i<n.length-1;i++){
if (n[i] > n[i+1]){
int temp = n[i];
n[i] = n[i+1];
n[i+1] = temp;
staus = 1;
}
}
if (staus == 0){
return;
}
bubble(n);
}
//non-recursive
static void noRecursion(int[] n){
int staus = 1;
while (staus == 1){
int k = 0;
for (int i = 0; i<n.length-1;i++){
if (n[i] > n[i+1]){
int temp = n[i];
n[i] = n[i+1];
n[i+1] = temp;
k = 1;
}
}
staus = k;
}
}
3. Quick sort
Understanding: quick sort must be very fast. It is said on the Internet that quick sort is the most popular sort method at present, but I don't care whether it is popular or not. I only know that its code is a few lines more than heap sort. At present, many quick sorting methods on the Internet only have recursive method tutorials. Here I get a non recursive one, so I hope you can understand what you are reading. During the interview, tell the interviewer about two methods and ask him which one he wants, whether the B grid is high or not, and measure it yourself.
The idea of quick sorting here is to take the value of the first position as the referee, put the smaller one on the left and the larger one on the right, and then repeat the above operations with the larger one and the smaller one respectively:
public static void main(String[] args) {
int[] n = {56, 7, 23, 235, 45, 321, 45, 324, 46, 23, 0,1,320,89};
//recursion
//sort(n,0, n.length-1);
//non-recursive
noRecursion(n);
System.out.println("After sorting:"+ Arrays.toString(n));
}
//recursion
static void sort(int[] n,int start,int end){
if (start >= end){
return;
}
int left = start;
int right= end;
int temp = n[start];
//This while is only used to compare the current first value with the current last value
while (right != left){
while (right != left && n[right] > temp){
right --;
}
if (right != left){
n[left] = n[right];
left ++;
}
while (right != left && n[left] < temp){
left ++;
}
if (right != left){
n[right] = n[left];
right --;
}
}
n[left] = temp;
sort(n,start,left -1);
sort(n,left+1,end);
}
//non-recursive
static void noRecursion(int[] n){
List<Map<String,Integer>> list = new ArrayList<>();
Map<String,Integer> m = new HashMap<>();
m.put("left",0);
m.put("right",n.length-1);
list.add(m);
for (int i = 0; i < list.size();i++){
int left = list.get(i).get("left");
int right = list.get(i).get("right");
if (left >= right){
continue;
}
int indexStart = left;
int indexEnd = right;
int start = n[left];
//This while is only used to compare the current first value with the current last value
while (left != right){
while(left != right && n[right] > start){
right --;
}
if (left != right){
n[left] = n[right];
left ++;
}
while(left != right && n[left] < start ){
left ++;
}
if (left != right){
n[right] = n[left];
right --;
}
}
n[left] = start;
Map<String,Integer> ms = new HashMap<>();
ms.put("left",indexStart);
ms.put("right",left-1);
list.add(ms);
Map<String,Integer> mm = new HashMap<>();
mm.put("left",left+1);
mm.put("right",indexEnd);
list.add(mm);
}
}
4. Insert sort
Understanding: don't use any sort. It's just for fun. Just know it.
Its funny reason is: first find the minimum value every time, insert it into the current first position, and then move back one by one between the value of the first position and its position. You're right. Move back one by one:
public static void main(String[] args) {
int[] n = {56, 7, 23, 235, 45, 321, 45, 324, 46, 23, 0,1};
//recursion
//sort(n,0);
//non-recursive
noRecursion(n);
System.out.println("After sorting:"+ Arrays.toString(n));
}
//recursion
static void sort(int[] n,int start){
int index = start;
int status = n[start];
for (int i = start;i < n.length;i++){
if (n[i] < status){
index = i;
status = n[i];
}
}
int temp = n[index];
for (int i = index;i > start;i--){
n[i] = n[i-1];
}
n[start] = temp;
if (start == n.length-2){
return;
}
start++;
sort(n,start);
}
//non-recursive
static void noRecursion(int[] n){
int index = 0;
while (index < n.length-1) {
int start = n[index];
int end = index;
for (int i = index;i < n.length;i++){
if (n[i] < start){
end = i;
start = n[i];
}
}
int temp = n[end];
for (int i = end;i > index;i--){
n[i] = n[i-1];
}
n[index] = temp;
index++;
}
}
5. Select Sorting
Understanding: selecting sorting is a little better than inserting sorting. It is still recommended that you can use it. Its usage is to find the minimum value and exchange the position with the value of the first position, and then find the next smaller value and exchange the position with the value of the second position:
public static void main(String[] args) {
int[] n = {56, 7, 23, 235, 45, 321, 45, 324, 46, 23, 0,1};
//recursion
//selectionSort(n,0);
//non-recursive
sort(n);
System.out.println("After sorting:"+ Arrays.toString(n));
}
//recursion
static void selectionSort(int[] n,int index){
int temp = index;
for (int i = index+1;i < n.length;i++){
if (n[i] < n[temp]){
temp = i;
}
}
if (temp == index){
return;
}
int end = n[temp];
n[temp] = n[index];
n[index] = end;
index++;
selectionSort(n,index);
}
//non-recursive
static void sort(int[] n){
int index = 0;
while (index < n.length){
int start = n[index];
int end = index;
for (int i = index;i < n.length;i++){
if (start > n[i]){
end = i;
start = n[i];
}
}
if (index == n.length-1){
break;
}
if (index < n.length){
int temp = n[index];
n[index] = n[end];
n[end] = temp;
index++;
}
}
}
6. Heap sorting
Understanding: the final axis sorting, known as the sorting method on tall, is recommended by the author. Understanding this is equivalent to understanding the binary tree, and my code is less than the current online search priority recommended code. We must master it. My usage is: use the large root heap for ascending order, and treat the array as a tree. The first is the root node, the second is the left node of the first, and the third is the right node of the first. The fourth is the left node of the second, and so on. Compare each child node with the parent node. When the node is large, the maximum value can be moved to the position of the root node after one round, and then replace the value of the root node with the position of the current last value to obtain the ascending arrangement.
public static void main(String[] args) {
int[] n = {56, 7, 23, 235, 45, 321, 45, 324, 46, 23, 0,1,320,89,2};
//recursion
//heapSort(n,0,n.length-1);
//non-recursive
noRecursion(n);
System.out.println("After sorting:"+ Arrays.toString(n));
}
//recursion
static void heapSort(int[] n,int start,int end){
if (start >= end){
return;
}
for (int i = end;i > 0;i--){
if (n[i] > n[(i-1)/2]){
int temp = n[(i-1)/2];
n[(i-1)/2] = n[i];
n[i] = temp;
}
}
int index = n[end];
n[end] = n[start];
n[start] = index;
end --;
heapSort(n,start,end);
}
//non-recursive
static void noRecursion(int[] n){
int start = 0;
int end = n.length-1;
while (start <= end){
for (int i = end; i > start;i--){
if (n[i] > n[(i-1)/2]){
int temp = n[(i-1)/2];
n[(i-1)/2] = n[i];
n[i] = temp;
}
}
int temp = n[start];
n[start] = n[end];
n[end] = temp;
end --;
}
}
7. At the end of the gift, attach a topic about rabbits giving birth to children:
Question: a rabbit gives birth to one rabbit every month from the third month. The little rabbit will also give birth to one rabbit every month from the third month. If the rabbits don't die, what is the total number of rabbits every month?
Note: but after you understand the sorting method above, you will find that this problem is very simple.
Send code:
public static void main(String[] args) {
int month = 20;//Months
//recursion
//int s = sum(month);
//non-recursive
int s = noRecursion(month);
System.out.println(s);
}
//recursion
static int sum(int month){
if (month == 1 || month == 2){
return 1;
}
return sum(month-1)+sum(month -2);
}
//non-recursive
static int noRecursion(int month){
int[] stage = new int[month];
for (int i = 0;i < month;i++){
if (i <= 1){
stage[i] = 1;
}else {
stage[i] = stage[i-1] + stage[i-2];
}
}
return stage[month - 1];
}
Note: I hope it will be helpful to you.