【数据结构初阶-排序】经典的排序算法，很有趣，有没有你不会的呢

杨利霞

【数据结构初阶-排序】经典的排序算法，很有趣，有没有你不会的呢

前言
本期分享经典排序：

8 n6 I: r/ F( Y2 t" Q) |8 ^2 d插入排序
% l4 S6 [# c1 {/ F' b7 I直接插入排序
希尔排序
选择排序
直接选择排序
1 H+ b  `6 {$ N堆排序
交换排序
' R5 Y  j0 ^/ ]: s/ i5 Q; b冒泡排序
快速排序
) c( @+ ^; u/ e2 h注：讲解时默认排升序
7 t: [. ]- n$ K! ]) J; z1 X
插入排序
直接插入排序
9 B5 v' k  U2 r思想
1 N. j$ I6 F+ [' I3 h插入排序，就像玩扑克时，摸牌的过程：
, p7 d5 \& n$ M# B5 T8 R
9 T3 A8 ~- p7 y6 h最开始，左手没牌，右手从牌堆中摸
右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
如此一来就能保证左手的排始终有序，摸完牌后也就排序完成
( J  `, L0 z2 ?5 n: J! h7 }
9 m& E" A" v5 S% F
操作
设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
单趟排序：
每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
3 K6 G0 J, A3 {是正确位置：插入
$ \2 p3 f3 R7 W7 I不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
5 J0 j# b4 A5 V6 s% H整体趟数：
3 L( f) F  v6 X2 D若元素个数为n，需要排n趟
void InsertSort(int* arr, int sz)
9 F' }( N+ i* g# G5 s7 E! M{
        //end + 1 < sz
. G8 q; O) x1 T" c9 k! A        //end < sz - 1
        int i = 0;
: F1 L. g, {3 j* [/ r% S! E1 |        for (i = 0; i < sz - 1; i++)
0 e7 Z/ _; v! q5 z: F8 D        {
- x9 W/ v8 s* J5 P# K2 L; _                int end = i;
# E/ T6 v( {+ T5 R, \5 h                int tmp = arr[end + 1];
2 U$ n/ f; s5 a$ a
# |0 G4 h9 P- y% ?5 b, k2 F# ^                //找插入位置
$ `6 b: ?; o/ ^/ w5 ^% J                while (end >= 0)
  ]9 d6 R; q" s' \                {
                        //不是插入位置：当前数据往后挪
                        if (tmp < arr[end])
                        {
                                arr[end + 1] = arr[end];
                                end--;
                        }
                        //是插入位置：跳出循环插入
                        else
                        {
                                break;
                        }
                }
                //插入
                //1. 插入位置是[0]，end == -1，不合循环条件跳出
7 M' L$ ?1 a+ E7 h                //2. 找到插入位置，break跳出
5 c* e9 S$ d( s( g                arr[end + 1] = tmp;
        }
- N) y  u" `8 }9 P  S% e/ c/ w! K) f: R}
* \5 Z* E6 |7 t. [8 A
1
2
9 J$ G/ V6 ~+ t' |( f$ p3
8 ^, a. r; B9 ^4
5 \: b' Y5 n$ [5 ^% v5
6
) e; X' x  k4 x2 d! u9 U7
8
9
10
2 O5 U* {: I* y4 i7 a2 [11
* r) s/ e$ O  z6 U, o12
& i6 [1 L' p" k; y& j13
14
& ]. G% R+ e  e, }15
/ O) D4 P* c/ n% L  x1 m8 L8 ^) O16
! z7 `- b( l) ~+ W17
# N, T1 ^; s& z  W" ^18
- S1 h, C; h  m0 L19
20
! P2 \* J) ^# ]9 l1 b: s21
! W* I) Q& q8 T, z0 a22
/ Q5 L/ i$ q9 K) B! t( E' a! a23
24
25
26
27
8 E$ \& g5 G+ j28
% ]5 x- b3 [$ o7 e* I4 O* n5 ]29
0 \% d- i5 V, I% n# i30
( \7 P2 d6 _  M" P9 Y31


8 O; [2 J! v4 B+ v& I! _: Q& f9 J6 T稳定性
插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以
) x# Y5 P# f7 Y+ b# E+ e( ~
2 t" u7 \3 M- v$ Y  C直接插入排序是稳定的
5 g: a* k! l6 T4 i& g
5 W$ Y. q! O, ^复杂度
, {% V! W# I1 I8 p时间复杂度
% x% z" ], `2 }+ q最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）
/ z1 c0 {8 B1 }' B6 Z5 R
O(n)

最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2
0 k5 v# A2 o8 I: i
  h" K3 B5 p' e( E7 nO(n^2)
* ?" l7 O9 I( @
空间复杂度
; S; l3 `) H# m! m& H3 UO(1)

' Z1 P) c9 k3 R, i希尔排序（缩小增量排序）
8 P7 c3 F# S/ E+ Z/ ?( H希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序

优化思想
增量gap不止用来分组，也意味着数据移动的步长，所以
- Z- y0 p! V3 k
: S: @7 @9 T/ c$ V1 M1 J" ^" ogap很大时，序列很无序，插入排序的元素少，移动快
) ?% a! t  y0 ~! ?* T3 }$ g- d2 ggap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高


' O# o) f8 K8 p. Z. \9 A: @操作
& }3 }3 O4 C5 ~- g单趟排序：

设定一个不断减小的增量gap，也是元素移动的步长
以gap对序列分组，并对每组分好的序列进行直接插入排序
# C9 T) v5 {& v1 a, L' c* m5 K不断缩小gap，并排序
*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
整体趟数：

$ h9 s3 ]- ?' B$ m由gap决定：当gap = 1，排序完成
3 W+ y) b+ r7 b5 }! R! V注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。
! J4 {( H# r7 q( {# d/ _
# |9 p1 T0 X5 J% Z* pvoid ShellSort(int* arr, int sz)
{
        int gap = sz;
* S6 i* f% v7 s" l       
0 G. M- p6 [. r# F! n' \( u    //gap > 1，预处理排序
8 L* p+ m, n0 N  M+ K% Y    //gap == 1，直接插入排序
        while (gap > 1)
        {
                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
                //gap组
& U. L: [) R/ X; `; m- b8 ~+ H6 L                for (int j = 0; j < gap; j++)
                {
* t; g$ F3 s" P            //end + gap < sz
                        //end < sz - gap
5 x1 x, y% `4 Y                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
% }9 l6 _% z3 R" s5 V4 [) Z                        {
. s" J2 g+ K& y# J                                int end = i;
) j8 i' D, W. m8 Q% {                                int tmp = arr[end + gap];
: g& u5 x! u9 r* k& E3 s/ y- ]2 s                                while (end >= 0)
                                {
: ]/ @$ E0 o8 K: T6 T                                        if (tmp < arr[end])
1 h: Y0 B& Y5 b; k4 w& p7 `                                        {
, m: Q7 u  Z' A# X# V9 {                                                arr[end + gap] = arr[end];
                                                end -= gap;
                                        }
                                        else
                                        {
                                                break;
                                        }
9 G( [, g" t. d. G( A, @                                }
  y/ u' f$ n5 u1 [) H) J( J% Z* q                                arr[end + gap] = tmp;
$ g$ a( C' L1 l- T# d                        }
                }
- u5 f' [) k2 V        }
4 T* t. `& }) g}

1
2
3
4
$ t( f" q9 I, g: D. w( X" b0 L5
6
7
8
9
10
( R6 L4 E* m- v9 d8 H, a. D2 ], i11
! p4 L1 B9 c7 q12
) e. [9 @3 S& G9 N  ^13
3 q. I4 G; c3 b# v; ?' C. e14
" r. ~# |4 x  a: `, |- I0 H15
$ R* n  J" g3 o8 h( E6 s16
; N/ Z6 Z2 y$ E& l! Y17
: @" t( A, @8 Y' N, V, O$ Y+ ?$ m1 K4 o: U18
% W) a8 _; [7 ~% q19
, T) i4 \0 y7 H# M' o5 J20
  n. `$ ]9 M% B% r* E21
6 g, B" M4 i; R5 G, z, d" J22
23
' y, |% N9 Y8 z2 `9 T  e24
25
8 z9 b: U7 _& i& J- S26
, Z1 J2 d) Z# _1 E  h27
28
29
30
31
( `0 c9 Y( Z& T: F& J32
  c$ F$ C+ W; N& l4 ^33
  m7 ^* ]) ]2 ?! _. b$ @34
35
. A# Z8 j8 c, x1 t其实就是套上”缩小增量“的直接插入排序
1 k7 h5 E# ?& f7 p  s, ?& T( Y
0 N# d; h- {: S/ s
稳定性
) C% ]8 ]8 e* q% n; E我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以
. E9 a4 f# h8 T. V/ ]' ?
希尔排序是不稳定的
8 x% ]0 V2 d' }4 s
复杂度
时间复杂度
希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：

+ G2 U& Q) ~! {/ x3 G3 S% {O(n^1.3)

空间复杂度
O(1)

3 [6 F' h% j4 S+ l选择排序
4 p; }0 L3 _/ _8 D直接选择排序
% d. i8 }6 c; w" _思想
7 `+ C- X9 k. |# m选择排序，遍历序列，选出最小的元素，交换到左边


# w8 m1 |$ r9 t/ c5 M1 A/ _
; y3 o/ i) w8 @' Y! v7 U) I8 ~优化版本：
: J/ x! ~2 @$ Q2 L& l
3 m" h: S5 Q4 J* j0 R$ ^每次选出最小元素交换到左边，选出最大元素交换到右边

  @9 f7 f, L/ D! y/ w2 O8 h% A操作
) u5 Y: W, P3 E9 z" W" X设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]
! L; C5 A1 v; ~/ j- p
2 [: L$ n# ?5 J; A设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标
4 ]1 ~' w; i6 m8 Y. d
* R. g- y! T4 }3 m5 i6 ~单趟排序：
& B5 e- d1 v- \/ B4 O, n1 u& s
遍历选最值的下标
交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
（修正）
# `# _% ?; M& Z4 i& c整体趟数
8 `) J2 N+ P9 ^6 q& E
7 o  c9 P/ v1 a7 J若元素个数为n，趟数为 (2/n)
* A: p2 \- U7 l7 H" o; N修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标

void SelectSort(int* arr, int sz)
+ r  c* |; b7 J  @3 f2 h" `* d{
        //闭区间: [begin, end]
        int begin = 0;
        int end = sz - 1;
  L0 Z( y4 m& @  D- S3 ]! X$ G( @. s        while (begin < end)//begin == end 最后一个数，天然有序
        {
                int mini = begin, maxi = begin;
                int i = 0;
                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
, |3 a7 t; `. P4 V* _4 j0 X8 g                {
                        if (arr > arr[maxi])
% n, r6 y; Q" w4 e" _& l4 t, O                                maxi = i;
* i* g% d" R* T" U) j; n                        if (arr < arr[mini])
                                mini = i;
                }

" E' W5 N3 [0 q/ u4 H: k                Swap(&arr[mini], &arr[begin]);

                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
                if (maxi == begin)
                        maxi = mini;
  C) K3 w/ b! T1 d# M                Swap(&arr[maxi], &arr[end]);

                begin++;
                end--;
$ h4 @* n$ b+ z, ?. }+ d        }
}
4 l" p  W$ D# @; D
1
% {& U: X7 a6 P2 ]* `8 K5 U2
# [/ z/ c& a6 ~6 t; |; A5 C+ g3
" ~+ Q6 \& G6 D* [1 _1 k4
5
6
& d: r$ {, V  E" e- v. O# B) p7
5 \- f3 s% x$ z& G$ o8
9
10
11
% H9 Q" ^( N8 }9 o2 y+ d! O2 ^12
4 ?* K+ ~+ n6 \# y13
8 X! i8 T% C* K, U; Y: E14
6 c% n6 t2 M7 s' h15
16
" Z5 S0 v- v# x- I; k17
18
$ G3 w6 g) h: h0 K19
20
21
, |& Q0 I8 O0 V3 t4 J1 ?22
8 t% S" E* c6 q3 U! S6 r5 K0 F. W23
% W; Q1 T, T) }/ F5 ~; Z24
25
- `0 S& k2 X# I/ d8 _0 j26
! Q+ r/ P2 M7 c6 Y. Z3 ~, o27
28


3 B- c3 D% n; N3 _& D稳定性
/ v7 N2 h, v, F' i: m% |: S选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以

选择排序是不稳定的
# _! ~0 A8 ~; h* J1 o3 i6 I
. G1 O" j5 \* M( l复杂度
时间复杂度
最好：
+ ]6 r* \. S# U0 Y
5 G. A! c! e3 @4 O比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2

交换次数：O(1)，有序不用交换

$ Z+ y: [' y9 Z4 ?) e/ l% \% AO(n^2)

6 }' J5 v, F4 U1 K1 g$ T3 o/ k: B8 @最坏：

+ h0 J3 X1 L/ x5 s+ v比较次数：O(n^2)

交换次数：O(n)

8 Z5 X8 Q; X3 X4 m5 b6 qO(n^2)

空间复杂度
O(1)

+ z$ [& D( [& |. r. N! a* T堆排序
思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆
+ V0 ~5 A! C+ r  E9 K' H+ Y

/ [0 Y) P. I$ ~) R7 S
操作
建大堆
, Z4 `7 l0 U6 V' p- u( P单趟排序：
选堆顶和堆尾的元素交换，则堆尾的元素排好
每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
# r2 Y7 O/ \8 F7 i; K整体趟数：
若元素个数为n，则排n趟
void Swap(int* e1, int* e2)
{
        assert(e1 && e2);
( \; ~; ^5 C: V  {8 a
        int tmp = *e1;
7 n1 M6 W/ n& W: O        *e1 = *e2;
7 n/ w( j9 ]6 W/ \* o# H        *e2 = tmp;
$ S7 g! \% K: w; `( c% l}

void AdjustDown(int* arr, int sz, int parent)
9 |1 R3 ?( I0 Y{
        //建大堆，排升序
        assert(arr);
       
/ `5 Z6 B, O2 g' r4 a; n    //默认大孩子是左孩子
        int theChild = parent * 2 + 1;
: F: E/ B& r( K% u" d6 L* H        while (theChild < sz)
        {
# j" I6 n8 z) m        //如果大孩子是右孩子则修正
, y# K8 Z+ e/ F                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
                {
                        theChild++;
                }
                if (arr[theChild] > arr[parent])
0 r  }* z" e7 \  D& n' I                {
6 j0 H0 U/ |/ n- O9 V+ ~7 M& C) p, y                        Swap(&arr[parent], &arr[theChild]);
            //迭代往下走
2 i% l# I5 Z$ |* T1 K                        parent = theChild;
# j' I$ m+ m+ _6 w9 |                        theChild = parent * 2 + 1;
& `9 P$ ~% m( f& c9 C                }
+ L# N$ u! h. p) N                else
                {
                        break;
0 l3 C) b/ g6 o6 W9 r' ~( H                }
$ O- T' z  L$ b2 o- M        }
; m) S1 q+ _. F}
# U5 W9 y' R. K$ v+ }
void HeapSort(int* arr, int sz)
+ }; I- K) t. ]6 N/ ^{
        //1.建大堆
        int i = 0;
        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
        {
                AdjustDown(arr, sz, i);
        }

        //2. 选数
        i = 1;
        while (i < sz)
        {
                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
% o" y; F0 z: @! q                i++;
# R( o' T: F, D        }
}
! }6 b2 v6 t- I0 \- T1 C9 ?
1
2
& I+ q# K5 j! ]5 o8 d3
4
4 m) `! }& N( Y, l3 t5
6
7
% K8 q9 e# h1 r2 N: n5 L* ~1 ^8
9
10
11
12
; U- t3 Q: T5 j* I6 Q4 F13
* o. D) @5 y6 q! C  C8 ?14
15
9 {9 @, W+ _  F( J& E. ^  X1 T& C16
- K. `& ]3 \' o, u& Q17
' z! T; |; }1 Y; E18
19
7 y# E0 v; D( ?  Z4 S3 g6 p20
21
22
& }3 ~' S9 b9 L. _23
24
5 g! D6 \$ ?% N1 g  H  p25
1 E6 F) y# G% t26
* u6 U1 t$ F8 s" s+ ~27
28
) V/ B* l: x# M8 [" {% k7 K29
& ~9 M  X. B* {! Q5 J$ h$ C30
31
32
33
! i" j1 z+ H- @$ ~+ E" ~7 X34
35
+ |' T8 u( o" n36
& {. G( i( T( O37
% L2 z: d3 B* G5 Q" o38
39
" h, e! f7 X6 \  Z" u" Y40
7 z, K, D; d% b: A41
42
43
44
45
46
+ [: M  I8 R& s3 K47
48
49
  R' B+ T- ], c7 `4 [6 j1 o- H50
% T6 R. \9 y7 D0 B- L6 ?/ i% y51
" y2 i+ B; i, r/ T52
53
54
55
1 s+ t# W# B: E) e

稳定性
9 g3 ]1 Q) o9 [( H建堆和向下调整都会打乱元素顺序，所以

堆排序是不稳定的

复杂度
时间复杂度
7 ]7 S; q: s2 f) z$ W# \单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为

& `( |' V0 k7 VO(n*logn)
. t/ I4 e  A5 `" f* K' c
空间复杂度
原地建堆
  ?" A, K" a" S$ @
! k- h' m9 K6 l6 hO(1)
- j) n$ L; I4 H+ u& _. R
交换排序
冒泡排序
4 p, V: k& e) o8 K$ _8 y思想
冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素
: e) i8 o1 ]) l/ w: U
! e  G. `: I3 `: e7 R
, E$ w2 q+ k8 F; I
* A& y+ @9 D8 ^操作
( V  g& `4 p; {5 F7 B8 `6 l1 Z单趟排序：
每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
, s) w: ?! Q" Z- Y2 R; }每趟排好一个元素，所以需要排序的元素每次减少一个
整体趟数
! k: U: b% o4 m% B% L若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
void BubbleSort(int* arr, int sz)
. I1 Z) j: K& c  l8 q. V# B{
        int i = 0;
        int j = 0;
$ [: A5 u8 ]+ z: @        for (j = 0; j < sz - 1; j++)
        {
                for (i = 0; i < sz - j - 1; i++)
                {
& S# k6 F5 Q; I* _( f6 z7 f9 J                        if (arr > arr[i + 1])
                        {
                                Swap(&arr, &arr[i + 1]);
                                flag = 0;
                        }
                }
        }
}
' ]; G, p3 A* G" b
% }# V$ r: e2 Y9 x/ e5 o1
2
5 |' N. V5 w% _7 H1 w4 a) w1 s, Y3
% h. g/ t# r6 V8 S+ k4
  @! G' O- P' H6 v7 T( [0 O9 ^1 ?5
6
3 o, Q9 z0 a: ]" ~; ~' x7
" ^4 b2 l8 f3 a& U$ M8
5 ^7 h0 w& P# b8 a) b9
10
11
12
, l' R% i5 `+ H) q  c% i13
4 R- w) [0 Y5 G# }14
: K% o5 P/ e$ }15
/ V8 d5 M, I9 T' X: _16
优化
# W" [9 }; Y- \# j' y: |- J1 v% Y当遍历一遍发现序列有序，直接跳出
( h, c5 V7 k) @: @  s7 B# \
void BubbleSort(int* arr, int sz)
" R$ D# o/ M. g8 h3 I2 J{
        int i = 0;
        int j = 0;
        for (j = 0; j < sz - 1; j++)
/ J( r; d7 q9 v0 ^0 h- B        {
                int flag = 1;
                for (i = 0; i < sz - j - 1; i++)
! x" `4 q* f$ ?, }                {
                        if (arr > arr[i + 1])
  d# @4 E% @9 h! J                        {
                                Swap(&arr, &arr[i + 1]);
                                flag = 0;//不是有序就置0
                        }
( I7 b  K/ B% C9 J7 j, v                }
  b+ V5 L3 o3 g# x0 _                if (flag)//如果一趟下来还是1代表有序
                        break;
        }
$ F8 C6 N6 b" i}

1
! c6 |: |& M- G* i/ w8 k5 T2
3 u/ p2 O# ^4 T. Z3
0 ~9 r% I8 ^3 E/ D/ ]4
5
6
& D' D1 u( d, d! Y0 y  N( @7
8
7 S; b; U# _" P9
10
; Z' e7 W8 ^: _. ^" S5 a  D11
+ v) B  n& U, Q7 I* {5 g- w12
13
- I2 V- X' X) {' ~+ V0 R14
4 z! Y! @& Z$ G15
16
17
18
19
) V: N* R9 o- [7 C( |  M
+ a! S3 J& V  R+ R% c3 ~) o
稳定性
- d4 U" d2 W  P1 Z相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以
! E& {% s* \- n1 L/ q
冒泡排序是稳定的
1 s( g- ^) G& ]3 {: M5 v/ M
复杂度
时间复杂度
最好： 当序列有序

" d4 s: J+ d9 s  `) b1 \未优化：
8 ^5 V$ {+ f0 B& t5 ~; z4 P$ F
O(n)

优化：
0 g& H$ r# j6 u# Q9 u0 F
O(1)
: I, D/ c3 }6 M! q; y
6 @. S# l# n8 R1 H2 W最坏：要进行 n-1 趟排序，每趟交换 n-i 次
! J& A7 o9 N6 o0 l8 q: C
+ Y. `' ?% f% o* |3 p4 SO(n^2)

( l" `4 M  n5 f: A8 c空间复杂度
O(1)

快速排序
2 ~. c% Q: ]  Z& E5 d" n0 b* }思想
分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。

所以快速排序可以用递归来实现
2 f7 p6 L2 N/ z5 w
操作
有三种单趟排序的方法：

Hoare法
" m6 L7 l. `" E设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间

- j( D: w" x! i# E' G; O& o; V左下标 L = begin，右下标 R = end
, j) O  s/ ~4 X; W% {9 n
" R0 H% a9 Y9 J: `; f设 L R 相遇位置为 meeti

" I; v/ W1 e4 H1 Z& f9 T​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”

​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“
* b9 l5 X; x& G$ o5 z
选 键值的下标 keyi
" o3 v  T2 y2 S: x
7 Q% r* \" Y8 [* N7 C左1位置作 keyi，则 R 先走
9 v/ `$ _1 n$ z2 i# }: o3 K1 {, n+ j右1位置作 keyi，则 L 先走
+ E3 V; l% F4 y' J/ jR找小，

$ Z" U5 E: W5 e7 q: Y# a找到则停
遇到L，则交换 arr[keyi] 和 arr[meeti]
L找大
. U/ c& K+ f6 s! c* s0 G* z% T  S2 x5 @
. z% J6 k% W6 `找到则交换 arr[L] 和 arr[R]
遇到R，则交换 arr[keyi] 和 arr[meeti]
! a4 ~- N) k# ?! ]8 R: d

解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
答案是肯定的：
( _2 ?" ?% U( Q
; y3 \0 m2 K' _9 w" i


4 l! S0 P; X7 h4 p3 F//[left, right]
7 O, k, @: G7 n' ^0 Dint PartSort(int* arr, int left, int right)
/ n' M, w4 g& j# R7 b# }{
2 y8 z: A0 |. f5 j5 f        int keyi = left;
) u0 B8 x2 u8 z+ ]        //相遇则排好一趟
        while (left < right)
        {
                //R找小
        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
  C1 E# H2 k2 Z9 K( I& l; ?4 b        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
" S- J% a0 m& y7 ^3 B& G                while (left < right && arr[right] >= arr[keyi])
                {
% V/ |9 ~8 ]% {# N                        right--;
                }

( R: K/ S# a. c                //L找大
5 r. B" i2 K- U5 Z0 Y6 p+ j$ P, ^                while (left < right && arr[left] <= arr[keyi])
                {
  g/ |. y' q& ]6 g, n+ ?, e8 Z                        left++;
3 K3 Y4 m, U. y+ W" v( h                }
; J, f- x$ |4 i9 M! [- y               
        //相遇就不交换了
, `- p; V) r5 I% j# t                if (left < right)
, f- V9 M$ f0 L* S8 N3 Z                        Swap(&arr[left], &arr[right]);
- f$ P: p2 y' S8 r) T        }

, a; {) Q% s3 e0 j; J$ M        int meeti = left;

9 r- @2 [2 y& p; L        Swap(&arr[keyi], &arr[meeti]);

9 k" Z/ n3 Y0 Y        return meeti;
5 P/ P( ~* F% r, W" c5 B}
/ M% k) @7 R* A1 J! U3 S1 m; R, D
( r; Q2 G! J+ T1 A' m: a, k1
2
3
4
5
; Q3 ^! v& M" L  C, b6
2 B( W: {, f+ M0 T- }+ m$ k7
8
8 i, d/ g2 I" j% _, H' Q  ~9
! _0 E  M' t! H/ }10
- J; v/ [6 v- ~11
12
13
) D* ]! W& ^2 q/ v14
15
16
4 p/ L. E) `  l) a" S4 n17
9 C9 z( v% ?% _. f( q5 j18
. w; z& ]6 x9 U. P" @* E1 z19
5 a4 T' m9 k/ g. \; o+ D20
21
22
' E' b( \) T' y0 @" |& |23
24
3 h9 E: v. |8 K25
% [$ z, a/ I2 E# S26
27
28
29
30
6 m5 b/ A$ |& Y- e1 `8 i) r$ G31
32


解惑：为什么key要选左1/右1，选中间不行吗？


可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深
* e4 L  b6 d# N3 ]9 `

4 w1 [# g: Y8 ?3 i7 E

非常容易栈溢出，怎么解决？针对有序情况，优化选key

) W& s( D  H# R. E( F9 H优化选key
随机选 key （是一种办法，但是不那么彻底）
, T$ W- `: I8 F  F选中间位置作 key
解惑：那先前实现的单趟排序不就失效了吗！
0 Y% E7 H+ o; W/ B* b/ F5 ^/ k( ]：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑
$ d9 E3 y5 Q7 K" G7 q' _( Y
0 Y9 L) i$ k; z+ ?" z解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
前辈给出三数取中的方法
9 C1 B( H. l- K; C
三数取中
3 U, {, o- T9 W7 I. V在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
3 a' ^- |/ l9 y' M, Q& r这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
优化选key后的Hoare单趟排序：
1 y( ?' [# F& X2 J
int GetMidIndex(int* arr, int left, int right)
{
% m# T" _2 W: Y        int mid = left + (right - left) / 2;
% i6 h& z2 N/ F//  int mid = rand()%(right - left) + left;//增加了一定随机性
8 t& ?& J5 ]2 ?        if (arr[left] < arr[mid])
! ^, U/ P' A, k2 A9 ]9 k* G        {
                if (arr[right] < arr[left])
0 V; x/ z# X# P; e$ D' |& `                        mid = left;
& s& L3 k9 a2 `/ p- D) E2 ]3 r                else if (arr[right] > arr[mid])
                        mid = mid;
                else
                        mid = right;
5 L7 s1 M1 A2 p        }
        else//arr[left] > arr[mid]
" V. o9 B3 Z+ y8 ]/ B* p        {
3 {( `7 F! I4 J% I2 h                if (arr[right] > arr[left])
                        mid = left;
" r; [3 b" v- Z& j: z, g                else if (arr[mid] > arr[right])
$ w7 f8 ]$ }* \6 |                        mid = mid;
& S% C% A5 t, \( Q$ t                else
2 h# n9 \* Z+ u                        mid = right;
        }
2 x3 G% c- w2 w; V        return mid;
; i# N  @# i8 n" ^9 x5 ]/ \}
8 n+ v* p+ \1 V: c
int PartSort_Hoare(int* arr, int left, int right)
{
, q: `8 \' Z+ d! @8 R& ^% G- ^$ M+ v        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
        int mid = GetMidIndex(arr, left, right);

' S' `, I: w: _        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
& A7 k+ ]$ S  L  V$ K3 |! K* E! _9 y        Swap(&arr[mid], &arr[left]);
/ X( r% H; _! S9 W- i, u
        int keyi = left;
        while (left < right)
3 \0 n: k+ j2 C; Z2 N5 T        {
                //R找小
                while (left < right && arr[right] >= arr[keyi])
% T# e2 x* C( P7 Z* q                        right--;

- j/ ~! @  h3 |$ q! _: c4 R                //L找大
' l% \  j' M' D2 S! _6 i3 ^6 j% P; u6 ^                while (left < right&& arr[left] <= arr[keyi])
                        left++;

                if (left < right)
3 u* J/ m3 {: U1 D0 m; |                        Swap(&arr[left], &arr[right]);
6 T: a7 r4 q; s8 i6 ^  j; V        }
0 F$ m3 B% m: j' ?3 k6 z
        int meeti = left;
3 x7 x2 m. v; W4 X
& x4 h4 v0 p% z. a& I- _; K        Swap(&arr[keyi], &arr[meeti]);

& o1 U3 u7 ^# K' [        return meeti;
}
5 h9 _" x2 E$ j) B) ^
1
2 y" y0 J6 a# F% W9 n# F, T: M2
+ k% v5 f- C; X+ }$ b' s5 T3
4
( O' q# j9 h" S1 O/ g& M5
6
# M, O/ e/ @* e3 Z6 w( V7
* J2 T! \; h; k8
9
10
11
, }, B! @; L# W4 T1 k# O+ s0 r12
13
14
- y9 t$ @  Q6 j, Z- z9 K15
16
17
: F0 g4 c3 S7 |/ o18
19
& Y2 g8 b- H4 O7 b; j20
21
1 o3 v" i  I, `* o8 f22
23
8 @4 J) `; S. C24
0 H7 n% K" v2 D- Z# G6 ]25
26
27
28
29
" T, R& m9 w* O4 ^7 t30
9 I5 N& D4 F0 Z  i. E31
32
1 p& y' T, I+ n' h" ~, U33
/ m* `; s/ t8 _8 `2 `34
35
- m2 J1 l7 p0 G$ H8 V/ C36
37
38
4 w- W3 g2 I5 C7 `" b$ R- }39
40
3 i+ J+ U, D6 T: ^3 v, n  ?41
6 y( x) M! s/ i% {3 t4 N1 r42
  `2 o6 |' }# @" ?& q3 R- D43
44
45
46
/ g8 f$ L( [/ h  F47
" S7 K7 p$ X$ @5 Y3 L# r48
49
! A' \. ^! N, U/ a4 y# a4 v7 {50
" }5 Z; q8 z8 u- `51
52
53
54
挖坑法
! I6 c% }$ U5 U( N4 a# P4 U初始状态：L作坑，其下标存为key
: o& D  i4 B& B' a# o; f(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
重复 (1) (2)
最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]
, z, ^+ t2 ?% J. N  f7 J3 Z" Q
5 C; [# [1 k2 D- I
int PartSort_Hole(int* arr, int left, int right)
1 F0 z7 h" j0 l7 V{
4 U5 p* X' N. V5 ^2 M+ w. w        int mid = GetMidIndex(arr, left, right);
1 c. b2 D' ?6 O- j7 [1 q, g        Swap(&arr[mid], &arr[left]);

        int key = arr[left];
        //L作坑
        int hole = left;
/ T  [$ Z+ Y9 `/ o0 L: {* q# c        while (left < right)
7 z2 Q+ |2 p" H8 W- q        {
                //R找小，扔进坑，R作坑
                while (left < right && arr[right] >= key)
- ?, c! N) p8 m' e1 e# M; Q                        right--;
                arr[hole] = arr[right];
) T1 L5 h) j3 T' w6 o                hole = right;
& D) b* k5 X, k4 g6 F) ~
) T! e1 Q% S4 e9 Z- {5 F                //L找大，扔进坑，L作坑
                while (left < right && arr[left] <= key)
3 f& @6 i0 p% g/ s0 n5 P                        left++;
$ A1 r! y! n7 }+ U* w                arr[hole] = arr[left];
1 `3 E" r- T) y/ Z; B  Q3 @" \                hole = left;
        }
        //meet
        int meeti = hole;
7 ?$ b2 g  Y+ A: f9 l. d  v        arr[meeti] = key;

& f( R- Y) `; f5 v        return meeti;
}
% j& g9 j: G6 k& p
/ Y8 w( A0 a5 [' A1 s7 w3 E0 R! J1
2
, k& s  x% [0 ]$ m; H3
4
5
6
  F# \$ A' e1 S$ R& s+ \" `- J7
6 }3 N# i0 A; _* v8
9
+ x8 @8 R# W! F10
11
12
  Q! u' _) p3 S6 e( a, |1 a13
14
4 A6 c( q. t: x15
6 c! T7 c( b; C- u16
8 E# I/ f1 ]4 g17
6 }2 K" L; [. K2 X, r18
19
% s) @  ?& ]2 w# ^8 N20
21
22
, K4 q: p" p. s* D, e3 _: M0 |23
( K0 q1 s  W. `, }; `- @$ o24
, h: _  ?' u  ]4 u8 N25
26
/ |: V" Z' f# L  g& r+ u27
28
前后指针法
: l; B" Q# s6 C, [8 Q, C此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多
' V" w+ ]) }, |. W0 `% T
cur找小，找到则停
6 O) O& i3 x! A* P, A4 E++prev
* v! N9 n) ~  J0 R如果 prev != cur，交换 arr[prev] 和 arr[cur]
如果 prev == cur，不交换
当cur越界，代表找完，排好序了
# [, S: n0 r/ k6 Y. \- @2 g% g5 dprev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低

) K0 ^/ g( P% Y3 q: E

int PartSort3(int* arr, int left, int right)
6 H5 ?2 }/ x, J, I6 Q7 u, s{
! v/ B) ~3 X$ v) [6 X7 s        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
       
- D! \3 @, e4 s" _4 I' D  //int key = arr[left];
        int keyi = left;

        int prev = left;
8 z( h7 u7 L# {+ i        int cur = prev + 1;
5 H. R2 J2 N; Q8 W       
3 t/ K2 j+ [: [# X    //cur越界：找完小的，prev的左边全小，prev右边全大
9 Q5 x  q. J4 u3 u2 {4 f        while (cur <= right)
7 @9 X' c% ^# v/ @/ N8 J4 e        {
        //++prev == cur 没必要交换
                if (arr[cur] < arr[keyi] && ++prev != cur)               
                        Swap(&arr[prev], &arr[cur]);

                cur++;
, d: Y# U' Y, j7 d; {* `# g0 i% I        }
; ]$ A; |' z9 ^& D& [; U2 y
2 t2 s" y9 d/ M( l        //键值存是的值：
; r- ], G6 v# I) c0 c        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
        //Swap(&arr[prev], &arr[left]);//这才对
    //键值存的是下标：
0 x' K' h# Q$ S2 B7 c8 t        Swap(&arr[prev], &arr[keyi]);
5 `3 v! {* g( @  t
        return prev;
}

% R" Z. |2 D" X  g8 Q1
2 ?3 j4 t  J, t9 z, e+ [# n2
3
4
, I) t/ d& R& `& `0 e5
$ _, F; \9 i8 D6
7
- D  }& ^! x9 ]! ]$ u( \7 l8
9
10
& c/ S! e2 j* b8 N+ @( h. `9 \11
12
9 \2 |, W" d3 `, L; q3 F13
14
2 t, ^, V$ a. U3 \' w8 E15
# n; k# k! H/ `0 I16
17
- K2 S7 C4 g, \& h18
19
20
21
$ U  F8 B8 K+ w2 G7 F22
23
0 e4 p, H# [& u4 ?0 Y" p* }, b24
2 X/ C1 L! O- [' n/ @9 \25
26
27
28
6 k. N' O8 t# L# Y/ g29
整体排序
( c8 X' X7 @! r$ J2 h递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排
# O  E: z- G; g3 z: z% d
) L  I4 f0 c+ V3 @& h9 m//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
# O: v7 x6 R5 l8 _0 g. U& ~        // [begin, meeti-1] - meeti - [meeti+1, end]
                //1.begin > end:超出范围
                //2.begin == end:一个数天然有序
9 W5 ?! M+ i/ V* w. X! l* Q1 u9 f    if(begin >= end)
        return;
, q* @; l+ w3 Q7 b
                //排好meeti
  [' s5 X% c8 Y- Q3 b: n- t                int meeti = PartSort3(arr, begin, end);
) @+ `1 O! Q& T' Q+ i
+ @$ q" K6 h. |+ M) |                //排好左右子区间
" v" C& c; t; T0 T3 i% k8 |3 s                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
; w; R3 u/ u0 n: j% D1 d        }
. ~1 x7 v0 f; p5 F" a* H}

1
( }5 y# b" M8 _' Q' Q2
; c1 ?1 s4 l: k2 m/ t/ N3
" Y# |2 ]+ W) \4
5
3 g! f1 R: S6 ~; K1 I6
$ _5 E. C: ?3 k( G7 t# Y+ x7
) O# p: o) P9 K$ a+ W8
9
0 m- {5 [" {. L( X3 P10
11
12
& i$ p4 |" w5 k: h/ O! p6 j( n13
14
15
2 z; o1 t* s" X5 F( h16
17
18
…
7 {2 H+ l; |( ^
没想到吧，还还还还有可以优化的地方！

% K/ B; T/ z( P' J! Z* E; w  G+ O- V优化小区间


0 |0 w& R; n9 W$ j: p0 |1 E9 E; S如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序

; A' C  E" K3 Z, z3 T4 M那什么算是小区间？
, n9 e- ^0 f/ ]8 S4 R7 O
7 L- H) y8 T- N- u5 C, @/ {4 M其实小区间没有确切标准，8-15左右都可以的
1 @4 H0 l6 x# T

" z6 A' {9 f) T9 O& S" x# V0 j这里就把小区间定义为 含有 8个数或以内 的区间

) D2 h. N. }; V/ _//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
        if (begin >= end)
                return;

7 j* Z3 ~4 x7 B8 x6 A        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
        {
                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
4 ^, c- t% `. L9 S( u3 I                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
8 _0 ~7 s$ x/ x* {  E; T+ n9 M        }
        else
/ C: H7 [2 [4 k0 p/ ?" b7 A        {
                int meeti = PartSort3(arr, begin, end);
! J: G( K. X7 @% o( G6 w
                QuickSort(arr, begin, meeti - 1);
  r7 R. r6 C) _1 g4 B                QuickSort(arr, meeti + 1, end);
" U. M8 ^9 i/ t/ I: ^, j7 ^' P        }
, k- C) H3 a4 Y0 v  }& Q& F7 C5 T}

' p  X7 d% t7 U" e1
2
3
: C2 C3 n5 R2 W6 v6 d4
3 e* y3 m7 e9 R8 J5
* u6 L( Y/ k) x6
7
8
. y9 E; ^& ~) x/ G! o6 R0 l$ J9
6 P5 k& T% N' c0 D3 A10
' |7 L. _! s- }: F11
) T6 F5 s4 q0 K- }$ ^/ j- {. }12
13
14
15
16
17
18
19
快速排序非递归
5 e* G6 K1 u6 e- P( S1 W1 j为了解决彻底递归深度深的痛点，我们来试着把它改成非递归

9 k# e5 g! j3 z: V9 ~$ G思路：
递归深度深，栈的空间又小，会栈溢出…

! G7 f/ q, t; S4 C那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！

( t; @) [: }2 T: q$ q( D核心思路：在堆上创建“栈帧”

快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的

1 Y+ g$ g( |  M1 l. c
5 A- u: `* B; H, [; W9 u9 F
在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：

1 H  L  g  h% b/ J1 i' K+ k6 b  W先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
6 \. P  B0 D7 }先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
2 o$ a! y! e6 p8 C* K{
; j0 J* i4 Y; n" W1 `' w% [; ~        ST st;
        StackInit(&st);
* X2 S' l4 J, o5 }       
- D" l: b0 }" ^9 B4 e5 a3 \1 K    //先入begin
        StackPush(&st, begin);
4 H$ [, G' @; |- ]    //后入end
* g' O$ ]0 N% O' e        StackPush(&st, end);

        while (!StackEmpty(&st))
        {
" d( ~5 Z6 O9 \, u$ w                //先取end
                int right = StackTop(&st);
                StackPop(&st);
                //后取begin
                int left = StackTop(&st);
* w" T: D" |( u3 Q! p0 L( v# N                StackPop(&st);
; o$ u- T& L. S/ e% i( m; c3 P2 i
                if (left >= right)//1.只有一个值  2.区间非法
: F: \3 n, s2 q) E7 f. E' q/ N                        continue;  
                               
. g' _: i/ s9 V4 i                int keyi = PartSort_Pointer(arr, left, right);
. y7 ~5 U( e9 S, d
  q4 c: d7 P& |( X. b                //先入右区间
" A/ V& F, O, h) P  h                StackPush(&st, keyi + 1);
                StackPush(&st, right);
                //后入左区间
. C3 l7 \1 c' R( e1 }                StackPush(&st, left);

' b* J6 x, Q2 M/ Y                StackPush(&st, keyi - 1);
, K" f% Y4 P* j5 k! w+ ]3 l4 T$ x6 g        }

  m- g, o/ V  E9 D$ |        StackDestroy(&st);
" A0 N) f, P4 @& m6 T}
- I9 Y4 A: ]% l6 s+ c$ h: E8 O2 E; v
2 |" o" {# ?! E. c% P  `3 A1
2
3
2 p( r: f, }5 T2 Y2 B# d2 m2 p4
5
6
- A; _6 H3 |+ g/ T- t7
, L4 n  ]# e) ]  J; C6 O. \8
9
3 J. Y9 {- g8 x, P10
11
$ M2 |6 h0 ~& }; v4 A4 S12
+ e; @. s" \3 y* H; f13
14
$ G8 P- Q3 d" L15
16
( V4 K) C# {: S' x* L17
18
19
20
21
22
8 T* |, N' ~) c23
# q! M4 p1 g  h- E24
25
26
3 M2 i6 p2 B" ]" e/ v" `3 q27
# O0 h) G- E1 x4 H28
29
30
0 v& x+ b+ Q9 v; y31
32
33
5 T/ Z) O) f4 k% m34
35
& {* Z+ E/ d4 Y数据结构栈的实现可以看博主之前发的博客
. N4 O+ r9 X* h* I$ G

5 q0 O3 N; K! {9 T归并排序
$ j( \3 t) n6 U0 Z
  F& b% e2 _+ ]/ ^…
/ W2 r) \" i/ W2 L" Z. _; V; l( \) P
性能测试
void TestOP()
{
        srand(time(0));
& W0 S8 X) U8 o& W& \        const int N = 100000;
% g( Q% k  o- T3 s/ a" T! ]9 @        int* a1 = (int*)malloc(sizeof(int) * N);
2 _- E; I0 ?( J( i1 B& [2 o2 z* q        assert(a1);
: P4 @( {/ K; }        int* a2 = (int*)malloc(sizeof(int) * N);
; J; V: V$ D, E        assert(a2);
        int* a3 = (int*)malloc(sizeof(int) * N);
! T- e+ y2 D) }; J7 ?  R" M6 ]        assert(a3);
        int* a4 = (int*)malloc(sizeof(int) * N);
8 T( }1 a' ]4 |3 F, H% S+ M  s        assert(a4);
        int* a5 = (int*)malloc(sizeof(int) * N);
        assert(a5);

' o- K, L4 @# \: T+ ?' }        for (int i = 0; i < N; ++i)
        {
                a1 = rand();
% m! j0 ^+ n" c2 K8 {2 O- \                a2 = a1;
                a3 = a1;
                a4 = a1;
: G! ~( J1 C% f) R- G$ x0 e9 T  t                a5 = a1;
        }

& A  ~  B) t( d; R0 q        int begin1 = clock();
7 d4 ?9 c! P+ r' _) r1 E9 W! f/ P8 j        InsertSort(a1, N);
        int end1 = clock();
7 {( J% ~: F. z) p9 h- W5 x
+ y- j2 f. M, b1 O        int begin2 = clock();
, {1 b+ b+ v. H, R. e        ShellSort(a2, N);
, w" t4 {+ E/ A# c1 j        int end2 = clock();

        int begin3 = clock();
        SelectSort(a3, N);
        int end3 = clock();

        int begin4 = clock();
        HeapSort(a4, N);
        int end4 = clock();

2 Q% |2 [5 [: E5 m0 a! Q        int begin5 = clock();
        QuickSort(a5, 0, N - 1);
. c7 y. h& |# o* }                //1.中间key
( N" X' ?+ Q$ D4 F% A* \9 O                //QuickSort(a2, 0, N - 1);
7 {2 O' _! X& C6 m8 n                //2.三数取中
: q9 Z6 @2 t1 V9 \) X1 k7 e                //QuickSort(a2, 0, N - 1);
7 Z, y0 q0 ?8 N( [! C# d9 G                //3.小区间优化
5 {  w; Y6 A% Y6 K) y                //QuickSort(a2, 0, N - 1);
% S) f8 A) [9 o! I8 y( x        int end5 = clock();


        printf("InsertSort:%d\n", end1 - begin1);
        printf("ShellSort:%d\n", end2 - begin2);
9 K* D' x, b% [1 l        printf("SelectSort:%d\n", end3 - begin3);
        printf("HeapSort:%d\n", end4 - begin4);
5 I5 j7 p5 Q! h" ?        printf("QuickSort:%d\n", end5 - begin5);

8 y, w; ~" g; A0 q& ^        free(a1);
        free(a2);
        free(a3);
3 \  V5 [  a! x+ }- O2 P) V        free(a4);
        free(a5);
0 |/ c6 A& j# ?7 j, y: l2 J4 ~}
! Y- l; p) x2 Q% y7 r
1
2
3
6 J/ ?' J+ {8 j# O( F4
5
6 P2 m5 }9 O# _4 z! M8 X6
7 n! H* L' H4 F5 l0 _0 u7
8
) U0 j$ e( p, j* |9
  V6 H/ B+ g; E10
! P8 R' r& u& z0 l11
12
' G$ c# j( _6 s& o/ c- u6 n: y13
14
15
" {! K7 b" N* E16
) W! o; ^) M! v0 [0 H6 v$ o17
0 {& J' w' J/ G" A  y' d9 }, N/ {18
19
3 W8 d4 E5 N7 r$ v1 r6 ?20
21
7 s' W. J" ~& d8 B4 z$ f22
23
% g- i. I/ v8 [3 T" j0 J5 W24
25
9 G6 J# D) S! f  Y) q$ w26
0 o" X7 @* }1 p3 c, I/ _27
28
  r- @3 q* q  Z$ q) j0 p# ?29
& J  s+ }4 L; d0 c+ ]2 D1 ?9 }" f30
  y# Q2 Q( F" a% L/ o6 b, D5 E3 _* T31
32
33
34
35
36
: D; m0 ~+ l6 k) A1 h  R2 Q4 R% D  i5 v( H37
6 h( }2 P5 f) Q& \# x38
39
40
41
$ R/ r$ \* D+ ?- g# O. o42
- a9 ^5 d" W. M% P# M, l1 [, m43
44
$ ^, P1 B; r! ?1 }45
46
( O7 U) a- n; W47
48
- |+ I1 g2 Y$ l5 l- H3 A- L! d49
50
51
6 ^4 |" a, \7 z0 y52
! W3 C/ S+ N2 i$ i53
54
55
4 {# ~0 ?* ~" k* j# B  c56
57
& t6 H( @# }! O$ K) k( n- J58
59
60
61
62
63

: G& \6 j7 U2 I' O6 {& K2 ?
0 S" b9 `+ t& ~# n5 c3 C& H不愧我们费这么大劲优化快排，多帅哦！

差一个归并排序，后续补上！
. A+ J+ {/ |  c, o
% L4 A6 ^1 ~! ]7 \5 Z不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
————————————————
) u$ f! h$ X) W6 r1 g版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832

/ v: x1 ~, E8 D7 Z0 Q