目录
八大排序算法
排序算法的稳定性
稳定性：在排序过程中，相等元素的相对顺序在排序前后保持不变。
也就是说，若在待排序序列里有两个元素a和b，它们的值相等，
且在排序前a位于b之前，那么排序后a依旧处于b之前。
比较排序
比较排序顾名思义就是通过元素之间的大小比较来排序的方法。
插入排序
插入排序：将待排序元素插入到有序序列中，从而得到一个新的有序序列。
实际生活中，我们玩扑克牌时就用到了插入排序的思想。
直接插入排序
用 end 记录有序序列的最后一个位置，tmp 保存待排序序列中的第一个元素，
结合插入排序的思想来排序。
void InsertSort(int* arr, int n)
{
for(int i = 0; i < n - 1; i++)
{
//i < n - 1是因为当end = n - 2时就是在将最后一个待排序元素插入到有序序列中
int end = i;//end用来记录有序序列的最后一个位置
int tmp = arr[end + 1];//tmp保存待排序序列中的第一个元素
//找待排元素应该插入的位置
//当end<0时，说明待排元素比有序序列的最小元素还要小
while(end >= 0)
{
if(arr[end] > tmp)//说明待排元素的位置在有序序列中该元素的前面
{
//把有序序列中该元素向后移，给待排元素的插入腾出位置
arr[end + 1] = arr[end];
//找有序序列中的前一个元素
end--;
}
else//说明已经找到了待排元素应该插入的位置，跳出循环
break;
}
//将待排元素插入到有序序列中
arr[end + 1] = tmp;
}
}
下面是直接插入排序图解
直接插入排序总结
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O（N^2）
- 空间复杂度：O（1）
- 稳定性：稳定
希尔排序
希尔排序（Shell Sort）是插入排序的一种改进版本，也被叫做缩小增量排序。
它的基本思路是通过一个初始增量gap（通常是gap = n / 3 + 1）将待排序列分
割成若干个子序列，分别对这些子序列进行直接插入排序；然后通过gap = gap / 3 + 1
使增量gap逐渐减小，子序列的长度逐渐增加，整个序列会变得越来越接近有序，
当增量gap减至1时，整个序列就被合并成一个，再进行一次直接插入排序，排序完成。
下面是希尔排序图解
void ShellSort(int* arr, int n)
{
int gap = n;
while(gap > 1)
{
gap = gap / 3 + 1;
//下面是直接插入排序的代码，只不过有小小的改变
//因为直接插入排序每次移动1步，而希尔排序每次移动gap步
for(int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = arr[end + gap];
while(end >= 0)
{
if(arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
break;
}
arr[end + gap] = tmp;
}
}
}
希尔排序总结
- 希尔排序是对直接插入排序的优化。
- 当gap>1时都是预排序，目的是让数组更接近有序。当gap == 1时，
数组已经很接近有序了，再进行直接插入排序会很快。- 时间复杂度：O(N^1.3)
- 空间复杂度：O(1)
- 稳定性：不稳定
希尔排序的时间复杂度计算
外层循环：while(gap > 1)
时间复杂度可以直接给出为：O(logN)
内层循环：
忽略+1的影响，gap = gap / 3
希尔排序时间复杂度不好计算，因为gap 的取值很多，导致很难去计算，因此很多书中给出的
希尔排序的时间复杂度都不固定。《数据结构(C语⾔版)》—严蔚敏书中给出的时间复杂度为：
选择排序
选择排序的基本思想：每一次从待排序列中选出最小（或最大）的一个元素，
存放在序列的起始位置，直到待排元素全部排完。
直接选择排序
- 设begin和end分别为待排序列的首尾位置，在待排序列arr[begin]~arr[end]中找最大和最小元素。
- 若最小和最大元素不是待排序列的首尾元素，就让最小和最大元素与待排序列的首尾元素交换。
- begin++，end–为下一次选择排序做准备，重复上述步骤。
//直接选择排序
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[i] > arr[maxi])
maxi = i;
if (arr[i] < arr[mini])
mini = i;
}
//让最小元素与首元素交换，最大元素与尾元素交换
//如果最大元素就是首元素的话，第一次交换会把最
//大元素交换到mini位置处，所以要让maxi = mini
if (maxi == begin)
maxi = mini;
Swap(&arr[begin], &arr[mini]);
Swap(&arr[end], &arr[maxi]);
//为下一次选择排序做准备
begin++;
end--;
}
}
下面是直接选择排序的图解
直接选择排序总结：
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
堆排序
堆排序（Heap Sort）是一种基于二叉堆数据结构的比较排序算法，其基本思想是先将
待排序的序列构建成一个最大堆（对于升序排序），然后将堆顶元素（最大值）与堆的
最后一个元素交换，接着将剩余的元素重新调整为最大堆，重复这个过程，直到整个序列有序。
//向下调整算法 O(logN)
void AdjustDown(int* arr, int n, int parent)
{
int child = parent * 2 + 1;//左孩子
while (child < n)
{
//小堆：<
//大堆：>
if (child + 1 < n && arr[child + 1] > arr[child])
child++;
//小堆：<
//大堆：>
if (arr[parent] > arr[child])
break;
//<=就交换了，所以稳定性：不稳定
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
}
//向上调整算法 O(logN)
void AdjustUp(int* arr, int child)
{
int parent = (child - 1) / 2;
while (parent >= 0)
{
//大堆：>
//小堆：<
if (arr[parent] > arr[child])
break;
Swap(&arr[parent], &arr[child]);
child = parent;
parent = (child - 1) / 2;
}
}
//堆排序
void HeapSort(int* arr, int n)
{
//升序 - 建大堆
//降序 - 建小堆
//建堆 - 向下调整法 O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
建堆 - 向上调整法 O(NlogN)
//for (int i = 1; i < n; i++)
//{
// AdjustUp(arr, i);
//}
//堆排序 O(NlogN)
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, end, 0);
end--;
}
}
堆排序总结：
时间复杂度：O(NlogN)
空间复杂度：O(1)
稳定性：不稳定
交换排序
交换排序基本思想：通过比较序列中元素的大小，根据比较结果
对元素位置进行交换操作，逐步让序列达到有序状态。
冒泡排序
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
int flag = 0;
for (int j = 0; j < n - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
Swap(&arr[j], &arr[j + 1]);
flag = 1;
}
}
if (flag == 0)
break;
}
}
冒泡排序总结：
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
快速排序
快速排序（Quick Sort）是一种高效的排序算法，它采用分治法（Divide and Conquer）策略。
基本思想是从待排序序列中挑选一个元素作为基准（pivot），然后将序列划分为两部分，
使得左边部分的所有元素都小于等于基准，右边部分的所有元素都大于等于基准，接着
分别对左右两部分递归地进行快速排序，最终得到一个有序序列。
递归
void QuickSort(int* arr, int left, int right)
{
//递归出口
if(left >= right)
return;
//接收一个基准值的位置
int pi = _QuickSort(arr, left, right);
//将序列划分成两部分：[left, pi-1] [pi+1, right]
//递归左右序列
QuickSort(arr, left, pi - 1);
QuickSort(arr, pi + 1, right);
}
_QuickSort有以下三个写法
hoare版本
hoare版本的基本思路
- 假定首元素为基准值，让left++
- 在[left,right]中，先从右向左找不大于基准值的值，再从左向右找不小于基准值的值，
找到后，进行交换，再让left++和right–。- 循环结束，交换基准值和right指向的值,使得左边部分的所有元素都小于等于基准值，
右边部分的所有元素都大于等于基准值。
int _QuickSort(int* arr, int left, int right)
{
//假设首元素是基准值，记录其位置
int pi = left;
//让left指向下一个元素的位置
left++;
while (left <= right)
{
//从右向左找不大于基准值的值
while (left <= right && arr[right] > arr[pi])
right--;
//从左向右找不小于基准值的值
while (left <= right && arr[left] < arr[pi])
left++;
//找到后，进行交换，更新left和right
if (left <= right)
Swap(&arr[left++], &arr[right--]);
}
//交换基准值和right指向的值
//使得左边部分的所有元素都小于等于基准，右边部分的所有元素都大于等于基准
Swap(&arr[pi], &arr[right]);
//返回基准值的下标
return right;
}
问题一：为什么循环的条件是 left<=right ?
问题二：为什么跳出循环时，交换基准值和right指向的值？
当left>right时，即right走到left的左侧，而left扫描过的数据均不大于基准值，
因此right指向的数据一定不大于基准值,且是序列中最右边的不大于基准值的元素。
挖坑法
挖坑法的基本思路
- 假设首元素是基准值，并保存基准值，“坑”的位置就是基准值的位置。
- 从右向左找比基准值小的值，将小于基准值的元素填入坑，保存新的“坑”的位置，
丛左向右找比基准值大的值，将大于基准值的元素填入坑，保存新的“坑”的位置。- 当left==right时，跳出循环，此时left和right都指向坑的位置，将基准值放入该位置。
int _QuickSort(int* arr, int left, int right)
{
//假设首元素是基准值，并保存基准值
int pivot = arr[left];
//“坑”的位置就是基准值的位置
int hole = left;
while (left < right)
{
//从右向左找比基准值小的值
while (left < right && arr[right] >= pivot)
right--;
//将小于基准值的元素填入坑
if (left < right)
{
arr[hole] = arr[right];
//保存新的“坑”的位置
hole = right;
}
//丛左向右找比基准值大的值
while (left < right && arr[left] <= pivot)
left++;
//将大于基准值的元素填入坑
if (left < right)
{
arr[hole] = arr[left];
//保存新的“坑”的位置
hole = left;
}
}
//当left==right时，跳出循环，此时left和right都指向坑的位置
//将基准值放入该位置，使得左边部分的所有元素都小于等于基准，
//右边部分的所有元素都大于等于基准
arr[hole] = pivot;
//返回基准值的位置
return hole;
}
lomuto前后指针
lomuto前后指针的基本思路
- 假设首元素是基准值，记录其位置
- 创建前后指针prev和cur
- 从左向右找比基准值小的进行交换，使得小的都在基准值左边
- 交换基准值和prev指向的值
int _QuickSort(int* arr, int left, int right)
{
//假设首元素是基准值，记录其位置
int pi = left;
//创建前后指针prev和cur
int prev = left, cur = left + 1;
//只有cur遍历完数组才会出循环
while (cur <= right)
{
//从左向右找比基准值小的进行交换，使得小的都在基准值左边
if (arr[cur] < arr[pi] && ++prev != cur)
Swap(&arr[cur], &arr[prev]);
cur++;
}
//交换基准值和prev指向的值
//使得左边部分的所有元素都小于基准，右边部分的所有元素都大于等于基准
Swap(&arr[pi], &arr[prev]);
//返回基准值的下标
return prev;
}
快速排序总结：
- 时间复杂度：O(NlogN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
三路划分
//快排之三路划分 - 适合数据中有大量的重复值的情况
void QuickSort2(int* arr, int left, int right)
{
//递归出口
if (left >= right)
return;
//1.pivot默认取left的值
//2.left指向区间最左边，right指向区间最右边，cur指向left+1位置
//3.cur遇到比pivot小的值后跟left位置交换，换到左边，left++，cur++
//4.cur遇到比pivot大的值后跟right位置交换，换到右边，right--
//5.cur遇到跟pivot相等的值后，cur++
//6.直到cur>right结束
//随机选择基准值pivot - 主函数加srand(time(0));
int randi = left + (rand() % (right - left + 1));
Swap(&arr[left], &arr[randi]);
int begin = left, end = right;
int pivot = arr[left];
int cur = left + 1;
while (cur <= right)
{
if (arr[cur] < pivot)
Swap(&arr[left++], &arr[cur++]);
else if (arr[cur] > pivot)
Swap(&arr[right--], &arr[cur]);
else
cur++;
}
//[begin,left-1] [left,right] [right+1,end]
QuickSort(arr, begin, left - 1);
QuickSort(arr, right + 1, end);
}
自省排序
//快排之自省排序 - 基本能解决所有情况
void IntroSort(int* arr, int left, int right, int depth, int defaultDepth)
{
//递归出口
if (left >= right)
return;
//数组长度小于16的小数组，换为直接插入排序
if (right - left + 1 < 16)
{
InsertSort(arr + left, right - left + 1);
return;
}
//递归深度大于defaultDepth,改为堆排序
if (depth > defaultDepth)
{
HeapSort(arr + left, right - left + 1);
return;
}
depth++;
//随机选择基准值pivot - 主函数加srand(time(0));
int randi = left + (rand() % (right - left + 1));
Swap(&arr[left], &arr[randi]);
//lomuto前后指针
int pi = left;
int prev = left, cur = left + 1;
while (cur <= right)
{
if (arr[pi] > arr[cur] && ++prev != cur)
Swap(&arr[prev], &arr[cur]);
cur++;
}
Swap(&arr[pi], &arr[prev]);
pi = prev;
//[left, pi - 1] [pi + i, right]
IntroSort(arr, left, pi - 1, depth, defaultDepth);
IntroSort(arr, pi + 1, right, depth, defaultDepth);
}
void QuickSort(int* arr, int left, int right)
{
int depth = 0;//递归深度
int logn = 0;//递归太深需返回深度
int N = right - left + 1;
for (int i = 1; i < N; i *= 2)
{
logn++;
}
// introspective sort -- 自省排序
IntroSort(arr, left, right, depth, 2 * logn);
}
非递归
非递归版本的快速排序需要借助数据结构：栈
void QuickSortNonR(int* arr, int left, int right)
{
//借助数据结构 - 栈
//创建栈
ST st;
//初始化
STInit(&st);
//让首尾元素下标入栈，注意入栈和出栈顺序
STPush(&st, right);
STPush(&st, left);
//栈非空进循环
while (STSize(&st))
{
//保存首尾元素下标
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
//利用lomuto前后指针思想
int pi = begin;
int prev = begin, cur = begin + 1;
while (cur <= end)
{
if (arr[cur] < arr[pi] && ++prev != cur)
Swap(&arr[cur], &arr[prev]);
cur++;
}
Swap(&arr[prev], &arr[pi]);
//更新基准值的位置
pi = prev;
//为下一次排序排序做准备
//[begin, pi - 1] pi [pi + 1, end]
if (begin < pi - 1)
{
STPush(&st, pi - 1);
STPush(&st, begin);
}
if (pi + 1 < end)
{
STPush(&st, end);
STPush(&st, pi + 1);
}
}
//销毁
STDestroy(&st);
}
归并排序
递归
归并排序（Merge Sort）是一种采用分治法（Divide and Conquer）的经典排序算法。
它的基本思想是将一个大问题分解为多个小问题，分别解决这些小问题，最后将小问题
的解合并起来得到原问题的解。具体来说，归并排序将一个数组分成两个子数组，分别
对这两个子数组进行排序，然后将排好序的子数组合并成一个最终的有序数组。
下面是归并排序图解
void _MergeSort(int* arr, int left, int right, int* tmp)
{
//1.分解
//递归出口
if (left >= right)
return;
int mid = left + (right - left) / 2;
//递归分解左右序列：[left, mid] [mid+1, right]
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
//2.合并
//合并左右两个有序序列
//为了防止合并时覆盖有效数据，需要一个临时数组tmp
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
//[begin1, end1] [begin2, end2]
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
tmp[index++] = arr[begin1++];
else
tmp[index++] = arr[begin2++];
}
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//3.将tmp中有序的数据导入到原数组中
//[left, right]
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}
void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
exit(1);
}
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}
归并排序总结：
- 时间复杂度：O(NlogN)
- 空间复杂度：O(N)
- 稳定性：稳定
非递归
//归并排序 - 非递归
void MergeSortNonR(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
while (gap < n)
{
//根据gap划分左右序列
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
int index = begin1;
//越界处理
if (begin2 >= n)
break;
if (end2 >= n)
end2 = n - 1;
//合并左右有序序列
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
tmp[index++] = arr[begin1++];
else
tmp[index++] = arr[begin2++];
}
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//将tmp中的有序序列导入到原数组arr中
memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
文件归并排序
//文件归并排序
//创建N个随机数，写到文件中
void CreateNDate()
{
//造数据
int n = (int)1e6;
srand((size_t)time(NULL));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; i++)
{
int x = rand() + i;
fprintf(fin, "%d\n", x);
}
fclose(fin);
fin = NULL;
}
//比较函数
int compare(const void* e1, const void* e2)
{
return (*(int*)e1 - *(int*)e2);
}
//返回实际读到的数据个数，没有数据了，返回0
int ReadNDataSortToFile(FILE* fout, int n, const char* file)
{
int x = 0;
int* a = (int*)malloc(sizeof(int) * n);
if (a == NULL)
{
perror("malloc error");
return 1;
}
//想读取n个数据，如果遇到文件结束，应该读到j个
int j = 0;
for (int i = 0; i < n; i++)
{
if (fscanf(fout, "%d", &x) == EOF)
break;
a[j++] = x;
}
if (j == 0)
{
free(a);
return 0;
}
//排序
qsort(a, j, sizeof(int), compare);
//将读取到并排好序的有序序列写入file
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
free(a);
perror("fopen error");
return 1;
}
for (int i = 0; i < j; i++)
{
fprintf(fin, "%d\n", a[i]);
}
free(a);
fclose(fin);
fin = NULL;
return j;
}
//文件归并排序
void MergeFile(const char* file1, const char* file2, const char* mfile)
{
FILE* fout1 = fopen(file1, "r");
if (file1 == NULL)
{
perror("fopen error");
return;
}
FILE* fout2 = fopen(file2, "r");
if (fout2 == NULL)
{
perror("fopen error");
return;
}
FILE* mfin = fopen(mfile, "w");
if (mfin == NULL)
{
perror("fopen error");
return;
}
//归并逻辑
int x1, x2;
int ret1 = fscanf(fout1, "%d", &x1);
int ret2 = fscanf(fout2, "%d", &x2);
while (ret1 != EOF && ret2 != EOF)
{
if (x1 < x2)
{
fprintf(mfin, "%d\n", x1);
ret1 = fscanf(fout1, "%d", &x1);
}
else
{
fprintf(mfin, "%d\n", x2);
ret2 = fscanf(fout2, "%d", &x2);
}
}
while (ret1 != EOF)
{
fprintf(mfin, "%d\n", x1);
ret1 = fscanf(fout1, "%d", &x1);
}
while (ret2 != EOF)
{
fprintf(mfin, "%d\n", x2);
ret2 = fscanf(fout2, "%d", &x2);
}
fclose(fout1);
fclose(fout2);
fclose(mfin);
fout1 = fout2 = mfin = NULL;
}
int main()
{
CreateNDate();
const char* file1 = "file1.txt";
const char* file2 = "file2.txt";
const char* mfile = "mfile.txt";
FILE* fout = fopen("data.txt", "r");
if (fout == NULL)
{
perror("fopen error");
return;
}
int m = (int)1e5;
ReadNDataSortToFile(fout, m, file1);
ReadNDataSortToFile(fout, m, file2);
while (1)
{
//排序file1和file2
MergeFile(file1, file2, mfile);
//删除file1和file2
remove(file1);
remove(file2);
//重命名mfile为file1
rename(mfile, file1);
//当再去读取数据，一个都读不到，说明已经没有数据了
//已经归并完成，归并结果在file1
if (ReadNDataSortToFile(fout, m, file2) == 0)
break;
}
fclose(fout);
fout = NULL;
return 0;
}
排序性能对比
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);
int* a7 = (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];
a7[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();
int begin7 = clock();
BubbleSort(a7, N);
int end7 = 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);
printf("BubbleSort:%d\n", end7 - begin7);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
非比较排序
非比较排序不需要通过元素之间的大小比较来排序。
计数排序
计数排序又称为鸽巢原理，其核心思想是通过统计每个元素在序列中出现的次数，
进而确定每个元素在排序后序列中的位置。该算法适用于整数序列，且当待排序元素
的值范围较小时，计数排序的效率较高。
void CountSort(int* arr, int n)
{
//找arr数组中的最大值和最小值，用来确定申请的新数组的空间大小
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];
}
//所以新数组的大小为range
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail");
return;
}
memset(count, 0, range * sizeof(int));//初始化为0
//统计原数组中每个元素出现的次数
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
//排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[j++] = i + min;
}
}
}
计数排序总结：
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(N + range)
- 空间复杂度：O(range)
- 稳定性：稳定
比较排序算法总结
