https://en.wikipedia.org/wiki/Quicksort

Quick sort

• Principle: partition continuously by comparing the median value (pivot), until all intervals reach the minimum (capacity is 1), and the result is orderly; When performing the comparison operation, it is the comparison operation from low to high, and the sorting is realized by continuously removing the intermediate value
• All move operations of quick sort are carried out in the original array and do not need additional array space. Therefore, it belongs to in-situ sorting algorithm
• Stability: because the same elements also need to be moved, the relative positions of the same elements before and after sorting may be inconsistent; So quick sort is an unstable sort

Fast scheduling embodies the idea of divide and conquer, but the focus is on zoning. The purpose of zoning is to find the location of the central point, eliminate the central point elements, and continue the zoning steps for the left and right sections;

Fast sorting realizes the purpose of sorting by confirming the central position of each partition point each time and excluding the central element of the determined position for the partition

public interface Sort<T extends Comparable<T>> {
    /**
     * Sort the array
     *
     * @param array
     * @param flag  true It represents positive order; false stands for reverse order
     */
    void sort(T[] array, boolean flag);
}

public class QuickSort<T extends Comparable<T>> implements Sort<T> {

    /**
     * The main idea of fast scheduling is zoning, which achieves the effect of sorting through continuous zoning
     * 5    4   3   2   1
     *                  pivot(Center point)
     * low->Start traversing the current interval high
     * i,j ; When there is array [J] < pivot, exchange array[i],array[j] = array[j],array[i] (golang syntax). At this time, i + 1, move back one bit, and j continues to move back until high. Exchange the current I and high,array[i],array[high] = array[high],array[i]. At this time, I is the center point of the current partition
     * The result after the first partition is that the index of the current pivot is 0(i); The divided interval is [] [1] [4,3,2,5]; Continue zoning from the center point
     *
     * @param array
     * @param flag  true It represents positive order; false stands for reverse order
     */
    @Override
    public void sort(T[] array, boolean flag) {
        sort(array, 0, array.length - 1, flag);
    }

    /**
     * For quick sort, it is actually a process of continuous recursive partition
     *  pivot The element is initially the highest level element of the current partition, high is the previous position of the pivot element, and low is the lowest level element
     *  Realize contrast exchange through low high double pointers
     *
     * @param array
     * @param low
     * @param high
     * @param flag  true For ascending order, false for descending order
     */
    public void sort(T[] array, int low, int high, boolean flag){
        // If the low index value is greater than or equal to the high index value,Indicates that it is not necessary to continue partitioning
        if (low >= high) {
            return;
        }
        // Returns the partition intermediate value index
//        int pivotIndex = partition(array,low,high,flag);
        // Double pointer movement, low and high
        int pivotIndex = partition2(array,low,high,flag);
        // No intermediate elements will be included in the left and right partitions
        // Recursive left partition
        sort(array, low, pivotIndex - 1, flag);
        // Recursive right partition
        sort(array, pivotIndex + 1, high, flag);
    }

    // Double pointer,Through the block, the slow pointer moves from the low position, about[0,i]The interval is guaranteed to be greater than or equal to the middle element
    public int partition(T[] array, int low, int high, boolean flag) {
        // The highest point is the center point
        T pivot = array[high];
        // Position to be exchanged
        int i = low;
        // Traversal cursor
        int j = low;
        for (; j < high; j++) {
            // If ascending,When exist array[j] =< pivot,take array[j]Put it in front and i Exchange location,And will i Move back one bit
            if ((flag && array[j].compareTo(pivot) < 1) || (!flag && array[j].compareTo(pivot) > 0)) {
                // exchange i and j Element of
                T temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                // take i Move back one bit
                i++;
            }
        }
        // Ignore i Change,Center point element and current i Exchange location elements
        // Exchange current high and i Element of,Move the element of the middle point to the middle index position
        array[high] = array[i];
        array[i] = pivot;
        // Return intermediate index
        return i;
    }

    // Double pointer movement, The low pointer moves from low to high,The high pointer moves from high to low
    public int partition2(T[] array, int low, int high, boolean flag) {
        // Set the highest bit to pivot element
        T pivot = array[high];
        while (low < high) {
            if ((flag && array[low].compareTo(pivot) == -1) || (!flag && array[low].compareTo(pivot) == 1)) {
                low++;
            } else {
                // Exchange high and low order elements
                array[high--] = array[low];
                // here high Moved forward one bit
                array[low] = array[high];
                // here high A free slot already exists at the location of
            }
        }
        // Put the intermediate element into the free slot
        array[high] = pivot;
        return high;
    }

    public static void main(String[] args) {
        Integer[] values = new Integer[]{3,7,8,5,2,1,5,4};
        Sort<Integer> integerInsertSort = new QuickSort<>();
        integerInsertSort.sort(values, true);
        Stream.of(values).forEach(System.out::print);
        System.out.println();
        integerInsertSort.sort(values, false);
        Stream.of(values).forEach(System.out::print);
    }
}

There are two operation modes for partition operation of fast platoon

1. The fast and slow pointer mode of double pointer (corresponding method partition) is the traversal sequence from low to high. The elements pointed to by the fast pointer are compared with the pivot elements. For the elements that meet the sorting conditions, the elements pointed to by the block slow pointer are exchanged, and the fast and slow pointers are moved back at the same time; On the contrary, for elements that do not meet the sorting conditions, only the block pointer is moved; Finally, the slow pointer element and pivot element are exchanged, and the slow pointer index is returned as the intermediate value index; The slow pointer ensures that the elements in the [0, slow pointer index] interval are greater than or equal to the pivot element;
2. The low and high pointer modes of double pointers (corresponding method partition2). The low pointer traverses from low to high, and the high pointer traverses from high to low. Compare the elements pointed to by the low pointer with the pivot element. When the sorting conditions are met, only the low pointer moves backward; When the sorting conditions are not met, write the element pointed by the low pointer to the high pointer index position, move the high pointer forward one bit, and write the element pointed by the current high pointer to the low pointer index position. The low pointer does not move. At this time, the high pointer actually points to a free slot; When the high pointer and the low pointer meet, it indicates the end of the partition, and writes the intermediate element to the position pointed by the high pointer; At this point, the high pointer is the middle element pointer

"Unfinished to be continued ----- use python+Matplotlib to draw visual animation for the rest"

https://zhuanlan.zhihu.com/p/38157591