您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“C++中如何實(shí)現(xiàn)計(jì)數(shù)排序”的有關(guān)知識(shí),在實(shí)際案例的操作過(guò)程中,不少人都會(huì)遇到這樣的困境,接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
計(jì)數(shù)排序
計(jì)數(shù)排序是一種非比較的排序算法
優(yōu)勢(shì):
計(jì)數(shù)排序在對(duì)于一定范圍內(nèi)的整數(shù)排序時(shí),時(shí)間復(fù)雜度為O(N+K) (K為整數(shù)在范圍)快于任何比較排序算法,因?yàn)榛诒容^的排序時(shí)間復(fù)雜度在理論上的上下限是O(N*log(N))。
缺點(diǎn):
計(jì)數(shù)排序是一種犧牲空間換取時(shí)間的做法,并且當(dāng)K足夠大時(shí)O(K)>O(N*log(N)),效率反而不如比較的排序算法。并且只能用于對(duì)無(wú)符號(hào)整形排序。
時(shí)間復(fù)雜度:
O(N) K足夠大時(shí)為O(K)
空間復(fù)雜度:
O(最大數(shù)-最小數(shù))
性能:
計(jì)數(shù)排序是一種穩(wěn)定排序
代碼實(shí)現(xiàn):
#include <iostream> #include <Windows.h> #include <assert.h> using namespace std; //計(jì)數(shù)排序,適用于無(wú)符號(hào)整形 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; //要開(kāi)辟的數(shù)組范圍 size_t* count = new size_t[range]; memset(count, 0, sizeof(size_t)*range); //初始化為0 //統(tǒng)計(jì)每個(gè)數(shù)出現(xiàn)的次數(shù) for (size_t i = 0; i < size; ++i) //從原數(shù)組中取數(shù),原數(shù)組個(gè)數(shù)為size { count[a[i]-min]++; } //寫(xiě)回到原數(shù)組 size_t index = 0; for (size_t i = 0; i < range; ++i) //從開(kāi)辟的數(shù)組中讀取,開(kāi)辟的數(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; }
“C++中如何實(shí)現(xiàn)計(jì)數(shù)排序”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。