频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
C++研发面试笔记:常用算法--排序算法
2016-10-04 08:56:26      个评论    来源:tostq的专栏  
收藏   我要投稿

【C++研发面试笔记】19. 常用算法-排序算法

19.1 排序算法分类

比较排序和非比较排序:
常见的排序算法都是比较排序,非比较排序包括计数排序、桶排序和基数排序,非比较排序对数据有要求,因为数据本身包含了定位特征,所有才能不通过比较来确定元素的位置。
比较排序的时间复杂度通常为O(n^2)或者O(nlogn),比较排序的时间复杂度下界就是O(nlogn),而非比较排序的时间复杂度可以达到O(n),但是都需要额外的空间开销。
C++研发面试笔记:常用算法--排序算法


19.2 冒泡排序

冒泡排序通过重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来,直到没有再需要交换的元素为止(对n个项目需要O(n^2)的比较次数)。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

19.2.1 实现步骤

比较相邻的元素。如果第一个比第二个大,就交换他们两个。  对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。 针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

19.2.2 实现性能

最差时间复杂度O(n^2)
最优时间复杂度O(n) 
平均时间复杂度O(n^2)
最差空间复杂度:总共O(n),需要辅助空间O(1)

19.2.3 具体代码

C++研发面试笔记:常用算法--排序算法


19.3 简单选择排序

常用的选择排序方法有简单选择排序和堆排序,这里只说简单选择排序,堆排序后面再说。
假设所排序序列的记录个数为n,i 取 1,2,…,n-1。
从所有n-i+1个记录(Ri,Ri+1,…,Rn)中找出排序码最小(或最大)的记录,与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。

19.3.1 选择排序性能

在简单选择排序过程中,所需移动记录的次数比较少。最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。  最坏情况下,即待排序记录初始状态是按第一条记录最大,之后的记录从小到大顺序排列,则需要移动记录的次数最多为3(n-1)。 即进行比较操作的时间复杂度为O(n^2),进行移动操作的时间复杂度为O(n)。  简单选择排序是不稳定排序。

19.3.2 排序算法稳定性

通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。
排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。
不稳定排序算法口诀:快希选堆(快些选堆)

19.3.3 具体实现

C++研发面试笔记:常用算法--排序算法


19.4 插入排序

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。

比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。 如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。 所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

19.4.1 插入排序性能

将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,是稳定的排序方法。
空间复杂度O(1)。 
平均时间复杂度O(n^2)。
最差情况:反序,需要移动n*(n-1)/2个元素 ,运行时间为O(n^2)。
最好情况:正序,不需要移动元素,运行时间为O(n)。

19.4.2 折半插入排序

直接插入排序中要把插入元素与已有序序列元素依次进行比较,效率非常低。 
折半插入排序,使用使用折半查找的方式寻找插入点的位置, 可以减少比较的次数,但移动的次数不变, 时间复杂度和空间复杂度和直接插入排序一样,在元素较多的情况下能提高查找性能。

19.4.3 具体实现

C++研发面试笔记:常用算法--排序算法


19.5 堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值。
由于堆中每次都只能删除第0个数据,通过 取出第0个数据再执行堆的删除操作、重建堆(实际的操作是将最后一个数据的值赋给根结点,然后再从根结点开始进行一次从上向下的调整。),然后再取,如此重复实现排序。

19.5.1 堆排序性能

空间复杂度O(1)。 
平均时间复杂度O(nlogn)。
最差情况:运行时间为O(n^2)。
最好情况:运行时间为O(n)。
不稳定。

19.5.2 具体实现

C++研发面试笔记:常用算法--排序算法

点击复制链接 与好友分享!回本站首页
上一篇:C++研发面试笔记:基本数据结构-查找表与并查集
下一篇:Visual C++ 之 调试程序
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站