詳解桶排序算法的思路及C++編程中的代碼實現

2020-05-23 14:02:12

字體：大中小

來源：轉載

供稿：網友

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

無序數組有個要求,就是成員隸屬于固定(有限的)的區間,如范圍為[0-9](考試分數為1-100等)

例如待排數字

[6 2 4 1 5 9]

準備10個空桶,最大數個空桶

[6 2 4 1 5 9]  待排數組[0 0 0 0 0 0 0 0 0 0] 空桶[0 1 2 3 4 5 6 7 8 9] 桶編號(實際不存在)

1,順序從待排數組中取出數字,首先6被取出,然后把6入6號桶,這個過程類似這樣:空桶[ 待排數組[ 0 ] ] = 待排數組[ 0 ]

[6 2 4 1 5 9]  待排數組[0 0 0 0 0 0 6 0 0 0] 空桶[0 1 2 3 4 5 6 7 8 9] 桶編號(實際不存在)

2,順序從待排數組中取出下一個數字,此時2被取出,將其放入2號桶,是幾就放幾號桶

[6 2 4 1 5 9]  待排數組[0 0 2 0 0 0 6 0 0 0] 空桶[0 1 2 3 4 5 6 7 8 9] 桶編號(實際不存在)3,4,5,6省略,過程一樣,全部入桶后變成下邊這樣[6 2 4 1 5 9]  待排數組[0 1 2 0 4 5 6 0 0 9] 空桶[0 1 2 3 4 5 6 7 8 9] 桶編號(實際不存在)

0表示空桶,跳過,順序取出即可:

1 2 4 5 6 9

桶排序,C++,排序算法

C++示例：
以下是桶排序的c++程序,其中運用了list自帶的sort函數。

#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;}

程序運行結果：

桶排序,C++,排序算法