目录
排序的概念及运用
常见的运用
衡量排序标准
时间空间复杂度
辅助空间：有些排序算法在排序过程中需要额外的空间来辅助排序，例如归并排序和快速排序。这些算法的辅助空间通常为O(n)，而有些算法如插入排序和冒泡排序的辅助空间为O(1)。
稳定性：稳定性是指在排序过程中，相等键值的元素在原始序列中的相对位置是否保持不变。稳定排序算法会维持相等元素的相对次序，而不稳定排序算法则可能改变这些元素的相对次序。
特殊情况下性能：某些排序算法在特定情况下可能表现得更优，例如当数据已经部分有序时，插入排序和冒泡排序可能会更快。而快速排序在这种情况下可能会变慢。
常见排序的实现算法
插入排序
直接插入排序
代码实现
//直接插入排序
void InsertSort(int* arr, int n)
{
//i最后一次是n-2，对应数组中倒数第二个数字
for (int i = 0; i < n - 1; i++)
{
int end = i;//end从0开始
int tmp = arr[end + 1];//有序区间的后一个数字
while (end >= 0)
{
//比较
if (arr[end] > tmp)//end位置的数据大于tmp，那么tmp往前走
{
arr[end + 1] = arr[end];//将end位置的数据往后挪
end--;
}
else//end位置的数小于tmp位置的，我们就跳出循环
{
break;
}
}
//此时的end就小于0，跳出循环
arr[end + 1] = tmp;
}
}复杂度
最佳情况：如果输入数组已经是完全有序的，插入排序只需要进行 n 次比较（每次比较后插入一个元素到已排序部分），而不需要进行任何交换。在这种情况下，时间复杂度是 O(n)。
平均情况：在平均情况下，插入排序的时间复杂度是 O(n^2)。这是因为每个元素都需要与已排序部分的多个元素进行比较，平均下来，每个元素需要比较 n/2 次。
最坏情况：如果输入数组是完全逆序的，插入排序需要进行 n(n-1)/2 次比较和 n(n-1)/2 次交换，时间复杂度是 O(n^2)
希尔排序
希尔排序是一种基于插入排序的算法，它通过引入增量序列，采取分组排序策略：将大数组分为若干个子序列，对每个子序列进行插入排序。随着增量逐渐减小，子序列变得更小，最终达到增量为1，整个数组变成一个有序序列，完成排序。这种排序方式使得希尔排序在初始阶段，使用较大的步长让序列更快时间的接近有序，并且减少了不必要的比较与交换。
※希尔排序是对直接插入排序的优化
代码实现
//希尔排序
void ShellSort(int* arr, int n)
{
int gap = n;
//控制gap的变化
while (gap > 1)
{
//保证gap最后一次指定是一
gap = gap / 3 + 1;
for (int i = 0; i < n-gap; i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
//tmp小，小的就要往前面放
if (arr[end] > tmp)
{
//将end这个位置的数挪到end + gap这个位置
arr[end + gap] = arr[end];
end-=gap;
}
//tmp对应的数大于end对应的数，对于跳出循环的代码我们是相当于tmp是不动的
else
{
break;
}
}
//跳出循环之后tmp应该放在end+gap这个位置
arr[end+gap] = tmp;
}
}
}复杂度
最佳情况：在最佳情况下，当间隔序列满足特定条件时，希尔排序可以达到接近 O(n) 的时间复杂度。
平均情况：平均时间复杂度通常被认为是介于 O(n log n) 和 O(n^2) 之间，具体取决于所选择的间隔序列，我认为大概为O(n^1.3)。
最坏情况：在最坏情况下，希尔排序的时间复杂度为 O(n^2)。
选择排序
直接选择排序
在元素集合 array[i]--array[n-1] 中选择关键码最大(小)的数据元素。
若它不是这组元素中的最后⼀个(第⼀个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素交换。
在剩余的 array[i]--array[n-2]（array[i+1]--array[n-1]） 集合中，重复上述步骤，直到集合剩余 1 个元素。
代码实现
//直接选择排序
void SelectSort(int* arr, int n)
{
//指向第一个数据
int begin = 0;
//指向第二个数据
int end = n - 1;
//当begin=end的时候就调整完整个数组了
while (begin < end)
{
int maxi = begin, mini = begin;
for (int i = begin + 1; i <=end; i++)
{
//找最大的值
if (arr[maxi] < arr[i])
{
maxi = i;
}
//找最小的值
if (arr[mini] > arr[i])
{
mini = i;
}
}
//避免maxi begini都在同一个位置，begin和mini交换之后，maxi数据变成了最小的数据
if (maxi == begin)
{
maxi = mini;
}
Swap(&arr[maxi], &arr[end]);
Swap(&arr[mini],&arr[begin]);
++begin;
--end;
}
}复杂度
时间复杂度：O(n^2)
是排序中最差的。
堆排序
堆排序是一种有效的排序算法，它利用了完全二叉树的特性。在C语言中，堆排序通常通过构建一个最大堆（或最小堆），然后逐步调整堆结构，最终实现排序。
代码实现
//堆排序
void HeapSort(int* arr, int n)
{
//建堆
//向下调整算法建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, i, n);
}
//排序
//循环将堆顶数据跟最后位置（会变化，每次减少一个数据）的数据进行交换
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end);
end--;
}
}堆排序使用时需要的向下调整算法AdjustDown
//堆的向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{
//左孩子
int child = parent * 2 + 1;
//不能child++越界
while (child < n)
{
//左右孩子比较找出小的
if (child + 1 < n && arr[child] > arr[child + 1])
{
child++;
}
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
复杂度
最佳情况：在最佳情况下，堆排序的时间复杂度为 O(nlogn) 。
平均情况：平均时间复杂度下，堆排序的时间复杂度为 O(nlogn)。
最坏情况：在最坏情况下，堆排序的时间复杂度为O(nlogn)。
交换排序
冒泡排序
代码实现
//冒泡排序
void BubbleSort(int* arr, int n)//数组以及数组中的有效数据个数
{
for (int i = 0; i < n; i++)
{
int exchange = 0;
for (int j = 0; j < n - i - 1; j++)
{
//<就是降序
if (arr[j] < arr[j + 1])//大的在后面，那么我们就进行交换
{
exchange = 1;
Swap(&arr[j], &arr[j + 1]);
}
}
if (exchange == 0)
{
//那么就说明我们经历了一趟内循环，我们的exchange并没有改变，就说明这个数组可能之前就是有序的
break;
}
}
}复杂度
最佳情况：在最佳情况下，冒泡排序的时间复杂度为 O(n) 。
平均情况：平均时间复杂度下，冒泡排序的时间复杂度为 O(n^2)。
最坏情况：在最坏情况下，冒泡排序的时间复杂度为 O(n^2)。
快速排序
快速排序（Quick Sort）是一种高效的排序算法，它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序的目的。在C语言中，快速排序的实现通常涉及到递归函数的编写，以及对数组进行分区（partition）操作。
hoare版本
在这里我们是要，定义一个关键字（keyi）进行分区，然后分别向左右进行递归。
代码实现
// hoare版本
int _QuickSort(int* arr, int left, int right)
{
int keyi = left;
++left;
while (left <= right)
{
//用right找比keyi小的值，找不到往回走
while (left <= right && arr[right] > arr[keyi])
{
right--;
}
//用left找比keyi大的值，找不到往下走
while (left <= right && arr[left] < arr[keyi])
{
left++;
}
//都找到对应的大小值，交换，往下走
if (left <= right)
{
Swap(&arr[left++],&arr[right--]);
}
}
//right,keyi交换
Swap(&arr[right], &arr[keyi]);
return right;
}挖坑法
挖坑法类似于霍尔方法，挖坑就是记住关键字，保证关键字就是一个坑位，比关键字值小（大）的时候就入坑位，此时，这个值位置作为新的坑位直至两个前后指针指向同一个坑位。
代码实现
//挖坑法
int _QuickSort(int* arr, int left, int right)
{
int hole = left;
//key储存hole位置的值
int key = arr[hole];
while (left < right)
{
//用right找比key小的值，找不到往回走
while (left <right && arr[right]>key)
{
--right;
}
//找到了hole的值就是right的值
arr[hole] = arr[right];
//hole就到right位置上
hole = right;
//用left找比key大的值，找不到往下走
while (left < right && arr[left] < key)
{
++left;
}
//找到了hole的值就是left的值
arr[hole] = arr[left];
//hole就到left位置上
hole = left;
}
//最后hole的值变成了key
arr[hole] = key;
return hole;
}lomuto前后指针
prev 指针初始化为数组的开始位置，cur 指针初始化为 prev 的下一位置。
cur 指针向前遍历数组，寻找小于或等于基准值的元素，而 prev 指针则跟随 cur 指针的移动，直到 cur 找到一个小于基准值的元素。
一旦找到这样的元素，prev 和 cur 指针之间的元素都会被交换，然后 cur 指针继续向前移动，直到找到下一个小于基准值的元素，或者到达数组的末尾。最后，基准值会被放置在 prev 指针当前的位置，完成一次排序
代码实现
//lomuto前后指针法
int _QuickSort(int* arr, int left, int right)
{
int prev = left, cur = left + 1;
int keyi = left;
//当我们的cur越界了我们就不进行循环
while (cur <= right)
{
//两个指针相等的话，那么我们就不进行交换
if (arr[cur] < arr[keyi] && ++prev != cur)
{
//只要cur找到小的，就让prve++然后进行交换
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
//cur越界了
//将之前定义的基准值和现在prev指向的值进行交换
Swap(&arr[keyi], &arr[prev]);
return prev;
}非递归版本
那么非递归的快速排序的需要借助数据结构：栈
代码实现
//非递归版本快排
void QuickSortNonR(int* arr, int left, int right)
{
ST st;
STInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
//取栈顶元素---取两次
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
//[begin,end]---找基准值
int prev = begin;
int cur = begin + 1;
int keyi = begin;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
//根据基准值划分左右区间
//左区间：[begin,keyi-1]
//右区间：[keyi+1,end]
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (keyi - 1 > begin)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
STDestroy(&st);
}复杂度
快拍的所以时间复杂度：O(logn)。
归并排序
归并排序（MERGE-SORT）是建立在归并操作上的⼀种有效的排序算法,该算法是采用分治法（Divideand Conquer）的⼀个非常典型的应⽤。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。
代码实现
//归并排序
void _MergeSort(int* arr,int left,int right,int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
//[left,mid] [mid+1,right]
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
//合并
//[left,mid] [mid+1,right]
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else {
tmp[index++] = arr[begin2++];
}
}
//要么begin1越界但begin2没有越界 要么begin2越界但begin1没有越界
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//[left,mid] [mid+1,right]
//把tmp中的数据拷贝回arr中
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}
void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}复杂度
归并排序的时间复杂度：O(nlogn)。
归并排序的空间复杂度:O(n)。
非比较排序
计数排序
计数排序右称为鸽巢原理，是对哈希直接定址法的变形应用。
操作步骤：
(1）统计相同元素出现次数
(2）根据统计的结果将序列回收到原来的序列中
代码实现
//计数排序
void CountSort(int* arr, int n)
{
//根据最大值最小值确定数组大小
int max = arr[0], min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail!");
exit(1);
}
//初始化range数组中所有的数据为0
memset(count, 0, range * sizeof(int));
//统计数组中每个数据出现的次数
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
//取count中的数据，往arr中放
int index = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[index++] = i + min;
}
}
}复杂度
计数排序时间复杂度：O(n+range) 。计数排序空间复杂度：O(range) 。
总结
