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

杨利霞

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

& N) J  N+ C4 t9 Y3 S前言
本期分享经典排序：

插入排序
/ `  Z; Y3 i$ E$ k: Q" h) ?直接插入排序
希尔排序
选择排序
直接选择排序
. V( }' A1 g( w0 A+ p( R, T! z堆排序
交换排序
冒泡排序
快速排序
' Z) y& z4 p9 D2 ]  n* ?8 r( H注：讲解时默认排升序

# ^/ O( i# y+ _( ]1 _插入排序
' N: G" t5 }- z% \: H直接插入排序
思想
插入排序，就像玩扑克时，摸牌的过程：

最开始，左手没牌，右手从牌堆中摸
& U# }# y: D/ _7 W9 c右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
如此一来就能保证左手的排始终有序，摸完牌后也就排序完成
, \$ N9 @; C: ]# h% O

  ?/ ?4 X+ S- ?4 x- ^  q$ i操作
5 s5 ~! f1 x6 B, P6 }+ H设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
! O- U5 r. j- f. ?- d单趟排序：
每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
是正确位置：插入
; }, F+ N" N- i7 T, q/ `$ _. Q* J3 V不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
& A2 A4 m( J1 M% _6 D4 R整体趟数：
: G" ~8 Y. k$ d- F. _( U若元素个数为n，需要排n趟
void InsertSort(int* arr, int sz)
* Q, Q0 V5 }! d$ K: n/ L' U{
8 [( v% a6 C, c; j8 N        //end + 1 < sz
        //end < sz - 1
4 \. U) I6 p+ r        int i = 0;
        for (i = 0; i < sz - 1; i++)
        {
7 N/ J% R1 w. \, c6 k                int end = i;
! d0 K, Q" {8 r* p# j                int tmp = arr[end + 1];

                //找插入位置
" ], H, v: I- W7 f# S  q9 ?7 x7 d                while (end >= 0)
7 N4 A6 j( T: N# f# G                {
                        //不是插入位置：当前数据往后挪
                        if (tmp < arr[end])
                        {
! X! A5 d3 D7 U1 V! l/ M                                arr[end + 1] = arr[end];
                                end--;
                        }
                        //是插入位置：跳出循环插入
! J! a. F1 y* H/ @4 x/ v                        else
: h- y, y" o# X( E3 Q; \. b                        {
5 B% S1 @  h3 \) C% {: r% j                                break;
  A- X  g% X* S6 ]) L% j/ X; N                        }
                }
; A/ P4 X1 S- @2 K                //插入
9 _8 ^# j8 o+ L, }                //1. 插入位置是[0]，end == -1，不合循环条件跳出
                //2. 找到插入位置，break跳出
. `( N& h4 S6 D  }" _$ h+ p4 E                arr[end + 1] = tmp;
        }
}

) c! x9 \# f0 z" k# j1
* \  P9 }& H: C- L3 N3 L8 l2
3
% q- p% `5 e: ?4
' z/ C0 p9 z3 u2 C5
3 m0 e8 W  D* Y, e; }$ H6
7
8
9
10
; y  C5 V5 d; p: W4 F+ B11
12
! U) D+ W0 F9 K9 Q13
14
15
2 O  \3 f$ |, B+ |/ |% W4 U16
) |/ `: ^) G, [/ ?' G$ T" h/ ]+ a17
18
19
20
5 W' {0 ]' f* s# g+ y1 K$ S# I21
2 |+ E5 z7 M$ ^* w& i( ^1 ]0 O22
; d* g3 i) {" k! h. ~23
- d0 f2 v% t: y: P24
; u" V8 s1 i, V! H4 l. J; p25
26
4 {. I& |' }! l5 c27
28
. ]) W' e8 v" }29
30
* A% X$ S! y& ^& u* c31
) n# t- k& f) L

: O; m( f) v7 Q; Z/ V" W稳定性
: V; b2 F4 Z7 p4 G' U  [插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以

4 n7 z% b: h. E( y5 n( H7 p直接插入排序是稳定的
/ T1 g( e, {, \! P
复杂度
7 o' T' ]& g, b+ d3 e时间复杂度
, a2 ]" `: w* J( v9 }0 L/ Z: q* @最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）

O(n)

$ x  [/ W7 L$ s, q! s6 U最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2
0 Z+ D3 [% b, e, r
O(n^2)

/ c; @' f7 O8 t" n0 e空间复杂度
O(1)
) Q& f( `, b9 S: W
4 P  v5 F7 {$ h2 o! }7 P希尔排序（缩小增量排序）
希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序

2 L& G! v, k$ w优化思想
增量gap不止用来分组，也意味着数据移动的步长，所以
% S9 c: b: ~. o1 n4 v7 C6 S
) y7 Y) G. [3 r* [! U6 Dgap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高
4 w. W  {" @# z9 q# H- n
/ A' J0 J, r+ f$ w  ?# ^
操作
单趟排序：

1 p" F+ ]) t+ m6 x- {7 l6 q设定一个不断减小的增量gap，也是元素移动的步长
以gap对序列分组，并对每组分好的序列进行直接插入排序
不断缩小gap，并排序
*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
整体趟数：

2 P2 B  J- s6 m9 a  p由gap决定：当gap = 1，排序完成
3 j- \7 s# \( G5 [8 `7 ?! v注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。

void ShellSort(int* arr, int sz)
{
3 [; P1 R# w8 B' X9 R& O        int gap = sz;
       
. ~2 a2 \' H* T& F/ ^- x    //gap > 1，预处理排序
3 p. e8 A' d& _7 n    //gap == 1，直接插入排序
; C) Z" O  E: u: t6 G8 Q8 m        while (gap > 1)
        {
                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
                //gap组
, n' r( B$ x/ v( S' @                for (int j = 0; j < gap; j++)
* J8 [( `9 c( |6 p1 R                {
+ w* ]6 J, {9 n" ?            //end + gap < sz
                        //end < sz - gap
" G( D2 _, b' _1 R0 W; B! U: K5 e                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
                        {
* d) V3 g) p" v, o* B                                int end = i;
4 h0 I$ @6 T: ^% |                                int tmp = arr[end + gap];
6 {5 O3 I' p# Q. @9 N& M                                while (end >= 0)
                                {
                                        if (tmp < arr[end])
                                        {
                                                arr[end + gap] = arr[end];
' M- ~- m( P9 Y0 c9 ~$ u& X# J                                                end -= gap;
                                        }
                                        else
                                        {
                                                break;
! T! s' `4 _6 h* e9 e$ I& H                                        }
                                }
                                arr[end + gap] = tmp;
5 \/ W9 S6 D9 b                        }
                }
( f% x5 V( O4 x% j& x        }
0 t; u- A# ~! W( U# A; o& |! ^}

1
2
3
  x. n0 b) E" `5 g( \4 g' U8 j4
5
6
7
2 Z, a% C3 A% W) E0 f6 ~8
9
1 G4 k6 k% U* ?+ S2 }* ?10
; t+ Y& E% c/ F5 W- f- u6 H' X11
2 o, I. w- j7 }2 z! y5 F, [& l* L12
/ D6 N4 M$ g2 W) M, R& V) }13
* ^% X# N8 V: x- r14
$ }3 @1 z2 }4 Y7 t15
16
17
# F# J) e% O+ j) [% ?18
19
20
21
22
: @3 b' A+ S$ x9 n23
. x9 N  ?$ B$ j! }24
% d, D9 G6 H* j25
26
: ]( P- u% S; F: F27
' Z% f+ @& t  V" X28
29
) {/ ~- T0 \0 d; N30
31
# `$ I" Q) P$ z' U32
3 u) y" p9 Q2 ^$ `9 q* V% W2 n33
1 m7 c7 F3 U5 D1 ?2 W1 H' `34
35
, z. j' ?: w2 c, W7 z' a% [$ h其实就是套上”缩小增量“的直接插入排序


稳定性
# |$ [, S% Q( X$ a  I. n% `我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以

2 ]$ ^( q  [1 g% j4 ^* E. j6 L希尔排序是不稳定的
1 y* E; k+ S# _( G
复杂度
$ J6 {% k( W/ ~" ]+ a. }) z时间复杂度
/ v( k6 J# q- g" m6 b! S9 v; h& e1 z希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
; O! f: V. I  ]5 q& |
2 R* l- _! w: d, c; v; dO(n^1.3)

" h. ~# u, I- C4 I$ g0 w* ?# q空间复杂度
O(1)
# l' v- E' Z$ Z" U; o
选择排序
直接选择排序
& \( V3 J( y# S思想
6 P/ b6 f' \6 g3 t# z选择排序，遍历序列，选出最小的元素，交换到左边


0 _3 g. o' Y! ?. w# |! u: e8 q" a
优化版本：

每次选出最小元素交换到左边，选出最大元素交换到右边

操作
  `  T; o) @5 w2 W设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]

设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标

单趟排序：
! R& C" q6 n# l4 m  u) S2 K6 I1 f
. x: l. t; _/ D  F遍历选最值的下标
# Y+ s! Y+ J5 p4 D9 I交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
0 |0 d; K9 ~5 W) p（修正）
整体趟数

0 B8 B  e; d' c6 x# S; H' o若元素个数为n，趟数为 (2/n)
修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标

void SelectSort(int* arr, int sz)
{
        //闭区间: [begin, end]
. k  L7 i- c: R; D* e        int begin = 0;
" H# j" a% [$ B; {$ \$ v        int end = sz - 1;
: P7 A6 W) K2 n6 e% ]        while (begin < end)//begin == end 最后一个数，天然有序
' w, R6 K6 P2 `; x( w) a4 N1 h1 n1 k        {
; @& f) {$ N1 Q6 F. Z                int mini = begin, maxi = begin;
                int i = 0;
                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
# [! @- A. W; U3 C& A                {
                        if (arr > arr[maxi])
* C+ L1 \+ {/ W, J9 ~                                maxi = i;
3 W" e1 ]  ~/ W& r  y7 b                        if (arr < arr[mini])
4 ^' W1 P9 d+ t) |, M7 H/ O- D; I                                mini = i;
9 l2 }: m( o: Y( _                }
1 ~' o8 T% @1 d, k9 ?
$ ^8 ]8 s8 O7 ]. O2 [+ k. p                Swap(&arr[mini], &arr[begin]);
% J0 L: E3 H! S! H
                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
4 z7 Y2 ^4 y7 G8 }; H                if (maxi == begin)
' c- E& x# y9 Y- o8 Y& h6 d                        maxi = mini;
& q% K7 ?% z2 B- @. j8 [7 P+ M7 y                Swap(&arr[maxi], &arr[end]);
9 }1 B% m5 d9 ?9 Z% v4 a
                begin++;
! L8 \  n' r5 l; h' Q5 w, p3 n- F                end--;
2 _* S; S9 ?7 S$ e$ v8 n3 H        }
}

; t7 L; L% a0 h( O5 F1
2
3
4
5
6
7
+ f' D9 z% }# ^0 U  X3 i8
5 a4 C# w2 v5 m% g% u# ?4 `* P9
10
11
12
% m1 c  H. g  E3 X0 `/ f! W13
6 D" x9 z2 n3 z14
15
16
17
! C2 J% X. H* }' [18
19
20
7 E' X& `! O- O4 K. y7 x21
. B, Z! }+ Q/ m1 C' T22
0 G; S7 a) i8 o, B" K' h23
24
25
26
27
1 b$ e& z# j) P4 F/ r1 X28

" q! ~/ b5 X5 D& R' i; e. V" ~
( ]6 T+ H% m8 M7 m0 d' b稳定性
: |9 m: S4 M4 ~2 P选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以

选择排序是不稳定的
8 l' F+ M0 t' H5 T
5 l8 ]. ^- f* O9 }6 X: F, C复杂度
/ ?; k/ ]1 ~* V+ t: r: A$ T时间复杂度
最好：
/ `4 @: j. u' e0 }
比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2
/ u4 K7 S# Q. ~1 }( T% T; ]
$ R7 W! T" P2 i/ K- j0 s交换次数：O(1)，有序不用交换

  [. q( ]" Q( pO(n^2)

最坏：
& g1 @1 s2 B) Q6 ~
比较次数：O(n^2)
9 z0 b. V* t1 ?; G+ z4 p% }
交换次数：O(n)

O(n^2)

7 m+ s' z$ D  D2 k空间复杂度
O(1)
( J  Z. ?( f1 C  z; x+ k
6 r5 i. s$ J- n堆排序
思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆
1 z! }  x  O, q6 g9 M& g- |
; A* y* W2 \: S+ t6 ?3 `/ M
9 P8 n2 Y$ s* A' U, i0 \3 y- P) N
, R3 A& d9 {6 x7 L* ?操作
建大堆
; n) S" s* M' y- R% @9 [+ R* h单趟排序：
选堆顶和堆尾的元素交换，则堆尾的元素排好
1 J7 R% n* L0 R7 Z% F每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
" u; b3 r$ b9 d1 D6 ~& }5 K整体趟数：
  `1 b' m$ c" }& j0 P1 o若元素个数为n，则排n趟
+ c- y2 D( @7 \6 o) yvoid Swap(int* e1, int* e2)
- A& M! u0 u% k" `7 y6 K' S/ q/ a{
        assert(e1 && e2);
! f( y$ `/ }; Q& x1 [! Y: {
        int tmp = *e1;
        *e1 = *e2;
) _0 h$ S% S( a        *e2 = tmp;
}

void AdjustDown(int* arr, int sz, int parent)
0 g% j% o6 _. X& b4 H' \6 {{
        //建大堆，排升序
        assert(arr);
7 u# }% ?  C4 s# ?. U7 n       
    //默认大孩子是左孩子
5 W; E' W0 R" p6 \) S% M# C        int theChild = parent * 2 + 1;
        while (theChild < sz)
        {
        //如果大孩子是右孩子则修正
# p& e& ], Z' p                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
2 _& Q' B2 p5 S4 @3 L5 t. @                {
( O$ a0 y* M) \& `3 j                        theChild++;
* Y; K5 J; h1 g9 Y% b2 T) r                }
" B- V# v& P8 |2 R( b1 j/ r' D5 }: _                if (arr[theChild] > arr[parent])
                {
                        Swap(&arr[parent], &arr[theChild]);
5 v9 r2 C" W$ c            //迭代往下走
  p! @% u# ?- q/ a) b/ G                        parent = theChild;
& H# v9 }5 `  L3 C                        theChild = parent * 2 + 1;
# f% P* b( j7 h8 q; j                }
                else
                {
                        break;
                }
        }
}
0 _& u3 S1 u9 E8 J) T. O
void HeapSort(int* arr, int sz)
0 K4 x1 H- @, n6 t& c{
. n- e' M( u' U. Y+ F$ x        //1.建大堆
        int i = 0;
        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
        {
, }6 {3 ?0 r0 b" y) q. `7 L                AdjustDown(arr, sz, i);
        }
5 F/ t9 c1 D0 i8 `$ l1 b: A
1 b$ ?- a0 W9 M) U        //2. 选数
: F5 X8 t0 `3 R; v: C* J2 E" |        i = 1;
" m  @" v* M+ q5 h- }# A  o" z% J        while (i < sz)
        {
; J- r. t- u) t' F$ c$ J* _                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
& ?$ f6 ~2 B& H: I% h' X( }                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
& S% S" D8 U4 E& U9 J* K! O# n                i++;
        }
, z/ Y1 {9 d) Y4 U}

; \3 s: N( f( Z" B$ b( Z+ p1
9 U5 J3 R1 o1 H+ U8 G$ E/ G0 R# G2
3
; P! _+ Z) J  L$ U9 D- y+ q3 ~! l$ w  d4
5
6
: Q7 f$ d  D$ o+ `( k4 [) `7
8
& G( H# p8 C( M. U4 K+ B9
10
  E1 G+ f/ ?- M; V# r- x( T11
; g0 n9 u0 G& Q" t- v12
- R! C7 ^8 k+ ]1 L13
14
15
8 n7 ]3 A3 m: @, |7 ~16
17
18
- X4 P4 L% j6 p19
20
9 I" z2 Q+ ?- Q. y( Y21
$ ]  _& @! Q' D/ I7 `$ u22
% ]: A0 L* I8 K& R  P! N23
24
5 u6 m$ b$ u4 F. B25
26
27
& c* D! }9 v1 l, n0 C" U4 Y28
. `' E, S( ^  Q# M9 n' W29
30
31
' K6 Z0 A  u7 i, l* S6 C32
33
34
35
36
37
38
39
40
41
42
% H- s! \! P8 A; v* J4 K1 E43
44
45
46
  c* R: G2 z0 J9 Q6 X. `4 A5 h! O) d47
4 e: a. t' l+ |9 t48
/ v3 @3 r. m. G; y" X' B49
50
+ J5 d' {, @. \3 t( Z, Q- g9 u  f! P51
52
53
" T1 E2 i# c! S$ k1 s) r! F54
4 @( J4 W' L- @5 X& @3 B55
! Z4 b& Y% m( ~$ X. I
3 x, b, A, t2 i  g# ~# }, T
稳定性
4 t, B- L+ b; r- i建堆和向下调整都会打乱元素顺序，所以
" ]& c( U* ^9 ^0 S1 J
堆排序是不稳定的
* }, k5 h) N3 Y3 c
复杂度
( ]& A0 N# j$ J- @7 x时间复杂度
$ [2 q; S$ T3 o5 m; Y- n0 Q% U单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为
7 t% `( N0 @, V/ k5 O
O(n*logn)

空间复杂度
原地建堆
! v$ H# D& T; N8 P2 Q7 F* p
3 j$ j0 p4 m/ a3 d3 i, y8 RO(1)
9 k; ]( \: E) N2 D0 x0 F2 T' |
) |/ J/ d9 b1 ]: u0 b! [; h2 C交换排序
冒泡排序
8 h. J$ ]& `) ]/ H5 s# S) V思想
' _5 l. R( C2 [3 y" W冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素



% Q, Z: u, Z. |9 r$ ?操作
# \# W: v( u- X/ C# }- [$ A3 y单趟排序：
$ I/ ^$ R/ L$ E  x: K每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
每趟排好一个元素，所以需要排序的元素每次减少一个
# M9 Z4 N0 P/ q) r' d$ C整体趟数
; d  z# x6 M! D若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
' i4 s! }# S- D/ H" L' b' avoid BubbleSort(int* arr, int sz)
{
" c/ x1 S4 z6 ~7 F# V* j        int i = 0;
/ a6 s4 K: K! v8 u! R        int j = 0;
        for (j = 0; j < sz - 1; j++)
        {
                for (i = 0; i < sz - j - 1; i++)
" I7 }- b, v0 l; a6 ?; M$ \$ }                {
                        if (arr > arr[i + 1])
                        {
: e, o' A7 k/ T$ K) c                                Swap(&arr, &arr[i + 1]);
& V, T" b( Y$ T2 g) P' w  c                                flag = 0;
                        }
                }
( X1 q1 ]) _" X# ]; C( j        }
$ A+ m+ v* Q* A8 W}
% a' \1 [  ]! L* F: t
1
2
3
8 K$ H+ ~4 h( j( t/ d! N( Q4
5
6
, W5 l8 _6 ^$ U7 B+ R7
8
) N- p' l6 w' T$ f. T9
10
11
12
) M0 U% D, S# `7 c/ A4 f8 U13
14
% n4 V, P: ]  [% u( g# f5 Y15
16
9 m/ l* y$ V# ~优化
+ s6 n( n$ l  T5 p当遍历一遍发现序列有序，直接跳出
  m+ o- Q# i1 a6 p0 J
/ C! z5 G) D) T% G2 U4 A/ f/ V2 {8 lvoid BubbleSort(int* arr, int sz)
{
        int i = 0;
        int j = 0;
        for (j = 0; j < sz - 1; j++)
. ~/ X( o" N; r6 `8 X% P        {
0 u7 x; @0 a0 Z! k! N% p                int flag = 1;
7 b+ y, B; p, M1 {0 r6 T                for (i = 0; i < sz - j - 1; i++)
                {
                        if (arr > arr[i + 1])
                        {
6 |" o. g3 o: m9 d" D5 X                                Swap(&arr, &arr[i + 1]);
                                flag = 0;//不是有序就置0
                        }
                }
                if (flag)//如果一趟下来还是1代表有序
                        break;
        }
* ]3 X6 i. V9 x0 e}

7 w2 M9 {* [. ~3 k1
2
3
4
5 z& v" k# i  L9 a, p5
( f* E& g3 R4 O9 H  S+ J4 _6 b! Q2 ]6
7
$ P+ m5 G+ e6 \4 L0 R. u, D8
9
10
3 R) x9 N. E3 Y6 A% S11
12
( C% y5 |2 R+ U) ?: ]13
14
15
/ t% Z$ ^0 J/ u+ k: G2 H* c; {$ u16
, o& Q, n0 a7 l# `17
18
19
# s8 ?7 o8 O% [* O6 U
* v- A  i, i, n  ]5 C9 W
稳定性
相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以
2 B& o; m9 y1 X
! `, Y+ ^2 |. v" Q4 e; d冒泡排序是稳定的

复杂度
# H& }* @' W( T2 _( R6 o6 X5 t时间复杂度
最好： 当序列有序
2 F4 ?% c7 B) D0 \5 _
2 K# O* s, D& p, ~$ r未优化：

O(n)

优化：
2 s2 G  M, n/ d0 I1 R  F5 |* ]
3 f4 W5 v+ L% W/ L) _8 ?* LO(1)

最坏：要进行 n-1 趟排序，每趟交换 n-i 次
1 i5 c- v9 }9 k& }. L+ H
6 L" A8 [4 w+ p6 v3 m! vO(n^2)

空间复杂度
3 o8 W: w  R" f$ \O(1)

快速排序
思想
; e! u( f- Y/ p1 e4 B分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。

所以快速排序可以用递归来实现

操作
有三种单趟排序的方法：

Hoare法
% r2 s. y* G: Z: n0 e' p( }' ]设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间

- k$ {) [! r( J$ \" g左下标 L = begin，右下标 R = end

设 L R 相遇位置为 meeti

  O7 R9 n1 Z) `  D) ?& ?/ j: q​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”
  S* J0 v# A' ]+ o# }4 L* b
; g( ^1 ^3 W6 C+ t7 y​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“

选 键值的下标 keyi
4 w) d$ V) k( j  Z
左1位置作 keyi，则 R 先走
右1位置作 keyi，则 L 先走
R找小，

# j5 O. m5 ]6 b% k: G0 Z0 W找到则停
7 P' u9 [* \. m- k/ O/ r: [! R- D遇到L，则交换 arr[keyi] 和 arr[meeti]
L找大

找到则交换 arr[L] 和 arr[R]
遇到R，则交换 arr[keyi] 和 arr[meeti]
6 J1 {% A' x* }  [2 J, h; F
4 X6 z9 d, p/ c- G- c
解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
& j% q8 k% F- |$ U. `答案是肯定的：
- ~$ Q& v' e6 R/ {# E
9 c, E$ [: v, |


//[left, right]
int PartSort(int* arr, int left, int right)
0 N8 n* z9 r) w' C# u; O' f{
% G% F  K8 b& Y+ H, J/ h        int keyi = left;
' ~9 ?6 \2 I7 i. ^        //相遇则排好一趟
& r# E- ~' Q2 S7 c. p        while (left < right)
        {
" C. b  A( m5 I" q! q* f                //R找小
! N# Q$ F! o! ~# n! }9 S8 J1 ]. ~6 t        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
* [; a9 L; N: p& D2 l' z9 [, T        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
                while (left < right && arr[right] >= arr[keyi])
5 ~4 f/ p$ N% v7 F! `) i                {
- s8 R2 M3 K' h6 G- Z4 k                        right--;
                }
1 T* X: ^/ B' |8 d  I4 C" H/ x  G
- R9 H  d7 U& g/ F  u2 ]                //L找大
4 n+ \7 Q5 Z8 w" h7 @; z                while (left < right && arr[left] <= arr[keyi])
                {
                        left++;
                }
               
% C; A! i1 e) e* S6 y        //相遇就不交换了
                if (left < right)
3 x# ~# c) F$ }5 \                        Swap(&arr[left], &arr[right]);
8 n' b0 U) u6 H        }

3 E/ g, q# z, D* ^  e5 F        int meeti = left;
4 i3 N' o7 a" Y% V
; d9 ^) T2 X- U% ?: ^0 D, p) @        Swap(&arr[keyi], &arr[meeti]);

        return meeti;
}
# c/ O+ i8 M* g' t2 q2 j& s' C
+ b" P; C- Y3 q7 P0 L: T/ }1
2
3
4
5
0 ?. x$ M9 j7 c% m  f- B/ b) u5 ]6
7
1 r; x6 R4 v/ I" Q5 q; u# U5 L/ M8
9
10
! o& d" @$ Y5 A11
, K, R. X+ D1 j* q! ^& I" z/ X' E; @12
9 f5 ?2 Y' o( F7 b5 I. Y13
14
" P0 R- ^- G: J, C3 J5 x15
16
17
+ S$ f5 Y2 w* r: ~18
1 E; p' Y3 k/ ]7 `, X! Z9 n19
20
21
22
: G" b2 w6 N6 s+ A' B23
24
25
' b8 u2 B% L8 N3 ^0 ?- p& w( {( L; c26
% m) E: r* f3 {. u  q& E8 [* M: f27
28
; N* A8 f* W* P- n" x' q- O4 d29
$ m8 N4 I+ @2 b, d) B! b( c3 o9 G30
/ F5 {& M5 E3 M1 u$ u+ L2 A/ ^$ C31
32

2 h, P6 u9 L9 I0 J% S. a$ u- H
解惑：为什么key要选左1/右1，选中间不行吗？

: s# |6 n: k; w( Q9 ]7 v2 ^
2 ^# h. P$ w9 ~0 y5 J8 a可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深

& O: g# ]" ^- [


/ V+ \" m. l1 w2 O! ]非常容易栈溢出，怎么解决？针对有序情况，优化选key
8 j# a3 t6 c$ F/ q9 Y" |  r# u3 e/ J
, c7 ^, c) n/ n! B# N4 a, _% ?优化选key
5 C2 }# L- D2 [1 ^% k* U; V* J随机选 key （是一种办法，但是不那么彻底）
选中间位置作 key
5 x. U; \5 M; u) `1 n1 w) d解惑：那先前实现的单趟排序不就失效了吗！
9 d' Z4 a6 }7 O4 V' ~1 V7 K：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑
7 N7 T6 u. w& g' ^! S2 d; r* i
解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
+ c# u$ l9 u/ f; h; k: \2 Q) r0 I) x前辈给出三数取中的方法
/ L8 V. s3 H& i0 j
三数取中
在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
& t; r; k+ t6 _& G% W这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
9 L+ n: \2 ?1 d1 o' E6 Y0 X6 m优化选key后的Hoare单趟排序：

int GetMidIndex(int* arr, int left, int right)
{
: e. `9 |) s4 Y& f        int mid = left + (right - left) / 2;
//  int mid = rand()%(right - left) + left;//增加了一定随机性
7 L9 m/ h2 L- V, M5 k! D) `        if (arr[left] < arr[mid])
. Y* A; Q+ j, I+ I        {
7 z. |; G- P4 w4 V2 k, m                if (arr[right] < arr[left])
. q& C9 \0 ^* |% X                        mid = left;
) S& K( Y* @/ H1 _                else if (arr[right] > arr[mid])
' m! L- b. J' y" [1 l$ s                        mid = mid;
                else
                        mid = right;
4 f; o# I$ J/ z4 ^/ w        }
        else//arr[left] > arr[mid]
        {
                if (arr[right] > arr[left])
                        mid = left;
                else if (arr[mid] > arr[right])
                        mid = mid;
, f6 K  K- o% r/ G, S: y1 G                else
                        mid = right;
4 ]; a, K; F) H) [        }
        return mid;
}

int PartSort_Hoare(int* arr, int left, int right)
/ D) R# k% Z8 U  C' h{
        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
        int mid = GetMidIndex(arr, left, right);

        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
& S& z# T# C" W+ @8 l        Swap(&arr[mid], &arr[left]);

        int keyi = left;
- n, H% T0 j3 e( L1 ]5 a: h/ }        while (left < right)
) S& K- P' R- ~$ Z! ~6 h0 x3 P        {
# Y  n8 E1 r" g! A: [- |! I. |" B                //R找小
# h" V( `% |( t0 Z& s8 K                while (left < right && arr[right] >= arr[keyi])
% Q1 Q) n# g1 ^; E" k                        right--;

0 Q: P5 b+ P2 T                //L找大
                while (left < right&& arr[left] <= arr[keyi])
                        left++;
7 t7 [( T. X  v
2 ?1 \' H4 m) e( w2 l6 S) C6 t                if (left < right)
                        Swap(&arr[left], &arr[right]);
9 T, U* ~% p5 L: Y# `        }
2 x5 m' V6 M! Y
' g+ J2 ^: H" C$ }' S) l        int meeti = left;

* T- s7 H% s5 w; r        Swap(&arr[keyi], &arr[meeti]);

5 _; e# x4 E* F        return meeti;
% d4 F3 V: L5 _}
% e$ D+ n  ?" i7 `1 Z1 X+ A  M# R
1
2
% T; @, _0 d( s: Z! O& i3
; w6 e6 x; M* I3 W/ T: C4
: {8 h) T! `9 ~8 a! T5
  @' X4 m- A$ X8 x( U: R- }* r6
$ m; s1 ]' n6 x" P, I7
5 G+ Q- Z; J; d7 d( X0 \# \: A8
# ]5 A* ~% o! {6 y/ P9
10
: Q8 T: n- u" a  R; `3 D11
  o; V$ n3 v6 E1 u' ^! h12
5 H2 }$ k9 h1 L0 _" `13
+ {3 R* L4 ~2 @: M2 e14
15
16
17
7 D/ q& r7 l5 n1 H. r$ ?18
' a% ?# O( q0 l5 H% [, J& V4 o6 b19
7 D; \  J/ H2 e  D0 x2 E7 E; l20
: b- O: R0 [. b7 f/ @3 x& i21
22
23
! a2 B1 u5 b# z( y3 a$ i24
; H! Q3 t, Q" {5 y5 d25
8 w( w5 e/ N( ^! u+ O26
27
28
+ D3 k4 i9 R: c+ y# i29
30
/ N* i& h8 I" s5 k* M6 W) O31
: X& L- q! W1 P" e, H32
  ]+ w+ I. A! @$ W; S33
' l4 e8 J: F' _! R34
35
# P# S. r$ z$ ]4 |+ v" i( m36
: ^* w5 n3 s9 L4 M  q; Y" o37
38
( ?8 `/ \, ^; ]) S39
40
41
2 Y$ Y# S- n4 c) T42
4 t4 M4 D: J3 j8 M43
44
! @4 q  B+ j* ]  I3 E45
46
47
48
: Z9 c1 h+ |  S8 p. I2 t- ~49
50
: K5 O# c: _1 t" X- j% ^8 e51
52
$ w" c5 i& \# z$ X53
8 Y8 _  [$ m# y6 W! r- w; o54
挖坑法
) V2 e. B5 @4 t  R初始状态：L作坑，其下标存为key
9 B0 x, f0 y+ r# b: L# |(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
重复 (1) (2)
最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]
7 V# I" R" b0 |& N% f

int PartSort_Hole(int* arr, int left, int right)
{
/ w7 l' ~0 t# O, e2 ^) c% x        int mid = GetMidIndex(arr, left, right);
' O) k) K! M; J; j7 Y" n' ~$ r: N& _' n        Swap(&arr[mid], &arr[left]);

6 d4 ^5 _; q3 O' z$ }7 i8 C8 m        int key = arr[left];
% T: w2 y6 ^8 x. u! K4 B  Y        //L作坑
        int hole = left;
        while (left < right)
        {
                //R找小，扔进坑，R作坑
                while (left < right && arr[right] >= key)
                        right--;
                arr[hole] = arr[right];
, ~5 ?7 K+ [; J% d" A7 Y8 f6 o                hole = right;
: d; S4 b, [; v( I% e( j
& D7 ], n8 z7 e1 k0 J; g! a                //L找大，扔进坑，L作坑
& h, n) ?0 y5 \! Z8 \                while (left < right && arr[left] <= key)
                        left++;
! p5 _2 |% M, m% N- a& t$ v                arr[hole] = arr[left];
  ~; V! ?, p# r                hole = left;
2 [# S- A+ Q' o( ]1 {2 P1 v9 E        }
& X- V, j$ v9 d& p- `- D5 g        //meet
/ D5 m% K& v6 x4 A5 z, t        int meeti = hole;
; e* J% Z% |( g( q  y4 |8 Q1 I        arr[meeti] = key;
( |9 v6 [: t; z8 E
        return meeti;
4 v% D' }  _  g& D$ g6 d3 Y}
5 ^. j' l9 R- J- B4 Y
3 m4 J3 P- R. o: }6 s1
2
+ J% l0 D) r9 [+ h! h! M3
4
5
6
1 U8 [  ]# d  L/ M/ J+ N7
8
0 B# V& @# k1 W4 _! A- _5 B9
6 H1 x& X& O' K7 }& q10
11
12
13
14
7 U+ }! U! R2 b15
16
% V/ a* T. W! n" T17
( k; Z2 Z% f3 O. i/ g2 C, t' K18
8 Y2 f) B# ?" P5 `% Z4 W19
% A' h8 d3 n; B* W* I20
21
  {5 C& P  y$ z. ^1 M1 N22
23
24
25
26
3 @! ^3 ^8 ~4 S1 p! p+ N9 R8 W! _27
28
前后指针法
此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多

cur找小，找到则停
++prev
如果 prev != cur，交换 arr[prev] 和 arr[cur]
如果 prev == cur，不交换
6 {, S* k+ r4 p! B4 Q1 L, _5 r当cur越界，代表找完，排好序了
# h8 j" p* p* s. W( \* G( h* wprev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低
: t, T# d9 s# T5 ^6 r5 W
+ q+ O1 l1 i) u8 s2 c
+ V# V8 X, O! C! t4 w7 z* }
" z: d! c& I) O0 Pint PartSort3(int* arr, int left, int right)
{
        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
  [2 X: V; ~, R; o       
  //int key = arr[left];
; \; |& e. Z+ b% L5 S        int keyi = left;

        int prev = left;
        int cur = prev + 1;
: C) l8 W4 s' m) ^3 F       
    //cur越界：找完小的，prev的左边全小，prev右边全大
) J+ R* `# e9 c        while (cur <= right)
& N6 C) D, ?5 @9 O  D/ J        {
        //++prev == cur 没必要交换
7 H/ s, Q9 t/ [4 O                if (arr[cur] < arr[keyi] && ++prev != cur)               
                        Swap(&arr[prev], &arr[cur]);
( }5 r8 a6 J4 G4 W. E
                cur++;
$ @5 k$ n! q( j7 S- G' S        }
" {" R- l5 x6 X$ k& {# \+ |
3 _5 D. R* `/ L. J, A9 A, W1 s& u, P        //键值存是的值：
4 {1 c, X$ ], M2 v1 V# e0 |3 V        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
. X& c, Q8 V/ w3 U  s# o& F/ F  H        //Swap(&arr[prev], &arr[left]);//这才对
/ q0 a- M) Y, H    //键值存的是下标：
$ I0 q4 z3 ~) E$ d1 o  i3 l$ P, c+ p5 }        Swap(&arr[prev], &arr[keyi]);

        return prev;
}
, N9 {0 J. N" }& u5 w; f
" [; A3 Z# D' R& H9 ]% I/ R. v* T1
& A& p  O% y& Z  D6 n  G2
5 P. Q5 z6 a/ e) J* d3
4
. O% U! t1 I% m$ C- V3 A5
: L; }+ h% b9 k3 e9 H- f6 D6
7
. J5 P/ b8 {) O, r3 z8
3 u$ Q4 I& d1 ~' s* u6 X+ n9
4 ^" }1 r6 Q7 T( d: w* |" Q10
11
12
, x1 n3 _/ U/ P3 j. j: V: X13
14
15
16
) u. u- x( }) M5 k* T4 [# u# C17
18
+ b3 D7 B; V' [9 T0 [& d19
7 u; K3 \6 E: a) B0 g) y20
21
( Y* K) u( \. T; ]! e3 V& h22
23
* A6 N2 J# T- I% L7 O& K$ @24
  q$ J* G  B7 y# B* Y$ i25
- d/ @9 w1 h, U5 u# J26
27
1 o" n" c+ u# k; E28
29
整体排序
  D1 ?$ G0 C, c7 i8 m递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

//[begin, end]
* f) y# w8 k  P" L% f9 [3 Fvoid QuickSort(int* arr, int begin, int end)
{
        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
2 V3 E9 i/ R: i. ]        // [begin, meeti-1] - meeti - [meeti+1, end]
                //1.begin > end:超出范围
0 n/ t# _/ g" V7 o4 B                //2.begin == end:一个数天然有序
8 z, Z7 b8 g9 @/ t    if(begin >= end)
        return;
+ [! G6 q5 g- V0 S
                //排好meeti
                int meeti = PartSort3(arr, begin, end);

) D$ D! @) w6 J+ E  y                //排好左右子区间
. V5 p, v/ a1 Y) y: a4 a) \2 w                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
. B: d( `3 k: l- e) [; f7 g7 G        }
% D0 x4 H+ z8 b}

; t* P# g  I% T+ l1 t5 ~1
: Q! Q% L+ ^6 T: `5 m0 |$ i2
3
; a, Z# |$ C1 q4 F! D# F; V4
4 a. I; k# d  X, c. t& s5
3 _3 \2 z6 Q  J! l5 A: S8 K0 _6
7 g1 l8 t% s1 A7
1 W! E1 f: m" D8
9
10
+ N5 E3 N+ P% ]7 b5 |0 U2 y11
12
13
1 u; j7 S+ B; ~+ e5 ^( z7 _5 V14
3 t8 O0 ]5 g7 Z$ F- Y! t$ ~. b15
* j6 \8 Q* Z7 S9 C5 @16
17
2 h: r+ f" F. r. o% ~* X18
% `( }/ H9 Q' q( _" {( O…

没想到吧，还还还还有可以优化的地方！
* h2 b* Q+ Z/ u, G
优化小区间

- ?8 _" D: P( P
如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序

那什么算是小区间？
6 c3 d9 y- n( }& J" R  h3 R
% u3 Q6 s1 A3 q其实小区间没有确切标准，8-15左右都可以的


这里就把小区间定义为 含有 8个数或以内 的区间

) V) ], A% q3 Z6 l//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
) u; r! J+ P/ q. p        if (begin >= end)
% X7 Z3 G) q8 ~  M9 S                return;

        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
        {
                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
  k0 a& d8 }9 R8 K" a. z5 K        }
        else
        {
# G! B: k+ P; I; v+ x" H) y                int meeti = PartSort3(arr, begin, end);

                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
: D0 E2 L* F  s/ D. a        }
}
4 ]6 ]$ i/ t0 }' T, o; G) M$ M
1
2
3
" \) M; v9 @9 n. E6 a0 e" o4
9 C4 A% s3 o+ B5
6
* U3 c: S( W0 {7
8
  P6 C$ h3 B3 r3 ]6 K8 `- C" v9
6 _. E/ u2 h/ w10
11
12
- s. H5 q  v" Z+ g! @! \13
14
15
. z" D" k% a( G/ e# k( K" t, V6 S% X2 I16
5 b" U# n! t( ~) J* S  W( P17
18
19
快速排序非递归
# {( ?( \. Z6 ]" {2 `0 f为了解决彻底递归深度深的痛点，我们来试着把它改成非递归
. x- o9 \. ~8 ~1 G3 _
5 l" }9 k% F; Z7 D0 a思路：
递归深度深，栈的空间又小，会栈溢出…
1 p2 b" [* O9 a0 W
那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！

核心思路：在堆上创建“栈帧”
0 c) A8 ?- o: d) C% a) u! u
  T7 g  ]  Z% Q" }快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的
+ W$ _" c9 W9 b7 Q8 G

7 V5 L7 k( _7 t
在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：
! A2 x! S% D7 s
0 V6 u5 K% u/ y/ B2 y- L先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
( N+ n0 x, C# w+ E) \先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
3 R" j5 Q8 i. z0 S: q  C{
        ST st;
: y* J+ U" K9 J  j" K; U        StackInit(&st);
8 C" [3 g; H) Z% t       
; H3 C4 R4 `) a/ c9 O    //先入begin
0 ~' v& b2 t: ^# U# u        StackPush(&st, begin);
% K" e* {+ m5 w# Q$ e    //后入end
        StackPush(&st, end);

        while (!StackEmpty(&st))
        {
" i0 P) K3 K5 t$ V+ N# `5 e# z                //先取end
                int right = StackTop(&st);
                StackPop(&st);
                //后取begin
                int left = StackTop(&st);
                StackPop(&st);
# [$ `2 B# S% ?
                if (left >= right)//1.只有一个值  2.区间非法
                        continue;  
                               
                int keyi = PartSort_Pointer(arr, left, right);
5 c9 g0 e. @- F, C
  l% @# v8 ~1 c                //先入右区间
                StackPush(&st, keyi + 1);
% E' R  T0 w0 Z# p4 E! \                StackPush(&st, right);
* p2 S; {( N" ^- f                //后入左区间
                StackPush(&st, left);

                StackPush(&st, keyi - 1);
  F: f7 ?+ ^- z' ?, z        }

        StackDestroy(&st);
}

1
2
3
" `- @! K8 w8 a. O6 F& u4
5
6
6 c( k$ K$ j; J1 _) H7
1 R. x- o) A% n% C# t8
9
10
8 r* i  b4 B* r11
12
! f$ v4 _" V& h* g2 H- d4 z13
14
4 b7 z' @$ ]" k9 ~15
16
17
. y2 ], ?& B  ]18
19
20
5 h2 }4 @: J* ]6 Q. n* X21
2 X/ I) _2 n+ q" ~! C22
/ J% P4 Z. i" Q! D  Z% |0 [23
24
25
: Y# ?7 Y9 l6 t1 d26
( J1 z5 j# y, C/ M3 [' _5 X) w( F0 c3 W27
28
% X% B' Y" x$ j/ M9 E6 Z2 N1 C29
30
9 G- I9 W6 Q6 d4 |$ K" t2 |$ m31
9 A8 R8 Z6 S% T6 E, @* Z7 [32
) X' T5 M3 S- F, R33
# Y2 O2 H( i# o6 C4 t# @34
35
数据结构栈的实现可以看博主之前发的博客


归并排序
9 k$ O2 d2 _2 n
…

* Z9 D' ]( `: K性能测试
void TestOP()
( @7 g4 `0 U, t0 i* u{
        srand(time(0));
        const int N = 100000;
) @8 t; v, V# z        int* a1 = (int*)malloc(sizeof(int) * N);
        assert(a1);
& ?% ~) X, i1 n; P$ j        int* a2 = (int*)malloc(sizeof(int) * N);
* O. n# e- {( r; ^! Y5 ~# a$ d        assert(a2);
# p1 V% P1 L0 z: L1 }! O, `+ l  @        int* a3 = (int*)malloc(sizeof(int) * N);
# U6 u( z4 w1 s4 \8 b        assert(a3);
4 W3 H( X0 Y5 y9 y        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
7 z* a% |$ s8 D/ [0 I, Y. h% @        int* a5 = (int*)malloc(sizeof(int) * N);
( ]+ d' y6 T9 I, y        assert(a5);
2 y2 P* w4 S+ |- C$ W7 H
; _" H. _% u) {2 E+ M        for (int i = 0; i < N; ++i)
/ ]: j5 E3 s) x7 e' {        {
: R( E2 V4 F! f3 _+ L, `( J& G                a1 = rand();
                a2 = a1;
* \% j  E4 f' U  P  z+ Y, \' o                a3 = a1;
. P- G, W) e1 z5 h2 d6 q! \                a4 = a1;
                a5 = a1;
/ Z, C+ ?4 g1 a! o, K2 {        }

, q1 X' h2 I* A  a$ N' ?        int begin1 = clock();
        InsertSort(a1, N);
        int end1 = clock();

0 F- b' O! t8 N. k1 N$ d6 e        int begin2 = clock();
* m+ J$ Q$ T$ h" D        ShellSort(a2, N);
8 u+ |6 F; j( x% ^3 Y% W  D        int end2 = clock();
# q6 \! g' U) g* X
  r& V( {2 [; D6 S5 l        int begin3 = clock();
9 k* w# E) q, k  f        SelectSort(a3, N);
. ~0 e3 ^$ z, K+ t. y        int end3 = clock();

( _* U1 E7 B3 T  U        int begin4 = clock();
        HeapSort(a4, N);
$ B1 Z8 p; ]$ M        int end4 = clock();
: ^7 T5 {3 i) A) {3 @* h5 I+ [, f
        int begin5 = clock();
+ q+ i4 y) I! p8 A        QuickSort(a5, 0, N - 1);
                //1.中间key
                //QuickSort(a2, 0, N - 1);
1 ^5 d& g2 c: _                //2.三数取中
' J: ]+ ~  @, \- ~4 K0 a' U: C/ x                //QuickSort(a2, 0, N - 1);
9 `. f. q. ^% R1 C6 n                //3.小区间优化
                //QuickSort(a2, 0, N - 1);
* l0 M& _0 \. N1 l        int end5 = clock();

  C3 o' y- m8 J# {+ Y1 `8 F- r9 S
6 P" I( r1 L- B1 {+ p        printf("InsertSort:%d\n", end1 - begin1);
        printf("ShellSort:%d\n", end2 - begin2);
        printf("SelectSort:%d\n", end3 - begin3);
        printf("HeapSort:%d\n", end4 - begin4);
/ U" b7 `5 ~9 \- s5 C        printf("QuickSort:%d\n", end5 - begin5);

        free(a1);
  b3 \7 x5 G, u# b+ E2 P        free(a2);
        free(a3);
, q- J1 x/ u) U8 y  r        free(a4);
* [9 [  ~2 l6 S7 y& O1 g9 o% V        free(a5);
! v% Z3 o1 T# U8 j. b/ K& o/ f. a}

4 V# ?) D6 R" @- M+ H8 Q1
2
# V, J# L* z, m! m8 c9 ]3
- O  V2 h5 a! \4
1 ?& P/ w3 n( t8 J6 q' {5
6
; D% Q( M; \, w6 X1 p  M& w7
8
9
% V: ?% t3 A8 {& r10
" H2 {* I- E& \: Z11
3 I) E" q( w  T# n3 N12
# h5 Z  C5 q" u6 h13
14
, c! N( Y  {1 Y) r7 v) J" f  T15
$ L2 p( a+ X6 ?  j" y% K2 \16
! L! y2 e" f& F# A# w17
9 u" i6 \3 v7 N4 g% ~" A3 L" S. @; M18
19
/ A5 K' G- G# h/ q3 i! M. ]' a20
21
22
, v0 l( j; X2 s3 T3 S; O! V9 Q23
24
  U0 `- d" n0 W& X25
26
% w2 ^( j; x( g' H1 r  D8 V27
28
' m  H: N' I8 K1 d29
) q  o$ S9 Q$ T. |4 g30
31
32
( {7 h; Q+ F( a1 p  _* Q' v' ?33
34
35
' y( U. w# F" E36
$ L8 ^+ z2 H/ A- N6 b5 X37
+ }2 Z* f) A# v% y38
8 l# V3 n3 g, g: ]: c39
' M: l$ ]  l5 O0 T/ N: q- V; L  {7 Y40
! \0 \! m& \+ V4 b( U7 h41
/ n8 ~& W% |1 [* k9 s42
( J# L5 y( m2 m% n; x43
4 S; y8 K' A7 l, ?0 `" A6 m) {44
8 W6 s5 o! t) L45
46
- e7 s! g+ C% \* z0 h$ y- d47
48
49
" }$ y& }: w/ w3 F9 E) @50
51
52
53
5 j" X( Z. X/ p# ?/ `7 ^% `& Y54
55
- J9 L. N- q$ s56
* K7 M' r, y4 K1 m  a! G7 L57
58
59
60
! g2 }; t7 O( i- X% U# e. K5 d; u61
62
! b) v: Y. O$ J# [7 |$ l5 [63
$ l5 N. v8 C9 r3 M, r9 O
1 u9 Q. h" b  Q7 o" i
4 H# G7 e& \  o不愧我们费这么大劲优化快排，多帅哦！
# J6 P9 j5 f! {8 B; J  z) q
差一个归并排序，后续补上！
1 z# _2 h, B( a( @; c  e+ D8 M
不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
————————————————
3 ?6 g7 ?) m4 X7 g4 d/ g版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
2 f# Y. D6 o2 h# F8 f原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832
  ]: T" {5 x* w6 E' w" J