罗 可

（邵阳学院 图书馆，湖南 邵阳 422000）

0 引言

在人类各个领域中,数据排序得到了广泛的应用,几乎每一个地方都需要进行数据排序。 经过排序的数据,优点如下:(1)更易读,更易观察。 (2)数据有利于再进一步进行各种统计和整理工作,例如,要确定一组数据的中位数,必须先对数据进行排序,然后才能得出结果。 (3)排序后的数据可大大缩短搜索数据的时间。

随着数据排序技术的不断发展,各种排序算法相继出现。 常用的方法有选择排序法(Selection Sort)、冒泡排序法(Bubble Sort)、插入排序法(Insertion Sort)、希尔排序法(Shell Sort)、快速排序法(Quick Sort)等。 每一种排序算法都有其自身的特点,而且算法有简单和复杂之分。 通常简单的排序算法完成排序的速度较慢,即排序效率较低；复杂的排序算法完成排序的速度较快,排序效率较高。 一般来说,在目前众多的排序方法中,快速排序法(Quick Sort)是一种速度较快的排序算法,有关文献对其进行了大量的论述。 快速排序法的操作原理是在所有数据中选择一个基准键(Pivot),然后利用分割(Partition)方法将数据分成两半,然后再对这两部分进行分割,直到完成排序。 执行快速排序法所需的时间取决于对基准键(Pivot)的选择,同时还建议了许多选择方法,其中大部分的改进方法都是围绕对基准键(Pivot)的选择展开的。 本文探讨的是改进分割(Partition)算法,通过这种方法能否提高快速排序法的运行时间。

1 相关知识

1.1 快速排序

［2］……data［n］,由小至大排序,其步骤如下。

步骤1:将第1 个数据指定为键值(或称基准键,

Pivot key)。

步骤2:利用指标i 自左而右找到1 个data［i］＞＝pivotkey；