排序算法的稳定性问题

排序算法的稳定性是指：在待排序的记录序列中，存在多个相同的关键字的记录，经过排序以后，相同关键字的顺序若不变，则称此排序算法是稳定的。

今天介绍两种简单的排序算法稳定性：选择排序和插入排序。

选择排序：每趟从待排序的记录中选出关键字最小的记录，放在已排序记录的末尾，与原来末尾上的值交换位置，直到排序结束为止。

例如：     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

从以上过程可以看出，插入排序没有改变相等位置的前后顺序，所以它是一个稳定的排序算法。