各种排序算法的稳定性.doc

首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj, Ai原来在位置前,排序后Ai还是要在Aj位置前。为了简便下面讨论的都是不降序排列的情形,对于不升序排列的情形讨论方法和结果完全相同。 
    其次,说一下稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,对基于比较的排序算法而言,元素交换的次数可能会少一些(个人感觉,没有证实)。
    回到主题,现在分析一下常见的排序算法的稳定性,每个都给出简单的理由。
(1)冒泡排序
    冒泡排序是通过相邻比较、实时交换、缩小范围实现排序的。第1次操作n个元素,通过相邻比较将0~n-1中的最大元素交换到位置n-1上,第2次操作n-1个元素,通过相邻比较将0~n-2中的最大元素交换到位置n-2上……第n-1次操作2个元素,通过相邻比较将0~1上的最大元素交换到位置1上完成排序。在相邻比较时如果两个元素相等,一般不执行交换操作,因此冒泡排序是一种稳定排序算法。
(2)选择排序
    选择排序是通过不断缩小排序序列长度来实现的。第1次操作n个元素,选择0~n-1中的最小者交换到位置0上,第2次操作n-1个元素,选择1~n-1中的最小者交换到位置1上……第n-1次操作2个元素,选择n-2~n-1上的最小者交换到位置n-2上完成排序。在每次选择最小元素进行交换时,可能破坏稳定性。这种情况可以描述为:约定要发生交换的位置称为当前位置,被交换的位置称为被交换位置,被交换位置上的元素为选中的最小元素。如果当前位置之后和被交换位置之前存在与当前位置相等的元素,执行交换后就破坏了稳定性。如序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。
(3)插入排序
    插入排序是通过不断扩大排序序列的长度来实现的。第1次操作1个元素,直接放到位置0上即可;第2次操作2个元素,在0~1上为当前元素找到合适位置并插入;第3次操作3个元素,用在0~2上为当前元素找到合适位置并插入它……第n次操作
n个元素,在0~n-1上为当前元素找到合适位置并插入完成排序。讨论元素的插入过程,假设当前是第n次操作,要在0~n-1上为当前元素寻找合适位置,设置一个工作指针初始化为n-1,向前移动工作指针直到遇到一个不大于当前元素的元素,就在这个元素的后面插入当前元素,仔细体会这个插入过程,不难理解插入排序是稳定的。
(4)快速排序
    快速排序有两个方向,左边的i下标当a[i] <= a[center]时一直往右走,其中center是中枢元素的数组下标,一般取为当前排序段的第一个元素。而右边的j下标当a[j] > a[center]时一直往左走。如果i和j都走不动了,这时必有结论a[i] > a[center] >= a[j],我们的目的是将a分成不大于a[center]和大于a[center]的两个部分,其中前者位于左半部