對基數排序只使用穩定的排序算法有什麼需要？

我想了解在Radix排序中使用不穩定排序算法（如快速排序）的危險。此外，在兩種情況下都必須使用穩定算法（即MSD基數排序和LSD基數排序）？對基數排序只使用穩定的排序算法有什麼需要？

在此先感謝。

你是什麼意思與*將做這項工作*？如果你的意思是輸出將被排序，那麼請意識到MSD上的基數排序（穩定/不穩定）也可以完成這項工作。如果你的意思是這個算法是穩定的，那你爲什麼說*任何（穩定/不穩定）將會完成這項工作，因爲顯然一個不穩定的算法不穩定？你在說什麼*工作？ – trincot

看完你的評論後，我意識到我的問題含糊不清。另外，我意識到我對基數的理解並不完全正確。我編輯了描述。 –

好的，你說的*是什麼意思是穩定算法必須*：在這種情況下，我不理解單詞*必須*。 – trincot

MSD基數排序通常是不實際的，因爲每次通過後虛擬箱不能連接在一起。如果按8位字節排序，在第一遍之後，您有256個獨立的文件夾，兩遍之後，65536個文件夾，三遍之後，16777216個文件夾......。

LSD基數排序需要穩定，因爲虛擬箱按順序連接在一起，並且以下傳遞更重要的「數字」需要保留先前通道建立的順序。請注意，LSD基數排序是可以追溯到1900年代早期的舊卡分揀機的操作方式。

2016-07-28 06:17:03 rcgldr

回答