計數(shù)排序
計數(shù)排序是一種非比較的排序算法
優(yōu)勢：
計數(shù)排序在對于一定范圍內(nèi)的整數(shù)排序時，時間復(fù)雜度為O(N+K) （K為整數(shù)在范圍）快于任何比較排序算法，因為基于比較的排序時間復(fù)雜度在理論上的上下限是O(N*log(N))。
缺點：
計數(shù)排序是一種犧牲空間換取時間的做法，并且當(dāng)K足夠大時O（K）>O(N*log(N)),效率反而不如比較的排序算法。并且只能用于對無符號整形排序。
時間復(fù)雜度：
O（N） K足夠大時為O（K）
空間復(fù)雜度：
O（最大數(shù)-最小數(shù)）
性能：
計數(shù)排序是一種穩(wěn)定排序
代碼實現(xiàn)：
#include <iostream> #include <Windows.h> #include <assert.h> using namespace std; //計數(shù)排序，適用于無符號整形 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; //要開辟的數(shù)組范圍 size_t* count = new size_t[range]; memset(count, 0, sizeof(size_t)*range); //初始化為0 //統(tǒng)計每個數(shù)出現(xiàn)的次數(shù) for (size_t i = 0; i < size; ++i) //從原數(shù)組中取數(shù)，原數(shù)組個數(shù)為size { count[a[i]-min]++; } //寫回到原數(shù)組 size_t index = 0; for (size_t i = 0; i < range; ++i) //從開辟的數(shù)組中讀取，開辟的數(shù)組大小為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; } 
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
