本文實例講述了C語言實現桶排序的方法。分享給大家供大家參考，具體如下：
一、定義
假定：輸入是由一個隨機過程產生的[0, 1)區間上均勻分布的實數。將區間[0, 1)劃分為n個大小相等的子區間（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…將n個輸入元素分配到這些桶中，對桶中元素進行排序，然后依次連接桶輸入0 ≤A[1..n] <1輔助數組B[0..n-1]是一指針數組，指向桶（鏈表）。
二、性能
對于N個待排數據，M個桶，平均每個桶[N/M]個數據的桶排序平均時間復雜度為：
O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
快排的時間復雜度為n*log2(n)
當N=M時，即極限情況下每個桶只有一個數據時。桶排序的最好效率能夠達到O(N)。
桶排序是穩定的
三、實現
/*==============================8 name:bucket sort--------------------------------time complexity:averageO(n+nlogn-nlogm)--------------------------------space complexity:O(n)--------------------------------stability:unstable==============================*///suppose: 0<data[i]<100//we should design the project function based on the data distributionvoid bucket_sort(std::vector<int> &a){ std::vector<std::vector<int>> bucket; bucket.resize(10); std::vector<int>::iterator it=a.begin(); while(it!=a.end()) { int idx=*it/10; bucket[idx].push_back(*it); it++; } std::vector<std::vector<int>>::iterator it1=bucket.begin(); while(it1!=bucket.end()) { simple_sort(*it1); it1++; } it=a.begin(); it1=bucket.begin(); while(it!=a.end() && it1!=bucket.end()) { std::vector<int>::iterator tmp_it=(*it1).begin(); while(tmp_it!=(*it1).end()) { *it=*tmp_it; tmp_it++; it++; } it1++; }}希望本文所述對大家C語言程序設計有所幫助。
新聞熱點
疑難解答
