C++ 计数排序实例详解

概述计数排序            计数排序是一种非比较的排序算法

计数排序

             计数排序是一种非比较的排序算法

优势：

             计数排序在对于一定范围内的整数排序时，时间复杂度为O(N+K)  （K为整数在范围）快于任何比较排序算法，因为基于比较的排序时间复杂度在理论上的上下限是O(N*log(N))。

缺点：

             计数排序是一种牺牲空间换取时间的做法，并且当K足够大时O（K）>O(N*log(N)),效率反而不如比较的排序算法。并且只能用于对无符号整形排序。

时间复杂度：

            O（N）  K足够大时为O（K）

空间复杂度：

           O（最大数-最小数）

性能：

           计数排序是一种稳定排序

代码实现：

#include <iostream> #include <windows.h> #include <assert.h>  using namespace std;  //计数排序，适用于无符号整形 voID CountSort(int* a,size_t size) {   assert(a);   size_t max = a[0];   size_t min = a[0];   for (size_t i = 0; i < size; ++i)   {     if (a[i] > max)     {       max = a[i];     }     if (a[i] < min)     {       min = a[i];     }   }   size_t range = max - min + 1;   //要开辟的数组范围   size_t* count = new size_t[range];   memset(count,sizeof(size_t)*range);  //初始化为0   //统计每个数出现的次数   for (size_t i = 0; i < size; ++i)   //从原数组中取数，原数组个数为size   {     count[a[i]-min]++;   }   //写回到原数组   size_t index = 0;   for (size_t i = 0; i < range; ++i)  //从开辟的数组中读取，开辟的数组大小为range   {     while (count[i]--)     {       a[index++] = i + min;     }   }   delete[] count; }  voID Print(int* a,size_t size) {   for (size_t i = 0; i < size; ++i)   {     cout << a[i] << " ";   }   cout << endl; } 

#include "CountSort.h"  voID TestCountSort() {   int arr[] = { 1,2,3,4,5,6,8,9,11,22,12,12 };   size_t size = sizeof(arr) / sizeof(arr[0]);   CountSort(arr,size);   Print(arr,size); }  int main() {   TestCountSort();   system("pause");   return 0; } 

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

总结

以上是内存溢出为你收集整理的C++ 计数排序实例详解全部内容，希望文章能够帮你解决C++ 计数排序实例详解所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。