日韩在线亚洲,亚洲一级婬片,天天操一操

c#與算法--快速排序

原創(chuàng)|其它|編輯：郝浩|2009-04-27 09:55:21.000|閱讀 389 次

概述： 從事.net工作兩年,當(dāng)初學(xué)到的數(shù)據(jù)結(jié)構(gòu)算法一直沒有在實(shí)際工作中用到.近日閑來無事,突發(fā)奇想要溫習(xí)一下簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)算法.今日,用了一個(gè)下午的時(shí)間完成了排序中的"快速排序"。

# 界面/圖表報(bào)表/文檔/IDE等千款熱門軟控件火熱銷售中 >>

從事.net工作兩年,當(dāng)初學(xué)到的數(shù)據(jù)結(jié)構(gòu)算法一直沒有在實(shí)際工作中用到.近日閑來無事,突發(fā)奇想要溫習(xí)一下簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)算法.今日,用了一個(gè)下午的時(shí)間完成了排序中的"快速排序",以此作為入駐博客園的首篇隨筆!思想向后,是否將其放到金喜正規(guī)買球?最后,還是厚著臉皮,大著膽子決定放.但始終戰(zhàn)戰(zhàn)兢兢,心中不免忐忑.雖然內(nèi)容很簡(jiǎn)單,但確實(shí)我是在用心寫,希望它能夠被人看到.好了,閑話少敘,在下已做好挨罵準(zhǔn)備!如果管理員覺得此文不妥,就請(qǐng)隨意處置吧,呵呵.

快速排序 是采用遞歸的方式對(duì)待排序的數(shù)列進(jìn)行若干次的操作,每次操作使得被操作的數(shù)列部分以某個(gè)元素為分界值分成兩部分,一部分小于該分界值,另一部分大于該分界值.該分界值一般被稱為"樞軸".

; 以數(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 必定指向同一位置.在該位置的前部元素,其值均小于樞軸.而在該位置的后部元素,其值均大于樞軸.顯而易見,此時(shí) i 和 j 同時(shí)指向的位置就應(yīng)該是樞軸的"新家"._nArray[i]=nPivot.如下圖:

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

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

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

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

using System;
2

public class Sort
4{
5    public class Quick_Sort
6    {
7        private static int QuickSort_Once(int[] _pnArray, int _pnLow, int _pnHigh)
8        {
9      ;      int nPivot = _pnArray[_pnLow];      //將首元素作為樞軸
10            int i = _pnLow, j = _pnHigh;
11
12            while (i < j)
13            {
14                //從右到左,尋找首個(gè)小于nPivot的元素
15                ;while (_pnArray[j] >= nPivot && i<j) j--;
16                //執(zhí)行到此,j已指向從右端起首個(gè)小于nPivot的元素
17     ;           //執(zhí)行替換
18                _pnArray[i] = _pnArray[j];
19                //從左到右,尋找首個(gè)大于nPivot的元素
20          ;      while (_pnArray[i] <= nPivot && i<j) i++;
21                //執(zhí)行到此,i已指向從左端起首個(gè)大于nPivot的元素
22                //執(zhí)行替換
23                _pnArray[j] = _pnArray[i];
24            }
25
26            //推出while循環(huán),執(zhí)行至此,必定是i=j的情況
27            //i(或j)指向的即是樞軸的位置,定位該趟排序的樞軸并將該位置返回
28            _pnArray[i] = nPivot;
29            return i;
30        }
31
32        private static void QuickSort(int[] _pnArray, int _pnLow, int _pnHigh)
33        {
34    ;        if (_pnLow >= _pnHigh) return;
35
36            int _nPivotIndex = QuickSort_Once(_pnArray, _pnLow, _pnHigh);
37            //對(duì)樞軸的左端進(jìn)行排序
38            QuickSort(_pnArray, _pnLow, _nPivotIndex-1);
39            //對(duì)樞軸的右端進(jìn)行排序
40            QuickSort(_pnArray, _nPivotIndex + 1,_pnHigh);
41        }
42
43        public static void Main()
44        {
45           Console.WriteLine("請(qǐng)輸入待排序數(shù)列(以\",\"分割):");
46            string _s = Console.ReadLine();
47            string[] _sArray = _s.Split(",".ToCharArray());
48       ;     int _nLength = _sArray.Length;
49            int[] _nArray = new int[_nLength];
50            for (int i = 0; i < _nLength; i++)
51            {
52                _nArray[i] = Convert.ToInt32(_sArray[i]);
53 ;           }
54            QuickSort(_nArray, 0, _nLength-1);
55            Console.WriteLine("排序后的數(shù)列為:");
56      ;      foreach (int _n in _nArray)
57            {
58                Console.WriteLine(_n.ToString());
59            }
60        }
61    }
62}
63

標(biāo)簽：

本站文章除注明轉(zhuǎn)載外，均為本站原創(chuàng)或翻譯。歡迎任何形式的轉(zhuǎn)載，但請(qǐng)務(wù)必注明出處、不得修改原文相關(guān)鏈接，如果存在內(nèi)容上的異議請(qǐng)郵件反饋至chenjj@fc6vip.cn

文章轉(zhuǎn)載自：博客園

上一篇：C#3.0筆記(一)預(yù)備知識(shí)之Delegate 下一篇：詳解AJAX核心 —— XMLHttpRequest 對(duì)象 (下)