【概述】

?桶排序是一種穩(wěn)定的排序方法，其是非比較類排序中最簡(jiǎn)單的一種。

其基本思想是：假設(shè)待排序記錄的值都在 0~m-1 之間，設(shè)置 m?個(gè)桶，將值為 i 的記錄分配到第 i 個(gè)桶中，然后再將各個(gè)桶中的距離依次收集起來(lái)。

【時(shí)空復(fù)雜度分析】

最好的情況下，每個(gè)桶只有一個(gè)數(shù)據(jù)，那么最好時(shí)間復(fù)雜度為 O(N)

假設(shè) C 為桶內(nèi)排序所花費(fèi)的時(shí)間，那么平均時(shí)間復(fù)雜度：O(N+C)

此外，假設(shè) M 為桶排所需的輔助空間大小，那么空間復(fù)雜度為為：O(M)

【源程序】

int bucket[m];//m-1為數(shù)據(jù)的最大值 void bucketSort(int a[],int n){for(int i=0;i<n;i++)//將數(shù)組a存入桶中bucket[a[i]]++;int cnt=0;for(int i=0;i<m;i++){if(bucket[i]!=0){//桶不為空時(shí)a[cnt++]=i;//收集數(shù)據(jù)bucket[i]--;//桶中數(shù)據(jù)個(gè)數(shù)-1}} }

?

總結(jié)

以上是生活随笔為你收集整理的理论基础 —— 排序 —— 桶排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。