我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note

经典的十大排序算法！

前言

请==务必==看一下这个：排序算法前置知识+代码环境准备。

当上面的内容都准备好以后，那就开始快速排序吧！

快速排序

执行流程：

• ① 从序列中选择一个轴点元素（pivot）
  假设每次选择 0 位置的元素为轴点元素

  • ② 利用 pivot 将序列分割成 2 个子序列

  将小于 pivot 的元素放在pivot前面（左侧）
  将大于 pivot 的元素放在pivot后面（右侧）
  等于pivot的元素放哪边都可以

  • ③ 对子序列进行 ① ② 操作

  直到不能再分割（子序列中只剩下1个元素）

由图可见，快速排序的本质就是：

• 逐渐将每一个元素都转换成轴点元素

轴点构造

对于序列 { 6~a~, 8~a~, 8~b~, 2, 6~b~, 4, 9, 5, 7 } 构造轴点：

• 首先将 0 位置的元素备份，作为轴点元素；

• 最终目标是构造出以轴点元素为中心的序列：
  左半边是小于轴点元素的序列；
  右半边是大于轴点元素的序列；
  如下图：

那么如何构造呢？
begin 为序列首位置，

• 从右往左扫描，寻找比轴点元素小的元素；
  找到以后，放到 begin 位置，begin++，然后反向寻找；

  • 从左往右扫描，寻找比轴点元素大的元素；

找到以后，放到 end 位置，end--，然后反向寻找;

• 当 begin == end，说明左右都扫描完了，此时将一开始备份的轴点元素放到中间。

这个过程有点迷惑性，需要先从右往左找，找到以后再从左往右，不断循环这个过程，直到把所有比轴点元素小的元素放到左半部分，把所有比轴点元素大的元素放到右半部分，才算完成这个轴点的构造。

构造轴点-代码实现

代码中如何实现从左往右扫描和从右往左扫描的交替呢？看一眼代码就会恍然大悟。。。

/**
 * 构造出 [begin, end) 范围的轴点元素
 * @return 轴点元素的最终位置
 */
private int pivotIndex(int begin, int end){    
    // 备份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; // begin==end
}

构造轴点-优化

在轴点左右元素数量比较均匀的情况下，同时也是最好情况：

• T(n) = 2 ∗ T(n/2) + O(n) = O(nlogn)

如果轴点左右元素数量极度不均匀，最坏情况：

• T(n) = T(n − 1) + O(n) = O(n^2^)

为了降低最坏情况的出现概率，一般采取的做法是：

• 随机选择轴点元素

可以在备份轴点元素前，将 begin 位置的元素与序列中的随机元素交换一下。

// 随机选择轴点元素, 将 begin 位置的元素与序列中的随机元素交换一下
swap(begin, begin + (int)Math.random()*(end - begin));

// 备份begin位置的元素
T pivot = array[begin];
.....

思考？与轴点相等的元素

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

思考：把上面的代码中，cmp 位置的判断分别改为 ≤、≥ 会起到什么效果？

后果：

• 轴点元素分割出来的子序列极度不均匀
• 导致出现最坏时间复杂度 O(n^2^)

快速排序完整代码

/**
 * 快速排序
 */
public class QuickSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        sort(0, array.length);
    }
    /**
     * 对 [begin, 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){
        // 随机选择轴点元素
        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; // begin==end
    }
    
}

生成 20000 个取值在[1, 10000] 的随机数进行排序：

复杂度与稳定性

快速排序的复杂度与稳定性：

• 最好、平均时间复杂度：O(nlogn)
• 最坏时间复杂度：O(n^2^)
• 由于递归调用的缘故，空间复杂度：O(logn)
• 属于不稳定排序