数据结构与算法复习（一）快速排序

快速排序的步骤是：
1、在数组中任意选择一个元素，称为轴值
2、扫描数组，将大于等于轴值的元素放到轴的右边，将小于轴值的元素放到轴的左边；固定轴的位置不动，
于是，数组被分为大于轴值和小于轴值的两个部分
4、对轴两边的数组递归执行1和2两个步骤

before sort :
开始时选择最后一个元素40为轴
27 28 1 59 48 63 40
扫描数组，将大于等于40的元素放到40的右边，将小于40的元素放到40的左边
同样的，固定40的位置不动，对40两边的数组递归进行上述过程
27 28 1 40 48 63 59
1 28 27 40 48 63 59
1 27 28 40 48 63 59
1 27 28 40 48 59 63
after sort :
1 27 28 40 48 59 63

快速排序是一种非稳定算法（比如数组84 84，排序时两者会交换）。
每一趟划分都需要对划分数组的所有元素扫描一遍，那么每一趟划分需要的时间为O(n)；
因此快速排序的时间复杂度取决于划分的次数，
理想的情况下，每次划分都能将数组对半分，那么只需要划分log2n次，则时间复杂度为O(nlog2n)；
最坏情况下，每次划分都选择到最大或最小元素作为轴，那么需要划分n次，则时间复杂度为O(n*n)；
被证明是：快速排序的平均时间复杂度为O(nlog2n)。

快速排序的空间复杂度：只需要一个数据缓存作为交换空间；每划分一次需要入栈一次，因此需要的栈空间为划分次数。因此快速排序的空间复杂度为划分次数。

综上所述：快速排序的性能取决于轴值的合理性，因此在排序时要采用一些办法选择合适的轴值，比如随机法。

算法实现代码如下。

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 /* 用时间做种子产生随机数 */
 5 #include <time.h>
 6 
 7 void quicksort(int A[], int left, int right)
 8 {
 9     /*
10      * left：数组左下标
11      * right：数组右下标
12      */
13     int l, r;
14 
15     if (A == NULL || left >= right) {
16         return;
17     }
18 
19     l = left;
20     r = right - 1;
21     while (l <= r) {
22         while (A[l] < A[right]) {++l;}
23         while (r >= left && A[r] >= A[right]) {--r;}
24 
25         if (r >= left) {
26             exchange(A, l, r);
27         }
28     }
29 
30     if (r >= left) {
31         exchange(A, l, r);
32     }
33     /* 将轴换到l的位置，并将l作为数组分割点 */
34     exchange(A, l, right);
35     quicksort(A, left, l - 1);
36     quicksort(A, l + 1, right);
37 }
38 
39 static void printA(int A[], int len)
40 {
41     int i;
42 
43     for (i = 0; i < len; i++) {
44         printf("%d ", A[i]);
45     }
46     printf("
");
47 }
48 
49 int main(int argc, char **argv){
50     int i, res, len;
51     int A[50]; // = {-1,6,2,3,9,19};
52 
53     srand((int)time(NULL));
54     len = rand() % 51; //51;
55     printf("len is %d.
", len);
56 
57     srand((int)(time(NULL) + len));
58     for (i = 0; i < len; i++) {
59         A[i] = rand() % 100;
60     }
61 
62     printf("before sort :
");
63     printA(A, len);
64 
65     quicksort(A, 0, len - 1);
66 
67     printf("after sort :
");
68     printA(A, len);
69 
70     return 0;
71 }

数据结构与算法复习（一）快速排序

相关推荐