1 /************************************************************************/
 2 /* 快排
 3 /* 时间复杂度O(NlogN)
 4 /************************************************************************/
 5 #include <stdio.h>
 6 
 7 #define swap(a, b) {(a) = (a) ^ (b); (b) = (a)^ (b); (a) = (a) ^ (b);}
 8 
 9 //插入排序
10 void InsertionSort2(int* array, int size)
11 {
12     int i, j;
13     int tmp;
14     for (i = 1; i < size; ++i)
15     {
16         tmp = array[i];
17         for (j = i; array[j - 1] > tmp &&  j > 0; --j)
18         {
19             array[ j ] = array[j - 1];
20         }
21         array[ j ] = tmp;
22     }
23 }
24 
25 //选取枢纽元，将最左、最右和中间三个中最小的那个作为枢纽元
26 int MinThree(int *array, int left, int right)
27 {
28     int center = (left + right) / 2;
29 
30     //将三个数交换位置，使得array[left]<array[center]<array[right]
31     if (array[left] > array[center])
32     {
33         swap(array[left], array[right]);
34     }
35     if (array[left] > array[right])
36     {
37         swap(array[left], array[right]);
38     }
39     if (array[center] > array[right])
40     {
41         swap(array[center], array[right]);
42     }
43     
44     //将中间的枢纽元与right - 1上的元素交换，避免枢纽元参与排序过程
45     swap(array[center], array[right - 1]);
46 
47     return array[right - 1];
48 }
49 
50 void QuickSort(int array[], int left, int right)
51 {
52 
53     int pivot = MinThree(array, left, right);
54 
55     //递归终止的条件
56     if (left - right <= 3)
57     {
58         int i = left;
59         int j = right - 1;
60         while (true)
61         {
62             //快排核心思想，交换元素
63             while (array[++i] > pivot){}
64             while (array[--j] < pivot){}
65             if (i < j)
66             {
67                 swap(array[i], array[j]);
68             }
69             else
70             {
71                 break;
72             }
73         }
74         //将枢纽元与i位置元素交换回来
75         swap(array[right - 1], array[i]);
76 
77         //递归进行
78         QuickSort(array, left, i - 1);
79         QuickSort(array, i + 1, right);
80     }
81     else
82     {
83         //元素个数较少时，采用插入排序更快
84         InsertionSort2(array + left, right - left + 1);
85     }
86 }
87 
88 int main()
89 {
90     int array[10] = {10, 45, 78, 32, 89, 18, 105, 953, 243, 19};
91     QuickSort(array, 10);
92     int i = 0;
93     int j = sizeof(array) / sizeof(int);
94     while (i < j)
95     {
96         printf("%d     ", array[i++]);
97     }
98     return 0;
99 }