One , Insert sort

1.1 Direct insert sort

Spatial complexity ：.

Time complexity ：. In the best case , Elements in the table are ordered , At this time, every element is inserted , You only need to compare them once without moving the elements , So the time complexity is .

stability ： Every time you insert an element, always compare and move from the back to the front , So the relative position of the same element will not change . That is to say, direct insertion sort is a stable sort method .
public class InsertSort { public static void insertSort(int[] array,int n) {
int i=0; int j=0; for(i=1;i<n;i++) {// Unordered area to be sorted int t=array[i];
for(j=i-1;j>=0&&t<array[j];j--) {// Ordered area array[j+1]=array[j]; }
array[j+1]=t; } } public static void main(String[] args) { int[] a=
{4,0,2,3,1}; insertSort(a, 5); for(int n:a) { System.out.print(n+" "); } } }

1.2 Shell Sort

Spatial complexity ：.

Time complexity ： When n When in a certain range , The time complexity of hill sorting is about . In the worst case, the time complexity of Hill sort is .

stability ： When records with the same key are divided into different sub tables , May change the relative order between them , So Hill sort is an unstable sort method .
public static void shell(int value[],int n,int start,int step)     {
int i = 0;         for(i = start + step;i < n;i += step)         {
int temp = value[i];             int j = 0;             for(j = i - step;j >=
start && value[j] > temp;j -= step)             {                 value[j +
step] = value[j];             }             value[j + step] = temp;         }
}     public static void shellSort(int value[],int n)     {         int
step = n / 2;         while(step > 0)         {             int i = 0;
for(i = 0;i < step;i++)             {                 shell(value,n,i,step);
}             step /= 2;         }     }     public static void
main(String[] args){         int value[] = {8,3,6,2,4,5,7,1,9,0};
shellSort(value,10);         System.out.println(" The sorted result is ：");         int i =
0;         for(;i < 10;i++) {             System.out.print(value[i]);         }
}
Two , Exchange sort

2.1 Bubble sorting

Spatial complexity ：.

Time complexity ： Worst case , Best case （ The elements in the table are basically in order ）. The average time complexity is .

stability ： stable .
public class BubbleSort { public static void bubbleSort(int[] array,int n) {
for(int i=0;i<n-1;i++) { boolean flag=false; for(int j=n-1;j>i;j--) {
if(array[j-1]>array[j]) { int t=array[j-1]; array[j-1]=array[j]; array[j]=t;
flag=true; } } if(flag==false) { return; } } } public static void main(String[]
args) { int[] a= {3,8,7,1,2,5,6,4}; bubbleSort(a, 8); for(int n:a) {
System.out.print(n+" "); } } }
2.2 Quick sort

Spatial complexity ： Because quicksort is recursive , It is necessary to save the necessary information of each layer of recursive call with the help of a recursive work stack , Its capacity should be consistent with the maximum depth of recursive calls . Best case
. Worst case , Because it's going to be n-1 Recursion calls , So the depth of the stack is . On average , Depth of stack .

Time complexity ： The worst case scenario for quick sorting occurs in two areas n-1 Elements and 0 When elements , This maximum asymmetry occurs at every level of recursion , That is, when the initial sorting table is basically in order or basically in reverse order , We get the worst-case time complexity . At its best （ Balance Division ）, Time complexity is
. Fast sorting is the best sorting algorithm with the best average performance among all internal sorting algorithms .

stability ： instable .

public class QuickSort { public static void quickSort(int[] array,int low,int
high) { if(low<high) { int index=partition(array,low,high); quickSort(array,
low, index-1); quickSort(array, index+1, high); } } public static int
partition(int[] array,int low,int high) { int pivot=array[low]; while(low<high)
{ while(low<high&&array[high]>=pivot) { --high; } array[low]=array[high];
while(low<high&&array[low]<=pivot) { low++; } array[high]=array[low]; }
array[low]=pivot; return low; } public static void main(String[] args) { int[]
a= {3,8,7,1,2,5,6,4}; quickSort(a, 0,7); for(int n:a) { System.out.print(n+"
"); } } }
Three , Select sort

3.1 Simple selection sorting

Spatial complexity ：.

Time complexity ： As can be seen from the following code , Simple selection sorting process , Very few element moves , Not more than times
（ once swap need 3 Subelement movement ）, The best case is mobile 0 second , At this time, the corresponding table is in order . But the number of element comparisons is independent of the initial state of the sequence , Always next . So time complexity is .

stability ： instable .

public class SelectSort { public static void selectSort(int[] array,int n) {
for(int i=0;i<n-1;i++) { int min=i; for(int j=i+1;j<n;j++) {
if(array[j]<array[min]) { min=j; } } if(min!=i) { int temp=array[min];
array[min]=array[i]; array[i]=temp; } } } public static void main(String[]
args) { int[] a= {3,8,7,1,2,5,6,4}; selectSort(a,8); for(int n:a) {
System.out.print(n+" "); } } }
3.2 Heap sort

Spatial complexity ： Use only constant auxiliary units , So the space complexity is .

Time complexity ： At the best , Worst case and average case , The time complexity of heap sorting is .

stability ： instable .

Four , Merge sort

4.1 merge sort

Spatial complexity ：Merge() In operation , Because the auxiliary space is just about to be occupied n Units , But every time they merge, these spaces are released , So the spatial complexity of merging and sorting is .

Time complexity ： The time complexity of each merging is , It is necessary to merge , So the time complexity of the algorithm is .

stability ： stable .
public class MergeSort { public static void mergeSort(int[] array,int low,int
high) { if(low<high) { int mid=(low+high)/2; mergeSort(array, low, mid);
mergeSort(array, mid+1, high); merge(array,low,mid,high); } } public static
void merge(int[] array,int low,int mid,int high) { int[] num=new
int[array.length]; for(int k=low;k<=high;k++) { num[k]=array[k]; } int i=low;
int j=mid+1; int k=i; for(;i<=mid&&j<=high;k++) { if(num[i]<num[j]) {
array[k]=num[i++]; }else { array[k]=num[j++]; } } while(i<=mid) {
array[k++]=num[i++]; } while(j<=high) { array[k++]=num[j++]; } } public static
void main(String[] args) { int[] a= {3,8,7,1,2,5,6,4}; mergeSort(a, 0,7);
for(int n:a) { System.out.print(n+" "); } } }

Technology
Daily Recommendation