基數排序在C++

Question

我試圖編寫C++代碼來做基數整數的排序。在網上查看教程後，我發現我們必須將每個整數放到合適的桶中，從最不重要的數字開始。我的問題是，在普通算法中，我需要10個從0到9的桶嗎？如果我將這些存儲桶分配爲鏈接列表（例如* list1 ~~~ * list9），它會不會顯得有點奇怪？

謝謝你的時間。這不是功課，而是出於好奇。

Answer 1

我不認爲這是一個C++問題（儘管基數排序可以清楚地用C++實現），它可能與鏈接列表無關，至少不會像你想象的那樣：排序發生在每個數字的基礎上，您可以有效地訪問每個數字的桶。爲此，列表不會工作得太好，但是一個向量會。在每個桶裏面你可以使用一個列表。

至於你需要的桶的數量，答案是：這取決於！您可以使用任何大於1的整數基數，並且您需要相應數量的存儲桶。由於計算機特別擅長使用2的冪計算2的權力，可能比使用其他基數（如10）更高效，但10也可以工作。奇怪的是，Wikipedia's article on Radix Sort使用基數10--可能是爲了避免對基數的自由選擇造成太多混淆。