Question

为什么快速排序是不稳定的算法

Answer 1

分类: 电脑/网络 >> 程序设计 >> 其他编程语言
问题描述:

我用free pascal

解析:

排序算法不稳定的含义是:

在排序之前,有两个数相等.

但是在排序结束之后,它们两个有可能改变顺序.

比如说:

在一个待排序队列中,A和B相等,且A排在B的前面,而排序之后,A排在了B的后面.这个时候,我们说这种算法是不稳定的.

(只要有这种可能性,我们就说算法是不稳定的.)

注: 算法的不稳定性,与所用的语言没有关系的.

那么,快速排序为什么不稳定呢?

我们来看看快速排序的过程:(还是借用之前的那个假设,假设A,B相等,并和其它一堆数据一起参加排序.)

假设此时的快排是小于等于关键字为排在前面的一组组,大于为另外排在后面的一组.

在选取一个数出来分组的时候,如果选到了A,那么在B<=A的情况下,B将会排在A的前面.

因为有这样的_可能性_,所以说我们这种算法是不稳定的.

注:请参考快排的具体算法.

另外，TO 朱_大志同学,可能我们两个的教材有一定的差别.