桶排序算法的懂得及C說話版代碼示例

桶排序算法的懂得及C說話版代碼示例。本站提示廣大學習愛好者：（桶排序算法的懂得及C說話版代碼示例）文章只能為提供參考，不一定能成為您想要的結果。以下是桶排序算法的懂得及C說話版代碼示例正文

懂得：
桶排序是計數排序的變種，把計數排序中相鄰的m個"小桶"放到一個"年夜桶"中，在分完桶後，對每一個桶停止排序（普通用快排），然後歸並成最初的成果。
根本思惟：
桶排序假定序列由一個隨機進程發生，該進程將元素平均而自力地散布在區間[0,1)上。我們把區間[0,1)劃分紅n個雷同年夜小的子區間，稱為桶。將n個記載散布到各個桶中去。假如有多於一個記載分到統一個桶中，須要停止桶內排序。最初順次把各個桶中的記載列出來記獲得有序序列。
效力剖析：
桶排序的均勻時光龐雜度為線性的O(N+C)，個中C為桶內快排的時光龐雜度。假如絕對於異樣的N，桶數目M越年夜，其效力越高，最好的時光龐雜度到達O(N)。 固然桶排序的空間龐雜度 為O(N+M)，假如輸出數據異常宏大，而桶的數目也異常多，則空間價值無疑是昂貴的。另外，桶排序是穩固的。
桶排序的缺陷是假如只排幾個數，然則數字的規模卻異常年夜（10個數，數的規模再0~10000000），那末我們須要10000001個桶才可以，即使是10個數。

舉例
成績1：隨機輸出 5 個數，從年夜到小輸入。
思緒：借助一個依據輸出數字最年夜值和最小值的規模數組，每當輸出一個數字的時刻，將數字拔出對應數組的序號。

#include <stdio.h>
int main()
{
 int a[11],i,j,t;
 //初始化桶數組
 for(i=0;i<=10;i++)
 {
   a[i] = 0;
 }
 //輪回讀入5個數
 for(i = 1;i<=5;i++)
 {
   //把每個數讀到變量中去
   scanf("%d",&t);
   //計數  
   a[t]++;
 }
 //從年夜到小輸入
 for(i = 10;i>=0;i--)
 {
   for(j=1;j<=a[i];j++)
     printf("%d",i);
 }
 getchar();getchar();
 //getchar()用來暫停法式，以便檢查法式輸入的內容
 //也能夠用system("pause");來取代
 return 0;
}

成績2：對0-1000的整數停止排序

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