初阶数据结构之计数排序
非比较排序
计数排序
计数排序⼜称为鸽巢原理,是对哈希直接定址法的变形应⽤。
操作步骤:
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
注意:
希尔排序不稳定是在于分组
归并排序不稳定是因为找基准值
排序的相关内容先更新到这里告一段落喽! 希望大家有所收获!