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

杨利霞

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

- Y& U! k' G% q( r前言
* w, m; r& p& g! S1 t$ E: W7 a8 @8 Q" }本期分享经典排序：

7 J6 a( g* k6 g0 V插入排序
直接插入排序
希尔排序
  k1 w9 p) t3 }3 @+ o+ J- z9 D% n8 Q选择排序
8 {4 }6 D, G# }8 @. i3 U" X; O直接选择排序
堆排序
, Z. y. X  V+ L& l: \交换排序
: M6 v* y2 b7 T冒泡排序
快速排序
注：讲解时默认排升序
5 O  s2 y" g+ z5 ]- i
插入排序
直接插入排序
思想
4 [7 A* c! b6 ^5 `. c插入排序，就像玩扑克时，摸牌的过程：
- r3 |! N: V5 W8 E
最开始，左手没牌，右手从牌堆中摸
右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
如此一来就能保证左手的排始终有序，摸完牌后也就排序完成
7 x/ u, E+ Q7 c+ n8 b, ]
1 h" B3 E- \. y. I8 c" u4 W% L
: s2 j9 U3 w  s* ~7 ?7 l操作
2 \* m) E; R2 F" ]7 B设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
单趟排序：
每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
是正确位置：插入
不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
% L7 @, g5 v; h2 o) X整体趟数：
若元素个数为n，需要排n趟
void InsertSort(int* arr, int sz)
{
2 c9 q/ U+ k. D& I* `: G0 p6 t5 Y        //end + 1 < sz
        //end < sz - 1
        int i = 0;
' j0 k3 [' @- `. D8 O# ^9 O7 |  a        for (i = 0; i < sz - 1; i++)
! }6 g& K3 B2 {, U# n        {
                int end = i;
& C  t  B/ x* n9 e( y                int tmp = arr[end + 1];

$ j3 {- R, T' [                //找插入位置
                while (end >= 0)
8 r5 o* f8 k, r  U                {
                        //不是插入位置：当前数据往后挪
$ G( T' z$ c/ o: b7 i                        if (tmp < arr[end])
% Z1 Y+ |$ @( U                        {
3 [) B1 B& w& S8 A                                arr[end + 1] = arr[end];
                                end--;
                        }
                        //是插入位置：跳出循环插入
                        else
  g3 j9 V6 W( [* G$ W                        {
                                break;
; s% C; ^- m( |                        }
                }
* w: ?5 ^! S3 E5 R" y                //插入
                //1. 插入位置是[0]，end == -1，不合循环条件跳出
8 D3 t- ?4 c: [) K8 X# S) X! x                //2. 找到插入位置，break跳出
                arr[end + 1] = tmp;
        }
: ^2 b/ B3 B: I- d) b}
* |1 A5 I& k9 ?+ u# p
! J# m; }/ z1 A) b# J* u1
3 d  |# P: Y5 ~* g; C: a2
0 Y5 i  s0 E4 M' @& W3
3 E* U8 @# o! l0 z1 s9 k4
7 x0 a: T- P$ H  e+ b5
( s6 s# \3 Z* u  k# ]/ ?. C6
7
8
9
- }+ Y1 O& i; @3 Q. y/ Y; }& ^7 Y10
. W+ k  K$ m- w- N1 T  p9 u  r11
12
13
14
! Y4 W$ N" J' g15
16
! W: ]  e1 ^. O, w! P. b17
18
19
20
; W) h# E9 j3 H# H21
& v# Q, s0 l5 a2 X) o22
* E& _$ {5 l3 T' i0 |* B" n23
! W0 e9 v3 U0 b% X8 q% I% d& d24
4 l4 D% k& q+ b+ F5 C25
' {* E5 S1 K% L. n26
27
% Q' a, x* S1 g28
: D" Z; C- r7 p, i8 G29
" I) C3 M6 V) l3 s- [) l8 S* N30
8 A" s- f* I: t, I31

0 H- J- f$ Q2 Z' Z4 c
稳定性
2 ]8 _7 X- b1 t9 |; Y3 w0 n- n0 g2 I& s插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以

! h7 q0 w2 Y0 M5 p5 k直接插入排序是稳定的

- E, E  z" }& O# {复杂度
时间复杂度
最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）

) T7 m8 d0 U) A8 qO(n)
6 ^* U  K& M4 j0 _/ Q* ^8 H
最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2
- f2 g1 L/ I4 c0 S( B/ n" a
O(n^2)

空间复杂度
6 T$ i" F( i; H1 F. dO(1)
/ v; Y" y. \. Q* H" |
2 F0 u4 T7 b, F' Y/ }$ d希尔排序（缩小增量排序）
1 G( Y# s9 o3 p* A- D9 y希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序
% J# d! k7 j7 `5 d# w/ Q  f+ S# `5 m
+ `2 m/ c7 h; l优化思想
# z: q- }# a$ b; r& ^- h9 O增量gap不止用来分组，也意味着数据移动的步长，所以
& n' ^: _4 H: x) m; _/ R2 _
5 P4 q, j8 r% s# F0 igap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高
* o! M" A& I/ ~
! P' m# c6 Q& I& [% b
6 w* b. ]0 O4 O/ R操作
% }1 P7 j$ B% r单趟排序：

设定一个不断减小的增量gap，也是元素移动的步长
' b/ ~8 q0 Y4 }4 c以gap对序列分组，并对每组分好的序列进行直接插入排序
  ^3 H" r; C" o$ G/ W! F不断缩小gap，并排序
*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
整体趟数：
0 M  M4 P' a$ Y+ ~% X
由gap决定：当gap = 1，排序完成
注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。

void ShellSort(int* arr, int sz)
{
- v- @2 X( ^& x" `/ s; @/ H  {& Z+ S        int gap = sz;
       
! }& x7 w5 j3 n: y2 s, n- `    //gap > 1，预处理排序
$ B; e% z0 g/ \, t$ C    //gap == 1，直接插入排序
# }  }9 [3 b3 ]: U  k; o1 t" M3 g% \        while (gap > 1)
$ n3 u( \% |: I; s+ X        {
4 f8 X7 G% _. o7 z- ]+ _% e                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
                //gap组
% ?2 c' j0 l# [# w) k                for (int j = 0; j < gap; j++)
                {
            //end + gap < sz
                        //end < sz - gap
. R  b2 D0 l  M. s: N# e3 F                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
3 m; ~1 f4 C& v1 h% b8 A                        {
                                int end = i;
                                int tmp = arr[end + gap];
: Y9 d; r/ \) ~) D" K% L; B                                while (end >= 0)
5 _2 V; \0 j  I- \! k                                {
- W, z* m' D/ Y/ g" W                                        if (tmp < arr[end])
* I: P; ~+ T9 C% x8 f& I* `                                        {
                                                arr[end + gap] = arr[end];
                                                end -= gap;
# L9 Z2 S+ `/ A8 p, k# o                                        }
+ q2 O( v* Z& I" f) N/ Q& i. F) ~                                        else
                                        {
) O/ a/ o" S% t- e- R% f0 `) ~$ F* w                                                break;
% _, ^) f5 O' K- p4 O( p                                        }
                                }
                                arr[end + gap] = tmp;
                        }
                }
% b" c) a8 s* A, G9 \4 i        }
}
; {2 T* Y6 D4 G8 V
& \4 x% y% n7 H) u+ `1
- y/ H( p' G3 ?2 x* c2
* P+ [. n- {8 ?( `& J3
4
: h- s2 u$ }* m' |- p5
5 q7 c1 S. p7 r; ^4 K6
: k6 e0 ]& n/ H3 O+ W" Y7
! N, d, L! Z  W% U8
9
10
# S2 c4 \( w0 d3 G- d& }11
12
13
" Q! R; k) C5 \4 Y$ v$ h& j  u( l14
15
16
17
: a& T0 H$ D+ s  L2 O8 I' l+ u) C18
19
20
21
; J% s9 l6 D$ k4 W9 a* K$ r22
23
) u, u5 S2 w! L" n* p24
6 u. `# _$ m5 ?8 \% U& n& w1 m2 F25
26
27
. q  K& x2 N" I$ c- h28
29
30
4 Z1 e' g. q* a: V6 [$ Q/ [  z" f31
$ A( F$ A" b; R3 ^9 n32
33
% l1 l7 Y- D' b6 K) m# e7 K% {34
35
1 z' m) T" J+ x% G. O4 g其实就是套上”缩小增量“的直接插入排序
0 i) Z& b, o6 d

稳定性
我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以
4 K/ I* v1 A2 A7 F1 }
希尔排序是不稳定的

: H# |6 X1 Y; Y$ D复杂度
7 j- r1 G! x8 B9 k时间复杂度
0 l( F% v1 `6 ~2 x5 ^8 \; p: h希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
* y" S/ W* I" J  x
: \' v* h1 G" cO(n^1.3)

空间复杂度
O(1)

选择排序
9 R6 t; k7 C2 p0 o' n直接选择排序
- I: F" v9 K6 y: _( M$ y- a1 [思想
选择排序，遍历序列，选出最小的元素，交换到左边
$ ^5 _5 A) S  l9 M/ g8 b/ ^" ]
9 M4 ?8 X% D4 C# k. a8 n* G% ]/ J
/ o/ [" v2 j( H4 g
- _! |6 F$ N" ?$ @7 C优化版本：
) g0 Z6 i" \( S4 k1 [
每次选出最小元素交换到左边，选出最大元素交换到右边

操作
设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]
. b$ ?% G( Z+ S, L( d
' J9 W2 \7 ]; s* J* s设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标

单趟排序：
9 }) p# Y- K+ z" W1 s
9 a% j7 v) v9 H% ?遍历选最值的下标
交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
# ?& l4 I1 H6 Q. F2 G2 _. h（修正）
: C- O1 R7 ^7 S- V6 h% e: I整体趟数

若元素个数为n，趟数为 (2/n)
7 |! Q# J  l* U% [+ d6 d3 c! \" Q) W修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标
# t( H% }  i: J6 [$ T1 k; u4 n
* U+ g& c% A6 b. X- `( [void SelectSort(int* arr, int sz)
6 ^+ R1 s3 a# U+ O: D% g+ L8 Z; c{
        //闭区间: [begin, end]
        int begin = 0;
        int end = sz - 1;
        while (begin < end)//begin == end 最后一个数，天然有序
' _+ b% S, R! W) s& c) q$ M. p! w        {
                int mini = begin, maxi = begin;
                int i = 0;
                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
$ V+ L+ J( b1 I; b! I: Y                {
                        if (arr > arr[maxi])
+ L; E' Q1 o* o; W. \                                maxi = i;
                        if (arr < arr[mini])
                                mini = i;
! y, o3 C$ v5 e% X                }

7 U8 u/ g, {% l  ]3 F; @) b                Swap(&arr[mini], &arr[begin]);
( O2 Y& |/ K* X# }, R
8 M* G  ?' u( ^$ [                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
                if (maxi == begin)
% N# }& V5 l% f7 G" n                        maxi = mini;
                Swap(&arr[maxi], &arr[end]);
4 b( R* j* W4 x# V" j* ~( G' S
                begin++;
% _: \& p$ T: ?: m6 Y4 F- M                end--;
" E$ O' Z- p1 ]4 Q. E' }$ A( d        }
}

1
+ m3 v: i2 m2 Q( e' W5 H2
3
4
% N, i- [& ]0 W9 f+ w6 x7 G: {5
9 k3 L2 H; [- Z6
7
2 ?! v7 W4 w5 @! j$ I! v( r$ z8
, |. h% C5 L6 m. u% p9
5 u* U' T5 o$ s1 W. E10
11
+ ^0 f7 J& W9 W/ e# D$ ^; I) a12
9 ~* G* o  p8 [. S1 j, D4 a13
% c% @' ^" j  H# i! G' x5 p14
15
16
17
6 y- E- N$ R  i# N+ D' S9 U18
5 C0 }9 R9 p. \& q& f19
20
21
9 v" M- x% i% A6 L22
7 a& d' w- L6 R9 i23
24
25
26
27
28
% s' e* o, Q# r* A: A

. t. J& ~, x) @稳定性
选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以
4 B  k# ?# n/ h. Q7 V0 j' T" V
选择排序是不稳定的

复杂度
时间复杂度
0 A" v. D# \8 {最好：

+ P8 E- L0 Y2 ?$ s% t0 P比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2

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

5 Z; _5 M% v5 U1 F* ^* P6 WO(n^2)
6 M* j! m+ A% I
% |$ u. r8 S/ p. I, I* p最坏：
! V7 t& |8 V- D. ]+ c+ w$ b1 @
比较次数：O(n^2)
% b) ?* H# W: k' }. X. R
交换次数：O(n)
( F9 F, N2 M+ t; z- o) ^
O(n^2)
% c9 x5 _3 H! D8 J, i& T3 r; l
空间复杂度
O(1)

( q+ u* T. G0 @堆排序
思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆
; m% m9 R8 G. g3 [, ^
5 l+ v  I7 Q" H# \) ]/ F$ b

操作
  [6 |9 _; X) }2 V6 g0 F# X建大堆
4 m. |& A7 J: f2 k+ ?. n. A单趟排序：
+ C" U! f0 I1 d' v( v: |选堆顶和堆尾的元素交换，则堆尾的元素排好
& \  c" j! h4 i3 [. b3 H每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
3 \, O7 b" R6 Z整体趟数：
若元素个数为n，则排n趟
void Swap(int* e1, int* e2)
; n0 [, O! o; f3 o  _+ @# N" [{
' ~9 `0 F+ a$ y  R4 E" z- k4 F$ s        assert(e1 && e2);

        int tmp = *e1;
2 C: t4 q4 \" j) V3 e        *e1 = *e2;
! }/ \7 U; |$ I7 \5 e        *e2 = tmp;
}
- t" Y, Z/ m! N8 K0 [
" Q) f( n  ~! {- X* ]$ @8 Z" Vvoid AdjustDown(int* arr, int sz, int parent)
{
* G8 L0 {# J2 x# Y  t9 T& ~( p        //建大堆，排升序
        assert(arr);
       
0 F0 E3 u8 w8 I5 N$ H# X. H6 j    //默认大孩子是左孩子
        int theChild = parent * 2 + 1;
: N5 {/ T0 C0 H0 d6 l7 T        while (theChild < sz)
        {
        //如果大孩子是右孩子则修正
                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
                {
* \2 m, ?$ a; M$ t; f                        theChild++;
                }
                if (arr[theChild] > arr[parent])
2 ~6 \0 K! j) K4 u                {
& \+ g( A' J  Z* N( j                        Swap(&arr[parent], &arr[theChild]);
            //迭代往下走
                        parent = theChild;
; d) }, s( n7 k1 A! g" I3 k: |                        theChild = parent * 2 + 1;
& W5 |7 j1 ~% b0 r                }
$ Z- m0 q& i/ ?; e1 H                else
7 r; m5 W* p! i7 e                {
- S8 H% I! E6 e/ z6 i9 R                        break;
# s/ E% N- W2 h. ~) H6 t! N                }
        }
% g" F) X0 \0 V" g' L/ h}
7 W, A# Y! j$ q" Y$ |* E3 N$ I: k
void HeapSort(int* arr, int sz)
: H- I( j3 q$ `; d' V{
        //1.建大堆
/ Y7 k0 d6 h3 L$ ]1 E' _8 |        int i = 0;
        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
        {
: y( E5 n- d! h% ~; u                AdjustDown(arr, sz, i);
        }

# _% L% V5 H1 B, w        //2. 选数
- Q( P6 ~, y; ?9 C+ A: w6 g: m        i = 1;
! A# i1 E) G7 ~        while (i < sz)
        {
1 x! e8 k' v2 ~- O$ k                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
                i++;
- G& W+ ]$ ]( f5 S1 I        }
}
. J0 O* Y& h( z
+ y: t% @. f' N0 v6 O8 N. @- W" u1
9 a7 R: U/ Q/ D2
3
1 X# \, X' j, I& ]" T1 ~4
5
+ F) |% @/ d+ S  i$ C- x3 [6
- b+ b5 k  [) Q, m3 o  w# G7
; L5 P9 k  D: P, i# x0 m8
3 J' P% w7 v) P& p8 m* d9
6 Q! d" C% A7 c- C  k, M10
11
12
13
14
15
16
17
. w0 h: [$ Q, r8 `5 E/ i18
1 ~! g" X( C4 T+ Q- y19
/ k1 G* B' {- S" c0 n$ `20
21
( m. e( v4 O* _# t- d6 U" D22
( w' w0 K, t; j23
8 S8 }/ }; d+ z9 ^8 P24
25
26
; N- E* K  |; X$ G27
8 b, O/ i' `/ Z28
29
30
; z) E& W' e0 g% q5 r! i# W31
+ I& i# x: ^; Q/ i9 _  r: ]32
, ^9 Q( A5 |  z6 f! j33
6 M0 C5 z7 {' j1 q+ t# K: i34
8 C: P6 R+ o( d0 I4 l7 ~* q7 z3 M5 f# h35
36
37
; I, R" |; y0 k! A  L* S( S- a: d38
9 P: V: ~& H' M- A* \. C/ l39
40
7 X( `, i% W/ v6 n8 {8 |+ H6 a5 V41
/ Q, i0 Q; L/ v42
43
1 [- h) i: _; G2 j' D9 g9 d" y0 \; G44
0 G" W, c8 M3 d' W! S. w% _45
46
! `4 ]6 c8 [( \" _, I/ v# x47
+ |1 k  D9 l  r- N. \, z48
49
+ g+ ]* E5 z# o6 _6 c+ i50
1 i& V, f% D4 `. F. V# J9 i- c1 x51
52
53
54
55
6 \# t6 I' z5 E8 C

$ N2 L7 `1 w4 s% U% c& ]6 J0 x, `! i1 F稳定性
建堆和向下调整都会打乱元素顺序，所以
/ K8 `0 \  w% j* Y% }" N
" M- u, [$ z9 N5 c堆排序是不稳定的

* o! D1 d, H/ ~2 Q5 [, C! \复杂度
8 r+ E5 s# u- |8 k1 v" N' v  ]时间复杂度
, t. |. h" `& c/ E( q' ^6 M单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为
# Z, }6 }! X4 a2 D' ^1 ^* G: p6 \' e
O(n*logn)
: `4 R( j, l+ W1 r+ g+ a) H
空间复杂度
5 l+ x0 I" W0 E原地建堆

O(1)

& B4 V( b+ ]% h( _交换排序
冒泡排序
思想
冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素
6 D$ Z+ u" ^+ J5 v


操作
7 u4 O7 |/ m# J单趟排序：
/ w5 {/ z- w3 c3 C) f每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
每趟排好一个元素，所以需要排序的元素每次减少一个
整体趟数
1 k; H; ]+ e+ ]4 b若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
void BubbleSort(int* arr, int sz)
- p9 H- |; z  d" X{
        int i = 0;
% `6 K/ G4 y6 g6 x# S        int j = 0;
; h. Z  ~! A9 X- S        for (j = 0; j < sz - 1; j++)
4 d0 v3 \4 v6 Z4 v; ]        {
$ L* n% h8 I- p' t1 a5 a                for (i = 0; i < sz - j - 1; i++)
                {
                        if (arr > arr[i + 1])
4 Z1 a. [1 u3 j1 X$ R                        {
                                Swap(&arr, &arr[i + 1]);
5 n& k5 l$ |2 t7 v) x                                flag = 0;
                        }
0 d3 |8 P# X8 C' ^3 e5 S1 V) T" }                }
5 i  l0 j3 ?% ], [# ]        }
! m4 ?, L$ ^: f+ C5 t/ R4 J}
2 A! C9 l& Y4 c/ s8 b0 E9 h5 Y
! x" v/ {1 P; H! J8 Z* p; K& T0 o0 R1
2
2 c, y6 t& @+ n# e* W1 h& P3
, I, n/ z1 [4 P% s6 {/ K. {+ A4
* y& A! j; Z6 t& w3 d+ U6 q5
9 I% q2 P- d; s' A: v6
7
8
9 H4 X/ }, x" q  S6 P9
10
11
12
# C5 c' A' O" e7 k3 T6 u13
14
  W) v) [9 u* H: W9 h15
16
优化
当遍历一遍发现序列有序，直接跳出
1 o6 b3 \4 U/ I$ W( M: k
void BubbleSort(int* arr, int sz)
{
        int i = 0;
) S/ c: ^2 l- K8 `        int j = 0;
. w4 c, d. T6 r0 Q! O; }9 E        for (j = 0; j < sz - 1; j++)
2 y6 P3 u, l4 m3 K        {
                int flag = 1;
, K/ q& F  E' M3 v! f  g                for (i = 0; i < sz - j - 1; i++)
( ^3 m5 ]( r* `: A& Z% Q& Q' E, t                {
                        if (arr > arr[i + 1])
; S' y% J  t/ Z  C                        {
                                Swap(&arr, &arr[i + 1]);
                                flag = 0;//不是有序就置0
, @, P$ }2 Q! [& z7 x" I& a                        }
3 L9 \# T& B4 E! T                }
( V& {3 f$ B& @' p                if (flag)//如果一趟下来还是1代表有序
! ^$ X' \) V, o4 Z* x/ W# ?$ M9 x% u                        break;
6 X" M9 W/ N5 o        }
}
: e* i0 h+ @! a+ ]
1
2
2 K3 M2 }. I" |/ x5 z3
4
4 f# A% L8 T4 k5
4 n6 H; z% w/ {/ c6
$ o7 e+ e+ q/ A6 L& A7
) {; k9 n9 o1 K  [- W8
9
: Z/ L0 D7 z0 V9 c- f- \- ^( v8 L10
/ j4 B" X! Z# K) e& |11
12
$ }. }2 g) s1 ~7 q( K' `13
+ n9 S3 E: b) \7 K% ?7 K14
15
6 |# {: S2 V" |) G" i0 r, [16
# ]$ ]7 c8 _. B1 b8 V0 P17
18
19


稳定性
4 c, B& y. w" S4 \& R相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以
# M4 `6 e1 B. t, E6 w; B
8 u! A! A6 A$ Z* _& C7 H冒泡排序是稳定的
/ n& x3 Z* c. n# s
复杂度
时间复杂度
最好： 当序列有序
* S+ \2 K* l  i2 Q9 U# X7 a
0 {& d% Y7 Q& O未优化：
; p5 H4 U5 Y' i6 ~& F4 s. d4 v
O(n)
8 [& }1 J7 l) F, h- Y
! Q. N: Z. a7 d  {% s9 U$ R优化：
; m# N3 J# I/ A* N9 S+ {* q: M
O(1)
7 |7 h" ~5 O4 c/ D0 z, ], D1 ~
最坏：要进行 n-1 趟排序，每趟交换 n-i 次

, ?- T9 j! {/ Z% x- O# ^0 [O(n^2)

' ~% f7 p! m& G9 g空间复杂度
" Y4 |  ?! ^( iO(1)

快速排序
+ M2 }: c9 h: r7 O思想
分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。

所以快速排序可以用递归来实现
( O, R; m1 j( N
. o3 W6 D& z" D  d操作
0 }, h4 Q. j; O$ t: p3 M有三种单趟排序的方法：

Hoare法
设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间
$ N5 K- s. G0 e/ k
# ~! l' R& k9 O/ Q  v3 t左下标 L = begin，右下标 R = end

# u( W% P+ T5 m$ d+ ?设 L R 相遇位置为 meeti
& K! {3 o( ]) M% Y+ D  B! _
​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”
3 Y# {+ n  V3 e$ c, l
* u9 o/ ~1 F7 a/ [8 {. S* f) B​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“
8 S7 E, a) o" M. d, M; p8 A/ f* W: T
7 ?. }0 ~5 Z+ L4 a选 键值的下标 keyi
$ h& m: n6 D' U, o* X% I
4 b# ]8 G. L' H. P3 V左1位置作 keyi，则 R 先走
6 c3 i9 O7 v5 v2 B右1位置作 keyi，则 L 先走
( f" n+ t# s: M8 V) ^R找小，

( i6 `# s! ^. C1 l' J找到则停
! k2 l8 l0 g; w4 X: Z2 A' ~# i6 a# R遇到L，则交换 arr[keyi] 和 arr[meeti]
L找大

找到则交换 arr[L] 和 arr[R]
0 M* E$ @' p, }7 M9 h遇到R，则交换 arr[keyi] 和 arr[meeti]


3 ]5 W' k  x1 ?* l解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
答案是肯定的：
4 h" t! A4 A! @, Z* \' o7 `& D1 Q
3 Z* Z! r- O% d
9 s) J, v. j( X1 U; @2 P* o
5 L+ n8 H* ]4 v% p
/ o- B9 o3 y) j- ]" D2 B! h//[left, right]
int PartSort(int* arr, int left, int right)
{
        int keyi = left;
/ w6 p" \. U8 b1 X        //相遇则排好一趟
. d; M: f+ L, \2 _3 J5 H: b  Z$ S        while (left < right)
        {
6 B  f$ _- j4 E, w                //R找小
        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
                while (left < right && arr[right] >= arr[keyi])
                {
                        right--;
5 T5 H0 S! l0 [, R6 J  Z! j7 _                }

                //L找大
                while (left < right && arr[left] <= arr[keyi])
                {
  b  D( s5 u  _( s                        left++;
1 Z6 s* Z; q8 C( V7 \3 t* k                }
3 f, b4 \4 E! Z4 U+ o$ b' ?9 s               
+ H: |- ^% D/ t% |, m        //相遇就不交换了
                if (left < right)
                        Swap(&arr[left], &arr[right]);
# F1 `" P9 \+ N: m2 Y7 [        }

        int meeti = left;
' V' O) R) q7 K; p5 _
9 `' A% f% z1 i  q5 W4 K8 `        Swap(&arr[keyi], &arr[meeti]);
. G. H# R$ p) x5 R, J
        return meeti;
- L, h  c2 o' |' y0 _* O}
' B5 p/ ^( T' {3 r
3 d/ P0 H; u9 u3 ^3 n6 Q1
2
3
7 y4 U( z( L: K* m' _6 Q9 q4
5
6
7
+ @3 z; S  P6 V) P8
9
10
1 M. |( P# F/ o6 z: X2 k11
* O4 q+ X2 E1 S12
3 |7 g! L' s1 l) D13
14
/ z% c: j* O0 p7 K, L) E6 ^5 m15
16
17
4 Z: C3 I$ V+ L$ I8 a18
6 ]$ a' w* P4 y$ x19
20
* {* b# Z" j2 X, U9 h( ^5 f21
22
/ \. k( d& W. x3 a: x2 Z' \23
1 ?' I5 }/ s9 I! `& X" p/ O& \24
: D$ j/ c  F7 x$ \25
3 f% v" v$ P0 I: Z. x) E' r; K26
& `  x& N1 _$ |* f/ d. ?27
4 P, E: ?3 m6 u28
29
/ f1 ~: t- q) F5 g- z8 k30
& g1 L' ~9 w) H0 x- ]31
32
6 |7 W/ E# G- O  K* I
. a) Q( X% s! y1 _( a0 ?
- [/ [2 n) F2 l: ^" P- q" r解惑：为什么key要选左1/右1，选中间不行吗？

+ ^0 B* B9 ^4 J# R
可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深
* j) A$ r! e: {% j: X1 W

7 ~, g9 a0 z: r3 Q7 D3 R/ B
3 x( a; {/ M/ W/ s* p. `+ [
# |8 Z: _; B( Z非常容易栈溢出，怎么解决？针对有序情况，优化选key
9 ~( V: ?# J2 A6 a8 f0 a7 Y7 D
: Z4 m" g- f$ T: G2 Q# h  X+ p优化选key
1 i7 ]( {8 q# v- B9 q  z5 _  d随机选 key （是一种办法，但是不那么彻底）
选中间位置作 key
) V* Z4 N" ~% W% _解惑：那先前实现的单趟排序不就失效了吗！
3 i& B+ |& C0 W5 n：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑

8 k0 e2 O$ z( j7 f& n解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
) d+ r0 O5 H+ E' G1 ^" \前辈给出三数取中的方法

% }# k# a* o+ g* m3 Y三数取中
- v) N% n: H+ P7 |' q在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
4 ]6 H2 b% X( ^这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
$ ^) z6 N3 |+ E3 `9 _. z优化选key后的Hoare单趟排序：
5 @7 J8 V9 g5 b5 j$ H8 _
int GetMidIndex(int* arr, int left, int right)
{
        int mid = left + (right - left) / 2;
//  int mid = rand()%(right - left) + left;//增加了一定随机性
        if (arr[left] < arr[mid])
        {
- \5 k% B1 J) J2 _& I                if (arr[right] < arr[left])
                        mid = left;
4 d+ H$ x- d. ^1 z                else if (arr[right] > arr[mid])
                        mid = mid;
                else
                        mid = right;
        }
- N0 F+ C& y3 B        else//arr[left] > arr[mid]
        {
5 f1 K* y0 [2 G, d8 u. {3 C- n9 Z                if (arr[right] > arr[left])
                        mid = left;
                else if (arr[mid] > arr[right])
                        mid = mid;
                else
; c6 _! u- T7 Y& X1 _                        mid = right;
        }
4 E7 M* T3 B" i9 s7 H# T. D        return mid;
. T3 u* F  I7 C' \# u+ s8 }0 l}
1 N& |  ]' Z- C, N' ~
- A9 R9 e/ z* {" d& J+ @- Q$ r6 O8 iint PartSort_Hoare(int* arr, int left, int right)
{
        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
# {; u/ {6 I0 m' c1 q        int mid = GetMidIndex(arr, left, right);
% s; l& Y/ ~$ P# L, j( ]$ i8 O
        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
        Swap(&arr[mid], &arr[left]);
) i& G8 n% g( L
        int keyi = left;
7 w7 X+ \& R7 y1 _        while (left < right)
        {
( I  {2 V/ q! ^4 H4 I" }                //R找小
; V  Q  K( }% q                while (left < right && arr[right] >= arr[keyi])
                        right--;
- B8 R: t# i' u; E& e5 c; f! \
                //L找大
& _. O( C8 m  A1 B9 T                while (left < right&& arr[left] <= arr[keyi])
6 S. r* s0 J2 }1 a0 H% g/ k                        left++;

                if (left < right)
                        Swap(&arr[left], &arr[right]);
        }
' g/ y6 r- Y1 u$ s% Q! N
, Y1 V2 n8 f9 @/ p; d. c        int meeti = left;
* c% T4 n* g- x8 `
: V" t, y5 c. g3 s* x' }3 p        Swap(&arr[keyi], &arr[meeti]);
  r/ A/ z8 M& z7 H
" n" @4 T* D) Y$ w6 G$ f        return meeti;
0 P2 j) f' k$ h0 T( R% q+ B}
9 u4 D1 d" o4 H! \
' {! _* F! o8 g! Y3 B1
7 x& v$ J3 P! o6 P" T+ r2
2 G) v6 }5 m5 w, {% x3
0 ~8 v4 r) @# K4
* |. a% w3 \3 F" \3 p5
, C4 M# j/ ?9 U) g' u9 D6
+ q( O; x# {! k7 s/ e7
8
9
10
11
12
13
0 @7 m" w9 v8 }5 `+ M/ K) R0 M14
15
" j9 ~7 f6 m' u16
2 }- J3 D+ f; U5 p6 ]17
$ |) t: |* I- c0 [18
19
! \9 |9 M6 `0 V3 k1 U20
0 [4 S7 [8 `2 l6 \21
22
; G  J* o; k' u7 V3 l  G6 I2 i. q23
24
25
26
+ O# H7 u, b7 ?* v27
1 d- h9 ], O& q" q5 G0 c28
/ |! S' W9 k6 W0 \$ S29
30
' w% S* ?- D  h1 h1 Q31
32
33
34
35
' g3 A, F$ e" Y: W36
37
: C1 Z; l' \) t9 a38
39
40
41
7 ]/ `7 O/ C1 ^5 [; Z42
3 A6 ?% H$ X6 X% U* @3 S43
- W2 f+ z0 x4 x! t) L% D+ x% p44
0 ~8 `/ K9 e: Z. ?; I' }3 s# Y45
46
47
48
; V$ Y6 m% G# z* U* o$ z6 Q49
50
51
52
53
54
+ P# R: @- I2 T挖坑法
初始状态：L作坑，其下标存为key
(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
重复 (1) (2)
最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]

, l$ J- M# D( Q) W3 a, ?9 ^
+ _" r+ M2 r# zint PartSort_Hole(int* arr, int left, int right)
{
' ]* Y: }3 O- ~: ]9 Y8 @1 {        int mid = GetMidIndex(arr, left, right);
# e% f% L8 D; B) j7 h        Swap(&arr[mid], &arr[left]);
% l' d) F, x! Y. V5 z
3 {3 ^8 F" k, s( c        int key = arr[left];
- ~9 A' ?$ d) `/ @$ Y$ S) a        //L作坑
        int hole = left;
/ V# o% v7 q4 x  J! v7 G. Y        while (left < right)
8 M8 E' o4 N  `' n4 w        {
3 C% u/ e9 p5 `# E0 M* H. Q: K                //R找小，扔进坑，R作坑
1 G8 f, f; n  t5 E( S- Z6 m                while (left < right && arr[right] >= key)
2 g$ ]8 j7 T- G4 q                        right--;
                arr[hole] = arr[right];
$ {& D* B2 e2 Q, ^3 j$ k/ ^- ]# c: R                hole = right;
0 V" _" X6 J- [
                //L找大，扔进坑，L作坑
5 i% y2 X3 h( V% N% N7 l/ T2 x                while (left < right && arr[left] <= key)
                        left++;
1 `# J. u# `& `                arr[hole] = arr[left];
                hole = left;
$ G% Y# H" t2 |4 Z5 I5 o8 ]4 `8 J        }
, V, E) b5 i, G% t9 e. o! \. n        //meet
% E2 x- `6 o( s2 S        int meeti = hole;
        arr[meeti] = key;
- }. T: d- i. p, y" L/ X' n, K5 M
, Z+ c2 v1 Z: Z  a9 V7 {        return meeti;
}

& ?9 M% _4 Q& i8 {3 @0 U1
8 \) y+ x' G8 S2 w0 M2 B7 G9 y3 {. i( L# }2
3
4
5
6
7
8
9
10
11
, H$ [- A( ]9 D, o# m12
) T6 a9 C/ `3 v: v7 d8 \( N0 V13
2 d) H0 |, Q( B# R14
* ~& ]/ g3 j' c15
16
17
18
- j0 J+ v! ~8 e  x8 o19
20
21
- ^! W  o8 F9 o6 a22
3 F' p% O! y' @8 Z, M" c23
24
- I$ ^7 b& ~7 H0 N% H25
3 ^8 g8 n( v" [7 _7 r1 N% W26
27
28
前后指针法
. |8 o1 V8 D3 l% K此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多
, g: V5 v: Q  B+ S4 q& G6 z
, N1 ]4 H' H! k, b  ocur找小，找到则停
++prev
如果 prev != cur，交换 arr[prev] 和 arr[cur]
如果 prev == cur，不交换
0 s: }8 \; p( {1 A* N当cur越界，代表找完，排好序了
5 R" d# ]5 }4 X7 z& zprev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低
0 _  T2 @# Q% O/ r, L! R
. Z# s# u3 U1 f: @/ m: o
1 M" @  K/ [/ U' M' X
( h2 D7 u* i0 w/ V+ c, Aint PartSort3(int* arr, int left, int right)
( r/ \) u8 O; j) u# K{
- Q2 y* b( }' d/ p' J! m        int mid = GetMidIndex(arr, left, right);
- C; x0 ?5 {: v, g        Swap(&arr[mid], &arr[left]);
; I4 L3 }' i: g4 I( N: ^' T7 w       
1 s' ^; a6 H: ?  ]! j+ I  //int key = arr[left];
8 b- t' l8 x) I7 J' M        int keyi = left;
1 A! X5 f$ x( z1 @. w9 x$ l
        int prev = left;
) J5 |! l  @, {! `* y        int cur = prev + 1;
6 `$ f8 v# x( u  {8 `$ X& f( ?       
) F2 n9 h2 `8 n+ O( @" s1 T    //cur越界：找完小的，prev的左边全小，prev右边全大
+ c( v+ O% k# F& s7 ]1 G) a2 f) r3 b        while (cur <= right)
8 f* R6 F2 T7 w* e        {
' `, ~* p7 O; G* ^' N4 X  }! m  A        //++prev == cur 没必要交换
                if (arr[cur] < arr[keyi] && ++prev != cur)               
$ m0 D& v1 E: J$ S% H* s9 C                        Swap(&arr[prev], &arr[cur]);

4 w/ g  Y! n$ q) v5 Z- Y, G1 N' I                cur++;
        }
. s4 c( W, n! p
7 Y$ U5 v: Z0 L; |: ]+ f        //键值存是的值：
) G) ?4 r; h$ r        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
        //Swap(&arr[prev], &arr[left]);//这才对
    //键值存的是下标：
: p1 p6 |- m" }! Q8 |1 h        Swap(&arr[prev], &arr[keyi]);

! J7 |5 N9 q# D% h) `9 S2 H        return prev;
. x* ?. R" Y, p/ R4 g& R  }4 ~9 f}
3 r+ P( t3 ^! T: Z% ?' P. q8 H
1
/ F- H* l  ~% x) {8 {% L2
. i8 T) ?- Z: H& u2 i6 P, F1 h) L3
4
% ^( Q3 j# a8 v5
6
7
8
9
10
; `* s, B: e: d" K11
  _1 i4 R6 x2 s0 I- A12
13
& W( F9 M: b$ {  z( ]+ u14
  }. E5 a- Q6 ]: C4 Y0 X15
7 ?1 A7 T9 B! |+ M* I9 P) X- f16
17
18
1 R4 u( {  r5 u1 e$ h: f' g19
20
21
22
& ~& t; p: V, u1 k" X" g23
( e9 u3 M1 c9 L& R* d+ n) R24
8 S; Z+ p( P) X25
# b8 K, y: S! s4 C) O26
27
/ v* a- q% u8 D' W6 n( a* B28
29
整体排序
! p0 }) t6 |7 w, t! W7 t; U5 _% _递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
1 ~% S! z8 k% E3 q+ Z9 p+ v4 I        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
        // [begin, meeti-1] - meeti - [meeti+1, end]
                //1.begin > end:超出范围
$ f8 o7 X7 ]  K2 }/ F6 v  S( e                //2.begin == end:一个数天然有序
    if(begin >= end)
        return;

9 m+ l! k  g) K) h8 T; S/ i3 U                //排好meeti
                int meeti = PartSort3(arr, begin, end);

                //排好左右子区间
; S& U" a* Q5 w; ~! k" @                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
! ~; }5 ^4 F" P! R3 z% F& n' h+ P        }
}
5 L2 |9 K, I& h/ i( Z
: y9 i3 W! E- D9 E$ q* i1
6 J1 ?0 ]6 [8 x  g  E! X2
3
9 N2 B2 E# w3 l( ~) n4
- K8 H- ~# P7 S4 o" c4 z/ w% m5
6
0 E' X1 ^4 D) ]7
. D( ?* i1 I- J! h& v# b" c8
9
( V4 S8 g0 ]" X- R8 h10
11
2 A1 T9 f4 T/ b. s12
13
14
15
16
17
. [" j0 Q0 e5 Q+ n" e6 {1 y/ ^18
- Q4 J" n* C( r! ^+ j; H' O" e…

' c0 U8 o2 V- I4 Y0 m  O) a没想到吧，还还还还有可以优化的地方！
, A: r5 N& T- C$ o& \
" Y$ l- f6 k/ k! N6 y: Q/ p) z3 c; U$ z优化小区间

) r7 j" N, z$ q3 A
如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序

2 f, J* b# k) X, y; ?那什么算是小区间？
& |9 S9 n; V" p) l+ j( g0 u- [$ I8 s
5 h6 U' N9 R3 I% p6 x# f其实小区间没有确切标准，8-15左右都可以的
- N- E4 f# T1 ]1 B  C6 c
; S8 n7 m8 v* S$ B: G9 O: O2 b. W/ H
这里就把小区间定义为 含有 8个数或以内 的区间

//[begin, end]
' u  I# [+ s3 ^% s0 [void QuickSort(int* arr, int begin, int end)
{
        if (begin >= end)
) P+ Y) Q$ F8 Q8 H3 D" X4 v                return;
8 z+ ?" ?; Q9 T4 c& @
        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
        {
                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
9 W  K. X& Q3 Y$ E1 Y* ]; t1 J6 ^        }
        else
0 X9 E' d& i8 q$ ^$ y) e1 v7 w        {
                int meeti = PartSort3(arr, begin, end);

3 |) _# X; A* S' Z9 Q1 Y. t                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
        }
}

3 Q' D) ?( q/ x1 v* w7 O: c- @1
2
6 t2 K4 ]$ z- {4 r3 r( d/ G3
4
5
6
7
8
9
10
11
: j& p" ^& ]. G) m" S  r4 ^# N12
. l. F5 t2 s+ z/ E) L  p13
* W' z9 R, d  P" r0 K% I14
15
16
$ Q3 ^9 ]3 J1 I+ O4 W* g17
4 s4 ^% s, T$ p2 a& `18
3 t+ e' T) e" u* }19
% r2 r" x, ?! F0 \6 n9 C3 Q, a快速排序非递归
为了解决彻底递归深度深的痛点，我们来试着把它改成非递归

5 C" O) Q9 f/ t思路：
递归深度深，栈的空间又小，会栈溢出…

: g" k- ]9 Y  \1 b那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！
) c: ^% u. T" X# v2 b
& D/ m/ r0 d. \/ C4 u核心思路：在堆上创建“栈帧”
) @: ~1 ]* e2 z1 Q) A
" x0 Q$ F5 L+ `2 S快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的
3 e' R3 }5 q7 r& w8 n5 ~* a1 D

) P7 V; z: }# q- s
在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：

先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
8 y. o7 c6 ^, t+ x& c先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
{
        ST st;
        StackInit(&st);
       
    //先入begin
) O8 j. V& V$ f" z! G4 N        StackPush(&st, begin);
    //后入end
        StackPush(&st, end);

" w5 P& p4 D" }: P# t        while (!StackEmpty(&st))
        {
3 C! x( X0 z3 ]. F0 a: z+ y5 ^6 X                //先取end
                int right = StackTop(&st);
' K8 y# m9 |  b& y" _4 V+ m) [                StackPop(&st);
) ^1 O/ W+ q: u2 a1 {: ]9 x                //后取begin
                int left = StackTop(&st);
  J& {- a& z( S' q4 G0 M0 g                StackPop(&st);

; m$ p5 o* @# J5 Q                if (left >= right)//1.只有一个值  2.区间非法
                        continue;  
( @% a9 X  G6 p" t% f/ }( h                               
                int keyi = PartSort_Pointer(arr, left, right);
! I1 u8 k4 a; `" w8 A, U
9 o/ ^* ^( _7 y3 M5 ]                //先入右区间
                StackPush(&st, keyi + 1);
: H. E  A, K0 w& Y                StackPush(&st, right);
                //后入左区间
' Q3 A4 t* p5 D3 G, D                StackPush(&st, left);
- W" U# L5 P2 c2 `
# o; |4 J+ C  g" ]  O. N                StackPush(&st, keyi - 1);
3 e. D4 G+ C9 b/ B% h        }
1 W! u! R% T5 F1 q: K8 p
        StackDestroy(&st);
2 R: n. r( x8 K* |" |}
$ A( x7 K& w( N% V* e, N
1
* t$ X$ {0 j+ F  q, U2
$ E$ H- f  X$ O2 v. E9 j& @" Z" o3
4
5
6
3 l$ H, }6 n, x( i; V7
* l# F( _1 R1 M3 U) T8
) l* l; z+ `+ x9 E# v9
1 Y3 Z4 G) r. k6 q10
11
" e7 C' r5 k. S1 B* s12
13
14
6 x# B/ N9 r) Q7 X1 f15
16
0 i# o- J( Y, y! {5 i17
( W0 m9 v3 ?! w& m18
- n8 u& i9 N6 T# q19
1 h2 L+ Z! U- e$ F3 ?9 Z# s20
21
7 {1 O% m3 w2 k% M' H- J" H22
23
24
; M; t' s- p2 S2 L25
9 z# L! B5 s5 b  o& L1 w26
27
+ N  ]" K' J! J1 ?* B28
( x3 h1 S' T, B$ j. F* y0 e29
* u6 V! d! m9 p/ z  J$ {30
' M# F) G3 v( s( Y5 ]" H31
32
33
34
; v/ N5 `9 M: P/ X8 V2 G35
数据结构栈的实现可以看博主之前发的博客
9 `: ?& b. a9 x7 E! |+ ?

归并排序

…
, ~( q. r7 P& d6 |0 n0 a
性能测试
0 J0 h' c. K2 F# t4 ^4 b2 H  ]" ivoid TestOP()
# Y# [' A' a( O- @: X! \* r{
6 e  g1 r/ s8 I! ]        srand(time(0));
        const int N = 100000;
+ C7 x' }. l+ ?" y% |5 N2 R* n- o        int* a1 = (int*)malloc(sizeof(int) * N);
% R) S. r4 [5 s' j* I; E        assert(a1);
        int* a2 = (int*)malloc(sizeof(int) * N);
        assert(a2);
5 W7 |% C: i% j        int* a3 = (int*)malloc(sizeof(int) * N);
        assert(a3);
        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
        int* a5 = (int*)malloc(sizeof(int) * N);
, T. C: s0 J& v' p" B( F        assert(a5);

        for (int i = 0; i < N; ++i)
        {
                a1 = rand();
                a2 = a1;
( @$ U% T+ @; n& c                a3 = a1;
  Q8 b; b; r  X# h. k                a4 = a1;
                a5 = a1;
% W; s3 X( V  f; ]1 {2 d        }

# W, D* m& R3 p        int begin1 = clock();
        InsertSort(a1, N);
4 S( o2 {3 ^' l: a) f        int end1 = clock();
2 ?( L% X( F. x8 a! J2 n
        int begin2 = clock();
        ShellSort(a2, N);
        int end2 = clock();
+ \6 S. x2 J% r+ P% a$ _
        int begin3 = clock();
7 e+ A8 N. {7 I7 k+ C0 F8 Q1 r! v        SelectSort(a3, N);
5 P6 P: s/ m. }" p4 J        int end3 = clock();

        int begin4 = clock();
        HeapSort(a4, N);
& ]' Q( N) t, f! B        int end4 = clock();

' m/ B+ R% D: f4 w, }$ g# U, e2 \7 J        int begin5 = clock();
        QuickSort(a5, 0, N - 1);
                //1.中间key
                //QuickSort(a2, 0, N - 1);
                //2.三数取中
% d$ ~) ^7 M0 S+ ?                //QuickSort(a2, 0, N - 1);
, v/ H8 v$ H" C) I; L2 K; G0 C                //3.小区间优化
( @& \+ o; A, p& Y                //QuickSort(a2, 0, N - 1);
0 O3 Z( R/ C9 C4 D; i1 @' {7 E        int end5 = clock();
" I  v' y% v' \2 \/ {4 `

        printf("InsertSort:%d\n", end1 - begin1);
        printf("ShellSort:%d\n", end2 - begin2);
1 [# _+ e& q4 g        printf("SelectSort:%d\n", end3 - begin3);
        printf("HeapSort:%d\n", end4 - begin4);
4 s7 `6 U$ \" G$ J, g2 \8 A        printf("QuickSort:%d\n", end5 - begin5);

& G, S" k/ G) P1 x2 ~5 u6 P        free(a1);
        free(a2);
        free(a3);
        free(a4);
        free(a5);
}
( l: E& _& L7 P5 h% e- N6 w
$ ]! B/ B% ~0 j: L- w6 L1
( Y+ w3 I# P5 |4 U2
4 k' W# q0 L2 H$ a  |1 j3
4
% q; j+ [: t) h6 g! n+ \5
& h5 _- z, a8 m6 P/ e1 o& S) T0 V( W4 N6
8 r7 w, `0 Y5 E5 v- [( B& U7
8
9
0 @; ?5 A9 G  @/ ]# F10
11
12
! i5 D; z. D4 K3 D4 M13
4 Z8 m7 a' d" G' @: i/ x14
, J1 w7 q' j) R15
16
17
* U7 q7 G' I0 Y0 A6 ~" @18
19
20
21
22
23
/ ~6 Q* \0 ]5 `) }$ z24
' A8 ]* `' y" ?: {! {5 m: h25
! u# S# T4 x* N2 M& r) w26
27
28
/ H; Y9 w3 L% M" t: M29
" {* b: K; P& C30
31
; q* A  U  o9 g. M32
2 W6 m6 {4 t8 }) X, E33
34
35
. u; ^; O& h4 L9 K: @5 [% q36
4 R$ `' h( O# F. g% S) ~37
4 v, p) f! K1 O* W4 g% x& Q3 a: W38
39
8 E/ y! a* z  E* K40
# S, S! F  t; g' [' b) P. z41
42
' P  I7 c6 g1 a: X: G) O43
44
45
46
- T  ^; Z$ y  \47
% ^5 `4 r$ u: H/ r! ?0 _+ E48
49
9 Z8 z3 \8 T( h3 u' w7 w0 U$ e50
51
2 K( l6 C( c* K# s$ ^" [, @% Z52
7 h/ l- j" s) {53
6 w& g$ b* Y2 [2 V7 A54
55
: p* J) j4 Y( |, ?! a56
* d1 _; }, N: ^0 |- T$ E% g! c57
/ D/ J5 F+ P( T8 o; w- \  f58
59
7 Z+ u* t7 Q" a, R, f6 T60
61
2 i5 s# J$ k; M/ M62
63


不愧我们费这么大劲优化快排，多帅哦！

" E! Y3 i& _* \2 h差一个归并排序，后续补上！

不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
————————————————
- Q- U9 g: V( N2 k版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
) l0 }8 s( I. E原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832

$ T' `/ x) B/ e6 T' k" o4 T) }
* Q5 s- c+ r$ ?9 R* H5 ^