算法笔记（1）--排序算法
Table of Contents
排序
排序是一个非常经典的问题，它以一定的顺序对一个数组（或一个列表）中的项进行重新排序（可以进行比较，例如整数，浮点数，字符串等）（增加，非递减，递减， 增加，词典等）。
有许多不同的排序算法，每个都有其自身的优点和局限性。排序通常被用作各种计算机科学课程中的介绍性问题，以展示一系列算法思想。在不失概性的情况下，我们假设在这个可视化中，我们将只按非递减顺序对整数进行排序，但不一定是明显的。
1 排序算法思想
1.1 排序算法背后的计算机科学思想
排序问题有许多有趣的算法解决方案，体现了许多计算机科学的想法：
1.2 排序算法应用
当（整数）数组 A 排序时，涉及 A 的许多问题变得简单（或更容易）：
- 在数组 A 中搜索特定值 v，
- 查找（静态）数组 A 中的最小/最大/第 k 个最小/最大值，
- 测试唯一性并删除数组 A 中的重复项，
- 计算特定值 v 在数组 A 中出现多少次，
- 设置数组 A 和另一个排序数组 B 之间的交集/联合，
- 寻找一个目标对 x∈A 和 y∈A，使得 x + y 等于目标 z 等。
1.3 八大排序算法
-
基于比较的排序算法:
- BUB - 冒泡排序,
- SEL - 选择排序,
- INS - 插入排序,
- MER - 归并排序 (递归实现),
- QUI - 快速排序 (递归实现),
- R-Q - 随机快速排序 (递归实现).
-
不基于比较的排序算法:
- COU - 计数排序,
- RAD - 基数排序.
2 排序算法实现及可视化
2.1 冒泡排序
给定一个N个元素的数组，冒泡法排序将：
- 如果元素大小关系不正确，交换这两个数（在本例中为a> b），
- 比较一对相邻元素（a，b），
- 重复步骤1和2，直到我们到达数组的末尾（最后一对是第（N-2）和（N-1）项，因为我们的数组从零开始）
- 到目前为止，最大的元素将在最后的位置。 然后我们将N减少1，并重复步骤1，直到N = 1。
分析：
比较和交换需要一个以常量为界的时间，我们称之为c。（标准）Bubble Sort中有两个嵌套循环。
外循环正好运行N次迭代。 但内部循环运行变得越来越短：
-
当 i = 0，（N-1）次迭代（比较和可能交换）时。
-
当 i = 1，（N-2）次迭代时，...
-
当 i =（N-2）时，1次迭代,
-
当 i=（N-1），0迭代.
因此，总迭代次数=（N-1）+（N-2）+ ... + 1 + 0 = N *（N-1）/ 2（推导）。
总时间= c * N *（N-1）/ 2 = O（N ^ 2）。时间复杂度为O（N^2）.
冒泡排序实际上是低效的，它的 O(N^2) 时间复杂度。 想象一下，我们有 N = 10^6 个数字。 即使我们的计算机速度超快，并且可以在1秒内计算10^8次操作，但冒泡排序仍需要大约100秒才能完成。
代码：
/*
冒泡排序后的顺序为从小到大
*/
void Bubble_Sort(int *arr, const int len,int & cnt) {
int i, j, exchange;
cnt = 0;
bool flag = true; //增设标志位，判断是否已经完成排序
do {
flag = false;
for (i = 0; i < len - 1 && !flag; i++) {
//如果本趟比较没有数据发生交换，说明排序已经完成
//则flag一直为false，从而退出循环，不再进行下一趟的比较
for (j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
exchange = arr[j];
ar[j] = arr[j + 1];
arr[j + 1] = exchange;
flag = true;
cnt++;
}
}
}
} while (flag)
}
可视化操作
2.2 选择排序
给定 N 个项目和 L = 0 的数组，选择排序将：
- 在 [L ... N-1] 范围内找出最小项目 X 的位置，
- 用第 L 项交换X，
- 将下限 L 增加1并重复步骤1直到 L = N-2。
分析：
void selectionSort(int a[], int N) {
for (int L = 0; L <= N-2; L++) { // O(N)
int X = min_element(a+L, a+N) - a; // O(N)
swap(a[X], a[L]); // O(1), X 可能和 L 相等(就没有交换)
}
}复杂度: O(N2) — 实际上，这和冒泡排序很像。
代码实现：
第一种方法较为低效，交换次数较多。
/*
第一种形式的选择排序
选择排序后的顺序为从小到大
*/
void selectSort1(int *arr,int len)
{
int i,j;
for(i=0;i<len;i++)
for(j=i+1;j<len;j++)
if(arr[i] > arr[j])
{
int exchange = arr[i];
arr[i] = arr[j];
arr[j] = exchange;
}
}
第二种方法减少了元素交换次数，效率较高。
/*
第二种形式的选择排序，减少了元素互换的操作
选择排序后的顺序为从小到大
*/
void selectSort2(int *arr,int len)
{
int i,j,min_pos;
for(i=0;i<len;i++)
{
min_pos = i; //用来记录每一趟比较的最小值的位置
for(j=i+1;j<len;j++)
if(arr[min_pos] > arr[j])
min_pos = j; //仅记录最小值的位置
//如果最小值的位置发生了变化，
//则最后执行一次元素互换的操作
if(min_pos != i)
{
int exchange = arr[i];
arr[i] = arr[min_pos];
arr[min_pos] = exchange;
}
}
}可视化操作：
2.3 插入排序
插入排序类似于大多数人安排扑克牌的方式
- 从你手中的一张牌开始，
- 选择下一张卡并将其插入到正确的排序顺序中，
- 对所有的卡重复上一步。
代码分析：
void insertionSort(int a[], int N) {
for (int i = 1; i < N; i++) { // O(N)
X = a[i]; // X is the item to be inserted
int j = i-1;
for (; j >= 0 && a[j] > X; j--) // can be fast or slow
a[j+1] = a[j]; // make a place for X
a[j+1] = X; // index j+1 is the insertion point
}
}外循环执行N-1次，这很明显。
但内循环执行的次数取决于输入：
- 在最好的情况下，数组已经排序并且（a [j]> X）总是为假所以不需要移位数据，并且内部循环运行在O（1），
- 在最坏的情况下，数组被反向排序并且（a [j]> X）始终为真插入始终发生在数组的前端，并且内部循环以O（N）运行。
因此，最佳情况时间是O(N × 1) = O(N) ，最坏情况时间是O(N × N) = O(N2).
2.4 归并排序Merge
给定一个N个项目的数组，归并排序将：
- 将每对单个元素（默认情况下，已排序）归并为2个元素的有序数组，
- 将2个元素的每对有序数组归并成4个元素的有序数组，重复这个过程......，------递归
- 最后一步：归并2个N / 2元素的排序数组（为了简化讨论，我们假设N是偶数）以获得完全排序的N个元素数组。
这只是一般的想法，在我们可以讨论归并排序的真正形式之前，我们需要更多的细节。
我们首先讨论归并排序算法的最重要的子程序：O( N )归并，然后解析这个归并排序算法。
给定两个大小为 N1 和 N2 的排序数组 A 和 B，我们可以在O( N ) 时间内将它们有效地归并成一个大小为 N = N1 + N2的组合排序数组。
这是通过简单地比较两个阵列的前面并始终取两个中较小的一个来实现的。 但是，这个简单但快速的O( N )合并子例程将需要额外的数组来正确地进行合并。
代码：
/*
将有序的arr[start...mid]和有序的arr[mid+1...end]归并为有序的arr[start...end]
*/
void Merge(int *arr,int start,int mid,int end)
{
int i = start;
int j = mid+1;
int k = 0;
//brr为辅助数组，
int *brr = (int *)malloc((end-start+1)*sizeof(int));
//比较两个有序序列中的元素，将较小的元素插入到brr中
while(i<=mid && j<=end)
{
if(arr[i]<=arr[j])
brr[k++] = arr[i++];
else
brr[k++] = arr[j++];
}
//将arr序列中剩余的元素复制到brr中
//这两个语句只可能执行其中一个
while(i<=mid)
brr[k++] = arr[i++];
while(j<=end)
brr[k++] = arr[j++];
//将brr中的元素复制到arr中，使arr[start...end]有序
for(i=0;i<k;i++)
arr[i+start] = brr[i];
//释放brr所占的内存，并将其置为空
free(brr);
brr = 0;
}
/*
对arr[start...end]内的元素进行归并排序
归并排序后的顺序为从小到大
*/
void MSort(int *arr,int start,int end)
{
if(start < end)
{
int mid = (start+end)/2;
MSort(arr,start,mid); //左边递归排序
MSort(arr,mid+1,end); //右边递归排序
Merge(arr,start,mid,end); //左右序列归并
}
}
/*
将该排序算法封装起来
*/
void Merge_Sort(int *arr,int len)
{
MSort(arr,0,len-1);
}
3 分而治之思想
3.1 分治思想（D&C）
在我们继续之前，让我们先谈谈分而治之（Divide and Conquer，缩写为D＆C），这是一个强大的解决问题的范例。
分而治之算法通过以下步骤解决（某种类型的）问题 - 比如我们的排序问题：
- 划分步骤：将大的原始问题划分成较小的子问题并递归地解决较小的子问题，
- 解决步骤：结合较小的子问题的结果来产生较大的原始问题的结果。
3.2 分治与归并排序
归并并排序是分而治之的排序算法。
划分步骤很简单：将当前数组分成两半（如果N是偶数，则将其完全平等，或者如果N是奇数，则一边稍大于一个元素），然后递归地对这两半进行排序。
解决步骤是最有效的工作：使用 前面讨论的归并子例程合并两个（排序的）半部分以形成一个有序数组。
void mergeSort(int a[], int low, int high) {
// 要排序的数组是 a[low..high]
if (low < high) { // base case: low >= high (0 or 1 item)
int mid = (low+high) / 2;
mergeSort(a, low , mid ); // 分成一半
mergeSort(a, mid+1, high); // 递归地将它们排序
merge(a, low, mid, high); // 解决: 归并子程序
}
}分析：
与许多其他CS教科书通常显示的一样（因为教科书是静态的），合并排序的实际执行不会一层一层地分成两个子数组，但是它会在处理正确的子数组之前递归地排序左边的子数组。在示例数组{7,2,6,3,8,4,5}上，它将缓存到{7,2,6,3}，然后是{7,2}，然后是{7}（单个 元素，默认排序），回溯，递归到{2}（排序），回溯，然后在继续处理{6,3}等等之前，最终将{7,2}合并到{2,7}中。
在归并排序中，大部分工作是在解决/归并的步骤中完成的，因为分解步骤并没有真正执行任何操作（视为O（1））。
当我们称之为归并的（a，低，中，高）时候，我们处理k =（高 - 低+ 1）项。 最多会有 k-1 个比较。 从原始数组 a 到临时数组 b 有 k 个移动，而另一个 k 移回。 总的来说，归并子例程内的操作次数 <3k-1 = O（k）。
重要的问题是这个归并子程序被调用了多少次？
级别1：2 ^ 0 = 1调用merge( ) 和 N / 2 ^ 1个项目，O（2 ^ 0 x 2 x N / 2 ^ 1）= O（N）级别2：2 ^ 1 = 2调用 merge( ) 与N / 2 ^ 2个项目，O（2 ^ 1 x 2 x N / 2 ^ 2）= O（N）级别3：2 ^ 2 = 4调用merge( ) 与N / 2 ^ O（2 ^ 2 x 2 x N / 2 ^ 3）= O（N）...级别（log N）：2 ^（log N-1）（或N / 2）调用merge( ) ），其中N / 2 ^ log N（或1）个项目，O（N）
有 log(N) 个日志级别，每个级别都执行O（N）工作，因此总体时间复杂度为O（N log N）。 稍后我们会看到这是一种最佳（基于比较）的排序算法，即我们无法做得比这更好。
优缺点：
无论输入的原始顺序如何，归并排序中最重要的部分是其O（N log N）性能保证。 就这样，没有任何敌手测试用例可以使归并排序对于任何N个元素数组运行比O（N log N）更长的时间。因此，归并排序非常适合分类非常大量的输入，因为O（N log N）比前面讨论的O（N2）排序算法增长得慢得多。
归并排序也是一个稳定的排序算法。 讨论：为什么？
然而，归并排序有几个不太好的部分。 首先，从零开始实施起来并不容易（但我们不必这样做）。 其次，它在归并操作期间需要额外的O（N）存储，因此不是真正的存储效率。
3.3 快速排序
快速排序是另一个分而治之排序算法（另一个在这个可视化页面中讨论的是归并排序）。
我们将看到，这种确定性的，非随机化的快速排序的版本可能在对手输入中具有O（N^2）的很差的时间复杂度，之后再继续随机化的和可用的版本。
划分步骤：选择一个项目 p（称为枢轴点）然后将 a[i..j] 的项目分为三部分：a [i..m-1]，a [m] 和 a[m + 1..j]。 a [i..m-1]（可能为空）包含小于 p 的项目。 a [m] 是枢轴点 p，例如：指数 m 是已排序数组 a 的排序顺序中 p 的正确位置。 a [m + 1..j]（可能为空）包含大于或等于 p 的项目。 然后，递归地对这两部分进行排序。
解决步骤：不要惊讶......我们什么都不做！
如果您将其与归并排序进行比较，您会发现快速排序的 D＆C 步骤与归并排序完全相反。
【快速排序例子】
We will dissect this Quick Sort algorithm by first discussing its most important sub-routine: The O(N) partition (classic version).
To partition a[i..j], we first choose a[i] as the pivot p.
The remaining items (i.e. a[i+1..j]) are divided into 3 regions:
- S1 = a[i+1..m] where items are < p,
- S2 = a[m+1..k-1] where items are ≥ p, and
- Unknown = a[k..j], where items are yet to be assigned to either S1 or S2.
Discussion: Why do we choose p = a[i]? Are there other choices?
Harder Discussion: Is it good to always put item(s) that is/are == p on S2 at all times?
最初，S1 和 S2 区域都是空的，即除了指定的枢轴点 p 之外的所有项目都在未知区域中。
然后，对于未知区域中的每个项目 a [k]，我们将 a[k] 与 p 进行比较, 并决定两种情况中的一个：
- 如果 a [k]≥p，则将 a[k] 放入 S2 或
- 否则，将 a[k] 放入 S1 中。
接下来的两张幻灯片将会详细阐述了这两种情况。
最后，我们交换a[i]和 a[m] 来将枢纽 p 放在 S1 和 S2 的中间。
分区排序算法C++实现：
int partition(int a[], int i, int j) {
int p = a[i]; // p 是枢纽
int m = i; // S1 和 S2 一开始是空的
for (int k = i+1; k <= j; k++) { // 探索未知的区域
if (a[k] < p) { // case 2
m++;
swap(a[k], a[m]); // C++ STL algorithm std::swap
} // 注意：在情况1的时候我们什么不做: a[k] >= p
}
swap(a[i], a[m]); // 最后一步, 用a[m]交换枢纽
return m; // 返回枢纽的指数, 用于快速排序（Quick Sort）
}快速排序算法C++实现：
void quickSort(int a[], int low, int high) {
if (low < high) {
int m = partition(a, low, high); // O(N)
// a[low..high] ~> a[low..m–1], pivot, a[m+1..high]
quickSort(a, low, m-1); // 递归地将左子阵列排序
// a[m] = pivot 在分区后就被排序好了
quickSort(a, m+1, high); // 然后将右子阵列排序
}
}可视化实例：
分析：
在示例数组[27,38,12,39,27,16]上尝试Quick Sort。我们将详细说明第一个分区步骤如下：我们设置 p = a [0] = 27。我们设置 a[1] = 38作为 S2的一部分，因此S1 = {} 和 S2 = {38}。 我们用 a [2] = 12 交换 a[1] = 38，所以 S1 = {12} 和 S2 = {38}。 我们设置 a[3] = 39，然后 a [4] = 27 作为 S2 的一部分，因此 S1 = {12} 和 S2 = {38,39,27}。 我们用 a[5] = 16 交换 a[2] = 38，所以S1 = {12,16} 和 S2 = {39,27,38}。 我们用 a [2] = 16 交换 p = a [0] = 27，所以 S1 = {16,12}，p = {27} 和 S2 = {39,27,38}。
在此之后，a[2] = 27 保证被排序，现在快速排序递归地将左侧排序为 a[0..1]，然后递归地将右侧排序为 a[3..5]。
【三分区的快速排序分析】
首先，我们分析跑一次分区的成本。
在内部分区（a，i，j）中，只有一个for循环遍历（j-i）次。 由于j可以和 N-1一样大，i 可以低至0，所以分区的时间复杂度是O（N）。
类似于归并排序分析，快速排序的时间复杂度取决于分区（a，i，j）被调用的次数。
当数组a已经按照上面的例子升序时，快速排序将设置p = a [0] = 5，并且将返回m = 0，从而使S1区域为空并且S2区域：除了枢轴之外的其他一切 （N-1项）。
在示例输入数组[5,18,23,39,44,50]上尝试Quick Sort。
在这种最坏情况的输入场景中，会发生以下情况：
第一个分区需要O（N）时间，将a分成0,1，N-1个项目，然后向右递归。
第二个花费O（N-1）时间，将a分成0,1，N-2个项目，然后再次向右递归...
直到最后，第N个分区将a分成0,1,1项，并且Quick Sort递归停止。
当分区总是将数组分成两个相等的一半时，就会发生快速排序的最佳情况，如归并排序。
当发生这种情况时，递归的深度只有O（log N）。由于每个级别进行O（N）比较，时间复杂度为O（N log N）。
在这个手工制作的示例输入数组[4,1,3,2,6,5,7]上尝试Quick Sort。
在实践中，这很少见，因此我们需要设计一个更好的方法：随机快速排序。
3.4 随机快速排序
除了执行分区算法之外，它与快速排序相同，它随机选择 a[i..j] 之间的枢轴，而不是始终选择 a[i]（或 a[i..j]之间的任何其他固定索引）。
尝试Random Quick Sort这个大，但也有点随机的示例数组。
4 不基于比较的排序算法
在接下来的内容，我们将讨论两种不基于比较的排序算法:
这些排序算法可以通过不比较数组的元素来比时间复杂度为Ω（N log N）的基于比较的排序算法的下限更快。
任何具有最坏情况复杂度O（N log N）的基于比较的排序算法（如归并排序）都被认为是最优算法，即我们不能做得比这更好。
然而，如果存在输入数组的某些假设，我们可以避免比较这些项目来确定排序顺序， 然后实现更快的排序算法 - 比如在O（N）中。
4.1 计数排序
假设：如果要排序的元素是小范围的整数，我们可以计算每个整数（在这个小范围内）的出现频率，然后通过循环该小范围来按排序顺序输出元素。
在上面的示例数组中，对所有整数都在[1..9]内的示例数组尝试Counting Sort，因此我们只需要计算整数1出现的次数，出现整数2，...，出现整数9，然后遍历 如果频率 [y] = x，则 1至9 打印出整数 y 的 x 个副本。
时间复杂度为O（N）来计算频率，O（N + k）以排序顺序输出结果，其中 k 是输入的整数范围，在本例中为9-1 + 1 = 9。 计数排序（Counting Sort）的时间复杂度为O（N + k），如果 k 很小，那么它就是O（N）。
由于内存限制，当 k 相对较大时，我们将无法执行计数排序（Counting Sort）的计数部分，因为我们需要存储那些 k 个整数出现的次数。
算法思路：
计数排序代码：
/*
计数排序后的顺序为从小到大
arr[0...len-1]为待排数组，每个元素均是0-k中的一个值
crr[0...k]保存0...k中每个值在数组arr中出现的次数
*/
void Count_Sort(int *arr,int *crr,int len,int k)
{
int i,j=0;
//数组crr各元素置0
for(i=0;i<=k;i++){
crr[i] = 0;
}
//统计数组arr中每个元素重复出现的个数
for(i=0;i<len;i++)
crr[arr[i]]++;
//根据crr[i]的大小，将元素i放入arr适当的位置
for(i=0;i<=k;i++)
while((crr[i]--)>0)
{
arr[j++] = i;
}
}
4.2 基数排序
假设：如果要排序的元素是大范围但小数位的整数，我们可以将计数排序（Counting Sort）思想与基数排序（Radix Sort）结合起来，以实现线性时间复杂度。
在基数排序中，我们将每个项目排序为一个 w 数字串（如果需要，我们填充小于w数字的前几个零的整数）。
对于最低有效位（最右边）到最高有效位（最左边），我们通过 N 个项目并将它们按照活动数字放到10个队列中（每个数字[0..9]一个），就好像 一个修改的计数排序，因为这保留了稳定性。 然后我们再次重新连接组，以便进行后续迭代。
请尝试上面示例数组的Radix Sort来了解更清晰的解释。
请注意，我们只执行O（w×（N + k））次迭代。 在这个例子中，w = 4，k = 10。
计数排序代码：
/*
在第一种计数排序的实现形式上做了些修改
计数排序后的顺序为从小到大
arr[0...len-1]为待排数组，我们这里采用三位数
brr[0...len-1]为排序后的有序数组
w[0...len-1]用来保存取出的每一位上的数，其每个元素均是0-k中的一个值
crr[0...k]保存0...k中每个值出现的次数
*/
void Count_Sort(int *arr,int *brr,int *w,int *crr,int len,int k)
{
int i;
//数组crr各元素置0
for(i=0;i<=k;i++)
crr[i] = 0;
//统计数组w中每个元素重复出现的个数
for(i=0;i<len;i++)
crr[w[i]]++;
//求数组w中小于等于i的元素个数
for(i=1;i<=k;i++)
crr[i] += crr[i-1];
//把arr中的元素放在brr中对应的位置上
for(i=len-1;i>=0;i--)
{
brr[crr[w[i]]-1] = arr[i];
//如果有相同的元素，则放在下一个位置上
crr[w[i]]--;
}
//再将brr中的元素复制给arr，这样arr就有序了
for(i=0;i<len;i++)
{
arr[i] = brr[i];
}
}
/*
* arr[0...len-1]为待排数组，我们这里采用三位数
brr[0...len-1]为排序后的有序数组
w[0...len-1]用来保存取出的每一位上的数，其每个元素均是0-k中的一个值
crr[0...k]保存0...k中每个值出现的次数
基数排序后的顺序为从小到大
其中参数d为元素的位数，如100是三位的整数，d=3，1010是四位整数，d=4
*/
void Basic_Sort(int *arr,int *brr,int *w,int *crr,int len,int k,int d)
{
int i,j,val=1;
//从低位到高位依次进行计数排序
for(i=1;i<=d;i++)
{ //w中保存的是arr中每个元素对应位上的数
//范围在0-k之间
for(j=0;j<len;j++)
w[j] = (arr[j]/val)%10;
//对当前位进行计数排序
Count_Sort(arr,brr,w,crr,len,k);
val *= 10;
}
}
5 排序算法优劣
除了比较还是非比较，递归或迭代之外，还有其他一些属性可用于区分排序算法。
在本节中，我们将讨论就地与非就地，稳定与不稳定以及高速缓存排序算法的性能。
5.1 就地与非就地排序
如果排序算法在排序过程中仅需要恒定量（即，O（1））的额外空间，则称其为就地排序算法。就是这样，少量的额外变量的常量是可以的，但我们不允许具有可变长度的变量，这取决于输入大小N.
归并排序，由于其合并子例程需要额外的大小为N的临时数组，因此不在原位。
讨论：冒泡排序，选择排序，插入排序，快速排序（是否随机），计数排序和基数排序如何？哪些是就地？
5.2 稳定与非稳定排序
如果在执行排序后算法保留具有相同键值的元素的相对顺序，则这个排序算法称为稳定的排序。
稳定排序的示例应用：假设我们有按字母顺序排序的同班级学生姓名。 现在，如果此列表按组号重新排序（回想一个班级组通常有许多学生），稳定的排序算法会确保同一班级组中的所有学生仍按字母顺序显示其名称。
讨论：在这里讨论过的排序算法中哪些是稳定的？
尝试排序数组A = {3, 4a, 2, 4b, 1}进行排序，即有两个4（4a先，然后4b）的副本。
5.3 大容量数据时排序算法比较
参考博客：
https://blog.****.net/qq_36523667/article/details/81193657
堆排序和快速排序的比较
堆排序是接近nlgn的下界，而快排有性能坏的情况，为何还是快排表现更优秀呢？
1.堆排序是处理数组中相隔较远的数据，快速排序是根据两个 指针按序遍历的，根据寄存器、高速缓存的热cache、 局部性原理，快排更好
2.快排的极端情况太难复现，而且可以 用随机基准数
3.快排还有各种优化的方案
https://blog.****.net/ztkhhhhhd/article/details/53138631 大容量数据排序
https://blog.****.net/zhushuai1221/article/details/51781002 非常详细的排序性能分析和选择条件。