算法导论：c++快速排序

客官°小女子只卖身不卖艺 2022-06-04 02:26 239阅读 0赞

快速排序也采用分治的思想，以最后一个元素为基准把其分成大于它和小于它的两部分，关键在于确定分割点。

### 算法思想 ###

![这里写图片描述][SouthEast]

### 一趟快排 ###

![这里写图片描述][SouthEast 1]

![这里写图片描述][SouthEast 2]

### 算法实现 ###

安装书上的算法思想，主要要注意

> i,j的初始化,i=p-1,j=p  
> 终止条件j=r  
> 每次循环j都要+1移动

/*快排分割,p首端，r尾端,i控制小于,j控制大于*/
    int quick_partition(int array[], int p, int r)
    {
        int x = array[r];
        int i = p - 1; //注意i和p的初始值
        for (int j=p; j<r;j++)
        {
            if (array[j] < x) //小于则发生交换
            {
                i++;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        //交换分割点和最尾元素
        int temp = array[i+1];
        array[i + 1] = array[r];
        array[r] = temp;
        return i + 1; //返回分割点
    }
    /*快速排序*/
    void quicksort(int array[], int p, int r) 
    {
        if (p < r) {
            int q = quick_partition(array, p, r);
            quicksort(array, p, q-1);
            quicksort(array, q+1, r);
        }
    }

### 主函数测试 ###

int main()
    {
    
        const int len = 8;
        int array[len] = { 2,8,7,1,3,5,6,4};
        quicksort(array, 0, 7);
        for (int i = 0; i < len; i++)
        {
            cout << array[i] << " ";
        }
    
    }

> 输出： 1 2 3 4 5 6 7 8

[SouthEast]: /images/20220604/276d3b71709d4884b68fbde7e4325575.png
[SouthEast 1]: /images/20220604/a7c671c8058e43f2870c016ce3a3e3a9.png
[SouthEast 2]: /images/20220604/de2b514dbb5743849c1dc5cbcbdfcc02.png

发表评论取消回复

表情：

评论列表（有 0 条评论，239人围观）

还没有评论，来说两句吧...

相关阅读

相关算法_快速排序算法C/C++

目录快速排序 1. 算法思想 2. 实现原理 3. 动态演示 4. 完整代码 5. 结果展示 6. 算法分析 -------------------- 快

逃离我推掉我的手/ 2023年01月11日 03:49/ 0 赞/ 122 阅读

相关快速排序（算法导论）

本算法翻译自算法导论第三版（中文版）第7章170（有兴趣的可以看看，我感觉这本书还是跟晦涩的，可能我也没多读几次的原因）； 1、快速排序介绍快速排序是一种在实际排序应用

小鱼儿/ 2022年06月15日 12:57/ 0 赞/ 260 阅读

相关算法导论：c++桶排序

![这里写图片描述][SouthEast] 代码实现桶排序是按照桶的概念把元素往里面放，然后桶内还有一个排序，桶内排序可以用比较排序也可以用计数排序递归使用桶排序也可

客官°小女子只卖身不卖艺/ 2022年06月04日 04:29/ 0 赞/ 221 阅读

相关算法导论：c++计数排序

区别于比较排序需要元素进行相互比较，计数排序仅仅通过元素个数确定它在排序结果中的位置。 ![这里写图片描述][SouthEast] ![这里写图片描述][SouthEast

今天药忘吃喽~/ 2022年06月04日 02:54/ 0 赞/ 199 阅读

相关算法导论：c++归并排序

基本思想就是把数组一直分成两半，然后对这两半进行排序归并。先分成左右两半，然后合并时比较左右两半一直选最小的替代原数组。这种排序是非原址的，需要额外的空间。伪代码非

偏执的太偏执、/ 2022年06月04日 02:53/ 0 赞/ 214 阅读

相关算法导论：c++快速排序

快速排序也采用分治的思想，以最后一个元素为基准把其分成大于它和小于它的两部分，关键在于确定分割点。算法思想 ![这里写图片描述][SouthEast] 一趟快排

客官°小女子只卖身不卖艺/ 2022年06月04日 02:26/ 0 赞/ 240 阅读

相关算法导论：c++堆排序&优先队列

预习了一下算法导论的堆排序，以前数据结构课简直是一知半解。 ![这里写图片描述][SouthEast] ![这里写图片描述][SouthEast 1] 建大根堆的过程

向右看齐/ 2022年06月04日 01:38/ 0 赞/ 228 阅读

相关算法导论：排序算法笔记

排序算法相关笔记 ![这里写图片描述][SouthEast] 详细笔记堆排序：[http://blog.csdn.net/u013948010/article/d

Dear 丶/ 2022年06月04日 00:05/ 0 赞/ 253 阅读

相关算法 - 快速排序（C#）

分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangju

曾经终败给现在/ 2022年05月15日 14:25/ 0 赞/ 221 阅读

相关算法导论第7章快速排序答案

一、概念快速排序是基于分治模式的，选择一个数作为主元，经过一遍扫描，所有小于主元的数放在主元的左边，大于主元的数放在主元的右边，这样就划分成了两组数据。然后对两组数分别

﹏ヽ暗。殇╰゛Y/ 2022年05月14日 00:45/ 0 赞/ 298 阅读