詳解計(jì)數(shù)排序算法及C語(yǔ)言程序中的實(shí)現(xiàn)
關(guān)于計(jì)數(shù)排序算法
當(dāng)輸入的元素是 n 個(gè) 0 到 k 之間的整數(shù)時(shí)，它的運(yùn)行時(shí)間是 Θ(n + k)。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。
由于用來(lái)計(jì)數(shù)的數(shù)組C的長(zhǎng)度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量?jī)?nèi)存。計(jì)數(shù)排序是用來(lái)排序0到100之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。但是，計(jì)數(shù)排序可以用在基數(shù)排序中的算法來(lái)排序數(shù)據(jù)范圍很大的數(shù)組。
算法的步驟如下：
- 找出待排序的數(shù)組中最大和最小的元素
- 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
- 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加）
- 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1
代碼示例：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
void CountingSort(int *A,int *B,int *Order,int N,int K)
{
int *C=new int[K+1];
int i;
memset(C,0,sizeof(int)*(K+1));
for (i=1;i<=N;i++) //把A中的每個(gè)元素分配
C[A[i]]++;
for (i=2;i<=K;i++) //統(tǒng)計(jì)不大于i的元素的個(gè)數(shù)
C[i]+=C[i-1];
for (i=N;i>=1;i--)
{
B[C[A[i]]]=A[i]; //按照統(tǒng)計(jì)的位置，將值輸出到B中，將順序輸出到Order中
Order[C[A[i]]]=i;
C[A[i]]--;
}
}
int main()
{
int *A,*B,*Order,N=15,K=10,i;
A=new int[N+1];
B=new int[N+1];
Order=new int[N+1];
for (i=1;i<=N;i++)
A[i]=rand()%K+1; //生成1..K的隨機(jī)數(shù)
printf("Before CS:\n");
for (i=1;i<=N;i++)
printf("%d ",A[i]);
CountingSort(A,B,Order,N,K);
printf("\nAfter CS:\n");
for (i=1;i<=N;i++)
printf("%d ",B[i]);
printf("\nOrder:\n");
for (i=1;i<=N;i++)
printf("%d ",Order[i]);
return 0;
}
相關(guān)文章
C++實(shí)現(xiàn)簡(jiǎn)單的希爾排序Shell Sort實(shí)例
這篇文章主要介紹了C++實(shí)現(xiàn)簡(jiǎn)單的希爾排序Shell Sort實(shí)例,對(duì)于正在學(xué)習(xí)算法的朋友很有借鑒價(jià)值,需要的朋友可以參考下2014-07-07
C/C++實(shí)現(xiàn)發(fā)送與接收HTTP/S請(qǐng)求的示例代碼
HTTP（Hypertext Transfer Protocol）是一種用于傳輸超文本的協(xié)議,它是一種無(wú)狀態(tài)的、應(yīng)用層的協(xié)議,用于在計(jì)算機(jī)之間傳輸超文本文檔,通常在 Web 瀏覽器和 Web 服務(wù)器之間進(jìn)行數(shù)據(jù)通信,本文給大家介紹了C/C++發(fā)送與接收HTTP/S請(qǐng)求,需要的朋友可以參考下2023-11-11
C++11中跳轉(zhuǎn)initializer_list實(shí)現(xiàn)分析
這篇文章主要介紹了C++11中跳轉(zhuǎn)initializer_list實(shí)現(xiàn)分析,實(shí)例分析initializer_list<T>初體驗(yàn)，結(jié)合示例代碼給大家介紹的非常詳細(xì)，需要的朋友可以參考下2022-04-04
C++中的動(dòng)態(tài)規(guī)劃子序列問(wèn)題分析探討
可能有些讀者有接觸過(guò)動(dòng)態(tài)規(guī)劃，可能也有一些讀者以前完全不知道動(dòng)態(tài)規(guī)劃這個(gè)東西，別擔(dān)心，我這篇文章會(huì)為讀者做一個(gè)入門(mén)，好讓讀者掌握這個(gè)重要的知識(shí)點(diǎn)2023-03-03
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的五子棋小游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的五子棋小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
基于Matlab圖像處理的公路裂縫檢測(cè)實(shí)現(xiàn)
隨著公路的大量投運(yùn)，公路日常養(yǎng)護(hù)和管理已經(jīng)成為制約公路運(yùn)營(yíng)水平提高的瓶頸，特別是路面狀態(tài)采集、檢測(cè)維護(hù)等工作更是對(duì)傳統(tǒng)的公路運(yùn)維模式提出了挑戰(zhàn)。這篇文章主要介紹了如何通過(guò)Matlab圖像處理實(shí)現(xiàn)公路裂縫檢測(cè)，感興趣的可以了解一下2022-02-02
基于對(duì)話框程序中讓對(duì)話框捕獲WM_KEYDOWN消息的實(shí)現(xiàn)方法
下面我們將通過(guò)程序給大家演示基于對(duì)話框的應(yīng)用程序?qū)M_KEYDOWN消息的捕獲。需要的朋友可以參考下2013-05-05
下面小編就為大家?guī)?lái)一篇C++ string 字符串查找匹配實(shí)例代碼。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-10-10
c++相比c的一個(gè)好處就是實(shí)現(xiàn)了很多的容器和泛型算法，使得程序員的工作得到了很大的簡(jiǎn)化，本文重點(diǎn)給大家介紹C++string容器基本概念講解，需要的朋友參考下吧2021-07-07
C語(yǔ)言使用setjmp和longjmp實(shí)現(xiàn)一個(gè)簡(jiǎn)單的協(xié)程
這篇文章主要為大家介紹了C語(yǔ)言使用setjmp和longjmp實(shí)現(xiàn)一個(gè)簡(jiǎn)單的協(xié)程過(guò)程詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-12-12