WEB开发网
开发学院软件开发C语言 c#与算法--快速排序 阅读

c#与算法--快速排序

 2009-05-25 08:29:15 来源:WEB开发网   
核心提示: 4,向后移动头指针 i ,使其指向从数列头部算起首个大于枢轴(即14)的元素,并将该元素置换到尾指针 j 指向的位置._nArray[j] =_nArray[i].示意图如下:此处同样可以理解为 j 指针指向处的值已在上一步操作中置换了出去. j 处已是一个空位.5,如此重复执行步骤3和步

4,向后移动头指针 i ,使其指向从数列头部算起首个大于枢轴(即14)的元素,并将该元素置换到尾指针 j 指向的位置._nArray[j] =_nArray[i].示意图如下:

c#与算法--快速排序      

此处同样可以理解为 j 指针指向处的值已在上一步操作中置换了出去. j 处已是一个空位.

5,如此重复执行步骤3和步骤4,直至 i==j 时结束该循环.

6,退出了该循环后, i 与 j 必定指向同一位置.在该位置的前部元素,其值均小于枢轴.而在该位置的后部元素,其值均大于枢轴.显而易见,此时 i 和 j 同时指向的位置就应该是枢轴的"新家"._nArray[i]=nPivot.如下图:

c#与算法--快速排序      

至此,一趟排序结束.待排序数列的首元素将该数列分成了比其小和比其大的两部分.如下图:

c#与算法--快速排序

接着,我们对这一大一小两部分子数列执行相同的排序操作.

如此"递归",直至对整个数列完成排序操作.

以下是c#实现代码:

 1using System;
 2
 3public 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                //从右到左,寻找首个小于nPivot的元素
15                while (_pnArray[j] >= nPivot && i<j) j--;
16                //执行到此,j已指向从右端起首个小于nPivot的元素
17                //执行替换
18                _pnArray[i] = _pnArray[j];
19                //从左到右,寻找首个大于nPivot的元素
20                while (_pnArray[i] <= nPivot && i<j) i++;
21                //执行到此,i已指向从左端起首个大于nPivot的元素
22                //执行替换
23                _pnArray[j] = _pnArray[i];
24            }
25
26            //推出while循环,执行至此,必定是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            //对枢轴的左端进行排序
38            QuickSort(_pnArray, _pnLow, _nPivotIndex-1);
39            //对枢轴的右端进行排序
40            QuickSort(_pnArray, _nPivotIndex + 1,_pnHigh);
41        }
42
43        public static void Main()
44        {
45            Console.WriteLine("请输入待排序数列(以","分割):");
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("排序后的数列为:");
56            foreach (int _n in _nArray)
57            {
58                Console.WriteLine(_n.ToString());
59            }
60        }
61    }
62}
63

上一页  1 2 

Tags:算法 快速 排序

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接