Several common sorting methods
one , Direct insertion sort
Insertion sorting is a simple and intuitive sorting algorithm . Orderly construction sequence , For unsorted data , Scan back and forward in sorted sequence , Locate and insert . Insert sort is in the process of scanning from back to front , You need to repeatedly move the sorted elements back step by step , Provide insertion space for the latest elements .
algorithm ：
Treat the sequence to be sorted as an array ,i Initialize pointing array 1 Subscript No ,j Initialize pointing array 0 Subscript No , and i Compare the corresponding values , Compare once and take a step back , If j The corresponding value is greater than i Corresponding value , Exchange values , until i The previous numbers are smaller than it ,i turn back and proceed .
Time complexity ：（1） At worst O（n^2）
(2) The best case is orderly ：O（n）
Spatial complexity ：O（1）
stability ： stable
code ：
public static void insertSort(int[] array){ int tmp = 0; int j ; for(int i=1;
i<array.length; i++){ tmp = array[i]; for( j=i-1; j>=0; j--){ if(array[j] >
tmp){ array[j+1] = array[j]; // Change position }else{ // array[j+1] = tmp; // Don't change it , Put it back in place
break; } } array[j+1] = tmp; // Don't change it , Put it back in place } }
two , Shell Sort
Hill sort is also a kind of insertion sort , It adopts the idea of grouping , Insert and sort each group .
code ：
public static void shellSort(int[] array){ int[] drr = {5,3,1}; for(int i = 0;
i<drr.length; i++){ shell(array,drr[i]); } } public static void shell(int[]
array,int gap){ int tmp = 0; for(int i = gap; i<array.length; i++){ tmp =
array[i]; int j; for(j=i-gap; j>=0; j-=gap){ if(array[j]>tmp){ array[j+gap] =
array[j]; }else { break; } } array[j+gap]=tmp; } }
three , Select sort
Algorithmic thought ：
Start with the first number of the array , Compare this number with all the numbers after this number , If it is smaller than this number, exchange it , Then compare the second number of the array with all the numbers after it , I traded when I was younger than him , and so on , Until the last number in the array .
code ：
public static void selectSort(int[] array){ for(int i=0; i<array.length;
i++){ for(int j=i+1; j<array.length; j++){ if(array[j]<array[i]){ int tmp =
array[i]; array[i] = array[j]; array[j] = tmp; } } } }
Time complexity ：O（n^2）
Spatial complexity ：O（1）
stability ： instable
four , Heap sort
First, build the array into a large root heap , Start with the last number in the array , And array 0 Exchange subscript numbers , Then use the downward adjustment method . Then add the penultimate number and array 0 Exchange subscript numbers , Then use the downward adjustment method , and so on , until 0 Subscript number .
code ：
public static void heapSort(int[] array){ creatHeap(array); int end =
array.length-1; while(end>0){ int tmp = array[end]; array[end] = array[0];
array[0] = tmp; adjustDown(array,0,end); end--; } } // Build large root pile public static void
creatHeap(int[] array){ for(int i = (array.length-1-1)/2; i>=0; i--){
adjustDown(array,i,array.length); } } // Downward adjustment method public static void
adjustDown(int[] array,int root,int len){ int patrnt = root; int child =
root*2+1; // At least there are left children while(child<len){ // There are right children and the left child is smaller than the right child , Exchange if(child+1<len &&
array[child]<array[child+1]){ int tmp = array[child]; array[child] =
array[child+1]; array[child+1] = tmp; } // If the left child is larger than the father , To exchange if (array[child] >
array[patrnt]) { int tmp = array[child]; array[child] = array[patrnt];
array[patrnt] = tmp; patrnt = child; child = patrnt*2+1; }else{ break; } } }
Time complexity ：O（nlogn）
Spatial complexity ：O（1）
stability ： instable
five , Bubble sorting
Bubble sorting is that each trip starts with the first number , Compare each number of the array with the next number after it , Exchange when you are younger than it . So back and forth , Until the sequence is ordered .
code ：
public static void bubleSort(int[] array){ //i Indicates the number of trips for(int i=0;
i<array.length-1; i++){ for(int j=0; j<array.length-1-i; j++){
if(array[j]>array[j+1]){ int tmp = array[j]; array[j] = array[j+1]; array[j+1]
= tmp; } } } }
Time complexity ：O（n^2）
Spatial complexity ：O（1）
stability ： instable
six , Quick sort
Quick sort , Also known as partition exchange sort . The data to be sorted is divided into two parts by one sorting , Then quickly sort the two parts of data according to this method , In this way, the whole data becomes an ordered sequence
Step is ：
（1） Find an element from the sequence , be called “ benchmark ”.
（2）
Reorder sequence , All elements smaller than the benchmark value are placed in front of the benchmark , All elements larger than the datum value are placed behind the datum . After this partition is completed , The benchmark is in the middle of the sequence . This is called partition operation .
（3） The numerical sequence on the left of the reference element is quickly sorted by recursive method , The same is true for the right sequence . Until the whole sequence is in order .
code ：
public static void quickSort(int[] array){ quick(array,0,array.length-1); }
public static void quick(int[] array,int left,int right){ if(left>=right){
return; } int par = partition(array,left,right); // Recursively sort left and right
quick(array,left,par-1); quick(array,par+1,right); } // Find benchmark public static int
partition(int[] array,int left,int right){ int tmp = array[left];
while(left<right){ while(left<right && array[right]>=tmp){ right--; }
array[left]=array[right]; while(left<right && array[left]<=tmp) { left++; }
array[right] = array[left]; } array[left] = tmp; return left; }
Time complexity ：O（nlogn）
Worst case scenario ：1 2 3 4 5 6 7 8 9 / 9 8 7 6 5 4 3 2 1 ：O（n^2）
Spatial complexity ：O(logn)~O（n）
stability ： instable
seven , Merge sort
Merging and sorting adopts the divide and conquer method , The idea is to decompose the array into numbers one by one （ Split the array in two from the middle , Then recursively decompose the left and right ）, Recombine arrays .
The basic idea of merging is to compare the first number of two arrays , Take whoever is young first , After taking the corresponding direction, move it back one bit . Then compare , Until an array is empty , Finally, copy the rest of another array .
code ：
public static void mergeSort(int[] array){
mergeSortIn(array,0,array.length-1); } // decompose public static void
mergeSortIn(int[] array,int low,int high){ if(low>=high){ return; }
// decompose （ Split into two from the middle of the array , Until it is decomposed into numbers one by one ） int mid = (low+high)>>>1; // Moving right is equivalent to dividing 2
mergeSortIn(array,low,mid); mergeSortIn(array,mid+1,high); // Merge （ Merge the numbers one by one in order ）
merge(array,low,mid,high); } // Merge public static void merge(int[] array,int
low,int mid,int high){ int s1 = low; int s2 = mid+1; int len = high-low+1;
// Length of new array int[] ret = new int[len]; // Create a new array to store the numbers after merging and sorting int i = 0; // express ret Subscript of array
while (s1<=mid && s2<=high){ if(array[s1] <= array[s2]){ ret[i++] =
array[s1++]; }else { ret[i++] = array[s2++]; } } while (s1<=mid){ ret[i++] =
array[s1++]; } while (s2<=high){ ret[i++] = array[s2++]; } for(int j= 0;
j<ret.length; j++){ array[j+low] = ret[j]; } }
Time complexity ：nlogn
Spatial complexity ：O(n)
stability ： stable
Technology