為什麼基數排序只有從最低位開始才是「穩定的排序演算法」？？
01-05
可能我發的主題錯了。換句話是說為什麼演算法導論中描述的基數排序是從最低位開始？見演算法導論「基數排序」一章，從高位開始不行嗎？
與人們的直覺相反，基數排序是首先按最低位有效數字進行排序，以解決卡片排序的問題
謝邀。從高位可以，但是麻煩啊。
道理是基數排序每次都調用一個穩定排序，也就是說這一輪比不出大小的數據，保持原來的相對順序不變。而數字比較大小就是從高位開始，比不出大小去看低位，當然應該讓低位先排出「原來的相對順序」了。
從高位開始排，就要分段了，每排完一位，把分不出大小的幾個當成一段，一段段的排，不要讓排完的數據跨段移動，保證這一段的數都比下一段小，排到最後每段就只有一個數了。這樣就完全沒有利用到每次調用的都是穩定排序這一點，感覺上丑多了，也沒什麼意思。
我是這麼理解的：基數排序，又稱為bucket sort，因為Hollerith當時的人們是拿著真的桶進行排序的。如果數字從高位開始排序，意味著有n位，就得有10^n個桶。因為你先排最高位，然後對於這個最高位又要分出十個桶排下一位。比如現在有13，23，12，22，11這五個數。你先為高位排序，就相當於把十位為1的分在一個桶1里（13，12，11），十位為2的分在一個桶2（22，23）里。然後在桶1和桶2之中剩下的元素排序（（11），（12），（13））和（（22），（23））。這樣如果有很多位數，桶就很多。但是從最低位開始排就只需要10個桶，每移動一位，就用針對那一位排序（把元素扔進桶里）。所以不會佔用大量的桶。所以，低位排序優於高位排序。
樓主別被某些答案誤導了，LSD和MSD都是沒問題，不過從高位排序要從大桶裡面繼續分小桶，所以寫法跟低位的不一樣，要用遞歸。兩者應該都是穩定的，樓主可能理解錯了原文吧
我的理解是，高位的數字的大小相對於低位，可以決定性的比較2個數的大小。就是一個數字a高位比另外一個數字b大那a就一定比b大，低位則無法保證。所以，從低到高為必要條件。例如12和21，從高到低排就錯了。而當高位數字相等時，就需要低位去比較兩者大小。所以要用穩定排序，不穩定的話無法保證正確的排序。如12和13，個位排序完，13是在12後面的，如果是穩定排序，十位排序時，13還是在12後面。反之不穩定的排序則無法保證正確的順序。所以，穩定的排序也是必要條件。得證。
最高位開始可以。只是排完第一位數時，數字分到了幾個容器中，必須再分別排每個容器中的數，把每個容器中的數字拿出來再按次最高位排，如此遞歸下去，直到每個容器中只有一個數字後，在合併結果（這個過程類似於歸併排序）。而按最低位的話，就可以直接把每個容器中的數字按順序疊放在一起，排次一位的，不用再分開排，後合併了。穩定的話，指的是每一位數排序必須穩定，即是從容器中拿出來時按容器順序疊放，這保證排序的正確性。書中規定是基數排序是按最低位排，只是一種定義，這樣操作比較簡單。
書上說了「遺憾的是，為了排序一個容器中的卡片，10個容器中的9個都必須先放一邊。」
高位排序比低位多了空間開銷。
另外，高位排序也是可以穩定的，你說的「只」我怎麼沒在書上看到？
處理的好的話， MSD 也是可以是穩定的。 因為每一步都是按順序扔到筒里去的。 並沒有丟失順序。
RADIX-SORT(A,d)
for i &<- 1 to d
do use a stable sort to sort array A on digit i
從低位 第一次：31 22 13，第二次：13 22 31 對的
- 必須從低位開始，因為每趟都是對整個全集排序；另外，每趟排序必須使用穩定的排序演算法（比如bucket sort 或 merge so）。
- 如果先對高位排，每趟就必須對已排好的高位相同的子序列排序，此時可以用不穩定的排序演算法（例如quick sort），但是，這樣就必須先找到高位不同的那些子序列的邊界，從而降低性能。
我的理解是你無法預測高位有多高,假如已知，那即使從高位開始也是穩定的
但一般情況下就意味著你需要對需要排序的數先做一次按位拆分，然後再排序，從低位開始就不需要這工作
推薦閱讀：