以Ai与Aj为例子
快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],
其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的
j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,
i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。
交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的
时候,很有可能把前面的元素的稳定性打乱,比如序列5 3 3 4 3 8 9 10 11,
现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱
,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j]交换的时刻。
参考资料:http://hi.baidu.com/lovebenxiaohai/blog/item/20b6b6349fd2a4b0d1a2d32e.html