<> use java Realize bubbling , insert , Select equal sort

<> Bubble sort ( optimization )

<>1. thought

Traverse from subscript zero , Two adjacent numbers are compared with each other , Sink the maximum number to the bottom .

<>2. code
public void bubble(int[] a){ for (int i = 0; i < a.length - 1; i++) { for (int
j = 0; j < a.length-1-i; j++) { if(a[j]>a[j+1]) swap(a,j,j+1);// Put the first j And j+1 Value exchange of Subscripts
} } }
optimization
public void bubble(int[] a){ for (int i = 0; i < a.length - 1; i++) { boolean
s=false;// set mark for (int j = 0; j < a.length-1-i; j++) { if(a[j]>a[j+1]){
swap(a,j,j+1); s=true; } } if(!s)break; } }
<> Select sort

<>1. thought

Assume zero is the minimum value , Then take the zero position and compare it with the following numbers in turn , Swap if greater than . After traversing the array , The first value is the minimum value . Then set position 1 as the minimum value and compare it with the following .

<>2. code
public void select(int[] a) { for (int i = 0; i < a.length - 1; i++) { for
(int j = i + 1; j < a.length; j++) { if (a[i] > a[j]) swap(a, i, j); } } }
<> Insert sort

<>1. thought

Start with zero as an ordered array , Add the next digit of the array in sequence , The added number is compared with the previous number from front to back , Make it an ordered array . as a[0] Ordered by itself ; Join the next one a[1], yes a[0:1] Sort , If a[1]<
a[0] Then exchange , After exchange a[0:1] Orderly ; Join next a[2], take a[0:2] Orderly , Add to the last bit of the array in turn , Ordered array after sorting .

<>2. code
public void insert(int[] a) { for (int i = 1; i < a.length; i++) { for (int j
= i - 1; j >= 0; j--) { if (a[j + 1] < a[j]) swap(a, j + 1, j); } } }
<> Quick sort （ recursion ）

<>1. thought

Take any one of the objects to be sorted as the benchmark , According to the key size of the object , Divide the whole object sequence into left and right sub sequences . among , All keys in the left subsequence are less than or equal to the key of the reference object ; The keys of all objects in the right subsequence are greater than those of the base object . At this time, the position of the reference object is the final position of the object in the sequence . Then recursively repeat the above method in the left and right subsequences , Until all objects are placed in the corresponding position .

<>2. code
public int portion(int[] a, int left, int right) { int tmp = a[left]; while
(left < right) { while (left < right && a[right] >= tmp) --right; a[left] =
a[right]; while (left < right && a[left] <= tmp) ++left; a[right] = a[left]; }
a[left] = tmp; return left; } public void quickSort(int[] a, int start, int
end) { int par = portion(a, start, end); if (par > start + 1) quickSort(a,
start, par - 1); if (par < end - 1) quickSort(a, par + 1, end); }
<> Quick sort （ non-recursive ）

<>1. thought

Recursive fast sorting algorithm is automatically implemented by compiler with stack , When the recursion level is deep , It needs to occupy a large process stack space , Danger of process stack overflow . So we can simulate the recursive process with stack , That is, after taking a part from the top of the stack for division each time , Put the starting positions of the new two parts into the stack respectively .

<>2. code
public static int partion(int[] a, int low,int high) { int tmp = a[low];
while(low < high) { while(low < high && a[high] >= tmp ) { --high; } if(low >=
high) { break; }else { a[low] = a[high]; } while(low < high && a[low] <=tmp) {
++low; } if(low >= high) { break; }else { a[high] = a[low]; } } a[low] =tmp;
return low; } public static void QSort(int[] a) { int[] stack = new
int[a.length]; int top = 0; int low =0; int high = a.length-1; int par
=partion(a, low, high); if(par > low + 1) { stack[top++] = low; stack[top++] =
par - 1; } if(par < high - 1) { stack[top++] = par + 1; stack[top++] = high; }
// Out of stack while(top > 0) { high = stack[--top];// Last stack top++ Yes , So it's used here --top instead of top-- low
= stack[--top]; par = partion(a,low,high); if(par > low+1) { stack[top++] =
low; stack[top++] = par - 1; } if(par < high-1) { stack[top++] = par+1;
stack[top++] = high; } } }
<>shell sort （ Insert sort of enlarged version ）

<>1. thought

（shell（） The idea of method ） Take a less than n Integer of d1 As the first increment , Divide all records of the document into d1 Groups . All distances are d1 Records of are placed in the same group . First, carry out direct insertion sorting in each group ;
（shellSort（） Thought of ） then , Take the second increment d2< d1 Repeat the above grouping and sorting , Up to the increment taken dt=1(dt< dt-l< …< d2<
d1), That is, all records are placed in the same group until they are directly inserted and sorted .

<>2. code
public void shell(int[] a, int gap) { for (int i = gap; i < a.length; i++) {
for (int j = i - gap; j >= 0; j = j - gap) { if (a[j + gap] < a[j]) swap(a, j +
gap, j); } } } public void shellSort(int[] a) { int[] d = {7, 3, 1}; for (int i
= 0; i < d.length; i++) { shell(a, d[i]); } }
<> Heap sort

<>1. thought

Construct the sequence to be sorted into a large top heap , here , The maximum value of the whole sequence is the root node at the top of the heap . Swap it with the last element , At this time, the end is the maximum value . Then the remaining n-1 Elements reconstructed into a heap , This will get n Sub minor value of elements . So repeated , Then we can get an ordered sequence

<>2. code
// Get the parent node of the last left child private int lastLeftChildrenParent(int size){ return
size/2-1; } // Get the left child of the current node private int leftChildren(int i){ return i * 2 + 1; }
public void adjust(int[] a, int start, int end) { int tmp = a[start]; for (int
i = leftChildren(start); i <= end; i = leftChildren(i) ) { if (i < end && a[i]
< a[i + 1]) i++; if (a[i] > tmp) { a[start] = a[i]; start = i; } else break; }
a[start] = tmp; } public void heapSort(int[] a) { //1. Construct an array into a large root heap for (int i =
lastLeftChildrenParent(a.length); i >= 0; i--) { adjust(a, i, a.length - 1); }
//2. Using heap sorting for (int i = 0; i < a.length - 1; i++) { swap(a, 0, a.length - 1 -
i); adjust(a, 0, a.length - 2 - i); } }
-----------.

<> Merge sort

<>1. thought

The basic idea is to divide the array into a.length/2n Groups 2n number , For example, the third line on the left below is the second grouping , Divided 5 Groups , Each group 21
number . Then create a temporary array , Combine two adjacent ones into an ordered group , Put into temporary array . until 2n>=a.length.

<>2. code
public static void mergeSort(int[] a) { for (int i = 1; i < a.length; i = i *
2) { merge(a, i); } } public static void merge(int[] a, int gap) { int start1 =
0;// Beginning of the first group int end1 = start1 + gap - 1;// End of group 1 int start2 = end1 + 1;// Beginning of the second group int
end2 = start2 + gap - 1 < a.length - 1 ? start2 + gap - 1 : a.length -
1;// End of the second group int[] tmpa = new int[a.length];// Temporary array for merging int i = 0; while (start2 <
a.length) {// Adjacent as gap Group of , Using temporary arrays , Merge by two while (start1 <= end1 && start2 <= end2) {
if (a[start1] < a[start2]) tmpa[i++] = a[start1++]; else tmpa[i++] =
a[start2++]; } while (start1 <= end1) tmpa[i++] =
a[start1++];// If the second group is traversed first , Fill the first group after the temporary array while (start2 <= end2) tmpa[i++] =
a[start2++];// If the first group is traversed first , Fill the second group after the temporary array start1 = end2 + 1; end1 = start1 + gap -
1; start2 = end1 + 1; end2 = start2 + gap - 1 < a.length - 1 ? start2 + gap - 1
: a.length - 1;// If there is only the first group at the last time , Not enough for the second group , Exit loop } while (i < a.length) tmpa[i++] =
a[start1++];// Fill in the first group for the last time for(int j = 0;j<a.length;j++) a[j] =
tmpa[j];// Copy the temporary array to the original array }

Technology
Daily Recommendation