排序算法的穩定性問題

排序算法的穩定性是指：在待排序的記錄序列中，存在多個相同的關鍵字的記錄，經過排序以後，相同關鍵字的順序若不變，則稱此排序算法是穩定的。

今天介紹兩種簡單的排序算法穩定性：選擇排序和插入排序。

選擇排序：每趟從待排序的記錄中選出關鍵字最小的記錄，放在已排序記錄的末尾，與原來末尾上的值交換位置，直到排序結束為止。

例如：     6  9  6  3 8

第一趟     3  9  6  6 8  （這一次，兩個6的相對位置改變）

第二趟     3  6  9  6 8 

第三趟     3  6  6  9  8

第四趟     3  6  6  8  9

結果： 3  6  6  8  9

從以上過程可以看出，選擇排序是一個不穩定的排序算法。

插入排序：在一個有序的小序列上，一次插入一個元素。注意，比較是從序列的末尾開始，也就是說插入元素是和已排序序列的最大值進行比較，如果比它大，則直接插在有序序列最後，否則一直往前找到它該插入的位置。如果遇到相等的元素，則插入元素放在已排序好的相等元素的後面。是以相等元素的前後順序沒有改變。

例如：     6  9  6  3 8

第一趟     6  9  6  3 8

第二趟     6  9  6  3 8 

第三趟     6  6  9  3 8

第四趟     3  6  6  9  8

第五趟     3  6  6  8  9

結果： 3  6  6  8  9

從以上過程可以看出，插入排序沒有改變相等位置的前後順序，是以它是一個穩定的排序算法。