現(xiàn)有一串待排序的數(shù)字，求如何用最快的方式進(jìn)行升序排序？

看到這個(gè)問題，是不是有很多同學(xué)第一反應(yīng)是使用快速排序、插入排序，其實(shí)在一些特殊情況下還有一種比快速排序更快的排序——桶排序。

我們首先來看一下百度百科對桶排序的解釋：

“ 桶排序 (Bucket sort)或所謂的箱排序，是一個(gè)排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時(shí)候，桶排序使用線性時(shí)間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響?！?/p>

其實(shí)桶排序從字面意思上就很好理解，首先肯定和桶是離不開關(guān)系的，分成若干個(gè)桶，每個(gè)桶對應(yīng)不同的區(qū)間，把待排序的數(shù)字分別放入相應(yīng)的桶里面，每個(gè)桶里面的數(shù)字在進(jìn)行一次排序（排序方式自己決定），排序結(jié)束后，再依次把每個(gè)桶的數(shù)字打印出來，桶排序就完成了。

詳細(xì)步驟：

一、列出待排序的數(shù)字（如圖1-1）

二、確定桶的個(gè)數(shù)及桶的取值范圍（如圖1-2）

三、遍歷待排序的數(shù)組，將每一個(gè)元素依次放入對應(yīng)取值范圍的桶里面

四、對每一個(gè)桶里面的元素進(jìn)行排序（可任意選擇一種排序）

五、將每個(gè)桶中的元素按照順序賦值到原始數(shù)組中，完成本次排序（如圖1-5）

代碼實(shí)現(xiàn)：

#include <stdio.h>

void main()

{

? ? ?int a[11],i,j,t;

? ? ?for(i=0;i<=10;i++)

? ? {

? ? ? ? ? ? a[i]=0;? ? //初始化為0

? ? ?}

? ? ?for(i=0;i<5;i++)? ? //循環(huán)讀入5個(gè)數(shù)

? ? ?{

? ? ? ? ? ? scanf("%d",&t);? ?//把每一個(gè)數(shù)讀到變量t中

? ? ? ? ? ? a[t]++;? ? //進(jìn)行計(jì)數(shù)

? ? ?}

? ? ?for(i=0;i<=10;i++)? ? //依次判斷a[0]~a[10]

? ? ?{? ?

? ? ? ? ? ? for(j=0;j<a[i];j++)? ? ?//出現(xiàn)了幾次就打印幾次

? ? ? ? ? ? {? ?

? ? ? ? ? ? ? ? printf("%d",i);

? ? ? ? ? ? }? ?

? ? ?}

}

文章來源，學(xué)到牛牛 www.xuedaon.com