1一、快速排序 Quick Sort
21. 前提条件
3
4快排是最经典的：分治思想
5
6和归并一样：先拆再解决
7
8但和归并最大的区别：
9
10归并：先递归，后合并
11
12快排：先分区，后递归
13
142. 核心概念
15
16核心操作：Partition（划分）
17
18例如：
19
20[5,2,8,1,7]
21
22选：5
23
24作为基准值（pivot）。
25
26目标：
27
28小于5的放左边
29
30大于5的放右边
31
32变成：
33
34[2,1,5,8,7]
35
36注意：5已经到最终位置
37
38以后不用管它了。
39
40然后递归：
41
42[2,1]
43
44[8,7]
45
46继续快排。
47
483. 核心思想
49
50每次递归：确定一个元素最终位置
51
52归并：每层合并有序数组
53
54快排：每层确定一个 pivot
55
564. Partition（双指针）
57
58
59数组：[5,2,8,1,7]
60
61选：pivot=5
62
63定义：
64
65i 左边找大于5
66
67j 右边找小于5
68
69找到：
70
718
721
73
74交换：
75
76[5,2,1,8,7]
77
78最后：
79
80pivot归位
81
82得到：
83
84[1,2,5,8,7]
85
865. 固定模板
87partition
88int partition(int arr[], int left, int right)
89{
90 int pivot = arr[left];
91
92 int i = left;
93 int j = right;
94
95 while(i < j)
96 {
97 while(i < j && arr[j] >= pivot)
98 {
99 j--;
100 }
101 //相当于从左往右遍历直到直到跳过小于pivot的位置
102 while(i < j && arr[i] <= pivot)
103 {
104 i++;
105 }
106 //这里相当于从右往左跳过比pivot大的位置，直到找到最终pivot应该在的位置
107 if(i < j)
108 {
109 int temp = arr[i];
110 arr[i] = arr[j];
111 arr[j] = temp;
112 }
113 //这里就是左右指针没碰到，就交换两个位置，然后继续移动指针直到left=right
114 }
115//然后把left位置选中的pivot和i位置的数交换，之后相当于排好了pivot的位置，之后return
116 arr[left] = arr[i];
117 arr[i] = pivot;
118
119 return i;
120}
121
122quickSort
123void quickSort(int arr[],
124 int left,
125 int right)
126{
127 if(left >= right)
128 {
129 return;
130 }
131//这里是直接分到最小就直接返回
132//然后递归排mid左边和mid右边
133 int mid = partition(arr,left,right);
134
135 quickSort(arr,left,mid-1);
136
137 quickSort(arr,mid+1,right);
138}
139
1406. 例子
141
142数组：[5,2,8,1,7]
143
144第一次：pivot=5
145
146分区后：[1,2,5,8,7]
147
148继续：
149
150[1,2]
151
152[8,7]
153
154左边：[1,2]
155
156已经有序。
157
158右边：[8,7]
159
160变：[7,8]
161
162最终：[1,2,5,7,8]
163
1647. 复杂度
165
166平均：O(nlogn)
167
168最坏：O(n²)
169
170例如：[1,2,3,4,5]
171
172总拿最左边当 pivot。
173
174空间：O(logn)
175
176递归栈。
177
178稳定性：不稳定
179
1808. 易错点
181
182partition返回的是pivot最终位置
183
184pivot已经排好
185
186递归不要再包含pivot
187
188应该：
189
190left ~ mid-1
191
192mid+1 ~ right
193
194二、桶排序 Bucket Sort
1951. 前提条件
196
197桶排序不是比较排序。
198
199思想：先分类，再排序
200
201例如成绩：
202
20372
20491
20585
20660
207
208可以放进：
209
21060桶
211
21270桶
213
21480桶
215
21690桶
217
218然后桶内排序。
219
2202. 核心思想
221
222步骤：
223
2241. 建桶
2252. 放桶
2263. 桶内排序
2274. 收集
228
2293. 最简单情况
230
231如果数据范围：0~100
232
233其实就是计数排序。就是拿空间换时间的方式
234
235数组：[5,2,8,5,3]
236
237建立桶：
238
239cnt[101]
240
241统计：
242
243cnt[2]++
244
245cnt[3]++
246
247cnt[5]+=2
248
249cnt[8]++
250
251得到：
252
2532:1
254
2553:1
256
2575:2
258
2598:1
260
261输出：
262
2632
264
2653
266
2675
268
2695
270
2718
272
2734. 固定模板（计数排序）
274void bucketSort(int arr[],
275 int n)
276{
277 int cnt[101]={0};
278
279 for(int i=0;i<n;i++)
280 {
281 cnt[arr[i]]++;
282 }
283
284 int k=0;
285
286 for(int i=0;i<=100;i++)
287 {
288 while(cnt[i]--)
289 {
290 arr[k++] = i;
291 }
292 }
293}
294
2955. 为什么快
296
297因为：不比较直接统计
298
299例如：100万个成绩
300
301范围0~100
302
303只需要：统计101个桶
304
305即可。
306
3076. 复杂度
308O(n+k)
309
310其中：
311n=元素个数
312
313k=桶个数
314
3157. 局限性
316
317如果：
318
3191
320
3211000000000
322
323只有两个数。
324
325开桶：cnt[1000000001]会炸。
326所以：桶排序要求数据范围较小
327
328三、总结
329
330快速排序
331
332核心：
333 partition
334
335思想：
336 小的放左边
337 大的放右边
338
339每次确定一个pivot最终位置
340
341递归：
342 左边快排
343 右边快排
344
345平均：
346 O(nlogn)
347
348最坏：
349 O(n²)
350
351不稳定
352
353--------------------------------
354
355桶排序
356
357核心：
358 分类统计
359
360步骤：
361 建桶
362 放桶
363 桶内排序
364 收集
365
366复杂度：
367 O(n+k)
368
369要求：
370 数据范围较小
371
372典型：
373 成绩统计
374 年龄统计
375 计数排序
一、快速排序 Quick Sort
- 前提条件
快排是最经典的：分治思想
和归并一样：先拆再解决
但和归并最大的区别：
归并：先递归，后合并
快排：先分区，后递归
- 核心概念
核心操作：Partition（划分）
例如：
[5,2,8,1,7]
选：5
作为基准值（pivot）。
目标：
小于5的放左边
大于5的放右边
变成：
[2,1,5,8,7]
注意：5已经到最终位置
以后不用管它了。
然后递归：
[2,1]
[8,7]
继续快排。
- 核心思想
每次递归：确定一个元素最终位置
归并：每层合并有序数组
快排：每层确定一个 pivot
- Partition（双指针）
数组：[5,2,8,1,7]
选：pivot=5
定义：
i 左边找大于5
j 右边找小于5
找到：
8
1
交换：
[5,2,1,8,7]
最后：
pivot归位
得到：
[1,2,5,8,7]
-
固定模板
partition
int partition(int arr[], int left, int right)
{
int pivot = arr[left];
int i = left;
int j = right;
while(i < j)
{
while(i < j && arr[j] >= pivot)
{
j--;
}
//相当于从左往右遍历直到直到跳过小于pivot的位置
while(i < j && arr[i] <= pivot)
{
i++;
}
//这里相当于从右往左跳过比pivot大的位置，直到找到最终pivot应该在的位置
if(i < j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//这里就是左右指针没碰到，就交换两个位置，然后继续移动指针直到left=right
}
//然后把left位置选中的pivot和i位置的数交换，之后相当于排好了pivot的位置，之后return
arr[left] = arr[i];
arr[i] = pivot;
return i;
}
quickSort
void quickSort(int arr[],
int left,
int right)
{
if(left >= right)
{
return;
}
//这里是直接分到最小就直接返回
//然后递归排mid左边和mid右边
int mid = partition(arr,left,right);
quickSort(arr,left,mid-1);
quickSort(arr,mid+1,right);
}
- 例子
数组：[5,2,8,1,7]
第一次：pivot=5
分区后：[1,2,5,8,7]
继续：
[1,2]
[8,7]
左边：[1,2]
已经有序。
右边：[8,7]
变：[7,8]
最终：[1,2,5,7,8]
- 复杂度
平均：O(nlogn)
最坏：O(n²)
例如：[1,2,3,4,5]
总拿最左边当 pivot。
空间：O(logn)
递归栈。
稳定性：不稳定
- 易错点
partition返回的是pivot最终位置
pivot已经排好
递归不要再包含pivot
应该：
left ~ mid-1
mid+1 ~ right
二、桶排序 Bucket Sort
- 前提条件
桶排序不是比较排序。
思想：先分类，再排序
例如成绩：
72
91
85
60
可以放进：
60桶
70桶
80桶
90桶
然后桶内排序。
- 核心思想
步骤：
-
建桶
-
放桶
-
桶内排序
-
收集
-
最简单情况
如果数据范围：0~100
其实就是计数排序。就是拿空间换时间的方式
数组：[5,2,8,5,3]
建立桶：
cnt[101]
统计：
cnt[2]++
cnt[3]++
cnt[5]+=2
cnt[8]++
得到：
2:1
3:1
5:2
8:1
输出：
2
3
5
5
8
-
固定模板（计数排序）
void bucketSort(int arr[],
int n)
{
int cnt[101]={0};
for(int i=0;i<n;i++)
{
cnt[arr[i]]++;
}
int k=0;
for(int i=0;i<=100;i++)
{
while(cnt[i]--)
{
arr[k++] = i;
}
}
}
-
为什么快
因为：不比较直接统计
例如：100万个成绩
范围0~100
只需要：统计101个桶
即可。
- 复杂度
O(n+k)
其中：
n=元素个数
k=桶个数
- 局限性
如果：
1
1000000000
只有两个数。
开桶：cnt[1000000001]会炸。
所以：桶排序要求数据范围较小
三、总结
快速排序
核心：
partition
思想：
小的放左边
大的放右边
每次确定一个pivot最终位置
递归：
左边快排
右边快排
平均：
O(nlogn)
最坏：
O(n²)
不稳定
桶排序
核心：
分类统计
步骤：
建桶
放桶
桶内排序
收集
复杂度：
O(n+k)
要求：
数据范围较小
典型：
成绩统计
年龄统计
计数排序
