排序
日常生活中許多活動都跟排序有關，例如：成績由最高分到最低分排序、手機內通訊錄依照字母順序或筆畫順序排序、撲克牌依照花色或點數排序等，有利於搜尋與找出所需資訊。排序過程中需要確定排序的鍵值(key)，成績排序以分數為鍵值，通訊錄排序以姓名為鍵值，撲克牌以花色或點數為鍵值，排序的鍵值可以是整數、浮點數與字串等。
排序就是將資料依照鍵值由小到大或由大到小排列。常見排序演算法有氣泡排序(Bubble Sort)、選擇排序(Selection Sort)、插入排序(Insertion Sort)、合併排序(Merge Sort)、快速排序(Quick Sort)、堆積排序(Heap Sort)與基數排序(Radix Sort)等，其中以合併排序、快速排序、堆積排序與基數排序的演算法效率比較好，但程式也較複雜。
排序演算法的相關名詞
穩定排序
排序相同數值時，仍然維持原來的順序，不會讓相同數值的兩數交換，例如：數列「3, 6 , 7, 6^', 5, 4」進行排序，6與6^'都表示6，如果排序後獲得「3, 4, 5, 6, 6^', 7」，6仍然在6^'前面，則此排序演算法為穩定的(Stable)排序演算法。
in-place
演算法執行過程中，不需要太多額外的記憶體空間，但可以使用少數的額外記憶體空間，跟輸入的資料量相比，這些額外空間可以忽略，稱作「in-place」。
比較與交換
排序演算法的比較與交換次數，影響排序演算法的效率，比較是比較兩數的大小關係，交換是交換兩個數字所在位置，比較與交換次數取多者就是排序演算法的效率。
Python的串列(list)提供內建函式sort來排序串列，測試函式sort排序1000000個隨機數值所需時間。使用模組random的函式uniform(1,10)隨機產生浮點數，大於等於1且小於10。使用模組time的函式time計算排序所需時間，也可以改寫此程式測試自己撰寫的排序演算法所需執行時間，完整程式如下。
計算函式sort排序所需時間
(a)程式碼與解說
第1行：匯入模組random。
第2行：匯入模組time。
第3行：變數nums參考到一個空串列。
第4到5行：使用迴圈執行以下動作1000000次，模組random的函式uniform(1,10)隨機產生大於等於1，但小於10的浮點數。
第6行：變數start參考到模組time的函式time的回傳值，該值為目前時間從西元1970年1月1日00:00:00的偏移量，以秒為單位。
第7行：串列nums呼叫函式sort進行排序。
第8行：變數end參考到模組time的函式time的回傳值，該值為目前時間從西元1970年1月1日00:00:00的偏移量，以秒為單位。
第9行：計算排序所花時間。
(b)預覽程式結果
排序花費 0.46101903915405273 秒
8-1 氣泡排序(Bubble Sort)
將一個五個元素的陣列，使用氣泡排序演算法將這五個元素由小到大排序。
氣泡排序舉例說明
新增一個五個元素的陣列，如下圖。
氣泡排序演算法程式碼
(a)程式碼與解說
第1行：宣告5個元素的整數陣列A。
第2行：顯示「排序前」。
第3到4行：顯示陣列A的每個元素到螢幕上。
第5行：顯示換行。
第6到9行：氣泡排序演算法，外層迴圈變數i，控制內層迴圈變數j的上限，迴圈變數i由陣列A的長度少1到1，每次遞減1，內層迴圈j由0到(i-1)，每次遞增1，第8到9行比較相鄰兩數，前面比後面大就交換，第9行表示交換兩數。
第10行：顯示「氣泡排序外層迴圈執行第5-i次」。
第11到12行：顯示陣列A的每個元素到螢幕上。
第13行：顯示換行。
(b)程式執行結果
排序前
60 90 44 82 50
氣泡排序外層迴圈執行第 1 次
60 44 82 50 90
氣泡排序外層迴圈執行第 2 次
44 60 50 82 90
氣泡排序外層迴圈執行第 3 次
44 50 60 82 90
氣泡排序外層迴圈執行第 4 次
44 50 60 82 90
氣泡排序演算法效率分析
假設要排序n個資料，程式中第6行到第11行為氣泡排序演算法，外層迴圈i數值由n-1到1，每次遞減1，外層每執行一次內層執行i次，內層迴圈的執行總次數影響整個程式的執行效率，累加內層迴圈的執行次數為「(n-1)+(n-2)+(n-3)+…+2+1」，總次數接近「n^2/2」，演算法效率為O(n^2)。
氣泡排序演算法在最佳情況(假設目標為由小到大排序資料，而輸入的資料已經由小到大排序)的交換次數為0，因為交換程式碼(第9行)不會執行，但比較次數還是O(n^2)。最差情況(假設目標為由小到大排序資料，而輸入的資料是由大到小排序)的交換次數為O(n^2) ，因為在內層迴圈內的交換程式碼(第9行)，每次都會執行執行，比較次數也是O(n^2)。在最佳情況與最差情況的比較次數都為O(n^2)，所以在最佳情況與最差情況的演算法效率還是O(n^2)。
氣泡排序演算法只有在交換時需要額外使用到一個記憶體空間，所以氣泡排序屬於in-place演算法。氣泡排序屬於穩定的(Stable)排序演算法。
8-2選擇排序(Selection Sort)
將一個五個元素的陣列，使用選擇排序演算法將這五個元素由小到大排序。
選擇排序演算法舉例說明
新增一個五個元素的陣列，如下圖。
選擇排序演算法程式碼
(a)程式碼與解說
第1行：宣告5個元素的整數陣列A。
第2行：顯示「排序前」。
第3到4行：顯示陣列A的所有元素。
第5行：顯示換行。
第6到11行：選擇排序演算法，外層迴圈變數i，控制內層迴圈變數j的上限值，外層迴圈變數i由4到1，每次遞減1，初始化變數max為0，內層迴圈j由1到i，每次遞增1，若陣列A索引值j所指定的元素值較陣列A索引值max所指定的元素值大，則設定變數max為變數j。當內層迴圈執行結束後，交換A[i]與A[max](第11行)。
第12行：顯示「選擇排序外層迴圈執行x次結果為」
第13到14行：顯示陣列A的所有元素。
第15行：顯示換行。
(b)預覽程式結果
排序前
60 50 44 82 55
選擇排序外層迴圈執行 1 次結果為
60 50 44 55 82
選擇排序外層迴圈執行 2 次結果為
55 50 44 60 82
選擇排序外層迴圈執行 3 次結果為
44 50 55 60 82
選擇排序外層迴圈執行 4 次結果為
44 50 55 60 82
選擇排序演算法效率
假設要排序n個資料，程式中第6行到第11行為選擇排序演算法，外層迴圈i數值由n-1到1，每次遞減1，外層每執行一次內層執行i次，內層迴圈的執行總次數影響整個程式的執行效率，累計內層迴圈的執行次數為「1+2+3+…+(n-2)+(n-1)」，總次數接近「n^2/2」，演算法效率為O(n^2)。
選擇排序演算法就以比較與交換所需次數來看，選擇排序演算法沒有最佳情況與最差情況。對各種輸入的數列，選擇排序演算法的比較次數都為O(n^2)，而第11行為交換程式碼，在外層迴圈內，內層迴圈的外面，外層迴圈跑n-1次，所以第11行的交換程式碼跑n-1次，交換次數的演算法效率為O(n)。
選擇排序演算法只有在交換時需要額外使用到一個記憶體空間，所以選擇排序屬於in-place演算法。選擇排序不是穩定的(Stable)排序演算法。
8-3插入排序(Insertion Sort)
將一個五個元素的陣列，使用插入排序演算法將這五個元素由小到大排序。
假設隨機產生五個陣列元素，如下圖。
插入排序演算法程式碼
(a)程式碼與解說
第1行：宣告5個元素的整數陣列A。
第2行：顯示「排序前」。
第3到4行：顯示陣列A的所有元素。
第5行：顯示換行。
第6到14行：插入排序演算法，外層迴圈變數i，控制內層迴圈變數j的初始值，外層迴圈變數i由1到4，每次遞增1，初始化變數insert為A[i]，內層迴圈j由i-1到0，每次遞減1，若陣列A索引值j所指定的元素值較變數insert大，則將A[j]複製到A[j+1]；否則中斷內層迴圈(第13行)。變數j遞減1(第14行)。
第15行：將變數insert儲存到A[j+1]。
第16行：顯示「插入排序外層迴圈執行x次結果為」
第17到18行：顯示陣列A的所有元素。
第19行：顯示換行。
(b)預覽程式結果
排序前
60 50 44 82 55
插入排序外層迴圈執行 1 次結果為
50 60 44 82 55
插入排序外層迴圈執行 2 次結果為
44 50 60 82 55
插入排序外層迴圈執行 3 次結果為
44 50 60 82 55
插入排序外層迴圈執行 4 次結果為
44 50 55 60 82
插入排序演算法效率
假設要排序n個資料，程式中第6行到第15行為插入排序演算法，外層迴圈i數值由1到n-1，每次遞增1，外層每執行一次內層執行i次，內層迴圈的執行總次數影響整個程式的執行效率，累加內層迴圈的執行次數為「1+2+3+…+(n-2)+(n-1)」，總次數接近「n^2/2」，演算法效率為O(n^2)。
插入排序演算法在最佳情況(假設目標為由小到大排序資料，而輸入的資料已經由小到大排序)的設定次數(第15行)為O(n)，比較次數也是O(n)，執行效率為O(n)。最差情況(假設目標為由小到大排序資料，而輸入的資料已經由大到小排序) 的設定次數(第9行與第14行)為O(n^2)，比較次數也是O(n^2) ，執行效率為O(n^2)。
插入排序演算法只有在交換時需要額外使用到一個記憶體空間，所以插入排序屬於in-place演算法。插入排序是穩定的(Stable)排序演算法。
8-4合併排序(MergeSort)
合併排序演算法屬於分而治之(Divide And Conquer)演算法，以下示範將一個八個元素的陣列，使用合併排序演算法將這八個元素由小到大排序。
合併排序演算法舉例說明，新增一個八個元素的陣列，如下圖。
合併排序演算法程式碼
(a)程式碼與解說
第1行：陣列a初始化為60、50、44、82、55、24、99、33。
第2行：陣列tmp初始化為0、0、0、0、0、0、0、0。
第3到24行：定義merge函式，輸入的參數有左邊界索引值L、中間索引值M與右邊界索引值R。
第4行：變數left(目前左半部執行到第幾個元素)初始化為L，因為左半部的目前合併元素left從左邊界索引值L開始。
第5行：變數right(目前右半部執行到第幾個元素)初始化為M+1，因為右半部的目前合併元素right從右邊界索引值M+1開始。
第6行：變數i(合併後的暫存陣列tmp的索引值)初始化為L，因為暫存陣列tmp的索引值i從左邊界索引值L開始。
第7行到第14行：當left小於等於M且right小於等於R，表示左右兩半部都還有元素可以合併，繼續執行合併動作。合併動作為當陣列a的索引值left元素小於陣列a的索引值right，將左半部元素放入陣列tmp第i個元素位置(第9行)，變數left都遞增1(第10行)；否則將右半部元素放入陣列tmp第i個元素位置(第12行)，變數right都遞增1(第13行)，變數i遞增1(第14行)。
第15行到第18行：若left小於等於M，表示左半部還有元素需要放入陣列tmp，而右半部已經全部放入，將左半部剩餘元素依序放入陣列tmp。
第19行到第22行：若right小於等於R，表示右半部還有元素需要放入陣列tmp，而左半部已經全部放入，將右半部剩餘元素依序放入陣列tmp。
第23行到第24行：將陣列tmp的第L個元素到第R個元素複製給陣列a的第L個元素到第R個元素。
第26行到第35行：定義mergesort，輸入參數有左半部索引值L與右半部索引值R。
第27行到第35行：若左半部索引值L小於右半部索引值R，則令索引值M為L與R除以2。呼叫函式mergesort(L,M)切割成左半部排序(第29行)，呼叫函式mergesort(M+1,R)切割成右半部排序(第30行)，最後經由呼叫merge(L,M,R)將左右兩邊已排序陣列元素(第31行)，合併成一個更大的已排序陣列。顯示變數L、變數M與變數R的數值，列印陣列所有元素，用於顯示執行合併排序的過程(第32到35行)。
第37行：顯示「排序前」。
第38到39行：顯示陣列a的所有元素。
第40行：顯示換行。
第41行：呼叫mergesort函式，排序陣列a所有元素。
(b)預覽程式結果
排序前
60 50 44 82 55 24 99 33
L= 0 M= 0 R= 1
50 60 44 82 55 24 99 33
L= 2 M= 2 R= 3
50 60 44 82 55 24 99 33
L= 0 M= 1 R= 3
44 50 60 82 55 24 99 33
L= 4 M= 4 R= 5
44 50 60 82 24 55 99 33
L= 6 M= 6 R= 7
44 50 60 82 24 55 33 99
L= 4 M= 5 R= 7
44 50 60 82 24 33 55 99
L= 0 M= 3 R= 7
24 33 44 50 55 60 82 99
合併排序演算法效率
假設要排序n個資料，程式中第3行到第35行為合併排序演算法，第29行到第30行的mergesort函式每次將資料拆成一半，所以合併排序的mergesort的遞迴深度為O(log(n))，第31行的merge動作每一層都需要O(n)，所以合併演算法效率為O(n log(n))，相較於氣泡排序、選擇排序與插入排序演算法效能較佳，合併排序沒有最佳與最差情況。合併排序須額外使用O(n)的暫存記憶體空間，合併排序不屬於in-place演算法，記憶體空間較氣泡排序、選擇排序與插入排序演算法來得多。合併排序是穩定的(Stable)排序演算法。
8-5快速排序(QuickSort)
快速排序演算法屬於分而治之(Divide And Conquer)演算法，以下示範將一個八個元素的陣列，使用快速排序演算法將這八個元素由小到大排序。
快速排序演算法舉例說明，新增一個八個元素的陣列，如下圖。
快速排序演算法程式碼
(a)程式碼新增與解說
第1行：陣列a初始化為60、50、44、82、55、47、99、33。
第2行到第21行：函式quicksort是快速排序演算法，整數變數L與R，表示要排序陣列a[L]到a[R]的所有元素。
第3行到第14行：當L小於R，表示還有兩個以上的元素需要排序，則變數i初始化為L，變數j初始化為R+1。變數i不斷遞增直到找出a[i]大於等於a[L]的元素或者i大於等於R就停止(第7到9行)。變數j不斷遞減直到找出a[j]小於等於a[L]的元素或者j小於等於L就停止(第10到12行)。當i大於等於j，就中斷while迴圈(第13行)，表示已經找到a[L]的放置位置。最後將a[i]與a[j]兩元素交換(第14行)。
第15行：把a[L]與a[j]兩元素交換，a[L]放在a[j]的位置，元素a[L]確定完成排序，也就是比a[L]小的放在左半部，比a[L]大的放在右半部。
第17到19行：顯示快速排序演算法的遞迴呼叫過程，與排序過程中陣列所有元素。
第20到21行：遞迴呼叫排序左半部，排序陣列a[L]到a[j-1]的元素，與遞迴呼叫排序右半部，排序陣列a[j+1]到a[R]的元素。
第23行：顯示「排序前」。
第24到26行：顯示陣列A的所有元素。
第27行：呼叫quicksort函式，排序陣列a的所有元素。
(b)程式結果預覽
排序前
60 50 44 82 55 47 99 33
L= 0 j= 5 R= 7
47 50 44 33 55 60 99 82
L= 0 j= 2 R= 4
44 33 47 50 55 60 99 82
L= 0 j= 1 R= 1
33 44 47 50 55 60 99 82
L= 3 j= 3 R= 4
33 44 47 50 55 60 99 82
L= 6 j= 7 R= 7
33 44 47 50 55 60 82 99
快速排序演算法效率
假設要排序n個資料，程式中第2行到第21行為快速排序演算法，第20行到第21行的quicksort函式每次將資料拆成一半或接近一半，所以快速排序的quicksort的遞迴深度接近O(log(n))，每一層都需要O(n)，所以快速排序演算法平均效率為O(n log(n))，相較於氣泡排序與插入排序演算法效能較佳，但最差情形就是每次切割都很不均勻，分成一邊沒有任何元素，另一邊是n-1個元素 (當數字已經由大到小或由小到大完成排序時，就會有此情況)，這時快速排序演算法效率為O(n^2)，並不會比氣泡排序與插入排序演算法來的好，相較於合併排序演算法，最差情形合併排序比快速排序效率要好。快速排序遞迴深度所占記憶體空間需使用O(log(n))記憶體空間，不屬於in-place演算法。快速排序不是穩定的(Stable)排序演算法。
8-6 堆積排序(HeapSort)
堆積(Heap)是完整的二元樹，儲存在一維陣列內，分成MaxHeap與MinHeap。上一層節點的數值大於等於下一層的所有節點，堆積內所有節點都符合此規則，稱作MaxHeap; 上一層節點的數值小於等於下一層的所有節點，堆積內所有節點都符合此規則，稱作MinHeap。
因為根節點45比所有子節點大，節點35比子節點24與13大，節點27比子節點25大，下圖二元樹滿足MaxHeap的定義。
堆積(Heap)資料結構可以使用一維陣列儲存，規定根節點(root)儲存在一維陣列索引值為1的元素內，則根節點的左子節點儲存在索引值為2的元素內，根節點的右子節點儲存在索引值為3的元素內。節點儲存在一維陣列索引值為2的元素內，則該節點的左子節點儲存在索引值為4的元素內，該節點的右子節點儲存在索引值為5的元素內，將上圖的MaxHeap儲存在一維陣列，結果如下。
可以找出以下規則性，節點在一維陣列索引值為k的元素，則該節點的左子節點在索引值為2*k的元素，該節點的右子節點在索引值為2*k+1的元素，利用此關係可以簡化程式碼。
建立堆積(Heap)的執行步驟如下。
Step1)首先將一維陣列轉換成堆積結構，如果要將一維陣列由小到大排序，則使用Max Heap；如果要將一維陣列由大到小排序，則使用Min Heap。
Step2)從堆積結構依序取出根節點(root)，與最後一個元素交換，再將除了最後一個節點外的一維陣列轉換成堆積結構，此時需要處理的堆積結構已經少一個元素，不斷重複上述步驟直到剩下一個元素為止，就會完成排序。
首先將一維陣列轉換成堆積結構，以下為建立Max Heap的執行步驟範例。
h = [None, 55, 45, 89, 35, 65, 99, 23, 79]
將陣列h轉換成Max Heap，將陣列h以二元樹表示如下。從下到上比較所有擁有子節點的節點(節點h[4]、h[3]、h[2]、h[1])，如果該節點小於子節點中較大的節點，該節點與子節點較大的節點互換。
(1)上圖中由下到上第1個有子節點的節點為h[4] (數值為35)，因為左子節點h[8] (數值為79)，就需要h[4]與h[8]互換，結果如下圖。
(2)上圖中由下到上第2個有子節點的節點為h[3] (數值為89)，因為子節點中較大為左子節點h[6] (數值為99)，就需要h[3]與h[6]互換，結果如下圖。
(3)上圖中由下到上第3個有子節點的節點為h[2] (數值為45) ，因為子節點中較大為左子節點h[4] (數值為79)，就需要h[2]與h[4]互換，結果如下圖，接著比較h[4] (數值為45)與子節點h[8] (數值為35)，發現不用互換。
(4)上圖中由下到上第4個有子節點的節點為h[1] (數值為55) ，因為子節點中較大為右子節點h[3] (數值為99)，就需要h[1]與h[3]互換，結果如下圖。
上圖中交換過後的節點h[3]，因為子節點中較大為左子節點h[6] (數值為89)，就需要h[3]與h[6]互換，結果如下圖。到此將一維陣列轉換成Max Heap。
建立Heap演算法程式碼
(a)程式碼與解說
第1行：宣告陣列a，有9個元素，分別是None、55、45、89、35、65、99、 23、79。
第2到13行：定義函式max_heapify，如果2*x+1小於等於n(第3行)，表示有右子節點，則接著判斷如果h[2*x]大於h[2*x+1]，表示左子節點大於右子節點，則變數max參考到2*x(第4到5行)，否則變數max參考到2*x+1(第6到7行)，表示變數max參考到較大的子節點的索引值；否則，表示沒有右子節點，則變數max參考到2*x(第8到9行)。
第10到13行：如果h[x]小於h[max]，需要將子節點h[max]與節點h[x]互換(第11行)，如果2*max小於等於n，表示子節點h[max]也有子節點，遞迴呼叫函式max_heapify是否與孫節點交換。
第15到17行：定義函式build_max_heap，將任何陣列轉換成Max Heap，迴圈變數i由n除以2取整數到1為止，每次遞減1，呼叫函式max_heapify檢查每一個h[i]是否需要與子節點交換，形成Max Heap。
第19行：呼叫build_max_heap函式，將陣列a轉換成Max Heap。
第20行：印出陣列a的所有元素。
(b)程式結果預覽
[None, 99, 79, 89, 45, 65, 55, 23, 35]
以下使用Max Heap由小到大排序陣列元素的執行步驟如下。
Heap Sort演算法程式碼
(a)程式碼與解說
第1行：宣告陣列a，有9個元素，分別是None、55、45、89、35、65、99、 23、79。
第2到13行：定義函式max_heapify，如果2*x+1小於等於n(第3行)，表示有右子節點，則接著判斷如果h[2*x]大於h[2*x+1]，表示左子節點大於右子節點，則變數max參考到2*x(第4到5行)，否則變數max參考到2*x+1(第6到7行)，表示變數max參考到較大的子節點的索引值；否則，表示沒有右子節點，則變數max參考到2*x(第8到9行)。
第10到13行：如果h[x]小於h[max]，需要將子節點h[max]與節點h[x]互換(第11行)，如果2*max小於等於n，表示子節點h[max]也有子節點，遞迴呼叫函式max_heapify是否與孫節點交換。
第15到17行：定義函式build_max_heap，將任何陣列轉換成Max Heap，迴圈變數i由n除以2取整數到1為止，每次遞減1，呼叫函式max_heapify檢查每一個h[i]是否需要與子節點交換，形成Max Heap。
第19到26行：定義函式heap_sort，呼叫build_max_heap函式，將陣列h轉換成Max Heap。印出陣列h(第21行)。
第22到26行：迴圈變數i由n到2，每次遞減1，h[i]與h[1]互換(第23行)。如果變數i大於2，則呼叫max_heapify讓陣列h形成Max Heap(第24到25行)。印出陣列h的所有元素。
第28行：呼叫函式heap_sort排序陣列a。
第29行：印出陣列a的所有元素。
(b)程式結果預覽
[None, 99, 79, 89, 45, 65, 55, 23, 35]
[None, 89, 79, 55, 45, 65, 35, 23, 99]
[None, 79, 65, 55, 45, 23, 35, 89, 99]
[None, 65, 45, 55, 35, 23, 79, 89, 99]
[None, 55, 45, 23, 35, 65, 79, 89, 99]
[None, 45, 35, 23, 55, 65, 79, 89, 99]
[None, 35, 23, 45, 55, 65, 79, 89, 99]
[None, 23, 35, 45, 55, 65, 79, 89, 99]
[None, 23, 35, 45, 55, 65, 79, 89, 99]
堆積排序演算法效率
使用函式build_max_heap將陣列轉換成Max Heap(第15到17行)，約執行n/2次，呼叫函式max_heapify進行交換形成Max Heap，最大深度為遞迴深度O(log(n))，所以函式build_max_heap的演算法效率為O(n*log(n))。函式heap_sort呼叫函式 build_max_heap建立Max Heap。執行n-2次，每次將h[i]與h[1]互換，呼叫max_heapify交換h[1]與其他元素，讓陣列h形成Max Heap(第24到25行) 函式max_heapify的最大深度為遞迴深度O(log(n))，第22到26行的程式效率為O(n*log(n))，因此堆積排序演算法效率為O(n*log(n))。堆積排序屬於in-place演算法。堆積排序不是穩定的(Stable)排序演算法。
8-7 基數排序(Radix Sort)
基數排序不使用比較與交換的方式進行排序，而是比較每一個數值的個位數、十位數、百位數、…、到最高位數為止。由最高位到最低位的順序進行排序，稱作Most Significant Digit(縮寫為MSD)，例如：123，依序比較百位數1、十位數2與個位數3就是由最高位到最低位方式進行排序；由最低位到最高位的順序進行排序，稱作Least Significant Digital(縮寫為LSD)，例如：123，依序比較個位數3、十位數2與百位數1就是由最低位到最高位方式進行排序，以下分別介紹。將一個十個元素的陣列，使用基數排序演算法將這十個元素由小到大排序。
基數排序演算法舉例說明，將十個數字放置於陣列中，如下圖，使用基數排序演算法由小到大排序此陣列。
程式撰寫時，最高位到最低位(Most Significant Digit，縮寫為MSD)方式進行基數排序時，需要額外結構維持最高位順序，排序第二高位的數字，也需要額外結構維持最二高位順序，排序第三高位的數字，以此類推，其他位數字也如此。最低位到最高位(Least Significant Digital，縮寫為LSD)方式進行基數排序，不需要額外結構維持最低位順序，直接使用穩定排序(Stable Sort)演算法排序第二低位數字，最低位數字順序仍然已排序，也就是當已排序的個位數進行十位數排序時，並不會對個位數排序結果有影響。接著排序第三低位數字時，不需要額外結構維持第二低位順序，直接使用穩定排序(Stable Sort)演算法排序第三低位數字，最二位數字順序仍然已排序，以此類推，其他位數字也如此。
以下程式為最低位到最高位(Least Significant Digital，縮寫為LSD)方式進行基數排序，首先介紹使用計數排序(Counting Sort)排序每一個元素都是個位數數字的陣列，可以使用計數排序擴展成最低位到最高位的基數排序演算法。
將十個數字放置於陣列中，如下圖，由小到大排序陣列a。
計數排序演算法程式碼
(a)程式碼與解說
第1行：宣告陣列a有10個元素，分別為4、6、5、7、1、0、6、8、9、2。
第2行：宣告陣列b有10個元素，每個元素都是0。
第3行：宣告陣列cnt有10個元素，每個元素都是0。
第4行：宣告陣列pos有10個元素，每個元素都是0。
第5到6行：計算每一個數字的個數到陣列cnt。
第7到9行：計算每一位數字的最後一個元素的位置到陣列pos。
第10到12行：陣列pos的第a[i]個的元素值遞減1 ,
將陣列a元素填入陣列b的陣列pos第a[i]個的元素。
第13到15行：印出陣列b的每一個元素值。
(b)程式結果預覽
0 1 2 4 5 6 6 7 8 9
基數排序演算法程式碼
(a)程式碼與解說
第1行：宣告陣列a有9個元素，分別為454、65、452、130、33、998、681、542與249。
第2行：宣告陣列b有9個元素，每個元素都是0。
第4到6行：定義函式dig取出數值x的第〖log〗_10 m位數字，m為10的次方。
第8到27行：定義函式radix_sort，排序n個數值，數值最大為k位數。
第9到27行：迴圈跑k次，由最低位到最高位進行基數排序，迴圈變數j等於1，將每個數字的個位數字由小到大排序，接著設定陣列cnt有10個元素，每個元素都是0(第10行)，設定陣列pos有10個元素，每個元素都是0(第11行)，設定變數m為10的j次方(第12行)。計算數字個數，計算n個數值的第〖log〗_10 m位數字的個數到陣列cnt(第13到15行)。累加數字個數，計算每位數字由小到大的累計個數到陣列pos(第16到18行)。填入適當位置，將陣列a的每個元素依照索引值高到低取出，使用陣列pos以每個數值的第〖log〗_10 m位數字查詢擺放位置(pos[x])，將pos[x]遞減1，將陣列a元素放入陣列b的第pos[x]位置(第19到22行)。將陣列b的每個元素拷貝回到陣列a(第23到24行)。印出陣列a的每一個元素(第25到27行)。
第29行：呼叫函式radix_sort，輸入9表示有9個元素要排序，輸入3表示最大元素數值為3位數。
(b)程式結果預覽
130 681 542 33 454 65 447 998 249
130 33 542 447 249 454 65 681 998
33 65 130 249 447 454 542 681 998
基數排序演算法效率
第9到27行為基數排序，迴圈需要跑k次，迴圈內第13到15行、第19到22行、第23到24行與第25到26行需要執行n次，第17到18行需要執行d次，此演算法效率為O(k(n+d))，k表示最大數值為k位數，n表示排序n個數值，d表示數值的基底，當n很大時，且k與d相對很小，演算法效率就會接近O(n)。基數排序需要額外O(n)的暫存空間，不屬於in-place演算法。基數排序是穩定的(Stable)排序演算法。
8-8各種排序演算法的比較
排序相同數值時，仍然維持原來的順序，不會讓相同數值的兩數交換，例如：數列「3, 6 , 7, 6^', 5, 4」進行排序，6與6^'都表示6，排序後獲得「3, 4, 5, 6, 6^', 7」，6仍然在6^'前面，此排序演算法為穩定的(Stable)排序演算法。
演算法執行過程中，如果不需要使用額外記憶體空間，稱作「in-place」，例如：氣泡排序、插入排序與選擇排序的記憶體空間使用量都是O(1)，所花費的額外記憶體空間屬於常數，就屬於in-place的演算法。快速排序的遞迴深度至少是log(n)，而合併排序與基數排序至少需要n個額外記憶體空間，n為輸入排序演算法的資料量，所以都不屬於in-place的演算法。
綜合比較本章所介紹的排序演算法，如下表。
