Code implementation and introduction of all commonly used sorting

stability

After sorting, it is stable without changing the relative order

Internal sorting

Sorting in which all data elements are placed in memory

External sorting

There are too many data elements to put in memory , According to the sorting process ·1 Can no longer move the sorting of data types between internal and external memory

Insertion sort

• The more ordered the data , The lower the time complexity .
• Specific stability

Slowest time complexity ： O(n^2)

Fastest time complexity ： O(n)

Spatial complexity ：O(1)

public static void insertSort(int[] array){
    
        for (int i = 1; i < array.length; i++) {
    
            int tmp = array[i];
            int j;
            for (j = i-1; j >= 0; j--) {
    
                if (array[j] > tmp) array[j + 1] = array[j];
                else break;
            }
            array[j+1] = tmp;
        }
    }

Shell Sort

• Group first and then insert and sort , Make full use of the characteristics that the more ordered the insertion sort, the lower the time complexity
• It's not stable

Time complexity ：O(n^1.3 ~ n^1.5)

Spatial complexity ：O(1)

 private static void shell(int[] array,int gap){
    
        for (int i = gap; i < array.length; i++) {
    
            int 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;
        }
    }

    public static void shellSort(int[] array){
    
        for(int i=array.length-1;i>=1;i--){
    
            shell(array,i);
        }
    }

Selection sort

• Except for beginners, it's easy to understand , There are no other advantages
• It's not stable

Time complexity ：O(n^2)

Spatial complexity ：O(1)

 public static void selectSort(int[] array){
    
        for (int i = 0 ; i < array.length; i++) {
    
            int min_index = i;
            for (int j = i; j < array.length; j++) {
    
                if(array[min_index] > array[j]){
    
                    min_index = j;
                }
            }
            swap(min_index,i,array);
        }
    }

Heap sort

• The only quick sort that doesn't need extra space
• It's not stable

Time complexity ：O(n^logn)

Spatial complexity ：O(1)

 private static void shiftDown(int parent,int[] elem,int limit){
    
        int child = 2*parent + 1;
        while(child < limit){
    
            if(child+1 < limit && elem[child] < elem[child + 1]){
    
                child++;
            }
            if(elem[parent] < elem[child]){
    
                swap(parent,child,elem);
                parent = child;
                child = 2*parent + 1;
            }
            else break;
        }
    }

    public static void heapSort(int[] array){
    
        for(int parent = (array.length-1-1)/2; parent >= 0; parent--){
    
            shiftDown(parent,array,array.length);
        }
        for (int i = array.length-1; i >= 0; i--) {
    
            swap(0,i,array);
            shiftDown(0,array,i);
        }
    }

Bubble sort

• With stability

Time complexity ：O(n^2)

If we judge whether there is exchange in each cycle, we can reduce the time complexity , Make its fastest time complexity reach 0(n)

Spatial complexity ：O(1)

public static void bubbleSort(int[] array){
    
        for (int i = 0; i < array.length-1; i++) {
    
            for (int j = 0; j < array.length-i-1; j++) {
    
                if(array[j] > array[j+1])
                    swap(j,j+1,array);
            }
        }
    }

Quick sort

• Average fastest sort
• It's not stable

Time complexity ：O(nlogn)

Slowest time complexity ：O(n^2)

Spatial complexity ：O(logn)

The worst spatial complexity ：O(n)

public static void partition(int start,int end,int[] array){
    
        if(start >= end)return;
        int key = array[start];
        int l = start,r = end;
        while(l < r){
    
            while(l < r && array[r] >= key)r--;
            array[l] = array[r];
            while(l < r && array[l] <= key)l++;
            array[r] = array[l];
        }

        array[l] = key;
        partition(start,l-1,array);
        partition(l+1,end,array);
    }

    public static void quickSort(int[] array){
    
        partition(0,array.length-1,array);
    }

Such a quick sort has many disadvantages , For example, if the array is ordered , This requires opening up n A function stack frame , On the one hand, it greatly increases the time complexity , Degenerate to O(n^2) Level , On the other hand, sorting an ordered array with hundreds of thousands of data will overflow the stack . So we can optimize the fast platoon .

• The reason why this happens to ordered arrays , In the final analysis, it is because the dividing point we take each time is the first number of each recursive interval , The simplest idea is that we can choose the dividing point randomly , In this way, the problem of opening up a large number of function stack frames is better avoided . But random is not stable enough , Another common way is to compare the three numbers in each interval , Let's take the leftmost side of the interval , The rightmost and middle are the three numbers , Take the number in the middle of them as the dividing point , This almost perfectly avoids the problem of opening up a large number of function stack frames .（ Find the dividing point and directly exchange the number with the first number in the interval ）

• Secondly, we can use insert sort directly in the last few recursions , Because the insertion sort is the more ordered the interval, the lower the time complexity , In the last two recursions, the interval has been basically ordered , So there is almost no difference in time between using insert sort and quick sort . meanwhile , Using insert sort optimization can also reduce the development of function stack frames .

Optimized quick sort

    public static void insertSort(int start,int end,int[] array){
    
        for (int i = start+1; i <= end; i++) {
    
            int tmp = array[i];
            int j;
            for (j = i-1; j >= 0; j--) {
    
                if (array[j] > tmp) array[j + 1] = array[j];
                else break;
            }
            array[j+1] = tmp;
        }
    }
    
    private static int getPrivot(int a,int b,int c,int[] array){
    
        if( array[a] <=  array[b]){
    
            if(array[b]<=array[c])return b;
            else{
    
                if (array[c]<= array[a])return  a;
                else return c;
            }
        }

        if( array[a] >=  array[b]){
    
            if( array[c] >=  array[a])return a;
            else{
    
                if( array[c] >=  array[b])return c;
                else return b;
            }
        }
        return -1;
    }
    public static void partition(int start,int end,int[] array){
    
        if(end - start < 7){
    // Insert sort optimization 
            insertSort(start,end,array);
            return;
        }
        if(start >= end)return;

        int l = start,r = end;
        int privot = getPrivot(start,end,start+end>>1,array);
        swap(start,privot,array);
        int key = array[start];
        while(l < r){
    
            while(l < r && array[r] >= key)r--;
            array[l] = array[r];
            while(l < r && array[l] <= key)l++;
            array[r] = array[l];
        }

        array[l] = key;
        partition(start,l-1,array);
        partition(l+1,end,array);
    }

    public static void quickSort(int[] array){
    
        partition(0,array.length-1,array);
    }

    public static void main(String[] args) {
    
        int[] array = {
    4,9,12,12,4,5,9,2,8,6,0,9,5};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Merge sort

• Time complexity ：O(nlogn)

• Spatial complexity ：O(n)

• With stability

import java.util.Arrays;

public class MergeSort {
    
    private static void merge(int start, int end, int[] array){
    
        if(start >= end)return;
        int mid = start+end>>1;
        merge(start,mid,array);
        merge(mid+1,end,array);

        int s1 = start;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = end;

        int[] tmp = new int[end - start + 1];
        int index = 0;
        while(s1 <= e1 && s2 <= e2){
    
            if(array[s1] <= array[s2])tmp[index++] = array[s1++];
            else tmp[index++] = array[s2++];
        }
        while(s1 <= e1){
    
            tmp[index++] = array[s1++];
        }
        while( s2 <= e2){
    
            tmp[index++] = array[s2++];
        }
        index = start;
        for (int i = 0; i < tmp.length; i++) {
    
            array[index++] = tmp[i];
        }
    }

    public static void mergeSort(int[] array){
    
        merge(0,array.length-1,array);
    }

    public static void main(String[] args) {
    
        int[] array = {
    4,6,2,8,3,6,4,7,9,3,6,5,4,6,8,9,12,14,13};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Sort the summary

Sorting method	best	Average	The worst	Spatial complexity	stability
Bubble sort	O(n)	O(n^2)	O(n^2)	O(1)	Stable
Insertion sort	O(n)	O(n^2)	O(n^2)	O(1)	Stable
Selection sort	O(n^2)	O(n^2)	O(n^2)	O(1)	unstable
Shell Sort	O(n)	O(n^1.3)	O(n^2)	O(1)	unstable
Heap sort	O(n * log(n))	O(n * log(n))	O(n * log(n))	O(1)	unstable
Quick sort	O(n * log(n))	O(n * log(n))	O(n^2)	O(log(n)) ~ O(n)	unstable
Merge sort	O(n * log(n))	O(n * log(n))	O(n * log(n))	O(n)	Stable