programming

快速排序算法：分治思想的经典应用

算法原理

快速排序（Quick Sort）是一种基于分治思想的高效排序算法，由C.A.R. Hoare在1960年提出。它通过选择一个基准元素，将数组分割成两部分，然后递归地对子数组进行排序。

基本思想

  1. 选择基准：从数组中选择一个元素作为基准（pivot）
  2. 分割操作：重新排列数组，使所有比基准小的元素放在基准前面，比基准大的元素放在基准后面
  3. 递归排序：递归地对基准元素前后的子数组进行快速排序

分割过程详解

分割是快速排序的核心，通常使用双指针技术：

  • 左指针从左向右找到第一个大于等于基准的元素
  • 右指针从右向左找到第一个小于等于基准的元素
  • 交换这两个元素，继续移动指针
  • 直到左右指针相遇

优缺点分析

优点

  1. 平均性能优秀：平均时间复杂度O(n log n)
  2. 原地排序：只需要O(log n)的额外空间
  3. 实用性强：在实际应用中通常比其他O(n log n)算法更快
  4. 缓存友好：局部性好，对现代计算机架构友好

缺点

  1. 最坏情况性能差：退化为O(n²)
  2. 不稳定排序：相等元素的相对位置可能改变
  3. 递归开销：深度递归可能导致栈溢出
  4. 基准选择敏感：基准选择策略影响性能

使用场景

适用场景

  1. 大规模数据排序：处理百万级以上数据
  2. 内存受限环境：需要原地排序的场合
  3. 一般用途排序：大多数编程语言的默认排序算法
  4. 系统级编程：操作系统、数据库内核

不适用场景

  1. 需要稳定排序：应选择归并排序或其他稳定算法
  2. 最坏情况不可接受：实时系统或关键应用
  3. 小规模数据：插入排序可能更高效
  4. 递归限制严格：栈空间非常有限的环境

C语言实现

基础版本

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

/**
 * 交换两个元素
 */
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

/**
 * 分割函数 - Lomuto分割方案
 * @param arr 待分割数组
 * @param low 起始索引
 * @param high 结束索引
 * @return 基准元素的最终位置
 */
int partition_lomuto(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = low - 1;       // 小于基准的元素的索引
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

/**
 * 分割函数 - Hoare分割方案
 * @param arr 待分割数组
 * @param low 起始索引
 * @param high 结束索引
 * @return 分割点位置
 */
int partition_hoare(int arr[], int low, int high) {
    int pivot = arr[low]; // 选择第一个元素作为基准
    int i = low - 1;
    int j = high + 1;
    
    while (1) {
        // 从左向右找到第一个大于等于基准的元素
        do {
            i++;
        } while (arr[i] < pivot);
        
        // 从右向左找到第一个小于等于基准的元素
        do {
            j--;
        } while (arr[j] > pivot);
        
        if (i >= j) {
            return j;
        }
        
        swap(&arr[i], &arr[j]);
    }
}

/**
 * 快速排序主函数
 * @param arr 待排序数组
 * @param low 起始索引
 * @param high 结束索引
 */
void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        // 分割数组并获取基准位置
        int pi = partition_lomuto(arr, low, high);
        
        // 递归排序基准左右两部分
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

/**
 * 三数取中优化的分割函数
 */
int median_of_three(int arr[], int low, int high) {
    int mid = low + (high - low) / 2;
    
    if (arr[mid] < arr[low]) {
        swap(&arr[mid], &arr[low]);
    }
    if (arr[high] < arr[low]) {
        swap(&arr[high], &arr[low]);
    }
    if (arr[high] < arr[mid]) {
        swap(&arr[high], &arr[mid]);
    }
    
    // 将中位数放到最后
    swap(&arr[mid], &arr[high]);
    return arr[high];
}

int partition_optimized(int arr[], int low, int high) {
    // 使用三数取中选择基准
    median_of_three(arr, low, high);
    
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

/**
 * 优化的快速排序
 */
void quick_sort_optimized(int arr[], int low, int high) {
    // 小数组使用插入排序
    if (high - low + 1 < 10) {
        insertion_sort_range(arr, low, high);
        return;
    }
    
    if (low < high) {
        int pi = partition_optimized(arr, low, high);
        
        quick_sort_optimized(arr, low, pi - 1);
        quick_sort_optimized(arr, pi + 1, high);
    }
}

/**
 * 插入排序（用于小数组优化）
 */
void insertion_sort_range(int arr[], int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;
        
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
}

/**
 * 非递归版本的快速排序
 */
void quick_sort_iterative(int arr[], int size) {
    // 创建栈来模拟递归
    int* stack = (int*)malloc(size * sizeof(int));
    int top = -1;
    
    // 初始化栈
    stack[++top] = 0;
    stack[++top] = size - 1;
    
    while (top >= 0) {
        // 弹出high和low
        int high = stack[top--];
        int low = stack[top--];
        
        // 分割数组
        int pi = partition_lomuto(arr, low, high);
        
        // 如果左子数组有多个元素，入栈
        if (pi - 1 > low) {
            stack[++top] = low;
            stack[++top] = pi - 1;
        }
        
        // 如果右子数组有多个元素，入栈
        if (pi + 1 < high) {
            stack[++top] = pi + 1;
            stack[++top] = high;
        }
    }
    
    free(stack);
}

/**
 * 三路快速排序（处理重复元素）
 */
void quick_sort_3way(int arr[], int low, int high) {
    if (low >= high) return;
    
    int lt = low;      // arr[low..lt-1] < pivot
    int gt = high;     // arr[gt+1..high] > pivot
    int i = low + 1;   // arr[lt..i-1] == pivot
    int pivot = arr[low];
    
    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(&arr[lt++], &arr[i++]);
        } else if (arr[i] > pivot) {
            swap(&arr[i], &arr[gt--]);
        } else {
            i++;
        }
    }
    
    // 递归排序两部分
    quick_sort_3way(arr, low, lt - 1);
    quick_sort_3way(arr, gt + 1, high);
}

// 测试和演示函数
void print_array(int arr[], int size, const char* title) {
    printf("%s: ", title);
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void test_quick_sort() {
    printf("=== 快速排序算法演示 ===\n\n");
    
    // 测试数据
    int test_cases[][10] = {
        {64, 34, 25, 12, 22, 11, 90, 88, 76, 50},
        {5, 2, 8, 6, 1, 9, 4, 0, 3, 7},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
    };
    
    const char* descriptions[] = {
        "随机数组",
        "普通数组", 
        "重复元素数组",
        "逆序数组"
    };
    
    for (int t = 0; t < 4; t++) {
        printf("%s:\n", descriptions[t]);
        
        int arr1[10], arr2[10], arr3[10];
        memcpy(arr1, test_cases[t], sizeof(test_cases[t]));
        memcpy(arr2, test_cases[t], sizeof(test_cases[t]));
        memcpy(arr3, test_cases[t], sizeof(test_cases[t]));
        
        print_array(arr1, 10, "排序前");
        
        // 测试基础快速排序
        quick_sort(arr1, 0, 9);
        print_array(arr1, 10, "基础快排");
        
        // 测试非递归快速排序
        quick_sort_iterative(arr2, 10);
        print_array(arr2, 10, "非递归快排");
        
        // 测试三路快速排序
        quick_sort_3way(arr3, 0, 9);
        print_array(arr3, 10, "三路快排");
        
        printf("\n");
    }
}

void performance_test() {
    printf("=== 性能测试 ===\n");
    
    const int sizes[] = {1000, 10000, 100000};
    const int num_sizes = sizeof(sizes) / sizeof(sizes[0]);
    
    for (int s = 0; s < num_sizes; s++) {
        int size = sizes[s];
        int* arr = (int*)malloc(size * sizeof(int));
        
        // 生成随机数据
        srand((unsigned int)time(NULL));
        for (int i = 0; i < size; i++) {
            arr[i] = rand() % 10000;
        }
        
        clock_t start = clock();
        quick_sort(arr, 0, size - 1);
        clock_t end = clock();
        
        double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
        
        printf("数组大小: %d, 排序时间: %.6f 秒\n", size, time_taken);
        
        free(arr);
    }
}

int main() {
    test_quick_sort();
    performance_test();
    return 0;
}

算法优化技术

1. 基准选择策略

1
2
3
4
5
6
7
// 随机选择基准
int random_partition(int arr[], int low, int high) {
    srand((unsigned int)time(NULL));
    int random_index = low + rand() % (high - low + 1);
    swap(&arr[random_index], &arr[high]);
    return partition_lomuto(arr, low, high);
}

2. 尾递归优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void quick_sort_tail_recursive(int arr[], int low, int high) {
    while (low < high) {
        int pi = partition_lomuto(arr, low, high);
        
        // 对较小的子数组递归，较大的子数组用循环
        if (pi - low < high - pi) {
            quick_sort_tail_recursive(arr, low, pi - 1);
            low = pi + 1;
        } else {
            quick_sort_tail_recursive(arr, pi + 1, high);
            high = pi - 1;
        }
    }
}

复杂度分析

时间复杂度

  • 最好情况：O(n log n) - 每次分割都均匀
  • 平均情况：O(n log n)
  • 最坏情况：O(n²) - 数组已排序且每次选择最值作基准

空间复杂度

  • 递归版本：O(log n) - 递归调用栈
  • 迭代版本：O(log n) - 显式栈
  • 最坏情况：O(n) - 递归深度为n

稳定性

快速排序是不稳定的排序算法，相等元素的相对位置可能发生改变。

实际应用

  1. 编程语言标准库：C的qsort、Java的Arrays.sort
  2. 数据库系统：内存排序操作
  3. 大数据处理：MapReduce排序阶段
  4. 系统内核：进程调度、内存管理

总结

快速排序是最重要的排序算法之一，其分治思想和优秀的平均性能使其在实际应用中被广泛采用。理解快速排序不仅有助于解决排序问题，更重要的是掌握分治算法的精髓，为解决更复杂的算法问题奠定基础。

通过合理的优化策略，快速排序能够在大多数情况下提供卓越的性能，是每个程序员都应该深入理解和掌握的经典算法。

版权所有，如有侵权请联系我