Catalog

1. stability

2. Bubble sort

3. Insertion sort

3.1   Binary Insertion Sort

4. Shell Sort

5. Selection sort

6. Heap sort

7. Quick sort （ Excavation method ）

8. Merge sort

 9.  The sorting problem of massive data

1. stability

Two equal numbers , If after sorting , Sorting algorithm can ensure that its relative position does not change , Then we call the algorithm a stable sorting algorithm .

44 2 a1 4 63 56 a2 34  After ordering  2 a1 4 34 44 63 56 a2 

The relative position has not changed

2. Bubble sort

    public void bubbleSort(int[] arr){
        // The outermost layer represents the number of trips to compare ,arr.length - 1,- 1  Because when there is only one element left in the array to be sorted , At this point, the array has been ordered 
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if(arr[j] > arr[j + 1]){
                    swap(arr,j,j + 1);
                    flag = true;
                }
            }
            if(flag == false){
                // There is no element exchange in the inner loop , The whole array is ordered 
                break;
            }
        }
    }

Time complexity ：O(N^2)    For better or worse  O(N^2) 

Spatial complexity ：O(1) 

Stable

3. Insertion sort

The whole interval is divided into Ordered interval and Disordered interval

Each choice Disordered interval The first element of , stay Ordered interval Select the appropriate position to insert

public void insertSort(int[] array) {
    for(int i = 1; i < array.length; i++) {
        int tmp = array[i];
        int j = i - 1;
        for(; j >= 0; j--) {
            if(array[j] > tmp) {
                array[j + 1] = array[i];  // Exchange the position of the previous number with the next number 
            } else {
                break;
            }
        }
        array[j + 1] = tmp;
    }
}

  Time complexity ：O(N^2) 

Spatial complexity ：O(1) 

Stable

Direct insert sort , Orderly case is O(N), because , When array[j] > tmp when , direct break,j Not again --.

3.1   Binary Insertion Sort

In the already An ordered array Insert a number （ It is often used when there is not much data , In regionally ordered data ）

Suppose there are now 10000 Number , If you sort this group of data , Use insert sort .

10000 Time complexity of data ：10000 * 10000 = 10000 0000

10000 Data = 100 Group * 100 individual , branch 100 Group , The time complexity of each group is 100 * 100 = 10000

From this we can find , Grouping makes time complexity change a lot .

4. Shell Sort

also called Reduction increment method .

Choose an integer first , Divide all records in the file to be sorted into n A set of , All distances are n The records are grouped in the same group , And sort the records in each group . Then repeat the above grouping and sorting . When grouping equals 1 when , All records are arranged in a unified group .

1. Hill's ranking is right Optimization of direct insertion sorting .

2. When gap > 1 It's all pre sorted , The goal is to make arrays more ordered . When gap == 1 when , The array is nearly ordered , This will soon . So on the whole , Can achieve the effect of optimization .

public static void shellSort(int[] array) {
    int gap = array.length;
    while(gap > 1) {
        shell(array, gap);
        gap /= 2;
    }
    shell(array, 1); // Make sure the end is 1 Group , Sort the entire array 
}
public static void shell(int[] array, int gap) {
    for(int i = 1; i < array.length; i++) {
        int tmp = array[i];
        int j = i - gap;
        for(; j >= 0; j -= gap) {
            if(array[j] > tmp) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        array[j + gap] = tmp;
    }
}

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

Spatial complexity ：O(1) 

unstable

In the process of comparison , See if there is a jumping Exchange , If it is jumping , Is unstable sorting . 

5. Selection sort

  Each time, the largest... Is selected from the unordered interval （ Or the smallest ） An element of , At the end of the unordered interval （ Or first ）, Until all the data elements to be sorted are finished .

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]) {
                swap(array,j,i);
            }
        }
    }
}

public static void swap(int[] array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

Time complexity ：O(N^2)

Spatial complexity ：O(n) 

unstable

  Direct insert sort , Orderly case is O(N), because , When array[j] > tmp when , direct break,j Not again --.

Select sort to say , Order and disorder are O(N^2) , Because of the time complexity ！= The elapsed time . In an orderly situation , Choosing to sort takes more time ,j++ It won't decrease .

6. Heap sort

  In ascending order, a lot of ; In descending order, build small piles

  Adjust to large root heap , The maximum value must be at the top of the heap , Exchange it with the last element , At this time, the maximum value of the last element in place , Then I'll take the rest n - 1 The reconstruction of elements is called a heap , Perform this step in sequence .

    public void heapSort(int[] arr){

        //1. Sort any array in place 
        // Start with the last non leaf node , That is, the parent node of the last leaf node 
        // The last leaf node arr.length - 1 ,  Parent node （arr.length - 1 - 1）/2
        for (int i = (arr.length - 1 - 1) / 2; i >= 0 ; i--) {
            siftDown(arr,i,arr.length);
        }
        // Take out the top element and the last position element in turn for Exchange 
        // In the beginning , Array to sort [0......arr.length - 1], Sorted array []
        // The second time , Array to sort [0......arr.length - 2], Sorted array [arr.length - 1]
        // third time , Array to sort [0......arr.length - 3], Sorted array [arr.length - 2,arr.length - 1]
        //......

        // here i > 0, Do not write i = 0, Because when there is only one element left in the array , The array is in order 
        for (int i = arr.length - 1; i > 0 ; i--) {
            // The first 0 Elements , Swap with the last element 
            swap(arr,0,i);
            // The last element does not need to consider sinking 
            siftDown(arr,0,i);
        }
    }

    /**
     *  Element sinking operation 
     * @param arr
     * @param i  Parent node 
     * @param n  At present arr Number of valid elements in the 
     */
    private void siftDown(int[] arr, int i, int n) {
        // Termination conditions ： There are still subtrees ( Subtree is less than the number of effective elements )
        while((2 * i) + 1 < n){
            int j = 2 * i + 1;
            // The right child exists and is larger than the left subtree 
            if(j + 1 < n && arr[j + 1] > arr[j]){
                j = j + 1;
            }
            if(arr[i] >= arr[j]){
                break;
            }else {
                swap(arr,i,j);
                i = j;
            }
        }
    }

Time complexity ：O(N * logN)

Spatial complexity ：O(1) 

unstable

7. Quick sort （ Excavation method ）

1. Select a number from the range to be sorted , As At baseline (pivot);

2. Partition: Traverse the entire range to be sorted , Will be smaller than the benchmark （ Can contain equal ） To the left of the reference value , Will be larger than the benchmark value （ Can contain equal ） To the right of the reference value ;

3. use Divide and conquer thoughts , Treat the left and right cells in the same way , Until the length between cells == 1, The representatives are in order , Or the length between cells == 0, It means there's no data .

（ optimization algorithm ） How to find the benchmark ：

Take the middle of three

Random method

Put the same data as the benchmark , Move together from both sides

Sort by direct insertion

    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 pivot = partition(array, left, right);
        quick(array,left,pivot - 1);
        quick(array,pivot + 1, right);
    }

    private static int partition(int[] array, int start, int end) {
        int tmp = array[start];
        while(start < end) {
            while(start < end && array[end] >= tmp) {  
                //start < end  Join a  12345,end-- Will make end < start , So we still need to add this condition 
                end--;
            }
            array[start] = array[end];
            while(start > end && array[start] <= tmp) {
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;// here start and end meet 
        return start;
    }
    

  Time complexity ：O(N * logN) （ Equivalent to a binary tree , Every layer of a binary tree is n）

Spatial complexity ：O(logN)   ( recursive , Keep the previous state ) 

unstable

  Time complexity ：

        The best situation ： The sequence to be sorted can be evenly divided each time O(N * logN) 

         The worst ： Data order , Or in reverse order O(N^2)

Spatial complexity :

         The best situation ： O(logN) 

         The worst ： A single branch tree O(N) 

8. Merge sort

  Merge sorting is an effective sorting algorithm based on merge operation , The algorithm adopts Divide and conquer method A very typical application . Merges ordered subsequences , You get a perfectly ordered sequence ; So let's make each subsequence in order , Zaizi Order between sequence segments . If two ordered tables are merged into one ordered table , It's called a two-way merge .

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

    private static void mergeSortInternal(int[] array, int low, int high) {
        int mid = low + ((high - low) >>> 1);
        mergeSortInternal(array, low, mid);
        mergeSortInternal(array, mid + 1, high);
        merge(array, low, mid, high);
    }

    private static void merge(int[] array, int low, int mid, int high) {
        int[] tmp = new int[high - low + 1];
        int k = 0;
        int s1 = low;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = high;
        while(s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            } else {
                tmp[k++] = array[s2++];
            }
        }
        while(s1 <= e1) { //  here s2 Has traversed 
            tmp[k++] = array[s1++];
        }
        while(s2 <= e2) {
            tmp[k++] = array[s2++];
        }
        for (int i = 0; i < k; i++) { // take tmp Copy the array elements in to the original array in 
            array[i + low] = tmp[i];
        }
    }

 

  Time complexity ：O(N * logN) 

Spatial complexity ：O(N) 

Stable

 9.  The sorting problem of massive data

Memory only 1G, The data to be sorted are 100G

Because we can't put all the data in memory , So you need an external sort , Merge sort is the most commonly used external sort

1. First cut the file into 200 Share , Every 512 M

2. Respectively for 512 M Sort , Because the memory can be put down , So any sort can

3. Conduct 200 Road merging , At the same time 200 An orderly document to do the merging process , The end result is orderly