Visual C#常用排序算法(4)

4.快速排序

4.1.基本思想：

在當前無序區R[1..H]中任取一個數據元素作為比較的"基准"(不妨記為X)，用此基准將當前無序區劃分為左右兩個較小的無序區：R[1..I-1]和R[I+1..H]，且左邊的無序子區中數據元素均小於等於基准元素，右邊的無序子區中數據元素均大於等於基准元素，而基准X則位於最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當R[1..I-1]和R[I+1..H]均非空時，分別對它們進行上述的劃分過程，直至所有無序子區中的數據元素均已排序為止。

4.2.排序過程：

【示例】：

初始關鍵字 [49 38 65 97 76 13 27 49］

第一次交換後 ［27 38 65 97 76 13 49 49］

第二次交換後 ［27 38 49 97 76 13 65 49］

第三次交換後 ［27 38 13 97 76 49 65 49］

第四次交換後 ［27 38 13 49 76 97 65 49］

［27 38 13 49 76 97 65 49］

（一次劃分過程）

初始關鍵字 ［49 38 65 97 76 13 27 49］

一趟排序之後 ［27 38 13］ 49 ［76 97 65 49］

二趟排序之後 ［13］ 27 ［38］ 49 ［49 65］76 ［97］

三趟排序之後 13 27 38 49 49 ［65］76 97

最後的排序結果 13 27 38 49 49 65 76 97

各趟排序之後的狀態

4.3.程序實現

/// <summary>
/// 快速排序法
/// </summary>
/// <param name="dbArray"></param>
/// <param name="StartIndex"></param>
/// <param name="EndIndex"></param>
private static void QuickSort( ref double[] dbArray ,int StartIndex ,int EndIndex)
{
　//基數
　int CurrentIndex = StartIndex ;
　//順序查找
　bool IsOrderSearched = true ;
　//反序查找
　bool IsDisOrderSearched = true ;
　while(IsOrderSearched || IsDisOrderSearched)
　{
　　IsDisOrderSearched = false ;
　　IsOrderSearched = false ;
　　for(int i =EndIndex ; i>CurrentIndex ;i--)
　　{
　　　if(dbArray[i] < dbArray[CurrentIndex])
　　　{
　　　　ExchangeValue(ref dbArray[i] ,ref dbArray[CurrentIndex]);
　　　　CurrentIndex = i ;
　　　　IsDisOrderSearched = true ;
　　　　break ;
　　　}
　　}
　　for(int i = StartIndex ; i < CurrentIndex ; i++)
　　{
　　　if(dbArray[i] > dbArray[CurrentIndex])
　　　{
　　　　ExchangeValue(ref dbArray[i] ,ref dbArray[CurrentIndex]);
　　　　CurrentIndex = i ;
　　　　IsOrderSearched = true ;
　　　　break ;
　　　}
　　}
　}
　if( EndIndex - StartIndex > 0 )
　{
　　if(CurrentIndex != StartIndex )
　　{
　　　QuickSort(ref dbArray ,StartIndex,CurrentIndex -1);
　　}
　　if(CurrentIndex != EndIndex)
　　{
　　　QuickSort(ref dbArray ,CurrentIndex+1,EndIndex);
　　}
　}
}
/// 交換數據
/// </summary>
/// <param name="A"></param>
/// <param name="B"></param>
private static void ExchangeValue(ref double A , ref double B)
{
　double Temp = A ;
　A = B ;
　B = Temp ;
}