快速排序（C#实现）

快排是对冒泡排序的一种改进。基本思想是：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快排递归实现：

 1         internal static void QuickSort(int[] inputArray, int lowIndex, int highIndex)
 2         {
 3             if (lowIndex >= highIndex)
 4             {
 5                 return;
 6             }
 7             int middleIndex = SortFunction(inputArray, lowIndex, highIndex);
 8             QuickSort(inputArray, lowIndex, middleIndex);
 9             QuickSort(inputArray, middleIndex + 1, highIndex);
10         }
11 
12         private static int SortFunction(int[] inputArray, int lowIndex, int highIndex)
13         {
14             int minValue = inputArray[lowIndex];
15             for (; highIndex > lowIndex; highIndex--)
16             {
17                 if (inputArray[highIndex] <= minValue)
18                 {
19                     inputArray[lowIndex] = inputArray[highIndex];
20                     for (; lowIndex < highIndex; lowIndex++)
21                     {
22                         if (inputArray[lowIndex] >= minValue)
23                         {
24                             inputArray[highIndex] = inputArray[lowIndex];
25                             break;
26                         }
27                     }
28                 }
29             }
30             inputArray[lowIndex] = minValue;
31             return lowIndex;
32         }

快排非递归实现：

 1         static void Main(string[] args)
 2         {
 3             int[] array = new int[] { 2,3,9,1,8,6};
 4             Stack<int> stack = new Stack<int>();
 5             stack.Push(0);
 6             stack.Push(array.Length - 1);
 7             while (stack.Count > 0)
 8             {
 9                 int low = stack.Pop();
10                 int high = stack.Pop();
11                 if (low > high)
12                 {
13                     low = low + high;
14                     high = low - high;
15                     low = low - high;
16                 }
17                 QuickSort(array, low, high, stack);
18             }
19         }
20 
21         internal static void QuickSort(int[] inputArray, int lowIndex, int highIndex, Stack<int> stack)
22         {
23             int low = lowIndex;
24             int high = highIndex;
25             int minValue = inputArray[lowIndex];
26             while (high > low)
27             {
28                 while (low < high && minValue <= inputArray[high])
29                 {
30                     high--;
31                 }
32                 if (high > low)
33                 {
34                     inputArray[low] = inputArray[high];
35                 }
36                 while (low < high && minValue >= inputArray[low])
37                 {
38                     low++;
39                 }
40                 if (high > low)
41                 {
42                     inputArray[high] = inputArray[low];
43                 }
44 
45                 if (low == high)
46                 {
47                     inputArray[low] = minValue;
48                     if (lowIndex < low - 1)
49                     {
50                         stack.Push(lowIndex);
51                         stack.Push(low -1);
52                     }
53                     if (highIndex > low + 1)
54                     {
55                         stack.Push(low + 1);
56                         stack.Push(highIndex);
57                     }
58                 }
59             }
60         }

快排是一种不稳定的排序。快排的最差时间复杂度是o（n²），理想时间复杂度是o（nlogn）。