归并排序：
归并排序算法过程
所以，我们总结一下归并排序的算法过程：
假设我们要对数组a[1..n]排序。初始化左端点l=1，右端点r=n。
下面假设我们对l到r子段内的数字进行划分。取l和r的中点mid，将l到mid的元素看成第一个子段的部分，将mid+1到r的部分看成第二个子段的部分。两边分别进入下一层，重复调用上面的过程。直到子段长度为1，返回上一层。
当算法阶段返回到当前层时，使用归并操作合并下一层的左右两个有序序列，形成本层的有序序列，继续返回上一层。
当整个过程结束以后，整个序列排序完毕。
归并排序时我们仍然使用递归函数的方式。具体框架如下：
#include <bits/stdc++.h> #define N 100010 using namespace std; int n; int a[N]; void merge_sort(int l, int r) { // l和r分别代表当前排序子段在原序列中左右端点的位置 if (l >= r) return; // 当子段为空或者长度为1，说明它已经有序，所以退出该函数 int mid = l + r >> 1; // 取序列的中间位置，并将序列分成两部分（左右长度相差最多为1） // l + r 的值右移1位，相当 l + r 的值除以2取整。 merge_sort(l, mid); // 对``l``到``mid``第一个子段进行归并操作 merge_sort(mid + 1, r); // 对``mid+1``到``r``第二个子段子段进行归并操作 /* 这里省略将数组a[l..mid]和数组a[(mid+1)..r]合并的过程。 */ } int main() { // 输入 scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); // 归并排序 merge_sort(1, n); // 输出 for (int i = 1; i <= n; ++i) printf("%d ", a[i]); return 0; }
归并排序完整代码
将前两步骤中「整体框架」和「归并操作」进行合并，就能得到完整的归并排序代码：
#include <bits/stdc++.h> #define N 100010 using namespace std; int n; int a[N], b[N]; // 合并操作 void merge(int l, int r) { for (int i = l; i <= r; ++i) b[i] = a[i]; // 将a数组对应位置复制进辅助数组 int mid = l + r >> 1; // 计算两个子段的分界线 int i = l, j = mid + 1; // 初始化i和j两个指针分别指向两个子段的首位 for (int k = l; k <= r; ++k) { // 枚举原数组的对应位置 if (j > r || i <= mid && b[i] < b[j]) a[k] = b[i++]; // 上文中列举的条件 else a[k] = b[j++]; } } void merge_sort(int l, int r) { // l和r分别代表当前排序子段在原序列中左右端点的位置 if (l >= r) return; // 当子段为空或者长度为1，说明它已经有序，所以退出该函数 int mid = l + r >> 1; // 取序列的中间位置，并将序列分成两部分（左右长度相差最多为1） merge_sort(l, mid); merge_sort(mid + 1, r); merge(l, r); // 将l..mid和mid+1..r两个子段合并成完整的l..r的有序序列 } int main() { // 输入 scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); // 归并排序 merge_sort(1, n); // 输出 for (int i = 1; i <= n; ++i) printf("%d ", a[i]); return 0; }
代码实现 —— stable_sort函数使用
同样，归并排序实现起来也并不容易，所以STL中也有对归并排序的优化实现，函数名为stable_sort。使用方法与sort一样，见下例：
#include <bits/stdc++.h> using namespace std; int a[10] = {0, 2, 3, 1, 5, 4}; // 1-base，0号元素无意义 int n = 5; bool cmp(int x, int y) { // 比较函数，函数的参数是当前比较的两个数组中的元素 return x > y; // x和y分别为排序数组中的两个元素。 } // 当函数返回值为true时，x应该排在y的前面。 int main() { stable_sort(a + 1, a + n + 1, cmp); // 比较函数作为第三个参数传入sort函数 for (int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << endl; }
之所以该函数叫做stable_sort，是因为归并排序是稳定排序，而快速排序不是稳定排序（这是因为选择作为分界线的点在不同实现中位置可能不一样。对于有些实现，当i被选为分界点，且该位置的值是a[i]时，它右边和a[i]相等的元素很有可能被换到i的左边，这时就破坏了稳定性）。回忆稳定排序的概念：
稳定性描述的是对于有重复元素的序列，如果排序前后，重复的元素相对位置不变。这种叫做稳定算法，否则就是不稳定。参考下面的示意图：
复杂度分析
空间复杂度
首先该算法的空间复杂度是O(n)O(n)，但尽管如此，在整个排序过程中，元素的移动借助了另一个辅助数组。所以归并排序是一种非原地排序算法。
时间复杂度
因为归并排序有着和快速排序一样的框架，所以我们仍然通过分别分析每一层的时间复杂度和总层数来分析总时间复杂度。
在每一层中，问题拆分的复杂度是O(1)O(1)，这是因为我们只是单纯分解，并没有枚举或者移动元素，唯一的操作仅是计算位置的分界线。对于子段解的合并，其复杂度是O(n)O(n)，因为对于每个子段，我们需要将其枚举每个位置进行填写。而如果我们同时考虑整层的操作，总枚举的范围就是整个数组的范围。
那么一共有多少层呢？因为归并排序每次都是将序列平分，所以下一层子段的长度一定比上一层减少了一半，直到长度为1算法停止。所以整个算法有\log nlogn层。
所以归并排序的复杂度在任何情况下都是O(n\log n)O(nlogn)。
总结
和快速排序一样，归并排序也是基于分治法的排序算法。其基本思想在于将待排序序列分成长度相差不超过1的两份，分别对左右子段进行同样的划分和排序过程，最后将两个已经排好序的子段合并成整个完整的有序序列。
归并排序的时间复杂度是O(n\log n)O(nlogn)，在实现时，需要辅助数组帮助合并子段，所以是一种非原地排序算法。
和快速排序不同的是，归并排序是一种稳定排序，即相同元素在排序前后的数组中相对位置不变。
stable_sort函数是C++标准模板库（STL）中一种对归并排序的优化实现，可以通过传入头指针、尾指针和比较函数来对数组中的对象进行排序。
归并排序示例：
将数组{2, 3, 1, 5, 4}从小到大排列。
不使用stable_sort函数
将「整体框架」和「归并操作」进行合并，我们得到归并排序完整代码：
#include <bits/stdc++.h> #define N 100010 using namespace std; int n; int a[N], b[N]; // 合并操作 void merge(int l, int r) { for (int i = l; i <= r; ++i) b[i] = a[i]; // 将a数组对应位置复制进辅助数组 int mid = l + r >> 1; // 计算两个子段的分界线 int i = l, j = mid + 1; // 初始化i和j两个指针分别指向两个子段的首位 for (int k = l; k <= r; ++k) { // 枚举原数组的对应位置 if (j > r || i <= mid && b[i] < b[j]) a[k] = b[i++]; // 上文中列举的条件 else a[k] = b[j++]; } } void merge_sort(int l, int r) { // l和r分别代表当前排序子段在原序列中左右端点的位置 if (l >= r) return; // 当子段为空或者长度为1，说明它已经有序，所以退出该函数 int mid = l + r >> 1; // 取序列的中间位置，并将序列分成两部分（左右长度相差最多为1） merge_sort(l, mid); merge_sort(mid + 1, r); merge(l, r); // 将l..mid和mid+1..r两个子段合并成完整的l..r的有序序列 } int main() { // 输入 scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); // 归并排序 merge_sort(1, n); // 输出 for (int i = 1; i <= n; ++i) printf("%d ", a[i]); return 0; }
使用stable_sort函数
#include <bits/stdc++.h> using namespace std; int a[10] = {0, 2, 3, 1, 5, 4}; // 1-base，0号元素无意义 int n = 5; bool cmp(int x, int y) { // 比较函数，函数的参数是当前比较的两个数组中的元素 return x > y; // x和y分别为排序数组中的两个元素。 } // 当函数返回值为true时，x应该排在y的前面。 int main() { stable_sort(a + 1, a + n + 1, cmp); // 比较函数作为第三个参数传入sort函数 for (int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << endl; }
计数排序：
计数排序的基本思想：
假设我们已知在待排序的序列中，值都是整数并且出现在一个很小的范围内，例如[0..1000]。那么，我们可以通过：
分别统计每一种可能的值在序列中出现的次数。
从小到大（假设要求将序列从小到大排序）枚举所有值，按照出现次数输出对应个数。
计数排序算法描述
给定长度为n的序列，假设已知序列元素的范围都是[0..K]中的整数，并且K的范围比较小（例如10^6106，开长度为10^6106左右的int类型数组所占用的内存空间只有不到4M）。解决该问题的计数排序算法描述如下：
使用整数数组cnt统计[1..K]范围内所有数字在序列中出现的个数。
使用变量i枚举1到K，如果i出现了cnt[i]次，那么在答案序列的末尾添加cnt[i]个i。
下图是一个n=6, K=3的例子：
值得一提的是，如果元素的范围可以被很容易转换到[0..K]，我们也可以使用计数排序。如果元素范围是[A..B]，我们可以通过简单的平移关系将其对应到[0..B-A]上。或者所有数值均为绝对值不超过100的两位小数，那么我们可以通过将所有数字放大100倍将其转换为整数。
算法描述如下：
统计原序列中每个值的出现次数，记为cnt数组。
从小到大枚举值的范围，对cnt数组求前缀和，记为sum数组。
从后往前枚举每个元素a[i]，分配其在答案中的位置idx[i]为当前的sum[a[i]]，也就是将其放在所有值等于a[i]中的最后一个。并且将sum[a[i]]减少1，保证下次再遍历到同样的值时，它分配的位置正好在idx[i]前面一个。
计数排序代码实现
下面我们给出计数排序的简单实现：
#include <bits/stdc++.h> #define N 1000005 #define K 1000001 // 假设非负整数最大元素范围为1000000 using namespace std; int a[N], n, b[N]; int cnt[K]; int main() { // 输入 cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; ++cnt[a[i]]; // 这里通过计数数组cnt来维护每一种值出现的次数 } // 维护最终有序序列 for (int i = 0, j = 0; i < K; ++i) // 枚举每一种值i，指针j用来枚举填充答案数组中的位置 for (int k = 1; k <= cnt[i]; ++k) // 根据该值出现的次数 b[++j] = i; // 添加对应个数的i到答案序列 // 输出 for (int i = 1; i <= n; ++i) cout << b[i] << ' '; cout << endl; return 0; }
其中：
在计数排序的输入部分，我们用cnt数组统计了每种值出现的个数。
在维护最终有序序列的部分，我们按照值从小到大的顺序，放置相应cnt个元素到答案数组里。
代码实现 —— 计数排序2
找出原序列中的元素和答案数组中的对应
这里，我们给出另外一种计数排序的实现方法。其中
在输入部分，我们统计每一种值出现的次数
在求原序列和答案序列的位置对应关系的部分，我们对cnt数组求前缀和，并存储在sum中。回忆上一节提到，对于一个值x，sum[x]的含义是“小于等于x的数字个数”，同时，也可以看作指向答案序列中最后一个x出现的位置的指针。
然后，我们从后向前枚举原序列的每个元素x，将sum[x]指向的位置分配给它，存在idx数组中，然后将sum[x]前移。这里“从后向前”是因为考虑到对于同一个值，分配位置的顺序是从后向前。所以，我们从后向前枚举原序列，可以保证在值相同的情况下，在原序列中出现在后面的元素会被分配到更大的位置，也就保证列排序的稳定性。
因为原序列中i位置的数字，在答案序列中出现在idx[i]处。所以我们据此生成答案序列。
#include <bits/stdc++.h> #define N 1000005 #define K 1000001 // 假设非负整数最大元素范围为1000000 using namespace std; int a[N], n, b[N]; int cnt[K], sum[K]; int idx[N]; // 用来记录原序列中每个元素在新序列中的位置 int main() { // 输入 cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; ++cnt[a[i]]; // 这里通过计数数组cnt来维护每一种值出现的次数 } // 求原序列和答案序列中的位置对应 sum[0] = cnt[0]; // 假设最小值为0 for (int i = 1; i < K; ++i) // 求cnt的前缀和 sum[i] = sum[i - 1] + cnt[i]; for (int i = n; i; --i) // 给每个元素分配位置 idx[i] = sum[a[i]]--; // 之所以倒循环，是因为对于相等的元素我们是从后向前分配位置 // 这样我们可以保证排序的稳定性 // 根据求出的位置将每个元素放进答案序列中 for (int i = 1; i <= n; ++i) b[idx[i]] = a[i]; // 输出 for (int i = 0; i <= n; ++i) cout << b[i] << ' '; cout << endl; return 0; }
复杂度分析
计数排序代码简单实现
这里我们分析第一种计数排序实现方法。
#include <bits/stdc++.h> #define N 1000005 #define K 1000001 // 假设非负整数最大元素范围为1000000 using namespace std; int a[N], n, b[N]; int cnt[K]; int main() { // 输入 cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; ++cnt[a[i]]; // 这里通过计数数组cnt来维护每一种值出现的次数 } // 维护最终有序序列 for (int i = 0, j = 0; i < K; ++i) // 枚举每一种值i，指针j用来枚举填充答案数组中的位置 for (int k = 1; k <= cnt[i]; ++k) // 根据该值出现的次数 b[++j] = i; // 添加对应个数的i到答案序列 // 输出 for (int i = 1; i <= n; ++i) cout << b[i] << ' '; cout << endl; return 0; }
其中
在计数排序的输入部分，我们用cnt数组统计了每种值出现的个数。
在维护最终有序序列的部分，我们按照值从小到大的顺序，放置相应cnt个元素到答案数组里。
找出原序列中的元素和答案数组中的对应
空间复杂度
因为在上面的代码中一共开了3个数组，长度分别为O(N)O(N)（对于a和b）和O(K)O(K)（对于cnt）。整个空间复杂度为O(N + K)。
时间复杂度
容易发现，算法的输入输出部分所占时间复杂度为O(n)O(n)。
在“维护有序序列”的部分，我们首先考虑最外层循环，因为它遍历了所有[0..K]的数字，所以它的复杂度是O(K)O(K)。
其次，我们考虑内层循环的循环次数，其在外层循环为i时为cnt[i]。因为对于不同的输入，以及外层循环枚举到的不同的i，cnt[i]差别很大。但如果我们把所有i对应的内层循环次数相加，即可得到：
\text{内层循环总次数} = \sum_{i = 1}^{K} cnt[i] = n内层循环总次数=i=1∑Kcnt[i]=n
所以，整个算法的复杂度为O(n + K)O(n+K)。
我们提到过，有一条结论
所有基于比较的排序算法的时间复杂度都为\Omega(n\log n)Ω(nlogn)。（\OmegaΩ和OO记号类似，但OO表示的是“不会超过”，而\OmegaΩ表示的是“不会少于”）。
我们看到当K = O(n)K=O(n)时，整个算法的时间复杂度为O(n)O(n)。之所以计数排序可以达到比O(n\log n)O(nlogn)更好的时间复杂度，就是因为它并不是基于比较的排序。
对于基于原序列和答案序列位置对应设计的计数排序，经过分析可以发现其复杂度和第一种一样。大家可以自己尝试分析一下。
总结
计数排序的基本思想是通过统计序列中不同的值出现的次数来排序。因为要用数组统计个数，所以要求在计数排序之前，整个序列中的元素需转换成在很小范围[0..K]的非负整数。
计数排序的算法描述：
统计原序列中每个值的出现次数，记为cnt数组。
从小到大枚举值的范围，对cnt数组求前缀和，记为sum数组。
从后往前枚举每个元素a[i]，分配其在答案中的位置idx[i]为当前的sum[a[i]]，也就是将其放在所有值等于a[i]中的最后一个。并且将sum[a[i]]减少1，保证下次再遍历到同样的值时，它分配的位置正好在idx[i]前面一个。
计数排序的代码实现1：
#include <bits/stdc++.h> #define N 1000005 #define K 1000001 // 假设非负整数最大元素范围为1000000 using namespace std; int a[N], n, b[N]; int cnt[K]; int main() { // 输入 cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; ++cnt[a[i]]; // 这里通过计数数组cnt来维护每一种值出现的次数 } // 维护最终有序序列 for (int i = 0, j = 0; i < K; ++i) // 枚举每一种值i，指针j用来枚举填充答案数组中的位置 for (int k = 1; k <= cnt[i]; ++k) // 根据该值出现的次数 b[++j] = i; // 添加对应个数的i到答案序列 // 输出 for (int i = 1; i <= n; ++i) cout << b[i] << ' '; cout << endl; return 0; }
其中：
在计数排序的输入部分，我们用cnt数组统计了每种值出现的个数。
在维护最终有序序列的部分，我们按照值从小到大的顺序，放置相应cnt个元素到答案数组里。
上述计数排序实现方法的时间和空间复杂度都是O(n+K)O(n+K)。正因为它不是基于比较的排序，所以才能达到比O(n\log n)O(nlogn)更好的时间复杂度。
计数排序的基本思想还可以拓展成桶排序和基数排序。使用桶排序和基数排序的，可以对更大范围内的，甚至不是整数的序列进行排序。
