学步园

类别：排序-交换排序
参看 维基百科的定义

using System;<br /> using System.Collections.Generic;<br /> namespace Com.Colobu.Algorithm.Exchange<br /> {<br /> /// <summary><br /> /// <b>快速排序</b>是所有排序<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>中最高效的一种.<br /> /// 它采用了分治的思想：先保证列表的前半部分都小于后半部分，<br /> /// 然后分别对前半部分和后半部分排序，这样整个列表就有序了。<br /> /// 这是一种先进的思想，也是它高效的原因。<br /> /// 因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，<br /> /// 而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后<br /> /// 都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。<br /> ///<br /> /// 平均时间复杂度:O(nlogn)<br /> /// Stability:No<br /> /// </summary><br /> public class QuickSortAlgorithm<br /> {<br /> // QuickSort implementation<br /> public static void QuickSort<T>(IList<T> szArray, int nLower, int nUpper) where T : IComparable<br /> {<br /> if (nLower < nUpper)<br /> {<br /> int nSplit = Partition(szArray, nLower, nUpper);<br /> QuickSort(szArray, nLower, nSplit - 1);<br /> QuickSort(szArray, nSplit + 1, nUpper);<br /> }<br /> }<br /> // QuickSort partition implementation<br /> private static int Partition<T>(IList<T> szArray, int nLower, int nUpper) where T:IComparable<br /> {<br /> T szPivot = szArray[nLower]; //分隔点的值，用数字第一个值代替<br /> int nLeft = nLower + 1;//左边开始点<br /> int nRight = nUpper; //右边开始点<br /> T szSwap; //交换变量<br /> //开始查找<br /> //将小于分隔点的值都挪到左边<br /> //将小于分隔点的值都挪到右边<br /> while (nLeft <= nRight)<br /> {<br /> //找到左边第一个大于分隔点的值<br /> while (nLeft <= nRight && szArray[nLeft].CompareTo(szPivot) <= 0)<br /> nLeft = nLeft + 1;<br /> //找到右边第一个小于分隔点的值<br /> while (nLeft <= nRight && szArray[nRight].CompareTo(szPivot) > 0)<br /> nRight = nRight - 1;<br /> //如果左右还没有交叉(碰头)，交换左右两个值<br /> if (nLeft < nRight)<br /> {<br /> szSwap = szArray[nLeft];<br /> szArray[nLeft] = szArray[nRight];<br /> szArray[nRight] = szSwap;<br /> nLeft = nLeft + 1;<br /> nRight = nRight - 1;<br /> }<br /> }<br /> //将分隔点移动到最后那个点,此时nRight = nLeft - 1<br /> //所以那个点的值小于分隔点，可以与分隔点进行交换<br /> szSwap = szArray[nLower];<br /> szArray[nLower] = szArray[nRight];<br /> szArray[nRight] = szSwap;<br /> //现在在nRight左边的值都小于分隔点，nRight右边的值都大于分隔点<br /> return nRight;<br /> }<br /> }<br /> }<br />