快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據段變成有序序列。
過程:
每趟調用都要選擇一個基准元素,將待處理段按這個基准數據進行劃分,即左邊的元素都小於等於基准元素,而右邊都大於等與基准元素.
針對下面的算法,注意掃描過程是右->左->右->左....這樣交替進行的, 算法首先把基准元素保存到temp中,這樣數組就空出一個位置了(i 指向的位置) ,接著從右邊開始掃描尋找比temp小的元素,找到後將元素覆蓋到 i 指向的位置(i 中的元素已經放到temp中了),接著換左邊開始掃描(i中元素是有效數據,這時j 指向的空間是交換空間),左邊掃描時逐1增加i的數值,直到找到一個Array[i]>temp,將array[i]保存到arra[j]中,j 指向的空間是交換空間,接著再換右邊開始掃描,如果到i=j都沒找到符合條件的元素就表示i(i=j)位置就是temp元素應該存放的位置了,上面過程可以看到i或j其中必然有一個指向交換空間(元素已經被移動,裡面的內容沒有意義了,在C#的引用類型中這個就是一個指針數據)而當i=j時可以放心的執行array[i]=temp 或array[j]=temp 操作,將基准元素放會到數組排序後對應的位置.
關鍵點: 選擇基准元素是隨機的(一般是第一個)因此這個元素的位置是不確定的,(不要老以為它應該放到數組的中間位置),而上面的操作實質上都是圍繞給基准元素找到一個合適位置進行的,執行上面描述的過程後, 只要基准元素找到位置則可. 比方數組的第一個元素是23,而23是數組的最小元素,那麼根據上面過程執行後會發現最後i=j=0, 那麼array[i]=temp 將把23放回array[0]位置.這樣繼續遞歸時左邊的遞歸調用直接返回,而右邊則是少一個元素的QuickSort.
說明: 快速排序是不穩定排序,即兩個等價元素其先後(左右)位置與排序前不統一,比方 x1,.....x2 ,排序後有可能是 ...x2,x1...,這樣的形式.
C#代碼實現
-----------------------------------------
public class QuickSort<T>
{
public static void Sort(T[] array, IComparer<T> comparer)
{
Sort(array, 0, array.Length - 1, comparer);
}
/// <summary>
/// 注意這裡注意掃描過程的處理
/// 元素移動後,那麼它原來的位置就用來當臨時空間來使用了
/// 而i或j其中一個始終指向這個臨時空間,當i=j時,表示掃描結束
/// 最後array[i]=temp,將選擇的中間元素放回到數組裡(排序後對應的位置)
/// </summary>
/// <param name="array"></param>
/// <param name="L"></param>
/// <param name="h"></param>
/// <param name="comparer"></param>
private static void Sort(T[] array, int L, int h, IComparer<T> comparer)
{
T temp;
int i, j;
if (L < h)//至少有2個元素
{
//選擇第一個元素為基准元素,從右開始掃描
temp = array[L]; i = L; j = h;
while (i < j)
{
//選擇 array[j] < temp的元素,將其移動到前面 i 指向的位置
//而移動後的空間可空出來做下次交換使用,這時j為這個空間的下標
while (i < j && comparer.Compare(temp, array[j]) <= 0) j--;
//i<j 表示找到一個小於temp的元素
if (i < j) array[i] = array[j];
//從左邊開始掃描大於temp的元素
while (i < j && comparer.Compare( array[i],temp) <= 0) i++;
//i< j表示找到一個大與
if (i < j) array[j] = array[i];
}
//這裡有i=j;temp元素找到自己的位置了,
//左變的都比temp小,右邊的都比temp大(或者等於)
array[i] = temp;
Sort(array, L, i - 1, comparer);//完成左邊
Sort(array, i + 1, h, comparer);//完成右邊
}
}
}
------------------------------
另外在.net2.0中的很多集合類其中的Sort方法使用的都是快速度排序實現的,因此進行集合排序時不需要自己專門實現這麼個排序方法.
從Reflector摘錄的部分代碼
---------------------------------
private void QuickSort<TValue>(T[] keys, TValue[] values, int left, int right, IComparer<T> comparer)
{
do
{
int a = left;
int b = right;
int num3 = a + ((b - a) >> 1); //中間值下標,等價於 a+ (b-a)/2
this.SwapIfGreaterWithItems<TValue>(keys, values, comparer, a, num3);
this.SwapIfGreaterWithItems<TValue>(keys, values, comparer, a, b);
this.SwapIfGreaterWithItems<TValue>(keys, values, comparer, num3, b);
T y = keys[num3];
.............................
這裡在排序前先進行"三者取中",即比較這3個元素的大小取中間值做為基准,另外上面類的掃描過程不是交替進行的,而是兩邊同時掃描(可能找到2個後互換),具體參考Reflector後的代碼,下面給出鏈接中的算法分析有"三者取中"的說明.
參考
快速排序算法原理與實現
算法分析(網站名稱: 數據結構)
