金喜正规买球

      从事.net工作两年,当初学到的数据结构算法一直没有在实际工作中用到.近日闲来无事,突发奇想要温习一下简单的数据结构算法.今日,用了一个下午的时间完成了排序中的"快速排序",以此作为入驻博客园的首篇随笔!思想向后,是否将其放到金喜正规买球?最后,还是厚着脸皮,大着胆子决定放.但始终战战兢兢,心中不免忐忑.虽然内容很简单,但确实我是在用心写,希望它能够被人看到.好了,闲话少叙,在下已做好挨骂准备!如果管理员觉得此文不妥,就请随意处置吧,呵呵.

      快速排序 是采用递归的方式对待排序的数列进行若干次的操作,每次操作使得被操作的数列部分以某个元素为分界值分成两部分,一部分小于该分界值,另一部分大于该分界值.该分界值一般被称为"枢轴".

 ;     以数列 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#实现代码:

 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   &nbsp;      &nbsp; while (i < j)
13          &nbsp; { 
14   &nbsp;       &nbsp;    //从右到左,寻找首个小于nPivot的元素
15                ;while (_pnArray[j] >= nPivot && i<j) j--;
16    &nbsp;           //执行到此,j已指向从右端起首个小于nPivot的元素
17     ;          &nbsp;//执行替换
18    &nbsp;  &nbsp;        _pnArray[i] = _pnArray[j];
19                //从左到右,寻找首个大于nPivot的元素
20 &nbsp;        ;      while (_pnArray[i] <= nPivot && i<j) i++;
21    &nbsp;           //执行到此,i已指向从左端起首个大于nPivot的元素
22         &nbsp;      //执行替换
23                _pnArray[j] = _pnArray[i];
24  &nbsp;         }
25
26           &nbsp;//推出while循环,执行至此,必定是i=j的情况
27   &nbsp;        //i(或j)指向的即是枢轴的位置,定位该趟排序的枢轴并将该位置返回
28 &nbsp;   &nbsp;      _pnArray[i] = nPivot;
29        &nbsp;   return i;
30        }
31
32        private static void QuickSort(int[] _pnArray, int _pnLow, int _pnHigh)
33        {
34    ;        if (_pnLow >= _pnHigh) return;
35
36     &nbsp;      int _nPivotIndex = QuickSort_Once(_pnArray, _pnLow, _pnHigh);
37       &nbsp;    //对枢轴的左端进行排序
38  &nbsp;         QuickSort(_pnArray, _pnLow, _nPivotIndex-1);
39            //对枢轴的右端进行排序
40  &nbsp;         QuickSort(_pnArray, _nPivotIndex + 1,_pnHigh);
41        }
42
43        public static void Main()
44        {
45 &nbsp;         Console.WriteLine("请输入待排序数列(以\",\"分割):");
46      &nbsp;     string _s = Console.ReadLine();
47 &nbsp;      &nbsp;   string[] _sArray = _s.Split(",".ToCharArray());
48       ;     int _nLength = _sArray.Length;
49         &nbsp;  int[] _nArray = new int[_nLength];
50       &nbsp;    for (int i = 0; i < _nLength; i++)
51&nbsp;           {
52    &nbsp;           _nArray[i] = Convert.ToInt32(_sArray[i]);
53 ;           }
54            QuickSort(_nArray, 0, _nLength-1);
55 &nbsp;          Console.WriteLine("排序后的数列为:");
56&nbsp;     ;      foreach (int _n in _nArray)
57           &nbsp;{
58                Console.WriteLine(_n.ToString());
59 &nbsp;          }
60        }
61    }
62}
63