爲什麼不應該從MSD開始實施基數排序？

Question

我正在閱讀Cormen等人的算法導論。人。而且在它們所描述的基數排序的一部分，他們說：

直覺，你可能會在自己最顯著位數排序，每個遞歸所產生箱，然後 排序結合甲板 秩序。不幸的是，由於10個垃圾箱中有9個垃圾箱的卡片必須是 ，因此需要對每個垃圾箱進行分類，此過程會生成許多卡片，您必須對其進行跟蹤。

這是什麼意思？ 我不明白如何按MSB排序會是一個問題？

Answer 1

它們指的是LSD基數排序的有用屬性，既然你確保每個排序步驟是穩定，你只需要對整個數組上的每個數字運行一個步驟，而且你不必單獨對任何子集進行排序。

採取邁克爾的示例性數據：

後0步驟：

170，045，075，090，002，024，802，066，182，332，140，144

後1個步驟（排序上單位）：

170，090，140，002，802，182，332，024，144，045，075，066

後2個步驟（上幾十排序）：

002，802，024，332，140，144，045，066，170，075，182，090

後3個步驟（排序在數百）：

002，024，045，066 ，075,090,140,​​144,170,182,332,802

如果你在二進制中進行基數排序而不是基於10，那麼這個屬性就變得特別有用。然後每個排序步驟只是一個分爲兩部分的分區，這很簡單。至少，直到你想要做，而不使用任何額外的內存。

MSD基數排序的工作，當然，它只是需要更多的簿記和/或非尾遞歸。這只是一個「問題」，因爲CLRS（與其他專家程序員一樣）不喜歡在必要之前進行繁瑣的工作。

Answer 2

考慮下面的示例列表進行排序： 170，045，075，090，002，024，802，066，182，332，140，144

• 排序由最顯著位（數百）給出：

  • 零數百桶：045，075，090，002，024，066

  • 上百種桶：170，182，140，144

  • 三百桶：332

  • 八個數百桶：802

• 由下一位現在需要在零和一百元一桶（其他兩個桶只能包含數字排序每一個項目）：

  • 零幾十：002
  • 二十年代：024
  個
  • 四十多歲：045
  • 六十年代：066
  • 七十年代：075
  • 九十年代：090

• 由至少排序顯著位（1S地方）是不需要的，因爲沒有幾十桶不止一個號碼。儘管如此，這不是這種情況（練習：自己遞歸排序）。因此，現在分類零個數百桶拼接，加入順序，與一，三，八數百桶給：

  002, 024, 045, 066, 075, 090, 140, 144, 170, 182, 332, 801

你可以看到，作者指的是中間遞歸排序步驟，這在LSD基數排序中不是必需的。