学步园

最近，学习算法导论，对快排法做个总结：

快排的特点：

最坏情况下，对n个数的排序所花的时间是O(n^2)。虽然这个结果比较差，但是快速排序却是用于排序的最佳的实用选择，因为它的平均性能相当好：期望的运行时间为O(nlgn),且O(nlgn)中的隐含因子比较小，另外，它还能够就地排序（也就是不需要另外开辟一个数组空间来进行中间数据存储），在虚存环境中也能很好的工作。

快排的原理：

public static void QuickSort(int[] arr, int p, int r)
{
    if (p < r)
    {
        int q = Partition(arr, p, r);
        QuickSort(arr, q+1, r);
        QuickSort(arr, p, q - 1);
    }
}

/// <summary>
        /// 将数组从下标p到r进行分解，返回一个下标(记为q吧)，
        /// 在下标左边的数均小于arr[q]，右边的数均大于arr[q]
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="p"></param>
        /// <param name="r"></param>
        /// <returns></returns>
        public static int Partition(int[] arr, int p, int r)
        {
            int i = p - 1;
            int tmp;
            for (int j = p; j <= r - 1; j++)
            {
                if (arr[j] <= arr[r])
                {
                    i++;
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
            tmp = arr[i + 1];
            arr[i + 1] = arr[r];
            arr[r] = tmp;
            return i + 1;
        }

关键点就在Partition方法了，下面举个例子来看看快速排序Partition的流程：

int[] arr = new int[8] { 2, 8, 7,1,3, 5,6,4};
QuickSort.Partition(arr,0,7);

相信看到这个运行过程后，已经基本理解了快速排序的思想了。现在给一个思考题：

如果数组p到r中的元素都相等，则Partition的返回值是多少呢？怎样才能让它返回(p+r)/2呢?