查看: 464|回复: 4

[C/C++] 快速排序实现&讲解

[复制链接]

1

技术

25

魅力

7

原创

管理员

Rank: 9Rank: 9Rank: 9

积分
11253
人气
296
分享
42

优秀版主活跃会员最佳新人灌水之王

发表于 2024-6-5 20:08:23 | 显示全部楼层 |阅读模式
因高中学业繁忙,很久没在论坛发帖了

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

快速排序可以分为两个部分,分区和递归。快速排序对一个数组进行排序,实际上是先选取一个基准数(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进行分区,并从返回值中获取基准数的位置,然后继续对基准数左边的区间和右边的区间进行同样的操作(分区、递归),这些步骤完成后,排序就成功了。

为方便大家理解,我再举一个例子来说明排序的过程,假设原数组序列如下:
9899 7637 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分区长。

评分

参与人数 2经验 +35 人气 +3 收起 理由
蒟蒻 + 20 赞一个!
faryou + 15 + 3 很给力!

查看全部评分

本帖被以下淘专辑推荐:

Just do it.

1

技术

25

魅力

7

原创

管理员

Rank: 9Rank: 9Rank: 9

积分
11253
人气
296
分享
42

优秀版主活跃会员最佳新人灌水之王

 楼主| 发表于 2024-6-5 20:26:42 | 显示全部楼层
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的元素进行排序。
Just do it.

1

技术

25

魅力

7

原创

管理员

Rank: 9Rank: 9Rank: 9

积分
11253
人气
296
分享
42

优秀版主活跃会员最佳新人灌水之王

 楼主| 发表于 2024-6-5 20:37:50 | 显示全部楼层


上面是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.

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x
Just do it.

0

技术

4

魅力

1

原创

网站编辑

心如止水,笑对人生!

Rank: 8Rank: 8

积分
10085
人气
59
分享
523

最佳新人活跃会员

发表于 2024-6-6 06:28:25 | 显示全部楼层
感谢楼主分享
之前区信奥队的老师讲太快了,没听懂,这回懂了
能不能再出一期质数筛的,那玩意儿当时也不太懂
faryou的个人主页
论坛相关事务请发送邮件到[email protected]
目前是区信奥队队员,正在学习算法
别把我当回事儿,我只是一个卑微的初中生……

1

技术

25

魅力

7

原创

管理员

Rank: 9Rank: 9Rank: 9

积分
11253
人气
296
分享
42

优秀版主活跃会员最佳新人灌水之王

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

好的,我有时间的话抽个时间写一下吧
Just do it.
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表