C++計(jì)數(shù)排序詳解
計(jì)數(shù)排序不同于比較排序,是基于計(jì)數(shù)的方式,對(duì)于計(jì)數(shù)排序,假設(shè)每一個(gè)輸入都是介于0~k之間的整數(shù)。對(duì)于每一個(gè)輸入元素x,確定出小于x的元素的個(gè)數(shù)。假如有17個(gè)元素小于x,則x就屬于第18個(gè)輸出位置。
計(jì)數(shù)排序涉及到三個(gè)數(shù)組A[0…..length-1],length為數(shù)組A的長(zhǎng)度;數(shù)組B與數(shù)組A長(zhǎng)度相等,存放最終排序的結(jié)果;C[0…..K]存放A中每個(gè)元素的個(gè)數(shù),k為數(shù)組A中的最大值。
int count_k(int A[],int length),此函數(shù)為了確定數(shù)組A中最大的元素,用來(lái)確定C數(shù)組的長(zhǎng)度。
int count_k(int A[],int length) { int j,max; max = A[0]; for(j=1;j<=length-1;j++) { if(A[j]>=max) max = A[j]; } return max; }
計(jì)數(shù)排序的實(shí)現(xiàn):
void count_sort(int A[],int B[],int k) { int *C = (int *)malloc((k+1) * sizeof(int)); int i,j; for(i=0;i<=k;i++)//初始化數(shù)組C C[i]=0; for(j=0;j<=length-1;j++)//計(jì)算A中元素的個(gè)數(shù) C[A[j]] = C[A[j]]+1; for(i=1;i<=k;i++)//計(jì)算小于等于C[i]的元素的個(gè)數(shù) C[i] = C[i] + C[i-1]; for(j=length-1;j>=0;j--) { int k=C[A[j]]-1; B[k] = A[j]; C[A[j]] = C[A[j]] - 1; } free(C); }
count_sort(A,B,k);
k=5
for(j=0;j<=length-1;j++)//計(jì)算A中元素的個(gè)數(shù) C[A[j]] = C[A[j]]+1;
表示數(shù)組A中有2個(gè)0、0個(gè)1、2個(gè)2、3個(gè)3、0個(gè)4、1個(gè)5
for(i=1;i<=k;i++)//計(jì)算小于等于C[i]的元素的個(gè)數(shù) C[i] = C[i] + C[i-1];
小于等于0的數(shù)有兩個(gè),小于等于1的數(shù)有兩個(gè)、小于等于2的數(shù)有4個(gè)、小于等于3的有7個(gè)、小于等于4的有7個(gè)、小于等于5的有8個(gè)
for(j=length-1;j>=0;j--) { int k=C[A[j]]-1; B[k] = A[j]; C[A[j]] = C[A[j]] - 1; }
for循環(huán)分析如下
j=7;A[j]=A[7]=3;C[A[j]]=C[3]=7;C[A[j]]-1=6;B[C[A[j]]-1]=B[6]=A[j]=3;C[A[j]]=C[A[j]]-1=6
j=6;A[j]=A[6]=0;C[A[j]]=C[0]=2;C[A[j]]-1=1;B[C[A[j]]-1]=B[1]=A[j]=0;C[A[j]]=C[A[j]]-1=1
j=5;A[j]=A[5]=3;C[A[j]]=C[3]=6;C[A[j]]-1=5;B[C[A[j]]-1]=B[5]=A[j]=3;C[A[j]]=C[A[j]]-1=5;
j=4;A[j]=A[4]=2;C[A[j]]=C[2]=4;C[A[j]]-1=3;B[C[A[j]]-1]=B[3]=A[j]=2;C[A[j]]=C[A[j]]-1=3;
j=3;A[j]=A[3]=0;C[A[j]]=C[0]=1;C[A[j]]-1=0;B[C[A[j]]-1]=B[0]=A[j]=0;C[A[j]]=C[A[j]]-1=0;
j=2;A[j]=A[2]=3;C[A[j]]=C[3]=5;C[A[j]]-1=4;B[C[A[j]]-1]=B[4]=A[j]=3;C[A[j]]=C[A[j]]-1=4;
j=1;A[j]=A[1]=5;C[A[j]]=C[5]=8;C[A[j]]-1=7;B[C[A[j]]-1]=B[7]=A[j]=5;C[A[j]]=C[A[j]]-1=7;
j=0;A[j]=A[0]=2;C[A[j]]=C[2]=3;C[A[j]]-1=2;B[C[A[j]]-1]=B[2]=A[j]=2;C[A[j]]=C[A[j]]-1=2;
計(jì)數(shù)排序的最后運(yùn)行截圖
計(jì)數(shù)排序分析:j=length-1;j>=0;j–此處為倒序,是為了保證排序的穩(wěn)定性,這個(gè)在基數(shù)排序中有重要的作用。
相關(guān)文章
VS2010 boost標(biāo)準(zhǔn)庫(kù)開(kāi)發(fā)環(huán)境安裝教程
這篇文章主要為大家詳細(xì)介紹了VS2010 boost標(biāo)準(zhǔn)庫(kù)開(kāi)發(fā)環(huán)境的安裝教程,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-04-04C語(yǔ)言中volatile關(guān)鍵字的深入講解
在程序設(shè)計(jì)中,尤其是在C語(yǔ)言、C++、C#和Java語(yǔ)言中,使用volatile關(guān)鍵字聲明的變量或?qū)ο笸ǔ>哂信c優(yōu)化、多線程相關(guān)的特殊屬性,這篇文章主要給大家介紹了關(guān)于C語(yǔ)言volatile關(guān)鍵字的相關(guān)資料,需要的朋友可以參考下2021-07-07C語(yǔ)言如何寫(xiě)類實(shí)現(xiàn)教程示例
這篇文章主要為大家介紹了C語(yǔ)言如何寫(xiě)類的實(shí)現(xiàn)教程示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-04-04VScode + keil開(kāi)發(fā)環(huán)境搭建安裝使用過(guò)程
這篇文章主要介紹了VScode + keil開(kāi)發(fā)環(huán)境搭建及安裝使用過(guò)程,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-07-07C語(yǔ)言實(shí)現(xiàn)輸入ascii碼,輸出對(duì)應(yīng)的字符方式
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)輸入ascii碼,輸出對(duì)應(yīng)的字符方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-01-01MFC擴(kuò)展DLL中導(dǎo)出類和對(duì)話框的實(shí)現(xiàn)方法
這篇文章主要介紹了MFC擴(kuò)展DLL中導(dǎo)出類和對(duì)話框的實(shí)現(xiàn)方法,詳細(xì)講述了實(shí)現(xiàn)擴(kuò)展DLL中導(dǎo)出類和對(duì)話框的具體步驟與方法,具有不錯(cuò)的實(shí)用價(jià)值,需要的朋友可以參考下2014-10-10