QuickSortImpl.cs

using System;
using System.Collections.Generic;

namespace QuickSortTest
{
    internal class QuickSortTest
    {
        /// <summary>
        /// Quick sort algorithm implement
        /// </summary>
        /// <param name="array">The array to be sorted.</param>
        public static void QuickSort(int[] array)
        {
            // Verify the input array
            if (array == null)
            {
                // we have 2 choices to handle the invalid input, choose 2 here
                // 1. throw new ArgumentException("array");
                // 2. return

                return;
            }

            QuickSort(array, 0, array.Length - 1);
        }

        private static void QuickSort(int[] array, int low, int high)
        {
            if (low < high)
            {
                int pivot = Partition(array, low, high); // 统计：1个变量

                if (pivot > 1)
                    QuickSort(array, low, pivot - 1);

                if (pivot + 1 < high)
                    QuickSort(array, pivot + 1, high);
            }
        }

        private static int Partition(int[] array, int low, int high)
        {
            int pivot = array[low]; // // 统计：2个变量
            while (low < high)
            {
                while (low < high && array[high] >= pivot)
                    --high;
                array[low] = array[high];
                while (low < high && array[low] <= pivot)
                    ++low;
                array[high] = array[low];
            }

            array[low] = pivot;
            return low;
        }

        private static void Main(string[] args)
        {
            // Create test data
            List<int[]> tests = new List<int[]>();
            tests.Add(new[] { 1, 2, 3, 4, 5 }); // 正序数列
            tests.Add(new[] { 5, 4, 3, 2, 1 }); // 逆序数列
            tests.Add(new[] { 1, 1, 1, 1, 1, 1 }); // 等值数列
            tests.Add(new[] { 10, -2, 0, 1224, 36 }); //常规数列
            tests.Add(new[] { 12, 8, 345345, 2342, 7, 1 }); // 正数
            tests.Add(new[] { -5, -54, -43, -2, 0 }); // 负数
            tests.Add(new[] { 0, 0, 0, 0, 0 }); // 特殊值
            tests.Add(null); // 空数列
            tests.Add(new[] { int.MaxValue, int.MaxValue, int.MinValue, int.MinValue }); //边界值
            tests.Add(new[] { 0 }); //单个数字长度的数列
            // tests.Add(new[] {...}) // 极限长度的数列，在此忽略
            // 很有很多case可以从运行平台，.Net版本，操作系统，兼容性，压力，性能方面出发，不仅仅考虑实现的功能

            // Run the test cases
            for (int i = 0; i < tests.Count; i++)
            {
                var test = tests[i];

                Console.WriteLine("Test Case #{0}", i + 1);
                Console.WriteLine("Before sorting: ");
                PrintArray(test);

                QuickSort(test);

                Console.WriteLine("After sorting: ");
                PrintArray(test);

                Console.WriteLine("====================");
                Console.WriteLine();
            }

            // Keep the console
            Console.Read();
        }

        /// <summary>
        /// Print the array.
        /// </summary>
        private static void PrintArray(int[] array)
        {
            if (array != null)
                Console.WriteLine(string.Join(",", array));
            else
                Console.WriteLine("NULL");
        }
    }
}