目录
- 基本概念
- 插入排序
- 直接插入排序
- 折半插入排序
- 希尔排序
- 交换排序
- 冒泡排序
- 快速排序
- 选择排序
- 简单选择排序
- 堆排序
- 归并排序
- 基数排序
- 外部排序
- 基本概念
- 败者树
- 置换-选择排序
- 最佳归并树
0 基本概念 定义
重新排列表中的元素，使得表中的元素按关键字有序的过程。
排序的稳定性若待排序表中有两个元素
R
i
R_i
Ri和
R
j
R_j
Rj，其对应的关键字相同即
k
e
y
i
=
k
e
y
j
key_i=key_j
keyi=keyj，且在排序前
R
i
R_i
Ri在
R
j
R_j
Rj的前面，若使用某一排序算法排序后，
R
i
R_i
Ri仍然在
R
j
R_j
Rj前，则称这个排序算法是稳定的，否则称其为不稳定的。
算法具有稳定性通常并不是衡量算法优劣的标准，它主要是对算法的性质进行描述。
如算法不允许关键字重复，那么就无须考虑算法的稳定性。
在排序过程中，根据元素是否全部在内存中，分为内部排序和外部排序：
- 内部排序，是指在排序期间元素全部放在内存中的排序，如插入排序、交换排序、选择排序、归并排序和基数排序等；（时间复杂度一般取决于比较和移动的次数）
- 外部排序，是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序，如多路归并排序。
1 插入排序
插入排序的基本思想是每次将一个待排序的元素按照其关键字大小插入到已排好序的子序列，直到全部全速插入完成。
1.1直接插入排序操作：
- 查找出插入位置k；
- k之后i之前的元素后挪（会覆盖掉q[i],因此需要提前存）；
- 插入到那个空位。
//对数组q，从q[l]到q[r]进行排序
void insert_sort(int q[], int l, int r)
{
for (int i = l + 1; i <= r; i++)//从第2个数开始遍历，第1个数时无需考虑顺序
if (q[i] < q[i - 1])//当前元素比前一个小
{
int e = q[i], j;//用e记录下当前值（因为后续操作会覆盖掉当前元素值）
for (j = i - 1; q[j] > e; j--)//前面的元素依次向后挪，直至前一个元素小于等于e（查找出插入位置）
q[j + 1] = q[j];
q[j + 1] = e;//将e插入到那个空位
}
}
空间效率：使用常数个辅助单元，空间复杂度为O(1);
时间效率：
- 在n个元素的排序过程中，向有序子表中逐个插入元素n-1趟，每趟都包含比较关键字和移动元素，而比较次数取决于待排序表的初始状态；
- 最好情况：数组已经有序，每次只需插入一个元素，只需比较一次而不需要移动，此时的时间复杂度为O(n);
- 最坏情况：数组逆序，总的比较次数达到最大 1 + 2 + . . . + ( n − 1 ) 1+2+...+(n-1) 1+2+...+(n−1)，总的移动次数 2 + 3 + . . . + n 2+3+...+n 2+3+...+n,时间复杂度是O(n^2)；
- 平均情况：数组中元素的位置是随机的，通过计算期望，得其时间复杂度也是O(n^2)；
稳定性：直接插入排序从后向前比较再移动，不会出现相同值的元素相对位置发生变化的情况，是稳定的；
适用性：适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。（大部分排序算法仅适用于顺序存储的线性表）
先折半查找出元素的待插入位置，然后统一移动插入位置之后的所有元素。
void insert(int q[], int l, int r)
{
int low, high, mid;
for (int i = l + 1; i <= r; i++)
{
int e = q[i];
low = l;
high = i - 1;
while (low <= high)//循环到最后会出现low=high，再进行一轮即可跳出循环
{
mid = (low + high) / 2;//二分
if (q[mid] > e)//查找左半边
high = mid - 1;
else//右半边
low = mid + 1;
}
for (int j = i - 1; j >= high + 1; j--)
q[j + 1] = q[j];
q[high + 1] = e;
}
}
折半插入排序仅减少了比较元素的次数，约为O(nlogn);移动次数未改变，因此总的时间复杂度依旧是O(n^2).
折半插入排序也是一种稳定的算法。
希尔排序又称缩小增量排序。
主要思想：先追求表中元素部分有序，再逐渐逼近全局有序。
先将待排序表分割成若干形如L[i, i+d, i+2d, … , i+kd]的特殊 “子表”，对各个子表分别进行直接插入排序。缩小增量d，直到d=1为止。
const int N = 1e5 + 10;
int q[N];
void ShellSort(int q[], int n)
{
int d, i, j; //初始增量d
for (d = n / 2; d >= 1; d /= 2)
for (i = d + 1; i <= n; i++)
if (q[i] < q[i - d])
{
q[0] = q[i];
for (j = i - d; j > 0 && q[0] < q[j]; j -= d)
q[j + d] = q[j];
q[j + d] = q[0];
}
}
注意：
- 空间复杂度：O(1)；
- 时间复杂度：和增量d1,d2,d3…的选择有关，目前无法用数学手段证明确切的时间复杂度；
- 最坏时间复杂度：O(n^2);
- 当n在某个范围内，时间复杂度可达 O ( n 1.3 ) O(n^{1.3}) O(n1.3);
- 希尔排序是不稳定的；
- 希尔排序仅适用于顺序表，不适用于链表。
2 交换排序
交换，是指根据 序列中两个元素关键字的比较结果 来对换这两个记录在序列中的位置。基于交换的排序算法主要有 冒泡排序 和 快速排序。
2.1 冒泡排序基本思想：
从后往前两两比较相邻元素的值，若为逆序，则交换它们，直至序列比较完。
void bubble_sort(int q[N], int l, int r)
{
for (int i = l; i < r; i++)//i从最左边开始遍历到倒数第二个元素
for (int j = r; j > i; j--)//j从最左边遍历到i之前一个位置
if (q[j] < q[j - 1]) swap(q[j], q[j - 1]);//两两比较，小者前移
}
优化一下下：
如果某趟冒泡过程中，没有发生交换，则说明已经有序，无需继续。
void bubble_sort(int q[N], int l, int r)
{
for (int i = l; i < r; i++)
{
bool flag = false;//表示本趟冒泡没有发生交换
for (int j = r; j > i; j--)
if (q[j] < q[j - 1])
{
swap(q[j], q[j - 1]);
flag = true;
}
if(!flag) return;
}
}
空间效率：仅使用了常数个辅助单元，因此空间复杂度为O(1)；
最好时间复杂度：对于优化后的冒泡排序，如果表已经有序，则进行一趟冒泡就会结束，此时为最好时间复杂度O(n)；
最坏时间复杂度：第一趟比较n-1次，第二趟比较n-2次，…，第n-1趟比较1次，并且每次比较后都需要移动3次(t=a,a=b,b=t)来完成交换，此时为最坏时间复杂度O(n^2)；
平均时间复杂度同最坏时间复杂度；
稳定性：前一个元素和当前元素相等，无须进行交换，因此是稳定的。
2.2 快速排序
基本思想——分治：
- 在待排序表L[l…r]中任取一个元素q[x]作为分界点(可以是左端点、右端点、中点、随机点)；
- 调整区间：左边区间所有的数都<=q[x]，右边区间所有的数都>=q[x]；
- 递归处理左右两段。
调整区间的一个好办法：
- 左端指针i向右移动，直到指向的元素>=x;右端指针j向左移动，直到指向的元素<=x;（进行完一次就会使得q[l…i-1] < x, q[i] >= x, q[j-1…r] > x, q[j] <= x ）
- 交换两个元素的位置；（就会使得q[l…i] <= x, q[j…r] >= x ）
- 交换后，两个指针分别向中间移动一位；
- 继续移动，直到相遇。
一趟快速排序是一个交替搜索和交换的过程。
机试用模板：
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int x = q[l + r >> 1], i = l - 1, j = r + 1;
while (i < j)
{
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
严蔚敏教材：
void quick_sort(int A[], int low, int high)
{
if(low < high)//跳出循环的条件
{
int pivotpos = Partition(A, low, high);//划分
quick_sort(A, low, pivotpos-1);
quick_sort(A, pivotpos, high);
}
}
int Partition(int A[], int low, int high)
{
int pivot = A[low];
while(low < high)
{
while(low < high && A[high] >= pivot) high--;
A[low] = A[high];
while(low < high && A[low] <= pivot) low++;
A[high] = A[low];
}
A[low] = pivot;
return low;
}
空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用栈的最大深度一致。最好情况下为O(logn)，最坏情况下因为要进行n-1次递归调用，所以栈的深度为O(n)，平均情况下为O(logn)。
时间效率：快速排序的运行时间与划分是否对称有关，快排的最坏情况发生在两个区域分别包含n-1个元素和1个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于排序表基本有序或基本无序时，就得到最坏情况下的时间复杂度O(n^2)；
在最理想的情况下，每次均衡划分，得到两个子问题的大小不大于n/2，此时，时间复杂度为O(nlogn)；快排的平均时间复杂度和最好时间复杂度接近，是所有内部排序算法中平均性能最优的排序算法。
快排不稳定，如3, 2, 2 取2作为分界元素。
3 选择排序 3.1 简单选择排序
主要思想：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。
第一趟，[1,n]，将最小的元素放在第一个位置；
第二趟，[2,n]，将第二小的元素放在第二个位置；
…
第n-1趟，[n-1,n]，将倒数第n-1小的元素放在第n-1个位置；
最后剩余一个元素——最大的元素。
void select_sort(int q[], int l, int r)
{
for (int i = l; i < r; i++)
{
int mmin = i;
for (int j = i + 1; j <= r; j++)
if (q[j] < q[mmin]) mmin = j;
if (mmin != i) swap(q[i], q[mmin]);
}
}
3.2 堆排序
void HeapAdjust(int A[], int k, int len) //对k为根的子树进行调整
{
A[0] = A[k]; //存放根节点，防止被覆盖
for (int i = 2 * k; i <= len; i *= 2) //从左孩子开始
{
if (i < len && A[i] < A[i + 1]) //左孩子在堆中，左孩子小于右孩子
i++; // i指向右孩子(大的那个)
if (A[0] >= A[i]) //根节点最大
break;
else
{
A[k] = A[i]; // A[i]最大
k = i; //小元素下坠
}
}
A[k] = A[0];
}
void BuildMaxHeap(int A[], int len) //建立最大堆
{
for (int i = len / 2; i > 0; i--) //对所有的非终端节点一一调整
HeapAdjust(A, i, len);
}
void HeapSort(int A[], int len)
{
BuildMaxHeap(A, len);
for (int i = len; i > 1; i--)
{
swap(A[i], A[1]);
HeapAdjust(A, 1, i - 1);
}
}
4 归并排序
归并 是 将两个或两个以上的有序表组合成一个新的有序表。
方法：
- 分解：将原问题分解为若干规模较小的子问题；
- 解决：递归的求解子问题；
- 合并：将子问题的解合并为原问题的解。
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = (l + r) >> 1;
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
while (i <= mid) tmp[k++] = q[i++];
while (j <= r) tmp[k++] = q[j++];
for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}
空间效率：辅助空间为n，空间复杂度为O(n);
时间效率：可以通过递归树求解，归并排序的时间复杂度为O(nlogn);
稳定性：不会改变相同关键字元素的顺序，稳定。
设有表长为n的线性表中每个结点
a
j
a_j
aj的关键字由d元组
(
k
j
d
−
1
,
k
j
d
−
2
,
k
j
d
−
3
,
.
.
.
,
k
j
1
,
k
j
0
)
(k_j^{d-1},k_j^{d-2},k_j^{d-3},...,k_j^1,k_j^0)
(kjd−1,kjd−2,kjd−3,...,kj1,kj0)组成，其中，
0
<
=
k
j
i
<
=
r
−
1
(
0
<
=
j
<
n
,
0
<
=
i
<
=
d
−
1
)
0<=k_j^i<=r-1(0<=j
基数排序得到递减序列的过程：
- 初始化：设置r个空队列 Q r − 1 , Q r − 2 , . . . , Q 1 . Q 0 Q_r-1,Q_r-2,...,Q_1.Q_0 Qr−1,Qr−2,...,Q1.Q0;
- 按照各个关键字位 权重递增的次序(个、十、百)，对d个关键字位分别做“分配”和“收集”。
- 分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入 Q x Q_x Qx的队尾；
- 收集：把 Q r − 1 , Q r − 2 , . . . , Q 1 . Q 0 Q_r-1,Q_r-2,...,Q_1.Q_0 Qr−1,Qr−2,...,Q1.Q0各个队列中的结点依次出队并链接。
算法效率：
空间复杂度：需要r个辅助队列，空间复杂度是O®;
时间复杂度：一趟分配O(n)，一趟收集O®，总共d趟分配和收集，共O(d(n+r));
稳定性：稳定。
应用：
年龄排序（按照年月日排序）；
擅长解决的问题：
- 数据元素的关键字可以方便地拆分为d组，且d较小；
- 每组关键字的取值范围不大，即r较小；
- 数据元素个数n较大。
- 操作系统以“块”为单位对磁盘存储空间进行管理；
- 磁盘的读写以“块”为单位；
- 数据读入内存之后才能被修改；
- 修改完了还要写回磁盘。
- 数据元素太多，无法一次全部读入内存进行排序；
- 使用“归并排序”的方法，最少只需在内存中分配3块大小的缓冲区即可对任意一个大文件进行排序。
- 构造初始归并段；（设共16块，则需要16次读，16次写）
- 第一趟归并；
- 把8个有序子序列（初始归并段）两辆归并，得到4个归并段；
- 输出缓冲区满了就立即写回外存；
- 某一块缓冲区空了就要立即用该归并段的下一块补上；
- 归并为一个更长的有序序列。
- 处理其他归并段。
- 第二趟归并；（得到2个归并段）
- 第三趟归并。（得到有序文件）
外部排序时间开销=读写外存的时间(很大比例)+内部排序的时间(初始归并段)+内部归并的时间
读写外存的时间：读写磁盘次数=文件总块数 * 2 + 文件总块数 * 2 * 归并次数
- 增加输入缓冲区个数
采用多路归并可以减少归并趟数，从而减少磁盘的读写次数。 - 增加初始归并段的长度
减少初始归并段的数量r，从而减少磁盘的读写次数。
对r个初始归并段，做k路归并，则归并树可以用k叉树表示
若树高为h，则归并趟数=h-1=[
l
o
g
k
r
log_kr
logkr]
多路归并的负面影响：
- k路归并时，需要开辟k个缓冲区，内存开销增加；
- 每挑选一个关键字需要比较次数(k-1)次，内部归并所需时间增加。
败者树可视为一棵完全二叉树（多了个头头）。
k个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的失败者，而让胜者继续进行比较，一直到根结点。
对于k路归并，第一次构造败者树需要对比关键字k-1次；
有了败者树，选出最小元素，只需对比关键字
l
o
g
2
k
log_2k
log2k次。
设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录。置换选择算法的步骤如下：
- 从FI输入w个记录到工作区WA；
- 从WA中选出其中关键字取最小值的记录，记为MINMAX记录；
- 将MINMAX记录输出到FO中；
- 若FI不空，则从FI输入下一个记录到WA中；
- 从WA中所有关键字比MINMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINMAX记录；
- 重复3)~5)，直至在WA中选不出新的MINMAX记录为止，由此得到一个初始归并段，输出一个归并段的记录标志到FO中；
- 重复2)~6)，直至WA为空。由此得到全部初始归并段。
归并树的性质：归并过程中的磁盘读写次数 = 归并树的WPL * 2
要让磁盘读写次数最少，就要使归并树的WPL最小————哈夫曼树！
注意：对于k叉归并，若初始归并段的数量无法构成严格的k叉归并树，则需要补充几个长度为0的虚段，再进行k叉哈夫曼树的构造。
需要补充虚段的个数？
- 若 (初始归并段数量-1)%(k-1)=0，说明刚好可以构成严格k叉树，此时不需要添加虚段；
- 若 (初始归并段数量-1)%(k-1)=u≠0，则需要补充(k-1)-u个虚段。
