資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法學使用桶排序實現 C++ 程式
在桶排序技術中，資料項會分配給一組桶。每個桶都可以容納類似型別的資料。分配完之後，會使用其他排序演算法對每個桶進行排序。然後，將所有元素收集到主列表中以獲取已排序的形式。
桶排序技術的時間複雜度
時間複雜度：對於最好和平均的情況為 O(n + k)，對於最壞的情況為 O(n2 )。
空間複雜度：對於最壞的情況為 O(nk)
Input − A list of unsorted data: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69 Output − Array after Sorting: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79
演算法
bucketSort(array, size)
輸入：一個數據陣列，以及陣列中的總數
輸出：已排序的陣列
Begin
for i := 0 to size-1 do
insert array[i] into the bucket index (size * array[i])
done
for i := 0 to size-1 do
sort bucket[i]
done
for i := 0 to size -1 do
gather items of bucket[i] and put in array
done
End示例程式碼
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void display(float *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void bucketSort(float *array, int size) {
vector<float> bucket[size];
for(int i = 0; i<size; i++) { //put elements into different buckets
bucket[int(size*array[i])].push_back(array[i]);
}
for(int i = 0; i<size; i++) {
sort(bucket[i].begin(), bucket[i].end()); //sort individual vectors
}
int index = 0;
for(int i = 0; i<size; i++) {
while(!bucket[i].empty()) {
array[index++] = *(bucket[i].begin());
bucket[i].erase(bucket[i].begin());
}
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
float arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
bucketSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}輸出
Enter the number of elements: 10 Enter elements: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69 Array before Sorting: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69 Array after Sorting: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79
更新於：30-Jul-2019
2K+ 次觀看
廣告