C++ 经典排序算法

1.1.概述

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。

1.2.算法原理: 冒泡排序算法的运作如下:(从后往前)

1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。

2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤,除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

1.3.参考代码:

1.4.效率分析: 相对于简单选择排序,冒泡排序交换次数明显更多。它是通过不断地交换把最大的数冒出来。冒泡排序平均时间和最坏情况下(逆序)时间为o(n^2)。最佳情况下虽然不用交换,但比较的次数没有减少,时间复杂度仍为o(n^2)。此外冒泡排序是稳定的。

2.快速排序

2.1.概述:

快速排序是冒泡排序的一种改进,那么我们想了,既然冒泡排序第一轮排完了是最大值冒出来了,那么我们期望,能不能先随机选定一个值,然后依次与序列中的数进行对比,把小于该值的和大于该值的数据分割成独立的两个部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。这就是快速排序,我们把选定的那个值称为中心值,如果中心值为序列中的最大值,那么其实就相当于冒泡排序了。

2.2.参考代码:

2.3.效率分析

快速排序时间与划分是否对称有关。快速排序的平均时间复杂度为o(n*logn),至于为什么是o(n*logn)。且常数因子很小,所以就平均时间而言,快速排序是很好的内部排序方法。在待排序序列有序或逆序时不宜选用快速排序。 最佳情况下,每次划分都是对称的,由于中心值不再考虑,所以得到的两个子问题的大小不可能大于n/2,同时一趟快速排序时间为o(n),所以运行时间递归表达式: T(n)<=2T(n/2)+o(n)。 最坏情况下,每次划分都很不对称,T(n)=T(n-1)+o(n),可以用递归树来解,第i层的代价为n-i+1.总共有n层。把每一层代价加起来有n-1个n相加。所以这个递归式的解为T(n)=o(n^2),此时就是冒泡排序。

3.直接选择排序

3.1.概述 直接选择排序也是一种简单的排序方法,它的基本思想是:第一次从A[0]~A[n-1]中选取最小值,与A[0]交换,第二次从A{1}~A[n-1]中选取最小值,与A[1]交换,....,第i次从A[i-1]~A[n-1]中选取最小值,与A[i-1]交换,.....,第n-1次从A[n-2]~A[n-1]中选取最小值,与A[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列.

3.2.参考代码

3.3.效率分析 容易看出,要插入的记录个数为n-1,其中关键字的比较次数和记录移动次数是依赖于给出的待排序序列是否基本有序。在最佳情况下(待排序序列有序),比较次数和移动次数时间为o(1),所以时间复杂度为o(n)。在最坏情况下(待排序序列逆序)和平均时间均为o(n^2).我们可以看出,直接插入排序适合记录数比较少、给定序列基本有序的情况。早了解和熟悉了排序过程后,我们发现,直接插入排序是一种稳定的原地排序算法。

4.折半插入排序

4.1.概述

折半插入排序是对直接插入排序的简单改进,对于直接插入排序而言,当第i-1趟需要将第i个元素插入前面的0~i-1个元素序列中时,总是需要从i-1个元素开始,逐个比较每个元素,直到找到它的位置。这显然没有利用前面0~i-1个元素已经有序这个特点,而折半插入排序则改进了这一点。

对于折半插入排序而言,当需要插入第i个元素时,它不会逐个进行比较每个元素,而是:

(1)计算0~i-1索引的中间点,也就是用i索引处的元素和(0+i-1)/2索引处的元素进行比较,如果i索引处的元素值大,就直接在(0+i-1)/2~i-1半个范围内进行搜索;反之在0~(0+i-1)/2半个范围内搜索,这就是所谓的折半;

(2)在半个范围内搜索时,按照(1)的方法不断地进行折半搜索,这样就可以将搜索范围缩小到1/2、1/4、1/8…,从而快速的确定插入位置;

4.2.参考代码:

4.3.效率分析 折半插入排序是对直接插入排序的一种改进,这种改进只考虑了关键字比较次数,并没有减少移位次数,所以平均时间和最坏情况下(待排序序列逆序)时间复杂度o(n^2),如果记录数量很大的话,这两种情况下是优于直接插入排序。再来看一下最佳情况(待排序序列有序),此时关键字比较次数并不为o(1),时间复杂度为o(n*log2n)。(其中折半查找时间复杂度o(log2n),这个在以后写查找的时候再分析,这里不做详细讲解。)。所以在记录数较小、待排序序列基本有序情况下直接插入排序优于折半插入排序。此外,折半插入排序是不稳定的原地排序,实现起来也较复杂。

看了这么多比较经典的排序算法,有没有觉得算法真的是一个神奇的“道具”。稍微一改优化就能大大提升效率。针对不同的情况选择最优的算法,提高效率也正是我们在项目中所追求的。如果小伙伴们有更多的有趣和经典的算法,也欢迎给老九君留言哦,我们都会不断的完善和补充!

老九学堂出品

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏.NET技术与企业级解决方案

C#开发BIMFACE系列3 服务端API之获取应用访问凭证AccessToken

BIMFACE 平台为开发者提供了大量的服务器端 API 与 JavaScript API,用于二次开发 BIM 的相关应用。

11530
来自专栏网络小说作家的编程技术沉思录

JAVA中for与while关于内存的细节问题

JAVA的程序结构有顺序结构,循环结构,分支结构,以及跳转结构,而循环结构里经常用到的无外乎有以下几种:for循环,while循环,以及do-whil...

10630
来自专栏二狗的DBA之路

将excel文件导入到数据库

参考:http://blog.csdn.net/jayxujia123/article/details/13684313

10130
来自专栏程序生活

GAN对抗网络入门教程

译:A Beginner's Guide to Generative Adversarial Networks (GANs) https://skymind.a...

17130
来自专栏机器人课程与技术

ROS2编程基础课程--接口

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

9240
来自专栏网络小说作家的编程技术沉思录

如何写出一个性能优化的单例模式

单例模型是面试当中最常见的一种设计模式,它是一种对象创建模式,用于产生一个对象的具体实例,可以确保系统中一个类只产生一个实例。

10920
来自专栏二狗的DBA之路

LENGTH 和 CHAR_LENGTH 的区别

char(N) 和 varchar(N) 这里的N指的是字符长度,而不是字节长度。就是说可以插入N个字符的长度的内容(不管插入的是英文还是中文,反正是按照长度...

7020
来自专栏BAT的乌托邦

@Qualifier高级应用---按类别批量依赖注入(QualifierAnnotationAutowireCandidateResolver原理详解)【享学Spring】

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

23920
来自专栏二狗的DBA之路

pt-archiver Bug不会迁移max(id)那条数据的解决方法

参考: http://www.ttlsa.com/mysql/pt-archiver-bug-cannot-migration-max-id-record/

7230
来自专栏算法channel

求两个有序数组合并后的中位数,最透讲解| 腾讯面试编程50题(三)

本文是腾讯50道常考编程题之一:求解两个有序数组合并后的中位数,属于 "Hard" 难度,在校招中难倒一大波校招生。本文提供一种基本解法:基于归并排序。并对归并...

14920

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励