快速排序 quick sort

https://github.com/hotwater99/practice_datastructure_and_algorithm.git

《数据结构与算法分析——C语言描述》机械工业出版社，原书第2版，7.7

快速排序的思路是在数组中设定一个数为“枢纽元”，比“枢纽元”小的数全部放到“枢纽元”的左边；比“枢纽元”大的数全部放到“枢纽元”的右边。然后采用分治的方法分别处理左边右边的数组，这样就可以完成排序了。

在实际操作时，主要有两个问题对效率影响较大：

1、如何找到合适的枢纽元pivot；

2、如何对数组进行分割（分割成比枢纽元大的、小的两个子数组）。

用Median函数确定枢纽元。首先在数组中把Left，Right，Center这3个位置上的数拿出来，把其中最小的放到Left，最大的放到Right，剩下的那个就作为枢纽元，为了提高效率，把Center与Right-1的位置数交换一下，把枢纽元保存在Array[Right-1]，这样后续只要处理Array[Left+1]到Array[Right-2]就好了。

数组分割。用i, j两个光标，i从Array[Left+1]开始，从左往右扫描，遇到≥pivot的就停止；j从Array[Right-2]开始，从右往左扫描，遇到≤pivot的就停止。i和j扫描都停止后，就交换Array[i]和Array[j]，最后直到i和j两个交叉了为止。最后将枢纽元所在的Array[Right-1]与Array[i]（i停止时Array[i]≥pivot）交换一下，这样就完成了数组分割。

快速排序：

  1 // 返回“左端、中心、右端”中数值处于中间的那个，即枢纽元pivot
  2 // 处理“左端、中心、右端”，并隐藏枢纽元pivot
  3 int Median(int array[], int left, int right)
  4 {
  5   int center = (left + right) / 2;
  6 
  7   if (array[left] > array[center])
  8     Swap(&array[left], &array[center]);
  9   if (array[left] > array[right])
 10     Swap(&array[left], &array[right]);
 11   if (array[center] > array[right])
 12     Swap(&array[center], &array[right]);
 13 
 14   Swap(&array[center], &array[right - 1]); // hide pivot
 15   return array[right - 1];
 16 }
 17 
 18 void QSort(int array[], int left, int right)
 19 {
 20   int i, j;
 21   int pivot;
 22 
 23   if (left + CUT_OFF <= right) {
 24     pivot = Median(array, left, right);
 25     i = left;
 26     j = right - 1;
 27     for (;;) {
 28       while (array[++i] < pivot) {}
 29       while (array[--j] > pivot) {}
 30       if (i < j)
 31         Swap(&array[i], &array[j]);
 32       else
 33         break;
 34     }
 35     Swap(&array[i], &array[right - 1]);
 36     QSort(array, left, i - 1);
 37     QSort(array, i + 1, right);
 38   }
 39   else {
 40     // 数组长度太短时，用插入排序效率更高
 41     InsertSort(array + left, right - left + 1);
 42   }
 43 }
 44 
 45 void QuickSort(int array[], int N)
 46 {
 47   QSort(array, 0, N - 1);
 48 }

完整代码：

  1 #include <iostream>
  2 #include <ctime>
  3 
  4 using namespace std;
  5 
  6 #define random(x)       (rand()%x)
  7 #define ARRAY_LENTH     10
  8 
  9 #define CUT_OFF         3 // 数组长度太短时，用插入排序效率更高
 10 
 11 void InsertSort(int array[], int n)
 12 {
 13   int i, j;
 14   int tmp;
 15 
 16   for (i = 1; i < n; i++)
 17   {
 18     tmp = array[i];
 19 
 20     for (j = i; j > 0 && array[j - 1] > tmp; j--) {
 21       array[j] = array[j - 1];
 22     }
 23     array[j] = tmp;
 24   }
 25 }
 26 
 27 void Swap(int *a, int *b)
 28 {
 29   int tmp = *a;
 30   *a = *b;
 31   *b = tmp;
 32 }
 33 
 34 // 返回“左端、中心、右端”中数值处于中间的那个，即枢纽元pivot
 35 // 处理“左端、中心、右端”，并隐藏枢纽元pivot
 36 int Median(int array[], int left, int right)
 37 {
 38   int center = (left + right) / 2;
 39 
 40   if (array[left] > array[center])
 41     Swap(&array[left], &array[center]);
 42   if (array[left] > array[right])
 43     Swap(&array[left], &array[right]);
 44   if (array[center] > array[right])
 45     Swap(&array[center], &array[right]);
 46 
 47   Swap(&array[center], &array[right - 1]); // hide pivot
 48   return array[right - 1];
 49 }
 50 
 51 void QSort(int array[], int left, int right)
 52 {
 53   int i, j;
 54   int pivot;
 55 
 56   if (left + CUT_OFF <= right) {
 57     pivot = Median(array, left, right);
 58     i = left;
 59     j = right - 1;
 60     for (;;) {
 61       while (array[++i] < pivot) {}
 62       while (array[--j] > pivot) {}
 63       if (i < j)
 64         Swap(&array[i], &array[j]);
 65       else
 66         break;
 67     }
 68     Swap(&array[i], &array[right - 1]);
 69     QSort(array, left, i - 1);
 70     QSort(array, i + 1, right);
 71   }
 72   else {
 73     // 数组长度太短时，用插入排序效率更高
 74     InsertSort(array + left, right - left + 1);
 75   }
 76 }
 77 
 78 void QuickSort(int array[], int N)
 79 {
 80   QSort(array, 0, N - 1);
 81 }
 82 
 83 int main() {
 84   int test_array[ARRAY_LENTH];
 85   int i, N = ARRAY_LENTH;
 86   clock_t start_time, stop_time;
 87 
 88   for (i = 0; i < N; i++) {
 89     test_array[i] = random(N);
 90   }
 91 
 92   if (N <= 100) {
 93     cout << "raw : ";
 94     for (i = 0; i < N; i++) {
 95       cout << test_array[i] << " ";
 96     }
 97     cout << endl;
 98   }
 99 
100   start_time = clock();
101 
102   QuickSort(test_array, N);
103 
104   stop_time = clock();
105 
106   if (N <= 100) {
107     cout << "sort: ";
108     for (i = 0; i < N; i++) {
109       cout << test_array[i] << " ";
110     }
111     cout << endl;
112   }
113 
114   cout << "QuickSort(" << N << ")..." << endl;
115   cout << "total time used: ";
116   cout << (double)(stop_time - start_time) / CLOCKS_PER_SEC << "s" << endl;
117 
118   system("pause");
119 
120   return 0;
121 }

测试结果

N=10

raw : 1 7 4 0 9 4 8 8 2 4
sort: 0 1 2 4 4 4 7 8 8 9
QuickSort(10)...
total time used: 0s

N=100

raw : 41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36 91 4 2 53 92 82 21 16 18 95 47 26 71 38 69 12 67 99 35 94 3 11 22 33 73 64 41 11 53 68 47 44 62 57 37 59 23 41 29 78 16 35 90 42 88 6 40 42 64 48 46 5 90 29 70 50 6 1 93 48 29 23 84 54 56 40 66 76 31 8 44 39 26 23 37 38 18 82 29 41
sort: 0 1 2 3 4 5 5 6 6 8 11 11 12 16 16 18 18 21 22 23 23 23 24 26 26 27 27 29 29 29 29 31 33 34 35 35 36 37 37 38 38 39 40 40 41 41 41 41 42 42 42 44 44 45 46 47 47 48 48 50 53 53 54 56 57 58 59 61 62 62 64 64 64 66 67 67 68 69 69 70 71 73 76 78 78 81 82 82 84 88 90 90 91 91 92 93 94 95 95 99
QuickSort(100)...
total time used: 0s

N=1000

QuickSort(1000)...
total time used: 0s

N=10000

QuickSort(10000)...
total time used: 0.001s

N=100000

QuickSort(100000)...
total time used: 0.011s