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

19.1 排序算法分类

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

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 具体代码

19.3 简单选择排序

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

19.3.1 选择排序性能

19.3.2 排序算法稳定性

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

19.3.3 具体实现

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 具体实现

19.5 堆排序

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

19.5.1 堆排序性能

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

19.5.2 具体实现