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

杨利霞

【数据结构初阶-排序】经典的排序算法，很有趣，有没有你不会的呢
0 \& h9 l8 ?, E# c
前言
: V2 f0 v7 f- z本期分享经典排序：
& c7 V* F) ]: G: l- `  f6 L( K
插入排序
直接插入排序
希尔排序
2 X, H0 P; r% w, D1 {- @% \选择排序
直接选择排序
% h. T7 M1 N6 Q  \% S堆排序
5 Y- e( r* t. J$ i/ P交换排序
冒泡排序
9 A. k% c1 T* i% C. x; v快速排序
注：讲解时默认排升序

; ^6 m: H) N% F; K5 |! v6 L( q插入排序
直接插入排序
& i% E3 [3 H7 `" V思想
插入排序，就像玩扑克时，摸牌的过程：

最开始，左手没牌，右手从牌堆中摸
$ e7 P1 ^/ h+ H. ^- M& C右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
* `2 y4 U. u3 o. h如此一来就能保证左手的排始终有序，摸完牌后也就排序完成
7 @: T8 g. U0 L# o. o

0 a/ Y! f7 A) H+ w! S操作
4 I" R3 d  R$ x1 e' j; S, e/ F设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
单趟排序：
0 m& a3 Y6 f) P) }( D6 X每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
是正确位置：插入
不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
整体趟数：
+ T% r; Z8 U) q+ P7 K) G! l- M8 N若元素个数为n，需要排n趟
void InsertSort(int* arr, int sz)
5 L, p2 u0 K* A2 M3 H" j- B{
9 U. O2 @/ n1 x8 x        //end + 1 < sz
        //end < sz - 1
( v! r. \2 h4 ~- H$ i+ Y8 @4 i, l        int i = 0;
        for (i = 0; i < sz - 1; i++)
        {
                int end = i;
5 h: y% o0 T/ N& ]& S                int tmp = arr[end + 1];

                //找插入位置
                while (end >= 0)
4 c7 z* B/ ^2 \                {
                        //不是插入位置：当前数据往后挪
                        if (tmp < arr[end])
, j) l, D2 J1 a( ~& X2 {0 p& ]                        {
. Z: b7 g- i$ T8 l                                arr[end + 1] = arr[end];
                                end--;
                        }
                        //是插入位置：跳出循环插入
, B! u& M" ^  j% k  m$ C                        else
                        {
                                break;
                        }
  ~/ s2 D; @% }, W                }
8 d  D7 g4 ~- q: j3 g                //插入
                //1. 插入位置是[0]，end == -1，不合循环条件跳出
; |; ~1 A6 J$ y+ Y8 P                //2. 找到插入位置，break跳出
                arr[end + 1] = tmp;
' X( E' l/ C( X& o* N        }
}

6 X' m9 ]3 V3 h# a3 o1 D& U1
2
3
5 k2 M7 Q) K) u& l$ O. l: r4
+ }2 q8 G; W' ?- H5
6
7
) Q- Y2 A' |: r( J+ q, K* Z8
/ x4 w* ~& m4 A- M4 B. M+ B; Q9
" J* d+ X0 a; P10
9 P; H. [& m7 j11
12
& K3 x4 c" O5 D  a* }& }$ N" ?13
14
& F6 A5 [6 j+ |) U15
16
) A" |+ K9 n( _* q. H/ `17
# o) n+ u. D8 d5 y+ K3 ?9 T18
19
20
$ v# u7 u# c$ H/ J' P21
5 K8 K* P  x# x2 s; W22
23
* `: D% U: Y# Z' z3 @8 Q24
25
3 O; g! x6 |  Z1 g26
27
28
  i$ f- c$ O4 C9 y& Q29
  L" A1 A- @& K. t. J3 D30
31

! V! t) x- E# n, y( G$ _
! a8 o& `. e2 a% m1 W& `稳定性
3 x, V# N: N# }7 h8 E插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以

直接插入排序是稳定的
+ |# F0 X; j; I" V6 `$ J1 `
复杂度
* Z; ~  O+ ^* t# |4 J: H时间复杂度
最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）

. ?: W8 z  J7 w% h- ?O(n)

' l7 h$ o) f" u9 X# ], }: |最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2
, A8 ?' A+ h" Y9 y, I/ T3 p
O(n^2)

空间复杂度
, G* T/ d! A) L% n" y% Q! `O(1)

希尔排序（缩小增量排序）
希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序
) }( q8 |3 J" R5 r8 Y* p5 T
优化思想
增量gap不止用来分组，也意味着数据移动的步长，所以

4 d3 d  `4 a! D3 V% |gap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高


+ j- S( @, n' N, ^操作
单趟排序：
& c$ H7 w. q5 I& d- ^
设定一个不断减小的增量gap，也是元素移动的步长
! d) L4 H+ M' i以gap对序列分组，并对每组分好的序列进行直接插入排序
不断缩小gap，并排序
; B2 \4 P7 S5 S9 w: {/ l" L*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
整体趟数：
# ]8 G+ Q8 V& E0 D8 B6 t8 C2 W! k
* t# g3 V% s( I4 K* ]9 a, D由gap决定：当gap = 1，排序完成
注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。
- a. M5 y4 J! Z% U+ `
void ShellSort(int* arr, int sz)
{
2 Z6 S8 {2 w2 n  c1 I5 i        int gap = sz;
       
* }2 w4 ?' N6 H% a2 ]    //gap > 1，预处理排序
    //gap == 1，直接插入排序
        while (gap > 1)
        {
                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
3 D+ p  [# Y0 L' {# ~                //gap组
  b7 p& |6 W/ F                for (int j = 0; j < gap; j++)
                {
            //end + gap < sz
, V& O" x% y  A7 l: H4 _                        //end < sz - gap
6 h) O% D3 {& H/ S- S( E                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
: I* D' X9 x' r3 a4 S; h0 b( b  B' t                        {
9 B+ E& {1 |1 ^& ~2 n. b3 F                                int end = i;
+ _( e) \) M7 D& Y' F0 o                                int tmp = arr[end + gap];
                                while (end >= 0)
2 K& w1 s) D' T  d3 P                                {
' N( g0 B1 [& L! @: _) K                                        if (tmp < arr[end])
                                        {
                                                arr[end + gap] = arr[end];
) ^" w1 j5 w) W                                                end -= gap;
" \) g4 {7 S# O( T+ Y& l9 m                                        }
  v# z) H( \/ Q1 e: ?# H  [8 n                                        else
6 K: _# Z+ D! g1 Z/ T6 X: F                                        {
% v: x2 G8 c1 S  [2 X1 K0 G: h0 D8 Y2 z                                                break;
                                        }
                                }
                                arr[end + gap] = tmp;
6 F- v# U0 _- A- U                        }
3 a. U% @" B9 E' m) \/ Q  ^+ k. z                }
        }
9 n( ?5 ?. {# V$ t}

1
" c9 J2 A. F6 r6 }5 ^2
( z: r' z! L% J, L: Z# X  T" o3
4
: h$ V# k/ F' Y) z! h8 Y) M* F  s/ E5
2 @( P1 U  g; V$ s6
) ^% B9 ?( a- a0 X7
8
7 o& O; f- D- e& R  Z9
10
  i% h! ]8 i5 {; Z( q6 X4 T* N11
12
13
, f# j8 s( z& Z' q14
15
4 `1 A* x0 p' n/ S/ v" [# \3 l16
5 @* a* U& m2 Q: C17
- V9 s% m- p% w' ]* {/ B* n1 ?18
19
20
21
22
. [/ P3 U! a) {4 A23
24
25
26
' h1 }6 b" ?7 v' c+ T! v7 h27
28
29
30
3 c( L" F5 y; Z1 f31
  h1 N6 l% B. g% e8 K& a' w32
6 G4 U3 E# n, \$ M' u" c# h8 O33
34
0 O2 y1 d0 I& g! G7 n, W6 h35
0 U; X' k5 I2 W" a3 P其实就是套上”缩小增量“的直接插入排序
" Y, F0 u+ S! o3 I4 D

稳定性
# P5 q  t8 I: f我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以
1 p' a8 E% H  I5 u+ B. V
4 u" f4 K4 S8 g, O$ p希尔排序是不稳定的

复杂度
时间复杂度
% n* T; q4 q: `, U+ v* {希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
0 R3 O) f* e5 x/ X0 @& ]
$ T* l" Y7 k  B+ @% Y6 d, SO(n^1.3)

空间复杂度
O(1)

1 v8 x8 z" V& ?3 i6 m: V& R& n选择排序
直接选择排序
思想
选择排序，遍历序列，选出最小的元素，交换到左边
' }1 x* l) L/ z2 C3 I$ N8 y; R
6 @' p  z. j, s

: M2 F$ [- d  ?  z9 i0 z7 K优化版本：
8 c) o5 c2 t, A4 L9 l
2 |! V" d4 P4 |每次选出最小元素交换到左边，选出最大元素交换到右边
8 G! j% e* R9 v& V6 Q; |2 g
操作
; f& @! f4 ?; \) s1 a, N$ F: F设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]
1 _. n" m" _; l- I+ e6 Z+ W" |
$ |$ e7 b% ]! T% D! r; j, f设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标
# I8 ^$ t' c. f; W( ^) b- d1 R* q
单趟排序：

- D0 ~+ H5 ~6 {- M4 I2 |" \8 @遍历选最值的下标
交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
4 A# R/ A2 p" w+ C4 ~% Y/ z7 T（修正）
整体趟数

若元素个数为n，趟数为 (2/n)
修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标
& |- t, J5 W( E/ I
void SelectSort(int* arr, int sz)
% m: i% r2 ^8 j: ^{
0 @- ?; t8 X1 v* k! O        //闭区间: [begin, end]
        int begin = 0;
+ z( q$ I! d! x& p" Q. U$ U& r        int end = sz - 1;
        while (begin < end)//begin == end 最后一个数，天然有序
5 j9 w! @3 U1 S3 X" E( G3 B        {
                int mini = begin, maxi = begin;
                int i = 0;
, z3 `; t0 W* n1 A) m                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
                {
                        if (arr > arr[maxi])
                                maxi = i;
7 U* J# v" W& J- [) ?0 O                        if (arr < arr[mini])
                                mini = i;
1 d+ i; H" Q7 y9 S/ O: D                }

                Swap(&arr[mini], &arr[begin]);

                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
; |! ~  ]* i' p5 ^+ W4 Q+ g                if (maxi == begin)
3 Z" Q5 E+ J0 R2 N" W: S5 ^+ d( d                        maxi = mini;
1 P0 E6 z- u! K) _) V$ S                Swap(&arr[maxi], &arr[end]);

5 M( d. S# k) O, _' k+ b                begin++;
# K! \' f& n4 b9 e) Y                end--;
% u9 H: X: `; ?& R' j) l0 G3 d        }
}

* S; q- o5 Y' a) J! Z( D1
2
3
4
5
6
) `$ I) N5 P% T- S7
8
9
+ o6 m; s* }# W+ X: e10
) A0 X* ]2 f# D11
' d4 J5 R3 j0 a# E' w/ \12
5 |: Z% s& l0 N3 L13
14
* ?) x3 m. u. \15
16
) {* Y# G. ^% Q  x& W- I17
18
+ \8 h1 c! R) r; n- H0 k" O8 M19
* ?8 d- U; e7 j20
$ K" M1 g: w5 Z* j5 j21
22
$ f0 h5 a& q# Z/ c6 V9 L23
24
, b1 X( r  R$ i! c8 v3 o& C+ g25
4 p( Y$ F+ ]* d( x( }1 Y6 T26
27
: ]9 Z2 [% G/ z9 Z2 [+ ~9 P28


稳定性
选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以

选择排序是不稳定的
8 X0 p2 p8 @; ~" ?1 c
复杂度
- L+ m; B4 ^+ ^' [. q时间复杂度
0 W" X' o: F- h- j最好：
# u% e, K, q$ n# @6 R2 r
7 x. _" P0 [2 ]1 a3 O/ E比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2

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

O(n^2)

# i3 R8 A: E" P: k7 v  {最坏：
# N) L; d( j1 A2 q5 i/ @' Z' c
比较次数：O(n^2)
5 G, T2 _8 d8 O2 z
交换次数：O(n)

O(n^2)

/ H6 K; h8 k% U空间复杂度
* z$ y  `/ e2 M! j% m* h3 zO(1)
! W- U% @. Y) _# f) _  [5 u
! f$ h3 A+ ]& V% ^! O堆排序
* W7 H9 c; ~: s" Y0 Z思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆
& f$ \9 X2 X0 l) d* I5 u


操作
建大堆
单趟排序：
选堆顶和堆尾的元素交换，则堆尾的元素排好
每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
整体趟数：
" z* g3 l) n* }, ]5 z; z- M若元素个数为n，则排n趟
void Swap(int* e1, int* e2)
{
        assert(e1 && e2);
- B+ V4 y4 N7 P$ ]! o2 i" s
        int tmp = *e1;
        *e1 = *e2;
) p" ^7 j! i$ T3 p0 M3 h; l" z        *e2 = tmp;
- H: K% T+ n- l. k4 X# Y% i/ ^* r6 A}

' ~7 q: E2 X; q( b2 qvoid AdjustDown(int* arr, int sz, int parent)
# [3 t( O- T  S7 ~{
$ m% C5 m8 F' Y! e, Y7 Y; r        //建大堆，排升序
: U7 S+ K1 D4 M4 ]        assert(arr);
       
3 w7 a9 S; L) p$ d- B9 J    //默认大孩子是左孩子
        int theChild = parent * 2 + 1;
2 i- Y/ Z( d3 {- c# U        while (theChild < sz)
, A3 B# S3 }" i, i5 p% t        {
        //如果大孩子是右孩子则修正
( H" `5 m0 Q6 J! @                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
                {
                        theChild++;
                }
                if (arr[theChild] > arr[parent])
9 X( a$ X6 {) W( G6 k$ j                {
$ |9 t1 X, p. [% Q, s, s                        Swap(&arr[parent], &arr[theChild]);
            //迭代往下走
                        parent = theChild;
+ q! Q1 r7 E( u5 _- y( n                        theChild = parent * 2 + 1;
" O% \/ w) }" ?                }
1 |" L) `4 ~7 Y* b                else
                {
! n: T3 [" J6 a+ n) T  z% t                        break;
                }
- r3 g3 L, c4 l3 n0 s# y! M! n) a        }
, Z9 M7 S+ Q* Y' h9 W, b}

void HeapSort(int* arr, int sz)
- I: e% i% d: H% M+ a" f# D1 K4 }{
) W: B; ?7 k2 b3 S        //1.建大堆
        int i = 0;
" j1 A9 h1 ~+ n" {/ r6 s0 i1 S% k# `- S        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
  i% p& r8 m+ U0 ~2 Y2 _        {
                AdjustDown(arr, sz, i);
  @. ]! S" e) D* f- X) |        }

        //2. 选数
0 F# \! Y( F1 `' x7 t, p* p- Q5 l8 z        i = 1;
; A2 Y" l& F/ `% S. F  Y" N        while (i < sz)
        {
9 U( C) n6 u3 B: `% ]                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
' N( i8 C$ C1 J, L! Z                i++;
& k7 w) O/ D( }, C  v7 J( E        }
6 y+ L- e: x7 M0 S" V# O' v4 K}

1
2
$ a1 l0 Z3 R& W$ V3
6 W% e" \% u; V5 f( C. Q4
5
+ j# J5 d2 ]: W% N+ e6
7
8
' Y- g4 x4 F' t( f. @# i9 g7 }0 }9
10
11
12
13
! n. R5 b8 ?* B; e14
* ]3 q2 U! O+ ?0 Z: d4 U- F! G1 c15
16
) s  I2 i9 A4 |/ O" q% }17
18
19
: @. I8 t! ?- j. l/ k" Q% S- n20
21
22
23
24
25
; U" ]) {' u1 V9 b* r26
27
" ~4 \8 L( X6 o. @: s( a1 Z' q28
29
4 x3 Z4 V( t( U3 K7 L30
31
! {" o# i6 O4 I- G; t32
7 O/ ?* ]% c9 @/ d) p$ s; h' S1 s3 X33
34
. ?* t/ |  x' h+ [1 L$ {35
8 p. }9 L+ N" R3 c& r36
37
* K4 l! s5 a! o* W8 F: I38
39
* {7 L  j; i& }( s2 S" P3 i40
41
42
# g) R0 l! V, N43
! G  |- Z5 h2 @3 j. B  s44
7 o4 k/ T2 F; f8 P' {7 Z5 D6 D45
46
47
48
49
( d. T  P$ {; n6 E) l( T50
51
52
53
" O" d' X7 j  e- x% O8 S: @$ H54
& F2 A" ~7 W6 h2 P, y0 C55

4 D6 C; i! C8 o5 Z0 v8 d& N# I
稳定性
建堆和向下调整都会打乱元素顺序，所以
) \" l  a0 z; I1 S2 ~- D
堆排序是不稳定的
% y5 g/ E5 K) q6 Z. M
复杂度
, B, k6 i/ I: L- R. q# J时间复杂度
单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为
- }( K/ A: g$ X+ E$ u' e
O(n*logn)
5 \: @1 I4 u4 m) T# C( C
6 O6 ]1 Z6 a8 {空间复杂度
, F( Z% `4 ~% z1 y, W4 h7 k: N$ q原地建堆

# i8 ]# Z# K: D$ r& h. S3 @. j8 ZO(1)
! V! J/ {# O5 v9 H. X, X" v( T
交换排序
3 ]' j' e( m$ t' _冒泡排序
( w0 {+ }2 J2 ^! A* j思想
5 e- v& ?( K+ t+ L0 l冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素

3 _9 s1 e) A, z9 O0 Y; S* u' \

操作
单趟排序：
每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
4 f6 P( |) U8 L每趟排好一个元素，所以需要排序的元素每次减少一个
整体趟数
& I* j9 U& o$ r. I3 _若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
void BubbleSort(int* arr, int sz)
{
5 e* ?* [# E5 G0 e1 {) N/ o        int i = 0;
0 [# m% W5 x3 w6 C& T' X" c1 \        int j = 0;
# {- ]# k# C4 a+ H. O/ q. F" S        for (j = 0; j < sz - 1; j++)
        {
+ ^$ Q( Z0 w3 F  W% w                for (i = 0; i < sz - j - 1; i++)
                {
                        if (arr > arr[i + 1])
                        {
                                Swap(&arr, &arr[i + 1]);
  j9 _! H8 e( P                                flag = 0;
                        }
: P) ^+ e1 Q5 R                }
        }
}

! r! x9 {- J- n  q1
2
( O/ G+ e% x  l" q4 P1 ^+ G3
4
" n4 h( u/ s+ M1 H( }5
6
7
8
9
10
11
, A0 m: x! y) c. K+ l% k' d% M12
13
- C* V$ D/ o1 k: ?3 m5 k14
15
16
优化
当遍历一遍发现序列有序，直接跳出

2 l6 l" C$ @- _; J% {8 }void BubbleSort(int* arr, int sz)
{
4 s" [1 D1 y: r  J; k. I        int i = 0;
        int j = 0;
        for (j = 0; j < sz - 1; j++)
        {
                int flag = 1;
9 _1 H% [& H* F% J                for (i = 0; i < sz - j - 1; i++)
! `  W- |& m( n9 v                {
                        if (arr > arr[i + 1])
                        {
                                Swap(&arr, &arr[i + 1]);
/ m& i! @% \% e$ S' @& @$ C# t                                flag = 0;//不是有序就置0
                        }
+ w8 g$ i+ q/ X( i( S8 s8 e. o                }
                if (flag)//如果一趟下来还是1代表有序
                        break;
        }
}

1
3 X# U) ~4 G/ X8 W- B3 W* y2
3
0 A; D. `4 [4 z' o; p7 x) D, u- h4
! v$ x, e9 D+ n9 i+ U5
6
7
$ |6 y: l2 J  t% k7 j+ p8
9
& k: C8 c! Q) n5 N' G" {. G# f7 M10
11
8 L4 y6 Q8 ?# A7 u+ A3 C12
13
14
- K; k' j) |! z/ [" D" [15
16
# B; A1 u3 ~% Y2 M& c0 I$ w) t( g17
18
' y' d6 r) \7 r. F' k19

9 l; o: P1 W5 \( v- h( k
稳定性
4 j& z3 @6 ]; r: d- O; x相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以
9 _; i/ l9 A8 ^# R; [
冒泡排序是稳定的
/ D& e5 F4 A  z% f4 F9 j) X% d) P
复杂度
时间复杂度
) m$ k) m! F9 N* B7 M9 `2 p1 E最好： 当序列有序
8 C4 R3 R: W3 f9 R' ^5 P
未优化：

O(n)
+ h3 z* p# ~0 Q% c2 M
优化：

* e" A8 O' I" o8 F, ?6 }O(1)

9 D# x$ M, g# m最坏：要进行 n-1 趟排序，每趟交换 n-i 次
( r: o# D) E% f5 g& M4 E
O(n^2)
, {) b8 _& t* \- x( Z% z0 {
3 @+ i5 c, c/ N2 f1 M5 p空间复杂度
- {" L% X1 j1 U" e, u! WO(1)

快速排序
思想
分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。
) ~2 t- Q! d$ H* l( ]
所以快速排序可以用递归来实现
2 p1 f$ l9 [1 c/ K% o
操作
有三种单趟排序的方法：

Hoare法
" I2 F: L2 U6 x$ p设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间
; L* ?3 r4 \0 `$ [
左下标 L = begin，右下标 R = end
. E' r; y  x/ c: k& h# ~1 g
设 L R 相遇位置为 meeti
6 h) s  U2 q( N3 h6 t3 \# {
​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”
: u; J. D6 m6 _
7 L- I8 i# @. c  z​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“

选 键值的下标 keyi
! a: V+ S: Q) s
左1位置作 keyi，则 R 先走
( d( m; S2 |8 Q4 ]  V9 h# V# r% N# m右1位置作 keyi，则 L 先走
0 d( H  a( X# }& h# G& \& YR找小，
7 I, n! S( O: k  h, S
找到则停
遇到L，则交换 arr[keyi] 和 arr[meeti]
- }% [% i& A; @L找大

找到则交换 arr[L] 和 arr[R]
遇到R，则交换 arr[keyi] 和 arr[meeti]
' h! [- A- u  S
$ `0 w0 E6 R* K0 U# ~( A" i
解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
答案是肯定的：
# L* X- k# a2 C: \& G4 ~



//[left, right]
int PartSort(int* arr, int left, int right)
{
: t- x/ }- V3 }9 c. k        int keyi = left;
        //相遇则排好一趟
$ `1 I, `  O5 q) `9 V9 x        while (left < right)
        {
                //R找小
        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
! P1 G8 o; y: T$ i+ q) r. O$ @                while (left < right && arr[right] >= arr[keyi])
& M( P) k" S8 @1 O0 Z0 \: s                {
                        right--;
                }

1 \% ?9 e) A* ~% D0 }                //L找大
                while (left < right && arr[left] <= arr[keyi])
# D% B+ l+ t! V. W' C                {
                        left++;
                }
8 e' G9 w% w  m7 S" |               
        //相遇就不交换了
7 ~+ t: b7 }/ P. ^, E                if (left < right)
                        Swap(&arr[left], &arr[right]);
        }
6 v# d# Y4 A% `7 _2 F' X
+ V, J/ z& o/ l1 c        int meeti = left;

        Swap(&arr[keyi], &arr[meeti]);

        return meeti;
}
# _/ J. [$ o! o. i6 Q- }
$ ^& u/ p: O  f( y1
2
3
8 v0 A& [8 W" \+ F! w" m+ I- U4
5
6
7
8
9 f! g" d$ ^& ^6 O9
3 k5 w4 ~" M& g. W10
11
1 K: \  R! p7 [& d3 t8 `12
13
14
15
% G1 r6 t, e5 a16
+ `, n# ^) G& a. ~* c17
# s- D6 K. {/ j" c% B* X% k18
4 _8 d9 h) X$ t- t8 F7 s19
20
, _' s; K5 x" L$ l21
22
23
24
2 D! p4 P' Z) K* l25
" s8 r4 a# T- t$ x) Y" \7 C26
: K3 L3 \9 @1 p1 B/ F* i( e9 o27
# C6 m! p; K% i5 d$ @28
# k" z& i( C" [, g29
  C4 U4 l/ ]1 D# T" B30
31
( R% Q* s- c) Q& B0 f& t32


6 H$ M! E: X/ K% ?+ L2 M" t解惑：为什么key要选左1/右1，选中间不行吗？

7 n' D# M0 C+ H
. A0 L6 s( s# \2 B8 K/ k$ n可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深
2 w4 d& O* L  J! i. i9 a8 @

: p+ ^; m' A( w8 W
& `. R/ E8 L; O# `+ d
非常容易栈溢出，怎么解决？针对有序情况，优化选key
# S) V. X+ ~1 b, T( t7 b
优化选key
随机选 key （是一种办法，但是不那么彻底）
' E$ d/ r* b/ H& v* e( [6 w5 K7 I选中间位置作 key
0 {3 d! A' s9 F+ z6 @1 J% P解惑：那先前实现的单趟排序不就失效了吗！
# Y! C  y5 q- I3 u+ j$ x：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑

* f* v% K1 p8 V# I# {' x解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
前辈给出三数取中的方法

, D& E, z. q" m0 t三数取中
在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
优化选key后的Hoare单趟排序：
8 \) B, B6 E- }
. A+ a, ?3 t9 k9 {0 i0 lint GetMidIndex(int* arr, int left, int right)
{
: m/ M5 V* F( H3 h5 K5 {5 r        int mid = left + (right - left) / 2;
//  int mid = rand()%(right - left) + left;//增加了一定随机性
        if (arr[left] < arr[mid])
        {
% e4 A7 z0 [1 Z/ p" o                if (arr[right] < arr[left])
                        mid = left;
! ]3 J- `4 q, p! G+ _7 E7 }                else if (arr[right] > arr[mid])
                        mid = mid;
                else
2 v. D% U# z$ _, i; o/ w; B. d* G" ]                        mid = right;
        }
        else//arr[left] > arr[mid]
        {
                if (arr[right] > arr[left])
                        mid = left;
9 R0 u% g. P9 A2 z$ G4 X6 i                else if (arr[mid] > arr[right])
' J) U* A5 S1 w. d  P" T                        mid = mid;
                else
                        mid = right;
        }
        return mid;
4 w+ \- n% Z( T& L/ [5 g}

. v+ \3 @3 m: [+ C0 a- X/ h5 zint PartSort_Hoare(int* arr, int left, int right)
2 |  W3 Q) f1 q8 k* r{
% r! r; t/ z) ?6 U& z3 W        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
        int mid = GetMidIndex(arr, left, right);
' T6 v5 @' V% C( H
- s4 V+ S' U* \; r% L        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
. ^& ^+ a0 L) y5 t        Swap(&arr[mid], &arr[left]);

. V6 f2 B7 ^6 g4 w4 n, c; Z9 C( O/ b0 {        int keyi = left;
        while (left < right)
        {
                //R找小
  i* ?( r0 [6 X                while (left < right && arr[right] >= arr[keyi])
" v0 o9 ]8 x1 C* ~, Y9 C3 u0 `& g                        right--;

9 c, Y9 _  ^; n$ O/ E                //L找大
                while (left < right&& arr[left] <= arr[keyi])
                        left++;

                if (left < right)
                        Swap(&arr[left], &arr[right]);
  O$ I5 M1 y5 R0 X+ T# w        }

        int meeti = left;
5 k5 f3 R# p# D) [, f9 w% V, @
4 L1 s4 @7 e) |        Swap(&arr[keyi], &arr[meeti]);

        return meeti;
( Q% F' d0 e6 Z4 Q6 i}
+ _* S2 W. l' ~/ \% t
/ K; k8 I/ H3 r) t+ O. h' Q% I1
$ Y3 w; ?) ?5 w. j7 k2
3
+ m+ |( X0 l4 T! {  q( f5 d4
5
6
) j: h( O& x$ _; P7
8
9 I- i: w  [+ Y3 K1 `) y# a* b' h' l9
8 x0 h; c# V' H10
11
8 b( T( L' q& D9 g# p12
13
8 K6 e: n8 \' D1 ^14
15
, D& P- @( T% @4 Z2 }' K) P/ Y16
17
5 {/ G7 o+ k% c18
- y1 }! a* K9 j7 Z5 u. x# I) W1 g19
. w; x) g* F7 @) H" N0 d20
7 j' u1 L# j& b  {) N$ I2 C21
* t* t4 o& q4 n6 X" F22
2 X# s1 Q' z8 n23
24
25
26
27
" o: i) g% {# ]+ {28
29
2 D% r( P" p$ h. I$ `" f30
; r: Z, y) M3 o- a: L6 v0 F31
32
33
' k4 Y) j! S% K34
35
36
37
7 A8 X8 H$ j+ s- Y% p6 T38
39
40
41
2 D$ p7 P0 d, L7 h' s% Q: E42
43
7 v& E; b5 a- g* n/ u1 x; v44
45
+ L' P% R# O% c4 Z3 O% t+ R46
47
48
+ d1 V6 T1 o: h1 d49
) H. ~0 D3 E, h3 Q1 O# X, W, y+ Q50
51
52
/ u% e5 g- b% Q, o53
54
: X" A7 S4 @% O9 t' f挖坑法
/ R$ o6 e+ R0 n: d7 ]初始状态：L作坑，其下标存为key
(1) R找小，扔进坑，R作坑
2 e0 V* y( W; G# B: d(2) L找大，扔进坑，L作坑
* }7 m0 H, T! S) g$ [, X9 `3 G重复 (1) (2)
& b3 k! {- m& @( a/ n/ ?最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]


int PartSort_Hole(int* arr, int left, int right)
{
        int mid = GetMidIndex(arr, left, right);
& X/ c! z% t8 f' \& }        Swap(&arr[mid], &arr[left]);

: h4 W5 K8 ?( m' R        int key = arr[left];
. [1 G8 j0 k/ Z( a  l! `/ P. L; C        //L作坑
        int hole = left;
0 ~! c0 ?" a+ |" I2 V. d4 a' C        while (left < right)
        {
                //R找小，扔进坑，R作坑
                while (left < right && arr[right] >= key)
                        right--;
* F# s2 F% m; o4 X0 r  R! l                arr[hole] = arr[right];
                hole = right;

                //L找大，扔进坑，L作坑
                while (left < right && arr[left] <= key)
6 B( A' c9 b! ?9 F+ ~' W; J5 o3 }/ p                        left++;
                arr[hole] = arr[left];
6 X- |: A+ O+ ~; F. O: W                hole = left;
0 |$ z, n& N* D9 I- q8 o+ t+ M, D        }
        //meet
% N3 q, x* [& Y9 y        int meeti = hole;
; M! W; p/ N: e6 K        arr[meeti] = key;

        return meeti;
, X/ i. J0 h/ s. F+ \}

/ {' h1 Q. ?' U( o1
4 n. v) S0 C* }1 l3 r2
6 A) N, R8 o  j9 B2 f8 s3
4
5
$ P: G+ z1 K$ N- v9 [/ |6
' |6 U! w# R7 C7
4 B9 c9 _7 z6 @, s8
9
3 G  m" t7 ~& G8 D7 i/ @' J10
( S% f* ]8 T9 _0 I% x; `+ h9 @" m11
5 ~. ?' l: V9 T5 d5 g( D# s12
13
, e2 \/ Y8 p& l1 ^  U14
15
16
17
% U# g! i6 T1 E- j( U: i2 b18
( G' ]" t" \( x% ]4 `( a19
" J. [8 e: {6 p& V# N20
21
0 e# i3 {# g/ f% Z22
, s7 G, j' |9 J! S  ~23
1 l' P7 f& j; s7 O: D. I24
25
5 R3 u8 g) \! c9 ]+ y26
27
28
/ v. @3 J$ g* M% z* o7 `1 k前后指针法
9 F0 c# K6 J; ?# q# z  @此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多
/ d" c- j& {- S* o' _3 o: \
cur找小，找到则停
! }3 S8 q9 f6 R1 z++prev
如果 prev != cur，交换 arr[prev] 和 arr[cur]
如果 prev == cur，不交换
当cur越界，代表找完，排好序了
1 i: }6 e, e1 y+ d- R) Yprev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低
9 n1 N3 O( C4 U; l* j. n! f( j& c4 C
2 N- b, O$ }/ f

int PartSort3(int* arr, int left, int right)
{
        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
       
  //int key = arr[left];
        int keyi = left;
2 q0 k. w4 V% V% P
        int prev = left;
        int cur = prev + 1;
       
    //cur越界：找完小的，prev的左边全小，prev右边全大
        while (cur <= right)
        {
& u# y; ~: f- S1 m+ h& D; X        //++prev == cur 没必要交换
& P* V6 v; }7 _2 T, V. F) `% v                if (arr[cur] < arr[keyi] && ++prev != cur)               
$ ^1 X9 z* Q% t* @9 ?- n9 `                        Swap(&arr[prev], &arr[cur]);
+ w# T& [8 C4 [/ A
                cur++;
        }
- P  }0 C" t# B& d$ d: c
# Z) i% q, I- N; }        //键值存是的值：
        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
& W" N/ J: T9 I. v* M5 g$ `7 _9 C        //Swap(&arr[prev], &arr[left]);//这才对
2 y0 o! T0 t6 c  o) }  ~    //键值存的是下标：
        Swap(&arr[prev], &arr[keyi]);
, X  v! h& W; \6 {# V4 m$ M. K- {; V
        return prev;
& j* {6 a( [) t0 p8 M- A( f}
, f0 ~. c3 c% W
6 g8 S) M9 d' z+ G! f1
( L- P$ _0 i+ `; L+ z2
3
4
5
6
/ g% p- L0 ?4 G" T7
7 ~8 O% F+ n2 I; o" r0 v8 P) U8
9
& e1 W6 M% l: Y* m. D: k10
% I& H5 B" M- f* `9 i11
' W; ]% }  e1 V9 D# A12
, i1 z" s0 n4 F- O13
14
( g% S/ O1 w! P8 V+ Q15
' ^% y+ Q1 ?; `6 b16
9 V# X8 \' `* O. ^9 ]' A17
5 Q1 k4 E8 ?& C0 e( l! j18
19
6 k2 }' L3 U& S" L  R& w0 I! [) A/ w20
) w& v- x) r0 W8 P/ I/ K; J9 ?9 U21
: c1 T( D* J( f1 k4 g22
* E. J: r0 h& l& L23
* `1 R0 h7 d- D; ^$ R- @  O24
, |' {$ G+ Q4 w5 T25
26
. @5 d9 y- U' X! t: E27
; t- j) G9 ^& Y2 _: ]0 P3 Z28
29
整体排序
递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

//[begin, end]
  P* @# i4 e# n/ e4 m7 S* ovoid QuickSort(int* arr, int begin, int end)
{
        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
) Y  H: S4 J6 }) i  o, q' L+ D* M        // [begin, meeti-1] - meeti - [meeti+1, end]
- {/ q: v' U9 Q+ C' Q! F0 X9 {                //1.begin > end:超出范围
, M$ l; L! B2 E8 [1 F0 Q                //2.begin == end:一个数天然有序
4 s& v4 ]1 f9 \    if(begin >= end)
  o6 E; Z0 R8 e$ U4 o2 H        return;
% S; D0 T% s5 Z* q% J0 T
                //排好meeti
4 r: ^$ g7 {0 s                int meeti = PartSort3(arr, begin, end);
3 n1 {2 u' S# W1 k
, W1 [% \4 p* H) ~                //排好左右子区间
/ C2 S9 v! Z. D* g0 I4 e  `                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
        }
9 s7 M6 S! a' [}
- p4 m9 E3 y: C8 I# s7 B8 p
1 _# o) c. c8 }8 x/ W1
2
' K( p* }7 N4 D3
6 j6 R# N0 i2 B4 i4
5
. g( L% \& S2 |7 ^# _' F6
7
% o+ P6 ~. M# l8
! m3 ]  g. A$ i' t+ U: e9 D9
2 Q- ~7 U- @, O10
2 z5 X- K: U" D$ N/ P11
7 S+ U) X( `, g* v5 @9 l* h, J12
1 {5 L/ C0 P2 U' P% w! v( Z. t) R13
6 Z  }, s1 P/ f3 c$ B& t  f+ l14
15
8 ]1 f+ C5 [7 ^( o! Q# K16
+ k" F( J& c9 _) A( B17
18
…

( B) b/ e% w3 e! B% t# f没想到吧，还还还还有可以优化的地方！
4 x& x) B9 C7 }( M) c$ |
  W  C& M9 S, A0 D$ }" g0 ~7 {优化小区间

+ F6 O) V1 L: b: u. s
, Z7 D2 n  m" j7 E- B+ _如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序

那什么算是小区间？
- O/ T+ a! ?& e  ?5 X
其实小区间没有确切标准，8-15左右都可以的
- p+ u: q( G9 t' y/ X
5 H; O; P: j1 z4 ?0 p
这里就把小区间定义为 含有 8个数或以内 的区间
% d! O# v' {. S  _  u+ f2 ?5 M
//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
        if (begin >= end)
9 |4 E) }' V* K2 w                return;
' n- w( E& v5 Q3 h
        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
        {
- F& K+ m" E: L6 z. a                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
) Q- P2 w! ~  N1 o$ O# `8 `3 E! l        }
5 N. G0 C9 Q% ?: |" y/ d        else
) x( r0 `) {. f8 p; J4 P2 w! u        {
1 s, f) p8 y; N& z                int meeti = PartSort3(arr, begin, end);

* p8 B: q3 `+ m0 R                QuickSort(arr, begin, meeti - 1);
. X9 m" }* V; g( h% i                QuickSort(arr, meeti + 1, end);
5 k; B8 B. q& c        }
}

7 ]5 D* p  q/ a9 X1
* _  Q  I% |0 f0 J. z; `$ l7 x2
3
4
( W; [) v0 R4 y6 i; R' F. G$ f5
6
7
9 C( O! Y1 R  w9 W. {8
9
10
/ ~: I% N6 T/ ~$ W: J11
& I: ~+ o3 B% W7 h5 ~12
& K& |0 w& G+ O9 D7 |13
14
7 F2 r' s1 u/ x. H15
3 d9 ^' @  T, F% @' y16
6 N8 Z& g8 V' q0 Y" x( Z2 Q4 E2 P1 V17
18
, M$ r' v$ s  Y+ Y19
快速排序非递归
为了解决彻底递归深度深的痛点，我们来试着把它改成非递归

思路：
& j5 \  C" f, y/ g, v递归深度深，栈的空间又小，会栈溢出…
% {/ q/ K8 P1 F* j6 @: V; B' q# o4 {
那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！

核心思路：在堆上创建“栈帧”

8 b2 e8 _$ g* |$ P4 P快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的



2 T# L8 @; c0 G# s) d9 z在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：

. P/ _( R0 H/ G& v- t先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
" D8 _1 }! B9 y- }; p先取end：先入begin
" x% k- r6 O6 Svoid QuickSortNonR(int* arr, int begin, int end)
{
        ST st;
" }7 G2 L# X  c' d0 m" _        StackInit(&st);
# ]4 c% T. }! ~* C) q' u- {: }- |       
    //先入begin
% q: V. @: d- C. H0 u$ h5 h        StackPush(&st, begin);
* K8 O: G7 M. p  E    //后入end
# v- j6 b' q5 h( p        StackPush(&st, end);
. d4 E# t9 j" z: z8 Z2 h" Q1 F
2 B# T9 [! g; k1 H$ m        while (!StackEmpty(&st))
0 C# a( a, M* g4 t; |9 w        {
                //先取end
$ J3 }# D! o) @. F0 P4 \; g                int right = StackTop(&st);
                StackPop(&st);
                //后取begin
                int left = StackTop(&st);
" M7 M5 ^, R( C  ^$ ]                StackPop(&st);

                if (left >= right)//1.只有一个值  2.区间非法
  O% ^* J& h0 c/ G+ @                        continue;  
- f: T' T" _/ }4 Y" G$ t% J                               
# B* W2 Z, K4 E$ b! O1 g                int keyi = PartSort_Pointer(arr, left, right);
& E2 m# `# O6 u2 U( ]) V3 |6 n) M
8 h* S9 J& Q, s4 G! O0 p5 w                //先入右区间
: |6 ]( r% \2 e7 x% v1 P: o: r                StackPush(&st, keyi + 1);
                StackPush(&st, right);
                //后入左区间
                StackPush(&st, left);
  }8 l( E. X: K: m. W
3 I2 I0 `1 Y; r                StackPush(&st, keyi - 1);
: t% ^( w' p6 A4 K  R; V6 S        }
3 D$ o% s6 f( a/ c7 Y
# i( e# b5 y" @" {- @$ N/ x        StackDestroy(&st);
}

1
2
4 c  d9 T$ k' G5 T3
- X5 t- ~$ a% d" q1 \( |  K4
7 x3 M7 e( l( O2 Q# }9 U, J( I5
+ N4 ~8 x- n1 C! \; E6
7
8
9
10
  f9 P) d4 n7 r8 V11
12
3 m1 V6 z  z. v$ O+ e- V( Y* M7 Q13
14
15
16
17
18
19
20
21
  e" _1 u# e1 L* n: U% M5 g22
( u! l8 [* J6 I" D, O/ C23
. y7 @+ a+ ?  [6 i* f: _24
25
26
( Q3 G) n4 d+ g27
28
4 t4 P/ m% Q7 v- x9 n, _$ ^9 \29
30
; w" _, ]8 I: {+ X3 H& k31
4 n, \8 N) u( L2 W; W32
* H( v$ t8 \+ m% C# u# O33
' U' l. k5 J+ v34
35
+ s9 ]7 a- w  p1 E! ~$ Y9 q2 D& ^数据结构栈的实现可以看博主之前发的博客


8 M3 q5 {6 S8 `8 b( f0 r归并排序
  m; M/ T" |6 r: f5 ?
! |( n3 Y9 p( W% S# U…

性能测试
void TestOP()
{
% w* T* q& x: m6 |3 F        srand(time(0));
        const int N = 100000;
) I! W: s$ P6 G/ `; S6 O! N9 g        int* a1 = (int*)malloc(sizeof(int) * N);
  A4 a0 \9 h$ w! V  F3 q        assert(a1);
7 }$ \7 Q% |- M! i7 r. Z+ W        int* a2 = (int*)malloc(sizeof(int) * N);
        assert(a2);
# V2 E1 M. ~: u/ |: k& _        int* a3 = (int*)malloc(sizeof(int) * N);
        assert(a3);
        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
9 Q/ O7 E' i) c        int* a5 = (int*)malloc(sizeof(int) * N);
, r& j5 @5 L! F: G. v        assert(a5);
7 a1 Q8 n+ f& n
        for (int i = 0; i < N; ++i)
        {
; {0 |& f- ^3 f* S7 C$ @  a! ]' e                a1 = rand();
                a2 = a1;
                a3 = a1;
  V$ G  y2 ]# C2 j* D. q8 |                a4 = a1;
                a5 = a1;
) m5 Q$ k# p$ r: s% C        }
; O! ?3 c$ J4 |: m" f2 |
        int begin1 = clock();
* E7 F. o6 L/ {/ b$ M1 M        InsertSort(a1, N);
        int end1 = clock();

# Y+ z9 j1 {  j# N- K/ y; B- D        int begin2 = clock();
* v3 {+ F' f# u+ U        ShellSort(a2, N);
) S; |" r' G: E1 x8 B9 {! k1 [2 E  U        int end2 = clock();

& f' @, W/ P9 b: e# s        int begin3 = clock();
        SelectSort(a3, N);
        int end3 = clock();
# A) W3 u# s& C, c$ w
        int begin4 = clock();
6 b9 l* |" u2 r" P* |- ]* ]' X4 i        HeapSort(a4, N);
9 {0 E& u" p8 {( M: t% p3 ^        int end4 = clock();

        int begin5 = clock();
& T5 @3 a0 ?3 d# \; ^# P        QuickSort(a5, 0, N - 1);
5 l& C& o1 m' i% k: I1 b/ g3 I                //1.中间key
( f" Q9 ]" j7 s                //QuickSort(a2, 0, N - 1);
( Q4 e1 d1 p) Y4 Q: H- B5 ~3 h                //2.三数取中
' k! T5 R0 ^  a7 m6 R/ E- M                //QuickSort(a2, 0, N - 1);
( I* R3 F) b  w" |1 |( m                //3.小区间优化
                //QuickSort(a2, 0, N - 1);
        int end5 = clock();


! Z. k4 |  n1 V* ?3 J        printf("InsertSort:%d\n", end1 - begin1);
        printf("ShellSort:%d\n", end2 - begin2);
        printf("SelectSort:%d\n", end3 - begin3);
        printf("HeapSort:%d\n", end4 - begin4);
        printf("QuickSort:%d\n", end5 - begin5);
* D! `, V. w/ d! O
: G% y- Z1 ?# P% T: {  n2 ]' H        free(a1);
. T/ C! [- U5 ~4 N! H        free(a2);
        free(a3);
        free(a4);
        free(a5);
4 r, }  ^- D$ j! s8 ]* U}
. h' c+ W8 ~  G7 `# y. @% M
1
2
- o$ ^8 [# k# ^9 C3
4
5
6 ^# B4 g& f8 T3 y" S6
7
0 w& Z& I3 Y8 l! Y5 X- E8
9
10
$ q- c2 y3 k' x  `2 {11
2 q) z% f$ R) `; Y% G6 z1 ]* T12
13
2 Q5 i4 R$ o( w  V14
$ s/ u# C: S) |$ ]15
/ N" ?" @$ ?3 p9 _* {- {16
17
1 ]3 G! V% s. O" s18
  @! m9 M0 I- j! }- |9 s' `19
3 ^- W1 Z3 g0 }5 \, u: A/ a20
* T7 e) h: N! l9 i, d21
% M- u" y# q4 o" {22
23
24
25
26
27
28
) q$ B' B" S( R+ z' [% `6 _29
+ q( ]% H5 {& Z8 X6 c  P  O. Z30
31
, s3 M3 \& ]9 {3 @4 A4 `2 m9 C32
5 w; e3 O1 h- B  A/ k$ b33
34
! D7 B/ a% U& z. T5 @7 L35
' Y' r, v, i. g$ k9 z36
37
6 A, X# h: U- m7 y38
( k8 ?+ O4 y( o" D, c39
40
- ^5 y* m8 s; [3 j41
9 q# @% V- o2 i8 H) \9 h42
( c& {7 j; S# s; w43
44
45
; m6 L2 g) z, v+ |6 n  W' n46
47
; G( k! n( |6 Z48
# y: H3 t/ m! `# R49
7 }8 ^8 n, d$ ^5 m  r9 X! _, c50
6 w# I3 [+ C5 a# J1 a+ w/ B51
3 v/ _% x  n; ~, u6 a52
53
4 X: ~+ ?" o" d- [54
55
. N- [% f* J1 e" L. [) k- w' h5 W56
  Q% F( o' Y! ?! w$ [; r5 p0 X# \57
! L" o7 u. D  W# [. w# t: g. A- b2 o58
, |) n3 M  {3 _" A4 ~59
60
61
62
: ]& ?: ~5 U* e" v2 f1 {7 h$ B2 p63

& W6 T# v% G3 ]7 l& E) q
. A; u9 w/ ?, l0 l- [不愧我们费这么大劲优化快排，多帅哦！

差一个归并排序，后续补上！
+ N6 L; O% K, l- `) w
不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
————————————————
版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
: F  d) z; c! T9 y& C; t( r原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832
& s5 a7 y- a$ B- R: e0 A
3 V* f- h0 q6 t# N: S- P  G