快速排序

前言：
快速排序相较于之前的排序方法是一种比较特别排序方法
原理：
1、从序列中选择一个轴点元素（pivot）假设每次选择 0 位置的元素为轴点元素；
2、利用 pivot 将序列分割成 2 个子序列将小于 pivot 的元素放在pivot前面（左侧）将大于 pivot 的元素放在pivot后面（右侧）等于pivot的元素放哪边都可以
3、对子序列进行 1、2、操作直到不能再分割（子序列中只剩下1个元素）

快速排序的本质：逐渐将每一个元素都转换成轴点元素

快速排序 – 轴点构造

一个轴点完成之后，数组被分割成两部分，我们就可以构造成一个前轴点，和一个后轴点；以此类推，当每个元素都成为轴点之后，数组排列完成。
示例：

protected void sort() {
        sort(0, array.length);
    }
    /**
     * 对 [begin, end) 范围的元素进行快速排序
     * @param begin
     * @param end
     */
    private void sort(int begin, int end) { 
        if (end - begin < 2) return;
        // 确定轴点位置 O(n)
        int mid = pivotIndex(begin, end);
        // 对子序列进行快速排序
        sort(begin, mid); 
        sort(mid + 1, end); 
    } 
    /**
     * 构造出 [begin, end) 范围的轴点元素
     * @return 轴点元素的最终位置
     */
    private int pivotIndex(int begin, int end) {
        // 随机选择一个元素跟begin位置进行交换
        swap(begin, begin + (int)(Math.random() * (end - begin)));
        // 备份begin位置的元素
        T pivot = array[begin];
        // end指向最后一个元素
        end--;
        //这里是一个很神奇的交替循环方式，不过还是比较好用的
        //如果大家有更好的方法可以评论
        while (begin < end) {
            while (begin < end) {
                if (cmp(pivot, array[end]) < 0) { // 右边元素 > 轴点元素
                    end--;
                } else { // 右边元素 <= 轴点元素
                    array[begin++] = array[end];
                    break;
                }
            }
            while (begin < end) {
                if (cmp(pivot, array[begin]) > 0) { // 左边元素 < 轴点元素
                    begin++;
                } else { // 左边元素 >= 轴点元素
                    array[end--] = array[begin];
                    break;
                }
            }
        }
        // 将轴点元素放入最终的位置
        array[begin] = pivot;
        // 返回轴点元素的位置
        return begin;
    }

算法分析：
`3%ML8W`D70YE~HAAS9BK8X.png

快速排序 – 与轴点相等的元素

如果序列中的所有元素都与轴点元素相等，利用目前的算法实现，轴点元素可以将序列分割成 2 个均匀的子序列

我们利用if else 中else实现了如果其他元素与轴点相等的情况，但是如果将其中’<’或’>’修改成’<=’或’>=’这种情况呢？

导致的结果是显而易见，他会造成轴点元素切割出来的子序列极度不均匀，从而影响了效率，导致出现最坏的时间复杂度.

希尔排序

前言：
总感觉希尔排序就像归并的那种感觉，但是！他的原理就像插入排序一样，在不断减少逆序对进行排序
原理：
希尔排序把序列看作是一个矩阵，分成 𝑚 列，逐列进行排序
𝑚 从某个整数逐渐减为1
当 𝑚 为1时，整个序列将完全有序
因此，希尔排序也被称为递减增量排序（Diminishing Increment Sort）
矩阵的列数取决于步长序列（step sequence）
比如，如果步长序列为{1,5,19,41,109,…}，就代表依次分成109列、41列、19列、5列、1列进行排序
不同的步长序列，执行效率也不同

希尔本人给出的步长序列是 𝑛/2𝑘，比如 𝑛 为16时，步长序列是{1, 2, 4, 8}

分成8列进行排序

分成4列进行排序

分成2列进行排序

分成1列进行排序

不难看出来，从8列变为 1列的过程中，逆序对的数量在逐渐减少；因此希尔排序底层一般使用插入排序对每一列进行排序，也很多资料认为希尔排序是插入排序的改进版
示例：

protected void sort() {
    //选择不长序列，后面会讲到
        List<Integer> stepSequence = sedgewickStepSequence();
    //循环使用步长序列排序
        for (Integer step : stepSequence) {
            sort(step);
        }
    }

    /**
     * 分成step列进行排序
     */
    private void sort(int step) {
        // col : 第几列，column的简称
        for (int col = 0; col < step; col++) { // 对第col列进行排序
            // col、col+step、col+2*step、col+3*step
            for (int begin = col + step; begin < array.length; begin += step) {
                int cur = begin;
                while (cur > col && cmp(cur, cur - step) < 0) {
                    swap(cur, cur - step);
                    cur -= step;
                }
            }
        }
    }
    //希尔提供的步长序列
    private List<Integer> shellStepSequence() {
        List<Integer> stepSequence = new ArrayList<>();
        int step = array.length;
        while ((step >>= 1) > 0) {
            stepSequence.add(step);
        }
        return stepSequence;
    }
    //目前最好的步长序列
    private List<Integer> sedgewickStepSequence() {
        List<Integer> stepSequence = new LinkedList<>();
        int k = 0, step = 0;
        while (true) {
            if (k % 2 == 0) {
                int pow = (int) Math.pow(2, k >> 1);
                step = 1 + 9 * (pow * pow - pow);
            } else {
                int pow1 = (int) Math.pow(2, (k - 1) >> 1);
                int pow2 = (int) Math.pow(2, (k + 1) >> 1);
                step = 1 + 8 * pow1 * pow2 - 6 * pow2;
            }
            if (step >= array.length) break;
            stepSequence.add(0, step);
            k++;
        }
        return stepSequence;
    }

希尔排序——步长序列

希尔排序中最灵魂的地方可能就是步长序列了吧
希尔排序是利用步长序列来分割原序列，而每次分割，都会影响排序的复杂度，而目前已知的最好的步长序列，最坏情况时间复杂度是 O(n4/3) ，1986年由Robert Sedgewick提出

示例：

private List<Integer> sedgewickStepSequence() {
        List<Integer> stepSequence = new LinkedList<>();
        int k = 0, step = 0;
        while (true) {
            if (k % 2 == 0) {
                int pow = (int) Math.pow(2, k >> 1);
                step = 1 + 9 * (pow * pow - pow);
            } else {
                int pow1 = (int) Math.pow(2, (k - 1) >> 1);
                int pow2 = (int) Math.pow(2, (k + 1) >> 1);
                step = 1 + 8 * pow1 * pow2 - 6 * pow2;
            }
            if (step >= array.length) break;
            stepSequence.add(0, step);
            k++;
        }
        return stepSequence;
    }

排序3

快速排序

快速排序 – 轴点构造

快速排序 – 与轴点相等的元素

希尔排序

希尔排序——步长序列