1. 排序的概念及其运用
1.1 排序的概念
https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Insertion_sort
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 常见的排序算法
// 排序实现的接口
// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 选择排序
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n);
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right);
// 归并排序递归实现
void MergeSort(int* a, int n);
// 归并排序非递归实现
void MergeSortNonR(int* a, int n);
// 计数排序
void CountSort(int* a, int n);
// 测试排序的性能对比
void TestOP()
{
srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
}排序OJ(可使用各种排序跑这个OJ)力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode-cn.com/problems/sort-an-array/
2. 常见排序算法的解析与实现
2.1 插入排序
2.1.1 基本思想
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
实际中我们玩扑克牌时，就用了插入排序的思想
2.1.2 直接插入排序
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
2.1.3 直接插入排序的实现
// 定义一个插入排序函数
void InsertSort(int* a,int n)
{
// 遍历数组，从第一个元素到倒数第二个元素
for (int i = 0; i < n-1; i++)
{
// 定义当前元素的位置
int end = i;
// 保存当前元素的值
int temp = a[end + 1];
// 循环向前比较，直到找到合适的位置插入当前元素
while (end >= 0)
{
if (temp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
// 将当前元素插入到合适的位置
a[end + 1] = temp;
}
}直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度: Worst : O(N^2) , Best : O(N)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
2.2 希尔排序
2.2.1 基本思想
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
2.2.2 希尔排序的实现
一组一组排：
void ShellSort(int* a, int n)
{
int gap = n; // 初始化间隔为数组长度
// 开始希尔排序
while (gap > 1) // 当间隔大于1时进行排序
{
gap = gap / 3 + 1; // 根据规则更新间隔
// 以下是希尔排序的核心算法
for (int i = 0; i < n - gap; i++) // 以间隔为步长进行插入排序
{
int end = i;
int temp = a[end + gap]; // 保存当前位置的值
while (end >= 0)
{
if (temp < a[end]) // 如果当前值小于前一个值，则交换位置
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = temp; // 插入当前值到正确位置
}
}
}
多组并排：
void ShellSort(int* a, int n)
{
int gap = n; // 初始化间隔为数组长度
// 开始希尔排序
while (gap > 1) // 当间隔大于1时进行排序
{
gap = gap / 3 + 1; // 根据规则更新间隔
// 以下是希尔排序的核心算法
for (int j = 0; j < gap; j++) // 以间隔为步长进行插入排序
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;
int temp = a[end + gap]; // 保存当前位置的值
while (end >= 0)
{
if (temp < a[end]) // 如果当前值小于前一个值，则交换位置
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = temp; // 插入当前值到正确位置
}
}
}
}
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：
《数据结构(C语言版)》--- 严蔚敏
《数据结构-用面相对象方法与C++描述》--- 殷人昆
https://en.wikipedia.org/wiki/Shellsorthttps://en.wikipedia.org/wiki/Shellsort 4. 稳定性：不稳定
2.3 选择排序
2.3.1 基本思想
https://en.wikipedia.org/wiki/Selection_sorthttps://en.wikipedia.org/wiki/Selection_sort
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
2.3.2 直接选择排序
（1）在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素。
（2）若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个(第一个)元素交换。
（3）在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。
2.3.3 选择排序的实现
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
// 开始选择排序
while (begin < end)
{
int min = begin;
int max = begin;
// 找到当前范围内的最小值和最大值的索引
for (int i = begin + 1; i <= end; i++)
{
if (a[i] < a[min])
{
min = i;
}
if (a[i] > a[max])
{
max = i;
}
}
// 将最小值与当前范围的起始位置交换
int temp1 = a[begin];
a[begin] = a[min];
a[min] = temp1;
// 如果最大值的索引等于当前范围的起始位置，更新最大值的索引
if (max == begin)
{
max = min;
}
// 将最大值与当前范围的结束位置交换
int temp2 = a[max];
a[max] = a[end];
a[end] = temp2;
begin++;
end--;
}
}
直接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
2.4 堆排序
2.4.1 基本思想
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
https://en.wikipedia.org/wiki/Heapsorthttps://en.wikipedia.org/wiki/Heapsort
2.4.2 堆排序的实现
typedef int HeapDataType; // 定义堆数据类型为整型
void Swap(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
// 向上调整建大堆
void AdjustUp1(HeapDataType* a, int child)
{
int parent = (child - 1) / 2; // 计算父节点索引
while (child > 0)
{
if (a[child] > a[parent]) // 如果子节点大于父节点
{
Swap(&a[child], &a[parent]); // 交换子节点和父节点的值
child = parent; // 更新子节点索引
parent = (parent - 1) / 2; // 更新父节点索引
}
else
{
break; // 如果子节点不大于父节点，则退出循环
}
}
}
// 向上调整建小堆
void AdjustUp2(HeapDataType* a, int child)
{
int parent = (child - 1) / 2; // 计算父节点索引
while (child > 0)
{
if (a[child] < a[parent]) // 如果子节点小于父节点
{
Swap(&a[child], &a[parent]); // 交换子节点和父节点的值
child = parent; // 更新子节点索引
parent = (parent - 1) / 2; // 更新父节点索引
}
else
{
break; // 如果子节点不小于父节点，则退出循环
}
}
}
// 大堆的向下调整
void AdjustDown1(HeapDataType* a, int size, int parent)
{
int child = parent * 2 + 1; // 计算左孩子节点索引
while (child < size)
{
if (child + 1 < size && a[child] < a[child + 1]) // 如果右孩子存在且大于左孩子
{
child++; // 右孩子节点索引加1，选择较大的孩子节点
}
if (a[child] > a[parent]) // 如果孩子节点大于父节点
{
Swap(&a[child], &a[parent]); // 交换孩子节点和父节点的值
parent = child; // 更新父节点索引
child = child * 2 + 1; // 更新孩子节点索引
}
else
{
break; // 如果孩子节点不大于父节点，则退出循环
}
}
}
// 小堆的向下调整
void AdjustDown2(HeapDataType* a, int size, int parent)
{
int child = parent * 2 + 1; // 计算左孩子节点索引
while (child < size)
{
if (child + 1 < size && a[child] > a[child + 1]) // 如果右孩子存在且小于左孩子
{
child++; // 右孩子节点索引加1，选择较小的孩子节点
}
if (a[child] < a[parent]) // 如果孩子节点小于父节点
{
Swap(&a[child], &a[parent]); // 交换孩子节点和父节点的值
parent = child; // 更新父节点索引
child = child * 2 + 1; // 更新孩子节点索引
}
else
{
break; // 如果孩子节点不小于父节点，则退出循环
}
}
}
void HeapSort(HeapDataType* a, int n)
{
#if 1
// 大堆排序
for (int i = ((n - 1) - 1) / 2; i >= 0; i++) // 从最后一个非叶子节点开始向上调整建堆
{
AdjustDown1(a, n, i); // 向下调整建大堆
}
int end = n - 1; // 堆尾索引
while (end > 0)
{
Swap(&a[0], &a[end]); // 将堆顶元素与末尾元素交换
AdjustDown1(a, end, 0); // 重新调整堆顶元素
end--; // 缩小堆范围
}
#endif
#if 0
for (int i = 0; i < n; i++)
{
AdjustUp2(a, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown2(a, end, 0);
end--;
}
#endif
}
堆排序的特性总结：
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
2.5 冒泡排序
https://en.wikipedia.org/wiki/Bubble_sorthttps://en.wikipedia.org/wiki/Bubble_sort
2.5.1 基本思想
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
2.5.2 冒泡排序的实现
// 定义一个函数，用于交换两个整数指针指向的值
void Swap(int* x, int* y)
{
int temp = *x; // 用一个临时变量保存x指向的值
*x = *y; // 将y指向的值赋给x指向的值
*y = temp; // 将临时变量的值赋给y指向的值
}
// 定义一个函数，用于对整型数组进行冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++) // 外层循环控制比较的轮数
{
int flag = 1; // 设置一个标志位，用于判断是否已经完成排序
for (int j = 0; j < n - 1 - i; j++) // 内层循环进行相邻元素的比较和交换
{
if (a[j] > a[j + 1]) // 如果前一个元素大于后一个元素
{
flag = 0; // 将标志位置为0，表示还未完成排序
Swap(&a[j], &a[j + 1]); // 调用Swap函数交换两个元素的值
}
}
if (flag) // 如果标志位仍为1，说明已经完成排序
break; // 跳出循环，排序结束
}
} 冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
2.6 快速排序
https://en.wikipedia.org/wiki/Quicksorthttps://en.wikipedia.org/wiki/Quicksort
2.6.1 基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
if(right - left <= 1)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
int div = partion(array, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div+1, right);
}2.6.2 快速排序优化
1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序
这里的partion（分区）方案我选的是三数取中：
int partion(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[end] < a[begin])
return begin;
else if (a[end] > a[mid])
return mid;
else
return end;
}
else
{
if (a[end] < a[mid])
return mid;
else if (a[end] > a[begin])
return begin;
else
return end;
}
}上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
2.6.3 快速排序的实现
C/C++库函数实现：
qsort：
int compare(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
int main()
{
int arr[] = { 3, 2, 6, 8, 4, 10, 0, 9, 5, 7, 1 };
qsort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(int), compare);
for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
printf("%d ", arr[i]);
return 0;
}sort：
// 排序算法示例
#include <iostream> // 标准输入/输出操作
#include <algorithm> // std::sort 函数
#include <vector> // std::vector 容器
// 比较两个整数以进行排序的函数
bool myfunction(int i, int j) { return (i < j); }
// 用于比较两个整数进行排序的仿函数结构体
struct myclass {
bool operator() (int i, int j) { return (i < j); }
} myobject;
int main() {
int myints[] = { 32,71,12,45,26,80,53,33 };
std::vector<int> myvector(myints, myints + 8); // 使用myints中的值初始化向量
// 使用默认比较函数（operator <）对前4个元素进行排序
std::sort(myvector.begin(), myvector.begin() + 4); // 结果: (12 32 45 71) 26 80 53 33
// 使用函数myfunction作为比较函数对剩余元素进行排序
std::sort(myvector.begin() + 4, myvector.end(), myfunction); // 结果: 12 32 45 71 (26 33 53 80)
// 使用对象myobject作为比较函数对整个向量进行排序
std::sort(myvector.begin(), myvector.end(), myobject); // 结果: (12 26 32 33 45 53 71 80)
// 打印向量的内容
std::cout << "myvector contains:";
for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
递归方式实现：
1. hoare版本：
// 参数：
// a: 指向待排序整数数组的指针
// left: 数组最左边元素的索引
// right: 数组最右边元素的索引
// 返回值：
// 分区后枢纽元素所在的索引
int QuickSortPart1(int* a, int left, int right)
{
// 找到枢纽元素并对数组进行分区
int mid = partion(a, left, right); // 假设partion函数在其他地方定义
// 将枢纽元素与最左边元素交换位置
Swap(&a[left], &a[mid]);
// 初始化用于分区的变量
int begin = left;
int end = right;
int key = begin;
// 执行分区操作
while (begin < end)
{
// 将'end'指针向左移动，直到找到比枢纽元素小的元素
while (begin < end && a[end] >= a[key])
end--;
// 将'begin'指针向右移动，直到找到比枢纽元素大的元素
while (begin < end && a[begin] <= a[key])
begin++;
// 交换'begin'和'end'指针指向的元素
Swap(&a[begin], &a[end]);
}
// 将枢纽元素放置到正确的位置
Swap(&a[begin], &a[key]);
return begin;
}
//一定注意是右边先走！！！【注意】
为什么相遇位置比key要小？
2. 挖坑法版本：
// 参数：
// a: 指向待排序整数数组的指针
// left: 数组最左边元素的索引
// right: 数组最右边元素的索引
// 返回值：
// 分区后枢纽元素所在的索引
int QuickSortPart2(int* a, int left, int right)
{
// 找到枢纽元素并对数组进行分区
int mid = partion(a, left, right); // 假设partion函数在其他地方定义
// 将枢纽元素与最左边元素交换位置
Swap(&a[left], &a[mid]);
// 保存枢纽元素的值
int key = a[left];
int hole = left;
// 执行分区操作
while (left < right)
{
// 将'right'指针向左移动，直到找到比枢纽元素小的元素
while (left < right && a[right] >= key)
right--;
// 将找到的元素放入之前枢纽元素的位置
a[hole] = a[right];
hole = right;
// 将'left'指针向右移动，直到找到比枢纽元素大的元素
while (left < right && a[left] <= key)
left++;
// 将找到的元素放入之前枢纽元素的位置
a[hole] = a[left];
hole = left;
}
// 将枢纽元素放置到正确的位置
a[hole] = key;
return hole;
}
3. 前后指针版本：
// 参数：
// a: 指向待排序整数数组的指针
// left: 数组最左边元素的索引
// right: 数组最右边元素的索引
// 返回值：
// 分区后枢纽元素所在的索引
int QuickSortPart3(int* a, int left, int right)
{
// 找到枢纽元素并对数组进行分区
int mid = partion(a, left, right); // 假设partion函数在其他地方定义
// 将枢纽元素与最左边元素交换位置
Swap(&a[left], &a[mid]);
// 初始化前后指针
int prev = left;
int cur = prev + 1;
int key = left;
// 执行分区操作
while (cur <= right)
{
// 如果当前元素小于枢纽元素，则交换当前元素和前指针指向的元素
if (a[cur] < a[key])
{
prev++;
Swap(&a[prev], &a[cur]);
cur++;
}
else
{
cur++;
}
}
// 将枢纽元素放置到正确的位置
Swap(&a[prev], &a[key]);
key = prev;
return key;
}
非递归方式实现（借助栈）：
// 参数：
// a: 指向待排序结构体数组的指针
// left: 数组最左边元素的索引
// right: 数组最右边元素的索引
// 返回值：
// 分区后枢纽元素所在的索引
int PartSort1(STDataType* a, int left, int right)
{
// 找到枢纽元素并对数组进行分区
int mid = GetMid(a, left, right);
// 将枢纽元素与最左边元素交换位置
Swap(&a[left], &a[mid]);
// 初始化起始和结束指针
int begin = left;
int end = right;
int key = begin;
// 执行分区操作
while (begin < end)
{
// 将'end'指针向左移动，直到找到比枢纽元素小的元素
while (begin < end && a[end] >= a[key])
end--;
// 将'begin'指针向右移动，直到找到比枢纽元素大的元素
while (begin < end && a[begin] <= a[key])
begin++;
// 交换找到的元素的位置
Swap(&a[begin], &a[end]);
}
// 将枢纽元素放置到正确的位置
Swap(&a[key], &a[begin]);
return begin;
}
// 参数：
// a: 指向待排序结构体数组的指针
// left: 数组最左边元素的索引
// right: 数组最右边元素的索引
void QuickSortNonR(STDataType* a, int left, int right)
{
Stack st;
StackInit(&st);
StackPush(&st, right);
StackPush(&st, left);
// 非递归快速排序
while (!StackEmpty(&st))
{
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
int key = PartSort1(a, begin, end);
// 将未排序部分压入栈中
if (key + 1 < end)
{
StackPush(&st, end);
StackPush(&st, key + 1);
}
if (key - 1 > begin)
{
StackPush(&st, key - 1);
StackPush(&st, begin);
}
}
StackDestroy(&st);
}
快速排序的特性总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
2.7 归并排序
https://en.wikipedia.org/wiki/Merge_sorthttps://en.wikipedia.org/wiki/Merge_sort
2.7.1 基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
2.7.2 归并排序的实现
递归方式实现：
/**
* @brief 归并排序算法的实现函数，使用递归的方式进行排序
*
* @param a 待排序数组的指针
* @param begin 子数组的起始位置
* @param end 子数组的结束位置
* @param temp 临时数组用于存放排序结果
*/
void _MergeSort(int* a, int begin, int end, int* temp)
{
if (begin >= end)
return;
// 计算中间位置
int mid = (begin + end) / 2;
// 递归调用_MergeSort对左右两个子数组进行排序
_MergeSort(a, begin, mid, temp);
_MergeSort(a, mid + 1, end, temp);
// 合并两个有序子数组
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int i = begin; // i表示临时数组的下标
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
temp[i] = a[begin1];
i++;
begin1++;
}
else
{
temp[i] = a[begin2];
i++;
begin2++;
}
}
// 处理剩余元素
while (begin1 <= end1)
{
temp[i] = a[begin1];
i++;
begin1++;
}
while (begin2 <= end2)
{
temp[i] = a[begin2];
i++;
begin2++;
}
// 将排序后的结果拷贝回原数组
memcpy(a + begin, temp + begin, sizeof(int) * ((end + 1) - begin));
}
/**
* @brief 归并排序算法的入口函数，分配临时数组并调用_MergeSort函数
*
* @param a 待排序数组的指针
* @param n 数组的大小
*/
void MergeSort(int* a, int n)
{
// 分配临时数组
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{
perror("malloc fail");
return;
}
// 调用_MergeSort函数对整个数组进行排序
_MergeSort(a, 0, n - 1, temp);
// 释放临时数组内存
free(temp);
}
*/非递归方式实现：
// 这个函数以迭代方式实现归并排序算法，而不使用递归
// 参数：
// a：要排序的整数数组
// n：数组中元素的数量
// 返回值：void
void MergeSortNonR(int* a, int n)
{
// 分配内存用于临时数组以存储排序后的元素
int* temp = (int*)malloc(sizeof(int) * n);
// 检查内存分配是否成功
if (temp == NULL)
{
printf("malloc失败");
return;
}
// 初始化要比较的元素之间的间隔
int gap = 1;
// 循环直到间隔小于元素数量
while (gap < n)
{
// 以当前间隔大小的增量遍历数组
for (int i = 0; i < n; i += (gap) * 2)
{
// 定义要合并的两个子数组的边界
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
// 检查边界是否超过数组大小
if (end1 >= n || begin2 >= n)
{
break;
}
// 如果结束边界超过数组大小，则调整它
if (end2 >= n)
{
end2 = n - 1;
}
// 打印正在合并的子数组的边界
// printf("[%2d,%2d][%2d,%2d]\n", begin1, end1, begin2, end2);
int j = begin1;
// 按顺序合并两个子数组
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
temp[j] = a[begin1];
j++;
begin1++;
}
else
{
temp[j] = a[begin2];
j++;
begin2++;
}
}
while (begin1 <= end1)
{
temp[j] = a[begin1];
j++;
begin1++;
}
while (begin2 <= end2)
{
temp[j] = a[begin2];
j++;
begin2++;
}
memcpy(a + i, temp + i, sizeof(int) * ((end2 - i) + 1));
}
gap *= 2;
}
}归并排序的特性总结：
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
2.8 计数排序
https://en.wikipedia.org/wiki/Counting_sorthttps://en.wikipedia.org/wiki/Counting_sort
2.8.1 基本思想
计数排序是一种根据小正整数键对对象集合进行排序的算法。也就是说，它是一种整数排序算法。它通过对拥有不同键值的对象数量进行计数，并对这些计数应用前缀和来确定每个键值在输出序列中的位置来进行操作
2.8.2 计数排序的实现
// 参数：
// a：要排序的整数数组
// n：数组中元素的数量
// 返回值：void
void CountSort(int* a, int n)
{
// 寻找数组中的最小值和最大值
int min = a[0];
int max = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] <= min)
{
min = a[i];
}
if (a[i] >= max)
{
max = a[i];
}
}
// 计算数值范围
int range = max - min + 1;
// 分配内存用于计数数组
int* count = (int*)calloc(range, sizeof(int));
// 检查内存分配是否成功
if (count == NULL)
{
printf("calloc失败");
return;
}
// 统计每个元素出现的次数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
// 将排序后的元素放回原数组
int i = 0;
for (int j = 0; j < range; j++)
{
while (count[j]--)
{
a[i++] = j + min;
}
}
}
计数排序的特性总结：
1. 时间复杂度：O(N+k) , 其中N为数组的长度，k为哈希表的长度
2. 空间复杂度：O(N+k), 需要用到一个哈希表和一个额外数组
3. 稳定性：稳定
3. 排序算法复杂度及稳定性分析
![洛谷 P8627 [蓝桥杯 2015 省 A] 饮料换购](https://img-blog.csdnimg.cn/direct/4c1388c4673c4f14855f5f6c863e8c87.png)
