排序算法中的不稳定排序

​​排序算法的稳定性是指两个相同的元素排序后，相对位置不改变。有四种排序算法是不稳定排序:希尔排序，选择排序，快速排序，堆排序。

1.  希尔排序又称缩小增量排序，是直插入排序的改进。有n个待排序元素，以n/2为增量，分组进行排序，每个分组内采用直接插入排序。假设有数组｛3,5,1,2,8,7,6｝,以3为增量，则分组为{3,2},{5,8},{1,7},{6}，组内直接排序后可得｛2，5，1，3，8，7，6｝，以2为增量，排序后可得｛1，3，2，5，6，7，8｝，以1为增量后排序可得｛1，2，3，6，7，8｝。增量排序之所以是不稳定排序，比如有｛2（x），2（y），1，3｝，以2为增量，可得｛1，2（y），2（x），3｝，排序后是不稳定的。

2. 选择排序。每次从待排序的数组中选择最小的一个元素和当前的元素进行替换。以｛3，5，1，2，8，7，6｝为例，指针指向当前元素3，从后面的元素中选择最小元素1和3替换，可得｛1，5，3，2，8，7，6｝，指针指向5，从后面元素中选择最小的元素2和5替换，可得｛1，2，3，5，8，7，6｝。选择排序的特点就是比较的次数和元素的初始顺序无关，无论是无序的还是基本有序，都要比较相同的次数。那么为什么是不稳定排序，比如有｛2（x），2（y），1｝，第一次排序后可得｛2（y），2(x)，1｝，是不稳定的。

3. 快速排序。快速排序是比较复杂的一种排序，原理是随机选中一个元素，一般是第一个，每一趟排序后，把比该元素小的移动到其左边，比它大的移动到其右边，然后对左右两边分别再进行快速排序。每一趟排序其实至少确定了一个元素的位置。以｛3，5，1，2，8，7，6｝为例，选中第一个元素3，从后往前找到第一个比3小的元素，交换位置，可得｛2，5，1，3，8，7，6｝，从前往后找到第一个比3大的元素，交换位置，可得{2，3，1，5，8，7，6}，再从后往前找到第一个比3小的元素，交换位置，可得｛2，1，3，5，8，7，6｝，从前往后找的时候已经没有比3大的元素，从后往前也没有比3小的元素，到这里，第一趟排序完成。此时3在整体中的位置已经确定了。再分别对左右两边进行快速排序。快速排序为什么是不稳定排序？以{2(x)，2(y)，1}为例，第一趟排序后，得到｛2（y），2(x)，1｝，是不稳定的。

4. 堆排序。堆排序用到了堆这个数据结构，堆分为大顶堆和小顶堆。堆是一棵完全二叉树，大顶堆就是父节点的值大于或等于左孩子和右孩子的值，所以大顶堆根节点的值是最大的。对于数组A=｛3，5，1，2，8，7，6｝，可以对应到一棵完全二叉树上，然后经过调整，成为大顶堆或小顶堆。数组下标为i的节点的左孩子对应下标为2i+1，右孩子为2i+2，所以a数组A的根节点为A[0]，左孩子为A[1]，右孩子为A[2]，A[1]的左孩子为A[3]，右孩子为A[4]，然后将其调整为大顶堆。数组长度为n，从n/2-1开始，之所以从n/2-1开始，是要找到所有的非叶子节点，这里n/2-1=2，比较A[2]和左右子树，将最大的值替换到父节点，然后依次比较A[1]和A[0]的左右子数，最大值就移到了根节点，最大值为8。此时将根节点得到的最大值和待排序数组的最后一个值交换，然后对前n-1个待排序的数组继续构造大顶堆，这样每次得到一个最大值，大顶堆也在逐渐变小，直到排序完成。堆排序不需要排序完成就可以得到前k个元素。堆排序为什么是不稳定排序。比如数组{2（x），2(y)，3}，构造大顶堆，第一次构造得到堆顶元素3，此时剩下｛2（x），2(y)｝，再次构造大顶堆得到堆顶元素2（x），最终排序为{2（y），2(x)，3}，是不稳定的。​​​​