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

杨利霞

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

前言
本期分享经典排序：

; ?8 h5 r" N' w2 w2 ^) Y+ n插入排序
& w% p# R: j. A/ [直接插入排序
7 O( z+ c: I" v2 l* y- f; E' d希尔排序
1 A" K4 T: C( Z# I( ^选择排序
直接选择排序
堆排序
4 O; c1 x: z5 k, k, o交换排序
冒泡排序
快速排序
注：讲解时默认排升序
( I7 s  Y$ {: B. e
插入排序
  v9 Y' l* O6 Q3 F* o直接插入排序
1 w: U8 ^" Q+ u) |思想
插入排序，就像玩扑克时，摸牌的过程：

+ S! Q* T$ }3 v2 Y  T# H4 P2 R最开始，左手没牌，右手从牌堆中摸
" Z  u7 y6 ]3 H0 F4 f右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
如此一来就能保证左手的排始终有序，摸完牌后也就排序完成

. H9 {( G2 I* x: C$ G& w4 N
4 _! s; ?5 ^5 B3 Y+ J8 T操作
设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
单趟排序：
* h2 D: r9 F4 ~0 @: z5 p* b' [. X, l每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
/ G6 r; v. X; Z; F8 i( \* Q7 y# K是正确位置：插入
不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
整体趟数：
0 v& b, \( c0 t/ c$ j! U- e, t+ |  G若元素个数为n，需要排n趟
void InsertSort(int* arr, int sz)
{
, U4 H9 g( y4 e        //end + 1 < sz
        //end < sz - 1
6 I% Q3 P. y: \: G& R: }- |- B        int i = 0;
1 X4 S+ ?+ S3 D7 N        for (i = 0; i < sz - 1; i++)
        {
                int end = i;
                int tmp = arr[end + 1];
/ u$ {8 c( o6 L( t+ R1 v9 ?' e# G3 _: C
                //找插入位置
. }1 S. R. c$ K: w+ {2 K                while (end >= 0)
                {
( z7 s% F' G8 q! S5 m5 d+ o                        //不是插入位置：当前数据往后挪
                        if (tmp < arr[end])
* k& \1 n: d% A                        {
& o& l7 Y/ J0 f& k- E& Z2 A2 `                                arr[end + 1] = arr[end];
                                end--;
8 u9 C* z$ C2 i                        }
- ^/ {  w4 Z" ?6 L( @                        //是插入位置：跳出循环插入
6 k4 m/ k! ], I, Z9 F: A  ]3 m                        else
" C* @, m* t; M. D& v7 \                        {
! @% y1 e+ ]/ Q$ O                                break;
                        }
                }
: L; P* a+ [; V# b                //插入
, _0 U" R" ^1 N7 ~  S, p' S: r                //1. 插入位置是[0]，end == -1，不合循环条件跳出
/ i% a$ g9 X7 w9 q- G                //2. 找到插入位置，break跳出
0 e  i% h/ d, j$ m# q                arr[end + 1] = tmp;
2 a/ a: h  [" E' o2 X        }
# y, E+ ^- t* x/ M4 h5 B}
9 P1 A$ U% G4 F3 t6 ~2 T
1
2
3
: D- s* |: V; X* D$ t0 H4
5
6
7
8
, \& [" X8 k2 \  ^+ Z$ T9
" L& |9 [* S3 {( a% E10
11
: K1 r# o0 m; o+ y$ |* L: p; B$ H12
13
8 f" e  v9 H8 Y8 w, F" q7 x14
0 {$ Y* e% ?. u. j3 j+ I2 P2 T, k15
) l( m( x7 V! W+ W+ W! ]2 o, O4 u16
- I# I$ q! \' \6 n! l# [% ~17
; J( D! v9 G  t/ r9 B5 m8 w* g18
19
20
3 b4 k1 Q4 p' a7 l21
! d; d$ m4 M+ M2 Q, ^; T2 o3 ]% t22
; l$ E. H, B$ J* k7 a23
24
25
26
- W; C& G- b# C  N6 q+ I27
28
29
30
31

2 \1 G; l* `, M$ L/ [3 y! r, \! A! `: \
% H9 t" A0 S( V9 _稳定性
插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以

& @! k/ @9 m" d% F' r' b- {8 s直接插入排序是稳定的
. J1 x6 ]8 z8 O4 x( Z
8 k; z0 ]( o  S. l: M, Y8 H2 D复杂度
3 o9 e7 _; {' P8 z; O2 r: k/ Q时间复杂度
最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）
% ?" W. @3 i9 k3 M5 x
! h+ S8 f8 A; k. M& d; l0 _+ pO(n)

最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2
0 I( [) f1 W; [* H7 @2 U
O(n^2)

' M- ]4 B" Q2 o7 S& g2 o空间复杂度
6 E$ Y0 K) p5 z' T! }O(1)

& {; e* p+ V2 N1 G: t1 {希尔排序（缩小增量排序）
+ g! ]3 g8 v. a6 k希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序
/ [% C! F; v. @  J0 ^% i
0 M# @2 p. B& c; r; `" {# R优化思想
增量gap不止用来分组，也意味着数据移动的步长，所以

5 m6 W( K' Y7 r: Agap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高

- L, ^0 X! u6 A/ n! Q$ o
7 |5 ?  U8 r# Y8 |' V7 n操作
单趟排序：

8 m" _# X# @. {7 \; d# O* k- {* S设定一个不断减小的增量gap，也是元素移动的步长
& E1 z$ Y) ]  k8 ?; @3 k! v& ]2 T以gap对序列分组，并对每组分好的序列进行直接插入排序
& F0 x/ L9 P  @' G不断缩小gap，并排序
; K, |! V& B1 G, \  A; L3 G*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
' M: q) z( N; f整体趟数：

4 A6 ~% j! E) r9 _8 b% Z* U由gap决定：当gap = 1，排序完成
注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。
4 G( n! i# h6 b; A- Z$ S
void ShellSort(int* arr, int sz)
+ @0 F0 D+ J/ {8 e, a, J" a{
        int gap = sz;
       
$ |3 V. `% K% X; M' O    //gap > 1，预处理排序
7 B& `: J5 U: u$ y  J    //gap == 1，直接插入排序
        while (gap > 1)
        {
                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
7 ]6 J* O- V: M3 ?                //gap组
                for (int j = 0; j < gap; j++)
5 Q5 c" |+ {0 i' b* z                {
. R6 v; X$ O  @0 B+ o7 _            //end + gap < sz
                        //end < sz - gap
                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
( M' L4 G3 v0 l8 ~+ t7 `. @* ?) Y                        {
/ t3 J6 ?- \% J6 t" y                                int end = i;
) {+ c/ e6 ~$ R" ?6 k                                int tmp = arr[end + gap];
                                while (end >= 0)
9 G  p8 b# \* ?# i, P: [4 c0 f                                {
* W6 g+ h$ O$ ?. y2 {                                        if (tmp < arr[end])
) N: }: F  X& b9 ?( v0 G                                        {
  a" m% W1 X% N9 ?/ U4 M' i  A                                                arr[end + gap] = arr[end];
  [* @- n3 H& g1 Z& y+ T                                                end -= gap;
" ]. k3 G) f% Z6 e( g8 G                                        }
# k. x6 L- L  M1 Q- o. O3 M6 d5 M                                        else
7 U7 w$ K7 e1 A" q                                        {
                                                break;
                                        }
# {% J* o  u" v1 x# P, X  g, [                                }
                                arr[end + gap] = tmp;
                        }
+ L; }( U, o* V+ x2 L$ b) N                }
        }
}
9 P1 X' B5 `5 u2 Z$ D
1
2
. x6 {( h4 U$ `3 p) J3
4
5
$ ]8 V) ?* d9 \; W3 ]1 Q; D/ `6
; Y+ T4 F$ S2 g/ K7
# K6 X5 O$ o) Z6 X: [: K- s8
0 H/ O6 z4 ]/ M+ W9 R: Y: b3 F9
! M3 j" q  J0 t2 K10
1 A* z: j2 g5 i3 i) |' z+ f7 X11
12
. D  S% ]  {$ P- Y; t3 G% w* g$ Q13
14
15
( d0 Z! u. X; q" G3 p16
$ ?8 j. `- \1 y17
! {) U) v) @/ t* u( `) P18
( d2 \9 C! ~0 Z. D) q19
20
! m/ n( E' x2 ^: w9 g5 F21
; R7 M$ b- C: w5 a1 C22
2 O5 o) P3 `: G; x1 i: t23
24
4 h2 }4 P. W2 J8 t25
5 r; ]4 e7 \5 O% y( ]26
2 ~% h; C2 _+ q: }# Q27
( Z+ ]& y+ Z1 c28
% n8 O/ C( q. h& `29
30
31
9 O4 d- v5 I' S/ f$ R9 d6 @32
33
34
( p2 u5 r0 s6 C4 W- \35
" I* F: v) j1 K& ]# _其实就是套上”缩小增量“的直接插入排序

3 e! ]+ G* z" x+ l) R
稳定性
我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以
( k) h# l( @; C$ J6 V
希尔排序是不稳定的
) R) p+ }1 s/ H9 J* ]" T
$ z- h" p9 `- o0 q( Z复杂度
% x8 O; O& D, x" B3 x! p2 h; P时间复杂度
+ }( l% l  x6 V* Z$ {4 S- L希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
  D: n( @. Q2 J  H7 E
2 t) x' i9 g; F! f: \' a/ d+ T# RO(n^1.3)
- S" |2 N2 ^' w( Y# U
! D  f3 ]2 B' Y5 Y! D! M空间复杂度
O(1)
6 j7 F/ K# Y! t( }: X9 P3 E
选择排序
. v" H2 y2 J7 ^1 J8 @9 R, A直接选择排序
思想
8 Z. T7 t$ x1 _: z选择排序，遍历序列，选出最小的元素，交换到左边


( {* i/ A, j7 N3 O, j0 c
' e. I/ z  s7 V$ `+ v. Y3 e优化版本：

3 }2 ]0 W# ~, q5 o2 u每次选出最小元素交换到左边，选出最大元素交换到右边

& ~" k9 S% {* }3 j8 p操作
3 |* p5 W1 j+ s; _设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]

设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标
# U) o. U/ ]6 d5 H5 Z+ ?- P
单趟排序：

遍历选最值的下标
# ?/ p( {8 E* |- k0 v& ~8 C交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
2 s8 ~& \' v+ G! [（修正）
整体趟数
8 d  \' I$ S9 p* F6 m" X
若元素个数为n，趟数为 (2/n)
0 ]6 _( u: @3 e" w/ W! [# w2 Y修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标
9 O0 p" F3 ~7 ~9 B6 E! b, D1 Y  Q
void SelectSort(int* arr, int sz)
3 B6 I" m  S$ ]{
        //闭区间: [begin, end]
        int begin = 0;
        int end = sz - 1;
4 p+ S$ @( [0 U# c        while (begin < end)//begin == end 最后一个数，天然有序
        {
! k9 y8 U7 \9 L5 X, Y1 G% O% S                int mini = begin, maxi = begin;
                int i = 0;
                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
                {
                        if (arr > arr[maxi])
1 F" i1 k' X" k8 g; O$ Z, U$ I                                maxi = i;
- k. @7 r' E: s3 ?+ ~' C                        if (arr < arr[mini])
                                mini = i;
                }

0 ~, e) P- r! n+ {                Swap(&arr[mini], &arr[begin]);

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

                begin++;
                end--;
        }
" }  R0 G0 O; r5 j" j3 }. k6 T% O, k! U}

; C% f3 }+ z, y+ e! T/ b1
2
) I' h9 m4 }9 l& X/ I0 Q" Q. b+ `, A3
; |" n! y, ?# C4 i, f- V+ V4
1 Q. w7 \1 }! r5
( Z2 t- G9 V+ B6
/ ~' g; ^# s+ P$ P7
. I: j) n* X% M" S) v6 n8
2 x, Y6 u/ d, K9
10
11
12
13
14
; v4 D6 u, m7 P0 d4 ]! K# R3 H" F15
4 Q& s; C, e2 B16
17
18
# {0 h0 i3 T' M: F$ ^7 R. m19
20
21
) W$ C- v/ A6 n; E, Q8 m22
0 g0 q4 [4 `$ i23
) F2 ?9 `+ _0 x! z3 Z4 o) n4 U24
- ~( X3 s. b% w: S5 k25
# l* W! [: g  s. ?; I+ z1 W; S26
27
28


8 D4 Y& Y& c3 P7 m& O" ]稳定性
8 R) E9 M' q+ x3 h4 e, T选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以
, T% m5 j# s, K) [, _* g* x
; j: |* H% `6 ^& Q选择排序是不稳定的
8 {" r: |/ }8 i" A
1 M( U  n! z# ^4 T复杂度
时间复杂度
; B+ I9 z1 k, J: R  m最好：
) b5 {2 ]8 M( ^' ~
比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2
' S/ v$ B3 Y7 Q# y: Z
8 {9 E7 K4 h' a7 B, T3 h交换次数：O(1)，有序不用交换
; ?  H( s; z" w- \" ^+ g) K
O(n^2)
/ W4 u8 J/ }3 d2 }, i
- n% C8 v8 @  m最坏：
- Q+ ^2 J+ q0 U2 N
  N) O9 z  D' Z7 `比较次数：O(n^2)
% |/ A5 u9 W9 J8 d. B2 R
- g4 N8 R, [$ f. I" r- J交换次数：O(n)

O(n^2)
8 L0 M7 z6 z) [6 m, ]
3 C& E4 b/ Q& R7 D; o空间复杂度
O(1)
$ A0 {# {# s% Y) o+ |# e
; ~& K1 W: I, H$ g1 u" o) a堆排序
思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆

" B% w, @# c7 }: H

操作
9 [. F0 T) c; }( q. t建大堆
单趟排序：
& z# e  \4 k- Z- C+ I+ Z; L; O选堆顶和堆尾的元素交换，则堆尾的元素排好
1 e) w* f5 F* K* P# V每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
整体趟数：
若元素个数为n，则排n趟
7 N4 n) L+ a' wvoid Swap(int* e1, int* e2)
{
        assert(e1 && e2);

4 u# W, B8 K6 Q        int tmp = *e1;
) a3 [. N3 r% d& V        *e1 = *e2;
        *e2 = tmp;
: ^1 ?: Z/ s# i6 @5 d' _4 V}

- ]! U" o4 n& d& kvoid AdjustDown(int* arr, int sz, int parent)
{
, V4 W5 z% l( v0 r7 {" p9 v/ B/ h        //建大堆，排升序
" L7 T; P0 r/ `  s, I        assert(arr);
       
    //默认大孩子是左孩子
        int theChild = parent * 2 + 1;
$ u9 L5 \3 Y. z5 l/ `. v        while (theChild < sz)
4 ~( g2 h7 o% X' Z9 b* V/ `& a        {
        //如果大孩子是右孩子则修正
  w9 v- O5 l/ u9 ^& {  ]/ `  j                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
$ ~8 a+ I: R( b  _                {
8 U* X/ W, z4 b0 V8 ^                        theChild++;
% m1 V3 S8 b9 X" u- F                }
8 i' b" V3 Z- v5 V) A3 k5 M9 c/ c; _/ v                if (arr[theChild] > arr[parent])
                {
                        Swap(&arr[parent], &arr[theChild]);
' s( `" S; C$ y# Q( P1 l& J            //迭代往下走
                        parent = theChild;
7 k$ L: }, E4 s- ^& [- I6 I  F# V; ]                        theChild = parent * 2 + 1;
. q' ]# D' Q  z& q' Y                }
( Q, h2 B- ^0 a                else
: @% w. |% _; }' z; O6 k                {
3 n! k! S% [/ E$ \, P- n                        break;
                }
        }
}
* s; \- U: d( x2 ?  L' Q  K4 p
void HeapSort(int* arr, int sz)
{
        //1.建大堆
        int i = 0;
        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
        {
                AdjustDown(arr, sz, i);
+ }! [- w1 _2 @1 u+ b        }
, H4 k+ P6 C8 p8 p+ ^) C$ l! _! j
! p: i( W1 U( Q, ]& J  m$ c        //2. 选数
# S1 F7 ^, t. a- I3 T! n3 h        i = 1;
        while (i < sz)
& A& z& p" V2 Y- v+ r        {
7 R% J( D/ v9 L$ L                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
; K  X3 c, b+ f9 @3 @                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
8 q6 b9 M3 Y& ?7 k! f& W2 @5 k                i++;
        }
}
* P1 c! t% G: G5 o
1
' P7 K2 _6 M, ?! k1 b% u/ ^2
# \& S' u- S+ L, `6 R3
4
- d/ ~% T1 t1 I9 ~7 d. A5
- }7 m# C2 I; s6
" }- H& {- n2 m4 _7
8
) t$ A" d, h! k9 e9
10
11
12
13
; w) ~# M4 _3 R& l4 n0 M( `3 y- z14
8 p2 F+ i& a3 r: ~15
& J" `8 B! _: v16
( Q' ~7 V4 f  b17
18
* s1 R2 h, }; Q; n3 G) ]' y. x6 N19
20
" w) p% T8 d9 p21
22
23
24
% p# G5 h  e1 o6 I8 W25
/ m! Z+ z# L8 e% B% b26
27
28
. z) l* e) r& Q( P" L$ v29
30
& b7 c5 G; u% g# [, y31
" Z% T* v# R! a5 U1 \32
33
1 r/ a6 `2 W8 f34
35
36
37
38
39
+ }0 m2 F( e% r1 R40
' J( Y5 M+ R: c1 Z: f$ w41
5 d$ X, \: u2 j42
, l! M9 e7 P3 V. l$ L/ M. v43
* T# }" G' e: _8 @, X44
45
46
47
48
$ _2 N5 r4 r" j% _8 P49
50
51
; f3 R1 g! c" I52
6 x' W4 ?( U" S5 J& {; G0 [53
54
55

/ u% g4 R: ]. S( ^2 ]  O. c: _
2 R$ C- W, {3 V) L' y4 Z; a! x稳定性
建堆和向下调整都会打乱元素顺序，所以
. [, }$ D' ?8 ~. @
0 l$ H8 z. @+ x# I% i堆排序是不稳定的

复杂度
0 z' {: [" r* x8 m5 j时间复杂度
单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为

7 L9 [, s* z* m3 e! \O(n*logn)

空间复杂度
2 L- o$ [; q/ r: X9 h6 K6 f* g原地建堆

, n' c/ V7 G1 P) ]/ [8 xO(1)

. a( i; W' y# }+ d交换排序
冒泡排序
9 f/ w0 o/ ?0 @/ W4 q+ x1 D思想
7 z- _8 R# M2 [- J2 d冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素

) n2 Q3 I+ b; o4 f

* }) W2 I, J- M+ v2 T. Z2 w操作
6 u6 }; P9 B7 ^4 |$ o, E单趟排序：
" S; ?! U8 l& q; g+ _6 I每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
$ a  T( u7 H, M- r5 ]2 o每趟排好一个元素，所以需要排序的元素每次减少一个
整体趟数
若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
. G0 K% I. z& z2 D7 Xvoid BubbleSort(int* arr, int sz)
{
8 ?3 B  q1 _- P0 Y5 a! I* Z2 W        int i = 0;
% K9 U: Z( u: o$ [# U* ]! e        int j = 0;
        for (j = 0; j < sz - 1; j++)
        {
7 K* y& ]6 X( m5 h3 q                for (i = 0; i < sz - j - 1; i++)
                {
                        if (arr > arr[i + 1])
7 l% T% s) A  n/ w" H8 J                        {
                                Swap(&arr, &arr[i + 1]);
                                flag = 0;
! o1 @3 _9 a3 a! K" L3 j                        }
                }
' V, f3 [' ^8 R+ u; q6 X        }
% g. s' z0 `" L) K}

1
7 [& |& c  G( n; y+ R2
! l: Y8 {; Q  M0 W$ y9 o3
4
) i) `- l! n- e) ~+ A  t& ]& N/ {5
% ]9 p4 L0 G/ z+ h6 z* M0 S2 D6
8 d3 _/ _$ H; d) N6 g7
8
2 {0 f& M2 p0 x4 e0 v9
10
( D, H/ G* b1 q% n11
12
+ b2 _1 W+ e7 Z& R% E: o13
14
15
16
优化
当遍历一遍发现序列有序，直接跳出

) w2 x# N; r: d' Y; m9 {void BubbleSort(int* arr, int sz)
{
        int i = 0;
        int j = 0;
        for (j = 0; j < sz - 1; j++)
3 g7 W/ t6 B: s  l7 |0 e        {
$ F9 ^: j6 j  p& Z6 y                int flag = 1;
9 t0 Q6 E: \' Z* k, @                for (i = 0; i < sz - j - 1; i++)
0 D. S" X, J6 [. ]  H. h, U" K/ n; }                {
+ o: @) F+ p7 i$ p! t6 ?, M/ s                        if (arr > arr[i + 1])
. L3 [% P+ L9 j& E                        {
5 @, t) |5 f9 A7 Q5 U# d                                Swap(&arr, &arr[i + 1]);
                                flag = 0;//不是有序就置0
, o" {3 ]% ?! ^0 b                        }
                }
                if (flag)//如果一趟下来还是1代表有序
                        break;
( f( A( X5 R1 e/ S" K8 M' e        }
}

1
& C1 \( O* T  e" P9 j0 O' b4 a2
3
4
5
6
0 ~2 K9 a% k" S4 n+ S" o7 c7
8
9
10
! m. g% M9 x) `2 Z11
( Z$ [7 P, S) j$ i; u; {12
7 c5 q6 E* \- y" ^4 p! j13
1 g7 _6 w. z( V1 D14
, u! v/ t- U" J( V15
4 \8 N: z8 e0 Y) o* W16
17
( N7 G. ^/ M9 [6 `0 Y7 V3 S18
19

2 ]6 E3 \6 i- I3 I) Z
稳定性
相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以
+ ?- T3 X. X6 e6 I
冒泡排序是稳定的
' y1 g5 x5 ?8 d  H, g* I  M: c
: s* Y- J. Q+ k0 s复杂度
时间复杂度
! K4 e8 M& ~# L9 m1 N最好： 当序列有序
$ D4 Q8 C" ?( q& l0 f
未优化：

8 C$ E1 J) Y. k5 i3 T" r% \5 aO(n)

优化：
' L0 n3 r) P: `5 }% f4 b0 G9 r
O(1)
* S# l4 U9 e+ F( I& `
最坏：要进行 n-1 趟排序，每趟交换 n-i 次
6 c# d( _! q) t
, [  K2 N' @- F) d+ \" nO(n^2)

空间复杂度
O(1)
& @) B( d( a" u) T' J. d
快速排序
思想
分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。

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

; `5 U6 E" q, `5 A+ M) Z- _8 {操作
有三种单趟排序的方法：
; Z) o1 \% L% j, u) Q, s
Hoare法
3 X1 G0 ~3 J0 f# A8 V7 _设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间

1 i4 A2 h* ?7 ]- l) @0 n左下标 L = begin，右下标 R = end

设 L R 相遇位置为 meeti
( e2 [3 n7 y8 S/ h
​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”

; s5 v, J1 u/ S  o+ _6 [​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“
3 V" F9 Q% o1 n! M" f- R( Z! |% e) T
选 键值的下标 keyi
, W9 m! o3 E" C( V9 W7 }+ }
$ }/ C( H4 E/ B# d/ t左1位置作 keyi，则 R 先走
1 Q8 S- g( t: o右1位置作 keyi，则 L 先走
" z' ]* D% C. G  AR找小，

  K9 a" |: S- w6 U找到则停
) k1 Q. ?: D7 E8 |  j遇到L，则交换 arr[keyi] 和 arr[meeti]
! Y5 g! w6 `! V3 Q. f, ~8 _L找大

8 M0 v6 O, S1 [9 i8 M) r( V  j找到则交换 arr[L] 和 arr[R]
遇到R，则交换 arr[keyi] 和 arr[meeti]


8 B' q- `+ |2 B. W0 F解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
4 n  j* D1 m/ M6 T3 s# F+ j; d( y  H. y答案是肯定的：
1 O2 [9 u( V+ x0 z5 j, p! l! @
8 s2 K- J& _" U1 o4 f# x- \( M


//[left, right]
int PartSort(int* arr, int left, int right)
{
7 B6 a: z6 R7 s4 c! O5 s        int keyi = left;
5 O3 E1 P" ]+ T; W; B2 e3 i( O        //相遇则排好一趟
        while (left < right)
! t" a' f! J: r2 |7 A        {
) t! t  W* C. K9 \( l4 S; h2 Z                //R找小
- T- E" ^+ C( ~, n, o        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
3 T4 i, S: y* x        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
                while (left < right && arr[right] >= arr[keyi])
                {
                        right--;
+ L0 K/ X  S5 C8 P8 e6 ]                }
' H1 T# j; r7 z8 h8 L- v- W. o; k
                //L找大
                while (left < right && arr[left] <= arr[keyi])
                {
) {! `6 m2 {+ p, H1 _                        left++;
                }
               
! H! J  a6 q- k5 w        //相遇就不交换了
                if (left < right)
                        Swap(&arr[left], &arr[right]);
        }
% X# n9 z# D/ `$ R, x+ ]
        int meeti = left;
* R% X' y* f" [2 o8 s* G/ i0 J
        Swap(&arr[keyi], &arr[meeti]);
) Z* a; ?8 E9 v/ x+ N; u2 m5 V
        return meeti;
}

1
2
5 u8 p0 v  L1 O' w& w0 f3
4
5
. v& T9 i/ o$ A6
7
8
" q9 C) M' Q' Q  N# S0 B& [' p9
10
" c7 L% J3 Y9 t! Q! f+ M11
12
13
* B/ z/ }* q- b4 o" W) K14
9 Z, h# a$ g* S: V15
16
3 I7 r6 v! T% T+ o17
18
19
" ^% Y* y5 ?! j. s9 W- _20
21
22
' N* ?2 j! E+ f( @* \# N/ C23
/ o( e. ~. {! _9 M8 T( z24
25
26
27
28
8 R3 R. [/ ^4 i# \! F6 h' W; S29
30
31
. `1 S! g" i3 ?$ |" t4 D; M) h32
- }! g, x! u. v) o, t
* B# T' N$ S; n3 _) _" b
6 ?& j2 N9 b8 o' q- K: r4 {解惑：为什么key要选左1/右1，选中间不行吗？
7 K3 y$ r: \8 g; K$ Q
7 i5 [" y3 j1 ~, k
* s% J; p* `0 R可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深
3 I! [$ h; G8 s( q: i5 z# _# v

0 r- |; ~7 i# ?: C$ o9 x# h9 n
+ g8 B/ Q# ~. G+ @0 X
非常容易栈溢出，怎么解决？针对有序情况，优化选key
2 O# |4 k& c5 s! f. ?% x0 ~
, s" L0 Q% c2 o: F! S9 d8 F- W优化选key
随机选 key （是一种办法，但是不那么彻底）
$ B3 x3 t. P6 L: R  X# f" ^- N2 K# L: l7 w选中间位置作 key
* h" ~! ~+ Q; g解惑：那先前实现的单趟排序不就失效了吗！
：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑
% J& B& e7 V$ L, X; W5 ]! v
解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
前辈给出三数取中的方法

- @  T2 [8 U0 A& p6 W  x) D! i三数取中
3 H. S9 u! Y5 Y6 C5 J, w5 l0 _在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
! \& R  U! W6 B优化选key后的Hoare单趟排序：
5 ]  Y6 n* C0 |1 A
" ^4 J8 J- z, L. x) r# _int GetMidIndex(int* arr, int left, int right)
9 O: S/ g: Q# J4 {$ H; |# q{
        int mid = left + (right - left) / 2;
//  int mid = rand()%(right - left) + left;//增加了一定随机性
) h9 v9 i  a$ I; m4 R; \' n        if (arr[left] < arr[mid])
" s9 \& k# B: c& {7 O' T        {
7 N" b# B* q, d/ M! |. [+ |                if (arr[right] < arr[left])
                        mid = left;
                else if (arr[right] > arr[mid])
                        mid = mid;
6 i+ r; N: P& g5 B, R' t4 ?: m                else
                        mid = right;
* }# J, J5 ]; y( Z6 W        }
1 `) U$ k4 c5 v# ?1 ]        else//arr[left] > arr[mid]
        {
8 F1 O/ h6 y/ M. q; j                if (arr[right] > arr[left])
                        mid = left;
9 a' L( e/ V' |5 T% Y                else if (arr[mid] > arr[right])
& E5 j% e8 k( l0 H% e& g9 E                        mid = mid;
                else
6 |1 }3 ?' h' U. T2 z! n" k                        mid = right;
        }
        return mid;
. C4 x) Y: j, W}
- [4 S7 o3 |- g. H, v& h' K
int PartSort_Hoare(int* arr, int left, int right)
. O7 J8 R0 o5 j( G0 H{
, i5 y. E  |/ l        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
        int mid = GetMidIndex(arr, left, right);
. t# f7 P* `# l
        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
2 I/ A' L$ r+ f8 M        Swap(&arr[mid], &arr[left]);

4 C% ]1 @( e9 J: j        int keyi = left;
; K" P) l+ i" U8 O8 s2 E# w0 Y        while (left < right)
! j# Q  _2 f) l        {
; G/ S- o& L7 B6 G6 i  w  g1 s                //R找小
5 R1 z3 v1 J% ~                while (left < right && arr[right] >= arr[keyi])
                        right--;
4 _$ t+ d9 G8 ~, ~0 D
( L9 @" f: A2 V$ _  t                //L找大
                while (left < right&& arr[left] <= arr[keyi])
                        left++;

                if (left < right)
                        Swap(&arr[left], &arr[right]);
        }

        int meeti = left;

        Swap(&arr[keyi], &arr[meeti]);
- P" a8 b: _2 }, O+ d" w
8 [+ m8 _  e5 X8 R' U1 R/ n        return meeti;
3 I! h9 _$ `- S& y, J. w1 x}

/ ^8 [. c9 @+ w1 J5 M; ?1
2
; ^' ?. B9 L; J0 i3
$ ?7 R' G' s! h. Y- P% @4
0 [# O2 a! n2 z2 v5
: {  f; [3 |& ]2 U5 T+ ^6 C" r- q6
& @$ S+ u% _: l0 I7
7 y2 q- B9 Z$ y0 K8
9
; h' x( Y) W( E8 ~# W! [10
11
12
6 i9 h# u0 u- t' D3 I1 P13
  D) q( V5 ?( \" s4 F, A14
15
16
17
2 p2 e8 `4 C% ]18
19
20
21
22
. J% X0 O9 o2 X4 O# P+ B23
24
25
26
27
28
! w9 P; c0 z+ C# _29
30
$ m% y1 R4 @. k31
32
& j( B7 u3 l1 M, {( m1 N33
" H  J- p# x+ ]% E& I+ F! N34
35
1 F+ p- n8 k, l7 D* h36
/ G* R0 {8 y0 f7 S; @! A37
- P0 W. M+ d  C* }38
& H7 w6 h' A, o9 L" e39
  _+ L7 O' Z/ [! R40
$ T- h/ P# M* V41
42
43
44
) Y7 r: Q) X/ s* P3 ^/ ]45
46
47
48
49
; [* K9 L7 G  m50
: ~5 l# O" h' {4 n( ]51
52
4 i* x7 V9 A0 U9 a. K53
  X" k+ `$ M8 T$ h6 Z54
7 I* e5 o+ I; e* {2 S挖坑法
初始状态：L作坑，其下标存为key
5 F7 P/ {. x# H8 v4 M2 d(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
; A* p/ B" q. b5 D& d: S! l: \重复 (1) (2)
* n  l+ Z& M* X& L3 B最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]
& r, f% g  ^5 `$ Z

int PartSort_Hole(int* arr, int left, int right)
9 J5 y9 L4 i4 M3 }* |{
- F- Y& B( A1 e6 v7 V5 @        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);

        int key = arr[left];
        //L作坑
        int hole = left;
; H. L4 M5 n! t0 S9 x' h* O+ c% N        while (left < right)
6 @) _- h$ {6 T* s7 R$ }        {
                //R找小，扔进坑，R作坑
                while (left < right && arr[right] >= key)
                        right--;
- L; e4 n! |! |: h                arr[hole] = arr[right];
                hole = right;

. [- \& {3 j# g0 b! n, D% r5 C5 U                //L找大，扔进坑，L作坑
' D9 y6 O2 @; ?8 J                while (left < right && arr[left] <= key)
  n8 F9 t* J% l& i, a  @( ]                        left++;
                arr[hole] = arr[left];
                hole = left;
6 j) G% f$ N+ {6 v  \( {! c8 y        }
- H% T: _4 k+ E        //meet
# T1 L; `) C, g6 C" [: u        int meeti = hole;
        arr[meeti] = key;

        return meeti;
}

# T# @! S4 X9 b* h1
2
3
* S% j! t0 b5 K. i+ {4
8 B5 _, Y2 p9 V5
6
; B4 [* i" f7 O( J, b7
8
9
10
5 N4 r7 g5 a& Y9 }" g; i  g11
3 ]. X5 B) ]2 n4 I4 Q% J  g7 c6 E12
13
14
15
* M) R: e+ u4 q$ N7 E16
$ U6 N9 w/ i# h) G$ Y' z* [17
. o$ T8 d$ a$ R5 \' k* d18
( h* I$ ~+ U3 G" h# M. K19
20
+ w9 ~7 H  c9 a* J21
22
9 s7 C  `, X0 \0 z( F23
24
25
: F( \% c, [; [, P  }* U: k1 R26
27
28
7 D1 y3 K3 ^# V2 N, I- \前后指针法
( t2 W. W3 [7 c# {/ m% s此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多

# l, F; s1 C6 t1 @: ?; ~) v7 Ocur找小，找到则停
$ b. d4 B( `, Z++prev
如果 prev != cur，交换 arr[prev] 和 arr[cur]
如果 prev == cur，不交换
2 B) V$ E/ R" b0 P* ]( t当cur越界，代表找完，排好序了
prev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低
: ]5 O! B1 w) ]! h$ v2 z6 l- S7 q
% j6 I6 V* L' i) O, M

int PartSort3(int* arr, int left, int right)
% S9 `( I* S2 \/ @" n$ w# q$ G5 _# {$ w{
        int mid = GetMidIndex(arr, left, right);
& C+ i" d( ^5 @9 @. m& G        Swap(&arr[mid], &arr[left]);
       
( G/ m* g) H" ~, E( }- U& ^  //int key = arr[left];
        int keyi = left;
9 o% u( r" n: J* E  n1 s$ G$ ~
        int prev = left;
$ m$ g% B; C2 o' U" t8 F8 d' A" K        int cur = prev + 1;
( r; J. ?- D# w5 t5 @, @; B7 A       
/ x2 \, w; Y" w    //cur越界：找完小的，prev的左边全小，prev右边全大
) \+ N; w5 H* n4 C$ S, U        while (cur <= right)
        {
) b: a/ r5 F) F        //++prev == cur 没必要交换
* l: }8 A. X1 j0 Z) ?( I- D, m( |                if (arr[cur] < arr[keyi] && ++prev != cur)               
                        Swap(&arr[prev], &arr[cur]);
/ s4 B, Q! Q/ B4 n8 \. f" a+ d
                cur++;
        }
) C6 v2 N9 ~3 }* V( H/ `, ]& o
        //键值存是的值：
) D+ i; a. z% g6 N        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
: l, V( `. r5 S# R0 ]" J        //Swap(&arr[prev], &arr[left]);//这才对
    //键值存的是下标：
% M/ z  G* |- O0 o        Swap(&arr[prev], &arr[keyi]);
5 {: Q/ Q! a1 V. a; S
        return prev;
1 V" ~: L0 ^) h8 }6 _$ p}

! h- I6 k3 S6 j$ I# @/ F1
2
3
( W- Q3 F9 |# X2 W  c! G! X* U9 N4
5
+ y3 q6 e$ X( u( I: H: e. p. Z6
7
8
. g( k6 ?. d( k) j2 e9
* R3 ?  A' c) ]8 ]4 I5 H/ e10
: [/ u( ]# _1 B  e11
12
( i, ?- z! W" X. v13
/ O- e" _2 v, _, G# P6 A: ^$ b1 u( L14
15
16
* v) C) r: r' ]  n8 H17
7 g- G( }" s" W5 A18
  u" f' I+ V; q19
20
21
' G1 ^3 c* I( w2 v  [22
23
24
! ~, I( g, l: s6 l' w25
$ A' @4 q; m- P# d4 K26
# C; p2 L  G& J27
! V9 _# y( N! S% t$ y! x2 b28
29
/ d( n$ S6 ^' y, O) |) {: m$ \整体排序
递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排
/ @9 w8 j" q9 @/ K7 {2 U
" v' y  s; N( o7 j$ ^# N& `- R//[begin, end]
void QuickSort(int* arr, int begin, int end)
, x; z5 W. z6 ~{
        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
        // [begin, meeti-1] - meeti - [meeti+1, end]
5 o8 d! m  [* Q* N+ W+ m                //1.begin > end:超出范围
                //2.begin == end:一个数天然有序
% v, V- V7 d+ G: y    if(begin >= end)
        return;

4 Q0 |9 m% s  |5 v  U% l+ I                //排好meeti
( s9 Q8 U6 i$ I; ?! f7 k                int meeti = PartSort3(arr, begin, end);

( _4 }0 z$ l1 |/ o% q# v                //排好左右子区间
* \5 A4 L4 ]5 l+ t4 d                QuickSort(arr, begin, meeti - 1);
1 m3 H* F# a) l# e+ k                QuickSort(arr, meeti + 1, end);
        }
}

1
2
( q- d& n9 [+ @1 j  X" s- a3
4
5
6
7
0 s3 ^' s; `. ^3 _8
6 G% @! e9 H/ D  ^4 s) U( C9
8 M4 ?' O" k6 @7 K10
11
* ^" e. C* w$ H; z" r; m" o$ d12
13
14
15
16
) L$ A( C& H7 y) u- O  X17
18
; W* V1 G7 ~9 c  f% {; ^…
% r; c) L- T/ }1 b* r+ n
没想到吧，还还还还有可以优化的地方！
' i4 a, ^7 n6 a/ F: A
: b9 b2 \5 P& P2 m! E8 [优化小区间


& {1 R6 {1 K0 T1 `5 v! ~: l如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序

那什么算是小区间？
3 A8 p& ^: }3 P1 a: k8 }; }
其实小区间没有确切标准，8-15左右都可以的
( F6 g* P! x/ U! V

1 i8 L+ v# j* v' {这里就把小区间定义为 含有 8个数或以内 的区间
2 d; u$ I: s  o; r! X: e2 J1 _1 b
//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
        if (begin >= end)
                return;
' u2 i# I4 W2 e( z8 V
$ S3 e0 B9 E* K6 D1 D5 S9 x; N7 \        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
! b, R) C+ l8 I. o7 o# O' ^5 i        {
0 g# d1 H. V6 x6 w( O5 L, j% a                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
$ d  ^3 _2 i! S        }
+ L7 e$ B; E" i8 J( G        else
        {
                int meeti = PartSort3(arr, begin, end);
' I& P' E" |! ?2 A) s
                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
$ C. S/ \- [0 H. `! c. y: T, ^        }
6 E$ f: q! b. e7 x! u8 I}
% V4 O( Y  H% t* h0 H+ R8 _& l0 \$ C
  u( ~& m* M' o% O5 \/ a6 X1
. b8 X, N' s8 m) }' O+ v2
3
5 J& u/ P8 }* x. ]  u. z* w  M7 l4
# Z1 ^( o$ J# f* ^: ]5
6
7
8
! i; Q" i  E5 A! K4 y! x% n9
; c: B' c0 U: T5 q: w& l10
# c9 y; H6 Y' P0 ~9 O4 F11
1 D) u& {, l( l, R# a12
13
2 ^  M  ~1 N: T  Q* J; ^6 z7 W14
15
16
3 z( A  H* L9 y6 J6 y17
18
19
快速排序非递归
为了解决彻底递归深度深的痛点，我们来试着把它改成非递归
/ x8 J" z  i- q4 F- T$ q3 @
& I7 p6 s0 H6 O/ X思路：
递归深度深，栈的空间又小，会栈溢出…
+ {3 t# T, Z3 F( f
那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！

核心思路：在堆上创建“栈帧”
0 u; O$ B3 j5 U6 Y8 P5 ~) @2 i
% A! l6 r, l$ N4 X& O快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的
( ~. Y" e7 {! J1 M4 S
3 J4 f$ q3 f2 B& N5 x7 Z
# c' F& H# V5 r' X- R3 D$ ^
在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：

# x* Z; l4 x' L* E1 j先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
! ^/ E6 S$ H! y{
5 f  D4 `+ b8 K* ]8 s        ST st;
        StackInit(&st);
       
    //先入begin
+ Z! y3 t0 d  J- ?& T        StackPush(&st, begin);
0 }; C3 G2 c$ Y# C    //后入end
- ]) F4 j1 S4 R. E" {        StackPush(&st, end);
5 ?& o" N( L4 V, r5 J' Q
, u9 u5 l" q$ S4 \/ N. v4 ?' R+ `        while (!StackEmpty(&st))
# w/ k1 m1 {* V9 _( m8 ~% }( K        {
3 N0 z1 U! V5 ^7 F+ ~6 X, z; c$ K                //先取end
0 s) H( L* |" l  x1 a! t                int right = StackTop(&st);
- I" d9 D$ @0 e* r: a/ R0 t                StackPop(&st);
                //后取begin
' ~' N7 ]* }/ g+ _) E8 X5 @9 g                int left = StackTop(&st);
                StackPop(&st);
! @) p) Z  ?/ [
1 [3 y- m4 i7 A. H/ b& f4 ]' Y9 n                if (left >= right)//1.只有一个值  2.区间非法
                        continue;  
                               
                int keyi = PartSort_Pointer(arr, left, right);

0 D/ O; u7 [1 F: ]                //先入右区间
                StackPush(&st, keyi + 1);
                StackPush(&st, right);
                //后入左区间
                StackPush(&st, left);
6 ]- `9 c- S% P1 T
; x( S9 B9 n8 i: U                StackPush(&st, keyi - 1);
+ O' J1 i$ O7 `& I        }

& R2 L2 }* _. }' \# _        StackDestroy(&st);
}
/ U  W! w6 p+ H$ n; B5 e# H
% N* W1 b! b0 @7 ~; g7 y4 h1
  v0 C1 Q" D, x* V) d. L& H! y2
( l) \" t1 }, \. z; c' R3
/ A+ b* P9 R6 N- ?/ c9 q2 _4
5
6
7
2 H9 P3 i# Y% D- q! Y8
( R; p$ S% t1 e6 |8 W" w) \9
! U+ x% O3 [, H4 f; p7 ?10
11
/ q; w/ ^; b: h+ u0 R12
, B! k4 }) Q  ?, a$ j- r13
" ?* ?9 m6 ?" L' e  M7 g2 v2 r6 {2 O14
15
" {' r1 L& l' {( q7 }16
7 B3 ^# |( N6 Y: v4 C17
( y: s2 W9 c' u; t) L( i0 ~6 C18
19
. O, v" J- v+ N: T/ N20
/ h* d: a' s. O9 l1 T5 E& }21
3 F) g# X3 [# D5 u, ?22
23
24
25
. X- @, a8 [/ N; x, O; Q% i$ l: H, F9 R26
27
28
* W* m- O3 `% u& T7 X) u& w# p29
' `* p8 b/ o' Y, S4 O$ {- D1 z30
. |" v( ^, Q7 A. M31
32
& \+ E4 c8 E% G; _; g33
5 N7 _% s: D" W  L& x7 Z34
$ }4 f4 i& b* ~35
数据结构栈的实现可以看博主之前发的博客
9 }& u6 c( `! Z% D/ ~+ n0 u& {
( @+ g. g0 ^0 h5 l& ^; @: N
归并排序
7 l& N$ ~& @1 C/ S
…
" ?1 A" [. A; @3 [5 _+ s
! G& p& C1 Y0 Q0 k! P2 z性能测试
void TestOP()
{
        srand(time(0));
        const int N = 100000;
5 F$ r- k6 V0 }% f        int* a1 = (int*)malloc(sizeof(int) * N);
        assert(a1);
) Q) h, J- p7 c/ K) t& l. n        int* a2 = (int*)malloc(sizeof(int) * N);
        assert(a2);
6 s/ a9 q) F7 o# @        int* a3 = (int*)malloc(sizeof(int) * N);
2 I5 a0 c" Y5 Y* P& c5 W; K        assert(a3);
        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
        int* a5 = (int*)malloc(sizeof(int) * N);
        assert(a5);
/ C, r' o% E! F" L
        for (int i = 0; i < N; ++i)
        {
                a1 = rand();
                a2 = a1;
# V5 m6 m& K+ _4 g5 `, \. [4 ~0 ]- ~                a3 = a1;
8 Q4 M; n: ]) _/ I% b                a4 = a1;
                a5 = a1;
# U& \0 k- ]* l3 {        }
5 K  m$ k& E9 ^
        int begin1 = clock();
( j! p* E. v2 ^5 u7 v        InsertSort(a1, N);
6 U  T% |9 X) b; z9 U        int end1 = clock();

        int begin2 = clock();
        ShellSort(a2, N);
6 @+ l+ c# n6 k4 ], L% D8 A0 d) n& i) Y        int end2 = clock();

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

1 S4 @. ]" x* U4 f5 `        int begin4 = clock();
        HeapSort(a4, N);
9 o) H5 |0 Y* k        int end4 = clock();
! Z9 I0 r+ A; J* c
        int begin5 = clock();
        QuickSort(a5, 0, N - 1);
7 g$ h2 f' r* k4 M" J4 @( o8 w                //1.中间key
8 P  [3 ?4 u# C) q! E4 C                //QuickSort(a2, 0, N - 1);
  @/ O; V6 }" ?  [4 i. z                //2.三数取中
                //QuickSort(a2, 0, N - 1);
                //3.小区间优化
& [$ w1 u2 ~! P, t                //QuickSort(a2, 0, N - 1);
        int end5 = clock();


        printf("InsertSort:%d\n", end1 - begin1);
: L' A1 g( m# ], J5 J) p        printf("ShellSort:%d\n", end2 - begin2);
        printf("SelectSort:%d\n", end3 - begin3);
        printf("HeapSort:%d\n", end4 - begin4);
" d) a* j/ M) r        printf("QuickSort:%d\n", end5 - begin5);

3 v7 m. O/ R& A% E: [# L$ ]: V        free(a1);
. |6 d( W* q( r        free(a2);
% F: b# u( s/ [5 ]$ T! M5 v1 c5 e        free(a3);
        free(a4);
5 f2 ^5 ?2 t1 t' @$ ~( l& ]) y        free(a5);
}
; c% z" O: J8 q* n5 P
1
' j+ u6 M" C6 Q+ f6 X3 z2
4 f2 D( D* D/ [+ q) h$ t3
4
5
6
7
8
9
2 f/ e. z0 y% @) x7 U3 X; E+ n10
11
12
/ [& g# t( n( ]  o9 {* C4 j13
" P2 Z. k" [1 y1 }$ n- V+ T# c3 Z0 h7 N14
15
4 l% D1 E) q+ W* j2 C" [- M. B16
17
, a6 W0 |) \; j' N18
; k- V& `4 M! n# T19
9 ~( X# {# n8 K( |2 N20
21
0 E: X! ]6 L+ o' k* J7 c22
23
& K9 w: v! w6 {0 D* y- R8 u24
2 {: [! Y) ]% R; e" g25
26
- z; G3 S4 n- Q9 ]) u: c2 x1 W27
28
29
30
- `9 m5 j$ ~8 p" U" u; g  c31
32
+ {  d/ N$ _  u2 E5 V1 g33
* ?! t2 `- `# c$ u% {9 |* p34
35
36
37
38
6 J& a( O' h' }; p* d! H$ ^' \' b39
1 ^; h* a% T0 a! i( z4 W% L, |6 V40
41
1 I$ b7 x' J; E42
43
! r) k- N0 `, @0 l( T8 ?, i; o44
45
+ ]+ T! M/ H. L, u" x7 ^  [, O46
47
48
49
% I) ~2 _) o  b9 R5 a50
4 p- a" X; d- Z& _' i/ K, N51
52
53
54
55
56
57
58
0 i! V# m2 m7 N59
60
* W3 ?  Z% c; F9 ~$ b' x0 k61
# |2 t' x4 t) O0 z62
1 g+ a5 j/ z2 D" i; D5 H63
9 m+ U9 c# ]& Y4 ?# q3 X
; |1 h9 s  s9 @
" k' F- {! P/ B! ]9 r不愧我们费这么大劲优化快排，多帅哦！
5 D! Q/ D8 p' z. b/ N
差一个归并排序，后续补上！

不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
————————————————
版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 L1 @6 w/ r8 i& Q原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832
2 _. W5 @; }9 g! W* i. R+ e9 P
0 g6 d+ I  O7 Y