PARTITION算法的实现

Implementations of PARTITION Algorithms

自 1 96 2年 Hoare提出快速排序算法以来 ,就成为各种程序设计、数据结构和算法等方面教科书的必备例题 .然而其中的 partition算法几乎都采取了二重循环的形式 ,掩盖了 partition的线性本质 ,削弱了程序的可读性 .本文介绍了 Nico Romuto所做的改进 ,最后给出了一种新的实现方法 ,采取了 while- if- else的形式 ,准确表达了 partition的线性本质 。

Quicksort algorithm has been an essential example in all most textbooks on Programming,Data structures and Algorithms,since Hoare presented in 1962. But the PARTITION algorithms in it make use of two layer loop form, which conceals its linear essence, and reduces readability . This paper introduces the modification by Nico Romuto, and present a new implementation which may correctly express the linear essence and improve readability.