采用部分快速排序算法實作數組的部分排序
Author: 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
兩次一趟排序後，前2條排序記錄已經算出，但從結果可以看出，這時整個數列并沒有被完全排序，因為我們不需要完整的排序數列。 第二輪的演化過程請參考嚴蔚敏的資料結構教材，采用的是相同的算法。
下面來分析一下部分快速排序的時間複雜度
理想情況
我們假設理想情況下，每次基準都選擇在數列的中間位置，那麼其掃描的趟數是
1 + 1/2 + 1/4 + 1/8 ... 1/ K (K = log(M/N)) + NlogN
這個等比級數，如果K趨近為無窮的時候值為2，為什麼是2，參考高等數學，這裡不多闡述。
那麼現在我們可以看出，在這種情況下時間複雜度 < O(2M + NlogN), 當N遠小于M時，時間複雜度近似為小于 O(2M)
這個時間複雜度在N>4時要比部分堆排序的 O（MlogN)要小，而且随着N 的增大，部分快速排序的優勢越來越明顯。
最佳情況
最佳情況并不是每次基準都出現的中間位置，而是第一趟排序選擇的基準正好位于第N個位置。這時時間複雜度為O(M)
最壞情況
每次基準出現在M-i 的位置，這時時間複雜度為 O (M*M)
下面是測試結果：
測試1 數組中為随機資料，數組長度M從2的16次方到2的22次方，N=100，每組長度下測試100次計算平均用時
| 平均用時(機關毫秒)/ 數組長度 | 65536 | 131072 | 262144 | 524288 | 1024857 | 2097152 | 41944304 |
| 部分快速排序 | 0.55 | 1.61 | 3.13 | 7.46 | 13.04 | 30.1 | 62.96 |
| 完全快速排序 | 10.45 | 21.85 | 45.55 | 93.97 | 197.3 | 405.54 | 841.75 |
測試2 數組中為以排序好的資料，數組長度M從2的16次方到2的22次方，N=100，每組長度下測試100次計算平均用時
| 平均用時(機關毫秒)/ 數組長度 | 65536 | 131072 | 262144 | 524288 | 1024857 | 2097152 | 41944304 |
| 部分快速排序 | 0.03 | 0.11 | 1.12 | 3.04 | 6.66 | 12.87 | |
| 完全快速排序 | 2.12 | 4.9 | 10.49 | 21.6 | 44.29 | 91 | 185.77 |
從測試結果看采用部分快速排序擷取前100條有序記錄要比采用完全快速排序要快10到100倍。
下面給出代碼，由于.Net的Array.Sort就是完全快速排序，是以直接使用，沒有自己實作完全快速排序。
QuickSort 類
using System;
using System.Collections.Generic;
using System.Text;
namespace Sort
{
/// <summary>
/// Quick Sort
/// </summary>
/// <typeparam name="T"></typeparam>
public class QuickSort < T >
{
// Partition for int
private static int PartitionInt( int [] array, int low, int high, int pivotIndex)
{
int pivotValue = array[pivotIndex];
array[pivotIndex] = array[low];
array[low] = pivotValue;
while (low < high)
{
while (array[high] >= pivotValue && high > low)
{
-- high;
}
if (high > low)
{
array[low] = array[high];
}
while (array[low] <= pivotValue && high > low)
{
++ low;
}
if (high > low)
{
array[high] = array[low];
}
}
array[low] = pivotValue;
return low;
}
// Partition for long
private static int PartitionLong( long [] array, int low, int high, int pivotIndex)
{
long pivotValue = array[pivotIndex];
array[pivotIndex] = array[low];
array[low] = pivotValue;
while (low < high)
{
while (array[high] >= pivotValue && high > low)
{
-- high;
}
if (high > low)
{
array[low] = array[high];
}
while (array[low] <= pivotValue && high > low)
{
++ low;
}
if (high > low)
{
array[high] = array[low];
}
}
array[low] = pivotValue;
return low;
}
// Normal Partition
private static int Partition(T[] array, int low, int high, int pivotIndex, IComparer < T > comparer)
{
if (comparer == null )
{
Array arr = array;
if ( typeof (T) == typeof ( int ))
{
return PartitionInt(( int [])arr, low, high, pivotIndex);
}
else if ( typeof (T) == typeof ( long ))
{
return PartitionLong(( long [])arr, low, high, pivotIndex);
}
}
T pivotValue = array[pivotIndex];
T pLow = array[low];
while (low < high)
{
while (comparer.Compare(array[high], pivotValue) >= 0 && high > low)
{
-- high;
}
if (high > low)
{
array[low] = array[high];
}
while (comparer.Compare(array[low], pivotValue) <= 0 && high > low)
{
++ low;
}
if (high > low)
{
array[high] = array[low];
}
}
array[low] = pLow;
return low;
}
public static void TopSort(T[] array, int top)
{
TopSort(array, top, null );
}
public static void TopSort(T[] array, int top, IComparer < T > comparer)
{
// If comparer is null
if (comparer == null )
{
Array arr = array;
if ( typeof (T) != typeof ( int ) &&
typeof (T) != typeof ( long ))
{
Array.Sort(array);
return ;
}
}
// Judge input
if (array.Length <= 2 || top >= array.Length / 2 )
{
Array.Sort(array, comparer);
return ;
}
// One time partition
int pivot = Partition(array, 0 , array.Length - 1 , array.Length / 2 , comparer);
int lastPivot = pivot;
// Run until pivot near the top
while (( ! (lastPivot >= top && pivot <= top)))
{
lastPivot = pivot;
if (pivot > top)
{
pivot = Partition(array, 0 , pivot, pivot / 2 , comparer);
if (pivot == lastPivot)
{
pivot -- ;
}
}
else
{
if (pivot >= array.Length - 1 )
{
lastPivot = array.Length - 1 ;
break ;
}
pivot = Partition(array, pivot + 1 , array.Length - 1 , (array.Length - pivot) / 2 , comparer);
}
}
// Finally sort
if (lastPivot < array.Length)
{
Array.Sort(array, 0 , lastPivot + 1 , comparer);
}
else
{
Array.Sort(array, 0 , lastPivot, comparer);
}
}
}
}
測試代碼
static void Main( string [] args)
{
int [] testArr = null ;
int [] testArr1 = null ;
Stopwatch sw = new Stopwatch();
List < int > testValues = new List < int > ();
Random rand = new Random();
int pow = 16 ;
int count = ( int )Math.Pow( 2 , pow);
int top = 100 ;
while (pow < 23 )
{
Console.WriteLine( string .Format( " Test count={0} " , count));
double topSortElapsedMilliseconds = 0 ;
double fullSortElapsedMilliseconds = 0 ;
for ( int j = 0 ; j < 100 ; j ++ )
{
testValues.Clear();
for ( int i = 0 ; i < count; i ++ )
{
testValues.Add(rand.Next());
// testValues.Add(i);
}
testArr = new int [testValues.Count];
testArr1 = new int [testValues.Count];
testValues.CopyTo(testArr);
testValues.CopyTo(testArr1);
sw.Reset();
sw.Start();
Sort.QuickSort < int > .TopSort(testArr, top);
sw.Stop();
topSortElapsedMilliseconds += sw.ElapsedMilliseconds;
sw.Reset();
sw.Start();
Array.Sort(testArr1);
sw.Stop();
fullSortElapsedMilliseconds += sw.ElapsedMilliseconds;
// Compare result
for ( int i = 0 ; i < top; i ++ )
{
if (testArr[i] != testArr1[i])
{
Console.WriteLine( string .Format( " Wrong at {0}! {1} {2} " ,
i, testArr[i], testArr1[i]));
Console.ReadKey();
// For test
while ( true )
{
testValues.CopyTo(testArr);
Sort.QuickSort < int > .TopSort(testArr, top);
}
}
}
}
Console.WriteLine( string .Format( " Top sort elapses {0} ms " ,
topSortElapsedMilliseconds / 100 ));
Console.WriteLine( string .Format( " Full sort elapses {0} ms " ,
fullSortElapsedMilliseconds / 100 ));
count *= 2 ;
pow ++ ;
}
Console.ReadKey();
}