文章目录
- 1. 计数排序（CountSort）
- 1.1 核心思路
- 1.2 实现代码
- 2. 时间复杂度比较
1. 计数排序（CountSort）
1.1 核心思路
计数排序的核心思路是另外创建一个数组，记录原数组中出现的成员个数，再依次打印新数组中的成员个数。
以上述数组为例。已知数组中最小的数是1，最大的数是67.那么就需要开辟一个大小为max - min + 1的新数组。并且遍历原数组，将原数组成员的相应出现次数记录在新数组中。得到：
接着我们在遍历新数组，当新数组成员不等于0时，我们就打印相应的位置并且加上min。得到：
注意：由于计数排序需要另外开辟一个根据成员大小来决定大小的数组。所以计数排序的使用需要注意空间复杂度。当原数组的数据比较集中时，才推荐使用计数排序。
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);//开辟新数组countif (count == NULL)//count开辟失败就直接退出程序{perror("malloc fail!");exit(1);}memset(count, 0, sizeof(int) * range);//将新开辟的数组count的成员全部置于0for (int i = 0; i < n; i++){count[arr[i] - min]++;//已知数组的空间第一位是min，将arr[i] - min之后就是该成员在新数组的位置}int index = 0;for (int i = 0; i < range; i++)//将数组中全部的成员依次放回原数组{while (count[i]--)//count[i]表示该成员重复出现的次数{arr[index++] = i + min;//将排序完的数依次放回原数组中}}
}
2. 时间复杂度比较
根据时间复杂度来看，只推荐使用希尔排序，堆排序，快速排序，归并排序，计数排序。但是由于计数排序需要注意空间复杂度上面的问题，所以一般情况下，只推荐使用希尔，堆，快速，归并这四种排序方法。
另外关于“稳定性”，什么是稳定性？稳定性就是数组在排完序之后，原数组中成员的位置没有改变。例如：
上面的数组，将第一个出现的5定义为第一个5，第二个出现的5定义为第二个5，在排完序之后，应该是：
那么此时数组里的第一个5是不是刚才我们定义的第一个5呢？如果是，那么就可以说该排序方法具有稳定性；如果不是，则不具有稳定性。
以上就是所有的数组排序方法，可以根据具体的需求使用相应的排序方法。
