你的位置:首页 > 软件开发 > Java > 快速排序深入之荷兰国旗问题

快速排序深入之荷兰国旗问题

发布时间:2015-05-31 12:00:13
一、序言  在使用partition-exchange排序算法时,如快速排序算法(即使选择了一个好的关键元素pivot values),我们往往面临一个很尴尬的境地--当排序对象中有很多重复的元素,partition-exchange排序算法表现很不尽如人意。当所有元素都相等时, ...

一、序言

  在使用partition-exchange排序算法时,如快速排序算法(即使选择了一个好的关键元素pivot values),我们往往面临一个很尴尬的境地--当排序对象中有很多重复的元素,partition-exchange排序算法表现很不尽如人意。当所有元素都相等时,这就特别容易理解了。在每次递归中,左边部分是空的(没有元素比关键元素小),而右边部分只能一个一个递减移动。结果导致耗费了二次方时间来排序相等元素。为了解决这个问题(有时叫做荷兰国旗问题),我们详细介绍下解决这个问题的方法。

 

二、”荷兰国旗难题“问题描述

  ”荷兰国旗难题“是计算机科学中的一个程序难题,它是由Edsger Dijkstra提出的。荷兰国旗是由红、白、蓝三色组成的。

      快速排序深入之荷兰国旗问题

  现在有若干个红、白、蓝三种颜色的球随机排列成一条直线。现在我们的任务是把这些球按照红、白、蓝排序。

快速排序深入之荷兰国旗问题

 

三、问题分析

  

 

这个问题我们可以将这个问题视为一个数组排序问题,这个数组分为前部,中部和后部三个部分,每一个元素(红白蓝分别对应0、1、2)必属于其中之一。由于红、白、蓝三色小球数量并不一定相同,所以这个三个区域不一定是等分的,也就是说如果我们将整个区域放在[0,1]的区域里,由于三色小球之间数量的比不同(此处假设1:2:2),可能前部为[0,0.2),中部为[0.2,0.6),后部为[0.6,1]。我们的思路如下:将前部和后部各排在数组的前边和后边,中部自然就排好了。具体的:

原标题:快速排序深入之荷兰国旗问题

关键词:排序

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。