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

杨利霞

【数据结构初阶-排序】经典的排序算法，很有趣，有没有你不会的呢
) B: f7 K( M3 C
- ]- a. h0 W  S& }! R4 J前言
本期分享经典排序：
+ @$ I. S; H7 {( t" y0 g2 a
3 ~- c) j5 ]; l2 G& v" r插入排序
* a) C! S7 v8 f8 i9 N: L1 ?直接插入排序
希尔排序
选择排序
+ N& P' Q6 V4 Q9 I; j直接选择排序
+ v" ]( R6 m) [: ^) F; M堆排序
5 `; I! s! M0 J$ _8 b交换排序
, M* t0 X$ m# t- P' ~! h冒泡排序
快速排序
注：讲解时默认排升序

插入排序
3 d" F4 R3 f' Q) j) s' H7 j+ ~直接插入排序
思想
/ U; t8 L# Y$ R插入排序，就像玩扑克时，摸牌的过程：
( e( R8 P5 L( S8 ^, T2 T" P6 N) x0 z; ?
% V: ], ^1 ?4 R7 z8 w& ]最开始，左手没牌，右手从牌堆中摸
+ c1 `+ G8 w# [0 Q& L" y# X- r9 O右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
3 D1 I3 P& k7 Y# `  S  E  J+ J如此一来就能保证左手的排始终有序，摸完牌后也就排序完成
" j$ H/ o9 L2 i4 J; G, W: u

1 `1 W/ g( \" c4 |' T# R, q, y  K8 S8 T操作
- h( A6 U# ^) h0 X: [/ g% O" o设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
# `  p! @# \; C  i/ @+ q# l! d单趟排序：
+ t6 z) _" x* b5 O  A( i5 r每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
; H% }4 K6 n' V是正确位置：插入
不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
整体趟数：
若元素个数为n，需要排n趟
9 E) l- U* R/ x6 Q2 M6 P! yvoid InsertSort(int* arr, int sz)
{
        //end + 1 < sz
" o! I6 }( k. J) M        //end < sz - 1
- ?" P( E+ B/ M4 I: Y( T        int i = 0;
        for (i = 0; i < sz - 1; i++)
1 J) x( J4 ~$ w1 l        {
                int end = i;
                int tmp = arr[end + 1];

                //找插入位置
4 `3 [6 ~' O- `, I! N6 V                while (end >= 0)
                {
( ^6 a8 Y$ \0 z' V" p                        //不是插入位置：当前数据往后挪
                        if (tmp < arr[end])
& l5 K# t" F- \; J. \! }, M& s                        {
. {7 Y) H4 F2 _* V& a                                arr[end + 1] = arr[end];
% Z4 }4 O% \4 }1 j/ @& F5 u: e                                end--;
4 B( O" L# J0 b5 _+ V# H8 k                        }
# M9 c+ l% l8 l9 [/ `                        //是插入位置：跳出循环插入
                        else
                        {
                                break;
3 K# B. u: ]7 v/ w7 T- k7 l$ u' s' n                        }
8 ]0 n- {+ D9 g6 ~                }
                //插入
9 Q3 K. g! ^$ U                //1. 插入位置是[0]，end == -1，不合循环条件跳出
                //2. 找到插入位置，break跳出
                arr[end + 1] = tmp;
        }
}
6 O6 R0 {$ ]# U( P8 ]
9 `' D$ a; Y! Y. o9 m1
4 L) r- K+ `3 ]  C) k2
3
4
5
6
% ?3 @) |( s% k7 Q0 p/ R7
8
9
10
11
3 }* I, [# A. ]+ t$ z9 \8 F/ E! B12
/ b( ^  o5 X0 U2 j13
14
6 G* F0 f& g0 |% a, N( P4 B15
16
! x0 s2 ~6 E6 h17
18
19
# ~8 ?3 s" u3 p  g9 Q3 K& V20
# A; F  {; Y+ f! Y6 X# n/ ?# V, \21
" Y; J% j0 D3 ~" N8 z# t* @- X22
23
24
25
26
27
! _; t7 A( y& Q2 G8 {8 ~28
29
30
31

2 r6 M) O5 [& r8 @8 F5 H  i6 M
稳定性
插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以
! R6 |9 I' ]9 r( a3 Q, [/ H0 Y7 e
直接插入排序是稳定的
7 l! n& _" c3 C/ b. ?, @
复杂度
时间复杂度
( f5 B3 ]. x! \7 w+ K7 u* x最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）

; l3 \, {* F" l+ B8 uO(n)
- L  R, E) Z1 K% E% N1 m- `2 y
# M4 b$ k% G8 V) y5 e, w6 I最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2
' p! ]7 s9 Q* l& z8 p
! m% H& [( c2 r; g$ ^O(n^2)

空间复杂度
O(1)
/ \: Y* j! t! R3 h
. }; ]5 I- g7 i+ R) n$ T希尔排序（缩小增量排序）
$ U. A0 r" `( U+ A( Y希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序

* p3 k! r4 u% U优化思想
8 b, f& [! {/ Y; H" O& l7 z8 F增量gap不止用来分组，也意味着数据移动的步长，所以
: O& r: b; T! Q& Y
gap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高

0 G. }# f* l+ ]3 B8 z# x: E
操作
单趟排序：

设定一个不断减小的增量gap，也是元素移动的步长
) Q- b2 S) R4 w& D4 L1 N( O. P! C以gap对序列分组，并对每组分好的序列进行直接插入排序
不断缩小gap，并排序
*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
整体趟数：

5 E4 J+ b1 K/ O, d1 V6 t由gap决定：当gap = 1，排序完成
' L( J8 R# c! ~* E注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。

+ k: u1 X8 _/ O* dvoid ShellSort(int* arr, int sz)
: I! O; Y7 m# p# @! f{
* ]4 K2 L3 \5 L$ ?7 Y4 w- ]        int gap = sz;
9 M* ^! a3 K) G0 W       
  E8 u3 V. J% H; @& ~    //gap > 1，预处理排序
  @! d4 s1 W  [7 u% J( t    //gap == 1，直接插入排序
# j7 d, e5 o& Z; s        while (gap > 1)
        {
8 _. B+ D  _7 y. G$ Z& W3 J                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
                //gap组
                for (int j = 0; j < gap; j++)
                {
            //end + gap < sz
                        //end < sz - gap
+ P% u# p! B3 y% J2 L$ _: ]7 X                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
                        {
                                int end = i;
                                int tmp = arr[end + gap];
3 K0 M; w- N/ `$ b! x                                while (end >= 0)
                                {
                                        if (tmp < arr[end])
                                        {
                                                arr[end + gap] = arr[end];
. Z  i8 a8 ]6 c5 |, p) `                                                end -= gap;
$ e( A8 _7 g5 P! {! o& ^                                        }
$ S" {" C% }  N% E                                        else
                                        {
                                                break;
                                        }
0 Q9 V' B8 b  T                                }
                                arr[end + gap] = tmp;
                        }
                }
5 G- m: B0 C8 F0 [9 `- H3 m        }
  c! Q9 L4 p! B# H3 f3 z) \}
0 j2 G0 j% e2 [/ m" t% f
1
2
+ x* |. D8 K1 [. R7 P3
$ r. K/ H* r$ X4
0 D& M( t  u0 O5 n5
0 c+ G) x6 c7 \, `; p, Y6
; o( @4 S9 V( [6 F7
- D. V0 H5 G8 n( T8
5 N! u$ D) X. ~& x! \1 D9
10
11
12
13
) N4 E& K' G4 C6 [2 H8 ?14
- w- V- F9 V( J3 c15
3 {3 ^& J' H" ^9 @6 n16
17
1 l6 }3 Y4 j8 ?  Q$ g9 z- j18
19
20
- W# M! \0 H9 i1 S3 @1 f  z& r" _21
22
5 t. c0 y& i+ r: Z; G. h23
24
25
26
* V; @0 L3 q; y* P( P27
28
29
30
! x6 v8 j# A1 \5 n8 _1 d- {9 x7 F31
32
33
34
35
. M5 S. r7 j, k其实就是套上”缩小增量“的直接插入排序
( h6 G6 n* ]! P, j% B
& V) q8 B$ {0 n
稳定性
/ P& P4 C8 [" U, M  e$ m- k7 O+ a我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以
7 {7 N8 _7 D, x% t/ R2 I, q: E
希尔排序是不稳定的
& W8 s8 g  H! A6 K" j
: y; Y3 J( x$ B复杂度
时间复杂度
希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
4 G$ X6 J, n  h- Z  l
* v* M' b7 ^* ]3 M* rO(n^1.3)

# S* c- u+ x4 L+ ^空间复杂度
O(1)
: b9 k5 b. P# j, r+ Y' `
选择排序
+ e  E/ p! j0 {1 w直接选择排序
/ l1 i- [% J4 w" ~思想
* u; q2 \0 [9 [/ w选择排序，遍历序列，选出最小的元素，交换到左边

1 X; u9 B5 B2 i8 \; m& o
, B+ O" U" y7 w, b
优化版本：
2 @0 r8 ~9 Y1 v# G& a  L
每次选出最小元素交换到左边，选出最大元素交换到右边

. x- w5 K. b8 t操作
# Q# i: w/ j1 u0 Y4 `7 H3 y设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]

设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标
7 g3 }; A2 [# d
) T, s  j1 }$ `( h单趟排序：
* N* I. v7 }0 F) c% J! O. I" `
  _8 L- P5 Z# d5 m遍历选最值的下标
交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
（修正）
0 n, a& {0 o2 U8 }9 C5 N9 h整体趟数
2 X/ F: ^' G' R: F$ d4 p
8 v- ?. l- U+ Z/ ~3 K! T+ ?若元素个数为n，趟数为 (2/n)
/ C; E. {3 I/ u( q修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标
7 {) S1 M1 m6 c
5 b6 |) }9 M3 j8 d7 l0 U  Y' Uvoid SelectSort(int* arr, int sz)
  c0 _0 _! y( a3 L* C. N3 Z{
        //闭区间: [begin, end]
        int begin = 0;
$ T; f, J& K/ J& U6 ~        int end = sz - 1;
        while (begin < end)//begin == end 最后一个数，天然有序
        {
( H8 c  K& `, a1 s                int mini = begin, maxi = begin;
                int i = 0;
! G  L, L8 O% C                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
                {
                        if (arr > arr[maxi])
7 r3 q, E; d6 M4 x* C& j                                maxi = i;
                        if (arr < arr[mini])
                                mini = i;
                }

3 P; [+ v3 G& p+ b- I                Swap(&arr[mini], &arr[begin]);
, Z0 E- y3 L7 z: s- a% o, _
                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
                if (maxi == begin)
) P/ S7 a( A; y* o# }0 k; N                        maxi = mini;
                Swap(&arr[maxi], &arr[end]);

5 R2 Y+ G4 Y7 t) D5 p3 A                begin++;
! {8 j* u  k3 z! ?' t                end--;
: R9 t. P  u3 e( O% j        }
# @5 K  k. Y, [0 V& X" j! _}

1
- ?8 N6 S$ `4 P3 F" u% {! S5 S4 F2
3
; X, Z0 l1 |( |5 Y4
4 x$ _  y. g  s5
8 H1 _% f1 _% S8 B: E: q1 t6
7
8
$ r+ T6 O2 p' @3 s! k& y' c3 _# b9
/ j$ K$ V7 w% J, [( u$ f9 t6 S. \10
11
% a1 K) s  j) `% ^" m+ P+ ?# j+ [12
13
5 E- b. x/ {( E2 P14
. L+ I# Y3 @+ Q3 z15
; G& P9 p1 M7 e# c5 z! E7 r16
% W& H  g# ?1 x/ \. V17
18
19
' u) O: F5 J3 x) t4 y* e. c- A7 S4 s20
1 |: Q: v9 \; \5 X& h, B21
& `7 M% P9 D, S' z. c22
. I3 }% e4 U/ i3 g+ [23
24
0 b* b/ k$ W' B; }: Q25
0 T- t3 _4 C. }) T* _26
27
28
2 @% u; {# G1 q8 |" W) i2 d- t' y) h
# Y8 ~# q( g5 J1 ?9 W) }$ P6 O  ~) F
' r  V! x' u! m4 T5 Q' G稳定性
选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以
# i, q. c1 f6 n2 f8 G2 y
( j: p3 {" u: v" Y+ Y选择排序是不稳定的
3 f+ D' F* _# N2 j3 N
# J% W0 u) a& D复杂度
时间复杂度
最好：

$ |% s0 h, z1 x! K0 M比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2
  O: k% b0 ]4 v$ \, L/ M
2 c0 Y1 y9 w3 q! d$ C0 X交换次数：O(1)，有序不用交换
' C9 Z" c) `% Q7 K1 u
O(n^2)
' \( i) @8 i3 X3 r1 R+ O* u9 M' m' G
5 o+ ?) Y& v; T: @最坏：
! _$ U  W3 K$ n$ @, Y6 e
% l5 ^7 P1 y# ^" ]5 `; g比较次数：O(n^2)
( a3 F5 w, a5 J) K% n0 J% b
交换次数：O(n)

6 V+ G, D6 N6 R( BO(n^2)
* J4 v( T; i. R  D
, A, W: r' Y- t空间复杂度
; {$ t/ }/ f7 n6 S: vO(1)
7 G8 u$ l. w. g7 C- {2 K
3 J& C& p  c2 h堆排序
: E, Y0 ?; }! z3 ]思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆
; c* ?  ?( M& E, q4 h: ?
/ L" ^& ^( {  f$ e
( c( Y* ~% U6 G9 ?* r  l) U
9 g, G; @! P( Z, J9 u: Y; I操作
建大堆
单趟排序：
+ I& l" d! N3 I, P0 w- r; d选堆顶和堆尾的元素交换，则堆尾的元素排好
; `5 x" c2 K9 o6 v* M每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
' Z* i( P% @# {" ?4 @0 @整体趟数：
若元素个数为n，则排n趟
- `$ _4 \$ R; r3 {4 Tvoid Swap(int* e1, int* e2)
{
. `6 q; Z  [$ W! F( O        assert(e1 && e2);
! s+ Z0 a, L; K. M: O9 [
. \* W' u$ P- c6 P7 U        int tmp = *e1;
        *e1 = *e2;
        *e2 = tmp;
6 Q' C' t# A! U" L) g4 x  |}
  ~# |; g$ e3 M& n% |; O% u/ ?/ Y" T
void AdjustDown(int* arr, int sz, int parent)
/ i# H! V# o6 j{
1 m# Q, `2 j  ~. Y, D: e8 j        //建大堆，排升序
        assert(arr);
       
2 M- z1 @) J! @5 V) V, j4 I! U    //默认大孩子是左孩子
$ Q4 M+ A1 q7 X( Z        int theChild = parent * 2 + 1;
        while (theChild < sz)
        {
        //如果大孩子是右孩子则修正
                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
- S; X( G4 F. w& N4 V+ s                {
8 t3 R- a  U, l- e+ {$ _% W, d; a                        theChild++;
3 w, f, M. p7 ^7 `( v5 y. n  p                }
) {0 o. z: b/ z2 Y, I                if (arr[theChild] > arr[parent])
                {
' I0 |4 I; \/ R                        Swap(&arr[parent], &arr[theChild]);
            //迭代往下走
/ V) r' u+ `. w3 ~                        parent = theChild;
  T* m  F+ x4 c; U' ~! y                        theChild = parent * 2 + 1;
3 E! K! Q# d8 Y0 k' F6 o: |3 K                }
3 a/ B" M% ~6 Z! l$ I5 y                else
                {
5 M, K8 d& t/ f3 o                        break;
                }
2 B. C# C) A6 e* g. T        }
5 E; R" D. E: N7 u2 }}

% u% b* n$ X: tvoid HeapSort(int* arr, int sz)
{
        //1.建大堆
        int i = 0;
        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
6 g6 J0 U' D, d. @" F" a- u        {
1 I! P6 P: Q5 O8 p, z0 g3 E  P                AdjustDown(arr, sz, i);
  ]$ s2 v5 P. U" r' t% k& }: M# h        }
: D% B& O* e) h
        //2. 选数
- `2 m4 D9 t: @( {        i = 1;
        while (i < sz)
        {
8 E! S5 @1 T% a, a0 _$ J9 S                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
                i++;
        }
7 I" f: N1 G) v% E}

1
# m/ p# o, W# E+ d- X, E' S, p2
3
4
2 o* b1 N  E$ @: B4 I5 M6 G5
- t4 @7 {+ e8 y+ k& c6
7
8
1 j+ o  z5 B5 B$ E: X5 |# I3 W9
$ X  r& t# J' Z+ U; @10
11
12
13
" b+ q2 z( A, j0 E14
15
( k1 o2 j6 t# B3 A16
17
18
19
* X1 w7 |/ W) A3 |5 K6 n% O20
2 R2 }7 s$ f, q21
" M" j. n+ Y9 Y: H! B22
23
24
# i: x+ m+ u* O- k25
26
! a7 A& A6 W0 i1 `( W27
2 ^. N! ]" S$ c3 W( J" |) y5 b* z28
4 d9 H3 O3 a( Q7 X1 @, v29
$ k3 M- O3 ~( w1 l9 y% e5 u30
31
( n, }" f( C4 r+ ^) k0 V" C! ~32
* [: e& W6 g/ }- E33
& W1 J$ T6 X# R+ u" R4 v5 T34
" C* |% S+ |$ q3 H, K' j: C) v9 w) }35
36
37
' K( _9 O* {6 Q; x2 M: V5 p38
9 _" R4 B/ S  b- c+ i39
40
; r5 e% y* O9 J9 \41
42
43
44
45
" {" `: I, ^! T' y' n46
% F+ ?$ D2 Q! q47
48
49
$ T% J6 b6 ?, R) o! Q2 A$ T50
2 S# G+ C, D7 \3 C51
  M# C6 g% q4 `0 t9 m2 n$ M7 B52
( }+ O, ~& P  l. {% b4 |9 Z53
54
55


稳定性
3 r# R' g% I5 j9 ]# }  s% z建堆和向下调整都会打乱元素顺序，所以

堆排序是不稳定的

+ t( G9 C5 M9 h5 A, }6 z复杂度
. F  e; ?4 m: |: U时间复杂度
& P5 Z3 x& w/ p$ Y8 u% y单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为
1 \, v. ~% \8 l0 H
; Q' _' p4 X# B. K; lO(n*logn)

空间复杂度
0 u, D' Q: q+ }5 X5 D, t( v) }, A原地建堆

) u4 T- m+ y" z& {8 E# yO(1)
' S2 y6 g0 I8 U. C" i  ^4 Z6 B
交换排序
' @3 h! o& {2 w冒泡排序
思想
冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素

# M8 u8 q( R6 [  r3 Y
4 t4 g5 h2 R4 \" T$ S! d  H
操作
4 L4 y6 b1 Q! m: H单趟排序：
  z( Q  n8 q; I每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
% J' N" V3 x$ A每趟排好一个元素，所以需要排序的元素每次减少一个
9 |, K0 d/ w& ^' L整体趟数
0 h) R. |/ ^; w1 s0 k* M若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
! E+ v6 x* n. yvoid BubbleSort(int* arr, int sz)
{
        int i = 0;
+ A: ~/ ~+ W* ?" C+ Y2 _8 R# [" j" {# `        int j = 0;
        for (j = 0; j < sz - 1; j++)
8 T- Q( n4 B6 o2 g% B        {
& \' U& b/ I# J' |" i, T                for (i = 0; i < sz - j - 1; i++)
2 L0 _2 t1 Q3 a                {
                        if (arr > arr[i + 1])
                        {
                                Swap(&arr, &arr[i + 1]);
7 ~5 I, s( Y# {1 B1 ?; ?                                flag = 0;
                        }
                }
3 x8 X, r2 F- S        }
}
3 P4 Q- E0 d) ^8 M+ ]( ?  d
# E& V- \' `9 g- A2 Z1
4 J% T% `: C) ~$ M$ h3 |; A6 Z: p2
7 n- `1 W2 X8 K" \  }" g3
# l( q/ a: t0 H! M6 p% E' k  u4
5
( m: |$ n. X% `  c" x6
7
8
  L# l1 o# q9 {" A9
10
11
12
  F1 n& ^7 j# i13
" W5 [) ]* l3 l( s8 A% D$ h( M14
& c' |6 ?8 f; n6 Q15
9 T- M$ B7 s: x, L16
优化
当遍历一遍发现序列有序，直接跳出
8 l$ m5 q* D. q& V3 v
* m' E( Q; R( w  k+ qvoid BubbleSort(int* arr, int sz)
{
0 A* ~3 V3 N4 F' l3 m        int i = 0;
* @$ e, w" H- ^. Q- _8 C        int j = 0;
( Y' n8 H4 j& z( r/ i1 X% ~4 a2 z# T* G        for (j = 0; j < sz - 1; j++)
        {
                int flag = 1;
                for (i = 0; i < sz - j - 1; i++)
8 K! I- O# F4 X% S$ ^, y                {
  C! O. ~4 _6 |' ?" }6 v; P  k                        if (arr > arr[i + 1])
' t: e1 m# Q  C5 D+ Z# i                        {
' G4 T1 x- w0 j, m                                Swap(&arr, &arr[i + 1]);
' B6 w1 ~' T8 N1 s! h* D3 I                                flag = 0;//不是有序就置0
                        }
: x: @; b$ O# O6 ^7 z1 c                }
                if (flag)//如果一趟下来还是1代表有序
6 A% r) w2 b# ^, Y% E1 g+ W. w0 D                        break;
        }
}
; a1 B8 R- A% W
1
5 D8 X6 t4 j3 K* n% m8 T2
3
+ ^# {) R. v/ q. m4
: a. K: I4 ^# h0 |0 S% }5
" A  C- O: n" Q) C0 I6
7
8
7 q4 ~2 k3 Q2 ~9
10
11
12
13
6 n- g1 z- D! r$ ]1 \5 ~% I. z14
/ G/ A7 T, I+ E& o' A! M  w$ V15
16
1 I( c3 D2 c0 G$ r. ?17
18
, R+ t6 D' s  x5 f" Z0 |( v19
0 J  ~  {/ c! F2 v( n
% J+ d( [% x, t% |" V! o6 w
$ J2 x/ h) l$ a4 K' ^+ h; A+ l- x稳定性
相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以

% ?( {6 m$ b% i6 o* {冒泡排序是稳定的
6 K8 V6 S3 @2 \* Z5 {$ t
复杂度
时间复杂度
* F3 y( e/ N3 }# @最好： 当序列有序

未优化：
9 m0 _# L, ?5 v% \. D
O(n)
% W0 C% [& ^! W$ C! n/ C+ q
$ o" }0 _8 g( k! p2 |优化：
) l8 h0 C4 S$ o  ~- f& a
O(1)
& W# M1 t7 G; a  D  R& G3 t" _
3 S8 R6 Z8 G& Y# b最坏：要进行 n-1 趟排序，每趟交换 n-i 次

) l0 h0 C3 ~1 R$ e9 Z. Q  R8 ~O(n^2)

. \0 i9 x  s% i6 r* e空间复杂度
O(1)
' X! m9 }, ~  V( G
( a. Y3 `# a4 {3 K" {2 E: }快速排序
" X. d4 E! {1 D, k! K0 S思想
分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。
8 [0 _/ `1 s3 W1 ^  g
所以快速排序可以用递归来实现

操作
有三种单趟排序的方法：

  s' N+ X; q2 N, h7 M, S( hHoare法
设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间
; S9 G& M* Q3 i$ J8 h: V
左下标 L = begin，右下标 R = end

设 L R 相遇位置为 meeti

9 A) s3 I5 _4 [3 _. [* n​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”
- ]) e% w4 o3 l3 C& o" ?
8 c( U; _4 y" T7 h​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“

选 键值的下标 keyi
9 w: [) m& J# Y5 K& k% Y1 o; A
" S1 {( ]' ]: m/ m9 V左1位置作 keyi，则 R 先走
右1位置作 keyi，则 L 先走
R找小，
9 f; E+ W. x7 q3 k& d
找到则停
3 F( O6 Y- D2 W遇到L，则交换 arr[keyi] 和 arr[meeti]
, ?4 d  y2 i" Q' O" R4 A4 b& t0 zL找大
# ]) V! l2 n( W4 c/ o
! y& g7 ]; d8 m0 S0 F找到则交换 arr[L] 和 arr[R]
1 I+ o: C: j* A4 [. \遇到R，则交换 arr[keyi] 和 arr[meeti]
( W6 p( _. z2 ~4 W# ~+ H, V9 q

解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
答案是肯定的：
5 a8 B% c; E" o. w3 z: |; U% k

" C( Z" t9 M: ^9 B% @

4 K- j3 ?+ |2 U//[left, right]
% I' }7 h+ P' X7 |* Sint PartSort(int* arr, int left, int right)
{
) C7 p( \8 O. i  d/ G        int keyi = left;
        //相遇则排好一趟
        while (left < right)
- `) \! C4 W# M0 d# H7 i4 N/ k        {
                //R找小
( G+ q; D4 L/ e& y" F/ `        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
0 s" W* G- a  ^. H7 M% C        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
8 K5 i7 R6 F& ~" _; u+ x& j2 H                while (left < right && arr[right] >= arr[keyi])
                {
0 M9 z. H4 D9 P+ M4 X                        right--;
. S, ~/ g  A0 l; j                }
8 e8 c  @9 ~6 o7 M0 |3 \; r
                //L找大
                while (left < right && arr[left] <= arr[keyi])
, X  D- s7 C* w& Y                {
( ?: W+ T! x; e8 l                        left++;
                }
9 m7 d: o' L7 z7 ?+ ^" F               
2 ^) ?2 M6 o8 k. y7 Y" X7 H+ R2 i9 j        //相遇就不交换了
                if (left < right)
4 M' p9 ?; r& ^5 l3 n1 K( p( h6 G                        Swap(&arr[left], &arr[right]);
: h8 C/ A* _7 r4 }7 G! q        }
) e! E! z/ {( k- M* j% z
        int meeti = left;

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

3 x! D9 Q/ G9 ~6 R7 b* Q% b        return meeti;
}
0 N; e3 I1 _/ K& _
1
2
/ e: a5 p2 I: _( v) a' [- X% p3
+ \# m/ R: R/ f9 l3 ~( U4
- L) w. Q  x0 p! s: J, v5
6
7
8
4 H8 {) `/ w1 ^) f7 r9 X9
10
11
12
) a7 ?- b0 @$ g, _13
/ K9 q  E# Y# {14
15
. I% Z: H8 ]  k' p! V6 v16
17
  j8 A! u+ `( i/ O18
. N, L' f/ D- q/ X. M, a5 D0 i19
20
4 c4 c0 [2 b# T; |0 Q% J5 c/ L/ l21
7 n9 o$ W, ]. M: |8 f% D2 m5 B7 [! Z22
23
0 _! V1 \& T; B; f' n6 R24
. O: [& h: i# D. C25
26
- i4 g& o' }; ?9 R  e4 N6 A27
28
29
6 P* }2 t: B7 k+ E3 w0 F6 t% \% U( Z30
8 l4 s! h" b! J# Z  M/ q* x# R( ?) t31
4 m) A; s: L, r% b8 }32

; y7 A3 u  F6 f( b% f8 p
0 r( Y$ l$ q0 h$ s" d解惑：为什么key要选左1/右1，选中间不行吗？

% n' a. M0 g) G+ k
: I1 }) x) u0 y可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深




非常容易栈溢出，怎么解决？针对有序情况，优化选key
  d4 _& R! r# p/ V0 Q( e  _
9 g9 t. F+ ~& Y, n1 S优化选key
随机选 key （是一种办法，但是不那么彻底）
选中间位置作 key
3 w1 v- X' Z# ~! l$ P  G2 |/ N解惑：那先前实现的单趟排序不就失效了吗！
：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑

解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
前辈给出三数取中的方法
* z8 C5 r! B+ }) y* P8 o3 i2 T
三数取中
在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
, o; d! K7 n" ?* w% f; W% j, @优化选key后的Hoare单趟排序：

int GetMidIndex(int* arr, int left, int right)
{
$ v( e' o6 u3 c) c; i        int mid = left + (right - left) / 2;
//  int mid = rand()%(right - left) + left;//增加了一定随机性
        if (arr[left] < arr[mid])
        {
                if (arr[right] < arr[left])
                        mid = left;
                else if (arr[right] > arr[mid])
/ K9 s  F& n2 d; R. C8 j- B* G                        mid = mid;
                else
4 U6 |" t9 C/ M3 g                        mid = right;
/ I" B' x3 ^+ g, p( r        }
        else//arr[left] > arr[mid]
3 Q$ H4 k* L  ?. t' a! C* r5 i        {
                if (arr[right] > arr[left])
                        mid = left;
                else if (arr[mid] > arr[right])
                        mid = mid;
0 |0 b  X! v+ v4 D                else
7 q8 M" G% L4 s* ^& C+ u                        mid = right;
        }
        return mid;
) \  F  b3 |; j}

; {/ b! g! {: ^+ rint PartSort_Hoare(int* arr, int left, int right)
{
        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
4 ]; L+ `5 a7 |- r( k+ I6 x        int mid = GetMidIndex(arr, left, right);

        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
        Swap(&arr[mid], &arr[left]);
+ L) H1 Z; E5 _  U9 T2 U& V1 V
$ T  J: F- g& [9 N" d  d        int keyi = left;
! F/ c0 Q, w" P7 W! a& V        while (left < right)
        {
                //R找小
0 I7 @- {8 h8 Y% Y+ b& v6 W                while (left < right && arr[right] >= arr[keyi])
                        right--;
$ h. I6 F  U2 q
                //L找大
- X6 s$ _" t$ g3 ^6 Y6 \                while (left < right&& arr[left] <= arr[keyi])
+ y; W) U7 ~" h1 v                        left++;

                if (left < right)
                        Swap(&arr[left], &arr[right]);
. @+ I9 g/ k2 R( u$ P3 K        }
, k: X, w* H  }9 M' c3 s
        int meeti = left;
8 ?% o! S, k9 A1 x
( V, C4 P! c: f0 T        Swap(&arr[keyi], &arr[meeti]);
0 R0 z, X" i/ j3 \
  O% Y  u# N- l. F" Q! w( e- @" h- c        return meeti;
/ |1 F+ ?$ Y! d7 c1 I( w& ^& r}
8 x/ y% ~5 U* U0 {- r
1
2
3
6 g" m; G& e5 {1 ]' a7 i; t& d& H4
5
6
7
8
9
10
11
12
7 \/ X/ o- _3 w' z13
0 }& ]4 Y! D" W: w6 C14
! U2 i5 E& @& C& P: U7 N( Z15
& ]8 j. j, @1 m; A* C& t2 N16
# [2 l' I% m# o17
18
( z2 q8 v9 w3 \  ^8 w4 t  R# ~19
" L: v) v9 a4 |" x9 R) F8 m20
21
22
23
24
% |6 D5 W+ W% w9 Q1 [0 i: G9 z/ X25
26
% R$ M" C2 r2 \4 k0 q3 g27
28
: Q( G+ q) k4 {8 U! U% \; n29
7 p' N' ^7 m( g" b. L4 c& u6 P30
31
32
% \0 n5 W. H! l6 I8 F0 `/ Z! i33
+ ]  l. U% s( P34
35
. j7 ]) V, p/ @& s# |% W36
37
) g- ?$ D1 g4 O. H38
39
40
2 I( D6 e4 ]1 P6 T# Q8 H41
42
7 P8 x  g- b! R3 k( I7 F2 V2 D3 u43
$ k1 T, j% I4 l( E  {9 U44
/ O1 `: r- l! F. q+ h' b45
7 @7 \( Q# i. s, \& i+ I( R* B" g+ ?46
47
48
, G0 n8 g2 {3 V49
50
' o9 S0 i4 z7 m51
/ ?# m2 q. k% O7 x, [52
6 Q: @6 q9 P7 B2 {7 _5 M, |' K5 O53
54
5 e$ f* B, l" A2 O5 w5 `- r, g挖坑法
初始状态：L作坑，其下标存为key
3 V8 `7 W# j" n7 ~, P(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
9 T  Y0 s0 }5 G, k8 `$ q6 l! l重复 (1) (2)
最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]


/ C5 E( P( a* p% {4 N; T) dint PartSort_Hole(int* arr, int left, int right)
{
        int mid = GetMidIndex(arr, left, right);
4 L5 j8 |$ ^  q& N        Swap(&arr[mid], &arr[left]);

: Q4 u) b$ {: y' ?& S% B        int key = arr[left];
        //L作坑
0 @( K' [; f4 |9 _( z+ g+ \9 c        int hole = left;
        while (left < right)
0 n3 ~9 w% t0 h7 \        {
" q2 a2 a& K6 e1 y                //R找小，扔进坑，R作坑
7 N3 h0 |+ L1 Y# z+ w4 ^, J                while (left < right && arr[right] >= key)
9 G8 c/ y7 I$ d+ o( ?                        right--;
' Q7 s! t6 y* W9 P. q* u                arr[hole] = arr[right];
                hole = right;

& j( r! H) R# d0 C/ Q  u                //L找大，扔进坑，L作坑
                while (left < right && arr[left] <= key)
3 T9 q- j* M+ ]" k8 G$ V7 O                        left++;
                arr[hole] = arr[left];
                hole = left;
        }
+ b7 J) H! O5 z% M9 s! s5 D' ?) M        //meet
, C3 o- i$ ^7 L; R; i" Z9 O* T2 s        int meeti = hole;
        arr[meeti] = key;

9 m8 E: g+ _: [& G        return meeti;
: n% g0 W+ g) R}

1
2
7 m0 }- B" ^% I3
  k# E: l+ Q0 r2 E4
5
6
7
$ w- p: I" K( J! E8
# x# ^5 F" k) k9 q0 ~9
10
4 K: i; a$ x; u, ]. R4 {11
2 K5 E& i7 R( p12
13
14
15
& ?# E" l. S- I8 _9 [# |16
+ e% q& q, t6 K0 G2 @$ i17
18
19
( u$ V9 F. }; E20
21
22
' d8 X! `* H, P3 f23
  j6 b" `* T! H# Y6 {9 K24
. }- t- _& L9 Z25
26
" F% S( e( N/ B* v8 W* y+ k27
28
1 Y$ O( ], q0 B+ M9 K; D前后指针法
( V$ V  V1 [& N% r& j此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多

5 `$ F& h. v& Z. E! t) Mcur找小，找到则停
- o4 \  p9 f3 I  k- \( j1 f++prev
% m% j: J, I* u& Q  F9 |  w如果 prev != cur，交换 arr[prev] 和 arr[cur]
( M& q* l: G6 p' y8 m5 A如果 prev == cur，不交换
当cur越界，代表找完，排好序了
; h; |1 q+ H0 U! R( O, p. ^prev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低

9 J- Z+ k; h$ Q* Q

int PartSort3(int* arr, int left, int right)
{
        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
$ Z& c: ?# D' V       
8 q$ s6 f- P5 G+ I$ M1 A  //int key = arr[left];
  Q" H+ T5 Y' O        int keyi = left;

        int prev = left;
        int cur = prev + 1;
. B% b- m) b) r- o! h9 a       
4 G0 b6 B" h0 Z# E' k    //cur越界：找完小的，prev的左边全小，prev右边全大
% j$ q1 Q+ p& Z3 l3 d! J4 L8 Y        while (cur <= right)
7 I) j" j: E9 x  d# W! X        {
, x- `4 R9 t% _% ?3 C& D' J        //++prev == cur 没必要交换
( r4 G* ?; o  ^: S. v                if (arr[cur] < arr[keyi] && ++prev != cur)               
                        Swap(&arr[prev], &arr[cur]);
+ q9 |6 a0 P) O+ r+ P1 Z
                cur++;
# x- k4 ^7 @/ m% f+ Z8 f6 ^1 Y        }

) l- y4 e% x1 s6 f. m# o' ^        //键值存是的值：
        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
        //Swap(&arr[prev], &arr[left]);//这才对
/ W8 M1 K8 C6 `    //键值存的是下标：
        Swap(&arr[prev], &arr[keyi]);
# E4 }4 U- r! u
        return prev;
# Q/ O7 P4 e" i+ S}

1
2
# f' q+ Y  m2 D/ q/ [. U9 m3
4
5
6
: Q3 j4 E, n% ?, ?: m7
& u' l& m' w* z8
/ f8 F8 E; }/ k. x, U9
4 @7 y/ T: }. K' m" p6 a10
11
12
% ]8 s5 m- M& [/ q4 K" m. ~1 Z" J13
14
15
+ `& D! Z$ \9 s& m2 \16
+ a3 C* u; o7 Z2 z( ^17
18
19
20
7 U6 S. S% q( E( z* G21
22
: o7 r( r7 \. ?2 d23
& B2 c8 A: L# C24
$ G5 Z" E1 K/ }  X! Q2 ]25
7 e9 |1 n- `7 p$ o- |26
27
; H+ r4 C3 B  l+ q& ~0 h28
# V: r0 g0 P) f+ e. |3 g/ q7 q: ~29
整体排序
1 |" r( U4 c5 L5 q7 c8 `  G递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

) ?: n& d8 A! X3 ?//[begin, end]
void QuickSort(int* arr, int begin, int end)
  c- H; l' Y$ D" \( |; E{
        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
2 z8 U$ ~- g! P7 }7 H, A! \        // [begin, meeti-1] - meeti - [meeti+1, end]
                //1.begin > end:超出范围
                //2.begin == end:一个数天然有序
3 d) K( Q; E) X# \7 l  p2 g4 p    if(begin >= end)
* {4 N6 H; m1 Z6 |8 w- Q* u        return;
% {) D# M0 a8 |  F9 P$ Y2 c7 K* Z
, u9 _% F! x. j- ]' ~7 A) U                //排好meeti
% h; \" D/ W' @, ?2 |0 C, q                int meeti = PartSort3(arr, begin, end);
: s: }( j: Q/ r( t
( C8 M) q3 k+ J" d* k* `- m# {/ z                //排好左右子区间
3 d* ]6 X( ^8 B, V" g2 d; {                QuickSort(arr, begin, meeti - 1);
1 ]# Z* m. E, h5 P+ o! n                QuickSort(arr, meeti + 1, end);
        }
5 f& _! Z- D3 a9 L) V! v, X}
9 c: R7 a/ s- s% l
1
6 V+ F3 Q* g7 t' }! n. V2
! E5 q: i! b1 N, q5 b' H$ t4 S: {3
4
5
6
7
8
7 {/ D; i/ A! I1 b# x; n9
10
11
12
" D/ |1 K# ^* y( q4 }13
14
4 P  ?: a0 A- o( I15
16
17
2 b0 ]4 H1 ?* q2 k18
" ]& @2 _8 D1 D0 N$ w0 l2 X3 ]  O…
' ?, z) D) {1 F' j, T# i
没想到吧，还还还还有可以优化的地方！

' X6 \. {# @* R& k4 j优化小区间
( e6 R( I4 ^  H, O

如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序
- J8 y% U$ Z0 u
. s! P, ?9 Q+ E6 B( x! u1 n那什么算是小区间？

其实小区间没有确切标准，8-15左右都可以的


这里就把小区间定义为 含有 8个数或以内 的区间

//[begin, end]
3 a! J1 J1 U, o  g2 c- e* q4 rvoid QuickSort(int* arr, int begin, int end)
{
( B2 H5 @# ^! f- @( e' ?. W, ?        if (begin >= end)
5 a, x  I  n: R9 ]: J                return;

* B9 Q* Q. v) l. Z+ W0 ]$ L        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
! D: i0 D! a6 P" t  s# g: g( E        {
3 y- d: A9 `. a                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
3 S9 o" F3 v( @. |1 K+ E1 m! J        }
        else
        {
' k8 A5 I1 V4 A                int meeti = PartSort3(arr, begin, end);

# v( l) l6 m! p* H                QuickSort(arr, begin, meeti - 1);
& F7 ?7 @. O0 W. x3 l                QuickSort(arr, meeti + 1, end);
        }
9 ]3 F4 u! F4 b4 y}

4 Y: P+ S; g, D, b5 D. O' z1 z1
; T7 |4 r! H+ m$ T. _2
3
4
5 q8 n2 x5 w$ \4 d- r0 m5
6
- g6 D0 q: L6 B% E4 |0 F/ H7
8
9
/ U/ ?! j4 V: |+ M10
, ~3 R7 W, d! }0 y3 i+ ~* ]3 Z0 ]+ [11
9 L5 E6 }: L; u! i1 I12
$ S! A% d4 f3 ]2 Z0 z  b+ `13
4 S) k3 N4 Z: t' V14
2 r. M% g  h% X1 r% c15
16
: K- m5 j# E; p+ \: U, w8 ^$ w17
18
+ f2 V1 |& g! N19
快速排序非递归
" k( Y6 y1 |; Z' ?' k5 U% x" H为了解决彻底递归深度深的痛点，我们来试着把它改成非递归
' H: k& J3 z, X: d$ S. N1 r- v
8 ~+ M. Y$ r  W0 P5 f, w, v思路：
  F6 W" A! F$ S1 R8 t, p递归深度深，栈的空间又小，会栈溢出…
* k1 G  u4 A6 C3 D, g
那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！
4 X$ l$ s0 p! A& |
3 t1 K- A4 c: A! N& O. g1 F- B核心思路：在堆上创建“栈帧”

6 C- `4 t' x( _, _0 u7 \快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的
" H& s% r! J, m( K. A  r' t

8 i) Q6 U) H! G+ @5 \
8 f1 O. T& Z) o. X% X; W在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：
, E! {1 r# M: o  d
$ G$ z9 O' K6 l. \: J8 [先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
8 O3 z. Y% ]& ^" X$ d& ]{
        ST st;
. y; R' h) s7 `" h9 C        StackInit(&st);
3 D$ I! D' o4 \  y( s* {       
# \+ Y* {6 l- _& A1 D1 P    //先入begin
        StackPush(&st, begin);
    //后入end
        StackPush(&st, end);

/ a1 n/ w9 @1 [, R4 }        while (!StackEmpty(&st))
        {
                //先取end
0 t$ S6 A( x5 [" `' M* x: U0 ^  _                int right = StackTop(&st);
/ y, I! b* @: a$ F2 D+ A( S                StackPop(&st);
4 [; ]( C  ~0 ~8 R' [# B                //后取begin
                int left = StackTop(&st);
                StackPop(&st);

                if (left >= right)//1.只有一个值  2.区间非法
                        continue;  
                               
                int keyi = PartSort_Pointer(arr, left, right);

0 X3 _. R3 ^5 E8 |9 s                //先入右区间
                StackPush(&st, keyi + 1);
; Z0 D# e0 Z$ E( i% Q& j  U) N                StackPush(&st, right);
* |1 l2 ~2 P3 X4 G- ]  Y                //后入左区间
5 z& G1 f4 |" S2 I  |& I                StackPush(&st, left);

% Q; x" ~' ^/ Z5 Z                StackPush(&st, keyi - 1);
& Y+ E9 J7 y- K* E9 G4 H9 m        }

1 s  |+ V) x( g  A# o, g3 K        StackDestroy(&st);
9 K/ w( ~# L' Z  I* d}
- P. A5 B  E  S7 S4 ]6 \
1
2
3
4
, T" a' [  _- g; {' K& V) p. e5
6
! R6 r8 w( s  C9 D) ^2 D( O7
8
( K/ ]8 p# Q4 q7 q7 O) r" N; R7 {9
% z: J3 I/ c) ?- K7 T( p10
11
! F3 d: M/ Y: Y1 w( ?12
4 B% m0 u/ x  j13
$ X7 z  @( Q8 E  L# v7 M! a' l2 t! e14
1 O1 z( z2 Z  ]9 o. h- S15
/ l+ S3 O5 Q( C0 S+ w2 r3 K/ V" n16
17
18
19
2 A1 {& u$ _% W) ^& p. [20
21
22
  ?7 z9 Q3 V- X. }6 |& x  P23
24
7 [' ^9 S8 W4 P/ V4 S7 i25
+ [+ G/ c( N% q0 \+ A9 l26
27
28
6 ^4 O6 Y$ U# I# x4 `7 O( g29
( }9 p8 K; _& E: u/ `- f3 p30
% o+ s$ u  O" B/ d5 L31
* M5 o% J$ Y9 K32
' @% Q2 k. B/ p' [# G; ~, D33
+ N. T3 w) J* y8 v/ Q* }4 y. G34
35
数据结构栈的实现可以看博主之前发的博客

3 ~$ c. R, B& r/ B0 k
3 J/ R. }/ H2 \8 i+ c1 N  |归并排序
  d6 V0 C& d2 x& \" M6 P) g
5 L- m9 i" a3 ^/ r' G* ~' I…

性能测试
3 Q5 `' w) z) b0 H# d/ Tvoid TestOP()
6 ?# k! ]. B: E9 u9 W3 O{
        srand(time(0));
        const int N = 100000;
        int* a1 = (int*)malloc(sizeof(int) * N);
        assert(a1);
        int* a2 = (int*)malloc(sizeof(int) * N);
& a, K' j& f+ A        assert(a2);
        int* a3 = (int*)malloc(sizeof(int) * N);
        assert(a3);
        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
$ J4 l+ `2 x; O        int* a5 = (int*)malloc(sizeof(int) * N);
        assert(a5);
5 ?8 u7 b6 U9 b" r1 c/ m6 t) E
/ b! Z3 b  l/ Q* p& X0 g        for (int i = 0; i < N; ++i)
        {
                a1 = rand();
& Y5 y/ E9 V: ^' R$ \/ Q                a2 = a1;
                a3 = a1;
                a4 = a1;
                a5 = a1;
, @/ m' Q8 ^; c  @, t+ _        }

        int begin1 = clock();
        InsertSort(a1, N);
        int end1 = clock();

& V+ r7 ^2 u) j; F. V( v& E+ I        int begin2 = clock();
) V( V( A/ N- ~; ]$ _  s9 @        ShellSort(a2, N);
( E: U8 \, [" j# d0 A. Y; V7 Q# ]4 f        int end2 = clock();

* E, w5 A) O0 H9 P( U        int begin3 = clock();
        SelectSort(a3, N);
( O6 p  M* x  @, K( I        int end3 = clock();

        int begin4 = clock();
) R! f3 {7 i/ o4 E        HeapSort(a4, N);
        int end4 = clock();
. v5 L5 m0 j$ D7 E$ s1 O
        int begin5 = clock();
- t( H9 s* c. F. d        QuickSort(a5, 0, N - 1);
                //1.中间key
# z3 m$ g9 W8 D0 f                //QuickSort(a2, 0, N - 1);
                //2.三数取中
                //QuickSort(a2, 0, N - 1);
  }6 J( l4 }) u/ U, P$ S; r                //3.小区间优化
                //QuickSort(a2, 0, N - 1);
9 G. C: [% t" M( f5 E1 |        int end5 = clock();
: m: L. \3 G' T3 u
) H# y, |1 W; O% p# q2 J
$ E- S! F5 ~3 K/ a+ X0 A! E& C        printf("InsertSort:%d\n", end1 - begin1);
' K: }  F( j6 H* d        printf("ShellSort:%d\n", end2 - begin2);
        printf("SelectSort:%d\n", end3 - begin3);
        printf("HeapSort:%d\n", end4 - begin4);
1 h8 j) \5 q$ t  C: l0 U        printf("QuickSort:%d\n", end5 - begin5);
/ _- u+ a. y8 W& ], t: ]
        free(a1);
) {) r; h5 B! s; t5 {  U        free(a2);
        free(a3);
  d' J! F, X( S) C- g        free(a4);
        free(a5);
}

9 d' X& e8 f0 I* q1
7 O4 S# b+ M2 Y0 p" M2 E, p" ]2
: X# I+ _9 q% O9 B) \3
5 j- r6 L0 {" Y  R  J4
5
1 \0 H% T, q) C* e+ V6
7
8
# }, I( h3 @) M0 c, \: s9
10
11
12
) M2 h3 G7 A6 @: Y13
14
15
16
17
0 r5 a) K, h+ R4 v18
# V# M" o) m1 b! \* w' w5 u19
! s8 o, @1 y1 T1 C) V! \20
8 A, Q0 r% p6 {, M) L1 D21
% F; \& y) v/ H$ y) q) [5 C22
0 h' l" m2 j2 F2 d0 y8 [! |! c0 \23
24
25
! r5 a/ h1 Q7 }1 A* h6 J26
27
) k4 P6 i# p/ e  p/ p28
29
30
* T# y3 W$ s0 r5 y& m$ x31
32
33
- x$ w8 c& D6 g; L+ B34
35
36
" `+ |" H$ w9 w8 B. w/ f37
38
$ O+ Q( T3 }/ v39
40
41
42
* O9 e2 x( |+ P1 z  h43
% o5 k2 U0 j- M5 Q! p3 ~44
45
" Y+ j9 W2 D9 A46
47
  Z9 @7 Y2 V4 x. o* h48
' e- S5 D: D8 j$ i& i( P4 R49
50
51
52
, D2 E6 U) N, z3 [, w: T# Z53
& G4 I' K% {0 W4 z4 j54
3 m4 v/ {1 ~$ o4 r1 R55
56
57
- Y  Z1 Q8 L3 N& b58
59
60
1 |+ |1 m* {1 M$ {- p61
# P2 ^9 ?5 |5 i+ p; t9 o# f" y62
63
( I  Y& G9 k( Q- b4 B$ O+ U

不愧我们费这么大劲优化快排，多帅哦！
- a. Y& B' [" ?( O3 B$ D
5 W2 u. Y4 l4 U1 ]9 o差一个归并排序，后续补上！
/ s, A3 _! m/ H+ N. _  Q
6 t; ~4 b6 N6 L3 t  O9 H2 T不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
————————————————
; u8 I% @! m% ~# \版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
8 Q, D! w+ o) T6 }# e( c+ p( ~原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832
- X  ]1 s7 `$ Q/ e" U9 w
" o  g" ~0 `* H, Y
  K' ]. H2 ~) V  b