初阶数据结构之计数排序

非比较排序

计数排序

计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤。
操作步骤：
1）统计相同元素出现次数
2）根据统计的结果将序列回收到原来的序列中

#include "CountSort.h"
void Count(int* arr, int n)
{//根据最大值和最小值确定数组范围int max = arr[0];int min = arr[0];for (int i = 0; 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数组中所有数据为0memset(count, 0, range * sizeof(int));//统计数组中每个数据出现的次数for (int i = 0; i < n; i++){count[arr[i] - min]++;}//给数组元素初始化int index = 0;for (int i = 0; i < range; i++){//取count中的数据往arr中放while (count[i]--){arr[index++] = i + min;}}}

计数排序的特性：
计数排序在数据范围集中时，效率很⾼，但是适⽤范围及场景有限。
时间复杂度： O(N + range)
空间复杂度： O(range)
稳定性：稳定
注意点：
时间复杂度主要是因为count数组会出现里面元素0的情况

排序算法复杂度及稳定性分析

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
Q:怎样理解稳定性？
A:通俗点来说就是 ，举一个例子，2，1，3，4，2 稳定的情况是排完序后相同的数字前后顺序一致，不稳定则相反


稳定性验证案例
直接选择排序：5 8 5 2 9
希尔排序：5 8 2 5 9
堆排序：2 2 2 2
快速排序：5 3 3 4 3 8 9 10 11

注意：
希尔排序不稳定是在于分组
归并排序不稳定是因为找基准值

排序的相关内容先更新到这里告一段落喽！ 希望大家有所收获！