排序

排序¶

排序的基本概念¶

插入排序¶

折半插入排序时间复杂度依旧为o(n^2^)，因为还要进行移动。

希尔排序¶

对于希尔排序明明是直接插入排序的变种，但是却是不稳定这一问题，我的理解如下：因为希尔排序使用增量d，所以关键值相同的两个数可能分到了不同的组里，就可能会发生不稳定的问题。

交换排序¶

冒泡排序¶

快速排序¶

选择排序¶

简单选择排序¶

堆排序¶

在小根堆中，关键字最大的元素一定存储在该堆所对应的完全二叉树的叶结点中（最底层或次底层）。又因为二叉树中的最后一个非叶结点存储在floor(n / 2)，那么叶结点的范围就是floor(n / 2) + 1 ~ n

下标从1开始

建堆默认时间复杂度为o(n)是因为使用了自底向上扫描，让结点不断“下坠”，让数量多的结点尽快沉底，最后对每层最多需要的”下坠“次数进行求和。

自顶向下扫描则是让结点不断上升，但是这样会导致数量多的结点上升次数多，导致求和结果变大，时间复杂度上升为o(nlogn)

无论最好最坏情况，堆排序的时间复杂度均为o(nlogn)

归并排序、基数排序和计数排序¶

归并排序¶

基数排序¶

计数排序¶

前缀和

各种内部排序算法的比较及应用¶

各排序的时间复杂度：
o(n^2^)
- 简单选择排序：无论最好最坏都是o(n^2^)，与序列初始状态无关
- 直接插入排序，冒泡排序最好情况都可以达到o(n)，最坏为o(n^2^)
o(nlogn)
- 快速排序：最坏情况下达到o(n^2^)
- 堆排序：建堆为o(n)，完成排序为o(nlogn)
- 归并排序：最好最坏均为o(nlogn)
各排序的空间复杂度：
简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需要借助常数个辅助空间
快速排序需要一个递归栈，平均大小为o(logn)，最坏情况为o(n)
二路归并为o(n)
稳定性：
稳定：插入排序、冒泡排序、归并排序、基数排序
不稳定：简单选择排序、快速排序、希尔排序、堆排序
适合采用的存储结构：
顺序存储：折半插入、希尔排序、快速排序、堆排序
顺序和链式都可以：直接插入排序、冒泡排序、简单选择排序、归并排序、基数排序

外部排序¶

败者树¶

用以解决k路归并每次要比较k - 1次慢速问题

置换-选择排序¶

用以解决初始段长度短，数量多问题

最佳归并树¶

如何理解n - 1,k - 1:

初始有n个结点，我们要最后合并成1个结点，也就意味着我们要消耗掉n - 1个结点，每次消耗是将k个结点合为1个结点，因此每次消耗可以看做是消耗了k - 1个结点。若(n - 1) % (k - 1) == 0，那么每次消耗是正好的，不需要补空结点；若余数（这里设为u）不为0，则我们要凑齐k - 1个，也就是再补k - 1 - u个。