C#快速排序

快速排序思想：

基于分治策略，对冒泡排序的一种改进。对于要排序的一个序列，从中选一值进行排序，将其放入到正确的位置position。然后以position为界，对左右两部分再做排序。直到划分的长度为1。

步骤：设有一待排序的序列

1、分别设置low、high指向序列的最左端、最右端；从序列中选一个进行排序（通常选最左端的值low指向的值），存入到tmp；
2、从high端开始，查找比tmp小的，找到后将该值放入到low指向的存储位中；苯玥igh指向当前查到的值所在的位；
3、从low端开始，查找比tmp大的，找到后将该值放入到high指向的存储为中，同时low指向当前查到的值所在位；
4、若low位小于high位，返回步骤2；否则，将tmp值存入到空出来的low+1指向的位置，退出，返回low所在的位置position；
5、以position为界，将序列分成两部分，分别对两部分进行排序。

c#实现如下：

         //快速排序
        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];
                    // 有low < high，可将high向前推一位  
                    high--;
                }
            }
            items[low] = tmp;

            return low;
        }

最关键的是Partition,做一次排序的划分，将其放入到正确的位置。

.NET中的Array.Sort()方法内部使用的就是快速排序算法，看看Array.Sort()方法的实现：
   
    [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);
            }
        }
    }