C#快速排序詳解

使用快速排序法對一列數字進行排序的過程

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。

步驟為：

1. 從數列中挑出一個元素，稱為 "基準"（pivot），
2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺放在基準的后面（相同的數可以到任一邊）。在這個分割結束之后，該基準就處于數列的中間位置。這個稱為分割（partition）操作。
3. 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個演算法總會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。

C#算法實現

using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace 快速排序    //***對相同元素, 不穩定的排序算法***{    //相對來說，快速排序數值越大速度越快 。  快速排序是所有排序里面最快的    class PRogram    {        static void Main(string[] args)        {            int[] arr = { 15, 22, 35, 9, 16, 33, 15, 23, 68, 1, 33, 25, 14 }; //待排序數組            QuickSort(arr, 0, arr.Length - 1);  //調用快速排序函數。傳值(要排序數組，基準值位置，數組長度)            //控制臺遍歷輸出            Console.WriteLine("排序后的數列：");            foreach (int item in arr)                Console.WriteLine(item);        }        private static void QuickSort(int[] arr, int begin, int end)        {            if (begin >= end) return;   //兩個指針重合就返回，結束調用            int pivotIndex = QuickSort_Once(arr, begin, end);  //會得到一個基準值下標            QuickSort(arr, begin, pivotIndex - 1);  //對基準的左端進行排序  遞歸            QuickSort(arr, pivotIndex + 1, end);   //對基準的右端進行排序  遞歸        }        private static int QuickSort_Once(int[] arr, int begin, int end)        {            int pivot = arr[begin];   //將首元素作為基準            int i = begin;            int j = end;            while (i < j)            {                //從右到左，尋找第一個小于基準pivot的元素                while (arr[j] >= pivot && i < j) j--; //指針向前移                arr[i] = arr[j];  //執行到此，j已指向從右端起第一個小于基準pivot的元素，執行替換                //從左到右，尋找首個大于基準pivot的元素                while (arr[i] <= pivot && i < j) i++; //指針向后移                arr[j] = arr[i];  //執行到此,i已指向從左端起首個大于基準pivot的元素，執行替換            }            //退出while循環,執行至此，必定是 i= j的情況（最后兩個指針會碰頭）            //i(或j)所指向的既是基準位置，定位該趟的基準并將該基準位置返回            arr[i] = pivot;            return i;        }    }}