共计 3743 个字符，预计需要花费 10 分钟才能阅读完成。
下面哪种排序方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。（插入排序）
对序列 15, 9, 7, 8, 20, -1, 4 进行排序，若经一趟排序后的排列为 9, 15, 7, 8, 20, -1, 4，则采用的是（C）排序。
- A. 选择
- B. 堆
- C. 直接插入
- D. 冒泡
选择排序是每次选择未排序子列中最大（最小）的放到最后，显然 4 不是最值，所以 A 不对；
冒泡排序是相邻两两比较，把最大的顶上去（顶到最左边或者最右边），显然边上两个元素不是最值，所以 B 也不对；
希尔排序是先分组，然后针对组内采取插入排序，如果是希尔排序，那么 9 和 15 颠倒，20 和 - 1 也应该颠倒，所以 D 也不对；
插入排序是从第二项开始与前面每一项比较，如果小于那一项，则插入那一项前面，C 中第二项 9 比 15 小，所以放到 15 前面，完成一趟
对初始状态为递增序列的数组按递增顺序排序，最省时间的是插入排序算法，最费时间的是算法（快速排序）
堆排序：最好最坏都是 nlogn
快排：最好情况一趟比较可以划分两等份 nlogn 最坏相对有序 n *n
插入：最好相对有序 n 最坏 n *n
归并：最好最坏都是 nlogn
将序列 (Q, H, C, Y, P, A, M, S, R, D, F, X) 中的关键字按升序排列，则（F,H,C,D,P,A,M,Q,R,S,Y,X）是以第一个元素为枢轴的快速排序一趟扫描的结果。
以 Q 为基准值, 放到外面
首先从后往前, 到 f 比 q 小, 填充到刚才 q 的位置
然后从前往后到 y 比 q 大, 放到刚才的 f 的原始位置
再从后往前,d 比 q 小, 放到 y 原来的位置
再从前往后, 到 s 比 q 大, 放到 d 原来的位置
接下来, 前后两个标志碰头了
将基准 q 放到刚才最后移动的 s 的原来位置上
快速排序方法在要排序的数据已基本有序情况下最不利于发挥其长处。
快速排序的基本思想是以基准元素为中心，将待排序表分成两个子表，然后继续对子表进行划分，直到所有子表的长度为 1。如果每次划分结果，两个子表长度相等，则效率最高，如果一个子表的长度为 0 则效率最低。对已基本有序的表以第 1 个为标准进行划分时，其中一个表长度将基本为 0，效率最低。
设有 5000 个元素，希望用最快的速度挑选出前 10 个最大的，采用（堆排序）方法最好。
用堆排序最好，因为堆排序不需要等整个排序结束就可挑出前 10 个最大元素，而快速排序和基数排序都需等待整个排序结束才能知道前 10 个最大元素。
何为堆？
若需在 O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（C）。
- 快速排序
- 堆排序
- 归并排序
- 直接插入排序
若要求尽可能快地对序列进行稳定的排序，则应选（B）。
- A.
快速排序
- B.
归并排序
- C.
冒泡排序
“快些（希）选队（堆）”不稳定；稳定的排序算法：插入排序、冒泡排序、归并排序、基数排序
直接插入，简单选择和冒泡排序都是比较慢的。
当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（直接插入排序）。
当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需 n - 1 趟排序，也即时间复杂度仍为 O(n^2)。
而对简单选择排序来说，其比较次数与待排序列的初始状态无关，都是每次选择未排序子列中最大（最小）的放到最后；
归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为 O(n log2n)；
直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即 n - 1 趟比较的时间复杂度由 O(n^2)降至 O(n)。
各种排序方法的选择:
①就平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。当 n 较大时，归并排序较堆排序省，但归并排序所需的辅助空间最大。
②简单排序方法中，直接插入排序最简单，当待排序的结点已按键值“基本有序”且 n 较小时，则应采用直接插入排序或冒泡排序，直接插入排序比冒泡排序更快些，因此经常将直接插入排序和其他的排序方法结合在一起使用。
③当 n 很大且键值位数较小时，采用基数排序较好；而当键值的最高位分布较均匀时，可先按其最高位将待排序结点分成若干子表，而后对各子表进行直接插入排序。
④从方法的稳定性来比较，直接插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法；而直接选择排序、希尔排序、堆排序和快速排序都是不稳定的排序方法。
内部排序方法的选择: 各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有：待排序的记录个数；记录本身的大小；记录的键值分布情况等。
若待排序的记录个数 n 较小时，可采用简单排序方法 若 n 较大时，应采用快速排序或堆排序。若待排序的记录已基本有序，可采用起泡排序。
链式基数排序采用的是 LSD 的方法
而基数排序就是借助“分配”和“收集”对单逻辑关键字进行排序的方法
排序的时间复杂度和空间复杂度
快速排序的时间复杂度为O(nlogn)，空间复杂度也是O(nlogn)。
归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。
堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。
选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
在分配排序时, 最高位优先分配法比最低位优先分配法简单(错，两者无直接关系)
基数排序是桶排序的改进，改进空间复杂度。而基数排序中，只有最低位优先分配法才能取得正确结果，但是最高位和最低位的时间复杂度一样的。
进一步了解桶排序和基数排序
桶排序和基数排序均属于分配排序。分配排序的基本思想：排序过程无须比较关键字，而是通过用额外的空间来 ” 分配 ” 和 ” 收集 ” 来实现排序，它们的时间复杂度可达到线性阶：O(n)。简言之就是：用空间换时间，所以性能与基于比较的排序才有数量级的提高！
桶排序(Bucket Sort)，也称箱排序
基本思想：设置若干个箱子，依次扫描待排序的记录 array[0]，array[1]，…，array[n – 1]，把关键字等于 k 的记录全都装入到第 k 个箱子里 (分配)，然后按序号依次将各非空的箱子里的记录收集起来，从而完成排序。
桶排序所需要的额外空间取决于关键字的个数，若 array[0..n – 1] 中关键字的取值范围是 0 到 m – 1 的整数，则必须设置 m 个箱子。因此箱排序要求关键字的类型是有限类型，否则可能要无限个箱子。一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的，故箱子的类型应设计成链表为宜。
在实现上，桶排序一般采用另外的变种。即：把 [0，m) 划分为 m 个大小相同的子区间，每一子区间是一个桶。然后将 n 个记录分配到各个桶中。因为关键字序列是均匀分布在 [0，m) 上的，所以一般不会有很多个记录落入同一个桶中。由于同一桶中的记录其关键字不尽相同，所以必须采用关键字比较的排序方法 (通常用插入排序) 对各个桶进行排序，然后依次将各非空桶中的记录收集起来即可。
时间复杂度分析：桶排序的平均时间复杂度是线性的，即 O(n)。但最坏情况仍有可能是 O(n ^ 2)。
空间复杂度分析：桶排序只适用于关键字取值范围较小的情况，否则所需箱子的数目 m 太多导致浪费存储空间和计算时间。
基数排序(Radix Sort)
基本思想：基数排序是对桶排序的改进和推广。如果说桶排序是一维的基于桶的排序，那么基数排序就是的基于桶的排序。我这么说，可能还不是太清楚。比方说：用桶排序对 [0, 30] 之间的数进行排序，那么需要 31 个桶，分配一次，收集一次，完成排序；那么基数排序则只需要 0 – 9 总共 10 个桶（即关键字为数字 0 – 9），依次进行个位和十位的分配和收集从而完成排序。
时间复杂度分析：基数排序的时间负责度为 O(n)。
空间复杂度：基数排序所需的辅助存储空间为 O(n + r * d)，其中 r 为记录中关键字分量的最大个数，d 为关键字的个数。比如说：待排序为 0 – 999，那么分量的最大个数为 3，关键字的个数为 10（0 – 9）。
补充：基数排序是稳定的。若排序文件不是以数组 array 形式给出，而是以单链表形式给出(此时称为链式的基数排序)，则可通过修改出队和入队函数使表示箱子的链队列无须分配结点空间，而使用原链表的结点空间。人队出队操作亦无需移动记录而仅需修改指针。虽然这样一来节省了一定的时间和空间，但算法要复杂得多，且时空复杂度就其数量级而言并未得到改观。
在用堆排序算法排序时, 如果要进行增序排序, 则需要采用 ” 大根堆”
在用堆排序算法排序时, 如果要进行增序排序, 则需要采用“大根堆”，减序排列则要采用“小根堆”。
堆排序的方法：首先，将当前的数组调整为堆，也就是建立堆。然后把根与最后的元素交换，重新调整堆，然后再把调整后的根与倒数第二个元素交换，再重新调整堆，直到全部元素交换完毕。这样，对于大根堆，最大元素排列到了最后，是递增排序。而小根堆，最小元素排列到了最后，是递减排序。
在执行某个排序算法过程中, 出现了排序码朝着最终排序序列位置相反方向移动, 则该算法是不稳定的(错)
稳定是指存在多个具有相同的关键字的记录，若经过 排序，这些记录的相对次序保持不变，与排序码移动方向无关
