十四、排序算法

本章按

①插入类排序（插入、希尔）②选择类排序（选排、堆排）③交换类排序（冒泡、快排）④归并类排序（归并）展开介绍。需要特别注意其中快排的划分算法、归并排序合并两个有序序列的算法、堆排序引入的二叉堆等。了解掌握不同排序算法的时间空间复杂度与是否稳定。

插入类排序（插排、希尔）

其核心思想是将待排序元素划分为“已排序”和“未排序”两部分，每次从“未排序”的元素中选择一个插入到“已排序”的元素中。

①插入排序

平均时间复杂度：O(N^2)，空间复杂度O(1)。

②希尔排序（或称缩小增量排序）

每趟排序都会将原序列分割成间隔为h的不同子序列，并通过插入排序对所有子序列进行排序，每趟排序所取的间隔h逐渐缩小至1，此时相当于对原序列进行一次插入排序。若序列长度为n，通常选取的比较好的增量序列为。

时间复杂度： O(N^7/6)~O(N^3/2)，空间复杂度O(1)。

选择类排序：选择排序、堆排序

其核心思想是每次找出整个序列中第i小的关键字，并将它与位于第i个位置的关键字交换，这样操作n次后，整个序列就有序了。

①选择排序

平均时间复杂度： O(N^2)，空间复杂度O(1)。

②堆排序

堆排序相较于选择排序，它引入了二叉堆这一数据结构，将寻找最小值的操作的时间复杂度从O(N)降低到O(logN)。由于二叉堆是一棵完全二叉树，因此可以用一个数组存储这个二叉堆。

平均时间复杂度： O(NlogN)，空间复杂度O(1)。

C++的priority_queue就是大根堆的一种实现。有关题目中，只需掌握与堆相关的泛型算法即可（make_heap、is_heap、heap_sort）。

交换类排序：冒泡排序、快速排序

交换类排序是通过交换逆序关键字进行排序的方法。（对待排序列s，若i<j且s[i]>s[j]，则称s[i]和s[j]为一对逆序关键字）

①冒泡排序

每次检查相邻两个元素，若前面的关键字大于后面的关键字（此处排成升序），就将相邻的两个关键字交换。

平均时间复杂度： O(N^2)，空间复杂度O(1)。

②快速排序

按基值（枢纽元）划分左右区间并归位基值。快排在序列有序时性能最差，但可以稍加调整避免这种情况，并可以和堆排序结合（因为堆排序最坏都有O(NlogN)），即可保证对几乎所有输入都可达到不超过O(NlogN)的时间复杂度。

平均时间复杂度： O(NlogN)，空间复杂度O(N)。

注意其中相关的partition划分算法：void partition(b,e,p1)/void stable_partition(b,e,p1)和bool is_partitioned(b,e,p1)的使用。

归并类排序：归并排序

应用分治思想的递归算法，对序列s进行归并排序的具体步骤为①：若s关键字的个数为0或1，不需排序，直接返回；②将s分为左半部分序列s1与右半部分序列s2，对s1和s2分别进行归并排序；③将排序后的有序序列s1和s2合并为一个有序序列s。

其中第3步中需开辟一个数组存储最终合并后的s，空间复杂度为O(N)。其原理是利用双指针分别从两个有序序列中选择最小的值放入数组，直到遍历完两个序列。

其中合并两个有序序列为线性算法，此外需要递归调用，因此时间复杂度为O(NlogN)。但由于合并的过程中需要开辟数组存储合并结果，因此空间复杂度为O(N)。

注意C++标准库中合并的泛型算法_OIter merge(b,e,b2,e2,d)/_OIter merge(b,e,b2,e2,d,p2)与void inplace_merge(b,m,e)/void inplace_merge(b,m,e,p2)的用法。

可以自己模拟一下两个有序序列的合并过程：

回顾sort相关泛型算法

bool is_sorted(b,e)/bool is_sorted(b,e,p2)：表示序列是否按序列排列；

_FIter is_sorted_until(b,e)/_FIter is_sorted_until(b,e,p2)：查找从第一个元素开始最长升序连续子序列，返回尾后迭代器；

void partial_sort(b,m,e)/void partial_sort(b,m,e,p2)：将b到e序列中从小到大将元素放到b到m区间中，其余放到m到e区间中（用于找到序列中最小的m-b个数/前m-b个最小值）；

void nth_element(b,m,e)/void nth_element(b,m,e,p2)：使迭代器m指向的元素恰好是整个序列排好序后该位置上的值（用于找到序列中第m-b+1个最小值）。