快排是对冒泡排序的一种改进。基本思想是:
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
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(n2),理想时间复杂度是o(nlogn)。