C#快速排序算法

　　今天重溫了下排序算法，包括冒泡排序法和直接排序法，這些都比較簡單，只是快速排序法比較難，于是重點研究了下。

　　先說一說原理：快速排序法是采用遞歸的方式對待排序的數列進行若干次的操作,每次操作使得被操作的數列部分以某個元素為分界值分成兩部分,一部分小于該分界值,另一部分大于該分界值.該分界值一般被稱為"樞軸". 一般先以左邊第一個數作為分界值，將數列按該分界值分成左右兩部分，左邊部分小于該分界值，右邊部分大于該分界值，然后再對左右兩部分做重復的操作，直到最后完成排序。

以數列 14,11,25,37,9,28 為例,詳細描述執行一趟快速排序的算法:

1,選擇待排序數列的樞軸,一般以數列的首元素作為樞軸.此數列中,我們選擇首元素14作為樞軸,nPivot = 14.

2,設定兩個指針 i 和 j ,分別指向數列的首元素和尾元素. i 指向首元素14, j 指向尾元素28.示意圖如下:

3,向前移動尾指針 j ,使其指向從數列尾部算起首個小于樞軸(即14)的元素,并將該元素置換到頭指針 i 指向的位置._nArray[i] =_nArray[j].示意圖如下:

首次執行該操作時 i 指針指向處的值實際上就是樞軸的值,此處的操作可以理解為 i 指針指向處的值已在之前被置換到樞軸中,此時, i 指向處已經是一個空位,在此時用找到的小于樞軸的元素填在此處.

4,向后移動頭指針 i ,使其指向從數列頭部算起首個大于樞軸(即14)的元素,并將該元素置換到尾指針 j 指向的位置._nArray[j] =_nArray[i].示意圖如下:

此處同樣可以理解為 j 指針指向處的值已在上一步操作中置換了出去. j 處已是一個空位.

5,如此重復執行步驟3和步驟4,直至 i==j 時結束該循環.

6,退出了該循環后, i 與 j 必定指向同一位置.在該位置的前部元素,其值均小于樞軸.而在該位置的后部元素,其值均大于樞軸.顯而易見,此時 i 和 j 同時指向的位置就應該是樞軸的"新家"._nArray[i]=nPivot.如下圖:

至此,一趟排序結束.待排序數列的首元素將該數列分成了比其小和比其大的兩部分.如下圖:

接著,我們對這一大一小兩部分子數列執行相同的排序操作.

如此"遞歸",直至對整個數列完成排序操作.

以下是c#實現代碼

        static void Main(string[] args)        {            Console.WriteLine("請輸入待排序數列(以/",/"分割):");            string _s = Console.ReadLine();            string[] _sArray = _s.Split(",".ToCharArray());            int _nLength = _sArray.Length;            int[] _nArray = new int[_nLength];            for (int i = 0; i < _nLength; i++)            {                _nArray[i] = Convert.ToInt32(_sArray[i]);            }            var list = _nArray.ToList();            QuickSort(list, 0, _nLength - 1);            foreach (var i in list)            {                 Console.WriteLine(i.ToString());            }            while (true)            {                Thread.Sleep(10000);            }       }        //獲取按樞軸值左右分流后樞軸的位置        PRivate static int Division(List<int> list, int left, int right)        {            while (left < right)            {                int num = list[left]; //將首元素作為樞軸                if (num > list[left + 1])                 {                    list[left] = list[left + 1];                    list[left + 1] = num;                    left++;                }                else                {                    int temp = list[right];                    list[right] = list[left + 1];                    list[left + 1] = temp;                    right--;                }                Console.WriteLine(string.Join(",", list));            }            Console.WriteLine("--------------/n");            return left; //指向的此時樞軸的位置        }        private static void QuickSort(List<int> list, int left, int right)        {            if (left < right)            {                int i = Division(list, left, right);                //對樞軸的左邊部分進行排序                QuickSort(list, i + 1, right);                //對樞軸的右邊部分進行排序                QuickSort(list, left, i - 1);            }        }