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

杨利霞

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

前言
  a$ h3 P0 |+ T2 b' M. r本期分享经典排序：

插入排序
0 k/ w+ p: W7 n+ z5 x0 f* {0 Y直接插入排序
" j1 e% |2 X, E8 I9 W' t/ I$ r希尔排序
( n" h' J7 N( b- @选择排序
; \1 W2 {8 f/ o, R$ q7 i, o直接选择排序
! |' b' u" l4 o  W3 E5 W堆排序
交换排序
冒泡排序
快速排序
注：讲解时默认排升序
2 I: l; E5 J- n' @+ j
插入排序
直接插入排序
7 I2 U2 B8 x! |+ Q思想
. n3 E: s+ t$ Y1 `. H/ X9 s插入排序，就像玩扑克时，摸牌的过程：
$ P8 e" B0 w, f8 {: C9 Q8 [1 o
" V* C/ {! n1 z( `最开始，左手没牌，右手从牌堆中摸
右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
* T! C1 P! b# v2 O, G如此一来就能保证左手的排始终有序，摸完牌后也就排序完成
+ v; H7 N& r- Y4 c2 J

操作
" j+ X' p- E5 N设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
单趟排序：
每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
% n% Y$ Y( J6 p; `是正确位置：插入
不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
5 L7 {8 L5 e) T$ C0 I整体趟数：
若元素个数为n，需要排n趟
void InsertSort(int* arr, int sz)
9 Q( H" ^: b5 k{
5 r  @" e. K4 b) x# ?2 }( |( S        //end + 1 < sz
. `+ h7 I; k2 Q3 h3 e' v" B$ O        //end < sz - 1
        int i = 0;
1 w! R7 s' _) ?6 o- j        for (i = 0; i < sz - 1; i++)
        {
                int end = i;
* p" A& `4 l3 \& M9 h                int tmp = arr[end + 1];
  y6 U' C1 n+ k$ n4 |
4 P2 l  ^5 n& D) U                //找插入位置
                while (end >= 0)
: E9 p) b4 i+ {7 x% Z9 z                {
& B* G$ Z* w  r: @+ U8 m. W: p                        //不是插入位置：当前数据往后挪
' f4 s( S7 u- q+ D' [: W. |+ E                        if (tmp < arr[end])
                        {
                                arr[end + 1] = arr[end];
                                end--;
( Y9 Q: h/ ]$ l                        }
4 `( q8 `$ _+ [+ y                        //是插入位置：跳出循环插入
& J% ?- h" t' Y3 B9 Q" }: D                        else
9 H, {2 [# B* |8 Y( n/ Y+ |                        {
7 G- t+ @& u3 _' r                                break;
                        }
                }
                //插入
                //1. 插入位置是[0]，end == -1，不合循环条件跳出
                //2. 找到插入位置，break跳出
                arr[end + 1] = tmp;
- k) d1 d6 X% J2 P  p        }
}
/ Z: B( U- U# R2 f& Q
; V! W8 L) s0 g8 [3 R( e1
0 c5 C7 }& X2 g* U3 C0 X# o$ P2
3
4
9 t1 H: u' F  y1 i5
- F* h) V7 J  x+ Z1 Y* I# c8 K! I6
7
7 U/ a2 X, ^: C2 W! \5 b, s" c) x8
/ Q  E. a. h$ r! h9
( C2 E- y8 q# M7 S' V7 H& z10
11
12
13
14
15
# ?3 d) l: r- H0 v9 X. L" f' [16
' S2 T- n) I" q' M7 D) F17
18
3 ~/ W7 o9 c% ~  B19
20
21
* b) R9 A5 Q; N, t22
23
( H9 E2 X* Q% A' \- C, I0 x24
25
5 `8 P6 l  H+ E% W1 r26
+ G* B8 \" s% [0 H  H27
; S! F4 H7 c7 U+ h28
5 z2 w8 S1 n! z' ?2 c0 p: Q29
5 }" l* ^* [" o$ m3 c( L3 A& c30
& D, o. t& g9 a* r" A' u0 {# D  A; ^31
4 @/ S' {- k9 q2 I8 q$ E; k
  k- f, b9 s- X* L/ `- s
稳定性
3 ]" n! J. V8 m0 {; J1 E1 @1 R3 d插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以

; B& z# [+ _6 J" Y直接插入排序是稳定的

复杂度
" E4 N8 I6 ~* ~' h, a时间复杂度
最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）

5 S  @. E# \# \7 v2 y9 B1 U2 J5 f5 YO(n)
0 c+ ~0 x* R* l: o7 Y3 Z
, h4 L1 C1 O- m9 R0 D# x$ }最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2

O(n^2)
8 c, J5 Q4 j# m/ g# x, R" t
% ?  K# [2 M2 X$ y5 P4 G空间复杂度
O(1)

希尔排序（缩小增量排序）
希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序

+ Y  a1 C" }$ Q) F& J% V, r优化思想
- `5 N' _9 Y& H! q增量gap不止用来分组，也意味着数据移动的步长，所以
! C7 z# d3 ~5 Z8 E0 P
" {( l9 @* o0 M  w' v1 }gap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高


操作
单趟排序：

/ m. r4 v0 u3 z# P设定一个不断减小的增量gap，也是元素移动的步长
4 H5 u/ {* D, g7 s8 Q  @以gap对序列分组，并对每组分好的序列进行直接插入排序
不断缩小gap，并排序
' o4 I1 x- ^5 h; ?; Z! ]! \*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
( z! f3 y- N& N# v/ |整体趟数：
' d6 p. L3 K! Z/ T+ |
由gap决定：当gap = 1，排序完成
注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。
6 M$ t6 Q& Y* s: e/ c- P/ a
void ShellSort(int* arr, int sz)
{
        int gap = sz;
) ^8 R7 T, @' ]; {- P; m. h4 D       
    //gap > 1，预处理排序
    //gap == 1，直接插入排序
        while (gap > 1)
        {
3 Y& W) }/ L/ j: ?/ g6 H! \4 E, Q                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
% {4 E2 H& j& o7 }& a, y" Q                //gap组
# A/ Z( @( }$ e1 }                for (int j = 0; j < gap; j++)
" Y3 r) W. X% O; a                {
- e8 P# R2 l4 W4 t+ O& ]" p            //end + gap < sz
                        //end < sz - gap
$ `( D# X4 B/ m5 I                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
) ]' p: G: {+ d+ y9 c" D6 ]0 O& n8 m                        {
                                int end = i;
6 j  N3 Q1 G, A1 P+ r* k6 e                                int tmp = arr[end + gap];
                                while (end >= 0)
  J- [# O: E# f( }2 J( [/ Y6 t                                {
- G+ x0 |, E9 u3 a: s! d- W                                        if (tmp < arr[end])
                                        {
                                                arr[end + gap] = arr[end];
, W9 ]$ r  M3 Z9 {                                                end -= gap;
                                        }
                                        else
9 n' Z7 n1 r( K  C: c8 ]/ n                                        {
                                                break;
2 H4 J: Y( f1 z( m2 i+ v2 I                                        }
                                }
                                arr[end + gap] = tmp;
                        }
: w! H% r5 l# Z! f. i6 Q                }
7 I2 S0 z: a/ V        }
4 l& v# G+ z2 D+ s8 Z# ?3 g}
2 w3 e0 c: C9 Q5 Y! T
1
2
3
4
* h- r; r# J, v; r5
6 X! U& @! E* t6
7
! r" T3 f7 p- h* ^$ y0 C8
. V. G  n! M# C9 p9
10
11
12
13
14
- c! Z! {/ y4 j) N4 }# `. n. c15
16
% g5 Y& O8 d$ L2 {" c- A17
9 `" a: u' H. n0 A18
% F4 Z7 ^# c/ s$ U/ a+ w19
2 A% T( G$ j+ A6 D' O- U20
21
. z/ }4 f/ m, `1 j; F$ ?2 i22
23
( M& }+ }# `$ T+ Y: P+ _; ^24
) a! W$ S; \7 f$ Z25
9 X+ i4 s9 x* V" K7 C26
2 A1 u. U* P, w; q1 f0 d- s" V* T27
1 j  @, [' L$ F. P' e& I28
29
6 z2 J% [6 S! G3 |30
31
# e9 h) \+ f& t4 m32
33
9 c5 _0 K4 {" W/ }8 J; z34
35
其实就是套上”缩小增量“的直接插入排序
# s% z; b& V8 o, Z" N3 \1 f/ y- ]' r
: T6 P% k# O) C$ Q) e& ~
9 X6 q# Z2 Q+ s- |稳定性
我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以

希尔排序是不稳定的
9 _' ?# E! N1 a" e+ i
" b9 d2 d9 E; Z) Z复杂度
" V9 J" F4 R+ Z) v1 V5 O' l" Y时间复杂度
0 h1 i) F2 z$ H/ k# q希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
0 G! p1 H' L3 w, H8 ^+ C
O(n^1.3)

空间复杂度
7 O, G, F7 o- W) w! ?5 B+ N9 d8 M7 MO(1)

选择排序
直接选择排序
2 L$ j' n6 f" y# b4 g# u思想
3 \2 U5 R8 Y0 y4 r选择排序，遍历序列，选出最小的元素，交换到左边

* r6 z, @7 u" D+ U* E

0 ~4 {1 c2 Y1 P  O! v* R; p优化版本：

' p, C3 X) ]- h) A每次选出最小元素交换到左边，选出最大元素交换到右边

' B1 R: C% o/ `) L9 j" W4 h操作
& l: R; P" X, P+ a" t! ^( ^设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]

( L; C! C+ v$ l+ Z设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标
7 [- g5 x1 Z- M/ ]1 h
. @' A! M3 J7 N0 w9 J单趟排序：
- F) J% N1 ~8 k8 v: Q  |5 [/ d
1 z$ \* ]# K1 x遍历选最值的下标
8 b8 F$ Z2 K* T" H# I交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
（修正）
3 p1 h- M* P- Y1 X6 K+ D整体趟数
  Y) L. y6 Y0 Y# N6 _2 \
$ ~2 G; H9 G7 M/ [! `5 I若元素个数为n，趟数为 (2/n)
0 u9 s2 n! l$ B! }0 ~- g1 @修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标

void SelectSort(int* arr, int sz)
{
/ \/ M9 U$ B8 y! M. [! U  b, D9 B        //闭区间: [begin, end]
        int begin = 0;
1 e( z; R0 ~1 D1 f+ u- b        int end = sz - 1;
        while (begin < end)//begin == end 最后一个数，天然有序
        {
* q& v* S; E3 R, V2 j4 @% q: F* m                int mini = begin, maxi = begin;
, K0 ^( a  N2 q  a) u                int i = 0;
5 X: v( X" K  |1 E$ ~0 O                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
                {
; b. b* ?, e3 x1 }                        if (arr > arr[maxi])
& P6 k: N& V- h4 m                                maxi = i;
                        if (arr < arr[mini])
) h& }# p) Q" X                                mini = i;
; A& y0 \/ r- b* J+ n& A$ h& N                }
0 y9 ~% X; b2 i  U: B3 j1 T
                Swap(&arr[mini], &arr[begin]);

2 ]$ Z& t. r6 m- }4 J3 T5 O& s" Z                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
3 Q% H7 [/ c( g5 X+ ~                if (maxi == begin)
                        maxi = mini;
                Swap(&arr[maxi], &arr[end]);
7 T/ O5 a7 R! c+ p) ]
$ ?1 ~5 `- k+ N/ f0 R                begin++;
5 N6 A; q! Z3 ]. ?4 A( T* b                end--;
        }
; [6 S# Z4 @/ o8 ?, {' i}

" P3 x# c. e% T* Z# V1
% x, M6 T. A9 I( m4 J2
3
4
  g  r- Z- d0 J5
6
* |9 q+ R" e7 I% K6 `( g7
8
9
10
11
2 k% _4 @; o2 k  Y! v12
13
14
15
16
17
18
19
0 T9 e5 A/ x+ d+ l# L( E1 c  `20
) @5 A: y3 O- o. Y21
22
. O* _6 S& Q+ H8 v1 w5 X" a23
; k  m5 b/ e9 H) S* |# {8 `" t. H24
25
% O8 q7 l" `4 N3 i6 `26
27
28


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

/ \, G( W% A" ]/ z* ?) F% t选择排序是不稳定的

复杂度
# |# u4 g$ f: g- H; ?3 r5 H时间复杂度
! S( |" @+ _8 C; o% o最好：

6 w7 Y9 V3 L1 E  o9 |9 d, ]1 I+ x比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2

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

O(n^2)

最坏：

0 r+ @, M% j9 D5 Z# y3 d3 P比较次数：O(n^2)
" _' z5 R9 A& l8 g
! h  W. H& {0 W( r9 K交换次数：O(n)
2 M1 w" p& r# C7 A( M/ D. z2 j
9 o! x9 ?: X# l- v) q" qO(n^2)

空间复杂度
, V8 Z/ r5 ?, V9 j. bO(1)
3 s& C* ?, l: F/ ^8 C0 _+ l* t( w
5 D' v" Y6 f7 A5 L8 e堆排序
* l5 F, r8 w, [思想
& D: c7 D2 M$ y  h# V) G利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆
; T$ o5 L, e( g& q2 {7 j+ k
9 N2 P4 ]( I0 S' q: z" D
3 O: i. h8 e* O, Z  X' k
操作
建大堆
单趟排序：
" E9 o+ N+ A) o2 i+ t选堆顶和堆尾的元素交换，则堆尾的元素排好
每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
整体趟数：
若元素个数为n，则排n趟
void Swap(int* e1, int* e2)
{
4 t7 ^7 X. ?* {7 k1 E  f9 O' s# E& [1 z        assert(e1 && e2);

        int tmp = *e1;
/ Q+ F1 J/ E5 d" o' ^3 m1 x8 K        *e1 = *e2;
        *e2 = tmp;
}

1 z) j' z; t* u! i6 yvoid AdjustDown(int* arr, int sz, int parent)
{
# p: }8 l  @3 \0 h) B5 o4 g3 d        //建大堆，排升序
! U+ m0 Z/ Y4 M! S# U        assert(arr);
       
+ R2 ]* j- r0 R* q" `9 i2 X. R    //默认大孩子是左孩子
        int theChild = parent * 2 + 1;
        while (theChild < sz)
& |6 [, E" }! h) P; x8 j8 p        {
        //如果大孩子是右孩子则修正
5 W1 g( V5 }" Q                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
' }  T; j) X& ?& c, i# ?& n+ Z$ L1 a                {
3 \/ [, S& {" E/ D" i                        theChild++;
* n8 b& L- u% F( \# m                }
                if (arr[theChild] > arr[parent])
4 U! \4 S7 s& ?- [. I5 j  K: ?+ o( R                {
                        Swap(&arr[parent], &arr[theChild]);
            //迭代往下走
' m! m; ^+ I0 y" |: u! k. \                        parent = theChild;
                        theChild = parent * 2 + 1;
9 A, {! P; ~9 V) ]" j4 g. E9 Z                }
                else
  {2 j, R8 Z7 j; i/ E4 q$ z                {
                        break;
                }
. N/ P* L2 U0 T5 Y( `        }
}

void HeapSort(int* arr, int sz)
7 Q6 Q7 j: R  W7 V. k. j; f{
) w$ X9 o9 A$ @. i5 T        //1.建大堆
        int i = 0;
# x+ u+ L6 T  k6 ~! i( N        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
) l" m' F3 f( S* ?        {
                AdjustDown(arr, sz, i);
        }

2 k& J1 d0 k7 j0 n' G: i" e. s% _        //2. 选数
        i = 1;
        while (i < sz)
        {
. j. _, j6 L( V" Q( L9 i1 s                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
' V$ `# p, v& A3 M- P. L4 G                i++;
; v  q- \+ M' E0 A+ U4 H        }
}
) W' ]) y! i- H
: ?* U+ h( ~  ~1 _0 t! g1
$ }! `: T7 `' I6 R7 x0 `2
3
0 e( H- O2 x6 ~" S4
5
6
7
# H. U4 F5 x7 i" l. Z1 F8
9
10
" c& J4 C+ c) n" ?9 C11
' s: \# u, S4 |8 @12
$ C1 D/ ~: w: i6 s2 V# f* M13
: {; ?6 J! {+ D$ g2 e14
15
16
, d& A/ s$ b0 o+ N6 L. Z1 [7 `17
: ]5 o5 Y  m1 e! n+ F- d9 I8 S18
4 E% k" T9 h; E3 M0 t& F# B19
" |6 k4 L3 T4 d3 L3 f# s20
21
7 }2 s/ [# L- X22
  J* c) |1 j8 ^5 c( V% G! Z5 D23
7 y6 b* H( ?6 R4 X. o* I24
; t3 I# _2 e3 ?4 Q' U0 D25
% s0 e2 ~! A; ~1 H6 _26
) p7 A% y" k$ K27
28
) `1 O, L7 u% i7 u3 ~/ G7 ^- I. [# a/ N29
) s$ Q8 X/ s5 }2 R3 y30
31
7 p4 ~+ W% k  V* s5 P3 r" b32
- c! w8 W6 Z% V) d7 z33
- U; [- ]* n4 G* M+ _% N* D34
9 v8 i* \/ H! N5 d35
36
! z+ `4 J# U; H37
38
39
% L* b3 ^4 [0 W. ^+ X0 j40
41
; Y6 R1 A+ H; N0 U. u6 V. [# X42
5 M9 m; `  h3 [& y43
( h2 [- {" i- V/ L* {44
$ W5 }+ V0 A" z45
46
47
48
9 Z( w. s6 m/ E" U  J49
50
: T8 n8 K$ ]" A! C9 n51
5 w' Q# P, w# a5 l. o% W52
" V* u$ F% E, [+ a1 F53
5 d* u) N* l6 f4 w. O! C8 N54
55


稳定性
建堆和向下调整都会打乱元素顺序，所以

堆排序是不稳定的
  R: G' g! U1 {; I
' q$ `1 w0 e: z# ~复杂度
时间复杂度
单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为
( [) }8 n9 o1 p0 D+ O6 `$ s" _
  P/ ^0 J8 O7 V. M: C* k* s/ tO(n*logn)

% A! R3 j3 ~3 K$ g3 `5 x空间复杂度
! }/ m& k) ?! F" A原地建堆
( v* u5 F' a. p" ~% ^
O(1)
6 L9 [( S. A4 s6 K8 v8 I( n
9 y5 l" u4 T* |0 l, [6 A/ P# T交换排序
) ^3 Y( s' E4 G& }: x冒泡排序
$ t0 p# g. N% {7 K) A' I思想
冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素

/ S7 j) N! R0 a2 Z
5 G4 v" }: V+ Q" Z
操作
单趟排序：
每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
+ Z' U3 \2 L& u7 x, G4 A5 t每趟排好一个元素，所以需要排序的元素每次减少一个
整体趟数
若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
* h) h, B. i* z  e# d9 n' r! H7 }void BubbleSort(int* arr, int sz)
{
4 G6 S# i$ J% [2 B  t" T        int i = 0;
        int j = 0;
; O' b4 ~: h% ~- a1 }        for (j = 0; j < sz - 1; j++)
        {
                for (i = 0; i < sz - j - 1; i++)
! Y: G  m) x" [2 n, y                {
4 b* z' M* ~' m% I& u" ~                        if (arr > arr[i + 1])
                        {
% s; y5 u: _8 c1 F3 d3 p                                Swap(&arr, &arr[i + 1]);
5 a" Y5 t$ w) u                                flag = 0;
: M" O, F  `  \3 R6 l# o$ n1 w                        }
                }
        }
: e# i8 Z# R7 m}

1
3 K0 C# Y% I2 Y/ R, s' N- H2
3
4
5
7 h9 s2 I3 K9 v" \4 {3 h$ Q6
7
8
9
! v, D% I: C  J& H% q10
11
/ K; c) y) Z7 h6 J12
13
14
: Q1 |7 G. H& C$ B" O15
16
( G' ~# Z3 s1 s" Q% F  @( O- O" x优化
1 |! W2 C! W; C, C" N当遍历一遍发现序列有序，直接跳出
; d. n4 R: f/ F/ }8 X+ ]" N
void BubbleSort(int* arr, int sz)
{
        int i = 0;
        int j = 0;
        for (j = 0; j < sz - 1; j++)
        {
0 X0 K, y4 F& Z- o. y                int flag = 1;
                for (i = 0; i < sz - j - 1; i++)
" N# L  ^5 E, y" @) S; y2 J: z# g                {
4 Y+ T0 ^! W9 g8 [$ X                        if (arr > arr[i + 1])
) }- Y9 I8 p: F/ U" T                        {
' @1 `$ Q4 V2 O2 D( d4 M2 o                                Swap(&arr, &arr[i + 1]);
                                flag = 0;//不是有序就置0
3 |: ~! v& _' I2 Q& r                        }
                }
                if (flag)//如果一趟下来还是1代表有序
                        break;
  P8 Y6 M+ {1 s; n: b        }
( R3 k; F, z2 m5 W8 K9 d5 e}

) Z- D4 ~$ {1 l6 J% |1
4 k7 G1 o' x: q7 K9 B4 E( j2
3
$ r8 D; o: y$ A' {# o* g4
5
6
7
2 F* ?. z' o6 V+ _( l2 W4 ~9 |8
/ j  F. I, Y( {9
10
11
$ r' ^, a3 A- n12
; v! i8 f( F" I6 e/ G9 D% @" D$ G13
14
15
16
17
18
19


稳定性
% T1 ]* |! u* x+ K相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以
/ g8 v; J. `# v6 w  ~8 z
6 |1 N- F' y! R( z- V冒泡排序是稳定的
" a3 }4 i: R# K& P2 a
; K7 S: w$ C: W" m5 K# O复杂度
* ~8 J  d8 N/ t2 c时间复杂度
- S) k; a' j5 J' y+ P最好： 当序列有序

未优化：
& K% |" x7 F* {7 a1 f6 B, \+ ]
( L! b" {, E, D! W4 }8 h' {O(n)
$ w6 i+ Y) w' L" U
优化：

O(1)
' q* L9 ~6 Q- \# I6 N
最坏：要进行 n-1 趟排序，每趟交换 n-i 次

O(n^2)

空间复杂度
# @! Z! u; T# u, SO(1)
3 l" Z2 |! b' J# e* ?; K- h5 V  B
1 z8 Q, n6 @6 x$ Q2 r快速排序
思想
分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。

所以快速排序可以用递归来实现
, j6 ^2 g0 U* d5 c3 @; B" T* n
操作
有三种单趟排序的方法：

Hoare法
/ u1 d' _# t6 t+ o设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间
1 Q2 r; R0 U6 c; |5 @
& T% I1 q! N' y% O( J左下标 L = begin，右下标 R = end

设 L R 相遇位置为 meeti
0 k- \8 F# S' v1 u1 N. G" M
2 m& v( O, V$ o7 M8 B7 m# r2 V​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”
. ]) Y& q0 y1 i6 E' I$ }* Q7 G$ G
% |, D* \2 ?+ t4 u) b​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“
6 N( A2 ?$ ?  F
选 键值的下标 keyi
# H9 C% R9 i' E& l. y% m2 @
左1位置作 keyi，则 R 先走
1 e7 C1 S' ?! p0 S右1位置作 keyi，则 L 先走
, u, A' r$ v( OR找小，
: X; l" G( p" f" f0 a
找到则停
遇到L，则交换 arr[keyi] 和 arr[meeti]
L找大

找到则交换 arr[L] 和 arr[R]
遇到R，则交换 arr[keyi] 和 arr[meeti]
% f4 [) p; v7 E! s4 X7 q" E/ I# @

解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
3 b( @; R" e3 L  ~1 J' |! D4 [答案是肯定的：
" Z0 @- T5 c8 |' M% k

, S) d/ f( N& c( Q
, i0 v$ m4 r: y; D3 G9 ?+ D
' @/ |! h" Y4 P* y3 Z) P8 Q//[left, right]
/ E9 V; I, [5 g1 b0 z+ h$ C7 xint PartSort(int* arr, int left, int right)
{
( q+ J$ U6 \% k5 f        int keyi = left;
3 s- v6 y3 I3 ?+ @3 H        //相遇则排好一趟
        while (left < right)
        {
                //R找小
        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
                while (left < right && arr[right] >= arr[keyi])
$ t9 K* v9 K; x) U. m                {
                        right--;
4 V- ?  z3 e0 S& W                }

0 }7 E' Y0 n) E* Y* I                //L找大
                while (left < right && arr[left] <= arr[keyi])
                {
                        left++;
& n9 z! J* }7 ~% i% d                }
               
' x" F( @- h, u4 [        //相遇就不交换了
                if (left < right)
0 z* S1 I  z6 A5 _. `# T3 w" x- _                        Swap(&arr[left], &arr[right]);
5 E5 V' x  C$ ]) Y. B        }

. j% C$ E5 O; a& x! Q- K        int meeti = left;
; L2 o7 X- E2 c4 U( `
+ R6 T) G9 g; q% j        Swap(&arr[keyi], &arr[meeti]);
1 b6 `" t$ |/ [2 d9 v3 R
4 C+ O& T( Z' n8 q3 u        return meeti;
* r2 }1 \) _2 I; N8 C}
5 w% g! \6 p; {, f3 n- P4 g' e
1
2
& }& u, l/ r+ n# l: r4 u3
4
8 \: D6 b# o) z7 r8 ^5 T5
; y+ H) l, K+ {4 u, a  w+ b/ K6
7
8
9
10
# x; N3 v. ^9 G11
0 T; `8 b# V2 [$ c# p, s12
# S2 D' b  X# a% i# H1 C13
14
15
16
( U  Z6 e- E: |' b17
0 g0 M8 h! |1 \: K* P- A4 [. T18
19
3 Y: y" v9 P8 A+ z, o" R( n0 R20
" E' @$ U; e+ `7 A, L7 h/ B: }21
22
23
& Q$ `& X* r. s) m7 X2 R; g24
25
26
) {8 _0 l; q9 F2 P: c27
28
1 M9 i9 J8 ]! q$ Z29
- `) l6 N  s( h& H& v30
% U1 J; E, o1 f. q! p8 W31
32
# e" g+ V( l$ P  h5 D
/ c/ @. ?' X8 A& j& M5 x
( k* L8 y' o1 Y解惑：为什么key要选左1/右1，选中间不行吗？


% J! b, H. @( r" d& J可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深



. J: u5 ]: r  ^4 I( t% I# d
非常容易栈溢出，怎么解决？针对有序情况，优化选key
) z( D/ M% v2 z: I3 `; S
% K1 h6 ~# H: l; t1 ~优化选key
8 W: G" M( H5 R2 b& ~随机选 key （是一种办法，但是不那么彻底）
& N+ m4 x4 n0 o3 F8 x( }5 n选中间位置作 key
解惑：那先前实现的单趟排序不就失效了吗！
& m7 g, v6 a# X0 a' j$ }：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑
7 t' R8 h8 d( v. q" K* K0 X& c
. K& d; S3 D/ `* p. t5 Y解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
7 Z$ Q' s+ s! X$ d7 r  ?前辈给出三数取中的方法

- ]. Y9 Z' z# p3 x6 ^三数取中
" W# d# w/ W2 r+ l在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
3 K7 k2 j+ J% Z# R- X优化选key后的Hoare单趟排序：
2 Q$ S4 e# T) |- H0 X6 E9 C
. N7 G( N- x6 b% Dint GetMidIndex(int* arr, int left, int right)
{
        int mid = left + (right - left) / 2;
( w9 T$ n& Q8 y//  int mid = rand()%(right - left) + left;//增加了一定随机性
$ p2 S2 _5 \# |6 [  c5 ~        if (arr[left] < arr[mid])
) e( t- r( ?2 ?; P: p: q        {
                if (arr[right] < arr[left])
                        mid = left;
! Y( Q" s3 ]# z1 P. s. c                else if (arr[right] > arr[mid])
( n* C4 c1 G  R9 B3 a+ k                        mid = mid;
  F8 Q5 W1 m9 S! B1 k7 {% r                else
                        mid = right;
        }
        else//arr[left] > arr[mid]
        {
                if (arr[right] > arr[left])
1 S+ }- s# g% K4 O4 p+ Q% r5 u                        mid = left;
                else if (arr[mid] > arr[right])
                        mid = mid;
                else
9 P1 ^7 J6 w3 q! Q: O" P                        mid = right;
        }
' r# V: x, M: s- l3 i( H. O        return mid;
; k; x2 S6 U4 W' _$ q8 C& m}
7 d* V- V4 {5 E) V, j- I# j2 h7 j
3 z7 L1 O" ~# B2 p. eint PartSort_Hoare(int* arr, int left, int right)
# N+ I8 S4 ]/ f5 d! ^! P  Y2 D{
        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
        int mid = GetMidIndex(arr, left, right);
- u* K1 c& \* t4 [, U0 [$ |# r3 {7 G
8 h/ Z5 h- F) ~        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
8 T  X6 I! p0 [" r! n) C% P        Swap(&arr[mid], &arr[left]);

        int keyi = left;
) y9 l5 P4 N6 O) ]4 w        while (left < right)
0 p# l& J# ], b& ^        {
                //R找小
% d* R7 S5 E% R/ K) |) U* r/ {                while (left < right && arr[right] >= arr[keyi])
0 W) N3 a/ Z/ ^8 `                        right--;

                //L找大
                while (left < right&& arr[left] <= arr[keyi])
) D3 h/ Y) e$ f7 D2 L6 ]; c* g                        left++;
- s; z3 x$ |4 U2 p
                if (left < right)
                        Swap(&arr[left], &arr[right]);
5 |7 w4 s5 Q: n4 l        }

  Z+ `1 X7 j; I9 L. ~  d        int meeti = left;

        Swap(&arr[keyi], &arr[meeti]);
6 T6 P. Y& T' H0 o4 s$ x, K* L6 w8 {
. \5 ~& y# g" W; ^6 r- Y        return meeti;
}
  \  i* n3 I. C  e0 r% K
1
2
3
8 j0 k1 @7 f3 o, Y4
5
6
- a$ l* {, M- o9 w' Q  P7 y7
8
7 H' I$ d$ t" f: Z. @9 S2 j9
10
11
  p- v; T, X! h" s' I) y12
8 H5 z" K+ P3 {9 U- L1 j% U5 |13
14
* T+ i6 N; n! u* o15
* i6 i( I: v6 m3 r: B* a0 y  ^9 d16
+ C8 @8 _3 n: s% [* @17
18
* z) N1 N$ T, ?0 o2 h+ h19
20
21
22
9 M7 f" _& D% I- f7 {23
4 c4 k: `# O8 q( q24
6 J$ p/ J. S5 S9 T8 ?0 a3 V25
26
% g$ j$ H# W% `- j- x1 q% d4 u' _27
28
29
; H& ~5 c9 J3 Q- n) o' a30
8 z& x, y% z7 _: w- j: }  D1 M4 P. V31
32
% E3 [, j1 o: C6 ?6 ]6 d33
34
35
36
* A; b# h3 r7 T37
- v8 I6 z% F0 ~( x6 x( m38
39
; V5 [0 {2 ^6 b40
41
6 t! ?0 o( j& i42
# v' ?9 j2 _, `3 v8 t4 W) q43
, \# k3 f, D" E' q3 A44
- W0 F: p& J  T45
46
47
48
49
  h% f, o1 C, m50
+ x" i/ d! U. }/ Y0 F4 v  a! w1 W' ?& G51
52
53
4 s/ L- w" Z, |2 ^; x  }4 M" Z54
6 c$ z" V- r8 l( Y2 C6 q! q* n挖坑法
8 S& d2 U# r2 N' {2 ?) _初始状态：L作坑，其下标存为key
$ J- v; \  M* T(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
重复 (1) (2)
最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]


int PartSort_Hole(int* arr, int left, int right)
{
        int mid = GetMidIndex(arr, left, right);
; x# F$ ~  v$ K        Swap(&arr[mid], &arr[left]);
9 \* H( G& i5 V4 `" R5 R
$ q& t" W; Z: C* m* X        int key = arr[left];
        //L作坑
        int hole = left;
        while (left < right)
        {
                //R找小，扔进坑，R作坑
6 X8 h# H* {- Z3 w  b* \                while (left < right && arr[right] >= key)
. g+ Z; d8 W4 C* O" w                        right--;
! d5 g. k  D4 a+ ]6 |$ b                arr[hole] = arr[right];
                hole = right;

                //L找大，扔进坑，L作坑
                while (left < right && arr[left] <= key)
& t5 {3 `/ E. h4 ^9 g8 r! H                        left++;
                arr[hole] = arr[left];
                hole = left;
+ O- F$ r! {3 [2 @/ y        }
        //meet
. S0 r1 S- H8 k+ w0 u        int meeti = hole;
5 y# z" J; g' |3 l: p, ?        arr[meeti] = key;
! H9 x8 l/ _. o  i  N, B
        return meeti;
2 P! L9 Y) L2 d; Z}

3 I- i- ?! M: ~5 c, S8 g+ L6 o' R: M1
1 G) G6 b- K2 a, k: w8 K5 W0 z5 c2
3
4
5
/ j7 k, ~. J- g! P5 m6
7
8
! w3 v) p  s8 p5 g( v6 y* f9
10
  B- B/ K  w: l1 o, V11
2 g$ B. E! h) C- z' U5 F  x12
8 U6 Z/ X: u/ v* F7 Z" ~& i: L13
0 S2 e5 {. p! Q+ N4 |14
15
16
2 ^- }: T+ s! D% ~7 V! ]# v' C17
18
19
20
& W  \$ x# C5 n6 o" x% I; O21
4 b! I2 l  g: r) w22
23
24
25
26
* E) A7 L, j4 S8 j1 v27
% S! Y% a: B1 G5 ]% j28
! c: q2 G  m! d; n# Y前后指针法
此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多
7 A" S* ?. ?9 A6 `. b: ~' p6 h
cur找小，找到则停
++prev
2 f9 P' o; G" a/ p! K5 x- j3 H如果 prev != cur，交换 arr[prev] 和 arr[cur]
7 ?4 P: P9 e6 z如果 prev == cur，不交换
! n& K1 n+ m; @8 e0 U) U2 H) J2 C3 S当cur越界，代表找完，排好序了
* U/ |2 g- q, \# I* l; Z( Lprev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低

0 h; d+ H' b3 \: q/ |

int PartSort3(int* arr, int left, int right)
; d) F* p. f3 n! {4 \% d- {& B{
        int mid = GetMidIndex(arr, left, right);
) {! w4 K( H' L6 D4 q+ L2 @+ R        Swap(&arr[mid], &arr[left]);
       
  //int key = arr[left];
        int keyi = left;
3 S4 l# m' z4 y$ g. S, e
( {7 j" h; ~3 O, e; T        int prev = left;
        int cur = prev + 1;
- E- i; P( g5 c( V+ \+ T       
' B, R" Q+ e" R9 V4 B$ |    //cur越界：找完小的，prev的左边全小，prev右边全大
        while (cur <= right)
        {
2 h3 h& k8 n6 k2 c$ _; c8 Z) f        //++prev == cur 没必要交换
) P- ~) F& O, t$ v9 S7 y                if (arr[cur] < arr[keyi] && ++prev != cur)               
& G& ]( C$ F6 t$ O4 f( t                        Swap(&arr[prev], &arr[cur]);
" {7 j+ Y; X7 j6 g: {9 u
                cur++;
& [3 P' Q1 ?* U- ^/ K        }

2 T6 e, F" T+ \4 [- ~% O3 C  n        //键值存是的值：
4 s1 q; A! ^, R        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
        //Swap(&arr[prev], &arr[left]);//这才对
    //键值存的是下标：
        Swap(&arr[prev], &arr[keyi]);

" l' ^) h9 B" d$ v3 @        return prev;
! m" C3 D7 D4 W4 C}
. V* q) ]  V  _! P" c8 f( \7 k% P
$ b* D/ u8 E0 q1
& j+ a9 t1 Q2 Q3 J2 L0 v( V6 F  v2
3
* t; v. M: O; R) @: e! Q4
4 U1 C0 R2 b4 t+ @  w" b5
6
7
0 b6 B! Z; ^- F  Z# E8
, N, S9 H1 l" ~7 j9
# U% c  g9 s8 u10
) M+ x8 y: u& p& \11
12
$ |' K: j  e& d% O13
* e! s6 i1 {( s. a0 n14
15
16
17
18
; ^1 K8 |* y% O) i9 \) E6 a19
& Z& H7 Z' Z7 K  L20
  z' c# I9 j$ r. O3 k1 A21
2 P* i% _: j5 l; \2 q22
23
24
25
% R+ c# Q/ `8 [9 E* B" }. t. h26
27
; @. s7 f6 y- E8 s28
, c5 Z, O- A4 f' N) V29
整体排序
递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排
' F# }2 v% Z- S
8 C7 \( W$ m; W/ T( c4 S/ i( f//[begin, end]
& R5 M% P1 _' dvoid QuickSort(int* arr, int begin, int end)
{
        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
9 G% h, p& p" g2 x        // [begin, meeti-1] - meeti - [meeti+1, end]
                //1.begin > end:超出范围
                //2.begin == end:一个数天然有序
    if(begin >= end)
        return;
3 v5 M% Q0 X, w8 [2 x
                //排好meeti
$ g; }( N& Q1 g6 s& T3 ]7 v  i/ g5 {                int meeti = PartSort3(arr, begin, end);
- N  s5 c( d  ^- @! q& h. J
                //排好左右子区间
                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
. ]: d4 N( d" H, Q2 D9 X        }
, k- a4 q3 c, O3 k* z$ c}

* W% j8 e  |" f* _" U8 A5 y1
2
1 k/ a8 v* }% |& x1 e3
4
9 g6 o3 m8 o6 H0 X# x# h5
6
. S* _/ s7 W- i) {  L4 W% N7
5 L: W* o( A3 S: P6 \: a: `8 c8
) J* |( L1 B% a: {9
# G8 |3 @; N+ g  O" J10
/ I- e/ ^% e- ?11
. ?# }7 D. r- b$ Y8 u4 H; M4 a$ m12
4 z2 `* F9 D% `) h. v13
14
0 \0 R4 x0 }' _& \: d& c" }15
16
% U$ q) C4 l4 b+ n17
, y- Q+ i" H* T$ ?- C, g5 S; n18
…
! q+ J: y7 U4 {$ ^# |4 D/ e
0 P2 a% {' n& F没想到吧，还还还还有可以优化的地方！
. o; r; c: D5 i8 E1 v
) ~& L/ e9 @8 V5 Y% V优化小区间
: K- T9 O; B( y5 H

如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序
# M; R0 }8 b" H# ]/ y& k
! {4 V5 v5 S: X# z4 h5 \  m4 U那什么算是小区间？
+ {, f$ Z9 l1 s/ _: ^
其实小区间没有确切标准，8-15左右都可以的

, q- c* ^8 a6 N2 r/ w
2 Z; M( E, ]8 N/ ]! b" l这里就把小区间定义为 含有 8个数或以内 的区间
: m1 J/ Y+ e8 p) S$ Y. N# I
//[begin, end]
* ~9 n- g3 J* A! ~, Dvoid QuickSort(int* arr, int begin, int end)
: E  K' W/ }' ^8 M) m3 r{
        if (begin >= end)
( |9 L2 a( F  |' b* E7 y                return;
9 v) [9 E  P. a& s5 S( B
& v1 W! a0 \! h! t5 W4 n        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
        {
1 i+ g1 U" E5 ?# E+ O! f                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
6 f. A2 A) Y, d+ @                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
4 `( P; ?9 j* N        }
! k4 e9 d0 c# y: L        else
        {
. i8 v& k& u4 c2 c                int meeti = PartSort3(arr, begin, end);
9 H* p8 h: s% d) Z3 `. Y3 c1 O
                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
3 [+ w6 |2 c; m0 e4 g1 n) s( H        }
}

1
2
0 l6 `) s) Z' t0 e6 t1 \3
; t& y. F" f8 s" v4
5 a) Q0 M  c: i! }5 E5 V5
6
9 m7 m4 w! D, p8 m7
8
3 z0 T$ t5 ]/ Z2 G9
10
11
+ d8 d4 N7 N9 _- h12
- W4 N1 S8 W* w  [' I3 J13
9 F4 q0 Z+ J2 ~3 f9 H14
, [4 R8 P( {1 D% `0 W$ s" o/ f15
2 @% \. q* \1 U16
- a$ ?5 d/ [5 @0 L, A6 f17
8 t5 R1 L5 M7 G; H5 [18
  J5 g; `$ V6 I19
快速排序非递归
/ ]9 ?# V7 J( R, x为了解决彻底递归深度深的痛点，我们来试着把它改成非递归

4 `, \0 d- j) J9 P1 _/ F) O  h思路：
  p  D5 Q0 x3 |2 A5 X5 Q递归深度深，栈的空间又小，会栈溢出…
4 W1 Y. H7 b0 f- j
2 u1 X  w! `( [3 z7 y0 q9 z那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！
" ?$ @4 X( z* \3 A1 J/ x
; m! m9 f! l  @8 Y+ O/ N7 B9 b" p核心思路：在堆上创建“栈帧”
8 h3 i: {( ?  {" m% Q4 X9 N1 |
) x% k  R( y. n$ M, A快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的


7 S7 [1 P5 J" K
, }! \, T. {* x' ?0 R+ @在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：
$ _0 H& U( ?! [! e* b! _3 {/ o
先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
先取end：先入begin
5 Z% \+ o3 v; ?* c& Ovoid QuickSortNonR(int* arr, int begin, int end)
- a4 f+ m6 V( o% A+ i: N. L{
5 P5 U! m. g- j0 f2 O        ST st;
$ R( [$ W+ [1 _8 Q! L2 ~# B        StackInit(&st);
       
    //先入begin
        StackPush(&st, begin);
1 m" M6 ^# ^. @" O! x( Y8 W6 C% l    //后入end
. P) Z7 W% V9 e* d* J/ ?, X        StackPush(&st, end);
7 I, s, s$ g( I
        while (!StackEmpty(&st))
) o: Q+ _9 s0 B        {
                //先取end
                int right = StackTop(&st);
                StackPop(&st);
; \$ i- Z* w( e" d9 b) B& f; p                //后取begin
* }- K* A, Z, ], y  k2 k& g  F                int left = StackTop(&st);
                StackPop(&st);

/ r5 ]/ H& R1 ^. [: L8 ~                if (left >= right)//1.只有一个值  2.区间非法
                        continue;  
- V1 h$ K# V* Y1 s) |, ?) T                               
                int keyi = PartSort_Pointer(arr, left, right);
, ?: {1 \9 d; }4 a
                //先入右区间
6 N* L" P2 \* p4 j                StackPush(&st, keyi + 1);
                StackPush(&st, right);
                //后入左区间
4 B2 d) S8 D; {8 |6 ^0 z4 i                StackPush(&st, left);

  O2 z& L( c; P                StackPush(&st, keyi - 1);
        }

) G, R( x2 g8 r& Z( z        StackDestroy(&st);
8 _* a; v9 d$ |/ K1 L$ D0 \3 C}

1
: k4 B  v' @3 b! c( ]$ [  I: {2
3 c) {0 F- q3 C6 l' |3 R* @3
4
5
6
7
0 V5 Z1 P. S, ]* A; g7 \8
9
10
- c6 @1 d3 r6 s( z6 O$ _5 [11
12
8 }7 S0 U) c! I* P& c13
8 j- H$ x# _1 R5 N& ]14
15
' ?6 J, U- J7 i3 v1 S# p16
- R" A; j  u# e9 D; l17
: s5 {+ {8 ?4 ^: ]18
19
0 n: X4 G4 G/ L' a- B- }& g; Z20
21
22
8 f& g) ]1 d* T# Q  P23
24
. D2 C, D& w1 L& a( S7 ]' q25
+ U& h! X) b8 M# o% E, ~' o26
27
$ K  n2 @& W! G$ B5 h$ t28
29
30
7 }- r3 D8 M0 c! u% _$ J1 E# c7 l31
' G4 a; `" y  f1 w# g" {3 w32
7 K: Y* T4 Y* s) ]. X33
- i! }; |6 y* U' N34
( t* C( [2 _! H0 U  h6 t35
. l  K! i% Z6 \$ }, T) K. h数据结构栈的实现可以看博主之前发的博客
+ X$ R/ L, U' V! @
& V2 d, y: w* K, y" k" Z( V
归并排序

…

4 s6 Y" G9 h6 t! e性能测试
void TestOP()
( [5 ?7 @7 w# @5 M{
        srand(time(0));
+ \' d/ F9 r( @        const int N = 100000;
        int* a1 = (int*)malloc(sizeof(int) * N);
. }( E- L3 d6 o* F9 \$ E        assert(a1);
' i8 X9 g) x) C1 ]# Y2 o; ^        int* a2 = (int*)malloc(sizeof(int) * N);
0 }! c' C* ~! D' ~- R) y9 b        assert(a2);
        int* a3 = (int*)malloc(sizeof(int) * N);
* w' o# r: V- [& p( W2 ~0 `% ]        assert(a3);
        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
        int* a5 = (int*)malloc(sizeof(int) * N);
        assert(a5);

        for (int i = 0; i < N; ++i)
) x. L, C0 O- `' l$ d" e        {
                a1 = rand();
                a2 = a1;
                a3 = a1;
3 m0 H+ V" k5 ^                a4 = a1;
                a5 = a1;
        }
; o) R& P6 j$ I8 l/ q
$ E* ?' _5 v6 Q9 W: B9 i7 V        int begin1 = clock();
! |5 P3 ^& Z) |        InsertSort(a1, N);
! s7 D7 f+ G- Q) L% v        int end1 = clock();
5 G) E/ Q/ D( u5 J4 y- `
% m+ d% Y: c( l# }$ D        int begin2 = clock();
        ShellSort(a2, N);
        int end2 = clock();

        int begin3 = clock();
' U# M. n9 \5 o6 N! M        SelectSort(a3, N);
0 _) b- p+ A5 a; [9 ~        int end3 = clock();
- o& Y7 \% e$ M( v1 H4 ]
6 B& ?9 ~7 e# ?. b; ~7 p        int begin4 = clock();
        HeapSort(a4, N);
! {8 U( o! {3 S% q" |3 G        int end4 = clock();

        int begin5 = clock();
+ N  Y6 f& c, B1 t/ |6 P        QuickSort(a5, 0, N - 1);
                //1.中间key
                //QuickSort(a2, 0, N - 1);
9 Q+ b  Y2 L. P) D                //2.三数取中
                //QuickSort(a2, 0, N - 1);
                //3.小区间优化
0 ]4 O3 e  C$ d0 n5 w/ |" @/ v                //QuickSort(a2, 0, N - 1);
. a' q, j; x' Y+ o        int end5 = clock();

2 h; {/ f. `  d6 {6 K5 d$ q
- _8 ^- [9 w( j. C        printf("InsertSort:%d\n", end1 - begin1);
        printf("ShellSort:%d\n", end2 - begin2);
+ Y3 H9 E8 k; M        printf("SelectSort:%d\n", end3 - begin3);
        printf("HeapSort:%d\n", end4 - begin4);
        printf("QuickSort:%d\n", end5 - begin5);
8 L: i2 x" W6 r8 R3 [
+ A' o5 q9 g. ]2 S! y5 z        free(a1);
        free(a2);
        free(a3);
        free(a4);
7 k" D5 j7 C6 O0 W* M( E        free(a5);
}
5 Q0 o# m" q9 U4 h+ \9 ~% H3 q1 m
9 n. L/ q! [' f  W! g1
6 i# u6 C9 u! p. l- c" X# E2
% {/ r+ ~! P% f2 [3
/ u3 S" v: Y8 _$ y8 ^, K4 h4
5
6
7
; M9 c* _. c1 ^, h8
! ~8 c8 o2 j! d, ^7 U9
10
11
( x4 J* G9 ^! A3 k6 P( G3 D/ k12
* E6 n. j# {$ y' Y1 R13
# e  L2 f# ^5 E3 f& u14
# ~% _" ]2 \, e' O6 U15
16
17
18
19
20
21
/ R/ o/ Q- K* ]$ i9 y22
23
24
2 |  P: t+ H' O, p# J7 F* U25
26
27
. [* q$ N" L# X1 T: G1 f4 t: P  v) j28
29
. N$ L% K) l4 X% o+ q, Z30
7 v- K# t  P6 _1 \* K  H* B31
32
33
34
35
36
; A3 i" y& D+ Z- Z/ I37
38
' `9 m+ @, d. o1 ~* q& E* j( ?39
40
* V( U! Y9 v* R41
42
6 j/ e1 w4 W/ s% |. i0 j8 b43
44
) K( c' ^# c  @* L+ o1 T45
0 e0 b4 |  `& y/ _) ^46
2 ^+ E4 _% G7 b$ a  J6 j, I47
48
  U! P7 O6 L2 ?+ [( j49
0 c+ u' ~3 `5 C/ A6 q9 @% a50
51
5 J' C8 n. t% S$ l) }52
53
54
; `8 i. c5 P: ]# b  u. Q55
56
57
6 ~; e" B) i. A  T% ~: T& W4 Z! p58
* A0 Y; R  h- J3 \1 x7 B' q59
6 i! z7 i7 T$ |# L  {% J1 a5 |60
61
8 s" O4 P1 i/ c62
63
: o7 T4 F) w1 T- ~/ t  v9 h

7 n8 N9 Y- \) X$ e' o3 l& D不愧我们费这么大劲优化快排，多帅哦！

( [+ h; x" f& ?4 \8 W3 v差一个归并排序，后续补上！

; X) B' |, C. h% D不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
$ _. ~" D5 \, C0 ~( k% u6 v: |————————————————
版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! |' Z0 j: H- a/ o& g1 p原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832

4 V# P$ `/ z" {  k( p2 o& h
  b! Z9 u( ^& H- t% ~0 D