一、内部排序

内部排序，指的是待排序记录存放在计算机随机存储器中进行排序的过程

1.插入排序

1.1直接插入排序

void InsertSort(int a[], int n) {for (int i = 1; i < n; i++) {//从第二个元素开始比较if (a[i] < a[i - 1]) {//如果此前有序数列的最后一个(当前元素前一个)比它大int temp = a[i];//哨兵int j= i - 1;while(temp < a[j]) {//从后往前依次比较，寻找插入位置a[j + 1] = a[j];//并同时将比他大的元素后移一位j--;}a[j + 1] = temp;//插入在第一个小于他的元素后面}}
}

1.2折半插入排序

个人感觉比较鸡肋。

void BInsertSort(int a[], int n) {for (int i = 1; i < n; i++) {int temp = a[i];//哨兵int l = 0, r = i - 1;//在此前有序的数列中进行二分查找while (l <= r) {int mid = l + r >> 1;if (a[mid] <= temp)l = mid + 1;//保证其为稳定排序else r = mid - 1;}for (int j = i - 1; j >= r + 1; --j) {//同样从后往前移动元素a[j + 1] = a[j];}a[r + 1] = temp;}
}

1.3希尔排序

1.简介

希尔排序（英语：Shell sort），也称为缩小增量排序法，是 插入排序 的一种改进版本。希尔排序以它的发明者希尔（英语：Donald Shell）命名。

2.工作原理

排序对不相邻的记录进行比较和移动：

1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
2. 对这些子序列进行插入排序；
3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1。

void ShellSort(int a[], int n) {for (int dk = n >> 1; dk >= 1; dk >>= 1) {for (int i = dk; i < n; i ++) {if (a[i] < a[i - dk]) {int temp = a[i];int j = i - dk;while(j >= 0 && temp < a[j]) {a[j + dk] = a[j];j -= dk;}a[j + dk] = temp;}}}
}

3.性质

3.1稳定性

希尔排序是一种不稳定的排序算法。

3.2时间复杂度

希尔排序的最优时间复杂度为 O(n)O(n)O(n)。

希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取（就是间距如何减小到 1）有关，比如「间距每次除以 3」的希尔排序的时间复杂度是 O(n3/2)O(n^{3/2})O(n3/2)。已知最好的最坏时间复杂度为 O(nlog⁡2n)O(n \log^2n)O(nlog2n)。

3.3空间复杂度

希尔排序的空间复杂度为 O(1)O(1)O(1)。

2.交换排序

2.1冒泡排序

void BubbleSort(int a[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}
}

2.2快速排序

1.简介

快速排序（英语：Quicksort），又称分区交换排序（英语：partition-exchange sort），简称快排，是一种被广泛运用的排序算法。

2.工作原理

快速排序的工作原理是通过 分治 的方式来将一个数组排序。

快速排序分为三个过程：

1. 将数列划分为两部分（要求保证相对大小关系）；
2. 递归到两个子序列中分别进行快速排序；
3. 不用合并，因为此时数列已经完全有序。

排序过程：

I、 设置两个指针，i指向序列的首部上一个，j指着尾部下一个，取数组中第一个元素为主元。
II、交换：
j从右至左，不断–，直到遇到第一个比key小的元素kj。
i从左至右，不断++，直到遇到第一个比key大的元素ki。

​ 若此时 i < j ,则交换对应元素的值。

III、按上述方式不断进行，直到i，j相遇，ki=key，第一趟排序完成接下来重复II步骤，递归进行。

void QuickSort(int a[], int l, int r) {//hoare版if (l >= r) return;int i = l - 1, j = r + 1, x = a[l];//取边界(a[l])如果数组有序则被卡成o(n*n),某些题不过可以改成a[l + r >> 1]while (i < j) {//划分为两个区域，左边的小于x，右边的大于xdo {i++;} while (a[i] < x);//找出左部分大于x数do {j--;} while (a[j] > x);//找出有部分小于x的数//任何时刻i左边的数小于等于x，j右边的数大于等于x，当i，j相遇时被分为左右两个部分。if (i < j) swap(a[i], a[j]);//交换}QuickSort(a, l, j), QuickSort(a, j + 1, r);
}

3.性质

3.1稳定性

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

3.2时间复杂度

在平均状况下，排序nnn个项目要O(nlog⁡n)O(n\log n)O(nlogn)次比较。在最坏状况下则需要O(n2)O(n^{2})O(n2)次比较，但这种状况并不常见

3.3空间复杂度

快速排序所使用的空间，依照使用的版本而定。

使用原地（in-place）分割的快速排序版本，在任何递归调用前，仅会使用固定的额外空间。

然而，如果需要嵌套递归调用，它需要在他们每一个存储一个固定数量的信息。因为最好和最坏情况下需要O(logn)O(log n)O(logn)次嵌套递归调用，因此需要O(logn)O(log n)O(logn)的空间。

参考博客

参考书籍：算法导论

3.选择排序

3.1简单选择排序

每次找出第 i 小的元素，然后将这个元素与数组第 i 个位置上的元素交换

void SelectSort(int a[], int n) {for (int i = 0; i < n; i++) {int pos = i;for (int j = i + 1; j < n; j++) {if (a[pos] > a[j])pos = j;}if (i != pos) {int temp = a[i];a[i] = a[pos];a[pos] = temp;}}
}

3.2堆排序

1.简介

堆排序是指利用 二叉堆 这种数据结构所设计的一种排序算法。堆排序的适用数据结构为数组。

2.工作原理

本质是建立在堆上的选择排序。

排序过程：

首先建立大顶堆，只有当其子节点被堆化时，才能将堆化过程应用于节点，所以堆化必须按照自下而上的顺序进行；

然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质；

之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；

以此类推，在第 n−1n-1n−1 次操作后，整个数组就完成了排序。

void heapify(int heap[], int size, int u) {//大顶堆//维护一个size能有效的处理左右儿子越界的情况、简化代码，体现heapify的本质//选出三个中最小的 int maxv = u;int ls = u << 1, rs = u << 1 | 1;//从1开始建堆if (ls <= size && heap[maxv] < heap[ls])maxv = ls;if (rs <= size && heap[maxv] < heap[rs])maxv = rs;//如果最大的哪个不根节点if (u != maxv) {swap(heap[u], heap[maxv]);//最大的节点与根节点交换heapify(heap, size, maxv);//交换后的子树需要调整}
}
void HeapSort(int heap[], int n) {//从一棵完整的二叉树开始，我们可以通过在堆的 所有非叶节点 上运行heapify函数来将其修改为大顶堆for (int i = n / 2; i > 0; i--)heapify(heap, n, i);//包括根节点（细节）for (int i = n; i > 1; i--) {//从最后一个开始，调整到根节点时已经有序，不包括根节点（细节）swap(heap[1], heap[i]);//第一个与最后一个元素交换//调整范围减小（细节）heapify(heap, i - 1, 1);}
}

3.性质

3.1稳定性

同选择排序一样，由于其中交换位置的操作，所以是不稳定的排序算法。

3.2时间复杂度

堆排序的最优时间复杂度、平均时间复杂度、最坏时间复杂度均为 O(nlog⁡n)O(n\log n)O(nlogn)。

3.3空间复杂度

由于可以在输入数组上建立堆，所以这是一个原地算法。

参考博客

4.归并排序

1.简介

归并排序（英语：merge sort）是一种采用了 分治 思想的排序算法。

2.工作原理

归并排序分为三个步骤：

1. 将数列划分为两部分；
2. 递归地分别对两个子序列进行归并排序；
3. 合并两个子序列。

不难发现，归并排序的前两步都很好实现，关键是如何合并两个子序列。注意到两个子序列在第二步中已经保证了都是有序的了，第三步中实际上是想要把两个 有序 的序列合并起来。

排序过程：

对于归并排序难在合并的过程，对于给定的两个有序数组a[1…n],b[1…m]

我们设置两个指针i，j分别指向a,b开始位置，并开始逐个比较取出其最小的放入辅助数组t

若某个指针取到数组最末尾i=n(j=m)则说明b(a)内所有有序元素均大于t中最大元素，直接接入其后即可。

int t[N];//辅组数组
void MergeSort(int a[], int l, int r) {if (l >= r) return;//递归的划分int mid = l + r >> 1;MergeSort(a, l, mid);MergeSort(a, mid + 1, r);int i = l, j = mid + 1;int k = 0;while (i <= mid && j <= r) {//从两个分组中选最小的哪个加入数组，当某个分组选完后停止if (a[i] <= a[j]) t[k++] = a[i++];else t[k++] = a[j++];}//将另一个分组的有序元素直接加入数组后面while (i <= mid) t[k++] = a[i++];while (j <= r) t[k++] = a[j++];//归位for (i = l, j = 0; i <= r; i++, j++) a[i] = t[j];
}

3.性质

3.1稳定性

归并排序是一种稳定的排序算法。

3.2时间复杂度

归并排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 O(nlog⁡n)O(n\log n)O(nlogn)。

3.3空间复杂度

归并排序的空间复杂度为 O(n)O(n)O(n)。

5.基数排序

1.简介

基数排序（英语：Radix sort）是一种非比较型的排序算法，最早用于解决卡片排序的问题。

2.工作原理

它的工作原理是将待排序的元素拆分为 kkk 个关键字（比较两个元素时，先比较第一关键字，如果相同再比较第二关键字……），然后先对第 kkk 关键字进行稳定排序，再对第 k−1k-1k−1 关键字进行稳定排序，再对第 k−2k-2k−2 关键字进行稳定排序……最后对第一关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。

通常而言，基数排序比基于比较的排序算法（比如快速排序）要快。但由于需要额外的内存空间，因此当内存空间稀缺时，原地置换算法（比如快速排序）或许是个更好的选择。

分配和收集策略

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0Ovt5L8C-1668563213055)(C:\Users\13645\AppData\Roaming\Typora\typora-user-images\image-20220428155115954.png)]

3.性质

3.1稳定性

基数排序是一种稳定的排序算法。

3.2时间复杂度

一趟分配O(n){O(n)}O(n),一趟收集O(r),{O(r)},O(r), 总共ddd趟分配和收集，时间复杂度O(d(n+r))O(d(n+r))O(d(n+r))。其中rrr为基数。

3.3空间复杂度

需要rrr个辅助队列，空间复杂度O(r)O(r)O(r)。

法正确性测试

#include
using namespace std;typedef long long ll;
const ll N = 1e6 + 5;
const ll INF = 0x7ffffffff;
int a[N];
void InsertSort(int a[], int n) {for (int i = 1; i < n; i++) {//从第二个元素开始比较if (a[i] < a[i - 1]) {//如果此前有序数列的最后一个(当前元素前一个)比它大int temp = a[i];//哨兵int j = i - 1;while (temp < a[j]) {//从后往前依次比较，寻找插入位置a[j + 1] = a[j];//并同时将比他大的元素后移一位j--;}a[j + 1] = temp;//插入在第一个小于他的元素后面}}
}
void BInsertSort(int a[], int n) {for (int i = 1; i < n; i++) {int temp = a[i];//哨兵int l = 0, r = i - 1;//在此前有序的数列中进行二分查找while (l <= r) {int mid = l + r >> 1;if (a[mid] <= temp)l = mid + 1;//稳定排序else r = mid - 1;}for (int j = i - 1; j >= r + 1; --j) {//同样从后往前移动元素a[j + 1] = a[j];}a[r + 1] = temp;}
}
void ShellSort(int a[], int n) {for (int dk = n >> 1; dk >= 1; dk >>= 1) {for (int i = dk; i < n; i ++) {if (a[i] < a[i - dk]) {int temp = a[i];int j = i - dk;while(j>=0&&temp < a[j]) {a[j + dk] = a[j];j -= dk;}a[j + dk] = temp;}}}
}
void BubbleSort(int a[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}
}
void QuickSort(int a[], int l, int r) {if (l >= r) return;int i = l - 1, j = r + 1, x = a[l + r >> 1];while (i < j) {do {i++;} while (a[i] < x);do {j--;} while (a[j] > x);if (i < j) swap(a[i], a[j]);}QuickSort(a, l, j), QuickSort(a, j + 1, r);
}
void SelectSort(int a[], int n) {for (int i = 0; i < n; i++) {int pos = i;for (int j = i + 1; j < n; j++) {if (a[pos] > a[j])pos = j;}if (i != pos) {int temp = a[i];a[i] = a[pos];a[pos] = temp;}}
}
int t[N];//辅组数组
void MergeSort(int a[], int l, int r) {if (l >= r) return;//递归的划分int mid = l + r >> 1;MergeSort(a, l, mid);MergeSort(a, mid + 1, r);int i = l, j = mid + 1;int k = 0;//统计个数while (i <= mid && j <= r) {//从两个分组中选最小的哪个加入数组，当某个分组选完后停止if (a[i] <= a[j]) t[k++] = a[i++];else t[k++] = a[j++];}//将另一个分组的有序元素直接加入数组后面while (i <= mid) t[k++] = a[i++];while (j <= r) t[k++] = a[j++];//归位for (i = l, j = 0; i <= r; i++, j++) a[i] = t[j];
}
void heapify(int heap[], int size, int u) {//大顶堆//选出三个中最小的 int maxv = u;int ls = u * 2 + 1, rs = u * 2 + 2;//从0开始建立的堆if (ls < size && heap[maxv] < heap[ls])maxv = ls;if (rs < size && heap[maxv] < heap[rs])maxv = rs;//如果最大的哪个不根节点if (u != maxv) {swap(heap[u], heap[maxv]);//最大的节点与根节点交换heapify(heap, size, maxv);//交换后的子树需要调整}
}
void HeapSort(int heap[], int n) {//从一棵完整的二叉树开始，我们可以通过在堆的 所有 非叶元素上运行heapify函数来将其修改为大顶堆for (int i = n / 2 - 1; i >= 0; i--)heapify(heap, n, i);//包括根节点for (int i = n - 1; i > 0; i--) {swap(heap[0], heap[i]);//第一个与最后一个元素交换//调整范围减小heapify(heap, i, 0);}
}int main() {ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);int n;cin >> n;for (int i = 0; i < n; i++)cin >> a[i+1];HeapSort(a, n);for (int i = 0; i < n; i++)cout << a[i+1] << " ";cout << "\n";return 0;
}

二、外部排序

外部排序指待排序文件较大，内存一次放不下，需存放在外存的文件的排序。

1.为减少平衡归并中外存读写次数所采取的方法:增大归并路数和减少归并段个数。

2.利用败者树增大归并路数。

3.利用置换-选择排序增大归并段长度来减少归并段个数。

4.由长度不等的归并段，进行多路平衡归并，需要构造最佳归并树。

外部排序通常采用归并算法

外部排序总时间=内部排序时间+内部归并时间+外存信息读写时间

改进外部排序时间应着力减少磁盘I/O时间

只要增大归并路数k，或减少初始归并段个数r，都能减少归并趟数S，进而减少读写磁盘的次数，达到提高外部排序速度的目的。

败者树

为了使内部归并不受k的增大的影响，引入了败者树。败者树是树形选择排序的一种变体，可视为一棵完全二叉树。k个叶结点分别存放k 个归并段在归并过程中当前参加比较的记录，内部结点用来记忆左右子树中的“失败者"，而让胜者往上继续进行比较，一直到根结点。若比较两个数，大的为失败者、小的为胜利者，则根结点指向的数为最小数。

使用败者树后，内部归并的比较次数与k无关了。因此，只要内存空间允许，增大归并路数k将有效地减少归并树的高度，从而减少IO次数，提高外部排序的速度。

置换选择排序

设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录。

置换-选择算法的步骤如下:
1）从FI输入w个记录到工作区WA。

2）从WA中选出其中关键字取最小值的记录，记为 MINIMAX记录。

3）将MINIMAX记录输出到FO中去。

4）若FI不空，则从FI输入下一个记录到WA中。

5）从WA中所有关键字比MTNIMAX记录的关键字大的记录中选出最小关键字记录，作为
新的MINIMAX记录。

6）重复3）~5），直至在 WA中选不出新的MINIMAX记录为止，由此得到一个初始归并
段，输出一个归并段的结束标志到FO中去。

7）重复2）~6），直至WA为空。由此得到全部初始归并段。

最佳归并树

文件经过置换-选择排序后，得到的是长度不等的初始归并段。
各叶结点表示一个初始归并段，上面的权值表示该归并段的长度，叶结点到根的路径长度表示其参加归并的趟数，各非叶结点代表归并成的新归并段，根结点表示最终生成的归并段。树的带权路径长度WPL为归并过程中的总读记录数。
显然，归并方案不同，所得归并树亦不同，树的带权路径长度（I/O次数）亦不同。为了优化归并树的WPL，可将哈夫曼树的思想推广到m叉树的情形，在归并树中，让记录数少的初始归并段最先归并，记录数多的初始归并段最晚归并，就可以建立总的IO 次数最少的最佳归并树。

如何判定添加虚段的数目?

设度为0的结点有n0{n_0}n0​个，度为k的结点有nk{n_k}nk​个，总结点数为n{n}n个。

因为n=n0+nk=k∗nk+1{n=n_0+n_k=k*n_k+1}n=n0​+nk​=k∗nk​+1,所以nk=(n0−1)/(k−1){n_k=(n_0-1)/(k-1)}nk​=(n0​−1)/(k−1)。

若(n0−1)%(k−1)=0{(n_0-1) \% (k-1)=0}(n0​−1)%(k−1)=0，则恰好可以构成k叉归并树。

若(n0−1)%(k−1)=u{(n_0-1) \% (k-1)=u}(n0​−1)%(k−1)=u，则还需再加k−u−1{k-u-1}k−u−1个空节点。