C++ 计数排序实例详解

2020-01-26 14:02:00

字体：大中小

来源：转载

供稿：网友

计数排序

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

优势：

计数排序在对于一定范围内的整数排序时，时间复杂度为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, 0, 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, 6, 6, 6, 6, 6, 6, 6, 6, 2, 2, 2, 4, 5, 8, 9, 5, 11, 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; }