CS408/Data-Structrue/9-sort.md

排序

基本概念

• 排序：将一个数据元素的任意序列重新排列成一个按关键字有序的序列。
• 内部排序：待排序的记录存放在计算机的内存中所进行的排序操作称为内部排序。
• 外部排序：待排序的记录数量很大，以致内存一次不能容纳全部记录，在排序过程中需要访问外存的排序过程称为外部排序。
• 稳定的排序：比如一个序列是“$1,4,3,3*,2$”，按从小到大排序后变成“$1,2,3,3*,4$”，就叫做稳定排序，即3和3*相对顺序不变。如果相同关键字的顺序发生了改变，则是不稳定的排序。稳定性的需要看具体的应用场景。
• 内部排序的算法性能取决于算法的时间复杂度和空间复杂度，而时间复杂度一般是由比较和移动次数决定的。外部排序除此之外还要考虑磁盘读写速度和次数。
• 大部分排序算法都仅适用于顺序存储的线性表。
• 大部分排序需要经过比较和移动两个过程。（基数排序不需要比较）排序时至少需要比较$\lceil\log_2(n!)\rceil$次。每次比较两个关键字后，仅出现两种可能的转移。假设整个排序过程至少需要做$t$次比较。则显然会有$2^t$种情况。由于$n$个记录共有$n!$种不同的排列，因而必须有$n!$种不同的比较路径，于是有$2^t\geqslant n!$，所以得到不等式。

插入排序

插入排序共性

• 插入排序的排序序列分为未排序序列和已排序序列。
• 插入排序就是将选定的目标值插入到对应的位置，然后不断增长已排序序列并缩减未排序序列的过程。
• 每一趟排序都不能保证有一个元素到达最终的位置上。

直接插入排序

直接插入排序过程

每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成为止。

直接插入排序性能

空间复杂度为$O(1)$。

时间复杂度主要来自对比关键字，移动元素，若有$n$个元素，则需要$n-1$趟处理。

最好情况是原本的序列就是有序的，需要$n-1$趟处理，每次只需要对比一次关键字，不用移动元素，时间复杂度为$O(n)$。

最坏情况是原本的序列是逆序的，需要$n-1$趟处理，第$i$趟处理需要对比关键字$i+1$次，移动元素$i+2$次，时间复杂度是$O(n^2)$。

所以平均时间复杂度是$O(n^2)$。

直接插入排序算法是稳定的。

如果使用链表实现直接插入排序，移动元素的次数变少了，但是关键字对比次数仍然时$O(n^2)$，从而整体时间复杂度依然是$O(n^2)$。

直接插入排序特性

• 在待排序的元素序列基本有序的前提下，直接插入排序效率最高的。
• 直接插入排序进行$n$躺后能保证前$n+1$个元素是有序的，但是不能保证其都在最终的位置上。

二分插入排序

二分插入排序过程

也称为折半插入排序，是对直接插入排序的优化，在寻找插入位置时使用二分查找的方式。

当$data[mid]==data[i]$时，为了保证算法的稳定性，会继续在$mid$所指位置右边寻找插入位置。

当$low>high$时停止折半查找，并将$[low,i-1]$内的元素全部右移，并把元素值赋值到$low$所指的位置。

折半插入排序是找到位置了后一起移动元素，而直接插入排序是边查找边排序。

二分插入排序性能

空间复杂度为$O(1)$。

二分插入排序是稳定的。

比起直接插入排序，比较关键字的次数减少为$O(n\log_2n)$，移动元素的次数没变，所以总体时间复杂度为$O(n^2)$。

二分插入排序特性

• 对于直接插入的优化仅在于二分查找的比较次数。
• 二分插入排序进行$n$躺后能保证前$n+1$个元素是有序的，但是不能保证其都在最终的位置上。

希尔排序

又称缩小增量排序。

希尔排序过程

希尔排序也是对直接插入排序的优化。直接插入排序对于基本有序的序列排序效果较好，所以就希望序列能尽可能基本有序。从而希尔排序的思想就是先追求表中元素部分有序，然后逐渐逼近全局有序。

先将整个待排序元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的），分别进行直接插入排序，然后缩小增量重复上述过程，直到增量为$1$。每次对比只对比两个以上的个元素进行插入交换。

增量序列的选择建议是第一趟选择元素个数的一半，后面不断缩小到原来的一半。

希尔排序性能

空间复杂度为$O(1)$。

而时间复杂度和增量序列的选择有关，目前无法使用属性手段证明确切的时间复杂度。最坏时间复杂度为$O(n^2)$，在某个范围内可以达到$O(n^{1.3})$。

希尔排序是不稳定的。（因为相同的元素可能分到不同的子序列中进行重排打乱原有顺序）

希尔排序只适用于顺序表而不适合用于链表，无法快速进行增量的访问。

希尔排序特性

• 希尔排序在最后一趟前都不能保证元素在最后的位置上。
• 希尔排序在最后一趟前都不能保证元素是有序的。

交换排序

交换排序共性

• 交换排序即根据序列中两个元素关键的比较结构然后交换这两个记录在序列中的位置。
• $n$趟排序后就有$n$个元素到达最终的位置上。

冒泡排序

重点就是相邻两两比较。

冒泡排序过程

从后往前或从前往后两两比较相邻元素的值，若逆序则交换这两个值，如果相等也不交换，直到序列比较完。这个过程是一趟冒泡排序，第$i$趟后第$i$个元素会已经排序完成。每一趟都会让关键字最小或最大的一个元素到未排序队列的第一个或最后一个。一共需要$n-1$趟排序。

冒泡排序中所产生的有序子序列一定是全局有序的（不同于直接插入排序），也就是说，有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。

冒泡排序性能

空间复杂度为$O(1)$。

最好情况下即本身序列有序，则比较次数是$n-1$，交换次数是$0$，从而时间复杂度是$O(n)$。

最坏情况是逆序情况，比较次数和交换次数都是$\dfrac{n(n-1)}{2}$，所以时间复杂度是$O(n^2)$。

从而平均时间复杂度是$O(n^2)$。

冒泡排序是稳定的。

冒泡排序可以用于链表。

冒泡优化

对于每行冒泡进行优化：如果发现排序前几轮就已经实现了排序成功，那么后面的排序岂不是都浪费了时间进行比较？可以在第一轮循环中设置一个布尔值为$false$，如果在这一轮发生排序交换就设置为$true$，如果一轮结束后发现这个值还是$false$，说明这一轮没有进行交换，表示已经排序成功，就直接所有退出循环。

对于每列冒泡进行优化：默认每一轮冒泡是从$[length-i]$结束，如一共$5$个元素排序，需要$4$轮排序，第二轮冒泡排序应该从$0$开始，到$3$结束，因为最后一个元素4已经在第一轮排序成功。但是如果在第二轮发现$2$，$3$已经排序成功了不需要交换，那么默认排序方法第三轮还是要从$0$到$2$进行排序，还要比较一次$1$和$2$位置的数据，这就造成了浪费，那么如何解决？记录每一轮发生比较的元素的最大索引值，下一轮比较到这个索引值直接结束，不需要继续比较后面的元素。如果最大索引值为$0$则直接退出。这就进一步优化了上面一种策略。

void Bubble(int[] a) {
   int n = a.length - 1;
   while (true) 
   {
      //表示最后一次交换元素位置
      int last = 0;
      for (int i = 0; i < n; i++) 
      {
         if (a[i] > a[i + 1]) {
            swap(a, i, i + 1);
            last = i;
         }
      }
      n = last;
      if (n == 0) 
      {
         return;
      }
   }
}

冒泡排序特性

• 冒泡排序产生的序列全局有序，$n$趟排序后第$n$个元素到达最终的位置上，前$n$个或后$n$个位置的元素确定。

快速排序

排序过程类似于构建二叉排序树。基于分治法。

快速排序过程

取待排序序列中的某个元素$pivot$作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的关键字均小于或等于基准元素的关键字，右子序列的关键字则大于基准元素的关键字，称进行了一趟快速排序（一次划分），这个$pivot$已经成功排序。然后分别对两个子序列继续进行快速排序，直至整个序列有序。

单边循环快排

即$lomuto$洛穆托分区方案。

1. 选择最右边的元素值做标杆，把标杆值放入$pivot$变量中。
2. 初始时，令$low$和$high$都指向最左边的元素。其中$low$用于被动向右移动，维护小于标杆值的元素的边界，即每次交换的目标索引，一旦交换$low$就向右移动一个；$high$用于主动向右移动，寻找比标杆值小的元素，一旦找到就与$low$指向元素进行交换。
3. 然后$high$开始移动，判断$high$指向的元素值是否小于$pivot$值，如果不小于就继续向右移动。
4. 当遇到比标杆小的值，$high$指向的值就和$low$指向的值进行交换，如果$high$和$low$指向的值为同一个则不进行交换，然后$low$右移一个，$high$继续右移查找。
5. $high$继续移动，最后$high>=pivot$时将基准点元素值与$low$指向值进行交换，该轮排序结束。此时$low$指向的位置就是$pivot$值所应该在的位置。
6. 返回基准点元素所在索引，从而确定排序上下边界，递归继续执行排序。

双边循环快排

分为普通分区方案和$hoare$霍尔分区方案。逻辑基本上一样，只是边界选择方式不同。

1. 先选择个值做标杆，一般为最左边值，把标杆值放入$pivot$变量中。
2. 初始时，令$high$指向序列最右边的值，$low$指向序列最左边的值。
3. 然后从$high$开始不断左移，当遇到比标杆大或等于的值时$high--$。
4. 如果发现比标杆小的值，即$high<pivot$，需要交换，然后$high$不动，$low++$开始移动去找要交换的大于标杆的值。
5. 若$low$所指向的值比标杆小或等于，则$low++$进行寻找。（为什么要加上一个等于标杆值可以继续向右移动的条件？因为标杆值默认是第一个值，即初始化$pivot$跟$low$指向同一个值，如果只能小于标杆值才能继续移动不交换，则在第一个元素时，由于标杆值被初始化赋值为第一个值，则标杆$pivot$值等于$low$值，从而导致$low$值跟$high$值进行交换，导致$pivot$标杆值被交换走了，标杆值变为了最开始最右边的$high$值，导致了排序有问题）
6. 若$low$所指向的值比标杆大，则$low$值与$high$值进行交换。
7. 交换后$low$不动，$high--$开始移动。回到步骤三开始执行。
8. 当$low=high$时表示$low$和$high$之前的元素都比基准小，$low$和$high$之后的元素都比基准大，完成了一次划分。然后把基准元素放入$low==high$指向的位置。
9. 不断交替使用$low$和$high$指针进行对比。对左右子序列进行同样的递归操作即可，从步骤三开始。若左右两个子序列的元素数量小等于一，则无需再划分。

即对序列进行比较，有头尾两个指针，尾指针开始比较向前移动，若指向值比对比值小则要交换，交替让头指针开始移动，否则不改变指针则尾指针继续向前；同理头指针向后移动，若指向值比对比值大则交换，交替让尾指针移动，否则不改变指针则头指针继续向后。最后头尾指针指向一个位置，将对比值插入到当前值，此时一趟完成。

洛穆托分区与霍尔分区比较。

快速排序性能

由于快速排序使用了递归，所以需要递归工作栈，空间复杂度与递归层数相关，所以为$O(递归层数)$。

每一层划分只需要处理剩余的待排序元素，时间复杂度不超过$O(n)$，所以时间复杂度为$O(n\times$归层数$)$。

而快速排序会将所有元素组织成为二叉树，二叉树的层数就是递归调用的层数。所以对于$n$个结点的二叉树，最小高度为$\lfloor\log_2n\rfloor+1$，最大高度为$n$。

从而最好时间复杂度为$O(n\log_2n)$，最坏时间复杂度为$O(n^2)$，平均时间复杂度为$O(n\log_2n)$；最好空间复杂度为$O(\log_2n)$，最坏空间复杂度为$O(n)$，平均空间复杂度为$O(\log_2n)$。

所以如果初始序列是有序的或逆序的，则快速排序性能最差（速度最慢）。若每一次选中的基准能均匀划分，尽量让数轴元素平分，则效率最高（速度最快）。性能与分区处理顺序无关。

所以对于快速排序性能优化是选择尽可能能中分的基准元素，入选头中尾三个位置的元素，选择中间值作为基准元素，或随机选择一个元素作为基准元素。

最好使用顺序存储，这样找到数轴元素与遍历时比较简单。

快速排序算法是不稳定的。

快速排序特性

• 快速排序不产生有序子序列。
• 枢轴元素到达的位置是不确定的，但是每次都会到其最终的位置上。第$n$趟有$n$个元素到最终位置上。
• 求快速排序趟数就是找到符合这种性质的元素个数。
• 快速排序在内部排序中的表现最好。
• 对于基本有序或倒序的序列，快速排序速度最慢。
• 对于每次的数轴元素能尽量将表分为长度相同的子表，快速排序速度最快。
• 排序的递归次数与初始序列和选择的枢轴变量有关，与分区处理顺序无关。

选择排序

选择排序特性

• 分为已排序和未排序序列。选择排序就是每一趟在待排序元素中选取关键字最小或最大的元素加入有序子序列。
• 选择排序算法的比较次数始终为$n(n-1)/2$，与序列状态无关。

选择排序与其他排序的区别：

• 选择排序也需要交换，但是与交换排序的不断交换不同的是选择排序时选择出一个最后进行交换，一趟只交换一次。
• 选择排序也需要插入，且也分为已排序和未排序序列，但是插入排序不需要选择，且元素移动方式是插入而不是交换。

简单选择排序

简单选择排序过程

即每一趟在待排序元素中选取关键字最小的元素加入有序序列。交换发生在选出最值后，在每趟的尾部。经过$n-1$趟就可以完成。

简单选择排序性能

空间复杂度为$O(1)$。

时间复杂度为$O(n^2)$。

简单选择排序是不稳定的。因为选择后会进行交换，影响顺序。

简单选择排序也可以适用于链表。

直接插入排序与简单选择排序

插入排序和选择排序都是分为未排序和已排序两个部分，那么其中有什么区别？

如$18$、$23$、$19$、$9$、$23*$、$15$进行排序。

18 23 19 9 23* 15

插入排序：

18 23 19 9 23* 15
18 19 23 9 23* 15
9 18 19 23 23* 15
9 18 19 23 23* 15
9 15 18 19 23 23*

选择排序：

9 23 19 18 23* 15
9 15 19 18 23* 23
9 15 18 19 23* 23
9 15 18 19 23* 23
9 15 18 19 23* 23
9 15 18 19 23* 23

堆排序

堆的定义

若$n$个关键字序列$L$满足下面某一条性质，则就是堆：

1. 若满足$L(i)\geqslant L(2i)$且$L(i)\geqslant L(2i+1),(1\leqslant i\leqslant\dfrac{n}{2})$则是大根堆或大顶堆。
2. 若满足$L(i)\leqslant L(2i)$且$L(i)\leqslant L(2i+1),(1\leqslant i\leqslant\dfrac{n}{2})$则是小根堆或小顶堆。

所以堆就是用顺序存储的完全二叉树。

堆的叶子结点范围是$\lfloor\log_2n\rfloor+1\sim n$。

堆的建立

其实堆就是层序存储的完全二叉树。其中：

• $i\leqslant\lfloor\dfrac{n}{2}\rfloor$的结点都是非终端结点。
• $i$的左孩子是$2i$。
• $i$的右孩子是$2i+1$。
• $i$的父结点是$\lfloor\dfrac{n}{2}\rfloor$。

所以建立根堆过程是：

1. 按照关键字序列依次添加关键字到二叉树，按照层次遍历顺序添加。
2. 初始化成功后再从下往上、从左至右按逆层次遍历顺序不断调整位置。
3. 如果是大根堆则大元素往上，且当前结点与更大的孩子结点互换；如果是小根堆则小元素往上，且当前结点与更小的孩子结点互换。
4. 递归往上时父子结点不断交换位置。
5. 如果元素互换破坏了调整好的下一级的堆，则使用同样的方法对下一层递归调整。

如用堆排序对$(15,9,7,8,20,-1,7,4)$建立小根堆堆。首先将这组数据按层序初始化为无序堆，然后从最后向前开始调整：

堆排序过程

由于选择排序是在每一趟都选择最大或最小的值进行排序，所以堆排序中就通过堆这个存储结构来完成对最值的选取——直接选择堆顶元素。

堆排序即每次将堆顶元素与堆底元素（堆最底层最右元素）进行交换，表示这个部分已经排序完成了不需要进行调整，第$i$趟表示倒数$i$个元素已经有序，所以无序的元素就是堆前面的元素。

1. 每一趟将堆顶元素加入子序列（堆顶元素与待排序序列中的最后一个元素交换）。此时后面的这个元素就排序好了。最右下的元素作为堆顶元素。
2. 此时待排序序列已经不是堆了（堆顶不能保证是最小或最大的元素），需要将其再次调整为堆（小元素或大元素不断下坠）。
3. 重复步骤一二。
4. 直到$n-1$趟处理后得到有序序列。基于大根堆的堆排序会得到递增序列，而基于小根堆的堆排序会得到递减序列。

调整堆从右边即序列末尾开始。

注意：题目如果说是给出序列，然后调整为堆，则证明他这个堆已经建立好了，只需要调整顺序，如果说的是依次插入，则要一边插入一边调整堆。

堆排序性能

堆排序的存储就是它本身，不需要额外的存储空间，要么只需要一个用于交换或临时存放元素的辅助空间。所以空间复杂度为$O(1)$。

若树高为$h$，某结点在第$i$层，则将这个结点向下调整最多只需要下坠$h-i$层，关键字对比次数不超过$2(h-i)$次。

第$i$层最多$2^{i-1}$个结点，而只有第$1\cdots(h-1)$层的结点才可能需要下坠调整。所以调整时关键字对比次数不超过$\sum_{i=h-1}^12^{i-1}2(h-i)=\sum_{j=1}^{h-1}2^{h-j}j\leqslant2n\sum_{j=1}^{h-1}\dfrac{j}{2^j}\leqslant4n$。

所以建堆过程中，关键字对比次数不超过$4n$，建堆的时间复杂度为$O(n)$。

堆排序中处理时根结点最多下坠$h-1$层，而每下坠一层，最多对比关键字两次，所以每一趟排序的时间复杂度不超过$O(h)=O(\log_2n)$，一共$n-1$趟，所以时间复杂度为$O(n\log_2n)$。所以总的时间复杂度也是$O(n\log_2n)$。

堆排序是不稳定的。

堆排序适合关键字较多的情况。创如，在$1$亿个数中选出前$100$个最大值，首先使用一个大小为$100$的数组，读入前$100$个数，建立小顶堆，而后依次读入余下的教，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中$100$个数即为所求。

堆的插入

新元素放到表尾（即最右下角元素），并与其$\lfloor\dfrac{i}{2}\rfloor$的父结点进行对比，若新元素比父元素更大（大根堆）或更小（小根堆），则二者互换，并保持上升，直到无法上升为止。时间复杂度为树高$O(\log_2n)$。

堆的删除

被删除的元素用堆底元素（即最右下角元素）代替，然后让这个元素不断下坠，直到无法下坠为止。时间复杂度为树高$O(\log_2n)$。

堆排序特性

• 适合大量数据进行排序。
• 在含有$n$个关键字的小根堆中，关键字最大的记录存储范围为$\lfloor\dfrac{n}{2}\rfloor+1\sim n$。这是小根堆，关键字最大的记录一定存储在这个堆所对应的完全二叉树的叶子结点中；又因为二叉树中的最后一个非叶子结点存储在$\lfloor\dfrac{n}{2}\rfloor$中，所以得到范围。

归并排序

归并是指把两个（二路归并）或多个（多路归并）已经有序的序列合并为一个。

该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

在较大数据进行排序时为了加快速度使用归并排序，用空间换时间。

二路归并排序

二路归并排序比较常用，且基本上用于内部排序，多路排序多用于外部排序。

二路归并排序过程

1. 把长度为$n$的输入序列分成两个长度为$\dfrac{n}{2}$的子序列。
2. 对这两个子序列分别采用归并排序。
3. 将两个排序好的子序列合并成一个最终的排序序列。

归并排序趟数为$\lceil\log_2n\rceil$。

二路归并排序性能

二路归并排序是一棵倒立的二叉树。

空间复杂度主要来自辅助数组，所以为$O(n)$，而递归调用的调用栈的空间复杂度为$O(\log_2n)$，总的空间复杂度就是为$O(n)$，无论平均还是最坏，所以这个算法在内部排序算法中空间消耗最大。

$n$个元素二路归并排序，归并一共要$\log_2n$趟，每次归并时间复杂度为$O(n)$，则算法时间复杂度为O(n\log_2n)

归并排序是稳定的。

分配排序

分配排序过程无须比较关键字，而是通过用额外的空间来“分配”和“收集”来实现排序，它们的时间复杂度可达到线性阶$O(n)$。简言之就是：用空间换时间，所以性能与基于比较的排序才有数量级的提高。

基数排序

基数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

• 只能对整数进行排序。
• 元素的移动次数与关键字的初始排列次序无关。

基数的定义

假设长度为$n$的线性表中每个结点$a_j$的关键字由$d$元组$(k_j^{d-1},k_j^{d-2},\cdots,k_j^1,k_j^0)$组成，其中$0\geqslant k_j^i\geqslant r-1,(0\geqslant i\geqslant d-1)$，其中$r$就是基数。

基数排序过程

有最高位优先$MSD$和最低位优先$LSD$两种方法。

若是要得到递减序列：

1. 初始化：设置$r$个空辅助队列$Q_{r-1},Q_{r-2},\cdots,Q_0$。
2. 按照每个关键字位权重递增的次序（个、十、百），对$d$个关键字位分别做分配和收集。
3. 分配就是顺序扫描各个元素，若当前处理的关键字位为$x$，就将元素插入$Q_x$队尾。
4. 收集就是把$Q_{r-1},Q_{r-2},\cdots,Q_0$各个队列的结点依次出队并链接在一起。

基数排序性能

基数排序基本上使用链式存储而不是一般的顺序存储。

需要$r$个辅助队列，所以空间复杂度为$O(r)$。

一趟分配$O(n)$，一趟收集$O(r)$，一共有$d$趟分配收集，所以总的时间复杂度为$O(d(n+r))$。与序列初始状态无关。

基数排序是稳定的。

基数排序的应用

对于一般的整数排序是可以按位排序的，也可以处理一些实际问题，如根据人的年龄排序，需要从年月日三个维度分别设置年份的队列、月份的队列（$1$到$12$）、日的队列（$1$到$31$）。

所以基数排序擅长解决的问题：

1. 数据元素的关键字可以方便地拆分为$d$组，且$d$较小。
2. 每组关键字的取值范围不大，即$r$较小。
3. 数据元素个数$n$较大。

计数排序

作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序过程

1. 找出待排序的数组中最大和最小的元素。
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项。
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）。
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

当输入的元素是$n$个属于$[0,k]$的整数时，时间复杂度是$O(n+k)$，空间复杂度也是$O(n+k)$，其排序速度快于任何比较排序算法。

当$k$不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

计数排序是稳定的。

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

桶排序过程

1. 设置一个定量的数组当作空桶。
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去。
3. 对每个不是空的桶进行排序。
4. 从不是空的桶里把排好序的数据拼接起来。

桶排序性能

桶排序最好情况下使用线性时间$O(n)$，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为$O(n)$。桶排序的平均时间复杂度为线性的$O(n+C)$，其中$C=n\times(\log n-\log m)$，其中$m$代表桶划分的数量。

很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

桶排序是稳定的。

内部排序

指在排序期间元素全部存放在内存中的排序。除了分配排序，其他的内部排序往往要经过比较和移动。

算法种类	最好时间复杂度	平均时间复杂度	最好时间复杂度	空间复杂度	是否稳定	趟数
直接插入排序	O(n)	O(n^2)	O(n^2)	O(1)	是	n-1
希尔排序	?	?	?	O(1)	否	s
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	否	n-1
快速排序	O(n\log_2n)	O(n\log_2n)	O(n^2)	O(\log_2n)	否	初始序列
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	是	初始序列
堆排序	O(n\log_2n)	O(n\log_2n)	O(n\log_2n)	O(1)	否	初始序列
二路归并排序	O(n\log_2n)	O(n\log_2n)	O(n\log_2n)	O(n)	是	\log_2n
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	是	r

• 每趟排序结束都至少能够确定一个元素最终位置的方法：选择、交换。（插入和归并则不行）

外部排序

指在排序期间元素无法全部同时存放在内存中，必须在排序过程中根据要求不断地在内、外存之间移动的排序。

外部排序的原理

外部排序过程

磁盘的读写是以块为单位，数据读入内存后才能被修改，修改完成后还需要写回磁盘。

外部排序就是针对数据元素太多，无法一次性全部读入内存进行排序而进行处理的在外部磁盘进行的排序处理方式。

使用归并排序的方式，最少只用在内存分配三块大小的缓冲区（两个输入缓冲一个输出缓冲）即可堆任意一个大文件进行排序。然后对缓冲区里的数据进行内部排序。

外部排序过程：

1. 生成初始归并段（大小为输入缓冲区的总大小），需要读写并进行内部排序。
2. 重复读写，进行内部归并排序。填满输出缓冲就可以输出。输入缓冲空就可以输入新数据。

外部排序时间开销=读写外存时间（最大的时间开销）+内部排序所需时间+内部归并所需时间。

外部排序的优化方法

优化方法就是使用更多路的多路归并，减少归并趟数。

$k$路平衡归并：最多只能有$k$个段归并为一个，需要一个输出缓冲区和$k$个输入缓冲区；每一趟归并中，若有$m$个归并段参与归并，则经过这一趟处理得到$\lceil\dfrac{m}{k}\rceil$个新的归并段。

对$r$个初始归并段，使用$k$路归并，则归并树可以使用$k$叉树表示，若树高为$h$，则归并趟数最小为$h=\lceil\log_kr\rceil+1$。

但是多路归并会带来负面影响：

1. $k$路归并时，需要开辟$k$个输入缓冲区，内存开销增加。
2. 每挑选一个关键字需要对比关键字$(k-1)$次，内部归并时间增加。

同时，若能增加初始归并段的长度$k$，也可以减少初始归并段数量$r$从而进行优化。

败者树

用于通过过去归并的经历减少归并次数。败者树可以看作一棵多了一个单个的根的完全二叉树。$k$个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的失败者，而让胜者往上继续比较，一直到根结点。

如要用败者树排序$27,12,1,17,2,9,11,4$，格式：元素值$(归并段索引值)$：

                   1(3)
                    |
                   2(5)
                    |
         ----------------------
         |                    |
        12(2)                4(8)
         |                    |
    ------------         ------------
    |          |         |          |
  27(1)      17(4)      9(6)      11(7)
    |          |         |          |
 ------     ------     ------     ------
 |    |     |    |     |    |     |    |
27    12    1    17    2    9    11    4

传统方法从$k$个归并段选出一个最大或最小元素需要对比关键字$k-1$次，而使用$k$路归并的败者树只需要对比关键字$\lceil\log_2k\rceil$次（败者树层数，不包括成功结点）。

构建败者树还是需要$n-1$次对比。

置换选择排序

如果内存工作区只能容纳$l$个记录，则初始归并段也只能包含$l$条记录，若文件共有$n$条记录，则初始归并段的数量为$r=\lceil n/l\rceil$。

用于构建更长的初始归并段，从而减少归并次数。

假设初始始待排文件为$FI$，初始归并段输出文件为$FO$，内存工作区为$WA$，$FO$和$WA$的初始状态为空，$WA$可容纳$w$个记录。置换选择算法的步骤如下：

1. 从$FI$输入$w$记录到工作区$WA$。
2. 从$WA$中选出其中关键字取最小值的记录，记为$MINIMAX$记录。
3. 将$MINIMAX$记录输出到$FO$中去。
4. 若$FI$不空，则从$FI$输入下一个记录到$WA$中。
5. 从$WA$中所有关键字比$MINIMAX$记录的关键字大的记录中选出最小关键字记录，作为新的$MINIMAX$记录。
6. 重复步骤三到五，如果新输入到$FI$的关键字小于$MINIMAX$的值，则驻留在$WA$中，直至在$WA$中填满选不出新的$MINIMAX$记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到$FO$中去。准备输出新的归并段。
7. 重复步骤二到六，直至$WA$为空。由此得到全部初始归并段。

此时输出的初始归并段可以超过$WA$，且初始归并段长度是不一定相等的。

如$FI$：$4,6,9,7,13,11,14,22,30,2,3,19,20,17,1,23,5,36,12,18,21,39$，$WA$长度为$3$，$FO$为$4,6,7,9,11,13,14,16,22,30$、$2,3,10,17,19,20,23,36$、$1,5,12,18,21,39$。

^表示中断当前归并段，下一个$FI$开启新的归并段；√表示该$WA$值超过$MINIMAX$值，不能输出到当前$FO$归并段中，只能等待输出到下一个归并段。

FI	4	6	9	7	13	11	14	22	30	2	3	19		20
WA1	4	4	4	7	7	11	11	22	22	22	3√	3√	3	3
WA2		6	6	6	13	13	13	13	30	30	30	19√	19	19
WA3			9	9	9	9	14	14	14	2√	2√	2√	2	20
MINIMAX			4	6	7	9	11	13	14	22	30	30	2	3
FO			4	6	7	9	11	13	14	22	30	^	2	3

FI	17	1	23	5	36	12		18	21	39
WA1	17	1√	1√	1√	1√	1√	1	18	18	18
WA2	19	19	23	23	36	12√	12	12	12	39	39	39
WA3	20	20	20	5√	5√	5√	5	5	21	21	21
MINIMAX	17	19	20	23	36	36	1	5	12	18	21	39
FO	17	19	20	23	36	^	1	5	12	18	21	39	^

最佳归并树

因为现实中的每个归并段的长度不同，所以归并的次序比较重要。

最佳归并树的衡量

每个初始归并段可以看作一个叶子结点，归并树的长度作为结点权值，则归并树的带权路径长度$WPL$等于读写磁盘的次数。从而归并过程中的磁盘$I/O$次数=归并树的$WPL\times2$。

最佳归并树的构造

所以就需要一棵类似哈夫曼树来成为最佳的归并树，不断选择最小的$k$段进行归并。

添加虚段

对于$k$叉归并来说，若初始归并段的数量无法构成严格的$k$叉归并树，则需要补充几个长度为$0$的虚拟段从而能保证严格$k$叉归并，再进行$k$叉哈夫曼树的构造。

那么添加多少虚段呢？

$k$叉的最佳归并树一定是一棵严格的$k$叉树，即树中只包含度为$k$和$0$的结点。

设度为$k$的结点有$n_k$个，度为$0$的结点有$n_0$个，归并树的总结点树为$n$，则初始归并段数量+虚段数量=$n_0$。

所以$n=n_0+n_k$，$kn_k=n-1$，所以$n_0=(k-1)n_k+1$，所以$n_k=\dfrac{(n_0-1)}{(k-1)}$一定是可以整除的。如果不整除就要添加虚段。