2.快速排序 ***
一、算法思想
快速排序是C.R.A.Hoare於1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。分治法的基本思想是：將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然後將這些子問題的解組合為原問題的解。
二、快速排序的基本思想
設當前待排序的無序區為R[low..high]，利用分治法可將快速排序的基本思想描述為：
(1)分解：
在R[low..high]中任選一個記錄作為基准(Pivot)，以此基准將當前無序區劃分為左、右兩個較小的子區間R[low..pivotpos-1)和R[pivotpos+1..high]，並使左邊子區間中所有記錄的關鍵字均小於等於基准記錄(不妨記為pivot)的關鍵字pivot.key，右邊的子區間中所有記錄的關鍵字均大於等於pivot.key，而基准記錄pivot則位於正確的位置(pivotpos)上，它無須參加後續的排序。注意：劃分的關鍵是要求出基准記錄所在的位置pivotpos。劃分的結果可以簡單地表示為(注意 pivot=R[pivotpos] )： R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys,
其中low≤pivotpos≤high。(邊界條件)
(2)求解：
通過遞歸調用快速排序對左、右子區間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
(3)組合：
因為當"求解"步驟中的兩個遞歸調用結束時，其左、右兩個子區間已有序。對快速排序而言，"組合"步驟無須做什麼，可看作是空操作。
using System;
namespace QuickSorter
{
public class QuickSort
{
public static void Sort(int[] numArr)
{
Sort(numArr, 0, numArr.Length - 1);
}
private static void Sort(int[] numArr, int left, int right)
{
if (left < right)
{
int middle = numArr[(left + right) / 2];
int i = left - 1;
int j = right + 1;
while (true)
{
while (numArr[++i] < middle) ;
while (numArr[--j] > middle) ;
if (i >= j)
break;
Swap(numArr, i, j);
}
Sort(numArr, left, i - 1);
Sort(numArr, j + 1, right);
}
}
private static void Swap(int[] numArr, int i, int j)
{
int number = numArr[i];
numArr[i] = numArr[j];
numArr[j] = number;
}
}
public class Program
{
static void Main(string[] args)
{
int[] arr = new int[] { 20, 41, 27, 14, 16, 1, 8, 55, 9, 35, 22, 14 };
QuickSort.Sort(arr);
Console.WriteLine("Numbers after quicksort:");
foreach (int i in arr)
{
Console.WriteLine(i);
}
Console.Read();
}
}
}
