【小彥子老師】評論

A.選擇排序（Selection sort）　　選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩餘元素裡面給第二個元素選擇第二小的，依次類推，直到第n – 1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那麼，在一趟選擇，如果當前元素比一個元素小，而該小的元素又出現在一個和當前元素相等的元素後面，那麼交換後穩定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那麼原序列中2個5的相對前後順序就被破壞了，所以選擇排序是不穩定的排序演算法。B.堆排序（Heapsort sort）　　堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值，即A[PARENT[i]] >= A[i]。在陣列的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。　　既然是堆排序，自然需要先建立一個堆，而建堆的核心內容是調整堆，使二叉樹滿足堆的定義（每個節點的值都不大於其父節點的值）。調堆的過程應該從最後一個非葉子節點開始，假設有陣列A = {1, 3, 4, 5, 7, 2, 6, 8, 0}。那麼調堆的過程如下圖，陣列下標從0開始，A[3] = 5開始。分別與左孩子和右孩子比較大小，如果A[3]最大，則不用調整，否則和孩子中的值最大的一個交換位置，在圖1中是A[7] > A[3] > A[8]，所以A[3]與A[7]對換，從圖1.1轉到圖1.2。這裡寫圖片描述　　我們知道堆的結構是節點i的孩子為2 * i和2 * i 1節點，大頂堆要求父節點大於等於其2個子節點，小頂堆要求父節點小於等於其2個子節點。在一個長為n 的序列，堆排序的過程是從第n / 2開始和其子節點共3個值選擇最大（大頂堆）或者最小（小頂堆），這3個元素之間的選擇當然不會破壞穩定性。但當為n / 2 – 1， n / 2 – 2， … 1這些個父節點選擇元素時，就會破壞穩定性。有可能第n / 2個父節點交換把後面一個元素交換過去了，而第n / 2 – 1個父節點把後面一個相同的元素沒 有交換，那麼這2個相同的元素之間的穩定性就被破壞了。所以，堆排序不是穩定的排序演算法。C.快速排序（Quick sort）是對氣泡排序的一種改進，採用的是分治的思想。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩定性打亂，比如序列為5 3 3 4 3 8 9 10 11，現在中樞元素5和3（第5個元素，下標從1開始計）交換就會把元素3的穩定性打亂，所以快速排序是一個不穩定的排序演算法，不穩定發生在中樞元素和a[j] 交換的時刻。D.插入排序（Insertion sort ）　　插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那麼插入元素把想插入的元素放在相等元素的後面。所以，相等元素的前後順序沒有改變，從原無序序列出去的順序就是排好序後的順序，所以插入排序是穩定的。