排序算法中的不稳定排序

sxyyu 2019-10-21

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

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},是不稳定的。​​​​

相关推荐