- 相關(guān)推薦
桶排序算法的理解及C語(yǔ)言版代碼示例
桶排序非常快,但是同時(shí)也非常耗空間,基本上是最耗空間的一種排序算法。下面小編為大家整理了桶排序算法的理解及C語(yǔ)言版代碼示例，希望能幫到大家！
理解：
桶排序是計(jì)數(shù)排序的變種，把計(jì)數(shù)排序中相鄰的m個(gè)"小桶"放到一個(gè)"大桶"中，在分完桶后，對(duì)每個(gè)桶進(jìn)行排序（一般用快排），然后合并成最后的結(jié)果。
基本思想：
桶排序假設(shè)序列由一個(gè)隨機(jī)過(guò)程產(chǎn)生，該過(guò)程將元素均勻而獨(dú)立地分布在區(qū)間[0,1)上。我們把區(qū)間[0,1)劃分成n個(gè)相同大小的子區(qū)間，稱(chēng)為桶。將n個(gè)記錄分布到各個(gè)桶中去。如果有多于一個(gè)記錄分到同一個(gè)桶中，需要進(jìn)行桶內(nèi)排序。最后依次把各個(gè)桶中的記錄列出來(lái)記得到有序序列。
效率分析：
桶排序的平均時(shí)間復(fù)雜度為線性的O(N+C)，其中C為桶內(nèi)快排的時(shí)間復(fù)雜度。如果相對(duì)于同樣的N，桶數(shù)量M越大，其效率越高，最好的時(shí)間復(fù)雜度達(dá)到O(N)。 當(dāng)然桶排序的空間復(fù)雜度 為O(N+M)，如果輸入數(shù)據(jù)非常龐大，而桶的數(shù)量也非常多，則空間代價(jià)無(wú)疑是昂貴的。此外，桶排序是穩(wěn)定的。
桶排序的缺點(diǎn)是如果只排幾個(gè)數(shù)，但是數(shù)字的范圍卻非常大（10個(gè)數(shù)，數(shù)的范圍再0~10000000），那么我們需要10000001個(gè)桶才可以，即便是10個(gè)數(shù)。
舉例
問(wèn)題1：隨機(jī)輸入 5 個(gè)數(shù)，從大到小輸出。
思路：借助一個(gè)根據(jù)輸入數(shù)字最大值和最小值的范圍數(shù)組，每當(dāng)輸入一個(gè)數(shù)字的時(shí)候，將數(shù)字插入對(duì)應(yīng)數(shù)組的序號(hào)。
#includeint main(){ int a[11],i,j,t; //初始化桶數(shù)組 for(i=0;i<=10;i++) { a[i] = 0; } //循環(huán)讀入5個(gè)數(shù) for(i = 1;i<=5;i++) i="10;i">=0;i--) { for(j=1;j<=a[i];j++) printf("%d",i); } get);get); //get)用來(lái)暫停程序，以便查看程序輸出的內(nèi)容 //也可以用system("pause");來(lái)代替 return 0;}
問(wèn)題2：對(duì)0-1000的整數(shù)進(jìn)行排序
#includeint main(){ int book[1001],i,j,t; //初始化桶數(shù)組 for(i=0;i<=1000;i++) { book[i] = 0; } //輸入一個(gè)數(shù)n，表示接下來(lái)有n個(gè)數(shù) scanf("%d",&n); for(i = 1;i<=n;i++) i="1000;i">=0;i--) { for(j=1;j<=book[i];j++) printf("%d",i); } get);get); return 0;}
【桶排序算法的理解及C語(yǔ)言版代碼示例】相關(guān)文章：
C語(yǔ)言快速排序算法及代碼06-25
C語(yǔ)言奇偶排序算法詳解及實(shí)例代碼04-05
希爾排序算法的C語(yǔ)言實(shí)現(xiàn)示例02-06
快速排序算法及C#版的實(shí)現(xiàn)示例07-03
java常見(jiàn)的排序算法的代碼03-26
c語(yǔ)言的排序算法07-22
C#排序算法之堆排序07-21