当前位置：首页 > news >正文

数据结构初阶（17）排序算法——非比较排序（计数排序·动图演示）、排序算法总结

news 2025/8/17 12:04:12

2.0 十大排序算法

2.5 非比较排序

之前学习的排序算法都是比较排序——借助比较大小，来实现排序。

非比较就是不借助比较大小，来实现排序。——小众的、局限的

非比较排序大致有这些：计数排序、桶排序、基数排序。

桶排序、基数排序在实践中意义不大，面试也基本上不会考。

计数排序在实践中有所应用、校招也会有涉及。

2.5.1 计数排序

基本思想

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

动图演示

算法步骤

1. 统计相同元素出现次数。

2. 根据统计的结果将序列回收到原来的序列中。

图解演示。

适合：数据上界、下界差值小(<1000) ——数据范围集中的数组。

即不管数据大小，只看数据集不集中。

不做绝对映射——即数据109不必要映射到数组的109位置，只需要做相对映射。

数组的大小=最大值-最小值+1——找最值：遍历一遍（还是要比较）。

负数不是问题：min=-5 ——则-5-(-5)=0还是没问题。

反映射：5 + min = 105。

核心思想不是通过比较来达到有序的，找最值还是需要比较——遍历一遍O(N)。

代码实现

//计数排序
void CountSort(int* a, int n)
{//找最值——假设修正法int min = a[0], max = a[0];for (int i = 1; i < n; i++){//如果有更大——就更新一下最大值if (a[i] > max)max = a[i];if (a[i] < min)min = a[i];}//O(N)//0.计算数据范围int range = max - min + 1;//1.开辟计数数组int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail");return;}memset(count, 0, sizeof(int) * range);//也可以在上面直接calloc——不过calloc的底层逻辑本来就是malloc + memset；//2.统计次数——遍历原数组——count数组相对位置处值++for (int i = 0; i < n; i++){// （1）统计次数的时候“减”min——“对应”下标位置的值++count[a[i] - min]++;}//3.排序——遍历count数组，将数据映射回原数组// i控制count遍历、j控制a遍历int j = 0;for (int i = 0; i < range; i++){//如果count对应位置不为0——为几走几次while (count[i]--)    //--k走k-1次；k--走k次{// 直接覆盖原数组// （2）还原的时候再把min“加”回来，用下标i加回min就是对应的a中的值a[j++] = i + min;}}
}

时间复杂度：arr数组大小N和count数组大小range当中，较大的那个。

O(N) 或者 O(range)；
或者直接O(N+range)；

显然当范围range和数据量在同一量级时，计数排序就是最优排序。——O(N)

测试——100万个数据（空间不大，大概不到1MB = 2^20 ≈ 10^6，整型就是4MB）

void TestOP()
{srand(time(0));//要产生随机需要一个种子，否则随机是写死的伪随机const int N = 1000000;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() % 100;a1[i] = rand() % N;                    //产生100个数据——大小都在100万以内//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 begin7 = clock();//BubbleSort(a7, N);int end7 = clock();//int begin3 = clock();//SelectSort(a3, N);//int end3 = clock();//ShellSort(a2, N);int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin4 = clock();HeapSort(a4, N);//QuickSort1(a2, 0, N - 1);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();//PrintArray(a4, N);int begin6 = clock();MergeSortNonR(a6, N);int end6 = clock();int begin3 = clock();CountSort(a6, N);int end3 = clock();//printf("InsertSort:%d\n", end1 - begin1);//printf("BubbleSort:%d\n", end7 - begin7);printf("ShellSort:%d\n", end2 - begin2);//printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);//printf("QuickSort1:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("CountSort:%d\n", end3 - begin3);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{//TestInsertSort();//TestBubbleSort();//TestShellSort();//TestSelectSort();//TestQuickSort();//TestMergeSort();//TestCountSort();TestOP();//MergeSortFile("sort.txt");return 0;
}

测试结果。