桶排序算法的理解及C語言版代碼示例
理解：
桶排序是計數(shù)排序的變種，把計數(shù)排序中相鄰的m個"小桶"放到一個"大桶"中，在分完桶后，對每個桶進行排序（一般用快排），然后合并成最后的結(jié)果。
基本思想：
桶排序假設序列由一個隨機過程產(chǎn)生，該過程將元素均勻而獨立地分布在區(qū)間[0,1)上。我們把區(qū)間[0,1)劃分成n個相同大小的子區(qū)間，稱為桶。將n個記錄分布到各個桶中去。如果有多于一個記錄分到同一個桶中，需要進行桶內(nèi)排序。最后依次把各個桶中的記錄列出來記得到有序序列。
效率分析：
桶排序的平均時間復雜度為線性的O(N+C)，其中C為桶內(nèi)快排的時間復雜度。如果相對于同樣的N，桶數(shù)量M越大，其效率越高，最好的時間復雜度達到O(N)。 當然桶排序的空間復雜度 為O(N+M)，如果輸入數(shù)據(jù)非常龐大，而桶的數(shù)量也非常多，則空間代價無疑是昂貴的。此外，桶排序是穩(wěn)定的。
桶排序的缺點是如果只排幾個數(shù)，但是數(shù)字的范圍卻非常大（10個數(shù)，數(shù)的范圍再0~10000000），那么我們需要10000001個桶才可以，即便是10個數(shù)。
舉例
問題1：隨機輸入 5 個數(shù)，從大到小輸出。
思路：借助一個根據(jù)輸入數(shù)字最大值和最小值的范圍數(shù)組，每當輸入一個數(shù)字的時候，將數(shù)字插入對應數(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);
//計數(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ù)進行排序
#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);
//計數(shù)
book[t]++;
}
//從大到小輸出
for(i = 1000;i>=0;i--)
{
for(j=1;j<=book[i];j++)
printf("%d",i);
}
getchar();getchar();
return 0;
}
相關文章
C?語言內(nèi)存管理指對系統(tǒng)內(nèi)存的分配、創(chuàng)建、使用這一系列操作。在內(nèi)存管理中，由于是操作系統(tǒng)內(nèi)存，使用不當會造成畢竟麻煩的結(jié)果。本文將從系統(tǒng)內(nèi)存的分配、創(chuàng)建出發(fā)，并且使用例子來舉例說明內(nèi)存管理不當會出現(xiàn)的情況及解決辦法2022-05-05
這篇文章主要為大家詳細介紹了C語言實現(xiàn)火車票管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
關于C++讀入數(shù)字按位取出與進制轉(zhuǎn)換問題(典型問題)
這篇文章主要介紹了關于C++讀入數(shù)字按位取出與進制轉(zhuǎn)換問題,是一個非常典型的問題，本文通過實例舉例給大家介紹的非常詳細，需要的朋友可以參考下2020-02-02
這篇文章主要介紹了c++11&14中的STL要點，文中代碼簡單易懂，方便大家更好的學習參考，感興趣的朋友可以了解下2020-06-06
C語言實現(xiàn)linux網(wǎng)卡連接檢測的方法
這篇文章主要為大家詳細介紹了C語言實現(xiàn)linux網(wǎng)卡連接檢測的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-06-06
這篇文章主要介紹了c語言網(wǎng)絡編程-標準步驟(比較簡單),需要的朋友可以參考下2014-01-01
如何實現(xiàn)socket網(wǎng)絡編程的多線程
首先，學好計算機網(wǎng)絡知識真的很重要。雖然，學不好不會影響理解下面這個關于宏觀講解，但是，學好了可以自己打漁吃，學不好就只能知道眼前有魚吃卻打不到漁。在Java中網(wǎng)絡程序有2種協(xié)議：TCP和UDP,下面可以和小編一起學習下2019-05-05
這篇文章主要介紹了如何用C++編寫高性能服務器，文中通過示例代碼介紹的非常詳細，對大家學習C++有一定的參考價值，需要的朋友們可以了解下2020-06-06
這篇文章主要為大家詳細介紹了C語言實現(xiàn)掃雷小游戲的代碼，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
數(shù)據(jù)結(jié)構(gòu)之數(shù)組翻轉(zhuǎn)的實現(xiàn)方法
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)之數(shù)組翻轉(zhuǎn)的實現(xiàn)方法的相關資料,這里用幾種實現(xiàn)方法來實現(xiàn)這樣的功能，需要的朋友可以參考下2017-10-10