1. Hill sort

Hill sort is a kind of insertion sort, which is a more efficient sort algorithm

1.1 sorting principle

1. Select a growth amount h and group the data according to the growth amount h as the basis for data grouping
2. Insert and sort each group of data divided into groups
3. Reduce the growth to 1 at least, and repeat the operation in step 2

Determination of growth amount H: there is no fixed rule for the value of growth amount h, and the following rules are adopted here:

int h = 1;
while(h < N){ // Here N is the length of the array
    h = 2 * h + 1;
}
// At the end of the cycle, the maximum value of h can be determined
// The reduction rule of h is:
    h = h / 2;

1.2 API design

Class name	Shell
Construction method	Shell(): create shell object
Member method	1. public static void sort(Comparable[] a): sort the elements in the array 2. private static greater(Comparable v, Comparable w): judge whether element v is greater than W 3. private static exch(Comparable[] a, int i, int j): exchange the values at indexes I and j in array a

Implementation code 1.3

package sort;

public class Shell {
    public static void sort(Comparable<Integer>[] a) {
        // 1. Determine the initial value of the growth amount h according to the length of array a
        int h = 1;
        while (h < a.length / 2) {
            h = 2 * h + 1;
        }

        // 2. Hill sort
        while (h >= 1) {
            // sort
            // 1. Find the element to be inserted
            for (int i = h; i < a.length; i++) {
                // 2. Insert the elements to be inserted into the ordered sequence
                for (int j = i; j >= h; j -= h) {
                    // The element to be inserted is a[j]. Compare a[j] and a[j-h]
                    if (greater(a[j - h], a[j])) {
                        exch(a, j - h, j);
                    } else {
                        break;
                    }
                }
            }

            // Decrease the value of h
            h = h / 2;
        }
    }

    private static boolean greater(Comparable<Integer> v, Comparable<Integer> w) {
        // Compare whether element v is greater than element w
        return v.compareTo((Integer)w) > 0;
    }

    private static void exch(Comparable<Integer>[] a, int i, int j) {
        //Swap the values at indexes i, j in array a
        Comparable<Integer> temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

Pointer i always points to the next element to be sorted, but since there will be 2 or more groups in the same queue for insertion sorting at the same time, the next element to be inserted pointed to by pointer i always alternates between different groups The j pointer will initially point to the elements to be inserted in a group, and then follow the elements to be inserted until the appropriate position is found, just like the insertion sort

1.4 time complexity analysis

There is no fixed rule for the growth amount h in Hill ranking, which is beyond the scope of this paper However, post analysis can still be used to compare the performance of Hill sort and insert sort Generally speaking, the performance of Hill sort is better than insert sort

2. Merge and sort

Merging and sorting embodies the idea of divide and conquer

2.1} sorting principle

1. Split a set of data into two subgroups with equal elements as far as possible, and continue to split each subgroup until the number of elements in each subgroup after splitting is 1
2. Merge two adjacent subgroups and sort them at the same time to form an ordered large group
3. Repeat step 2 until there is only one group

2.2 API design

Class name	Merge
Construction method	Merge(): create a merge object
Member method	1. public static void sort(Comparable[] a): sort the elements in array a 2. Private static sort (Comparative [] A, int lo, int HI): sort the elements in array a from index lo to hi 3. private static void merge(Comparable[] a, int lo, int mid, int hi): from index lo to mid is a subgroup, and from index mid+1 to hi is another subgroup. Merge and sort the data of these two subgroups in array a to form an ordered large group (from index lo to hi) 4. private static boolean less(Comparable v, Comparable w): judge whether element v is less than element W 5. private static void exch(Comparable[] a, int i, int j): exchange the values at indexes I and j in array a
Member variable	1. private static Comparable[] assist: the auxiliary array needed to complete the merge operation

Merging principle:

2.3 code implementation

package sort;

public class Merge {
    // Auxiliary array required for merging
    private static Comparable<Integer>[] assist;

    public static void sort(Comparable<Integer>[] a){
        // Initialize auxiliary array
        assist = new Comparable[a.length];
        // Define lo and hi variables to record the smallest index and the largest index in the array respectively
        int lo = 0;
        int hi = a.length - 1;
        // Call the sort overloaded method to sort the elements in array a from index lo to hi
        sort(a, lo, hi);
    }

    private static void sort(Comparable<Integer>[] a, int lo, int hi){
        // Sort the elements from lo to hi in array a
        // Security verification
        if(hi <= lo){
            return;
        }

        // Divide the data between lo and hi into two groups
        int mid = lo + (hi - lo) / 2;

        // Sort each group of data separately
        sort(a, lo, mid);
        sort(a, mid + 1, hi);

        // Merge the data in the two arrays
        merge(a, lo, mid, hi);
    }

    private static boolean less(Comparable<Integer> v, Comparable<Integer> w){
        // Compare whether element v is smaller than element w
        return v.compareTo((Integer)w)<0;
    }

    private static void merge(Comparable<Integer>[] a, int lo ,int mid, int hi){
        // In array a, from lo to mid is a group, and from mid+1 to hi is a group. Merge the two groups of data
        // Define three pointers
        int i = lo;
        int p1 = lo;
        int p2 = mid + 1;

        /*
        Traverse, move the p1 and p2 pointers, and compare the values at the corresponding indexes,
        Find the smaller value and put it at the corresponding index in the auxiliary array
        */
        while (p1 <= mid && p2 <= hi){
            // Compare values at index
            /*
            Note that the if judgment condition here will make the merging algorithm unstable, 
            Only when the condition is changed to < = can the merging algorithm become stable
            */
            if(less(a[p1], a[p2])){
                assist[i++] = a[p1++];
            } else {
                assist[i++] = a[p2++];
            }
        }

        // Traverse. If the p1 pointer is not finished, move the other p1 pointer in sequence and put the corresponding elements into the auxiliary array one by one
        while(p1 <= mid){
            assist[i++] = a[p1++];
        }

        // Traverse. If the p2 pointer is not finished, move the other p2 pointer in sequence and put the corresponding elements into the auxiliary array one by one
        while(p2 <= hi){
            assist[i++] = a[p2++];
        }

        // Copy the elements in the auxiliary array to the original array
        for (int index = lo; index <= hi; index++){
            a[index] = assist[index];
        }
    }
}

2.4 time complexity analysis

The time complexity of merging and sorting is O(nlogn)
;) 

3. Quick sort

Quick sort is an improvement of bubble sort Its basic idea is to divide the data to be sorted into two independent parts through one-time sorting. All the data in one part is smaller than the other part, and then quickly sort the two parts of data according to this method. The whole sorting process can be carried out recursively, so as to turn the whole data into an ordered sequence

3.1 sorting principle

1. First set a boundary value and divide the array into left and right parts Generally, the boundary value can take the first data in the array
2. Put the data greater than or equal to the boundary value to the right of the array, and the data less than the boundary value to the left of the array At this time, all elements in the left part are less than or equal to the boundary value, while all elements in the right part are greater than or equal to the boundary value;
3. Then, the data on the left and right can be sorted independently. For the data on the left, you can take a boundary value and repeat the classification in step 2 The array on the right does the same
4. In this way, the data on the left and right sides are numbered recursively, and the sorting of the whole array is completed

3.2 API design

Class name	Quick
Construction method	Quick(): create a quick object
Member method	1. public static void sort(Comparable[] a): sort the elements in the array 2. private static void sort (Comparable[] a, int lo, int hi): sort the elements in array a from index lo to hi 3. private static int partition(Comparable[] a, int lo, int hi): group the elements in array a from index lo to hi, and return the index corresponding to the boundary value 4. private static void exch(Comparable[] a, int i, int j): exchange the values at indexes I and j in array a

3.3 segmentation principle

1. Find a reference value and point to the head and tail of the array with two pointers respectively
2. Search for an element smaller than the reference value from the tail to the head, stop when the search is reached, and record the position of the pointer;
3. Search an element larger than the reference value from the head to the tail, stop when the search is found, and record the position of the pointer;
4. Exchange the elements of the current left pointer position and the right pointer position;
5. Repeat steps 2, 3 and 4 until the value of the left pointer is greater than that of the right pointer

3.4 code implementation

package sort;

public class QuickSort {
    /*
    Sort the elements in the array
     */
    public static void sort(Comparable[] a){
         int lo = 0;
         int hi = a.length - 1;
         sort(a, lo, hi);
    }

    /*
    Sort the elements from index lo to index hi in array a
     */
    private static void sort(Comparable[] a, int lo, int hi){
        // Security verification is also the basic end condition of iteration
        if (hi <= lo){
            return;
        }

        // Group the arrays from lo to hi in the array
        int partition = partition(a, lo, hi);

        // Continue to sort the left subgroup iteratively
        sort(a, lo, partition - 1);

        // Continue to sort the right subgroup iteratively
        sort(a, partition + 1, hi);
    }

    /*
    Group the elements in array a from index lo to hi, and return the index corresponding to the grouping boundary
     */
    private static int partition(Comparable[] a, int lo, int hi){
        // Create two scan pointers and a key value
        Comparable key = a[lo];
        int left = lo; // Scan elements larger than the key value
        int right = hi + 1; // Scan elements smaller than the key value

        // Segmentation operation
        while (true){
            // Move the right pointer first. If an element smaller than the key value is found, it will stop
            while(less(key, a[--right])){ // If the key value is smaller than the element pointed to by the right pointer, continue
                if(right == lo){ // If the right pointer goes to the left, the scan from right to left ends
                    break;
                }
            }

            // Move the left pointer again. If an element larger than the key value is found, it will stop
            while(less(a[++left], key)){ // If the element pointed to by the left pointer is smaller than the key value, continue
                if (left == hi){ // If the left pointer goes to the right, the technology scans from left to right
                    break;
                }
            }

            // If the two pointers meet or interleave, the scanning has been completed
            if (left >= right){
                break;
            }else { //If there is no encounter, the elements at the two pointer positions are exchanged
                exch(a, right, left);
            }
        }

        // Exchange boundary value and key value
        // Note that the right pointer must be used here for exchange
        exch(a, lo, right);

        // Return boundary value index
        return right;
    }

    /*
    Judge whether v is less than w
     */
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }

    /*
    Swap the values at index i and index j in the a array
     */
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

3.5 time complexity analysis

The time complexity of quick sort is related to the selection of cut-off value
Optimal situation: the cut-off value selected for each segmentation just divides the sequence in front of the house -- O(nlogn)
Worst case: the cut-off value selected for each segmentation is the largest or smallest number in the current sequence, which makes each segmentation have only one subgroup, so it has to be segmented n times in total, so the time complexity is O(n^2)
Average: O(nlogn)