目录

1. 比较排序和非比较排序

2. 计数排序的原理

2.1 计数排序的弊端

3.代码复现

3.1 代码分析

3.2 排序核心

3.3 时间、空间复杂度

---

1. 比较排序和非比较排序

        比较排序是根据排序元素的具体数值比较来进行排序；非比较排序则相反，非比较排序例如：基数排序和计数排序，这两种排序方式虽然谐音类似，但是其实是完全不同的两种排序。

        首先基数排序是根据一个数字的某一位进行排序；而计数排序是根据某一个数字出现的次数来进行比较排序。

2. 计数排序的原理

①需要判断出整个原数组中最大的数字，例如是5，那么就需要创建一个0-5的数组（元素为6个）。

②新创建的数组的下标表示该数字的值，该数组的下标所对应的值就类似于该数字出现了几次。

③遍历原始数组，如果遍历到某一个数字，那么新数组的对应位置的值就会+1；

④遍历完毕之后，对统计次数的数组进行排序即可；

⑤排序的过程也非常巧妙，首先0下标的值是2，说明0出现了2次，1下标的值是0，说明没有1,2下标的值是2说明有两个2......我们直接对原数组进行覆盖即可。

2.1 计数排序的弊端

        例如需要将下面几个数进行计数排序，按照上面的原理，我们需要开辟一个0-5000（5001个数组元素）的数组，但是需要排序的数只有仅仅5个，这样一来，大量的数组空间会被浪费。

        从下图得知，最小的数是1000，也就是说0-1000这1000个数就没有必要为其准备空间了，所以只需要准备4000个空间就够了。

        此时数的存储是一个相对位置，例如1000存在数组下标为0的位置上，1005存在数组下标为5的位置上，1100存储在数组下标为100的位置上......5000存在数组下标为4000，计算方式a[i] - min，当前位置-最小值。

        所以说，比较稀疏的数进行排序的话，那么就会浪费大量连续空间。

3.代码复现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>// 计数排序
void count_sort(int* arr, int size)
{// 选出最大值和最小值int max = arr[0];int min = arr[0];for (int i = 0; i < size; i++){if (arr[i] > max){max = arr[i];}if (arr[i] < min){min = arr[i];}}// 创建一个具体数量的数组int range = max - min + 1;// 0-9一共10个数int* countArr = (int*)malloc(sizeof(int) * range);memset(countArr, 0, range * sizeof(int));// 遍历原数组给countArr赋值,计数for (int i = 0; i < size; i++)// countArr下标是arr的值;其值是次数{int val = arr[i] - min; // 这里是相对位置，若只有0-4000个位置，1005就是5号位置,// 这里要arr[i] - min得到相对位置++countArr[val];}int index = 0;// 原数组的覆盖下标// 遍历countArr将原数组覆盖for (int j = 0; j < range; j++){// 计数数组的值是几就覆盖几次while (countArr[j]--){arr[index++] = j + min; // 将下标进行还原，之前是-min存入countArr的 }}free(countArr);
}int main()
{int a[] = { 3,5,4,1,7,9,8,5,0,5 };int size = sizeof(a) / sizeof(int);count_sort(a, size);for (int i = 0; i < size; i++){printf("%d ", a[i]);}return 0;
}

3.1 代码分析

①首先计算出原数组的最大最小值，最大值-最小值+1就是计数数组的长度。

②遍历原数组，原数组的值对应计数数组的下标，如果遍历到2，那么就是计数数组下标为2的值进行+1；

③遍历计数数组，将对应下标作为原数组的值，计数数组的值就是需要赋值的次数，例如上图的5，在计数数组中存储的方式是index = 5,val = 3，那么就是将5赋值原数组，赋值3次，结果如下图。

3.2 排序核心

        就是利用数组的下标将无序的数字分别放入对应的下标，从而实现有序，这里对于重复数字进行一个累加的过程，反作用于原数组就是赋值的次数，这样的排序类似于下图：

        利用连续的有序数组下标作为“柱子”，如果该数字为这个柱子的编号，那么这个柱子就套一个圈，每一个柱子套圈的个数其实就是该数字出现的次数，由于柱子的编号是连续且有序，其实在套圈的过程中，我们已经将数字排好序了，此时只需要将结果覆盖原数组即可。

        所以这个算法可以运用于，数据非常集中，有大量重复出现的数字的数组中。

3.3 时间、空间复杂度

        我们注意这里的时间复杂度，看代码我们可以发现遍历了一次原数组，这里时间复杂度是O(n)，后面需要遍历计数数组，那么时间复杂度是O（range）,那么最后的时间复杂度就是：

空间复杂度，这里只需要一个range大的数组，所以这里是：

(不是橘子哈)