桶排序和基數排序有什麼區別？

桶排序和基數排序是親密的表親;桶排序從MSD到LSD，而基數排序可以在「方向」（LSD或MSD）中進行。兩種算法如何工作，特別是它們有何不同？桶排序和基數排序有什麼區別？

2010-12-16 Lazarus

RadixSort和BucketSort的初始合格完全相同。取決於最大數字中的位數，這些元素被放入增量範圍（例如0-10,11-20，... 90-100）的buckets（或bins）中。

然而，在下一回閤中，BucketSort將這些「桶」排序並將它們附加到一個數組中。然而，RadixSort追加沒有進一步排序的桶，並基於數字的第二個數字（十位）來「重新桶」。因此，BucketSort對於'Dense'數組更有效，而RadixSort可以很好地處理稀疏（很好，不完全稀疏但間隔開）數組。

來源

2011-01-06 15:19:45 Akash

您能否擴展此答案以解釋爲什麼這兩種方法的時間複雜性不同？即爲什麼是桶排序O（n + k），但基數排序是O（nk）？ – 2015-02-23 09:24:51

@ShaunBudhram這是一個老問題，但如果有人讀這個想知道。從描述中可以看出，桶排序在N上傳遞一次，然後合併K個桶（桶內的順序是任意的）。儘管基數排序對每個桶都有一個傳遞，但在這裏我認爲排序字符串會是更好的例子，因此您需要執行復雜度爲N的K遍。 – 2016-02-28 12:15:11

「BucketSort命令這些」桶「是什麼意思？每個桶是用不同的算法或者什麼排序的？因爲如果您按10秒分組，每個存儲桶都沒有完全分類。 – mpen 2017-10-24 20:11:34

桶排序和基數排序就像姐妹排序算法，因爲它們不是比較排序，總體思路是相似的。而且，它們在實現上都有點抽象。

基數排序：

沙蔘裝置基（二進制，八進制，十進制，等等）。因此，這種排序是爲數字（也用於字符串）。這工作時各元件E是像電子_ķ ... E ëË，其中e _我是在一定範圍內。（通常爲0至在ASCII字符等以十進制0-9或0-255的基座）
然後，它使用穩定子排序算法的k個道次（它必須是穩定否則基數排序贏得不工作）對數字進行排序。這種子排序算法通常是Counting排序或Bucket排序，但是它不能是基數排序本身。
可以從最高有效數位或最低有效位，因爲它混洗在每一通（從k以0或0至k）的每個數字
它是一種穩定排序算法開始。

桶排序：

它分離陣列分成更小的組或桶，並將它們個別地使用子排序算法或遞歸調用自身排序，然後組合結果。例如，通過將球員加入隊伍中，然後根據他們的球衣號碼排序球員，或將球隊從1-30分成1到1-10,11-20,21-30三個球隊等類別來排序球員。
組合步驟很簡單（與合併排序不同）。只複製每個桶的元件返回到原始排列或與以前的桶的尾加入每個桶的頭部（在鏈表的情況下）
基數/鹼可以是一個類型/實例的組/桶的同時排序數字。因此，你能想到MSD基數作爲排序
桶排序桶的修改實例不就地但穩定排序算法。但是，某些桶類的變體可能不穩定（如果使用不穩定的子分類算法）

來源

2015-05-15 22:30:12

一些比較好的:) – 2016-05-07 14:17:29

桶排序和基數排序有什麼區別？

回答

相關問題