排列组合c和a怎么计算(快速排序的详细过程)

上一章节已经详细的向大家介绍过排序的相关概念学习笔记-排序简单介绍,本文旨在为大家详细的介绍快速排序。

快速排序

快速排序(Quicksort)是对冒泡排序(学习笔记-详解冒泡排序)的一种改进,也是一种交换类排序。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以进行,以此达到整个数据变成有序。

学习笔记-详解快速排序

算法原理

本质是分而治之思想的运用。首先选取一个元素作为分界值,将大于该分界值的元素放在数组的右边,小于主元的元素放在数组的左边,等于分界值的元素位置不变,然后不断迭代上述规则完成排序。

快速排序算法的原理如下:

1,首先设定一个分界值,通过该分界值将数组分成左右两部分。

2,将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。

3,然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。

4,重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

学习笔记-详解快速排序

算法实现#include <stdio.h> #define elemType int /*元素类型*/int k=1;//轮次记录 void Print (elemType *arr, int len){ int i; for (i=0; i<len; i++){ printf (“%d\t”, arr[i]); } printf(“\n”);}void Sort(elemType *a, int left, int right){ if(left >= right) /*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/ { return ; } int i = left; int j = right; int key = a[left]; printf(“第%d轮选取的key值为:%d\n”,k,key); while(i < j) /*控制在当组内寻找一遍*/ { while(i < j && key <= a[j]) /*而寻找结束的条件就是,1,找到一个小于或者大于key的数(大于或小于取决于你想升 序还是降序)2,没有符合条件1的,并且i与j的大小没有反转*/ { j–;/*向前寻找*/ } a[i] = a[j]; /*找到一个这样的数后就把它赋给前面的被拿走的i的值(如果第一次循环且key是 a[left],那么就是给key)*/ while(i < j && key >= a[i]) /*这是i在当组内向前寻找,同上,不过注意与key的大小关系停止循环和上面相反, 因为排序思想是把数往两边扔,所以左右两边的数大小与key的关系相反*/ { i++; } a[j] = a[i]; } a[i] = key; /*当在当组内找完一遍以后就把中间数key回归*/ printf(“第%d轮排序后结果如下:\n”,k); Print(a, 9); k=k+1; Sort(a, left, i – 1); /*最后用同样的方式对分出来的左边的小组进行同上的做法*/ Sort(a, i + 1, right); /*用同样的方式对分出来的右边的小组进行同上的做法*/ /*当然最后可能会出现很多分左右,直到每一组的i = j 为止*/} int main() { int i; elemType arr[9] = {94,19,29,9,11,1,14,13,29}; printf(“待排序的序列为:\n”); Print(arr, 9); printf(“\n\n”); Sort (&arr,0,8); printf(“\n\n”); printf(“排好序的结果如下:\n”); Print(arr, 9); }
学习笔记-详解快速排序

序列红框为界

算法分析
学习笔记-详解快速排序

时间复杂度

快速排序的一次划分算法从两头交替搜索,直到left和right重合,因此其时间复杂度是O(n);而整个快速排序算法的时间复杂度与划分的趟数有关。

最优情况:每次划分所选择的中间数恰好将当前序列几乎等分,经过log2n趟划分,便可得到长度为1的子表。这样,整个算法的时间复杂度为O(nlog2n)。

最坏情况:每次所选的中间数是当前序列中的最大或最小元素,这使得每次划分所得的子表中一个为空表,另一子表的长度为原表的长度-1。这样,长度为n的数据表的快速排序需要经过n趟划分,使得整个排序算法的时间复杂度为O(n2)。

为改善最坏情况下的时间性能,可采用其他方法选取中间数。通常采用“三者值取中”方法,即比较H->r[left].key、H->r[right].key与H->r[(left + right)/2].key,取三者中关键字为中值的元素为中间数。

可以证明,快速排序的平均时间复杂度也是O(nlog2n)。因此,该排序方法被认为是目前最好的一种内部排序方法。

空间复杂度

从空间性能上看,尽管快速排序只需要一个元素的辅助空间,但快速排序需要一个栈空间来实现递归。最好的情况下,即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表,所需栈的最大深度为log2(n+1);但最坏的情况下,栈的最大深度为n。这样,快速排序的空间复杂度为O(log2n))。适合在数据集比较大的时候使用。

算法稳定性

值得注意的是,快速排序是一种不稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

 

本站部分内容由互联网用户自发贡献,该文观点仅代表作者本人,本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如发现本站有涉嫌抄袭侵权/违法违规等内容,请联系我们举报!一经查实,本站将立刻删除。

(0)

相关推荐

  • 电池耐用的手机(容量大像素高电池耐用的手机)

    续航时间长的手机是很多朋友们都感兴趣的,随着现在的手机搭配了更高刷的屏幕和更好的处理器,耗电速度也是非常快,电池容量大才能让续航时间持久精彩玩机体验不间断,因此一款手机的续航表现也是相当重要的,所以推荐几款续航出色的手机,彻底治愈你的低电量焦虑! 一加10 Pro 一加手机对屏幕态度可谓用心良苦,一加10 Pro的屏幕依旧惊艳,该机正面覆盖了一块三星6.7英…

    2023-05-24
  • 暗黑3更新,暗黑3更新:最新改动带来的新体验

    IT之家 4 月 7 日消息,暴雪官方已敲定《暗黑破坏神 4》将于 6 月 6 日上线,《暗黑破坏神 3》也将展开收尾工作,接下来新赛季将不再引入新内容。 暴雪总经理 Rod Fergusson 近日在接受 Wowhead 采访中表示,第 29 赛季将会引入新的主题,但不会像第 28 赛季那样精致或者紧凑。IT之家从报道中获悉,从第 30 赛季开始,内容将会…

    知识百科 2023-05-21
  • 天猫付完尾款退货定金退吗(淘宝付尾款后退定金吗)

    双十一在淘宝付定金之后不想要可以申请退款吗?用户在双十一剁手行为已经开始,对于这波付定金的行动,很多人都想要知道如果不想要已经付了定金的东西能不能退款,这个问题游综宅小编接下来就来和大家分析分析。   淘宝付了定金不想要了可以退款吗 可以的退款,通常来说是定金是不会退回的,有些店家都会在预售物品详情说明页备注定金不退,但是用户可以先支付尾款,之后再…

    2021-12-06
  • 军人退伍费怎么算?军人退伍费计算公式

    军人是我们中国人最羡慕的职业,每年到这个时候,每家每户讨论的就是是否让自己的孩子送到部队去呢?现在国家政策好了,每年都要招收30多万新兵战士,这些新兵进入部队国家包办了一切,衣食住行都在部队中,这部队里不仅能练就过硬的军事技能,还能培养良好的心理素质,这就是为什么很多退伍军人所说的,当兵苦两年,不当兵后悔一辈子。义务兵两年后可以考取士官,留在部队建功立业。即…

    2022-04-11
  • 2020年电信最划算的流量卡(移动联通电信流量卡哪个最划算)

    电信大旗卡29月租70G通用+30G定向+0.1/分钟通话(长期资费20年) 别再瞎办手机卡了! 你们有没有感觉到自从进入5g时代后,月租越来越贵,流量越来越少呢?那是因为随着5g建设,运营商成本和人力物力增长,成本越来越高,运营商不得不提高资费,回收成本! 今天给大家推荐一款长期资费正规流量卡,29元70g通用流量+30g定向流量,打电话0.1元/分钟,虽…

    2023-05-26 知识百科
  • 合唱指挥手势图(合唱指挥手势图解 初学)

    近日,“凉都百姓讲坛”第10期专题讲座——合唱指挥基本技能培训在凉都大剧院举行。六盘水师范学院教育科学与音乐学院音乐系主任、副教授赵蓉为来自市内的50名指挥人员参加培训。 培训现场 培训现场 为满足广大合唱指挥者对合唱指挥技巧的需求,六盘水市图书馆“凉都百姓讲坛”邀请专业音乐老师举办音乐知识专题讲座,进一步提升音乐素养及技巧的需求,倡导健康、积极、乐观、向上…

    2023-06-01 知识百科
  • 老款手机游戏大全集(诺基亚java老版手机游戏合集)

    以前玩游戏除了电脑跟游戏机之外手机也是一个重要的游戏来源,记得最早玩的手机游戏是我老豆的诺基亚3310自带的空间大战 这个超好玩的,有激光跟全屏攻击 后来手机进入彩屏,我又在1110玩bounce 这个是最早的版本闯关吃圈圈跟后来的bounce tales不同 山寨宠物小精灵 这个打砖块超好玩的 还有一些国内好的工作室比如华娱无线 斩妖伏魔录系列都很好玩 英…

    知识百科 2023-04-11
  • 卖家不发货先投诉还是先退款

    来源:【青岛信网】 信网1月3日讯(记者 李鑫邦)买了洗衣机却不给发货,退费还成了问题,近日,市民尹女士便遭遇了这一问题,她在李沧区一家“真快乐app体验中心国美电器馆”购买了一台洗衣机加干衣机,时间过了两个月都一直不发货,要求退款时也只是表示需要走流程,退款流程也是长达一个月之久,面对该情况,尹女士已将问题反馈至青岛市市场监督管理局。对此,青岛市市场监督管…

    知识百科 2023-04-10
  • 问卷调查赚钱(问卷调查赚钱的app)

    填写一份调查问卷直接领一百元现金红包。估计很多朋友一看到这个标题以为是忽悠人的,其实这个问卷是头条里面的一个广告,通过填写问卷真的可以领到红包,最多一百块钱。   很多朋友看到做自媒体的赚到很多钱,自己也想试试看,但是既不想露脸拍视频,又没有写作功底,而且还没那么多时间刷金币的,那么下面这个赚钱方法就非常适合你们。你只需要花点时间,填写一份调查问卷…

    2022-01-27 知识百科
  • 天津体检代检,天津体检:全面检测,保障健康

    天津河西区梅江街社区卫生服务中心老年人免费体检 体检年龄: 60岁及以上老人 体检项目:   (1)血常规、尿常规、肝肾功能、血脂(总胆固醇、甘油三酯、高、低密度脂蛋白胆固醇)、空腹血糖、血压、身高体重腰围、心肺听诊、心电图。   (2)65岁以上增加免费项目:中医体质辨识、腹部B超(肝胆胰脾)。 温馨提示:   请于工作日周一至周四下午14:00-16:0…

    知识百科 2023-05-22
  • 订阅是什么意思?订阅号付费能力

    公众号在今年1月15日宣布开始灰度测试订阅号付费能力。最终灰度测试选择的是单篇付费阅读的模式,而非专栏订阅的模式。本文从业务、用户、产品定位三个角度深入挖掘了其背后的原因。 017年被誉为了“知识付费”的元年,那一年大量的知识付费产品兴起——分答、在行在微信生态开了知识付费的第一枪。随后得到APP横空出世,在罗胖强大影响力下孕育出诸多知识网红。由于概念新颖且…

    2023-02-13
  • 兴化油菜花,兴化油菜花种植栽培技术

    每年的三、四月份是观赏油菜花的季节,国内有许多观赏油菜花的胜地,比如云南罗平、青海青海湖、江西婺源、陕西汉中、江苏兴化等地的油菜花,这些地方不仅有着犹如海洋般的油菜花田,景色也各异,吸引着众多游客前去赏花。今天,笔者跟大家分享下“兴化油菜花”。 千垛景区油菜花种植历史非常悠久,据说在千年前这里还发生过一场大战,而这里的垛田也被大家称为是岳飞大战金兵的“八卦阵…

    知识百科 2023-04-26