快速排序实现&讲解

skystars

因高中学业繁忙，很久没在论坛发帖了

看到论坛有选择排序的讲解，我也来个快速排序的讲解

快速排序可以分为两个部分，分区和递归。快速排序对一个数组进行排序，实际上是先选取一个基准数（pivot），把比基准数小的数字放到数组左边，比基准数大的数字放到数组右边，最后再分别对拆分出来的左右俩区间递归，分别重复上述过程。

快速排序一般有两种分区方法，Lomuto和Hoare，这里先讲比较易懂的Lomuto分区方法。话不多说，先上代码！

[C++] 纯文本查看 复制代码

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

这里的partition函数分区的过程如下：
首先，取最后一个数为基准数。接着循环遍历排序区间（不包括最后面的基准数）的每一个元素，一旦发现有元素小于等于基准数，就把元素移动到第一个位置，如果再发现一个，就移动到第二个位置，然后是第三个、第四个……以此类推。（注意这里并不是先删除再插入，而是直接交换。因为删除和插入的时间复杂度是O(n)）。最后，把最后面的基准数移动到左区间（比基准数小的区间）后面，就完成了分区工作。

当然我们也可以随机选取基准数，只需要在分区开始时把基准数移动到最后一个位置即可。

quickSort函数首先会调用partition进行分区，并从返回值中获取基准数的位置，然后继续对基准数左边的区间和右边的区间进行同样的操作（分区、递归），这些步骤完成后，排序就成功了。

为方便大家理解，我再举一个例子来说明排序的过程，假设原数组序列如下：
7639 9899 9056 8942 6462 3285 9987 3910 9283 8858

我们选取最后的8858作为基准数，发现7637比基准数8858小，于是和第一个数字交换位置，同时计数器i自增1。接着判断第二个位置，9899比8858大，不进行交换，第三个、第四个位置同理。第五个位置是6462，比基准数8858小，于是和第二个数字交换位置。第六个位置是3285，同样比8858小，于是和第三个数字交换位置……

分区的结果如下：
7637 6462 3285 3910 8858 9056 9987 8942 9283 9899

左边的区间（7637 6462 3285 3910）比基准数8858小，右边的区间（9056 9987 8942 9283 9899）比基准数8858大，对两个区间进行同样的操作，最终就得到了排序后的序列：
3285 3910 6462 7637 8858 8942 9056 9283 9899 9987

这就是Lomuto分区的过程了。Lomuto分区方法比Hoare分区方法更容易理解一些，但是对于同样的序列，其比较次数一般比Hoare分区多，排序时间一般比Hoare分区长。

skystars

Hoare分区和Lomuto分区的目的都相同：把比基准数大的元素移动到左侧，把比基准数小的元素移动到右侧。


先上代码：

[C++] 纯文本查看 复制代码

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[low];
    int i = low - 1;
    int j = high + 1;
    while (true) {
        do {
            ++i;
        } while (arr[i] < pivot);

        do {
            --j;
        } while (arr[j] > pivot);

        if (i >= j) {
            return j;
        }
        std::swap(arr[i], arr[j]);
    }
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex);
        quickSort(arr, pivotIndex + 1, high);
    }
}

首先，我们选取数组的第一个元素作为基准数，初始化两个变量i和j，i值从数组左边开始增加，j值从数组右边开始减少。接着，我们利用变量i在数组左侧找到大于等于基准数的元素，利用变量j在数组右侧找到小于等于基准数的元素，对其进行交换。不断循环这一过程，最终i和j会相遇。

i和j发生相遇，会出现两种情况。第一种是i==j，第二种是i>j，i==j说明i和j对应的元素值和基准数相等，无论划分到左区间和右区间都无关紧要。i>j则说明i是在数组右侧找到的大于等于基准数的第一个元素，j是在数组左侧找到的小于等于基准数的第一个元素。此时，i指向的是右区间（比基准数大）的第一个元素，j指向的是左区间（比基准数小）的最后一个元素。显然左区间为[low, i]，右区间为[j, high]，此时j=i+1。因此，我们在递归时需要对从low到pivotIndex（也就是j值）和从pivotIndex+1到high的元素进行排序。

skystars

上面是Hoare分区和Lomuto分区的排序时间对比（Quick是Lomuto分区，Quick 2是Hoare分区）

图片来自Karunanithi A K. A survey, discussion and comparison of sorting algorithms[J]. Department of Computing Science, Umea University, 2014.

faryou

感谢楼主分享
之前区信奥队的老师讲太快了，没听懂，这回懂了
能不能再出一期质数筛的，那玩意儿当时也不太懂

skystars

faryou 发表于 2024-6-6 06:28
感谢楼主分享
之前区信奥队的老师讲太快了，没听懂，这回懂了
能不能再出一期质数筛的，那玩意儿 ...

好的，我有时间的话抽个时间写一下吧

gian

感谢楼主用心分享
努力學習中