单选题
在快速排序法中,每经过一次数据交换(或移动)后( )。
A
不会产生新的逆序
B
只能消除一个逆序
C
能消除多个逆序
D
消除的逆序个数一定比新产生的逆序个数多
答案解析
正确答案:C
解析:
解析:在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。快速排序的思想是:从线性表中选取一个元素,设为T,将线性表中后面小于T的元素移到前面,而前面大于T的元素移到后面,结果就将线性表分成两部分(称两个子表),T插入到其分害性线的位置处,这个过程称为线性表的分割,然后再用同样的方法对分割出的子表再进行同样的分割。快速排序不是对两个相邻元素进行比较,可以实现通过一次交换而消除多个逆序,但由于均与1(基准元素)比较,也可能会产生新的逆序。本题答案为C选项。
相关知识点:
快排交换后,能消多个逆序
