建站
咨詢
售后
建站咨詢
新聞中心
排序，面試中考察基本功問的比較多的問題。
讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：空間域名、網(wǎng)站空間、營銷軟件、網(wǎng)站建設(shè)、響水網(wǎng)站維護、網(wǎng)站推廣。
時間復(fù)雜度為O(n)的排序，常見的有三種：
- 基數(shù)排序(Radix Sort)
- 計數(shù)排序(Counting Sort)
- 桶排序(Bucket Sort)
今天，1分鐘，爭取讓大家搞懂桶排序。
畫外音：百度“桶排序”，很多文章是錯誤的，本文內(nèi)容與《算法導(dǎo)論》中的桶排序保持一致。
桶排序的適用范圍是，待排序的元素能夠均勻分布在某一個范圍[MIN, MAX]之間。
畫外音：很多業(yè)務(wù)場景是符合這一場景，待排序的元素在某一范圍內(nèi)，且是均勻分布的。
桶排序需要兩個輔助空間：
- ***個輔助空間，是桶空間B
- 第二個輔助空間，是桶內(nèi)的元素鏈表空間
總的來說，空間復(fù)雜度是O(n)。
桶排序有兩個關(guān)鍵步驟：
- 掃描待排序數(shù)據(jù)A[N]，對于元素A[i]，放入對應(yīng)的桶X
- A[i]放入桶X，如果桶X已經(jīng)有了若干元素，使用插入排序，將arr[i]放到桶內(nèi)合適的位置
畫外音：
- 桶X內(nèi)的所有元素，是一直有序的;
- 插入排序是穩(wěn)定的，因此桶內(nèi)元素順序也是穩(wěn)定的;
當arr[N]中的所有元素，都按照上述步驟放入對應(yīng)的桶后，就完成了全量的排序。
桶排序的偽代碼是：
- bucket_sort(A[N]){
- for i =1 to n{
- 將A[i]放入對應(yīng)的桶B[X];
- 使用插入排序，將A[i]插入到B[X]中正確的位置;
- }
- 將B[X]中的所有元素，按順序合并，排序完畢;
- }
舉個栗子：
假設(shè)待排序的數(shù)組均勻分布在[0, 99]之間：
- {5,18,27,33,42,66,90,8,81,47,13,67,9,36,62,22}
可以設(shè)定10個桶，申請額外的空間bucket[10]來作為輔助空間。其中，每個桶bucket[i]來存放[10*i, 10*i+9]的元素鏈表。
上圖所示：
- 待排序的數(shù)組為unsorted[16]
- 桶空間是buket[10]
- 掃描所有元素之后，元素被放到了自己對應(yīng)的桶里
- 每個桶內(nèi)，使用插入排序，保證一直是有序的
例如，標紅的元素66, 67, 62最終會在一個桶里，并且使用插入排序桶內(nèi)保持有序。
最終，每個桶按照次序輸出，排序完畢。
神奇不神奇!!!
桶排序(Bucket Sort)，總結(jié)：
- 桶排序，是一種復(fù)雜度為O(n)的排序
- 桶排序，是一種穩(wěn)定的排序
- 桶排序，適用于數(shù)據(jù)均勻分布在一個區(qū)間內(nèi)的場景
【本文為專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請聯(lián)系原作者】
戳這里，看該作者更多好文
新聞名稱：拜托，面試別再問我桶排序了?。?！
URL標題：http://www.5511xx.com/article/dpoceij.html
