詳解桶排序算法的思路及C++編程中的代碼實(shí)現(xiàn)

來源：本站原創(chuàng)|時(shí)間：2020-01-10|欄目：C語言|點(diǎn)擊：次

算法思路理解
我自己的理解哈,可能與網(wǎng)上說的有一些出入,大體都是同樣的原理

無序數(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è)過程類似這樣:空桶[ 待排數(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省略,過程一樣,全部入桶后變成下邊這樣

[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表示空桶,跳過,順序取出即可:

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ǔ)充說明三點(diǎn)
1,桶排序是穩(wěn)定的
2,桶排序是常見排序里最快的一種,比快排還要快…大多數(shù)情況下
3,桶排序非常快,但是同時(shí)也非常耗空間,基本上是最耗空間的一種排序算法

上一篇：for循環(huán)中刪除map中的元素valgrind檢測(cè)提示error：Invalid read of size 8

欄目：C語言

下一篇：圖文詳解C語言位運(yùn)算基礎(chǔ)知識(shí)

本文標(biāo)題：詳解桶排序算法的思路及C++編程中的代碼實(shí)現(xiàn)

本文地址：http://mengdiqiu.com.cn/a1/Cyuyan/2180.html

更多C語言