快速排序算法实现思想个人理解

技术交流QQ群:1027579432，欢迎你的加入！

欢迎关注我的微信公众号：CurryCoder的程序人生

一.概述

  • 快速排序是冒泡排序的改进算法。它也是通过不断比较和移动交换来实现排序的，只不过它的实现增大了记录的比较和移动的距离，将关键字较大的元素从前面直接放到后面，关键字较小的元素直接从后面放到前面，从而减小了比较次数和交换次数。

二.原理

  • 通过一趟排序将待排序数据分割成独立的两个子序列，其中左边的子序列均比右边的子序列中的元素小，然后分别对左右两个子序列继续进行排序，达到整个序列有序的目的。下面主要做两件事情，第一：从什么位置划分原始序列，将其变成左右两个子序列，即确定主元pivotkey的位置pivot。第二：分别对左右两个子序列进行递归操作，继续分割使其变得有序(即大于主元的元素都放在主元的右边，小于主元的元素都放在主元的左边)，整个过程如下图所示，其中主元的位置选的是待排序数组中的第一个元素50。
    快速排序基础.jpg

三.快速排序的优化

  • 3.1优化主元的选择
    • 快速排序算法的快慢取决于主元元素的选择。上面的例子中，选择的是待排序数组中的第一个元素。事实上，固定选择第一个元素作为主元是不合理的，如下图中的例子。选择9为主元后，进行一次交换操作后，整个序列没有发生实质性的操作。最坏情况下，待排序的数组是正序或逆序时，每次划分只得到一个比上次少一个元素的子序列，另一个子序列为空。此时快速排序的时间复杂度就变成了0(n**2)。一般选择主元的方法是：三数取中法。即取三个元素(三个元素分别是待排数组的左端点、中间端点、右端点)先进行从小到大的排序，然后选择中间端点的元素作为主元，如下图中的例子。当待排序数组是非常大时，采用九数取中法，即从数组中分三次采样，每次取三个数，三个数各取出中间的元素，总共得到三个中间元素。接着，从这三个中间元素中再取一个中间数作为主元。
  • 3.2优化不必要的交换
    • 增加一个哨兵位置，暂存主元的值。然后每次当小于主元的元素出现在右边或大于主元的元素出现在左边时，进行直接替换操作，不进行交换，如下图所示。
      快速排序优化.jpg

四.对小数组的优化

  • 当待排序的数组元素个数很少时，采用快速排序有点大材小用。所以，设置一个阈值，用来判断是否采用快速排序。当待排序的数组中元素非常少时，使用直接插入排序算法；超过设定的阈值后，采用快速排序算法，如下面的代码所示： 
        // 因为快速排序适合由于待排序的序列很大的情况，所以设置一个阈值
    void Qsort1(Sqlist *L, int low, int high)
    {
        int pivot;
        if ((high - low) > MAX_LENGTH_INSERT_SORT)
        {
            pivot = Partition1(L, low, high);
            Qsort1(L, low, pivot - 1);
            Qsort1(L, pivot + 1, high);
        }
        else
        {
            InsertSort(L);
        }
    }
  • 上述Qsort1()函数进行快速排序时，在函数尾部有两次递归操作，这两次递归操作对性能有一定的影响，使用尾递归可以减少递归次数，提高性能。因为第二次执行递归操作针对的是右边的子序列，所以Qsort1(L, pivot + 1, high);可以替换为low = pivot+1;同时，增加一个while(low < high)的循环，采用迭代的方式不是递归的方法，缩减了堆栈的深度，从而提高了整体性能，具体见下面的代码: 
        // 由于Qsort1()函数在其尾部有两次的递归操作，如果待排序的序列划分极不平衡时，递归深度将趋于n，浪费栈空间
    // 使用尾递归
    void Qsort2(Sqlist *L, int low, int high)
    {
        int pivot;
        if ((high - low) > MAX_LENGTH_INSERT_SORT)
        {
            while (low < high)
            {
                pivot = Partition1(L, low, high);
                Qsort2(L, low, pivot - 1);
                low = pivot + 1;  // 尾递归
            }
        }
        else
        {
            InsertSort(L);
        }
    }

五.快速排序完整代码

    #include <iostream>
    #include <malloc.h>

    using namespace std;

    #define MAXSIZE 10
    #define N 9
    #define MAX_LENGTH_INSERT_SORT 7 // 快速排序设定的阈值

    typedef struct
    {
        int r[MAXSIZE + 1];
        int len;
    } Sqlist;

    void show(Sqlist L)
    {
        for (int i = 1; i <= L.len; i++)
            cout << L.r[i] << " ";
        cout << endl;
    }

    void Swap(Sqlist *L, int i, int j)
    {
        int temp = L->r[i];
        L->r[i] = L->r[j];
        L->r[j] = temp;
    }

    // 确定主元
    int Partition(Sqlist *L, int low, int high)
    {
        int pivotkey; // 主元
        pivotkey = L->r[low];
        while (low < high)
        {
            while (low < high && L->r[high] >= pivotkey) // 比主元大的放在主元的右边，不交换
                high--;
            Swap(L, low, high);                         // 比主元小的放在主元的右边，进行交换
            while (low < high && L->r[low] <= pivotkey) // 比主元小的放在主元的左边，不交换
                low++;
            Swap(L, low, high); // 比主元大的放在主元的左边，进行交换
        }
        return low;
    }

    // 快速排序
    void Qsort(Sqlist *L, int low, int high)
    {
        int pivot; // 主元位置
        if (low < high)
        {
            pivot = Partition(L, low, high);
            Qsort(L, low, pivot - 1);
            Qsort(L, pivot + 1, high);
        }
    }

    // 统一函数接口
    void QuickSort(Sqlist *L)
    {
        Qsort(L, 1, L->len);
    }

    // 快速排序的优化
    int Partition1(Sqlist *L, int low, int high)
    {
        // 确定主元位置---三数取中法
        int pivotkey;
        int center = low + (high - low) / 2; // 计算中间元素的下标
        // 对左 中 右三个数进行排序
        if (L->r[low] > L->r[high])    // 如果左边的数大于右边的数，进行交换操作
            Swap(L, low, high);        // 保证左边的数较小
        if (L->r[center] > L->r[high]) // 如果中间的数大于右边的数，进行交换操作
            Swap(L, center, high);     // 保证中间的值较小
        if (L->r[center] > L->r[low])  // 如果中间的数大于左边的数，进行交换操作
            Swap(L, center, low);      // 保证左边的值较小
        pivotkey = L->r[low];          // L->r[low]已经成为整个序列左中右三个关键字的中间值
        L->r[0] = pivotkey;
        while (low < high)
        {
            while (low < high && L->r[high] >= pivotkey)
                high--;
            L->r[low] = L->r[high]; // 使用的是替换不是交换
            while (low < high && L->r[low] <= pivotkey)
                low++;
            L->r[high] = L->r[low]; // 使用的是替换不是交换
        }
        L->r[low] = L->r[0]; // 将暂存的主元替换回L->r[row]
        return low;          // 返回主元的位置
    }

    // 直接插入排序
    void InsertSort(Sqlist *L)
    {
        int i, j;
        for (i = 2; i <= L->len; i++)
        { // 插入的元素从下标为2开始
            if (L->r[i] < L->r[i - 1])
            {                      // 插入的元素比之前的元素值小，就进行交换操作
                L->r[0] = L->r[i]; // 下标为0的位置存放的是哨兵
                for (j = i - 1; L->r[j] > L->r[0]; j--)
                    L->r[j + 1] = L->r[j]; // 进行移动操作
                L->r[j + 1] = L->r[0];     // 插入新的元素到正确的位置
            }
        }
    }

    // 因为快速排序适合由于待排序的序列很大的情况，所以设置一个阈值
    void Qsort1(Sqlist *L, int low, int high)
    {
        int pivot;
        if ((high - low) > MAX_LENGTH_INSERT_SORT)
        {
            pivot = Partition1(L, low, high);
            Qsort1(L, low, pivot - 1);
            Qsort1(L, pivot + 1, high);
        }
        else
        {
            InsertSort(L);
        }
    }
    // 由于Qsort1()函数在其尾部有两次的递归操作，如果待排序的序列划分极不平衡时，递归深度将趋于n，浪费栈空间
    // 使用尾递归
    void Qsort2(Sqlist *L, int low, int high)
    {
        int pivot;
        if ((high - low) > MAX_LENGTH_INSERT_SORT)
        {
            while (low < high)
            {
                pivot = Partition1(L, low, high);
                Qsort2(L, low, pivot - 1);
                low = pivot + 1;  // 尾递归
            }
        }
        else
        {
            InsertSort(L);
        }
    }

    // 统一函数接口:改进后的快速排序
    void QuickSort1(Sqlist *L){
        Qsort1(L, 1, L->len);
    }

    // 统一函数接口：改进后的快速排序使用尾递归
    void QuickSort2(Sqlist *L){
        Qsort2(L, 1, L->len);
    }

    int main()
    {
        Sqlist L;
        int d[N] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
        for (int i = 0; i < N; i++)
            L.r[i + 1] = d[i];
        L.len = N;
        cout << "快速排序前: ";
        show(L);
        cout << "快速排序后: ";
        QuickSort(&L);
        show(L);

        cout << "改进的快速排序后: ";
        QuickSort1(&L);
        show(L);
        
        cout << "改进的快速排序(尾递归)后: ";
        QuickSort2(&L);
        show(L);
        return 0;
    }
  • STL实现
    #include <iostream>
    #include <algorithm>
    #include <vector>

    using namespace std;


    // （小数，基准元素，大数）。在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。
    // 快速排序思路：
    // 1. 选取第一个数为基准
    // 2. 将比基准小的数交换到前面，比基准大的数交换到后面
    // 3. 对左右区间重复第二步，直到各区间只有一个数


    // 递归方法实现
    void QuickSort(vector<int>& v, int low, int high){
        if(low >= high)
            return;
        int first = low;
        int last = high;
        int key = v[first];   // 第一个元素作为主元

        while(first < last){
            while(first < last && v[last] >= key){
                last--;
            }

            if(first < last){  // 不符合条件时，即后面元素比前面的元素小时，进行交换操作!
                v[first++] = v[last];
            }

            while(first < last && v[first] <= key){
                first++;
            }

            if(first < last){
                v[last--] = v[first];
            }
        }

        // 基准位置
        v[first] = key;
        QuickSort(v, low, first-1);  // 前半部分递归
        QuickSort(v, first+1, high);  // 后半部分递归
    }


    // 最后一个元素作为主元
    template<typename T>
    void QuickSortRecursiveCore(T arr[], int start, int end){
        if (start >= end)
            return;
        T mid = arr[end];
        int left = start, right = end-1;
        while(left < right){
            while(arr[left] < mid && left < right){
                left++;
            }
            while(arr[right] >= mid && left < right){
                right--;
            }
            swap(arr[left], arr[right]);
        }

        if(arr[left] >= arr[end]){
            swap(arr[left], arr[end]);
        }
        else{
            left++;
        }

        QuickSortRecursiveCore(arr, start, left-1);
        QuickSortRecursiveCore(arr, left+1, end);
    }

    template<typename T>
    void QuickSortRecursive(T arr[], int len){
        QuickSortRecursiveCore(arr, 0, len-1);
    }

六、快速排序时间复杂度总结：

  • 平均时间复杂度：O(nlogn)
  • 最好情况：O(nlogn)
  • 最坏情况：O(n**2)
  • 空间复杂度：O(nlogn)——O(n)
  • 稳定性：不稳定
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,245评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,749评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,960评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,575评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,668评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,670评论 1赞 294
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,664评论 3赞 415
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,422评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,864评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,178评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,340评论 1赞 344
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,015评论 5赞 340
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,646评论 3赞 323
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,265评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,494评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,261评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,206评论 2赞 352