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

杨利霞

【数据结构初阶-排序】经典的排序算法，很有趣，有没有你不会的呢
% G4 W* j6 H9 G) @
9 E: B" ^2 g/ m) I6 _% l2 O2 Z8 V$ [前言
本期分享经典排序：
" S4 E1 d: y7 @1 A" u! ?' G/ P- ^
插入排序
直接插入排序
希尔排序
* v% F- o7 A) F7 M选择排序
* q3 t) ]0 ?/ g5 W+ F直接选择排序
9 W: C$ H% u! l% l堆排序
交换排序
0 s. W& w5 _( v- x2 o* a; k冒泡排序
7 \  e( q+ y! b: d" T快速排序
注：讲解时默认排升序

插入排序
5 m6 w* e# d5 @# [: ~直接插入排序
. B! D8 x- l0 |# x8 e. }思想
插入排序，就像玩扑克时，摸牌的过程：

5 _: J- `* Q( M$ t8 |+ |! ~最开始，左手没牌，右手从牌堆中摸
' _6 P$ Q# J, h: i右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
如此一来就能保证左手的排始终有序，摸完牌后也就排序完成


操作
* m* {' K. {: @6 ?1 G3 B- T1 ?设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
% ~9 b, \3 Y0 O单趟排序：
每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
是正确位置：插入
* `" p4 M8 d2 l( \: n不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
: F: p& @) O* A# O& g* T. o6 U( T& Z整体趟数：
若元素个数为n，需要排n趟
void InsertSort(int* arr, int sz)
{
) \+ l7 i% Q% q* z  T' j3 i        //end + 1 < sz
        //end < sz - 1
4 q, |9 I. J" z3 Y2 S1 f        int i = 0;
        for (i = 0; i < sz - 1; i++)
9 Y/ Y, y5 \% y" v6 [- X2 \        {
                int end = i;
                int tmp = arr[end + 1];
% Z4 I1 H. Z$ C4 ?9 I+ o2 G% `
$ L* W8 Z# C4 l! e9 o- ^                //找插入位置
                while (end >= 0)
& y2 Y/ ?% ?& z/ b9 a8 t                {
                        //不是插入位置：当前数据往后挪
: ]2 Z/ J' ]! H; H2 Z                        if (tmp < arr[end])
                        {
                                arr[end + 1] = arr[end];
                                end--;
                        }
                        //是插入位置：跳出循环插入
                        else
                        {
2 F) [. A+ y/ X9 ]1 c- i6 `* _4 }                                break;
                        }
* m: M  s3 |* h                }
                //插入
% m" z% Y. ?& _) M4 }8 C1 r                //1. 插入位置是[0]，end == -1，不合循环条件跳出
                //2. 找到插入位置，break跳出
                arr[end + 1] = tmp;
4 k: D; Z5 w# m  `6 ^        }
" ^, e! l4 t8 g* ~/ o+ K}

6 m. R) m) T9 x# a1
- E  V) M2 Z0 O. Y# f1 M8 F2
, D3 |: O0 I: [3
4
5
6
7
8
; g3 s1 x/ v5 v9
10
; r0 l) H! ]! a, l: |11
12
13
6 W+ j- t; z- s/ K14
15
* T7 W6 l8 G2 G, [. x! r/ c$ E16
17
18
- A0 C: i/ X2 q19
20
# i, s# V) Z; S( w, t$ A21
+ Z: `  w" f9 N22
/ x; G" V, @. g3 }( j23
/ j- `' m3 f! M/ W' c+ R5 e) ^. E24
$ P& j7 S2 o1 J& C: k  [* k25
26
4 `7 P  i5 F8 [+ Z2 E* ~27
1 y& L2 O) S2 P) X; L$ [7 o28
' c1 M. Q/ V3 r) P29
9 R. v% R5 @: H5 c; m4 X+ C30
31
, m' }' h, S: X* R8 A
& c0 F2 T; ?: k4 r
稳定性
1 o% Q! d- z1 w; ~. d* I8 M插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以
* F6 P. Z5 c9 w4 }' U
% P4 W; Y" F- O" J6 X) |; \, M7 a直接插入排序是稳定的

复杂度
! ?7 Q, G. C* n1 f& H7 a时间复杂度
8 q8 T# ^; i& K0 S+ e最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）

O(n)

4 M/ m, f, Q& `3 j& c" I最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2
) u- V* E& f+ L2 Z6 X2 w# ?+ P
O(n^2)
, Y% A* M& ~) J/ ^
& b- L6 C" g6 _7 W& {: `& {空间复杂度
O(1)

. ^) K3 b6 H6 u) U7 L: D希尔排序（缩小增量排序）
9 a- u1 x: P$ I. ?希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序

! Q/ ^* I" h8 }3 G- W" c7 ^优化思想
增量gap不止用来分组，也意味着数据移动的步长，所以

gap很大时，序列很无序，插入排序的元素少，移动快
1 P8 Q" P, p! W3 B! Sgap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高
+ o# F0 D! {" x1 J

0 b5 M# b9 I! V( z: f4 M, @操作
9 t2 A1 N3 I! `1 [8 S8 j单趟排序：

设定一个不断减小的增量gap，也是元素移动的步长
以gap对序列分组，并对每组分好的序列进行直接插入排序
( r4 X& u3 f) r- V! L: O8 {; q9 {. j不断缩小gap，并排序
*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
整体趟数：
- s* I/ \* r4 v* s0 x+ f
1 t  ~# J/ E+ U7 T/ M4 s7 O! B; d1 X由gap决定：当gap = 1，排序完成
注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。
* P0 n4 @9 ?+ d8 ]7 }- Z3 I
void ShellSort(int* arr, int sz)
& p; l9 H! o% m{
' R2 Q2 o' J* U        int gap = sz;
       
' D2 i% i" v8 P    //gap > 1，预处理排序
    //gap == 1，直接插入排序
0 ]8 Z' h6 f5 i6 D        while (gap > 1)
2 ]" V5 i2 d- i% L# k) l        {
                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
                //gap组
, X, p6 q: U* {3 G$ o+ l5 Q8 e+ x' H$ Y( E                for (int j = 0; j < gap; j++)
1 B3 [; h# l2 g" M& g- I/ J  [                {
" `6 q, d% h( j( e, s. i3 C            //end + gap < sz
  k1 \& ?# f& E9 V" ?6 f( d                        //end < sz - gap
/ G. M0 y& D9 J+ W! q6 c& ]" R                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
  C0 u: i! `& d) i" L7 D                        {
+ q2 X' t; @) i' Q                                int end = i;
                                int tmp = arr[end + gap];
. s! ]: c$ @! B% A% z! X3 g* O                                while (end >= 0)
                                {
) d9 e9 ?6 l) D6 N  ?! V                                        if (tmp < arr[end])
                                        {
                                                arr[end + gap] = arr[end];
+ B, l* q- K  x( A1 i8 `                                                end -= gap;
5 X" S! n4 v7 C4 i5 b                                        }
: j. K  F: G! {8 L                                        else
                                        {
                                                break;
4 G" |! o0 S+ R% C! p  [. @                                        }
                                }
                                arr[end + gap] = tmp;
                        }
                }
        }
}
$ @2 M  T/ o' G! k
' Q% o* O) ^* l! {' v" e- X: y" H1
2
: P% V  I5 W2 j& K" P3
) N" K# ~# |  v$ I6 d4
5
6
' ?9 v, Z1 c: J# S7
( f4 z7 s& U7 E' `0 H' u8
8 n3 R( w) x; I2 Q9
10
11
12
13
( o" A+ q+ `+ Z, b7 T; c14
15
16
17
2 D& N  k) y1 U& G, ~18
4 ~% j9 L* q2 r, d9 X' C5 L19
9 Y# _& D4 ^: K4 p% b' i20
: P$ R. R0 w# {8 s4 W) p21
22
5 E( c# @3 R9 o. V1 [23
! w  A' }6 h1 T* h9 x2 X24
" G6 ^$ _5 G3 t% H* f/ ]2 |25
& r8 Q# x6 z- u/ A. \  E5 X26
3 ^, p7 V2 ?: w' Z* T& C1 E27
% B, Z' n( k* W/ ]" t" E! L28
29
30
, N; j- ~+ T! ?9 L; j# n. Z1 y31
32
33
34
1 Q0 m, p) }! r( l+ S35
) {9 r  i  K# J0 z! x其实就是套上”缩小增量“的直接插入排序
3 A1 p% c9 m/ H, i& d

稳定性
我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以

希尔排序是不稳定的
2 x) i- ]! H3 v1 s
复杂度
时间复杂度
% T; v# u$ z# B% g6 q9 ^希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
% V, c+ }4 M: x1 A. G
O(n^1.3)
+ ]8 A/ `- _- n
空间复杂度
O(1)

" q. _8 l# x/ x! w5 h0 a+ t选择排序
9 s1 G& P* V& w  w$ u+ N直接选择排序
思想
# {( O3 @! x4 {选择排序，遍历序列，选出最小的元素，交换到左边

5 V$ x" l3 Z* t- n- X4 O* O

, A2 h' |* f7 x; d4 b9 U1 s) O优化版本：

% j$ f4 R9 w% k$ \# c! H  R' o6 }每次选出最小元素交换到左边，选出最大元素交换到右边
1 t" Z( k4 V0 T; U
8 |+ S* v, V# n8 {操作
设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]

. U& e0 M3 M! F设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标
( ^& }$ W7 Z: F
2 J2 n3 T6 x3 Y单趟排序：
0 w6 X  t5 F4 _$ h# Q4 I
1 K; P: Q( ?0 k% I* x遍历选最值的下标
* {8 Y9 f) G2 y' f交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
（修正）
整体趟数
/ a+ _  o8 I* ^" c; W
若元素个数为n，趟数为 (2/n)
$ H/ s3 q/ s( C# v3 L$ ^' J修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标

void SelectSort(int* arr, int sz)
{
        //闭区间: [begin, end]
$ T- r/ u9 W& |, J! B1 j. k        int begin = 0;
% \  U( t; T# f8 U        int end = sz - 1;
        while (begin < end)//begin == end 最后一个数，天然有序
) E+ e+ p3 D( p6 v8 \        {
                int mini = begin, maxi = begin;
                int i = 0;
                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
                {
                        if (arr > arr[maxi])
3 X8 |. u% H+ @                                maxi = i;
                        if (arr < arr[mini])
  ?2 v2 {& A) I1 l* Y                                mini = i;
8 C8 a+ h/ Y8 G9 P. t                }
/ \! d. X# p7 }$ D- U: @
                Swap(&arr[mini], &arr[begin]);

5 E5 o9 g  `$ G+ X                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
                if (maxi == begin)
5 J+ A& m- g. G% n                        maxi = mini;
                Swap(&arr[maxi], &arr[end]);
8 q* ~2 A+ F- p+ i& H7 B4 ^$ C
, _9 y; G+ c5 q6 A                begin++;
. b) I( v% M0 U! O6 z( [                end--;
        }
}
1 d  }4 h* |( U: K; ^
1
  u0 y+ \7 a0 V7 c7 d1 j: h2
3 g) J  j( o$ Y; B# o' X3
7 ^  O8 e5 y8 U* Y/ }3 ~2 E4
" x% D- G. {! ^; d5
6 u* d: S0 k9 k4 E" r, h7 [6
" p2 s( @: ^, ^/ R2 p. X+ A7
/ T. L% ^& x" q1 b1 K8
) G; M7 z, A; I$ U! N5 M9
10
! `1 ^' i. B% t! [7 u( u1 p11
12
" n$ |0 Y3 [: l13
1 |1 A6 p6 Y6 }, x; A0 P0 C9 t0 Z14
. Q) G/ s2 q0 J. h: i9 j15
16
17
18
. g, T9 r6 s+ R8 `6 ^19
20
; a& Q" F) H) a21
. H/ b7 I+ S; _) d- {0 }22
/ w' d$ M& Y% [* {! I23
* ^+ p# G  H+ M0 k+ B24
25
; H1 q) H9 N1 ?5 m26
27
( I9 N2 U  O  h& p" s. t* r' F. c28
5 L7 O+ \1 L. y8 r

3 t# K, b0 F1 F# v稳定性
选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以
4 N. o! E  K/ B% {7 E: t
选择排序是不稳定的
/ e4 f' I- R$ m% Y3 d
" s- n1 B: X  i$ M复杂度
/ p& C0 Y9 B: U) z3 O- P$ u! ?时间复杂度
最好：

比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2
7 @3 U  l# X* T3 D2 m9 [" g3 S
0 X7 k1 @4 A; }交换次数：O(1)，有序不用交换

' [% V# C4 c  ^3 T% hO(n^2)
1 }% W! a, Y- E2 k% K6 A/ p
最坏：
7 Q" P/ F% p. B- e1 o" F
比较次数：O(n^2)

交换次数：O(n)

O(n^2)

0 ^! Z. \. H4 `空间复杂度
O(1)
1 u8 T. m' ]2 x& u3 Y# D
堆排序
思想
, |' _6 p3 Y( K" \$ g利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆

4 ]: [8 H' `  E6 r" t2 q$ @
- O& B' l! ^/ L
操作
建大堆
' o6 A* ]9 p5 B1 D; o3 I( x  Q" f单趟排序：
) x; ^9 R& R/ z* j& u选堆顶和堆尾的元素交换，则堆尾的元素排好
每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
: c# p. o# r. d7 a' {' c3 D; {整体趟数：
% s$ r+ ]9 s8 M若元素个数为n，则排n趟
+ _& |% I; w8 o) F9 ^& M/ W1 _0 P  Jvoid Swap(int* e1, int* e2)
{
        assert(e1 && e2);
# i0 v* v& M" i5 b
7 s5 T7 T/ V4 O# Z& }' g5 E+ s        int tmp = *e1;
        *e1 = *e2;
1 d& j/ H- [( V  Q6 n        *e2 = tmp;
}
9 J& u0 L- C! _; B
' O9 J, `3 a& N. \$ e" R& T$ K4 x: \void AdjustDown(int* arr, int sz, int parent)
{
/ {3 O6 B/ Y% |7 S* t        //建大堆，排升序
        assert(arr);
$ U3 s# [2 G- k$ C. ?, u       
    //默认大孩子是左孩子
        int theChild = parent * 2 + 1;
' z- O: ~, ^0 o' Q3 z        while (theChild < sz)
        {
        //如果大孩子是右孩子则修正
                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
                {
                        theChild++;
                }
                if (arr[theChild] > arr[parent])
                {
; i, C$ u& v# U6 {& s* H                        Swap(&arr[parent], &arr[theChild]);
0 I; X6 Z7 R+ b+ T( I. ~. b4 M( l            //迭代往下走
! p- M! O& x* E6 ?                        parent = theChild;
                        theChild = parent * 2 + 1;
                }
- p5 h5 o7 Z+ f+ d5 E- ~                else
                {
$ A! ~. Z& w$ ~0 ^  u7 l% @                        break;
                }
' s; e+ d+ s: w9 x        }
}

void HeapSort(int* arr, int sz)
{
) j  m" E% I2 Y        //1.建大堆
        int i = 0;
! ]8 e+ u# s. v        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
9 x$ l  R5 {' J$ r+ }5 M. t( d8 m- J# n        {
0 |/ i  E, x' Z2 q( f, j. X: W                AdjustDown(arr, sz, i);
8 \& H, I$ N2 ?4 b9 P        }
& D; Q+ S) W% J* q/ m
        //2. 选数
        i = 1;
" g5 `1 M' G* B( G8 X        while (i < sz)
' _3 i# _8 ?& B0 q. K* C/ s        {
                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
1 j, S- }( |! O# i. T, M' P, L                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
                i++;
" h6 G' T) R/ |. b1 L  x6 ?        }
& e0 j6 {7 P( v/ o7 h: S- k}
8 p, Y5 f3 O7 E6 ?
1
: }7 @8 b5 n* U! q- u2
% Z  P$ |1 R* C) E* K0 Z9 ^) b3
4
0 h7 e+ d4 N) t7 Y! m3 Q# P5
6
2 }/ S5 x- ]' H4 O: k7
8
9
) l0 Z; E" K. r9 g& x. H4 u* j10
11
12
13
3 R+ X; o* W+ |( Q$ F+ J# Y, u14
15
16
17
/ M, k  p4 w8 `% B  ?. i# M3 I$ b18
19
20
21
9 z( m% }- d4 z2 r22
8 x: b3 J% ^5 v' a! u23
24
2 r- j' R) J; J. B7 P25
26
27
28
  p0 I- ~  \7 h5 i2 j& M( h+ c29
' I. W+ g$ m, f' w* N. W" g0 ?30
31
32
33
- l7 U- ?9 N0 `" F34
! [( N5 s$ W# t8 j35
36
& J5 z2 c4 U2 |4 c9 c5 h# [2 p% I37
1 E* E1 {6 k& i& w7 f38
39
40
41
  O) |1 l8 Y# n3 K7 O42
43
/ g. D4 c+ A' P/ t1 O44
45
8 r: m2 q) q) Y& q8 i46
" j- H/ B  {$ ^. ]" C6 ]47
48
49
50
51
52
53
54
55

8 d% {7 @/ y0 y; l0 c4 ?
8 @+ U4 E# B" h' }) {) i( U: g稳定性
; e1 m/ v8 ?4 l; W- B% H建堆和向下调整都会打乱元素顺序，所以

  _5 n4 d. v# M3 z; P9 ^2 P堆排序是不稳定的
# X9 V: t/ h/ f; N- Q6 [& |; v
复杂度
' Y' I3 z+ [; S1 e7 n: q时间复杂度
* R/ ~. [  P. e8 `- z8 M* [5 g( z单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为

. l$ n/ b5 a* uO(n*logn)
$ \1 B; H2 o, t$ M/ E" C9 I
, Z+ {( k/ y0 y空间复杂度
原地建堆
) p( X! l( @( |6 [/ e4 p, ]
O(1)
1 b- {7 O4 I5 ~/ \( m
5 O3 a4 h5 a7 g" d2 ~/ m. c交换排序
4 R/ `4 L* B" K4 d' J) L冒泡排序
思想
冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素
  i9 s5 b, k* J: {
$ [# e) w! W+ R6 ?  Q' s

操作
单趟排序：
% h+ W- U! g  v0 q+ k% P每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
每趟排好一个元素，所以需要排序的元素每次减少一个
" t# e" F; |% z8 I# t# {  E整体趟数
若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
; L6 f* D9 Z2 A5 b8 Z: \- m1 hvoid BubbleSort(int* arr, int sz)
1 A2 u. b# G9 P/ p3 H/ G5 f7 H{
        int i = 0;
0 c1 ]1 F; r1 F" N* p        int j = 0;
9 y5 u" m2 C7 C- i5 G        for (j = 0; j < sz - 1; j++)
        {
                for (i = 0; i < sz - j - 1; i++)
                {
8 E4 u$ ]/ q- `                        if (arr > arr[i + 1])
                        {
4 ~# @8 t3 B9 g1 U8 C- J                                Swap(&arr, &arr[i + 1]);
0 u) G0 U1 x2 G& v3 r- K6 Y% |6 {2 r                                flag = 0;
                        }
                }
& `& m# E) w- t6 L$ X9 @1 {        }
1 S1 e; F- u& ?! |}

1
2
8 h6 k) \; W- y% R8 ^! Z1 G3 C4 k3
- f: R' [4 R3 @, R1 O; I4 C6 Y4
: ~, K+ g4 [( g; {5
! M  k2 u# E2 F# i9 T6
7
8
9
$ |* N& L& D6 c10
: W  A, ~) Y" Q11
12
13
14
7 ]( n8 M3 |" ~* r15
1 r$ g# Y! j& G# n4 R6 }16
- U* ?3 _% K% v0 A! \优化
( P* D4 D1 e2 X0 a8 @5 g* B当遍历一遍发现序列有序，直接跳出

void BubbleSort(int* arr, int sz)
/ M% g' z# G0 N  x8 s& J( W# ]; z, |{
. L" e/ }" G# c2 Q        int i = 0;
. [- Z1 e  |% ^* T7 ^3 E        int j = 0;
5 \! y7 z" I0 H, A3 o        for (j = 0; j < sz - 1; j++)
        {
                int flag = 1;
                for (i = 0; i < sz - j - 1; i++)
                {
  [/ e& T% b9 n3 p                        if (arr > arr[i + 1])
                        {
                                Swap(&arr, &arr[i + 1]);
                                flag = 0;//不是有序就置0
                        }
                }
" E5 J0 |7 i7 P                if (flag)//如果一趟下来还是1代表有序
& m4 r# ^& g$ G) Y1 F                        break;
6 a2 Z8 y7 s# A9 V  {! |5 I        }
4 N2 C. `+ T5 T6 ?}

2 K: y; o; C2 T. J8 g9 C1
, n3 u+ @) X. @0 G6 n9 [- [2 [2
3
9 l6 w6 h. J7 h. R+ ?, |7 i4
3 @- D, W3 g$ A( F, A* K2 h, g5
6
7
8
9
1 M6 S5 ^0 W+ `& @! T* p1 o" ]/ w10
11
1 N5 j& F# u8 u1 ~% a12
6 O/ Q5 j! A8 y2 v9 H6 h) @13
& x( Q8 ~+ X' V14
15
# R3 N3 {$ l+ m' U$ f7 `: e16
17
  ^: U  M/ |, w18
8 H; L4 G8 N! ^2 t7 ?6 ~19

1 ?4 C9 A6 `+ m6 E& C
/ x$ b* W: m6 j. E  y5 z0 X稳定性
! }. Q: t4 L' o% u5 I相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以

冒泡排序是稳定的

8 w0 P* f/ P& \! a( o, Y复杂度
时间复杂度
最好： 当序列有序

未优化：

O(n)

' e) b8 _2 D  L: ^" @& l& C优化：
: J, |" A0 l8 p" P
O(1)
# r0 \: H& y% @' R' c
  i* X8 ?7 o' ~8 E+ t2 D最坏：要进行 n-1 趟排序，每趟交换 n-i 次

% I! b/ z$ E9 o& H3 qO(n^2)
% k2 z& p5 M5 n6 l* K
空间复杂度
- m- k6 t& }* cO(1)

" W7 ]+ D2 B2 b& N, W快速排序
思想
6 K: G3 X) T5 x1 q分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。

5 N* Z4 |' _, s; F所以快速排序可以用递归来实现

# E4 e& J6 T0 c- `+ p操作
9 C$ B6 Y' ]( _) T( c" y( Q: j8 E有三种单趟排序的方法：
0 S6 q- o9 F2 \* b
Hoare法
2 _  J+ d4 v& B4 Z6 V) q设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间

左下标 L = begin，右下标 R = end

设 L R 相遇位置为 meeti

, ]) O& q  G, e9 d9 H# Z& b" S​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”

​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“

选 键值的下标 keyi
% @9 b" x4 `" H/ {; o
左1位置作 keyi，则 R 先走
右1位置作 keyi，则 L 先走
& A; l7 X0 `% G7 {$ r1 N' @# jR找小，
! g, f: `, q2 N0 f, D( b# W
1 a& X* @- G0 F4 P; z) N找到则停
遇到L，则交换 arr[keyi] 和 arr[meeti]
- r" j3 E) |3 t6 h6 T6 kL找大
* x3 @- Q: E. b% F+ }
8 W, e; V% L; g& b找到则交换 arr[L] 和 arr[R]
! B' o3 r1 r) R" w遇到R，则交换 arr[keyi] 和 arr[meeti]

' k/ ^  X8 Z. S
解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
答案是肯定的：
! y/ ^0 T) W6 U& k/ m% n
/ A4 O2 ]! v, R$ J7 K
! ?% h* p6 v) U
8 _7 w; x) Y5 j  U* n  I
3 H# f4 j- _) z//[left, right]
4 D& y. i3 p9 ]( ?+ Z- iint PartSort(int* arr, int left, int right)
/ T9 \, G+ \9 G& t2 h$ W) i1 V{
3 S8 G" K$ Y( a4 {" j6 b9 R        int keyi = left;
0 O+ V9 o# s6 J! B3 S        //相遇则排好一趟
        while (left < right)
        {
1 S( M( S; u8 c+ k2 W8 ?( @                //R找小
/ E; |8 g* ]1 H4 n, r- R        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
2 Z& p0 C5 ~1 r  ?$ S- @9 F! s                while (left < right && arr[right] >= arr[keyi])
                {
                        right--;
! b  M# j, Q+ u+ L                }

7 {# X4 a. w7 G7 R4 n                //L找大
                while (left < right && arr[left] <= arr[keyi])
                {
                        left++;
2 @9 Z0 u: [: J( I# v                }
! z9 i( B: v2 ~. C7 ?/ O8 ~& L               
        //相遇就不交换了
% l3 l; k9 f/ U: ^                if (left < right)
* P! P& d' n! G7 m* l5 E! ~# c                        Swap(&arr[left], &arr[right]);
        }
- }( o( t0 n# s* O) W4 r
: Y# Y0 d! ^/ ~; a- \        int meeti = left;
4 R" L* Z# Z  y4 x4 h2 S
* Z) F$ n7 n3 P: D. p        Swap(&arr[keyi], &arr[meeti]);

2 Z+ ?* ~% J5 f( D& H$ B* \) @        return meeti;
}
" P% M1 y' ~7 }
+ P' b6 i. F4 S) L  j5 z, r2 S, J1
2
/ l2 }! b/ T' E3
4
6 H# n, j- Z5 _+ g0 [5
" P4 U+ J9 }8 _$ [) ~0 N( a2 _6
- [. |8 {0 w1 R7
2 B) l' C% Z' V1 U. g! ^3 o  c8
9
10
: i$ C1 B9 [3 L* D" F5 I11
12
13
14
/ g6 W5 A$ y6 t) o15
& [  }3 d% `/ O' c' I. R16
17
* P! D/ S* Z' X2 f18
. t8 b5 Y/ K! B& l: k3 C0 W19
1 |7 z) x& S; |7 v, q- f1 f1 D! v20
7 |) N$ a+ t1 O' k  f! F21
22
23
24
0 y) r# y+ A/ P5 m) W: `) R- O25
6 c* {2 }0 z( O! C26
27
6 G  m8 h# j3 C5 E! s# B. R28
29
& `& Q2 d& R. R4 H/ h( u30
31
32


( k! v4 |, ?1 n3 s( c9 w解惑：为什么key要选左1/右1，选中间不行吗？
& N( H% C) A/ `& k5 [- V) d

. Y& c: }9 C) |* Y- }# G$ r可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深
' `0 p% N# j( J* ^6 n


/ U/ G) C" C$ L: M
非常容易栈溢出，怎么解决？针对有序情况，优化选key
" h& |" B( A! g; {. c) U! C! U7 H( e
5 o3 t2 W' [& n- H- f6 r% g0 |优化选key
/ a, D+ M( M9 S- A% K$ f随机选 key （是一种办法，但是不那么彻底）
( ^4 L; M0 y) ~0 r3 e: \# `选中间位置作 key
, f2 Z' \: @9 G  Z% z0 u0 \0 m解惑：那先前实现的单趟排序不就失效了吗！
：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑
' d8 u, M" D  n9 W
# o5 v3 m9 J  h3 k8 ~解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
前辈给出三数取中的方法
: A$ a0 A6 ]" i0 r  Q: g1 k- p: j
三数取中
在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
" {1 [( l6 q7 g$ j" x9 X7 w- |+ [这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
# Z" D2 _& X' d& ]/ u" [- b优化选key后的Hoare单趟排序：
  X7 Y3 S7 n& Z' b! j
int GetMidIndex(int* arr, int left, int right)
{
, k9 Q6 C0 l* w7 ~: k/ |% h        int mid = left + (right - left) / 2;
3 R+ r, Q. S# M0 K# S//  int mid = rand()%(right - left) + left;//增加了一定随机性
: J5 k. j  k7 F3 ?4 d: W3 d- K- @        if (arr[left] < arr[mid])
        {
                if (arr[right] < arr[left])
                        mid = left;
                else if (arr[right] > arr[mid])
# Z, H; [: d+ [* e/ ?: X                        mid = mid;
                else
                        mid = right;
        }
        else//arr[left] > arr[mid]
$ }& L( w  Y' z        {
                if (arr[right] > arr[left])
: @7 w7 V8 K- y" g                        mid = left;
( e7 z+ a5 B# R' ]: z1 q" ^                else if (arr[mid] > arr[right])
0 W* E3 I6 I% H0 z: l6 A                        mid = mid;
/ h7 D8 T8 l1 i% m& D: u5 z                else
                        mid = right;
7 i0 G6 V# X* b+ ?2 j8 d6 v        }
        return mid;
, l/ p3 z6 g3 V) C; G% @}
! A2 T# Q# N/ ^* ?/ `8 G5 a# [
( D) l& L0 n- G1 l. tint PartSort_Hoare(int* arr, int left, int right)
- Y  |$ ]& h2 |) i2 R0 I: h+ ]. ~{
        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
: F- ]3 E- u6 z2 x        int mid = GetMidIndex(arr, left, right);
" N4 v5 ]: }# Z; A8 C
, b$ u/ k3 }5 z) o3 Z- p        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
7 [1 i6 Y9 S( B6 |% S8 x& o        Swap(&arr[mid], &arr[left]);
3 n0 h& e7 L( l1 r( L8 }/ V
        int keyi = left;
# G7 x/ @, a+ Y$ E        while (left < right)
: I7 _- U& A* ~        {
+ B8 X: G3 o8 x/ l7 r8 N# ?                //R找小
                while (left < right && arr[right] >= arr[keyi])
+ u! m. ]/ `6 [  t                        right--;
* i; R2 z- A: `4 x8 y! g0 e! q
0 T6 H3 X/ {9 E' c; O+ q& Q                //L找大
8 [8 u5 w( y" n* ?) C                while (left < right&& arr[left] <= arr[keyi])
  Q, S' D& k! o, |8 \- ^+ D; V& T& {                        left++;

                if (left < right)
                        Swap(&arr[left], &arr[right]);
+ H8 A* H3 p0 b' j7 c- y        }
8 S; u6 ?3 ~/ E0 H1 B' Z5 x, f
        int meeti = left;

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

# c$ X& _: \9 Q7 ]- P3 r1 k0 o        return meeti;
}
9 O+ s/ K) h5 {/ {: s1 X; L
1
; t) X% M: N6 ~$ f0 U, g  O- l, j  b2
* p. K' p0 k0 i, Z. k' `3
4
, e6 @9 o3 |* z" ]  B7 @5
9 c7 W2 _  B3 X6 `4 X6
7
8
7 F$ D. i0 ^$ e: k5 ?9
10
11
12
13
14
0 [' r5 s7 t# ?7 N, I4 t15
16
17
18
1 r  G: {8 E$ @( d3 o9 e! S1 Z3 L19
9 ?4 g3 g3 E( d' v9 p$ ?3 c- _20
21
& A) G( {, \- i% g6 W# v22
23
24
25
8 S8 \: |& a- k& J$ S26
, i( T5 t$ |" S, ^! X* j# J7 f( L27
28
: x6 l& U. t+ I# X3 k/ Q! D29
30
( z' f- k: G1 I6 }, `31
32
33
, d" B5 e8 f: h% t1 ?34
35
& n0 |3 d* C1 S36
37
38
- m; s5 J1 ^* u39
8 k1 [% L0 R( ^+ l0 j40
% v( K3 q' g) M" L41
, X, [  s; ~$ n% p42
43
& q3 e+ w7 G" F& ~2 z( Q44
45
* T7 K+ a5 U1 I* |; o8 s46
5 W8 u: N/ P2 L7 u. w* d' r& Q47
, B- |! H% u& A) J48
49
50
51
3 ]) W) Y" S9 y" g1 [( J+ H52
53
5 R$ [% z3 N( i54
挖坑法
- A# c# {5 B  F% Y- m* b初始状态：L作坑，其下标存为key
2 n3 ~5 o4 @3 u6 E(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
重复 (1) (2)
  O1 C3 |; X: c- s) R. k最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]

5 _6 D$ ~% R9 K/ y  \7 K5 `; W
int PartSort_Hole(int* arr, int left, int right)
* G: \" y5 C' X6 Z0 |{
  A* [7 Q% g# e$ U% j) H        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);

        int key = arr[left];
        //L作坑
  X1 x  d, z+ k        int hole = left;
# r; v! H+ d6 X- K/ G; k- [0 X        while (left < right)
" W( s( W6 E2 k4 b        {
) H' q. j% @( U0 Z) S; I                //R找小，扔进坑，R作坑
                while (left < right && arr[right] >= key)
                        right--;
                arr[hole] = arr[right];
                hole = right;
/ c* O; w- i2 G/ ?
                //L找大，扔进坑，L作坑
2 ~" _1 ?' a( K6 i                while (left < right && arr[left] <= key)
                        left++;
/ s$ v- }2 O8 X1 b                arr[hole] = arr[left];
                hole = left;
        }
        //meet
        int meeti = hole;
        arr[meeti] = key;
4 }# S& A4 ~- z' G( P3 d; ]
        return meeti;
0 T& B! l/ |: h. P' U}
6 Y8 U& m: p9 j. f* X* v
  ]7 O; H% a+ }# G  ~, X6 I4 z) e4 y1
4 c* [2 k- `7 M" J8 H/ w( M2
$ ~8 I: c/ n0 Y6 h6 m% V3
% J) J8 C$ o1 w+ Z. d4
' J- n& V" b6 l5
6
7
8
# b" M# F& J. ?" G& o9
10
# d+ e4 t, o; M# q. O7 i11
12
13
14
15
16
17
18
8 _1 N$ z0 k+ ?7 ~4 r2 g7 Q19
20
21
22
23
/ w$ j- G: @# L3 [/ C- d24
% Y5 ?5 x# [0 i6 g, f% ~0 ?25
* T; R! \4 c* X2 F26
. E6 E& M. y3 _7 u$ ~27
1 }, L, H% D. [28
前后指针法
此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多
3 O% p+ r2 r4 P; y
/ M0 Q. g) F) ?: a9 f+ ?: z# e5 @cur找小，找到则停
7 m- r- s, R' }- e6 L++prev
9 q! I' x9 i0 p- J6 {如果 prev != cur，交换 arr[prev] 和 arr[cur]
如果 prev == cur，不交换
' P8 e7 X: `9 x1 F6 j7 p; X当cur越界，代表找完，排好序了
. Y0 M3 G3 a/ q. Q. uprev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低
: ^# S+ R" _5 N' Q! q
- O- T( Z# [% X0 K% H4 J- K# q7 ~) R

int PartSort3(int* arr, int left, int right)
6 S2 Q' ]5 w1 r, |2 n{
* {1 @( s6 Q  l+ G! y/ Q) v& a- f        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
( I# q, r; |: i; g: A       
  //int key = arr[left];
        int keyi = left;
* X. y* T& P9 x/ U! U) R0 N
2 z$ S0 c, ?0 i1 P! Z( e6 E9 {. H; K        int prev = left;
+ @/ A/ i" P* @2 G        int cur = prev + 1;
       
- E3 R0 ~) X8 s# S  _    //cur越界：找完小的，prev的左边全小，prev右边全大
% q% n' Q5 e' _$ u        while (cur <= right)
        {
' t$ F8 T+ L7 f4 i( Q        //++prev == cur 没必要交换
                if (arr[cur] < arr[keyi] && ++prev != cur)               
7 Q. Q' ^; @" W% h2 T! J+ X. o2 _0 m                        Swap(&arr[prev], &arr[cur]);

                cur++;
        }

        //键值存是的值：
        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
        //Swap(&arr[prev], &arr[left]);//这才对
3 w0 d4 L6 Q* Y( I# s    //键值存的是下标：
* z+ @/ c2 j% O2 `& G        Swap(&arr[prev], &arr[keyi]);
1 V/ K; \* H4 X7 c* l5 `# {
        return prev;
9 h) r; ?; H! S9 F6 j}

4 g  K% R  Y/ |) i, `9 w& ^1
; e/ d1 Q& o9 P, L7 |2
; M" m! p" x  w1 m: ^* P7 e6 f3
4
/ ^& |; _9 [/ B7 Q5
8 e; [2 O. E9 U/ |6
7
3 @. z9 v. J" I/ W& S1 K8
9
10
: i% Q0 Y$ K1 ^% r4 C11
12
13
14
15
16
17
! W& O+ M) Q, X  B7 K" j0 Y; E) D. x$ O; U18
2 B6 I6 m7 b6 |4 b19
2 @2 U  y& S6 V8 Z, W& O" j20
, L- S$ k8 Y7 d4 F21
22
1 s7 r9 r- g# N6 p/ k$ g+ D23
2 V$ a$ @9 Z0 r6 n3 l+ v24
3 U: [  u* S" y7 N, ]+ f25
; h1 B6 |( Z# H- D/ Q26
27
28
29
7 z2 ~$ Z& ^' H* R" s2 g+ N整体排序
递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

- C9 j: }0 b# k. b9 h//[begin, end]
. P, D% f( w/ ivoid QuickSort(int* arr, int begin, int end)
% Z0 ]7 E2 r8 S2 W* _{
  B# v* y9 ]8 \0 s/ z        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
        // [begin, meeti-1] - meeti - [meeti+1, end]
                //1.begin > end:超出范围
" q8 r! S1 K6 f7 e$ Q                //2.begin == end:一个数天然有序
. r( |4 C" Q) @, d* F    if(begin >= end)
  D# r$ r& F( f1 T, n2 f: v2 `        return;
+ c  L1 A: {+ ?+ r$ c# Y& j' B
4 h+ {# g5 c9 z6 K* m7 e& m                //排好meeti
                int meeti = PartSort3(arr, begin, end);

                //排好左右子区间
# w$ g, [7 `! Y/ b+ O- O                QuickSort(arr, begin, meeti - 1);
; Q/ \+ m* f# H2 H5 R  i3 k  v+ q                QuickSort(arr, meeti + 1, end);
) C0 n' k# c8 I) f3 W$ w1 T        }
: i8 L( y5 w8 x}
+ j0 R, v0 e! K1 T: H0 F
1 C; X* X3 q# D3 n4 f- f! a- x9 [( U1
2 b- j" f7 \# d$ j; S2
3
4
( ]% Q" o. ?. x9 B3 l1 X5
6
5 Y1 E# u6 Z8 q5 C! U) T' G: q/ k7
: _% T" E- K6 o5 `) j6 N& U! {& a4 n5 J8
  Q! |( d/ T* S, X9
5 w. J+ W& B' U' j! E' [3 G10
$ M/ W; E  G! l* P# X11
5 n( j" L0 t4 Z12
13
14
15
: [; H3 {2 N0 v5 U. _& x* C16
% {) r& d0 F1 @/ G5 ~3 P17
18
2 h0 x  N+ j. E, C2 j2 d% h8 x…

没想到吧，还还还还有可以优化的地方！
6 U$ X! v$ o: X4 Z
优化小区间

6 d5 A: F1 ?3 O
如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序

: I$ S4 s; C. `/ F( R那什么算是小区间？
% u- _: C4 R+ N2 p3 U/ l4 Z6 T
其实小区间没有确切标准，8-15左右都可以的


这里就把小区间定义为 含有 8个数或以内 的区间
2 f( K5 D4 v. U! q
4 `- h4 \/ {; J7 X' e5 b//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
        if (begin >= end)
                return;

        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
        {
                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
$ }" s% w4 r/ L                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
% @' g1 Z. }! k; I        }
        else
        {
                int meeti = PartSort3(arr, begin, end);
9 b" l! h' e8 c- ~$ p4 P4 C! Z
. |! C7 \, }6 I3 q                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
        }
}

1
2
$ R5 @( v( T8 z! e8 Y: v3
4
6 d9 o3 }0 Z8 x% l% j, S* O! O* e5
3 y/ e2 f$ T; \& T3 w! ?6
7
$ I+ J7 V+ c2 s. Q# H9 R# i0 {- {& d8
9
10
2 X: u. F& g+ o9 t% p5 M1 g! I11
) a& L6 q8 X4 a6 m* A9 M+ C12
13
14
15
16
17
18
19
6 h* g( ]" {2 f" ?快速排序非递归
为了解决彻底递归深度深的痛点，我们来试着把它改成非递归
# L" U+ _; q# i- q% w
思路：
递归深度深，栈的空间又小，会栈溢出…
0 y$ o" f' [( H- N" k5 f
0 u1 q5 `8 I/ ]; R5 U+ f9 X那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！
6 u# K4 o$ Z9 X1 y$ O8 J
核心思路：在堆上创建“栈帧”

) D9 w/ t8 T6 W  }5 R7 P快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的
! f2 B: z1 }7 ]9 ^% z! O1 D' b& \, P


0 d2 D) \) R3 f4 Y+ z/ a1 f在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：
2 X/ m, E$ \7 s) X8 a% P8 o
先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
' i! v! E1 F6 {- e  L3 J先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
{
        ST st;
        StackInit(&st);
       
    //先入begin
$ u0 j! J. v/ [; @5 x5 ~5 i  P        StackPush(&st, begin);
    //后入end
        StackPush(&st, end);
0 ~) I" q% Y# V6 W2 E. P) E+ S6 M
2 ~8 z( t5 l6 ^% M* i. [        while (!StackEmpty(&st))
        {
7 _, u. }" F+ e* m! l                //先取end
                int right = StackTop(&st);
                StackPop(&st);
                //后取begin
                int left = StackTop(&st);
                StackPop(&st);

                if (left >= right)//1.只有一个值  2.区间非法
                        continue;  
! \/ a* h  M; q2 q/ `                               
4 j  l0 h) h) b/ O7 S* R                int keyi = PartSort_Pointer(arr, left, right);

* x6 j$ h: O- q8 M0 t                //先入右区间
4 Q& ^+ s5 \4 `' L2 l7 Q% z8 U& C                StackPush(&st, keyi + 1);
                StackPush(&st, right);
                //后入左区间
% t( O: R  c! r" y1 d' j: I. ^                StackPush(&st, left);
% x9 X7 x! W' V: B
                StackPush(&st, keyi - 1);
        }
% z& Q& b: Q7 E
/ H: p6 T+ U# k8 G* u; V7 S3 T        StackDestroy(&st);
}

1
3 B" A( F& a+ @2
: @* k% p* v4 W" T5 U4 D( c2 h3
6 s- D9 w( K5 [5 m- [4
5
) s4 [2 M: L& _7 ?! k+ z1 j; f6
' e; }, a) Q& o' m" }7
8
  U* p9 v, ^0 e7 b. Q9
. ?# n+ j5 d% v2 w/ U10
) B, u& @3 b( [6 W  c' ?11
, E5 R' O. C" g12
& c7 u  b& N. S. {! F3 y5 Q. T13
14
15
16
+ Y" l* l4 ^: \& [! n5 r) L( T17
18
! p9 s: a1 R$ A4 S/ l/ a19
20
: [# a  _5 }+ i, k* X" m21
3 w  s/ d7 s9 v* ~" ]! a4 y22
23
24
25
# k: }# Q8 q4 H9 b3 \( Q/ K5 _26
27
: N- }2 S: }$ \; a. S: s" s) `$ i28
8 ~5 e6 C& q$ r7 a29
! b  w% [1 n6 X, y6 I30
- ]) ?0 P* i( W4 T1 K9 q31
32
33
34
- ?* x$ x; Q" x; Z3 X  N$ ?+ v" x: ?( H35
数据结构栈的实现可以看博主之前发的博客
$ v- _, i) ?& o" Z) l6 X

1 f& j5 H" c. ~  f2 E归并排序
5 h( ?) \* O; I5 M
…

9 g+ T1 ~) T6 @) B- }4 I性能测试
! M& @4 K% a, o' i" G# C$ |! J* \void TestOP()
9 Y5 o1 X' M& J. t, A. B{
        srand(time(0));
0 S7 H: P8 p5 H( S% I) x6 ^6 x        const int N = 100000;
4 s4 _# E7 N/ i        int* a1 = (int*)malloc(sizeof(int) * N);
5 s6 {* c! a4 j7 K+ z        assert(a1);
        int* a2 = (int*)malloc(sizeof(int) * N);
" q) L. Q3 ^5 i6 r* Y% M        assert(a2);
4 B4 n  Q% q  S9 q        int* a3 = (int*)malloc(sizeof(int) * N);
0 J5 P0 f+ Y1 t        assert(a3);
! a" g/ `7 `2 P/ o        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
4 g8 P+ N* q, J1 j9 `8 U1 A- f2 [8 q, E        int* a5 = (int*)malloc(sizeof(int) * N);
4 o( H# ^4 F2 M        assert(a5);
: I: p7 R  \0 V6 M( [
        for (int i = 0; i < N; ++i)
        {
$ e0 `; j% i. r, @! ]                a1 = rand();
                a2 = a1;
2 e* A* o( v! P: f5 w) Y                a3 = a1;
                a4 = a1;
                a5 = a1;
  K' g5 h' C+ B7 c8 C. O        }
, ~0 b% x$ g. i3 r5 \
        int begin1 = clock();
        InsertSort(a1, N);
0 n) m* v* y" l        int end1 = clock();
& m9 Y" j- ?3 B: r$ V; _4 ?9 K' k
        int begin2 = clock();
1 ^. R6 y3 z& h        ShellSort(a2, N);
        int end2 = clock();
3 \8 B& I& p" l: Y0 M
3 y: Q! V  ^/ T3 R* }! Z6 \        int begin3 = clock();
        SelectSort(a3, N);
  G. k, A+ L2 R2 [  R9 D        int end3 = clock();

6 _( a& X4 }3 \% I; Y4 {+ L8 \        int begin4 = clock();
+ W7 h+ R0 R: R" n  w+ s& D" B" H        HeapSort(a4, N);
8 x. d" m/ ?9 X: {; v* Q" h        int end4 = clock();
( |+ m6 J4 Z* l% ^# T, y  H
        int begin5 = clock();
        QuickSort(a5, 0, N - 1);
# @" ?; y" v* k$ {4 C                //1.中间key
6 R7 ?0 C+ V- i7 d; ?) C3 ^                //QuickSort(a2, 0, N - 1);
$ a. N  y8 \' t" U: G                //2.三数取中
                //QuickSort(a2, 0, N - 1);
                //3.小区间优化
                //QuickSort(a2, 0, N - 1);
; @) ?- `  F7 {& p        int end5 = clock();
$ J( t& M6 {0 c- P$ x' U
: j( u- z5 d- f" Q1 p$ {
        printf("InsertSort:%d\n", end1 - begin1);
) d' J+ {) M- V% f: p4 H1 k, l        printf("ShellSort:%d\n", end2 - begin2);
        printf("SelectSort:%d\n", end3 - begin3);
) }' ~. p& I; {  q1 \        printf("HeapSort:%d\n", end4 - begin4);
$ ?/ A/ F% x% j. h+ p: b; i        printf("QuickSort:%d\n", end5 - begin5);
, _5 J9 a; ]$ u8 o8 O1 p) f2 t
        free(a1);
% f4 B# I( E: t        free(a2);
        free(a3);
, J# }( [2 O1 {$ P. x        free(a4);
        free(a5);
) r3 l0 V& m) V7 R; c# c/ J3 g+ m7 [/ [}

1
' C$ H, I1 A8 ^: T( p2
3
9 ~6 K4 K7 a4 G" d5 ~( X5 t  K4
9 V. A) J0 l  r5
+ _2 A, N: K9 _2 p6
7
8
/ {6 N! D4 l- Y( q6 m1 n! i9
10
" m( B2 A, ~8 N11
12
: d# |% {9 e) p$ ^7 {13
14
0 k( g# x- c0 r7 _! Y% m15
16
9 j! V% v; i5 Q; v9 W17
18
" k1 t8 I6 n' {, R19
20
5 B# U$ `( H, Z8 F, ~: d4 h21
8 @! `' G3 G' e4 X9 [22
23
24
7 Q# y9 _  Z, T( C& Y- E25
26
27
28
4 J8 r+ b* P" Q; s' s2 V29
30
31
32
* {2 z' l# z2 J8 w1 R2 U) o" X33
34
4 M% [/ r/ T' |& x' z) U" I$ S% c35
! f' N! c! ]8 _$ a( `8 E36
37
4 ~$ u# ^* c( ~5 [* F1 R4 W- O38
39
40
" Y' G5 _4 ^- E6 r' q41
$ r: Q, p! g0 {7 T% F1 X- u4 T42
  S, {8 _! y' {, b2 |; S! I# {+ X43
% `5 r* F  W& o  ]  e5 i44
% G; J8 l: ^- v! _* ]% h6 R; S45
46
; j! W7 o) l& b' c, w5 @/ _47
48
49
' b5 }6 y7 W" M, o" r# Q50
51
52
9 f( B) u% J: m53
54
, D( k$ W4 q" i# o( H55
56
6 b+ }! r2 w* g- ~8 f7 s57
5 Y: k& |- P6 p& O58
( g) W2 `; J; O* C) z, L+ v8 o4 M59
6 T% L- @, w4 M0 }8 y60
61
62
63

, _& g( p8 G/ S% F. Z) w
不愧我们费这么大劲优化快排，多帅哦！
, p& N4 ?8 A6 R3 W! p
差一个归并排序，后续补上！

不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
————————————————
版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 y4 p; f; ]2 s8 P9 [) J原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832


- J7 t) ?- Z$ l3 A  u, y