快捷導(dǎo)航

桶排序算法的理解及C語言版代碼示例

更新時間：2016年07月06日 15:14:26 作者：Mitchell

桶排序算法顧名思義,就是把要排序的元素分桶排序后合并結(jié)果,這里我們就來看一下桶排序算法的理解及C語言版代碼示例:

理解：
桶排序是計(jì)數(shù)排序的變種，把計(jì)數(shù)排序中相鄰的m個"小桶"放到一個"大桶"中，在分完桶后，對每個桶進(jìn)行排序（一般用快排），然后合并成最后的結(jié)果。
基本思想：
桶排序假設(shè)序列由一個隨機(jī)過程產(chǎn)生，該過程將元素均勻而獨(dú)立地分布在區(qū)間[0,1)上。我們把區(qū)間[0,1)劃分成n個相同大小的子區(qū)間，稱為桶。將n個記錄分布到各個桶中去。如果有多于一個記錄分到同一個桶中，需要進(jìn)行桶內(nèi)排序。最后依次把各個桶中的記錄列出來記得到有序序列。
效率分析：
桶排序的平均時間復(fù)雜度為線性的O(N+C)，其中C為桶內(nèi)快排的時間復(fù)雜度。如果相對于同樣的N，桶數(shù)量M越大，其效率越高，最好的時間復(fù)雜度達(dá)到O(N)。當(dāng)然桶排序的空間復(fù)雜度為O(N+M)，如果輸入數(shù)據(jù)非常龐大，而桶的數(shù)量也非常多，則空間代價無疑是昂貴的。此外，桶排序是穩(wěn)定的。
桶排序的缺點(diǎn)是如果只排幾個數(shù)，但是數(shù)字的范圍卻非常大（10個數(shù)，數(shù)的范圍再0~10000000），那么我們需要10000001個桶才可以，即便是10個數(shù)。

舉例
問題1：隨機(jī)輸入 5 個數(shù)，從大到小輸出。
思路：借助一個根據(jù)輸入數(shù)字最大值和最小值的范圍數(shù)組，每當(dāng)輸入一個數(shù)字的時候，將數(shù)字插入對應(yīng)數(shù)組的序號。

#include <stdio.h>
int main()
{
 int a[11],i,j,t;
 //初始化桶數(shù)組
 for(i=0;i<=10;i++)
 {
   a[i] = 0;
 }
 //循環(huán)讀入5個數(shù)
 for(i = 1;i<=5;i++)
 {
   //把每一個數(shù)讀到變量中去
   scanf("%d",&t);
   //計(jì)數(shù)  
   a[t]++;
 }
 //從大到小輸出
 for(i = 10;i>=0;i--)
 {
   for(j=1;j<=a[i];j++)
     printf("%d",i);
 }
 getchar();getchar();
 //getchar()用來暫停程序，以便查看程序輸出的內(nèi)容
 //也可以用system("pause");來代替
 return 0;
}

問題2：對0-1000的整數(shù)進(jìn)行排序

#include<stdio.h>
int main()
{
 int book[1001],i,j,t;
 //初始化桶數(shù)組
 for(i=0;i<=1000;i++)
 {
   book[i] = 0;
 }
 //輸入一個數(shù)n，表示接下來有n個數(shù)
 scanf("%d",&n);
 for(i = 1;i<=n;i++)
 {
   //把每一個數(shù)讀到變量中去
   scanf("%d",&t);
   //計(jì)數(shù)  
   book[t]++;
 }
 //從大到小輸出
 for(i = 1000;i>=0;i--)
 {
   for(j=1;j<=book[i];j++)
     printf("%d",i);
 }
 getchar();getchar();
 return 0;
}

您可能感興趣的文章: