排序算法

插入排序

插入排序是对少量元素进行排序的有效算法。

1
2
3
4
5
6
初始状态: 4,| 9, 7, 20, 3, 16, 18
第一趟: 4, 9,| 7, 20, 3, 16, 18
第二趟: 4, 7, 9,| 20, 3, 16, 18
第三趟: 3, 4, 7, 9,| 20, 16, 18
第四趟: 3, 4, 7, 9, 16,| 20, 18
第五趟: 3, 4, 7, 9, 16, 18,| 20

插入排序n个元素的排序需要进行n-1趟插入排序将所有元素完成排序。
插入排序是稳定排序算法。在数据及规模不大时,插入排序具有较好的效率。最好情况下每个元素都在其正确的位置上,进行排序所需事件为对每个元素与其前一个元素对比的时间,约等于一次遍历所花时间,所以最好情况下时间复杂度为$O(n)$,在普通情况和最坏情况下,n个元素每个元素都需要被移动一个线性的距离,所以平均和最坏情况下,插入排序的时间复杂度为$O(n^2)$

冒泡排序

冒泡排序(气泡排序)是交换排序的一种。分为下沉排序和上浮排序。

1
2
3
4
5
6
7
8
9
10
11
12
下沉排序
初始状态: 4, 9, 7, 20, 3, 16, 18
第一趟: 4, 7, 9, 3, 16, 18, 20
第二趟: 4, 7, 3, 9, 16, 18, 20
第三趟: 4, 3, 7, 9, 16, 18, 20
第四趟: 3, 4, 7, 9, 16, 18, 20

上浮排序
初始状态: 4, 9, 7, 20, 3, 16, 18
第一趟: 3, 4, 9, 7, 20, 16, 18
第二趟: 3, 4, 7, 9, 16, 20, 18
第三趟: 3, 4, 7, 9, 16, 18, 20

冒泡排序主要步骤是相邻元素的比较和交换,终止的标志为在某一趟排序过程中值有对比动作而没有交换动作。
冒泡排序在最好情况下,初始状态就已经是升序排序,则只需要经过一趟n-1次元素之间比较,且不用进行元素移动,就结束排序,最好时间复杂度为$O(n)$。最坏情况下,参加排序的数据元素为逆序排序,或最小值在序列最后时,需要进行n-1趟排序,平均和最坏时间复杂度都是$O(n^2)$
冒泡排序的元素交换发生在相邻元素之间,不会改变值相同元素的相对位置,因此,冒泡排序是稳定排序

选择排序

选择排序重复地从待排序的元素中选出最大的或最小的元素进行排序。
选择排序的时间复杂度为$O(n^2)$
选择排序是非稳定排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
选最小值排序
初始状态: 4, 9, 7, 20, 3, 16, 18
第一趟: 3, 9, 7, 20, 4, 16, 18
第二趟: 3, 4, 7, 20, 9, 16, 18
第三趟: 3, 4, 7, 20, 9, 16, 18
第四趟: 3, 4, 7, 9,20, 16, 18
第五趟: 3, 4, 7, 9,16, 20, 18
第六趟: 3, 4, 7, 9,16, 18, 20

选最大值排序
初始状态: 4, 9, 7, 20, 3, 16, 18
第一趟: 4, 9, 7, 18, 3, 16, 20
第二趟: 4, 9, 7, 16, 3, 18, 20
第三趟: 4, 9, 7, 3,16, 18, 20
第四趟: 4, 3, 7, 9,16, 18, 20
第五趟: 4, 3, 7, 9,16, 18, 20
第六趟: 3, 4, 7, 9,16, 18, 20

快速排序

快速排序是运用分治思想的算法。主要思想:有待排序数组S={d1, d2, d3, …, dn},从中找出元素划界元素v,将剩下元素中小于或等于v的元素移动到v的前面,将大于或等于v的元素i移动到v的后面,v就找到了它的最终位置,并将S划分为两个不相交的子数组S1和S2。其中S1中的元素均小于或等于v,S2中的元素均大于或等于v,这个过程称为一次排序。然后快速排序递归地对子序列S1和S2进行上述排序过程。直至所有的子序列都只包含0或1个元素时停止,整个数组完成排序。
划界元素一般取第一个元素、中间元素或最后一个元素。
快速排序是不稳定排序,主要是因为最后异步划界元素与S[i+1]交换的时候有可能打破前面元素的稳定性。
快速排序的最坏时间复杂度为$O(n^2)$,最坏情况为参与排序的元素原本有序,平均时间复杂度为$O(nlog_2n)$。

归并排序

归并排序是运用分治思想的算法。归并将两个或多个已排序序列合并成为一个按值排序的序列。
归并排序的平均时间复杂度为$O(nlog_2n)$

1
2
3
4
9, 4, | 7, 20, | 16,  3, | 18
4, 9, 7, 20, 3, 16, 18
4, 9, 7, 20, | 3, 16, 18
3, 4, 7, 9, 16, 18, 20

堆排序

堆数据结构是一种数组对象,可以将其看成一颗完全二叉树。堆分为最大堆和最小堆,最小堆的最小元素是根结点,最大堆的最大元素是其根结点。

堆排序算法

最大堆的根结点是最大值,堆排序的核心思想也是利用了堆结构的这一特性。对待排序数组进行建堆操作,使其数组中元素排列复合最大堆特性。每次取堆的最大值,再调整堆结构,直至堆的大小为2结束。

1
2
3
4
5
6
7
8
4 9 7 20 3 16 18
20 9 18 4 3 16 7
18 9 16 4 3 7 20
16 9 7 4 3 18 20
9 4 7 3 16 18 20
7 4 3 9 16 18 20
4 3 7 9 16 18 20
3 4 7 9 16 18 20

堆排序的时间复杂度为$O(nlog_2n)$
堆排序是非稳定排序

希尔排序

希尔排序是一种非稳定排序,希尔排序不适合链表结构。
希尔排序的主要思想:确定一个元素间隔数gap,将参与排序的元素从第一个元素开始按照间隔一次分成多个子序列,分别将所有位置相隔gap的元素看成一个子序列。对各个子序列排序,再缩小gap的值,重新按照新的gap划分数组,再对每个子序列排序,直到gap递减为1。

1
2
3
4
        3, 7, 5, 1, 12, 10, 8, 9
gap=4 3, 7, 5, 1, 12, 10, 8, 9
gap=2 3, 1, 5, 7, 8, 9,12,10
gap=1 1, 3, 5, 7, 8, 9,10,12

计数排序

计数排序是一种稳定排序,当待排序数组中有大量重复的数值并且这些数值较为集中时,使用计数排序算法较有优势。

基数排序

基数排序的主要思想:如果参加排序的元素具有d位,将元素先按最低位的值进行派位,如后按最次低位的值进行排序……最后进行最高位的排序。

1
2
3
4
5
6
初始   个位   十位   百位
329 463 329 329
568 564 839 463
839 -> 568 -> 463 -> 564
463 329 564 568
564 839 568 839

桶排序

桶排序将数组中的数据分组,将分好的组分别放在一个个的”桶”中,然后对每个桶中的数据再进行排序。对”桶”内部的排序,可以使用插入排序、冒泡排序或快速排序等排序方法。
桶排序数组中的数据满足以下两点:

  1. 均匀分布。输入数据需要均匀分布再一个给定的范围内。基于这种分配,算法创建n个桶来平分输入数据。
  2. 有序散列函数。桶必须是有序的。即,排在前面的桶中的所有数据必须小于后面桶的中的所有数据。

排序算法对比和选择

排序算法时间复杂度、空间复杂度、算法稳定性

算法名称 最好时间复杂度 平均时间复杂度 最坏时间复杂度 空间复杂度 算法稳定性
插入排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
冒泡排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
快速排序 $O(nlog_2n)$ $O(nlog_2n)$ $O(n^2)$ $O(log_2n)$ 不稳定
归并排序 $O(nlog_2n)$ $O(nlog_2n)$ $O(nlog_2n)$ $O(n)$ 稳定
堆排序 $O(nlog_2n)$ $O(nlog_2n)$ $O(nlog_2n)$ $O(1)$ 不稳定
希尔排序 O(n^1.3) $O(nlog_2n)$ $O(n^2)$ $O(1)$ 不稳定
计数排序 $O(n)$ $O(n)$ $O(n)$ $O(n)$ 稳定
基数排序 $O(d(n+w))$ $O(d(n+w))$ $O(d(n+w))$ $O(n+w)$ 稳定
桶排序 $O(n)$ $O(n)$ $O(n)$ $O(n)$ 稳定

排序算法选择标准

  1. 通常情况下,输入数据是随机的,快速排序、归并排序、希尔排序和堆排序的运行速度较快。其中堆排序是原地排序最节省空间,快速排序的速度是最快的。在内存空间不紧张的情况下,一般采用快速排序,如需节省空间则采用堆排序,希尔排序不适合用在链表数据结构上。
  2. 待排序数据规模不大而且一开始就局部有序,插入排序和冒泡排序的运行时间最快,为$O(n)$,一般采用这两种排序算法。
  3. 从待排序数据规模考虑:规模小,采用简单排序算法合适,整体性能高;规模大,采用改进型的算法比较合适。因为规模小时$n^2$和$log_2n$差异小,而简单算法实现比较容易。

C++代码实现

github代码 https://github.com/CaseZheng

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
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;


void PrintVec(vector<int> &vec)
{
for(auto x : vec)
{
cout<<x<<" ";
}
if(vec.size()>0)
{
cout<<endl;
}
}


void InsertSort(vector<int> &vec) //插入排序
{
if(vec.size() <= 1)
{
return;
}
for(int i=1; i<vec.size(); ++i)
{
int tmpIndex = i;
for(int j=0; j<i; ++j)
{
if(vec[j] > vec[i])
{
tmpIndex = j;
break;
}
}
int tmpValue = vec[i];
for(int j=i; j>tmpIndex; --j)
{
vec[j] = vec[j-1];
}
vec[tmpIndex] = tmpValue;
//PrintVec(vec);
}
}

void Swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}

void BubbleSinkSort(vector<int> &vec) //冒泡排序(下沉)
{
if(vec.size() <= 1)
{
return;
}

for(int i=vec.size()-1; i>0; --i)
{
bool flag = false;
int end = vec.size()-1-i;
for(int j=vec.size()-1; j>end; --j)
{
if(vec[j] < vec[j-1])
{
Swap(vec[j], vec[j-1]);
flag = true;
}
}
if(!flag)
{
break;
}
//PrintVec(vec);
}
}

void BubbleFloatSort(vector<int> &vec) //冒泡排序(上浮)
{
if(vec.size() <= 1)
{
return;
}

for(int i=0; i<vec.size(); ++i)
{
bool flag = false;
int end = vec.size()-1-i;
for(int j=0; j<end; ++j)
{
if(vec[j] > vec[j+1])
{
Swap(vec[j], vec[j+1]);
flag = true;
}
}
if(!flag)
{
break;
}
//PrintVec(vec);
}
}

void SelectionSort(vector<int> &vec) //选择排序
{
if(vec.size() <= 1)
{
return;
}
for(int i=0; i<vec.size(); ++i)
{
int minValue = vec[i];
int minIndex = i;
for(int j=i+1; j<vec.size(); ++j)
{
if(vec[j] < minValue)
{
minValue = vec[j];
minIndex = j;
}
}
Swap(vec[i], vec[minIndex]);
}
}

int Partition(vector<int> &vec, int l, int r)
{
if(l>r)
{
return l;
}
int position;
int index = r;
int tmpValue = vec[index];
while(l<r)
{
while(l<r && vec[l]<tmpValue) ++l; //从左边向右找一个大于tmpValue的下标l
while(l<r && vec[r]>=tmpValue) --r; //从右边向左找一个小于tmpValue的下标r
if(l<r)
{
Swap(vec[l], vec[r]); //交换两个值
}
}
Swap(vec[l], vec[index]);

//PrintVec(vec);
return r;
}

void QuickSort_Recursion(vector<int> &vec, int l, int r)
{
int position = 0;
if(l<r)
{
position = Partition(vec, l, r);
QuickSort_Recursion(vec, l, position-1);
QuickSort_Recursion(vec, position+1, r);
}
}

void QuickSort_Recursion(vector<int> &vec) //快速排序(递归)
{
if(vec.size() <= 1)
{
return;
}
QuickSort_Recursion(vec, 0, vec.size()-1);
}

void QuickSort(vector<int> &vec) //快速排序(迭代)
{
if(vec.size() <= 1)
{
return;
}
int l = 0;
int r = vec.size()-1;
stack<int> st;
st.push(l);
st.push(r);
while(!st.empty())
{
r = st.top(); st.pop();
l = st.top(); st.pop();
if(l >= r)
{
continue;
}
int position = Partition(vec, l, r);
st.push(l);
st.push(position-1);

st.push(position+1);
st.push(r);
}
}

void Merge(vector<int> &va, vector<int> &vb, vector<int> &vec)
{
vec.clear();
if(va.empty())
{
vec = vb;
}
else if(vb.empty())
{
vec = va;
}
else
{
int a = 0;
int b = 0;
while(a < va.size() && b < vb.size())
{
if(va[a] < vb[b])
{
vec.push_back(va[a++]);
}
else
{
vec.push_back(vb[b++]);
}
}
if(a < va.size())
{
for(; a<va.size(); ++a)
{
vec.push_back(va[a]);
}
}
if(b < vb.size())
{
for(; b<vb.size(); ++b)
{
vec.push_back(vb[b]);
}
}
}
}

void MergeSort_Recursion(vector<int> &vec) //归并排序(递归)
{
if(vec.size() <= 1)
{
return;
}
vector<int> va;
vector<int> vb;
int mod = vec.size()/2;
for(int i=0; i<vec.size(); ++i)
{
if(i<mod)
{
va.push_back(vec[i]);
}
else
{
vb.push_back(vec[i]);
}
}
MergeSort_Recursion(va);
MergeSort_Recursion(vb);
Merge(va, vb, vec);
}

void Merge(vector<int> &vec, int x, int y, int z)
{
vector<int> va;
vector<int> vb;
for(int i=x; i<y; ++i)
{
va.push_back(vec[i]);
}
for(int i=y; i<z; ++i)
{
vb.push_back(vec[i]);
}
vector<int> vc;
if(va.empty())
{
vc = vb;
}
else if(vb.empty())
{
vc = va;
}
else
{
int a = 0;
int b = 0;
while(a < va.size() && b < vb.size())
{
if(va[a] < vb[b])
{
vc.push_back(va[a++]);
}
else
{
vc.push_back(vb[b++]);
}
}
if(a < va.size())
{
for(; a<va.size(); ++a)
{
vc.push_back(va[a]);
}
}
if(b < vb.size())
{
for(; b<vb.size(); ++b)
{
vc.push_back(vb[b]);
}
}
}
for(int i=x; i<z; ++i)
{
vec[i] = vc[i-x];
}
}

int min(int a, int b)
{
return (a<b ? a : b);
}

void MergeSort(vector<int> &vec) //归并排序(迭代)
{
if(vec.size() <= 1)
{
return;
}
for(int i=1; i<vec.size(); i*=2)
{
int offset = i+i;
for(int j=0; j<vec.size(); j+=offset)
{
Merge(vec, j, min(j+i, vec.size()), min(j+offset, vec.size()));
//cout<<j<<" "<<min(j+i, vec.size())<<" "<<min(j+offset, vec.size())<<endl;
//PrintVec(vec);
}
}
}

void KeepHead(vector<int> &vec, int len, int i)
{
int left = 2*i+1;
int right = 2*i+2;
int largest = i;
if(left<len && vec[left]>vec[i])
{
largest = left;
}
if(right<len && vec[right]>vec[largest])
{
largest = right;
}
if(largest != i)
{
Swap(vec[i], vec[largest]);
KeepHead(vec, len, largest);
}
}

void BuildHeap(vector<int> &vec) //建堆
{
if(vec.size() < 2)
{
return;
}
int i = vec.size()/2 -1;
while(i>=0)
{
KeepHead(vec, vec.size(), i);
--i;
}
}

void HeapSort(vector<int> &vec) //堆排序
{
BuildHeap(vec);
int heap_size = vec.size();
for(int i=vec.size()-1; i>0; --i)
{
//PrintVec(vec);
Swap(vec[0], vec[i]);
--heap_size;
KeepHead(vec, heap_size, 0);
}
}

void CountingSort(vector<int> &vec) //计数排序
{
if(vec.size() < 1)
{
return;
}
int maxValue = vec[0];
int minValue = vec[0];
for(auto x : vec)
{
maxValue = x>maxValue ? x : maxValue;
minValue = x<minValue ? x : minValue;
}
vector<int> c(maxValue-minValue+1, 0);
for(auto x : vec)
{
++c[x-minValue]; //统计vec各元素出现的次数
}
for(int i=1; i<=maxValue-minValue; ++i)
{
c[i] += c[i-1]; //分布值计算
}
vector<int> s(vec.size(), 0);
for(int i=vec.size()-1; i>=0; --i)
{
int j = vec[i] - minValue;
s[c[j]-1] = vec[i];
--c[j];
}
vec = s;
}

void ShellSort(vector<int> &vec) //希尔排序
{
if(vec.size() < 2)
{
return;
}
int i, j, flag, counter=1, gap=vec.size();
int temp;
while(gap > 1)
{
gap = gap/2;
do
{
flag = 0;
for(int i=0; i<=vec.size()-gap-counter; ++i)
{
j=i+gap;
if(vec[i] > vec[j])
{
Swap(vec[i], vec[j]);
flag = 1;
}
}
}
while(counter < vec.size() && flag == 1);
}
}

int main()
{
vector<int> vecTest = {4, 9, 7, 20, 3, 16, 18};
vector<int> vec;

//cout<<"插入排序"<<endl ; vec = vecTest ; PrintVec(vec) ; InsertSort(vec) ; PrintVec(vec) ;
//cout<<"冒泡排序(下沉)"<<endl ; vec = vecTest ; PrintVec(vec) ; BubbleSinkSort(vec) ; PrintVec(vec) ;
//cout<<"冒泡排序(上浮)"<<endl ; vec = vecTest ; PrintVec(vec) ; BubbleFloatSort(vec) ; PrintVec(vec) ;
//cout<<"选择排序"<<endl ; vec = vecTest ; PrintVec(vec) ; SelectionSort(vec) ; PrintVec(vec) ;
//cout<<"快速排序(递归)"<<endl ; vec = vecTest ; PrintVec(vec) ; QuickSort_Recursion(vec) ; PrintVec(vec) ;
//cout<<"快速排序(迭代)"<<endl ; vec = vecTest ; PrintVec(vec) ; QuickSort(vec) ; PrintVec(vec) ;
//cout<<"归并排序(递归)"<<endl ; vec = vecTest ; PrintVec(vec) ; MergeSort_Recursion(vec) ; PrintVec(vec) ;
//cout<<"归并排序(迭代)"<<endl ; vec = vecTest ; PrintVec(vec) ; MergeSort(vec) ; PrintVec(vec) ;
//cout<<"计数排序"<<endl ; vec = vecTest ; PrintVec(vec) ; CountingSort(vec) ; PrintVec(vec) ;
//cout<<"堆排序"<<endl ; vec = vecTest ; PrintVec(vec) ; HeapSort(vec) ; PrintVec(vec) ;
//cout<<"希尔排序"<<endl ; vec = vecTest ; PrintVec(vec) ; ShellSort(vec) ; PrintVec(vec) ;

vecTest = {49, 55, 25, 97, 60, 27, 49, 50} ;

//cout<<"快速排序(递归)"<<endl ; vec = vecTest ; PrintVec(vec) ; QuickSort_Recursion(vec) ; PrintVec(vec) ;
//cout<<"快速排序(迭代)"<<endl ; vec = vecTest ; PrintVec(vec) ; QuickSort(vec) ; PrintVec(vec) ;
//cout<<"归并排序(递归)"<<endl ; vec = vecTest ; PrintVec(vec) ; MergeSort_Recursion(vec) ; PrintVec(vec) ;
//cout<<"归并排序(迭代)"<<endl ; vec = vecTest ; PrintVec(vec) ; MergeSort(vec) ; PrintVec(vec) ;

return 0;
}