脚本宝典收集整理的这篇文章主要介绍了

quick sort | 快速排序 C++ 实现

脚本宝典小编觉得挺不错的,现在分享给大家,也给大家做个参考,希望能帮助你少写一行代码,多一份安全和惬意。

Talk is cheap, show me the code

  • 参照wiki的快速排序中C++实现(递归)方式, 略改一点点, 更容易理解. 代码如下:
void quick_sort_recursive(vector<int> &a, int start, int end) {
    if (start >= end) return;
    int base = a[end];
    int left = start, right = end - 1;  // 从right=end开始也无妨, 因为`>=`就--right
    while (true) {
        while (a[left] < base) ++left;
        while (a[right] >= base) --right;
        if (left >= right) break;
        swap(a[left], a[right]);    // 原wiki的代码方式将出现多次浪费的swap,如swap(a[1],a[1])这种形式
    }
    if (a[left] >= a[end]) swap(a[left], a[end]);   // 将base放到指定位置
    else ++left;
    quick_sort_recursive(a, start, left - 1);
    quick_sort_recursive(a, left + 1, end);
}

需要说明的是:

  • while (arr[right] >= mid) right--; 如果>=换成>会导致陷入无限循环
  • 第一个while之后的if else语句作用是将mid放到指定位置(不会再变的位置), 完成左右划分,左边都是<mid,右边都是>=mid.
  • 上述实现过程和<算法导论>思路有差异, 和<数据结构/算法/C++实现> 思路一致,但是实现上略有差异

示例

int main() {
    vector<int> a{4, 8, 1, 3, 7, 5, 6, 2, 4, 4};
    quick_sort_recursive(a, 0, a.size() - 1);
    return 0;
}

if a[left]>base, ++left;
if a[right]<=base, --right;

内层while第1次swap

图片描述

第2, 3次变化过程

图片描述

跳出while后

图片描述

注意

该示例中, 如果if a[right]<=base, --right;没有=号将陷入死循环, 亲自演算一下排序过程大有裨益!

总结

以上是脚本宝典为你收集整理的

quick sort | 快速排序 C++ 实现

全部内容,希望文章能够帮你解决

quick sort | 快速排序 C++ 实现

所遇到的程序开发问题,欢迎加入QQ群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过