QuickSort實作(用C#)

最近跟同事討論到QuickSort這個演算法，因為網路上找到的範例好像都有些問題，就自已試著實作一次來瞭解一下QuickSort的原理。

正好手邊有一本「演算法之道：讓你學不會演算法都難」裏面有講到這個排序演算法，實作一下，還真的可行。

以下是實作的程式碼：

public class QuickSort
    {
        public static void SortCore(ref int[] src, int start, int len)
        {
            if (start < len)
            {
                DumpArray("Start sort", src);

                int pivotPos = Partition(ref src, start, len);
                SortCore(ref src, start, pivotPos);         // 對左邊的資料排序
                SortCore(ref src, pivotPos + 1, len);       // 對右邊的資料排序
            }
        }
        
        protected static int Partition(ref int[] src, int start, int len)
        {
            string msg = string.Format("Partition From {0} to {1}", start, len); 

            if (start >= len)
                return start;       // 不用排序

            int pivotPos = start;
            int pivotValue = src[pivotPos];
            int i = pivotPos;       // 比pivotValue小的最後一個位置

            // 由pivotPos右邊的值開始比較，只要比pivotValue小的，都置換到左邊這區
            for (int j = pivotPos + 1; j < len; j++)
            {
                if (src[j] <= pivotValue)
                {
                    i = ++i;
                    SwapArray(src, i, j);
                }
            }

            // 因為在i位置上的值一定 <= pivotValue，所以就將i跟pivotPos調換，
            // 這樣在 i 左邊的值都是小於pivotValue的，在i右邊的值都是大於pivotValue的。
            SwapArray(src, pivotPos, i); 

            // for DEBUG
            DumpArray(msg,src);

            return i;       // 傳回目前的分界點
            
        }        

        protected static void DumpArray(string msg , int[] src)
        {
            Console.Write(msg + "\t\t\t\t\t"); 
            foreach (int i in src)
            {
                Console.Write(i.ToString() + " "); 
            }
            Console.WriteLine(""); 
        }

        public static void SwapArray<T>(T[] src,int lhs, int rhs)
        {
            T tmp = src[lhs];
            src[lhs] = src[rhs];
            src[rhs] = tmp;
        }
    }

因為上面是依型別int寫的，以下改寫為可以用泛型的方式。不過，可使用的型別必須支援IComparable。

public class QuickSort2<T> where T : IComparable
    {
        public static void SortCore(ref T[] src, int start, int len)
        {
            if (start < len)
            {
                DumpArray("Start sort", src);

                int pivotPos = Partition(ref src, start, len);
                SortCore(ref src, start, pivotPos);         // 對左邊的資料排序
                SortCore(ref src, pivotPos + 1, len);       // 對右邊的資料排序
            }
        }

        protected static int Partition(ref T[] src, int start, int len)
        {
            string msg = string.Format("Partition From {0} to {1}", start, len);

            if (start >= len)
                return start;       // 不用排序

            int pivotPos = start;
            T pivotValue = src[pivotPos];
            int i = pivotPos;       // 比pivotValue小的最後一個位置

            // 由pivotPos右邊的值開始比較，只要比pivotValue小的，都置換到左邊這區
            for (int j = pivotPos + 1; j < len; j++)
            {
                if (src[j].CompareTo(pivotValue) <= 0)
                {
                    i = ++i;
                    SwapArray(src, i, j);
                }
            }

            // 因為在i位置上的值一定 <= pivotValue，所以就將i跟pivotPos調換，
            // 這樣在 i 左邊的值都是小於pivotValue的，在i右邊的值都是大於pivotValue的。
            SwapArray(src, pivotPos, i);

            // for DEBUG
            DumpArray(msg, src);

            return i;       // 傳回目前的分界點

        }

        protected static void DumpArray(string msg, T[] src)
        {
            Console.Write(msg + "\t\t\t\t\t");
            foreach (T i in src)
            {
                Console.Write(i.ToString() + " ");
            }
            Console.WriteLine("");
        }

        public static void SwapArray<T>(T[] src, int lhs, int rhs)
        {
            T tmp = src[lhs];
            src[lhs] = src[rhs];
            src[rhs] = tmp;
        }
    }