《算法与数据结构考研试题精析》笔记(10) - 排序
相关内容介绍博客
Internal Sorting
若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比较和记录的移动。
各种内部排序算法的排序过程中结果的特点
每一趟有一个元素达到它的最终位置：交换(冒泡、快排)，选择(简单选择、堆排序)。
基于交换的快排达到最终位置的元素是枢纽元素，可能出现在顺序表的任何位置(表的头部或者尾部或者中间都有可能，这依据选择枢纽的算法)； 而其他算法下，出现的最终位置都是在顺序表的头部或者尾部。
n趟插入排序之后，序列的首或尾会出现一个有序子序列：插入、冒泡、选择。
n趟插入之后出现的子序列，不一定是关键字最小的。比如
11,12,13,7,8,9,23,4,5； 但是对于冒泡和选择来说，在首尾出现的有序子列是处于其最终位置上的，所以也就一定是关键字最小的。比如：4,5,7,8,9,23,11,12,13。
空间复杂度不是O(1)的内部排序算法：归并O(n)，快排O(logn)，基数排序O(r).
- 稳定的算法：冒泡、直接插入、折半插入、归并、基数排序
- 不稳定的算法：Shell排序、快排、简单选择排序、树形排序、堆排序
大部分排序算法仅适用于顺序存储的线性表，但是直接插入算法可用于链式存储的线性表。
内排序算法不一定要求数据以顺序方式存储。
不基于比较和移动，基于关键字各位的大小的排序算法：基数排序。
如果题目中出现“基于比较方法的n个数据的内部排序”，这就直接排除了基数排序。
比较次数与序列初始状态无关的算法：归并、简单选择、折半插入。
为什么折半插入的比较次数与序列的初始状态无关？ 因为通过折半查找确定最终位置的时候，若设有序的子表长度为m，则比较次数必为
O(logm)。
排序趟数与序列的原始状态有关的排序算法：冒泡、快排。
当枢纽元素比较靠近顺序表的首尾的时候，趟数增加。
适合并行处理的排序算法：快排。
【并行处理】见博客《使用并行计算大幅提升递归算法效率》
注意点
题目问的是排序算法中的比较次数还是交换次数！
注意是“简单选择算法”还是“直接插入算法”！
细节
【直接插入中监视哨的作用】免去查找过程中每一步都要检测整个查找表是否查找完毕，提高了查找效率。
Shell排序的组内排序采用的是直接插入排序。
对于关键字为实数的情况，基数排序并不适合。
当待排序列基本有序的时候，直接插入最好，快排最糟糕。
直接插入
O(n)，快排O(n^2)。
对于判断一个序列是不是快排的结果，不能只看是不是有个枢纽落到其最终位置上，还要看其他元素的位置是不是符合快排的交换规则(在给定了原序列的情况下)。
对n个记录的线性表进行快排，为减少算法的递归深度，每次分区后，先处理较短的部分。
对n个元素进行堆排序，则在初始建堆过程中，需要进行的筛选次数为n/2.
为什么筛选次数为
n/2？ 【答】建堆从最后一个分支结点开始筛选，最后一个分支结点为n/2。 由此也可以知道，我们建堆的时候，入手的对象是分支结点，而且是从最后一个分支结点开始比较。
建堆的时候，要注意当元素从上层被换下来的时候，还要注意换下来之后还要和当前所处位置的下一层进行比较，如此循环往复，确定其是否完全满足堆的定义。
算法是否稳定并不是判断算法好坏的标准，只是说明了一个性质。
【错误说法】在分配排序时，最高位优先分配法MSD比最低位优先分配法LSD简单。
只是实现关键字排序的两种次序罢了，无所谓两者何者更简单何者更复杂。
快速排序在每次划分能得到两个长度相等的子文件的情况下最易发挥其长处。
【退排序】堆排序是一种选择排序。堆实际上是一棵完全二叉树结点的层次序列。对含n个元素的序列进行排序时，堆排序的时间复杂度为O(nlogn)，所需的附加结点为1个。
按LSD进行多关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用稳定的排序方法。
External Sorting
影响外排序的时间因素主要是内存与外设交换信息的总次数。
外排中使用置换选择算法的目的是产生更长的初始归并段以减少初始归并段的个数。
在外部排序中，使用选择树法可以减少初始归并段的数量。
磁盘排序(外排序)过程主要是先生成初始归并段，然后对初始归并段合并，而提高排序速度很重要的是减少外存信息的读写次数，我们采用增加归并路数和减少初始归并段个数的方法来提高排序速度。
设工作区的容量为W，则置换-选择排序算法所得到的初始归并段长度的期望值为2W。