By

Contents

QuickSort的思想很简单，整个排序过程只需要三步：

  1. 在数据集中，选择一个元素作为轴；
  2. 所有小于轴的元素，都移到轴的左边；所有大于轴的元素，都移到轴的右边；
  3. 对左右两个子集，不断重复1、2步（递归），直到所有子集只剩下一个元素为止。

下面是工作原理的图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
* 快速排序
*/
void swap(int &x, int &y) {
    int temp;
    temp = x;
    x = y;
    y = temp;
}
//方法一
void QuickSort1(int list[], int m, int n) {
    int key, i, j;
    if (list == NULL) {
        cout << "数组为空!\n";
        return;
    }
    if (m < n) {
        swap(list[m], list[(m + n) >> 1]);
        key = list[m];
        i = m + 1;
        j = n;
        while (i <= j) {
            while ((i <= n) && (list[i] <= key)) {
                i++;
            }
            while ((j >= m) && (list[j] > key)) {
                j--;
            }
            if (i < j) {
                swap(list[i], list[j]);
            }
        }
        swap(list[m], list[j]);
        QuickSort1(list, m, j - 1);
        QuickSort1(list, j + 1, n);
    }
}
//方法二
int Partition(int data[], int length, int start, int end) {
    if (data == NULL || length <= 0 || start < 0 || end >= length) {
        cout << "Invalid Parameters!\n";
        return -1;
    }
    int index = (end + start) >> 1;
    swap(data[index], data[end]);
    int small = start - 1;
    for (index = start; index < end; index++){
        if (data[index] < data[end]) {
            small++;
            if (small != index) {
                swap(data[index], data[small]);
            }
        }
    }
    small++;
    if (small != end) {
        swap(data[small], data[end]);
    }
    return small;
}
void QuickSort2(int data[], int length, int start, int end) {
    if (start == end) {
        return;
    }
    int index = Partition(data, length, start, end);
    if (index > start) {
        QuickSort2(data, length, start, index - 1);
    }
    if (index < end) {
        QuickSort2(data, length, index + 1, end);
    }
}

Contents