计数排序 原创 排序算法 2021年7月16日 07:13 夏至未至 1208 当前内容 1032 字，在路上，马上到，马上到 思想 计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。 计数排序对输入的数据有附加的限制条件： 1、输入的线性表的元素属于有限偏序集S； 2、设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。 在这两个条件下，计数排序的复杂性为O(n) 代码： ```cpp #pragma once //在范围中排序 void CountSortBetMaxAndMin(int *a, int min, int max,int size) { int gap = max - min + 1; int *temparray = new int[gap]; memset(temparray,0,sizeof(int)*(gap+1)); for (int count = 0; count < size; ++count) { temparray[a[count]]++; } //temparray是一个 int index = 0; for (int i = min; i < size; ++i) { while (temparray[i] != 0) { a[index++] = i; temparray[i]--; } } } //计数排序 void CountSort(int *a,int size) { //找一个范围 即就是数组的元素的最大和最小值 int max = a[0]; //最大 int min = a[0]; //最小 for (int i = 1; i < size; ++i) { if (a[i] > max) { max = a[i]; } else if (a[i] < min) { min = a[i]; } } //在这个范围中计数排序 CountSortBetMaxAndMin(a, min, max,size); } ``` 本文标题： 计数排序 本文作者： 夏至未至 发布时间： 2021年7月16日 07:13 最近更新： 2021年7月28日 07:02 原文链接： 许可协议： 署名-非商业性-禁止演绎 4.0 国际(CC BY-NC-ND 4.0) 请按协议转载并保留原文链接及作者 计数排序(1) 上一个 选择排序 下一个 直接插入排序 当前文章评论暂未开放,请移步至留言处留言。
