快速排序思想：

基于分治策略，對冒泡排序的一種改進(jìn)。對于要排序的一個(gè)序列，從中選一值進(jìn)行排序，將其放入到正確的位置position。然后以position為界，對左右兩部分再做排序。直到劃分的長度為1。

步驟：設(shè)有一待排序的序列

1、分別設(shè)置low、high指向序列的最左端、最右端；從序列中選一個(gè)進(jìn)行排序（通常選最左端的值low指向的值），存入到tmp；
2、從high端開始，查找比tmp小的，找到后將該值放入到low指向的存儲(chǔ)位中；苯玥igh指向當(dāng)前查到的值所在的位；
3、從low端開始，查找比tmp大的，找到后將該值放入到high指向的存儲(chǔ)為中，同時(shí)low指向當(dāng)前查到的值所在位；
4、若low位小于high位，返回步驟2；否則，將tmp值存入到空出來的low+1指向的位置，退出，返回low所在的位置position；
5、以position為界，將序列分成兩部分，分別對兩部分進(jìn)行排序。

c#實(shí)現(xiàn)如下：

         //快速排序
        public static void QuickSort(int[] items)
        {
            RecQuickSort(items, 0, items.Length - 1);
        }

        private static void RecQuickSort(int[] items, int low, int high)
        {
            if (low < high)
            {
                int i = Partition(items, low, high);
                RecQuickSort(items, low, i - 1);
                RecQuickSort(items, i + 1, high);
            }
        }

        private static int Partition(int[] items, int low, int high)
        {
            int tmp = items[low];
            while (low < high)
            {
                while (low < high && items[high] >= tmp)
                    high--;

                // 換位后不能將low加1,防止跳位  
                if (low < high)
                    items[low] = items[high];

                while (low < high && items[low] <= tmp)
                    low++;

                if (low < high)
                {
                    items[high] = items[low];
                    // 有l(wèi)ow < high，可將high向前推一位  
                    high--;
                }
            }
            items[low] = tmp;

            return low;
        }

最關(guān)鍵的是Partition,做一次排序的劃分，將其放入到正確的位置。

.NET中的Array.Sort()方法內(nèi)部使用的就是快速排序算法，看看Array.Sort()方法的實(shí)現(xiàn)：
   
    [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
    public static void Sort(Array array)
    {
        if (array == null)
        {
            throw new ArgumentNullException("array");
        }
        Sort(array, null, array.GetLowerBound(0), array.Length, null);
    }   

    [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
    public static void Sort(Array keys, Array items, int index, int length, IComparer comparer)
    {
        if (keys == null)
        {
            throw new ArgumentNullException("keys");
        }
        if ((keys.Rank != 1) || ((items != null) && (items.Rank != 1)))
        {
            throw new RankException(Environment.GetResourceString("Rank_MultiDimNotSupported"));
        }
        if ((items != null) && (keys.GetLowerBound(0) != items.GetLowerBound(0)))
        {
            throw new ArgumentException(Environment.GetResourceString("Arg_LowerBoundsMustMatch"));
        }
        if ((index < keys.GetLowerBound(0)) || (length < 0))
        {
            throw new ArgumentOutOfRangeException((length < 0) ? "length" : "index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
        }
        if (((keys.Length - (index - keys.GetLowerBound(0))) < length) || ((items != null) && ((index - items.GetLowerBound(0)) > (items.Length - length))))
        {
            throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
        }
        if ((length > 1) && (((comparer != Comparer.Default) && (comparer != null)) || !TrySZSort(keys, items, index, (index + length) - 1)))
        {
            object[] objArray = keys as object[];
            object[] objArray2 = null;
            if (objArray != null)
            {
                objArray2 = items as object[];
            }
            if ((objArray != null) && ((items == null) || (objArray2 != null)))
            {
                new SorterObjectArray(objArray, objArray2, comparer).QuickSort(index, (index + length) - 1);
            }
            else
            {
                new SorterGenericArray(keys, items, comparer).QuickSort(index, (index + length) - 1);
            }
        }
    }