2000年东北大学 · 快速排序 · 考研题

在起泡(冒泡)排序过程中,有的关键字在某趟排序中可能朝着与最终排序相反的方向移动,请举例说明之。

快速排序过程中有没有这种现象?

提示

起泡排序每一趟只能将序列中最大(或最小)关键字移到正确位置,其它关键字可能在相互交换中朝着与最终排序相反的方向移动。

快速排序每一趟不仅能将枢轴记录移动到正确位置,而且其它记录移动的方向也和其最终的位置方向一致。

答案

例如(4,3,2,1),第一趟起泡后为(3,2,1,4),关键字3的位置被移动到首位,朝着与最终排序相反的方向移动。

快速排序过程中没有此现象。因为经过一趟排序的划分所确定的枢轴记录的位置就是此记录最终的位置,而且所有比枢轴记录小的记录均被移到枢轴之前,所有比枢轴记录大的记录均被移到枢轴右之后。

笔记