Quick Sort 快速排序

class Program
    {
        static void Main(string[] args)
        {
            var numbers = new int[] { 6, 4, 3, 10, 2, 21, 15, 1, 8, 9, 24, 64, 43, 767, 7, 3, 8, 22, 87, 28, 56, 76, 23, 88, 13, 554, 775, 20 };
            QuickSort(numbers, 0, numbers.Length - 1);
            foreach (var n in numbers)
                Console.Write(n + "  ");

            Console.Read();
        }

        static void QuickSort(int[] R, int left, int right)
        {
            int dp;
            if (left < right)
            {
                dp = Partition(R, left, right);
                QuickSort(R, left, dp - 1);
                QuickSort(R, dp + 1, right);
            }
        }

        /// <summary>
        /// 对一个集合进行一次划分，选第一个记录为基准记录，一次划分的结果是
        /// 基准记录左边的都比它小，右边的都比它大。
        /// </summary>
        /// <param name="numbers"></param>
        /// <param name="left">左边指针位置</param>
        /// <param name="right">右边指针位置</param>
        /// <returns>基准记录的位置</returns>
        static int Partition(int[] numbers, int left, int right)
        {
            int basis = numbers[left];
            while (left < right)
            {
                // 从右到左找第一个比基准记录小的并交换
                while (left < right && numbers[right] >= basis)
                    right--;
                numbers[left] = numbers[right];
                numbers[right] = basis;
                // 从左到右找第一个比基准记录大的并交换
                while (left < right && numbers[left] <= basis)
                    left++;
                numbers[right] = numbers[left];
                numbers[left] = basis;
            }

            return left;
        }
    }