C#快速排序算法

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

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

以數(shù)列 14,11,25,37,9,28 為例,詳細(xì)描述執(zhí)行一趟快速排序的算法:

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

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

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

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

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

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

5,如此重復(fù)執(zhí)行步驟3和步驟4,直至 i==j 時(shí)結(jié)束該循環(huán).

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

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

接著,我們對(duì)這一大一小兩部分子數(shù)列執(zhí)行相同的排序操作.

如此"遞歸",直至對(duì)整個(gè)數(shù)列完成排序操作.

以下是c#實(shí)現(xiàn)代碼

        static void Main(string[] args)        {            Console.WriteLine("請(qǐng)輸入待排序數(shù)列(以/",/"分割):");            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; //指向的此時(shí)樞軸的位置        }        private static void QuickSort(List<int> list, int left, int right)        {            if (left < right)            {                int i = Division(list, left, right);                //對(duì)樞軸的左邊部分進(jìn)行排序                QuickSort(list, i + 1, right);                //對(duì)樞軸的右邊部分進(jìn)行排序                QuickSort(list, left, i - 1);            }        }