快排-荷兰国旗

【摘要】 在使用partition-exchange排序算法时，如快速排序算法，我们会遇到一些问题，比如重复元素太多，降低了效率，在每次递归中，左边部分是空的(没有元素比关键元素小)，而右边部分只能一个一个递减移动。结果导致耗费了二次方时间来排序相等元素。这时我们可以多分一个区，即，小于区，等于区，大于区。（传统快排为小于区和大于区）
 
下面我们通过一个经典例题来练习这种思想。 …

在使用partition-exchange排序算法时，如快速排序算法，我们会遇到一些问题，比如重复元素太多，降低了效率，在每次递归中，左边部分是空的(没有元素比关键元素小)，而右边部分只能一个一个递减移动。结果导致耗费了二次方时间来排序相等元素。这时我们可以多分一个区，即，小于区，等于区，大于区。（传统快排为小于区和大于区）

下面我们通过一个经典例题来练习这种思想。

荷兰国旗问题

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

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

样例输入

      3

      BBRRWBWRRR

      RRRWWRWRB

      RBRW

  


                    
        
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
人工智能