采用部分快速排序算法实现数组的部分排序

采用部分快速排序算法实现数组的部分排序2010-11-19 cnblogs eaglet快速排序算法，网上相关文章已经介绍的很多了，数据结构教材中也有很详细的介绍。本文需要阐述的不是全排序快速排序算法，而是部分快速排序算法。所谓部分快速排序算法是指通过排序获取一个数列中最大的若干条有序记录。比如我们需要从一个有1百万记录的数组中获取前100条有序记录，并按从大到小顺序显示给用户，这种应用在搜索引擎中经常被使用，很少会有人有耐心将100万条搜索出来的记录都阅读一遍，一般阅读前几百条纪录就可以得到自己满意的答案。其实这种很像SQLSERVER 中的TOP n 的实现，不过数据库是预先已经将记录通过B+树索引的方式进行了组织，实现方法完全不同。本文需要阐述的是不通过数据库，如何高效完成Top n 这种部分排序的功能。

在开始之前，我们先来分析一下2种其他的排序方法，如果进行部分排序。

1.选择排序

选择排序方法实现部分排序非常简单，如果你需要获取长度为M的数组中前N 条排序记录，你只需要对M条记录进行N次扫描，每次扫描都找出剩余序列中的最大（或最小值）就可以完成。当N 远小于 M 时，选择排序的时间复杂度大概为 O（M*N）。

2.堆排序

对排序可以说是实现部分排序时最常被用到的算法，包括著名的搜索组件 Lucene在内都采用了堆排序来实现部分排序。具体算法我在网上找了一个，请参见部分排序问题。根据这篇文章所述，堆排序实现部分排序的实现复杂度是 O（MlogN）

现在让我们开始部分快速排序算法。

快速排序的一趟排序，可以根据一个基准值将数组分割成两个部分，基准前的所有数都比基准小，基准后的所有数都比基准大。如上图所示，5 就是这个基准值。全排序的快速排序算法，在实现了一趟排序后，通过递归分别对基准前后的数列再进行相同的排序直到所有数据都有序。

我们可以巧妙的利用这种基准分割的方法来实现部分排序。如果要实现部分排序，我们不需要对所有的数据都进行排序，其实每次只需要对基准的一边进行一趟排序就可以了，其原理很像二分查找。如上图，如果我们希望得到最小的前 2个排序数据，我们只需要在第二次排序时对5之前的数列重新做一次一趟排序，而不需要对5之后的数据做，因为5在一趟排序后被排在了第6位，其之后的数据肯定不可能出现在前2位。假设第二次我们选取5之前的数列的中间位置的值2作为基准，那么第二次一趟排序的过程如下

3 4 2 1 5 5 9 8 7

_ 4 3 1 5 5 9 8 7 （2）

1 4 3 _ 5 5 9 8 7 （2）

1 _ 3 4 5 5 9 8 7 （2）

1 2 3 4 5 5 9 8 7