快速排序

1. 算法原理

快速排序的主要思想是分治法，将一个大问题分割成小问题，解决小问题后再合并它们的结果。

快速排序不是稳定的，这是因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。

2. 实现步骤

1. 从待排序的数组中选择一个元素，称为"基准"（pivot）
2. 将数组中小于基准值的元素移到基准值的前面，将大于基准值的元素移到基准值的后面，在这个分区结束之后，该基准就处于数列的中间位置，这个过程称为分区（partition）
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

3. 快速排序动图展示

4. 代码

/**
 * 排序器接口(策略模式: 将算法封装到具有共同接口的独立的类中使得它们可以相互替换)
 */
public interface Sorter<T extends Comparable<T>> {
    /**
     * 排序
     *
     * @param array 待排序的数组
     * @param start 开始索引
     * @param end   开始索引
     */
    default void sort(T[] array, int start, int end) {
    }
}

public class QuickSorter<T extends Comparable<T>> implements Sorter<T> {
    public void sort(T[] array, int start, int end) {
        quickSort(array, start, end);
    }

    public void quickSort(T[] array, int start, int end) {
        if (start < end) {
            int pivot = partition(array, start, end);

            System.out.println("\nPivot: " + pivot + ", start: " + start + ", end: " + end);
            System.out.println("Array:");
            Arrays.stream(array).forEach(item -> System.out.print(item + " "));
            System.out.println("\n==============================\n");

            quickSort(array, start, pivot - 1);
            quickSort(array, pivot + 1, end);
        }
    }

    public int partition(T[] array, int start, int end) {
        T pivot = array[start];

        while (start < end) {
            while (start < end && array[end].compareTo(pivot) >= 0) {
                --end;
            }
            array[start] = array[end];

            while (start < end && array[start].compareTo(pivot) <= 0) {
                ++start;
            }
            array[end] = array[start];
        }
        array[start] = pivot;
        return start;
    }
}