Tag Archives: 快速排序

稳定版快速排序算法

我们知道常规的快速排序算法是一个不稳定的算法,也就是两个相等的数排序之后的顺序可能和在原序列中的顺序不同。这是因为当选定一个枢轴(pivot),要把其他数分到小于pivot和大于pivot的两边的时候,不同实现的分法不一样。

下面我实现了一种稳定版快速排序算法,在Partition函数中保持了原序列中所有元素的相对顺序,只把pivot放到了它的正确位置。具体方法是三遍扫描原序列:1)第一遍先把小于pivot的元素按先后顺序放到tmp里,然后把pivot放到它的正确位置tmp[k];2)第二遍把大于pivot的元素按先后顺序追加在tmp里,这样除了pivot以前的其他元素,都保持了和原序列中一样的顺序;3)第三遍把tmp赋值回原数组A。

当排序算法稳定之后,就可以借此统计逆序数了,文件Q5.txt中共包含100000个不同的整数,每行一个数。我们可以使用稳定版快速排序算法对其排序,并统计出其中的逆序数个数。 Continue reading