詳解桶排序算法的思路及C++編程中的代碼實(shí)現(xiàn)
更新時(shí)間：2016年07月06日 15:28:31 作者：kkun
桶排序即是先把每個(gè)桶中的元素進(jìn)行排序然后遍歷桶依次列出元素的算法,桶排序在元素較少的情況下很高效,以下我們就來(lái)詳解桶排序算法的思路及C++編程中的代碼實(shí)現(xiàn):
算法思路理解
我自己的理解哈,可能與網(wǎng)上說(shuō)的有一些出入,大體都是同樣的原理
無(wú)序數(shù)組有個(gè)要求,就是成員隸屬于固定(有限的)的區(qū)間,如范圍為[0-9](考試分?jǐn)?shù)為1-100等)
例如待排數(shù)字
[6 2 4 1 5 9]
準(zhǔn)備10個(gè)空桶,最大數(shù)個(gè)空桶
[6 2 4 1 5 9] 待排數(shù)組 [0 0 0 0 0 0 0 0 0 0] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶編號(hào)(實(shí)際不存在)
1,順序從待排數(shù)組中取出數(shù)字,首先6被取出,然后把6入6號(hào)桶,這個(gè)過(guò)程類(lèi)似這樣:空桶[ 待排數(shù)組[ 0 ] ] = 待排數(shù)組[ 0 ]
[6 2 4 1 5 9] 待排數(shù)組 [0 0 0 0 0 0 6 0 0 0] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶編號(hào)(實(shí)際不存在)
2,順序從待排數(shù)組中取出下一個(gè)數(shù)字,此時(shí)2被取出,將其放入2號(hào)桶,是幾就放幾號(hào)桶
[6 2 4 1 5 9] 待排數(shù)組 [0 0 2 0 0 0 6 0 0 0] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶編號(hào)(實(shí)際不存在) 3,4,5,6省略,過(guò)程一樣,全部入桶后變成下邊這樣 [6 2 4 1 5 9] 待排數(shù)組 [0 1 2 0 4 5 6 0 0 9] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶編號(hào)(實(shí)際不存在)
0表示空桶,跳過(guò),順序取出即可:
1 2 4 5 6 9
C++示例：
以下是桶排序的c++程序,其中運(yùn)用了list自帶的sort函數(shù)。
#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
void bucketsort(double* a, int n) {
list<double>* b = new list<double>[n];
for (int i = 0; i < n; i++) {
b[int(a[i])].push_back(a[i]);
}
for (int i = 0; i < n; i++) {
b[i].sort();
}
for (int i = 0,j=0; i < n; i++) {
while (b[j].size() < 1)j++;
a[i] = b[j].front();
b[j].pop_front();
}
}
int main() {
double arr[] = {0.1,1.1,2.2,3.5,1.5,2.3,7.5,1.7};
int n = 8;
bucketsort(arr, n);
for (int i = 0; i < 8; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
程序運(yùn)行結(jié)果：
補(bǔ)充說(shuō)明三點(diǎn)
1,桶排序是穩(wěn)定的
2,桶排序是常見(jiàn)排序里最快的一種,比快排還要快…大多數(shù)情況下
3,桶排序非?？?但是同時(shí)也非常耗空間,基本上是最耗空間的一種排序算法
相關(guān)文章
C語(yǔ)言中的結(jié)構(gòu)體的入門(mén)學(xué)習(xí)教程
這篇文章主要介紹了C語(yǔ)言中的結(jié)構(gòu)體的入門(mén)學(xué)習(xí)教程,以struct語(yǔ)句定義的結(jié)構(gòu)體是C語(yǔ)言編程中的重要基礎(chǔ),需要的朋友可以參考下2015-12-12
這篇文章主要介紹了C語(yǔ)言怎樣用指針指向字符串問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-10-10
通過(guò)不同的方法，實(shí)現(xiàn)對(duì)所輸入字符串的反轉(zhuǎn)，有需要的朋友可以參考一下2013-09-09
C++ OpenCV實(shí)戰(zhàn)之手寫(xiě)數(shù)字識(shí)別
這篇文章主要為大家詳細(xì)介紹了如何使用machine learning機(jī)器學(xué)習(xí)模塊進(jìn)行手寫(xiě)數(shù)字識(shí)別功能，文中的示例代碼講解詳細(xì)，感興趣的可以了解一下2022-08-08
這篇文章主要介紹了C++實(shí)現(xiàn)遺傳算法，以實(shí)例形式較為詳細(xì)的分析了遺傳算法的C++實(shí)現(xiàn)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-12-12
這篇文章主要為大家整理并介紹了C語(yǔ)言編程必背的示例代碼大全，有需要的朋友可以借鑒參考下，希望能夠有所幫助2021-11-11
OpenCV實(shí)現(xiàn)直線(xiàn)檢測(cè)并消除
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)直線(xiàn)檢測(cè)并消除，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-06-06
list是一種序列式容器。list容器完成的功能實(shí)際上和數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表是極其相似的，list中的數(shù)據(jù)元素是通過(guò)鏈表指針串連成邏輯意義上的線(xiàn)性表，也就是list也具有鏈表的主要優(yōu)點(diǎn)，即：在鏈表的任一位置進(jìn)行元素的插入、刪除操作都是快速的2022-07-07
繼承是C++面向?qū)ο缶幊讨械囊婚T(mén)。繼承是子類(lèi)繼承父類(lèi)的特征和行為，或者是繼承父類(lèi)得方法，使的子類(lèi)具有父類(lèi)得的特性和行為。重寫(xiě)是子類(lèi)對(duì)父類(lèi)的允許訪(fǎng)問(wèn)的方法實(shí)行的過(guò)程進(jìn)行重新編寫(xiě)，返回值和形參都不能改變。就是對(duì)原本的父類(lèi)進(jìn)行重新編寫(xiě)，但是外部接口不能被重寫(xiě)2022-06-06
Visual Studio中scanf函數(shù)報(bào)錯(cuò)的幾種解決方法
本文主要介紹了Visual Studio中scanf函數(shù)報(bào)錯(cuò)的幾種解決方法,文中通過(guò)圖文示例介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2025-03-03