快速排序算法——C/C++_c++快速排序

快速排序

1. 算法思想

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

2. 实现原理

2.1、设置两个变量 low、high，排序开始时：low=0，high=size-1。
2.2、整个数组找基准正确位置，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面

1. 默认数组的第一个数为基准数据，赋值给key，即key=array[low]。
2. 因为默认数组的第一个数为基准，所以从后面开始向前搜索（high–），找到第一个小于key的array[high]，就将 array[high] 赋给 array[low]，即 array[low] = array[high]。（循环条件是 array[high] >= key；结束时 array[high] < key）
3. 此时从前面开始向后搜索（low++），找到第一个大于key的array[low]，就将 array[low] 赋给 array[high]，即 array[high] = array[low]。（循环条件是 array[low] <= key；结束时 array[low] > key）
4. 循环 2-3 步骤，直到 low=high，该位置就是基准位置。
5. 把基准数据赋给当前位置。

2.3、第一趟找到的基准位置，作为下一趟的分界点。
2.4、递归调用（recursive）分界点前和分界点后的子数组排序，重复2.2、2.3、2.4的步骤。
2.5、最终就会得到排序好的数组。

3. 动态演示

4. 完整代码

4.1. 核心函数

获取基准函数：int get_standard(int* array, int i, int j)
递归排序函数：void quick_sort(int* array, int low, int high)
1
2

4.2. 代码

#include <stdio.h>
#include <stdlib.h> // rand() srand()
#include <time.h>   // time()

void display(int* array, int size); // 打印函数
int  check(int* array, int size);   // 检查函数

/**
 * @brief 获取基准位置
 *
 * @param array        数组首地址
 * @param i            起始位置
 * @param j            结束位置
 * @return int         基准位置
 */
int get_standard(int* array, int i, int j)
{
    // 基准数据
    int key = array[i];
    while (i < j) {
        // 因为默认基准是从左边开始，所以从右边开始比较
        // 当队尾的元素大于等于基准数据 时,就一直向前挪动 j 指针
        while (i < j && array[j] >= key) {
            j--;
        }
        // 当找到比 array[i] 小的时，就把后面的值 array[j] 赋给它
        if (i < j) {
            array[i] = array[j];
        }
        // 当队首元素小于等于基准数据 时,就一直向后挪动 i 指针
        while (i < j && array[i] <= key) {
            i++;
        }
        // 当找到比 array[j] 大的时，就把前面的值 array[i] 赋给它
        if (i < j) {
            array[j] = array[i];
        }
    }
    // 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置
    // 把基准数据赋给正确位置
    array[i] = key;
    return i;
}

/**
 * @brief 快速排序
 *
 * @param array        数组首地址
 * @param low          起始位置
 * @param high         结束位置
 */
void quick_sort(int* array, int low, int high)
{
    // 开始默认基准为 low
    if (low < high) {
        // 分段位置下标
        int standard = get_standard(array, low, high);
        // 递归调用排序
        // 左边排序
        quick_sort(array, low, standard - 1);
        // 右边排序
        quick_sort(array, standard + 1, high);
    }
}

/**
 * @brief 快速排序：合并版
 *
 * @param array        数组首地址
 * @param low          起始位置
 * @param high         结束位置
 */
void quick_sort_all(int* array, int low, int high)
{
    if (low < high) {
        int i   = low;
        int j   = high;
        int key = array[i];
        while (i < j) {
            while (i < j && array[j] >= key) {
                j--;
            }
            if (i < j) {
                array[i] = array[j];
            }
            while (i < j && array[i] <= key) {
                i++;
            }
            if (i < j) {
                array[j] = array[i];
            }
        }
        array[i] = key;
        quick_sort_all(array, low, i - 1);
        quick_sort_all(array, i + 1, high);
    }
}

int main()
{
    // 测试用例
    // int array[]    = {49, 38, 65, 97, 76, 13, 27, 49, 10};
    // int array_size = sizeof(array) / sizeof(array[0]);
    // printf("%d \n", array_size);
    // printf("排序前数组：");
    // display(array, array_size);
    // quick_sort(array, 0, array_size - 1);
    // printf("排序后数组：");
    // display(array, array_size);

    // 随机测试
    int array_num  = 20;             // 数组数量
    int array_size = 20;             // 数组大小
    int array[array_size];           // 数组初始化
    srand((unsigned int)time(NULL)); // 随机数种子，保证每次不一样
    for (int i = 0; i < array_num; i++) {
        for (int j = 0; j < array_size; j++) {
            array[j] = rand() % 1000; // 随机生成数大小 0~999
        }
        printf("原来的数组：");
        display(array, array_size);
        quick_sort(array, 0, array_size - 1);
        printf("排序后数组：");
        display(array, array_size);
        // 检测排序结果
        if (check(array, array_size) != 0) {
            exit(-1);
        }
        printf("\n");
    }

    return 0;
}

/**
 * @brief 打印函数
 *
 * @param array        数组首指针
 * @param size         数组大小
 */
void display(int* array, int size)
{
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

/**
 * @brief 检查函数，从小到大
 *
 * @param array        数组首指针
 * @param size         数组大小
 */
int check(int* array, int size)
{
    for (int i = 0; i < size - 1; i++) {
        if (array[i] > array[i + 1]) {
            printf("sort array fail...\n");
            return -1;
        }
    }
    printf("sort array success...\n");
    return 0;
}
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

5. 结果展示

（递归调用，不好展示每次排序结果）

6. 算法分析

时间复杂度：

1. 最好：$O(nlo{g}_{2}n)$
2. 最坏：$O(n^2)$
3. 平均：$O(nlo{g}_{2}n)$

空间复杂度：$O(nlo{g}_{2}n)$

稳定性：不稳定