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; }