快捷導(dǎo)航

C#實(shí)現(xiàn)快速排序算法

更新時(shí)間：2022年04月15日 14:55:40 作者：Ruby_Lu

本文詳細(xì)講解了C#實(shí)現(xiàn)快速排序算法，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

快速排序是應(yīng)用最廣泛的排序算法，流行的原因是它實(shí)現(xiàn)簡(jiǎn)單，適用于各種不同情況的輸入數(shù)據(jù)且在一般情況下比其他排序都快得多。

快速排序是原地排序（只需要一個(gè)很小的輔助棧），將長(zhǎng)度為 N 的數(shù)組排序所需的時(shí)間和 N lg N 成正比。

1.算法

快速排序也是一種分治的排序算法。它將一個(gè)數(shù)組分成兩個(gè)子數(shù)組，將兩部分獨(dú)立地排序。

快速排序和歸并排序是互補(bǔ)：歸并排序是將數(shù)組分成兩個(gè)子數(shù)組分別排序，并將有序數(shù)組歸并，這樣數(shù)組就是有序的了；而快速排序?qū)?shù)組通過切分變成部分有序數(shù)組，然后拆成成兩個(gè)子數(shù)組，當(dāng)兩個(gè)子數(shù)組都有序時(shí)整個(gè)數(shù)組也就有序了。

歸并排序的遞歸調(diào)用發(fā)生在處理數(shù)組之前，快速排序的遞歸調(diào)用是發(fā)生在處理數(shù)組之后。

快速排序中切分的位置取決于數(shù)組的內(nèi)容。

    public class Quick: BaseSort
    {
        public new static long usedTimes = 0;
        public static void Sort(IComparable[] a)
        {
            usedTimes = 0;
            Stopwatch timer = new Stopwatch();
            timer.Start();
            Sort(a,0,a.Length-1);
            timer.Stop();
            usedTimes = timer.ElapsedMilliseconds;
        }

        public static void Sort(IComparable[] a, int lo, int hi)
        {
            if (hi <= lo)
                return;

            //切分
            int j = Partition(a,lo,hi);
            //Console.WriteLine(j);
            Sort(a,lo,j-1);
            Sort(a,j+1,hi);
        }
        public static int CompareCount = 0;
        public static int Partition(IComparable[] a, int lo, int hi)
        {
            int i = lo;
            int j = hi + 1;
            var v = a[lo];

            while (true)
            {
                //從左往右依次和 v 比較，直到找到 >= v 的值 索引i （索引i 左邊的值都小于切分元素）
                while (Less(a[++i], v))
                {
                    CompareCount++;
                    if (i == hi)
                        break;
                }

                //從右往左依次和 v 比較，直到找到 <= v 的值 索引j（索引j 右邊的值都大于于切分元素）
                while (Less(v, a[--j]))
                {
                    CompareCount++;
                    if (j == lo)
                        break;
                }

                //當(dāng) i >= j 時(shí)就找到了切分元素位置，位置為 j ,退出循環(huán)
                if (i >= j)
                    break;
                //如果 i 和 j 沒有相遇，將 i 和 j 的值交換，繼續(xù)循環(huán)，直到相遇
                Exch(a,i,j);
            }

            //將切分元素放到切分位置 j 
            Exch(a,lo,j);
            return j;
        }
    }

該算法的關(guān)鍵在于切分，在Sort(IComparable[] a, int lo, int hi) 方法中，切分后 a[lo] 到 a[j-1] 中的所有元素都不大于 a[ j ] ，a[j+1] 到 a[ hi ] 中的所有元素都不小于 a[ j ] ，然后對(duì)左子數(shù)組和右子數(shù)組進(jìn)行遞歸。因?yàn)榍蟹值倪^程總能排定一個(gè)元素，當(dāng)切分到剩一個(gè)元素時(shí)，子數(shù)組就是有序的。當(dāng)左數(shù)組和右數(shù)組都有序時(shí)，整個(gè)數(shù)組也就有序了。

切分方法：先隨意取 a[ lo ] 作為切分元素，即那個(gè)將被排定的元素。然后從數(shù)組的左端向右掃描直到找到大于等于它的元素，再從數(shù)組右端向左開始掃描直到找到小于等于它的元素。如果找到的這兩個(gè)元素不是同一個(gè)元素（索引不同），那么這個(gè)元素就還沒被排定；如果相同意味著這個(gè)元素已被排定。如果沒被排定，就交換這兩個(gè)元素，繼續(xù)掃描，直到左右索引相遇，即可返回將切分元素和找到的索引位置的元素交換，返回索引 j 。

排序?qū)嵙校?/p>

注意點(diǎn)

1. 原地切分

該算法是原地切分，如果使用輔助數(shù)組需要將切分后的數(shù)組復(fù)制回去的額外開銷。

2.越界

要防止掃描指針跑出數(shù)組邊界。

3.保持隨機(jī)性

該算法對(duì)所有子數(shù)組都是一視同仁的。

4.終止循環(huán)

該算法有三個(gè)循環(huán)都要注意什么時(shí)候終止。

5.處理切分元素值有重復(fù)的情況

該算法左右掃描都會(huì)在遇到相等值時(shí)停下來，盡管這樣會(huì)不必要的等值交換，但在某些情況下能夠避免算法的運(yùn)行時(shí)間變?yōu)槠椒郊?jí)別。

6.終止遞歸

任何遞歸調(diào)用都要先考慮什么時(shí)候終止。

2.性能

快速排序運(yùn)行時(shí)間的增長(zhǎng)量級(jí)為 NlogN 。

快速排序切分方法的內(nèi)循環(huán)用一個(gè)遞增的索引將數(shù)組元素和一個(gè)定值比較，這種循環(huán)很簡(jiǎn)潔。它比歸并排序和希爾排序都快，因?yàn)闅w并排序和希爾排序在內(nèi)循環(huán)中移動(dòng)元素。

快速排序的另一個(gè)速度優(yōu)勢(shì)在于它的比較次數(shù)很少（如果每次都對(duì)半分的話需要 N/2 * logN 次比較）。但是排序效率還是依賴切分?jǐn)?shù)組的效果，而這依賴于切分元素的值。切分一個(gè)較大的數(shù)據(jù)組，切分可能發(fā)生在任何一個(gè)位置。

快速排序的最好情況是每次都能將數(shù)組對(duì)半分。在這種情況下快速排序所用的比較次數(shù)正好滿足分治遞歸的 C(N) = 2C(N/2) + N 公式。2C(N/2) 表示將兩個(gè)子數(shù)組排序的成本， N 表示切分元素和所有數(shù)組元素比較的成本。C(N) ~ N log N 。平均而言切分元素都能落在數(shù)組中間。

快速排序在最壞情況下需要 ~ N^2 / 2 次比較，即每次切分總有一個(gè)數(shù)組是空的（逆序），比較次數(shù)為： N + （N-1）+ (N-2) ...+2+1 = (N+1)N/2 。這種情況不僅算法所需的時(shí)間是平方級(jí)別的，所需的空間是線性的。

快速排序平均需要 ~ 2N lnN 次比較（以及1/6的交換）。歸并排序也可以做到這個(gè)量級(jí)，但是快速排序移動(dòng)數(shù)據(jù)次數(shù)少（即交換次數(shù)），所以快速排序更快，盡管比較次數(shù)比歸并排序多了約 39%。

當(dāng)數(shù)組切分不平衡時(shí)（第一次用最小的切分，第二次用第二小的切分...）會(huì)倒置一個(gè)大數(shù)組需要切分很多次（上面說的逆序），所以非重復(fù)數(shù)組需要隨機(jī)打亂；當(dāng)存在大量重復(fù)元素時(shí)，排序過程會(huì)進(jìn)行很多次交換，重復(fù)數(shù)組可以使用稍后提到的三向切分的快速排序。

3.改進(jìn)

1.切換到插入排序

當(dāng)將一個(gè)大數(shù)組切分成一定小的數(shù)組時(shí)使用插入排序給小數(shù)組排序，這樣就不需要繼續(xù)遞歸調(diào)用 Sort() 方法了。

將if (hi <= lo)return; 改為

if（hi <= lo + M）{ Insertion.Sort(a, lo, hi); return;}

轉(zhuǎn)換參數(shù) M 的最佳值和系統(tǒng)相關(guān)，5 ~ 15 最佳。

2.三取樣切分

改進(jìn)快速排序性能的另一個(gè)方法是使用子數(shù)組的一小部分元素的中位數(shù)來切分?jǐn)?shù)組。這樣得到的切分更好，但是需要計(jì)算中位數(shù)。一般取樣大小為3并用大小居中的元素切分最好。

3.熵最優(yōu)排序

實(shí)際應(yīng)用中經(jīng)常會(huì)出現(xiàn)大量重復(fù)元素的數(shù)組，這會(huì)影響快排的性能。例如，一個(gè)全部重復(fù)的子數(shù)組就不需要排序了，但上面的算法會(huì)繼續(xù)切分。三向切分的快速排序可以將有大量重復(fù)元素的數(shù)組從線性對(duì)數(shù)級(jí)別提高到線性級(jí)別。

三向切分是將數(shù)組切分成小于，等于和大于三部分。它從左到右遍歷數(shù)組一次，維護(hù)一個(gè)指針 lt 使得 a[lo ... lt-1] 中的元素都小于 v（切分元素），一個(gè)指針 gt 使得 a[gt+1 ... hi] 中的元素都大于 v ，一個(gè)指針 i 使得 a[ lt ... i ] 中元素都等于 v , a[ i ... gt ] 中的元素都還未確定。一開始 lo 和 i 相等：

a[i]小于v：與 a[i] 交換 a[lt] 并增加lt 和i
a[i]大于v：將 a[i] 與 a[gt] 交換并減少gt
a[i]等于v：遞增i

    public class Quick: BaseSort
    {
        public new static long usedTimes = 0;

        //三向切分
        public static void Sort3Way(IComparable[] a)
        {
            usedTimes = 0;
            Stopwatch timer = new Stopwatch();
            timer.Start();
            Sort3Way(a, 0, a.Length - 1);
            timer.Stop();
            usedTimes = timer.ElapsedMilliseconds;
        }
        public static void Sort3Way(IComparable[] a, int lo, int hi)
        {
            if (hi < lo)
                return;
            int lt = lo, i = lo + 1, gt = hi;
            IComparable v = a[lo];
            while (i <= gt)
            {
                int cmp = a[i].CompareTo(v);
                if (cmp < 0)
                    Exch(a, lt++, i++);
                else if (cmp > 0)
                    Exch(a, i, gt--);
                else
                    i++;

            }

            Sort3Way(a,lo,lt-1);
            Sort3Way(a,gt+1,hi);
        }
    }