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

杨利霞

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

# o, }! j9 a9 |# X9 S前言
本期分享经典排序：
. y* Y. X/ D* X  B8 B! P
插入排序
3 J" H4 P0 v" `# e直接插入排序
希尔排序
选择排序
直接选择排序
0 O  w+ l9 h. X% F堆排序
交换排序
冒泡排序
快速排序
; ]$ Q' T# [& Z注：讲解时默认排升序

插入排序
2 ]) O- i$ @; Y8 z直接插入排序
思想
插入排序，就像玩扑克时，摸牌的过程：

最开始，左手没牌，右手从牌堆中摸
) Z, i/ ?% y9 E右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
如此一来就能保证左手的排始终有序，摸完牌后也就排序完成
& y# j; T' V3 E$ _
, m  z- l4 O  h' Z0 x
. ]4 ^% p; I0 j- P% E, S& n操作
设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
单趟排序：
4 z3 z$ G7 r* S每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
是正确位置：插入
不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
% H, C7 C$ K3 K( T+ A整体趟数：
' Y9 g: j% e- @6 J, b若元素个数为n，需要排n趟
1 E! N$ K1 q- |0 r) ]/ mvoid InsertSort(int* arr, int sz)
{
        //end + 1 < sz
% m6 q) D" g5 M8 y4 ?        //end < sz - 1
' f  ^* ~: F- h        int i = 0;
) R. e; z- {8 k; o- k, K, ?2 d: c        for (i = 0; i < sz - 1; i++)
/ g  D- n) A) k8 K# `' z        {
7 t& g0 c2 O3 v" S6 |7 l% [2 d# M                int end = i;
; x) T4 V1 _% z2 Z0 U                int tmp = arr[end + 1];

( Z$ F- G5 L) R2 a                //找插入位置
                while (end >= 0)
' L! v$ {4 b! s1 J                {
                        //不是插入位置：当前数据往后挪
                        if (tmp < arr[end])
                        {
                                arr[end + 1] = arr[end];
. R4 G( X+ X0 W& K                                end--;
                        }
                        //是插入位置：跳出循环插入
                        else
( U4 ^( K' _2 y                        {
                                break;
' G( y' W& g; v: U9 z0 l6 ~                        }
" ~/ U! G9 \9 @- ]# G                }
1 H7 Z' W; @- ^$ C                //插入
9 k9 ?3 s  V  |4 G& v! S& d                //1. 插入位置是[0]，end == -1，不合循环条件跳出
                //2. 找到插入位置，break跳出
1 v( V7 j0 h: }                arr[end + 1] = tmp;
        }
}
$ s6 U. {0 F' C- t* A5 y2 i7 F7 Y
) ?/ Y1 Z7 @7 x. z1
# [2 o( {" u; t# |! s5 Q0 f5 V2
& y5 E" s4 x# ~  S& k3
4
. r* z+ r# r' c! g/ ~( h5
' x# K! A. L- @+ H7 j/ U! g# x! K3 r6 s6
7
& G. J9 H% ~" S  m/ Z/ a8
* A$ B! v  l6 u# P2 M/ l4 @9
. [' r& a. v2 k10
8 T  S/ k. U9 M% l* A4 n5 J6 ?11
12
4 X& C( x% H3 W) o# K( e/ f13
* U: I& \# q, ]  b( y' a# \6 W14
9 G; e! Y" h; o8 X: A15
6 T/ s" J0 U3 n9 o3 {# }- g( m6 O% r16
, i" `' a/ Q+ o) C# @17
$ P1 t: B2 b0 g/ Z% Y18
19
20
21
1 ?, U' n4 j" R8 b. y8 ]& V22
23
# w3 c. E" c. b( @! H9 E! i1 t24
25
26
& ~9 }4 J* r6 v$ o* T27
28
29
( n( ^& A6 g# e30
* b$ a$ I; K* g+ g31
; A( F$ y/ y9 q

1 c4 [* g' z$ G+ T& F$ Q* [0 v; Q+ n$ E/ N稳定性
# g# P0 M' J5 N插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以
. X/ X! S( C- |# p. i9 A1 R
; x' x8 Y0 o. B' J5 n4 A6 S直接插入排序是稳定的
; E+ l+ |& g+ A) G
复杂度
时间复杂度
" Z. [* {) {. k最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）
( I" Q# O$ s) I# V4 o+ X, F
O(n)
) B- n( F, ]' e" j: t
+ [8 f* u& H6 ?: f: Q- K( j2 |% y# R最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2

4 n. V0 X2 Y4 g5 U8 `, |' K7 i7 TO(n^2)
) e8 @' v8 ~5 G' r; @4 `5 X
空间复杂度
4 S% B9 r% F& f% W( R" QO(1)

希尔排序（缩小增量排序）
希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序
* Q% M5 t! c; m7 P
优化思想
增量gap不止用来分组，也意味着数据移动的步长，所以
2 o8 a7 k+ Z1 \) t# V3 b$ O4 y3 v
: r# u9 F) G. v& p& Dgap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高
7 k# C! g7 ~/ q4 t0 ~, }

8 |5 ?' E3 i9 ~! G  K操作
单趟排序：

. [- O7 [( V' X设定一个不断减小的增量gap，也是元素移动的步长
0 e2 ]0 |4 G+ G) G以gap对序列分组，并对每组分好的序列进行直接插入排序
不断缩小gap，并排序
*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
: {6 u( V& N% c7 H& v" E) t# m整体趟数：

由gap决定：当gap = 1，排序完成
# z+ T, `' \' k/ X注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。
( ]  P# H2 p: B! Z* H
void ShellSort(int* arr, int sz)
* n) A3 T" V- i+ A/ t9 P{
( a1 R& r" u- w9 {        int gap = sz;
       
    //gap > 1，预处理排序
    //gap == 1，直接插入排序
        while (gap > 1)
        {
0 b. a1 D# n7 u( R9 i7 t0 y" M                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
                //gap组
                for (int j = 0; j < gap; j++)
2 B$ I: c; k6 `                {
7 ?( ^' v/ Z" R3 H* V+ `            //end + gap < sz
7 f8 ^5 [/ t4 O/ ]/ z7 r) ^9 F( Z                        //end < sz - gap
' C4 h; {8 J$ r4 v7 K" P: o+ x                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
                        {
6 e$ r  U# s6 \% b; ?' _                                int end = i;
                                int tmp = arr[end + gap];
                                while (end >= 0)
                                {
                                        if (tmp < arr[end])
                                        {
                                                arr[end + gap] = arr[end];
                                                end -= gap;
3 S( e6 J1 U2 M                                        }
                                        else
* H) E7 W: t* U; c; z: b0 q                                        {
$ M% ~# W5 U9 ~  c                                                break;
                                        }
6 i$ S# Z. s0 T                                }
( J: Q+ d1 i8 q/ |) b                                arr[end + gap] = tmp;
                        }
                }
9 n# ?1 ^: [' K, J2 V* j% e: z  L        }
}
. g# u# g2 F( B+ }, d9 m+ |
  L3 ~6 n2 M4 p4 F/ x. T# @2 e1
2
; i" Z! w. i  b" d3
! u& K1 g- y7 b9 F* H1 ?4
' L$ P/ {" \' O5
9 ^& v4 R0 l+ r2 T" d6
7
- v7 {5 U8 Q) U8
' M) G4 E+ k6 ~* F! k' [- `9
10
11
12
3 V$ i- N4 D# Z: C3 d13
14
15
16
17
; |: {6 x* A2 I5 q18
8 K$ R8 x: w7 X0 v, o19
) s3 k0 |3 D4 @" M2 d2 J20
21
22
23
24
$ |& M7 |* n; g+ Y. Q  m' [25
26
27
6 w9 I+ U& ^3 _% S3 H+ L28
$ Y8 F# J$ V0 i9 U6 y" z4 W- W29
30
31
32
0 ^$ D- e' A* n- q33
34
35
其实就是套上”缩小增量“的直接插入排序
. |. c7 z+ J7 [
# x+ q1 @+ C: m8 `9 M: E
稳定性
我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以
  C7 P: ~, e4 Z6 L3 Y' b1 X  R
' i0 u& G2 s' D* g( c希尔排序是不稳定的
1 Y! S" i, Z; z3 Z" H6 ~2 ]
复杂度
7 t' x; P) |4 C5 q+ V时间复杂度
希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
& v& p; t; C4 z% P6 K
8 n. O0 t9 O1 F) _! a5 }O(n^1.3)
3 \/ a( r: |% q' V4 u: j
空间复杂度
3 _  e% _0 r/ f' a7 k7 HO(1)

* ?: J8 }6 L# b/ \选择排序
  o4 ?' g' j  {% ]% g直接选择排序
3 r) m0 o* I) P( P4 R/ F# A2 A$ u- d思想
- w" H- S8 k( `) f0 @选择排序，遍历序列，选出最小的元素，交换到左边
! q) T& U( P+ \. q


优化版本：

每次选出最小元素交换到左边，选出最大元素交换到右边
9 o: Y) J7 L/ P& P4 [# n
操作
设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]
+ I. n! ], ^- g! Q8 Z, H9 V( Y
设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标
% r5 i0 C6 [5 ~4 A
单趟排序：

! X4 S/ o4 ]% m; |1 ?) Z' {遍历选最值的下标
0 D" T7 x/ j) E/ `0 H0 v& P7 ]: m; r$ X交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
（修正）
整体趟数
' L" l3 I' G3 p
若元素个数为n，趟数为 (2/n)
5 h) p2 S& P' o0 R4 u( q修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标
. F$ e  j6 d+ g! C7 K
6 D: ]8 e3 M7 Qvoid SelectSort(int* arr, int sz)
; ~$ Z& Z) {* a! N) S{
        //闭区间: [begin, end]
8 e* K: W) m0 z% c. k        int begin = 0;
2 }6 |  j! _; \# I* w2 R        int end = sz - 1;
6 k% s2 W7 s3 d0 l6 v) {        while (begin < end)//begin == end 最后一个数，天然有序
7 u5 l3 ^. k, w" z7 u" S        {
                int mini = begin, maxi = begin;
                int i = 0;
                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
                {
                        if (arr > arr[maxi])
' x8 r" ^9 @" [                                maxi = i;
% E+ d& T6 M4 J& G                        if (arr < arr[mini])
                                mini = i;
  I* E7 Q* L; s- v0 |4 S                }
* |& n7 \% _6 m& G# P4 v9 i* l0 w
                Swap(&arr[mini], &arr[begin]);
: G3 g1 [$ O/ e" E
                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
3 D/ X  t+ ~/ ^' ^' R  Q                if (maxi == begin)
6 a4 ]& v& p0 `3 L9 `                        maxi = mini;
6 }; w* p9 f% X$ c$ F- _7 ~7 ^1 C                Swap(&arr[maxi], &arr[end]);
3 ], |1 E% n. C! m# n- \: Z
) s; N, i  w. j; N7 f' S# z                begin++;
, y' a! z! a- n+ t% |6 I5 r8 Z3 B                end--;
4 a$ n$ ]/ \  \# d# ^( J7 |# G        }
}
8 P0 u! `. U$ u
7 \0 x$ z; b! x3 U1
2
( F" O. N2 W* L* a3
4
: ~! i5 X7 P( b# T% N* Q% |9 m5
6
; y- S) S- V1 C' _9 r: K* m7
8
9
. q& [  s1 d! P* D( o! B7 L5 l10
3 U7 l0 k5 ]8 o# m5 V* Z1 F" \11
12
7 r( y3 n% [% R  F13
14
15
16
17
18
: }9 V$ B. |! V8 J$ o19
20
21
. c6 f  m( D: M' l, ]/ A7 N! G+ ]22
23
- c- D' n3 r: m( m! g& Y24
25
% @1 U+ K& N1 o5 ~26
% Z  l) e) j6 g27
28


稳定性
选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以
: ~  {2 Z+ \  h" p( Z5 ~
选择排序是不稳定的

复杂度
# q: I8 d. x" i- B5 J, J时间复杂度
最好：
4 M, s* k7 t: j: f/ Q0 |
! k  F% @3 \5 j  s4 \- N' y比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2

# _3 C$ E4 N( w( q, G4 L" z: Q交换次数：O(1)，有序不用交换
3 T! `8 q9 F" N. i
O(n^2)

最坏：

& g2 a- N( i( @比较次数：O(n^2)

交换次数：O(n)
3 Z5 r) L- i* Q& d0 x$ f+ M% a" L
$ |4 c: W: b) X' fO(n^2)
" |' Y! |; E7 s5 R8 Z
空间复杂度
4 E! D4 r1 x7 Y5 OO(1)
9 Z/ X, i/ M" H: {/ ?
7 [# g* c  c, e堆排序
思想
' E( c3 d# |+ Y9 h1 n/ L利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆
" B" p1 `. T( K* d) a" u/ U
+ I7 }2 Z, j+ e" M' f5 z; Y2 k* C
; c* b# c, j  u7 r
操作
* D8 W& I! W. q, r2 c7 s4 o建大堆
单趟排序：
选堆顶和堆尾的元素交换，则堆尾的元素排好
& B4 M! ]6 }/ t. L. ~每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
) {8 V/ Q* B* p" Q3 m6 S整体趟数：
若元素个数为n，则排n趟
" v4 A* q7 g; p2 a' e, Qvoid Swap(int* e1, int* e2)
( b4 U4 J: N; T{
: Y$ f( W: D7 X# x/ X& `        assert(e1 && e2);

        int tmp = *e1;
        *e1 = *e2;
5 ]  H1 z/ q0 ^3 u6 X: k9 u7 k        *e2 = tmp;
, Z2 i! y2 {( K& O7 n: o& x) X8 Y}
+ I5 s7 |' i3 q; X* p0 g
void AdjustDown(int* arr, int sz, int parent)
; b6 H9 m* p- r4 O6 a{
; E- ?5 \$ Z% x# L9 p7 O        //建大堆，排升序
; q9 i+ Z* g+ d4 m, R        assert(arr);
       
    //默认大孩子是左孩子
2 S6 U+ P, j0 E5 a! }  S        int theChild = parent * 2 + 1;
; M( E. U+ O! k0 ~- D7 _        while (theChild < sz)
# k- R7 ^, S7 N9 l/ E. a        {
! a, j4 T/ K' K& D3 \- P3 G0 @$ A6 b+ C        //如果大孩子是右孩子则修正
                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
                {
                        theChild++;
                }
* L8 [5 \) f4 g/ D/ }; \# [5 ?1 b                if (arr[theChild] > arr[parent])
                {
                        Swap(&arr[parent], &arr[theChild]);
            //迭代往下走
8 ^0 k8 W) y- D0 F                        parent = theChild;
! R- H; D4 `* L                        theChild = parent * 2 + 1;
                }
: z3 y$ U( P; B                else
                {
3 E) p5 t, s! Y* K. W. k                        break;
                }
        }
( `+ x: u$ x  }3 U7 {1 [}

' t  `* q. c  pvoid HeapSort(int* arr, int sz)
{
, S5 i& E0 P* g5 p: K        //1.建大堆
; a$ [; Y) z: ?. [8 J        int i = 0;
        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
& G* A0 b( E9 N  G' D% S3 I0 \        {
                AdjustDown(arr, sz, i);
        }
" V% w1 b6 Z0 E- I+ v  H8 n5 Z
        //2. 选数
7 h4 P% z. B/ ]7 c  u1 z  ]        i = 1;
        while (i < sz)
        {
2 i% v3 M( ?: D+ O& z                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
# j9 U4 f$ U! D2 R6 _  n  D; a                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
/ h5 q& w) ~% U5 F                i++;
8 @; y/ M  t" Q        }
6 W8 Z, C8 f  u( R: C! l3 J}
8 m5 F- b: J- f) g
" r, ]  G. F. {# y7 t2 r/ ^0 @1
9 c. ^" n# P# l. n& h' {0 _, l0 k2
5 i& u* T5 a$ I7 z. ~2 W0 k+ r5 i) f3 G3
4
) D) k( J! l" D& L- R" C5
5 N* p" ]8 Z$ V2 [& z& }( K2 R* a7 B6
, B) i  {, S9 T2 C  A+ [! m  B) \7
' ?' M- {$ U6 C3 N) M8
9
1 }2 [$ D1 e( o& t! d( |10
& S1 F2 l7 J/ g11
* S3 ], R/ I% F( T$ N2 i2 I; Y12
13
14
15
3 W9 r( a2 T$ q! E- r2 C16
3 \* i2 _: j8 `' [4 i  J$ R' ~17
18
19
. X: M& k+ i/ ^, ^20
21
  Y! m: {3 W. T+ |22
23
24
9 u! o- ^- Q$ N25
26
27
$ X$ G4 d1 v) [# J5 M28
29
" \) i+ t$ @0 B% _30
& D1 W% B1 g& F  x, e, f3 b( a31
4 Q+ S/ r8 O% x/ R32
33
34
6 m6 ?! T! |5 E' C6 _. S1 t- V, y35
  P+ b- R/ v( U36
37
38
39
3 b, P4 N5 `$ J* A2 n40
41
42
43
44
5 \- E) n- G# [) |45
46
47
! k- f! X) d- |' `8 q48
3 R2 H9 s2 o# L4 Q+ Z49
; ^5 _' _. I8 u3 T9 [6 d50
6 C3 g" o. Q* z$ u2 l8 f; e51
52
53
54
  ?# H( k0 l/ s4 [0 c1 c5 X55


6 V/ {5 s; U1 \稳定性
建堆和向下调整都会打乱元素顺序，所以
. v+ j0 m# |# d" _7 A% V; L
8 r0 v( V% ]: T( v$ M  m, r" V9 ~堆排序是不稳定的

0 B0 c0 n; I6 M复杂度
0 d$ W& C6 x$ e时间复杂度
0 N) ^) E; _' a8 o单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为
; l  Y" j, n0 N2 H; I" H- n
: W1 q% O! c8 U$ A0 aO(n*logn)
  I0 D5 N. y. ~7 ^3 U6 v
5 F* H! D* U# v9 e空间复杂度
原地建堆
" m# `. B. u+ I. `
5 B: K2 `! s) g7 ?( z  Z6 S. M3 AO(1)
/ y6 G5 L% _- k6 G6 e6 @; J8 V$ x
. s- d7 D( \; f* M& G, P* O交换排序
冒泡排序
. G2 H6 w& R1 s" F4 r& p思想
" p% H: }+ _/ W0 f* z冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素


! r0 r  ^# c& z  P- N- g
操作
单趟排序：
每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
每趟排好一个元素，所以需要排序的元素每次减少一个
整体趟数
, v7 C8 w* o3 }7 a% B若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
void BubbleSort(int* arr, int sz)
{
+ x' E6 ]5 ^& _% K/ n8 j' M' p: m9 X        int i = 0;
; H. ~- }& H% |: ]        int j = 0;
4 f$ |6 k6 }+ i9 }; f/ [        for (j = 0; j < sz - 1; j++)
3 o6 z) a) l" e8 K# F: G& X7 {. X        {
                for (i = 0; i < sz - j - 1; i++)
& f4 B! o: X% A; x" X                {
                        if (arr > arr[i + 1])
                        {
% a% T' J  ]7 A: C                                Swap(&arr, &arr[i + 1]);
                                flag = 0;
                        }
                }
        }
8 j. ^' t# v; u- p) \8 G) N}
, b( b% `2 R5 ?8 Y6 k$ G# L1 I
$ l; Q. P( P' F. Y% \7 x1
' R  w- B$ [" `1 A% F2
! \" Z& ~  s; X  c  Z$ I3
" J8 e8 B% S$ u- v$ j4
5
6
7
% K5 j" q; G9 z' u* p: H/ N, S, F8
9
! Z7 n5 j6 M& v/ Q- h10
: L4 N. A+ u& Y2 L: Z# i/ [11
12
# u1 s' V& h: ^% z13
# W3 n) i: U0 B  d3 Y" j: X. {; J14
15
/ c" g' g* ~4 [16
优化
. ^& @$ _  t5 r% f当遍历一遍发现序列有序，直接跳出
" O1 t' K4 p2 H( O# A9 c+ `
+ Y3 k, j4 \0 x$ \2 r8 Y4 C: C) gvoid BubbleSort(int* arr, int sz)
{
        int i = 0;
        int j = 0;
- v0 X- T' ~1 d5 E8 ~        for (j = 0; j < sz - 1; j++)
+ \6 G# D6 W* P2 F3 k        {
                int flag = 1;
  B2 A+ X8 |" p, _8 h% _                for (i = 0; i < sz - j - 1; i++)
                {
3 w; k) k5 ?8 ~. ?! q3 s7 h) y: j                        if (arr > arr[i + 1])
2 {, V  X# }0 C0 B7 ~+ e                        {
& L7 f+ ]& j) M( o' l! V, J                                Swap(&arr, &arr[i + 1]);
                                flag = 0;//不是有序就置0
& h- ^) O2 V; F( \4 X3 r! U5 p                        }
                }
2 |6 G9 [* F3 m! @                if (flag)//如果一趟下来还是1代表有序
( a2 D9 e3 U8 D4 s, f# Y                        break;
5 n) n6 \  k4 w1 d: c! ]2 S7 V        }
}
+ t5 u8 K' N: B4 \4 I
  h6 Y4 z. @4 J  r( J1
7 ?; [+ {+ V6 ]5 q+ \& m& ?2
3
4
. l! z0 k& o; H, s5
& o5 W. @$ @; _& m5 M6
7
" V: V8 o3 F1 r' v+ N! q4 A8
" R- w  b% F* y, h6 H8 c! r9
10
9 _. z' c& D& n0 d# o11
* d7 o/ [0 m# U12
13
7 t5 H9 w: U. k- f2 n14
15
16
17
18
19
" L" a8 U. t' J! G* g
- Y' c5 l( |- [, Y& `/ c2 _4 ?
$ P4 Y) {/ S& j& M6 {* L稳定性
4 d# Z) c$ @4 ?相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以
7 p, W% X0 S8 c' T# [5 M! _2 y
* S5 l5 \7 L0 @# E冒泡排序是稳定的
7 j& B. C: Q4 G5 t4 p! r: i
复杂度
4 Q  H1 ~$ q. a+ [时间复杂度
最好： 当序列有序
$ o) [# n$ ^) ?& z, w& A: n' U$ p
未优化：
% q# O* s$ o" f9 M6 e2 c2 x* s
O(n)

# ?. E* a6 m. i  ~$ r优化：

6 Z4 ~! P6 x6 g, Q" qO(1)

- ?9 |/ v  x% k5 G3 {7 \最坏：要进行 n-1 趟排序，每趟交换 n-i 次

6 L6 Q2 Z) I+ Z( ]' }0 w, p, x4 nO(n^2)
0 S, }, F1 z% A/ W9 J
* D( A$ a& q2 m- m* ]空间复杂度
9 ~  [$ A0 m) t% |O(1)

/ _% I. i+ `8 H' P9 m1 _快速排序
思想
0 V; k  q* }# E* L+ n- V+ B- u分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。

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

* ~: I7 G9 U/ p7 [% Y8 \. @8 g: D8 b操作
有三种单趟排序的方法：
2 u: e- f4 f& `
Hoare法
设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间
( a7 C+ _% h* R5 b0 x6 Q! ]
+ b% T9 a4 H4 p1 ?; g左下标 L = begin，右下标 R = end
* x# ?4 ]9 q0 G* U
. N* h& n1 m! S% z2 b设 L R 相遇位置为 meeti
1 a7 [/ C+ Z( {3 ]! W. h( h
& d! P; U5 O! ^( l​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”

​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“
6 e; z' @* q% @, F
选 键值的下标 keyi

左1位置作 keyi，则 R 先走
$ ^) e+ Q: A8 S8 a7 @右1位置作 keyi，则 L 先走
, ~. \% @" A& C/ Y( R) {. i. mR找小，

找到则停
遇到L，则交换 arr[keyi] 和 arr[meeti]
L找大

# W: R. Z: @0 u6 \找到则交换 arr[L] 和 arr[R]
遇到R，则交换 arr[keyi] 和 arr[meeti]
2 {0 u! c  T7 P) [
' ]' {! b+ D4 ~- l5 J
5 j8 A3 |1 h5 {' r0 F- T0 f  C解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
答案是肯定的：

$ U; d5 W- H( G3 D* A
1 _  S7 k/ ~! d4 U* h6 y% r. F

. g; E$ Z6 M; R" r' c9 j% @% W//[left, right]
int PartSort(int* arr, int left, int right)
{
. ]0 `9 |5 Q4 o2 ~. q, Z        int keyi = left;
        //相遇则排好一趟
1 n$ l: M$ X& h* ]        while (left < right)
$ w: j. D( |6 M% L% O8 U7 y        {
                //R找小
1 p) P3 \2 N, P8 y8 d        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
( W1 Y. t; i# m0 A. U* S        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
                while (left < right && arr[right] >= arr[keyi])
# c' T- K6 W9 Z0 m                {
                        right--;
4 @2 F8 J* O9 ?& D                }
9 B; Q$ V+ x- p  Z0 ?
                //L找大
( ]5 T2 V# y" W' P                while (left < right && arr[left] <= arr[keyi])
" I' \* i( M$ Y/ a                {
" ~: J( x7 S; b2 i                        left++;
                }
               
        //相遇就不交换了
                if (left < right)
                        Swap(&arr[left], &arr[right]);
        }

        int meeti = left;

        Swap(&arr[keyi], &arr[meeti]);
+ _; O4 `2 f$ P
$ ~4 K- b, E& Z% g        return meeti;
}
" p( e2 i% l1 d! f8 ^" S5 B9 ^
' i; q* L; G6 ^2 i6 o/ p1
2
* g9 Z1 ?- ~( r/ M: s0 I4 Z3
3 E. r6 q# X1 @4
' U' z# @/ `) A5
4 k, C! `1 ~: _- p6
% `; |$ f  ~$ x/ I5 b5 v* \7
7 @* O  f4 T4 ]8 M  G" S8
( a6 b$ i" k  g+ Z9
4 Z% y& K3 e1 F10
' E, ~0 y" z8 ]' o/ ~11
# A( Q/ x% B; B6 ?% k! `12
13
% r/ R' ^8 F! [. z2 A( l* m  ?# h* W14
15
16
17
18
6 d0 U! `9 W% Q19
20
21
0 W) |9 G1 j/ S5 H& f22
( V2 u8 p: s* \$ i8 m2 r1 I" H23
; A# C, N# e' k& F. V1 Y" e+ F24
+ Z1 p1 Y* F+ e9 @2 ~' j8 v, h25
26
27
1 u* i  E" Y. q7 L3 P% q1 w8 J& p28
29
. X2 k5 y: D/ }! l% ^$ _30
" d/ ~" u* G9 n& G* H2 @8 P31
32

  a' R$ s( g6 {' z% w
9 i4 F( R1 w; q) l解惑：为什么key要选左1/右1，选中间不行吗？
' d3 T& B8 U8 [+ K& q

可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深
7 R- k( o. L! _- z

5 S2 ?0 R# l2 ]1 W7 V& z: g  v

非常容易栈溢出，怎么解决？针对有序情况，优化选key

优化选key
$ b7 _/ i6 p: G1 r+ H+ X  s随机选 key （是一种办法，但是不那么彻底）
选中间位置作 key
% R$ R7 c- t& e& ^  e解惑：那先前实现的单趟排序不就失效了吗！
9 I) f# p, t, [' [4 q9 Y0 j：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑

* ]( Y# i* D+ l5 p解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
前辈给出三数取中的方法
5 l, p1 l+ s; A. \& {& W; J4 e4 s6 H
! Q& F! w; k  u+ e/ g4 U三数取中
1 Y$ _1 k) z* h* r在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
优化选key后的Hoare单趟排序：
1 e* [7 z6 a# k2 s& o
int GetMidIndex(int* arr, int left, int right)
* n8 A; T0 y+ ^1 j{
        int mid = left + (right - left) / 2;
//  int mid = rand()%(right - left) + left;//增加了一定随机性
        if (arr[left] < arr[mid])
9 Q3 h- {# P& i5 K) }" w- |        {
                if (arr[right] < arr[left])
                        mid = left;
                else if (arr[right] > arr[mid])
                        mid = mid;
" _( V/ ]1 _  u) V& J( L  e3 i                else
# Q% I( s2 U/ c- L: c4 G& }3 C                        mid = right;
        }
7 t% s5 W" U& ?0 {9 l: [2 j8 J4 m        else//arr[left] > arr[mid]
! N; ?2 a! r. X* N/ D+ q( t' ?        {
( w* [& J9 T. G) p, C* }' P                if (arr[right] > arr[left])
5 U& g3 B' B9 Y2 b                        mid = left;
                else if (arr[mid] > arr[right])
, a( K; \& T1 ^+ M# [" i                        mid = mid;
                else
                        mid = right;
; [, f% I! ?0 f3 e) k# u        }
  z  u$ G+ ~6 B- P        return mid;
; z% `. n# W* I* e}
4 w$ H/ z+ E1 _/ N/ O+ h
4 W# M# w3 d& y1 r& z5 Oint PartSort_Hoare(int* arr, int left, int right)
, `, ?, P/ Q8 U# B# f& q6 H{
        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
        int mid = GetMidIndex(arr, left, right);
$ Y% B% m/ d2 f: C; z2 I2 f% R
4 o6 f6 E7 t* j2 G2 @% W        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
7 a& g9 K! |& o4 i. Z/ H. t3 ]        Swap(&arr[mid], &arr[left]);
9 Q* z9 W+ b/ r+ N4 i, j& D
        int keyi = left;
6 ?9 M- ^+ c* O0 W. }# u: T3 Z        while (left < right)
        {
                //R找小
                while (left < right && arr[right] >= arr[keyi])
                        right--;

! ~- @8 l/ B8 \4 l" ]1 w                //L找大
                while (left < right&& arr[left] <= arr[keyi])
) Y) S/ s! p3 O' n& I                        left++;
" \3 d" a* w, `! M! ]
+ X! {! M4 P9 w7 V3 B                if (left < right)
2 R$ X, a3 f; [* Y7 B                        Swap(&arr[left], &arr[right]);
$ a) w  L$ W7 e3 Q        }

        int meeti = left;

5 c% [& i$ A/ ], e& k. _        Swap(&arr[keyi], &arr[meeti]);

3 d4 M" R  w3 t        return meeti;
% K, ^' U, O6 w1 n}

1
2
9 \8 ~- W5 _+ c5 L, h( p& A3
4
9 \" U7 H! @# O& \& _3 @5
9 |9 @, J. z# q' p- T6
# R' m% M% n; R. m" o8 y7
8
9
10
0 G9 u& w7 E' V6 u/ y2 ~/ l/ o- @11
12
4 t7 p; _8 Q7 ~7 s13
14
15
4 I& K5 Y0 S. W16
17
6 j6 r! m) H1 w. S6 j+ V18
0 {" v% j* E& s. \! W8 R19
  l! a* Y" a# Q; i" T1 D5 d20
21
22
  t( }9 _' S2 Y9 h23
24
" r" @( T# v8 w) `6 S/ G8 }25
. R& v4 }, H" p26
27
: H) B' J9 f! ?/ f9 C+ \5 L# W28
29
30
- {( z0 B$ c2 R( ], d) N31
$ |, r- ~6 i. m& @$ j32
33
34
& m% \2 U. g% c3 e: o# f0 d, \9 d35
' ~9 t2 b4 b$ N3 u36
3 B+ ~% A, [4 J) V/ o5 ~37
9 G* G; {. \  G$ U38
39
40
" [: Q7 a: ]" T+ V6 d41
* N* u2 i; Q; F$ J, m42
$ L* C" O5 Z# t. ~+ R43
# A- ]9 @, {& j5 e/ `1 h" _44
45
! b. {' J& b, S  w" Z. E+ l+ G% b46
47
48
49
50
51
52
3 j( G- i- L0 N" G! P, f) Z53
& L/ f3 u. ~& `6 {* N8 A54
4 y. R# V8 a: R/ X! }4 u挖坑法
初始状态：L作坑，其下标存为key
2 d& K5 T8 s3 B9 n(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
3 N2 ]! R+ r; R2 s4 ?4 X重复 (1) (2)
: c& `1 l4 R; _7 U' f" f9 t4 T最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]
8 }& d* L: U8 m1 h" H9 m9 ?
1 u+ s- G! {3 L, L$ N: o+ j0 O
3 F- c! Z# Q3 @8 \0 s9 J% Lint PartSort_Hole(int* arr, int left, int right)
{
/ I5 W( g3 S8 N3 R7 }" L        int mid = GetMidIndex(arr, left, right);
3 a& g6 d1 X1 H9 N$ K# Z        Swap(&arr[mid], &arr[left]);

        int key = arr[left];
        //L作坑
        int hole = left;
        while (left < right)
        {
  f1 P1 T$ j; f6 B: @& _+ Q, @                //R找小，扔进坑，R作坑
. z  c; P0 G9 ?3 z, R                while (left < right && arr[right] >= key)
                        right--;
1 M. o& W/ D2 V8 g                arr[hole] = arr[right];
                hole = right;
- X! g  Z% k* G! f& s  N
9 o1 v( q9 s7 s+ m+ ~                //L找大，扔进坑，L作坑
$ p' @# W: v2 ~9 U/ l3 c                while (left < right && arr[left] <= key)
6 r% i" V) O" j, ^                        left++;
                arr[hole] = arr[left];
                hole = left;
        }
$ W  V+ t* x9 w/ }6 Q9 V! A: r        //meet
1 F9 y7 C! Z' y, v% S' A& u- {        int meeti = hole;
3 ?; Y$ U( @  C4 g5 a        arr[meeti] = key;

0 O; V* J3 P, W8 k        return meeti;
}

1
0 s/ n6 A4 M7 k- z! I5 o* ?* f2
- `' @0 q" N. Q3
4
5
6
1 q& k7 @" z+ y  k1 C' D7
7 y, ^' T% y% w& P1 {8
6 t! v% x* R; c9
6 k7 E/ q  N# B10
* \: u6 X9 P( b2 h# u11
* ?1 g- H( r2 n0 Z( F12
1 S! {$ `( d, P13
6 @; k: B! z: k) l8 g, g9 ?14
/ V- J* I) Q, I! G3 j# d3 ^  m15
16
17
18
19
# {# n, v. S/ U, W& s% x20
8 q) K4 a0 p8 K: \5 E; Y) N21
5 U; u( ~- l% A3 g6 b2 H' q; [4 C22
' Z8 w" b: v6 Y( L% e23
24
/ w$ Y7 D- w0 P3 l25
26
2 x4 l. s- M4 U( g0 v7 e27
4 Q7 c, R5 n% K; Q28
% s5 E( m. M- g. X前后指针法
此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多
9 D5 X8 D- a" v- o
! I2 ]' u, p7 C# [! I4 ~% p! {) Ncur找小，找到则停
++prev
如果 prev != cur，交换 arr[prev] 和 arr[cur]
如果 prev == cur，不交换
当cur越界，代表找完，排好序了
6 g: U7 [& Q7 \% sprev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低
0 P0 V* X) m1 q5 X! r8 D
9 W/ l+ e& W7 Z/ P9 i: ?+ n

int PartSort3(int* arr, int left, int right)
# b# k1 X/ v- h5 q& x5 V- ~$ B{
8 |- }5 M7 Y* J3 t        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
& f, a6 P" I* B4 d% j) f$ l+ t, T( `       
  //int key = arr[left];
        int keyi = left;
" C8 N4 g' a3 j5 Z4 t) M7 k! D: z5 i
% j/ G6 W, ?  }$ N        int prev = left;
        int cur = prev + 1;
$ x+ `. ?! ~- M       
8 X; C+ x& t+ q& ^2 `    //cur越界：找完小的，prev的左边全小，prev右边全大
8 q& T# n+ q  p. o7 Y$ o8 S5 E        while (cur <= right)
        {
+ e! O" \$ o" T/ b0 k        //++prev == cur 没必要交换
                if (arr[cur] < arr[keyi] && ++prev != cur)               
                        Swap(&arr[prev], &arr[cur]);

                cur++;
' C* ~- |- x( {7 r/ k# D: w        }

        //键值存是的值：
' A2 b9 ~% Y; @) X, T        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
5 m' v8 Y5 N+ q8 P  Q2 F        //Swap(&arr[prev], &arr[left]);//这才对
( B1 Q7 `0 h! R- _; P, ]/ R    //键值存的是下标：
0 `5 Q3 [4 m! I        Swap(&arr[prev], &arr[keyi]);

        return prev;
}

1
2
) c* Z+ P( F  |- s+ I3
4
5
" x4 E- S/ e* O; v' a2 T& B6
1 c) d' Q% w0 d, Z  k% g7
) w. p9 p. ?7 M& p9 `* z8
9
5 n/ A. g* s4 n( F10
; }3 h' \5 w; h4 {, J7 ~11
12
13
1 D9 t& Q# J2 Q, k14
15
. r3 h2 c6 G+ @* t5 l16
" k8 a  ]" ?$ S3 @- A3 `- u$ E17
18
19
- Y+ q" E7 i0 Q5 c1 Q20
8 L  P$ m0 N9 J. ~21
22
23
24
: I+ v7 C5 N( N25
26
. m+ T1 I" A' ?  @* k! z27
28
29
7 ]4 t5 x) |' h0 c1 C整体排序
递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

  s9 [4 Y7 s3 Q$ e5 U8 I) O//[begin, end]
4 l) ]) h# y7 Lvoid QuickSort(int* arr, int begin, int end)
/ c: Y, N- Z0 E3 m1 i& X6 [{
        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
        // [begin, meeti-1] - meeti - [meeti+1, end]
                //1.begin > end:超出范围
# q  T1 n& K" r5 U5 T$ }/ ~! O                //2.begin == end:一个数天然有序
    if(begin >= end)
5 K& }1 p( n2 j5 n        return;

5 G. n3 V$ _* A# J5 V, A                //排好meeti
                int meeti = PartSort3(arr, begin, end);

                //排好左右子区间
+ j  t! _+ P/ A, q0 N                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
        }
5 U. F4 e( _* c, N3 T}
2 i. t( I9 N0 d4 N  Y; ^& |% u) ?0 e
+ T1 z: C0 T& P; d1
9 ]" c! M- C$ s5 W8 z2
3
* j% L  C4 P+ R9 Q0 ~4
5
6
7
: G8 A6 W" O8 j* j/ B% O4 @8
# ^3 c7 `: h, p2 Z3 ]' s# |1 e/ g9
10
1 g: n4 V3 ^7 S' O. z/ i4 V11
2 y8 H% M1 p; R7 M& V12
, O2 k3 m5 y- o+ S# |13
14
15
16
17
18
…

没想到吧，还还还还有可以优化的地方！

优化小区间

% c5 O4 |4 J8 G3 r# y, r; i8 H
  B9 ]6 z- {- {0 w$ A如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序
2 M" o: k% o9 W, Z! W* S  P
+ t& O* C% _5 K- |  u那什么算是小区间？

其实小区间没有确切标准，8-15左右都可以的
7 _. Z3 U$ L1 Z0 p# ^3 t* D
* e8 W# I  q5 S6 c- P
这里就把小区间定义为 含有 8个数或以内 的区间

+ y) Z! e  d* p* _/ ^0 ^: a/ \: J//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
7 v, k% K8 D! V$ v. {- O, i        if (begin >= end)
                return;
$ q0 ^8 a5 A# I
9 e  I6 c  B* ^( C3 u8 F        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
" R- S9 p0 V" x4 A: c, d        {
3 M( Q1 {: q+ U1 J9 A3 H                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
        }
        else
        {
. V8 P( ]0 _2 n  z2 z                int meeti = PartSort3(arr, begin, end);
8 Q6 p, c* @; ~/ H
9 i' {2 G  o6 m) x! R9 N                QuickSort(arr, begin, meeti - 1);
! ~# ^0 u% a3 j                QuickSort(arr, meeti + 1, end);
        }
}
1 s, o0 G! |* `% |, T$ E7 H
9 o# b4 R, j* ~- l& U1
2 i3 m1 h& ]0 `; r9 }2
9 I+ p9 h5 X/ l, \  ?4 l3
* G6 f1 y. u+ \9 B4
5
6
7
" O1 i- c6 a# P; z- L8
9
10
$ f$ ^" j) h6 D" ]) X* N9 y11
12
13
1 C4 O  Z9 `. H8 n( t* @14
( J1 R8 M" _6 N8 {% Q, B" b15
16
17
5 p8 E+ Y) F; o& [( h! V18
% m# N- H! F! p7 l; O7 P# W8 [" y8 O19
快速排序非递归
8 o' y0 x" t" v% f- t6 _4 G为了解决彻底递归深度深的痛点，我们来试着把它改成非递归

+ H& r% ^: k5 f% y( p" [$ z! c思路：
4 F9 o0 Q6 `+ }* k  ]. ^+ L递归深度深，栈的空间又小，会栈溢出…

那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！

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

快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的



, o" {5 B) C9 U' G* Z$ M6 A& Z: L0 _/ m在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：

先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
* U9 V& F% J+ @* t6 N* C{
7 S' f9 m, @7 X! C        ST st;
9 a/ v0 S+ ^9 s; `; I( ]" x        StackInit(&st);
- m0 |) {3 B2 G       
( n& I* w, f7 `- {7 R: _    //先入begin
2 b% k: e5 @* m, n        StackPush(&st, begin);
6 |0 n" C6 |9 T  o8 l    //后入end
5 _+ `7 n9 T* N: P$ c        StackPush(&st, end);
% v8 Z" H, S2 {. W/ J
        while (!StackEmpty(&st))
* ?5 Q9 Y7 k3 z4 J8 {* w        {
- w: k0 @0 }+ D0 y- |& U( D                //先取end
0 H/ c# ^# M1 M6 E8 b  I3 r                int right = StackTop(&st);
/ }1 X3 X$ v; C5 s5 y: S                StackPop(&st);
                //后取begin
                int left = StackTop(&st);
                StackPop(&st);
2 {4 K# w, K$ B& Z. ?
                if (left >= right)//1.只有一个值  2.区间非法
                        continue;  
                               
3 u4 k' L8 \4 c                int keyi = PartSort_Pointer(arr, left, right);

5 c2 b9 C* Y) N% W# l6 @                //先入右区间
" j9 Z" u0 X4 E( f. s! g6 h" Z* q                StackPush(&st, keyi + 1);
                StackPush(&st, right);
                //后入左区间
0 }! H0 m/ ]2 \& ~                StackPush(&st, left);

                StackPush(&st, keyi - 1);
, m+ \0 X) z( L; g8 x        }

        StackDestroy(&st);
2 X3 P9 S' a) X8 B4 u) g) Q}

) o- ~6 _7 }! `7 m$ @" W! N8 P5 Z1
2
2 d( p5 @, v3 I2 M2 ~: O( O9 d! z6 Q2 T3
4
$ K( `. t  L8 L1 v' x7 V* F5
6
- I+ l  m4 Y6 D7
4 V% d( s. Z; I8
9
10
, l  o) Q9 l( I- x9 [  \11
# v5 [" u3 D$ o5 F12
13
% h' }5 Z7 N& `8 u( v14
15
9 H1 b1 B3 ?3 f5 `1 f16
17
18
- {# S& w3 X0 E9 ?: o$ D  t2 t( N19
& f, h& j5 g& c: A$ ]6 E( T9 z6 l% H20
21
22
23
: P7 B, [' \% v% @8 [1 Z6 W0 p24
& D( p* e! @1 o, c$ r25
26
27
$ V" \( p, @  D28
29
- n0 R+ O# D* ]& |, |% V30
31
32
33
! y! h0 I) B- O8 `: l, l; t3 y9 o2 i34
35
" X0 ^: F+ k+ h% n* u+ i数据结构栈的实现可以看博主之前发的博客


* G0 Q- w- k! ?% W" t. g% s6 u3 c  y归并排序
, @4 X7 V! H6 K
1 @0 {" Y4 L2 y* W% |  p% H7 V…
0 c2 F) v. c3 `1 E2 m
性能测试
  n' e8 x  O( H' n1 ]* V' Z0 U) r) Ivoid TestOP()
# o$ j( n* W) Q, `$ {% x! f- u{
        srand(time(0));
        const int N = 100000;
        int* a1 = (int*)malloc(sizeof(int) * N);
5 ]6 ?8 a5 ?1 v" |- h' d9 }        assert(a1);
4 s& G+ j' ]0 M  q7 @* m( J3 A        int* a2 = (int*)malloc(sizeof(int) * N);
* i( K8 F# n: |! G3 V        assert(a2);
        int* a3 = (int*)malloc(sizeof(int) * N);
6 E9 h) o9 a* }9 d! O4 ~, x1 D  }        assert(a3);
5 m: \2 j5 k7 @6 O$ B- R* g        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
        int* a5 = (int*)malloc(sizeof(int) * N);
        assert(a5);

  {: G) U' B' T! |, |. f; e$ m1 d        for (int i = 0; i < N; ++i)
) l* C5 Z. \1 ]  N1 @% Z6 L        {
9 C+ }4 D( ^4 C- a: z. Y                a1 = rand();
                a2 = a1;
1 @) ]6 ~( P! w: y9 k' w) k                a3 = a1;
                a4 = a1;
                a5 = a1;
% n8 C+ X! ^: |/ x        }
% A' r) F8 v: R% \3 j( b& z
# r" O7 G9 A/ @* O( z6 j        int begin1 = clock();
  G- d: g8 S3 R1 y0 A        InsertSort(a1, N);
        int end1 = clock();

  U) t3 m- `: J% ~+ b% t        int begin2 = clock();
        ShellSort(a2, N);
* t9 K# y; P  C9 V& i# i        int end2 = clock();
$ _! [2 g4 z' C- H
9 Q; N9 L( x" ?+ W. k9 X        int begin3 = clock();
        SelectSort(a3, N);
( J8 X/ A1 Y' l  q  X0 W        int end3 = clock();

        int begin4 = clock();
        HeapSort(a4, N);
        int end4 = clock();
4 O- c1 ^0 `$ y. y9 z
        int begin5 = clock();
3 I3 c" _7 T5 D6 b* ^6 B1 a+ ]        QuickSort(a5, 0, N - 1);
' h: o8 p  m" s5 `8 j2 m' r8 S1 r& f                //1.中间key
                //QuickSort(a2, 0, N - 1);
  G# }0 V# K; w( c& o0 ?                //2.三数取中
( ?* r9 w$ m! I4 b( a                //QuickSort(a2, 0, N - 1);
                //3.小区间优化
                //QuickSort(a2, 0, N - 1);
+ V9 E+ N- w% ]' p        int end5 = clock();
4 C! B7 B, c. u5 ?) N9 x

3 a  v0 `2 @, M$ A" n        printf("InsertSort:%d\n", end1 - begin1);
0 V/ @, j, z+ C7 _& a& M        printf("ShellSort:%d\n", end2 - begin2);
        printf("SelectSort:%d\n", end3 - begin3);
        printf("HeapSort:%d\n", end4 - begin4);
        printf("QuickSort:%d\n", end5 - begin5);
# _  P9 C" @2 ]) c
0 M  m* k' p# ~5 j( C: Y        free(a1);
        free(a2);
        free(a3);
9 D1 u* k; \) K& S& T8 X        free(a4);
        free(a5);
' f  T8 x4 ^% U2 d+ J( h}

1
2
  f) T* E# q; j7 y3 \# a* h3
2 o7 G. {- L, ?8 `1 l7 W; x4
5
6
7
8 e0 Q  N: c% w! v, i2 G8
' P3 B' S2 q; s& C: x. T9
10
5 u# a/ P; N& a9 B3 q; x1 a7 C2 @. `11
12
9 D' a% |5 [# A; ?  O* G13
* b1 v! |" ~: M/ H( J0 a3 m* Y14
15
4 n) u/ l0 t# k. I; Z9 W+ P16
17
  ^* P( Z2 D; g1 s" Q1 ~0 ]18
. V3 R7 X4 q$ a5 e: i+ U+ U" x3 u7 o19
) X( P- e! _' }+ z20
21
' P% V( ~  N/ a  e22
23
24
! C* T2 Z& `& z3 b25
26
27
28
& Y: R  i) b( L" [/ a5 U, {+ ?$ K29
30
" a" s: c& _' W31
32
33
34
35
- J- @  ?: s) x; k' t36
37
" D3 t) n- g. r& }; r, j; u; B38
39
40
41
3 Y$ F/ |" Q  L' T0 Q1 N42
4 [! T9 b  q+ ?. L% A43
44
! y: L3 D6 L. \) P4 K' g% ~45
46
47
% u0 P& l/ }/ s7 a0 I# b0 Z+ u! [' n48
& S7 z) W/ e9 K; [& _49
2 U: h+ ^7 Y& M50
51
52
* h  u% o. j3 F* U* r53
% ~9 U9 ^0 c  K5 x6 L& b% h" e" {54
55
4 C; ^' h$ e+ F) b56
. D9 |3 j8 Q, w% E57
58
9 `! Q( R* Q% s9 u' V/ K( ~; a! O59
6 V1 B: Z! @6 _5 ]& x60
61
62
. `( d: j7 |5 c: b% C5 S5 P63

/ Z- N1 H. Y7 Z
不愧我们费这么大劲优化快排，多帅哦！
5 L7 t: @  q9 O
差一个归并排序，后续补上！

不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
0 T$ I# q" Q7 A& I————————————————
# E- D# |( ?$ D0 h版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% A! j- t+ `7 y  K& r4 z1 s原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832