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

杨利霞

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

前言
& B- `6 u& G# T& U" r$ s本期分享经典排序：

) p1 K8 L4 V  R8 b4 p( ?( W/ O4 ^插入排序
直接插入排序
希尔排序
; Y' J$ {, G! _) P' a7 Y选择排序
; s( M4 g  E6 }7 L6 Y直接选择排序
! _: z; c/ [* _( I' `" R* G) Q2 U堆排序
7 o7 ^9 ^  T0 }' Y) j' R交换排序
冒泡排序
快速排序
注：讲解时默认排升序

% `1 i# V+ c. Q: d8 \9 C插入排序
直接插入排序
# d( @& z/ P* l1 c4 O* ]5 E2 N思想
插入排序，就像玩扑克时，摸牌的过程：
& E/ t8 B( R! I
; A4 t! H, D. D! E% b% _6 m最开始，左手没牌，右手从牌堆中摸
右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
如此一来就能保证左手的排始终有序，摸完牌后也就排序完成
) w- i4 A" y, N

操作
设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
单趟排序：
每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
8 Q5 P! @  X( M" z- T% V$ m7 s7 ], ~1 j是正确位置：插入
不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
整体趟数：
# I) Z2 ?5 z; \- D! Q, q0 a& n8 c' \若元素个数为n，需要排n趟
void InsertSort(int* arr, int sz)
{
        //end + 1 < sz
        //end < sz - 1
0 s; C9 I. @; x) J; n' }( T' d3 T        int i = 0;
" B- L# }3 m  ~) h$ m. q: }        for (i = 0; i < sz - 1; i++)
3 n) V5 Q. k7 s5 ?        {
/ {6 S+ s+ x& K0 @2 C# k* U% u  J; X                int end = i;
  c$ ^$ ~2 q0 a! X9 }; V* T7 D                int tmp = arr[end + 1];

                //找插入位置
                while (end >= 0)
7 \6 E& q) ]* _9 U                {
                        //不是插入位置：当前数据往后挪
2 Z& g% Z. \% A                        if (tmp < arr[end])
                        {
) O3 E- `% I2 X+ }8 }  M* g                                arr[end + 1] = arr[end];
                                end--;
# N# s! x; X, R3 s                        }
+ T9 M, n" v  L( _, Y# X: ~                        //是插入位置：跳出循环插入
5 E- k3 |# H% A* E' n0 O* T                        else
$ _7 W/ _% P* P: M/ H                        {
                                break;
3 G" U1 f# t2 L; Q4 m                        }
7 J8 ~5 b; m- D  w! e( N2 K0 p                }
                //插入
                //1. 插入位置是[0]，end == -1，不合循环条件跳出
                //2. 找到插入位置，break跳出
                arr[end + 1] = tmp;
) o" ^/ n% k6 o( ^$ U- b; {. B        }
}

1
& L* y& ]# b! Q4 j* L! p2
3
3 U7 Y9 z2 g% E% ?) j7 w- C; x. Z4
4 }- V+ x$ Z+ L6 H0 |) D% C5
6
; O( k: z* r) Q7
8
9
/ g6 K, S  u" t/ T+ b3 c- v# ^10
; @/ j+ y/ V! O- H- p11
12
13
14
15
16
0 P9 E- k# s% l# U' u2 @1 g5 ~17
+ {5 r$ |4 _% ^18
19
+ A$ ]9 `) o, V$ V/ ~20
21
22
23
24
9 Y5 D( L3 K8 [0 j! c! m25
26
6 q. W; f7 s% K* D: ^) \# V27
28
# n" c) Q" u8 x6 E& s29
/ w: j$ V2 b) j# f5 Q+ ]- F: x0 N4 N30
31
' B* S" o) l4 k/ J$ _' T
7 \7 F' b2 j4 K
. u+ {' z) h0 |+ J1 k! |稳定性
插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以
5 V" T: @1 V( k  l) \# Z: F& k
直接插入排序是稳定的

复杂度
: ^$ g, B2 g2 [3 s$ z时间复杂度
最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）

O(n)
$ z8 v1 ~0 e; @1 N  \% g
5 y, {5 a0 |8 ^! P2 z. S) J- Q0 D最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2

O(n^2)

2 \) r4 F& l/ J3 o7 ^: Q8 x% x空间复杂度
O(1)

希尔排序（缩小增量排序）
& ?! g6 d& @( y6 j0 j希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序

# ?: n: C/ M* E( Q$ z优化思想
; l. f3 r4 e& q. T+ O6 Q0 C增量gap不止用来分组，也意味着数据移动的步长，所以
1 J7 N3 ^! k! |
gap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高
, d$ L" m% e1 [% g
. T1 F! T$ a) ]3 W: W
, M: n2 p9 [6 A# w, j操作
8 v5 H. }- W7 Q. e单趟排序：

/ ~5 Z7 O( \" Y/ W3 @7 g5 C! Y) x+ |设定一个不断减小的增量gap，也是元素移动的步长
以gap对序列分组，并对每组分好的序列进行直接插入排序
6 P! [4 p; f4 P9 @( p4 E& \7 ~1 q7 i1 P不断缩小gap，并排序
/ w7 T, x3 {0 t, |2 `1 X% w*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
+ o: T' \. Q& \. L: P% n整体趟数：

7 {/ I2 i3 i5 _由gap决定：当gap = 1，排序完成
( y  X" e5 }1 ?* x, s' K+ j注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。

* G5 }! X% W4 u* K$ ]; K( uvoid ShellSort(int* arr, int sz)
/ M0 I- i7 }( Z7 Z9 I: v2 v{
        int gap = sz;
' l0 _  b5 U0 N! \: Z* l       
. \1 P9 X9 l* S    //gap > 1，预处理排序
    //gap == 1，直接插入排序
        while (gap > 1)
        {
                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
                //gap组
/ L; r) X3 z1 q4 e# M- N$ {; w% A                for (int j = 0; j < gap; j++)
: b/ p2 e8 Y9 ^& p+ }7 u                {
& c$ V) S- P& i, Z, r5 z9 w; f            //end + gap < sz
                        //end < sz - gap
4 U0 `  Q  b) Z9 j2 L                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
                        {
) U6 y$ M$ t9 ^6 d/ C9 ~- B1 k                                int end = i;
! U' t! p. ^/ ]' o2 {( l$ W& f3 T8 h                                int tmp = arr[end + gap];
                                while (end >= 0)
                                {
                                        if (tmp < arr[end])
                                        {
                                                arr[end + gap] = arr[end];
  ^; B4 K( B5 S! k                                                end -= gap;
                                        }
                                        else
! T" H( t& c  V& V- E' a! z; a                                        {
% V. \8 l- t7 h                                                break;
                                        }
                                }
                                arr[end + gap] = tmp;
" K' y) n) t2 g) ?6 {2 L                        }
" b# i$ j2 l/ f                }
        }
( W% c' {+ P  D0 c1 H! Y, C}

' o5 D3 E1 f# J; k3 f: @$ M1
2
3
4 f; z' F& Y! s) N8 L4
: k5 f; o$ \2 B. C0 z" ?, R4 n2 }$ \5
; v( z9 R  w& `2 i9 A8 o6
7
! L8 ^( t+ o5 j# H0 N; t! n8
+ J. O" y0 f. A. v2 e; Y0 E9
" j+ J- u; R; N9 S10
: C/ g" x: ?0 S6 y5 I% ]% P11
% ]# k9 _& Q. \# J12
1 k, F( }3 J4 r0 N& r13
! r: S/ D2 \" Y, O' V! `3 x4 h14
+ R* D; V) W- \+ N/ M15
16
+ \" D; }1 {# x- ]17
18
19
20
21
22
' x1 P9 y/ X0 V, H7 Z23
& H, y& K9 ~* s5 H+ u5 V) p8 r24
( ?% d7 x7 a  J+ B: g/ p, ^! [2 N25
26
" a2 g: @6 y( N27
28
! Y, o! R- {; g29
30
31
, l/ S  A. r/ h& v4 d6 M! z+ h32
33
+ |) H; x0 B1 e+ ~; @' \. J34
35
! c5 q, a  Y: ]8 K1 r其实就是套上”缩小增量“的直接插入排序


稳定性
8 V1 K: c: [; s3 A/ l) E我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以

$ N8 N" C% V9 U+ k希尔排序是不稳定的

, b( d, Z3 n$ d" W复杂度
: K8 d5 v, }% q- b) L时间复杂度
希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
6 Z* X( L8 R+ l; I- ^! w: M& z5 r! [
O(n^1.3)
% S2 E- E. T- `8 M$ J! b% c+ Z
空间复杂度
O(1)

选择排序
直接选择排序
/ H1 T( o; y5 V& _思想
/ u( ^& h' }; I8 s! `5 {选择排序，遍历序列，选出最小的元素，交换到左边

. m8 k: U* O$ o7 M0 I% l

: l7 n8 ?* a: [  ~8 l优化版本：

每次选出最小元素交换到左边，选出最大元素交换到右边
+ F, v5 A. b  w3 R! H
# j4 V% P6 Y4 c- C" J! T操作
7 ^! H8 T5 k* `; I, p/ ]. V( u设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]

设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标
8 E! x0 a! c/ }3 l
7 \! h/ S+ o, F3 h单趟排序：

3 d1 [( a, N( G! p" f遍历选最值的下标
& G& A1 A' u; d) `0 a交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
（修正）
整体趟数

- W) @1 d& J3 G( ]7 I若元素个数为n，趟数为 (2/n)
( Y! u1 f$ m" W2 I修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标
" b* o" c" ]7 J6 z! j& X' H
void SelectSort(int* arr, int sz)
{
& R% V/ \$ v; E$ {        //闭区间: [begin, end]
        int begin = 0;
        int end = sz - 1;
% r# @! f" M5 o7 B3 p4 B        while (begin < end)//begin == end 最后一个数，天然有序
        {
* h5 W! _, [) ]# h' ~$ e. k: o! g                int mini = begin, maxi = begin;
  k3 T' |2 g) V: ?  K+ \                int i = 0;
                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
& r$ X3 s9 k+ l5 p" _/ y                {
                        if (arr > arr[maxi])
                                maxi = i;
                        if (arr < arr[mini])
  ]: j7 g% B6 u# N                                mini = i;
0 j  E) I/ o( F, M! J                }
4 y+ i$ ]  I( A- K- j
                Swap(&arr[mini], &arr[begin]);
; L2 X+ p5 W' I
                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
2 g" O  m2 E5 |* Y4 W                if (maxi == begin)
                        maxi = mini;
+ b$ t; Y0 P% j$ z                Swap(&arr[maxi], &arr[end]);

                begin++;
                end--;
4 `2 C$ l" H, {! u' q        }
: P5 F9 ~4 t2 ?- X- a}

3 C! q6 O2 z3 D+ W! d6 }1
% h; i, x/ M4 D- q9 Y: C) ^2
3
+ g+ B  F7 d) u# P$ S4
6 \2 w5 q) `+ t! n  u) O/ |$ ?5
5 c' c" F" R7 J: Q. H7 f6
7
: L, ~" z5 U/ j1 w$ \8
% y( `" e/ g1 N3 O* n, y& ~8 q8 |9
) |7 m: a6 j: {7 R10
1 Y( k7 ^6 X7 X* f% W) J: h! B# {11
& |. A  E* @" j" m12
8 M' e$ u2 Z, K; L* X9 x6 f" P1 A2 @13
14
- p7 ^* k% Q; Y5 c1 b15
16
0 s0 H! h4 ~! i! \9 ^, U17
18
19
20
3 |, z& D) ~# j: B  M# }21
# g9 q3 u, l% U22
23
. F% `+ j: D  V4 J8 v( Q24
25
26
27
7 M4 y9 P$ \. D1 N( k28
6 \% U5 O0 I; F' }

/ f; r3 X7 C% H$ R3 @0 D稳定性
0 G& K/ s7 W; h5 b. C$ @( Q选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以

& _! ]4 @3 a% S4 F4 T选择排序是不稳定的

. J4 Y$ z* E* g5 S& X6 E复杂度
时间复杂度
5 N5 y) g! Y6 s! l& c% N* J最好：

  S2 T: @7 ?3 A8 q8 G" F比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2
7 ]: s( E+ {; K/ S
5 Z# R; H  i) Y! x) T交换次数：O(1)，有序不用交换
4 T9 y' D5 ?( O3 S
O(n^2)
, u, O- l+ u) o2 o* }+ x! U% |
最坏：

比较次数：O(n^2)
& X7 y1 o) X- }3 H7 _
交换次数：O(n)
) P2 q! O  l* b0 b0 X
O(n^2)

空间复杂度
( I+ u* R+ f# [8 T9 c" H  qO(1)
9 E! R; Z( c: p8 ?1 g6 D7 j
堆排序
+ ?- k/ i6 y2 _1 G  H思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆
4 m) ]' A: n( O7 a" H% |. x: y( {$ }
5 ~" c6 }" ^0 S1 Z/ r+ d
- t3 s9 @' @" Z; {
操作
% @4 t7 j9 B+ F2 ]2 _  ?1 k3 K建大堆
单趟排序：
& A& W; x, }  C, K3 R! q. @选堆顶和堆尾的元素交换，则堆尾的元素排好
每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
' l/ @3 ^) X) q& Q( Q整体趟数：
若元素个数为n，则排n趟
( D4 r1 ?) I7 J3 |void Swap(int* e1, int* e2)
{
        assert(e1 && e2);

6 i4 U0 S& f- P0 c; ~, q; v8 h& ~        int tmp = *e1;
        *e1 = *e2;
( c* S. ^# G; h        *e2 = tmp;
1 Q) A: _5 ]4 E+ @3 |% B/ E$ K. a}

7 L4 r6 j( b! hvoid AdjustDown(int* arr, int sz, int parent)
{
* V' v9 d* I" n, |5 `7 ]        //建大堆，排升序
        assert(arr);
$ i( Y( E( a" j& o9 R2 S       
/ s# s) F6 g& F1 ]+ h; O; I    //默认大孩子是左孩子
* `8 A0 Z. y% F5 Y$ |        int theChild = parent * 2 + 1;
        while (theChild < sz)
        {
8 f6 P) O3 ^  m0 \7 ^1 o/ N        //如果大孩子是右孩子则修正
1 p* o7 L+ u& t+ H                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
                {
, ^+ o0 m* {" ~3 W- P* V1 j( l9 [                        theChild++;
0 M4 D* H" ^7 M' V! l1 t                }
' E$ O* Y& F1 Y6 W5 v* g8 N                if (arr[theChild] > arr[parent])
* a# A6 |- i# G                {
                        Swap(&arr[parent], &arr[theChild]);
0 J3 q; {% P6 E9 s- v. \8 x5 X            //迭代往下走
                        parent = theChild;
                        theChild = parent * 2 + 1;
                }
/ ]: C9 Y* S2 J7 i                else
' E4 s0 ~+ O+ p8 G5 O) Z                {
7 ?9 q/ ~3 t. _2 {                        break;
" E1 n. q) Q7 u1 ]$ h                }
  \- ]  n  P7 j* g1 r        }
}
4 _6 Q* q4 C& V" q  {; \& K
" H* P; ]6 c* S( \4 Zvoid HeapSort(int* arr, int sz)
{
0 ]% B4 @! e7 t/ r0 m        //1.建大堆
        int i = 0;
! ~# d  {& |9 P        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
        {
                AdjustDown(arr, sz, i);
        }

        //2. 选数
1 F, N' T) d: T        i = 1;
        while (i < sz)
( z! H) Q: q& i8 J: a% f        {
                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
                i++;
        }
}
7 U3 J, e2 M, N1 H
9 x- ^7 u* i( U1
7 E) e4 m. ?5 V( y) P% }8 |2
3
4
; h- ]4 V; \# p) r5
. l9 m9 M% b! C( K6
7
8 i, X% x9 F9 D' L/ `6 ]8
- V* Z+ z5 C+ C& T+ f8 ^9
( V9 F9 h( ~+ m# @  G$ X% \10
* }- h  E: y! r( x# `11
12
13
9 a" `7 W# k5 _7 v' S9 q14
6 J5 }1 Q" @; x  R15
16
17
- L. q$ U' L) u9 D1 N18
! N# f8 H. e' B- ~1 ~19
20
* b; o# y+ a  F9 p, v5 c  @21
22
" ?! o/ X9 v' C% |$ N1 U23
# t+ c" b) `4 s3 I8 i1 w24
25
4 V5 [0 ]1 K5 w1 B, T+ n: q26
, b! Q8 L) x# ~7 @) s! i27
( p3 [: R: E2 u$ l" G28
29
30
# ?2 |' D9 m4 }: Q- v31
. H! z# O  R- J! d( ^8 X( S3 d9 N32
+ Y' {+ e2 `7 L7 O( H9 V33
34
4 \' P" O1 f) m) r, m1 Z/ i8 L) O: |35
36
0 ^# K1 O) |/ N% e( ?) H3 T37
* h5 x& d3 S8 L38
, q- g( _; e5 y- I% \39
40
/ o& j0 e9 R; Y, P* e. J' [41
42
43
' \# x& }: v; H& y  i2 q44
7 u- b" T( k- H, S2 Y* r45
" Q1 T# q# _2 k46
0 L7 \4 |# ?1 I$ W+ J1 c* k3 h47
9 G) ?7 E2 S/ d48
9 U3 D, ]% }3 y  G49
: `' U, L! i5 r4 ~50
% W  f7 e7 c5 V% y. @) T3 c51
52
53
7 [  b0 \; \( G1 F4 o, e6 N: S54
9 Q7 E0 Y( o- ]. A55
& n, \2 c& v- Z# `' y% q5 u3 }

. g; a7 A$ Y- g6 P/ }) r& U, v稳定性
建堆和向下调整都会打乱元素顺序，所以

堆排序是不稳定的

7 r2 O- P0 J; L& n1 s. G/ r* a复杂度
时间复杂度
: w- [5 v  h2 i+ k$ Y: I单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为
* \" B/ X7 j/ \" V3 _* O$ u) I0 e9 A
O(n*logn)
9 d0 V- `2 X+ q7 l  |# s/ f- ~
9 o  J  w% ^6 \# N空间复杂度
2 h, c$ ~* Z7 Y" V' e) b原地建堆

O(1)

& Q6 ~. L) K  u8 u7 Y# k4 Y4 c交换排序
; a- P+ w3 @: J' }冒泡排序
思想
冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素


* d$ ?/ u3 W* k1 |3 O- m: M
操作
单趟排序：
每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
  M/ ~& X4 l- y9 I7 w) k每趟排好一个元素，所以需要排序的元素每次减少一个
整体趟数
* S; k. u: t% w若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
. _8 d& f! R# i$ O: B( Qvoid BubbleSort(int* arr, int sz)
{
& o% M9 B9 D  x! Y) V        int i = 0;
        int j = 0;
" C! L5 v: |" C+ {# D. T( w        for (j = 0; j < sz - 1; j++)
        {
- O* f% f4 ]) Z" K* z                for (i = 0; i < sz - j - 1; i++)
8 ], }+ ]' q: s3 K6 G( x$ {                {
                        if (arr > arr[i + 1])
                        {
, w3 Z/ K6 d' Z0 k3 s) S) V' I                                Swap(&arr, &arr[i + 1]);
- }6 t0 K+ W% r! j8 k: {  H                                flag = 0;
                        }
                }
        }
}

1
5 ]; e6 G  g- i$ o: J3 ]# f2
3
4
& R& {" C; m6 y, E8 L4 q5
6
6 @+ b7 X* A' B. o3 [4 s1 l7
8
- C, a5 [6 ]( J" Z. N% g9
10
11
* q* J5 F0 K+ D8 h' A+ ?3 g. r12
13
14
' w% i; A3 `$ E# e( e' s) i15
  E3 ~: x) P, T% T( N( _5 J16
% ~- b' J0 D5 j2 |" A  A: t1 D优化
" J* E- ?; W& [! _- i当遍历一遍发现序列有序，直接跳出

  d% |# v6 F- s  Uvoid BubbleSort(int* arr, int sz)
2 g, ]6 m0 }) T' L/ E, p{
        int i = 0;
        int j = 0;
        for (j = 0; j < sz - 1; j++)
        {
0 B, T% N5 s9 G& {$ d! g                int flag = 1;
4 f. r. y. B1 t                for (i = 0; i < sz - j - 1; i++)
0 D0 B7 G! P  s5 }; @' ?                {
                        if (arr > arr[i + 1])
                        {
! J: l: _+ D6 d( m. A1 F5 W                                Swap(&arr, &arr[i + 1]);
                                flag = 0;//不是有序就置0
5 N( i4 K; f) s0 k+ p! G! F                        }
9 Q9 M" w/ R; K/ K                }
                if (flag)//如果一趟下来还是1代表有序
                        break;
, @. K9 a, ~- x! ^4 s        }
}
# y; u% V9 f5 @+ g
1
  y0 z! E8 Z$ N2 L/ X  |$ o4 ~" b2
3 m3 e. |! Z7 O* k7 E. U3
4
. b* v0 R+ i" _, O$ i5
$ L* ]: w+ v& z3 q0 f6
7
  T' b2 S" U( @' V$ F& V8
' J; }  D9 @4 O7 T9
) Q' D. _$ g+ W, ]10
11
) o9 S/ H* D& P, g6 c" M7 }12
$ K0 x0 ~4 K& a; j13
14
- U0 t! V8 D2 r+ }% e9 f15
) y. o, o+ \/ c! F0 g16
17
: r4 l- r7 n% `18
19

, y! x* ^/ ?. v# {/ @: q9 _
" F. ?1 C/ {' U) z稳定性
相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以
4 n9 M- H; }2 u( c1 W
冒泡排序是稳定的

复杂度
时间复杂度
2 H- r  p5 R6 O2 D; i最好： 当序列有序
! V* ^; j' j7 D2 P. V
未优化：
; t5 C* L6 v( T1 o+ v: q* b" x
O(n)

8 i9 b! C( t( s. }, p# S优化：

O(1)

最坏：要进行 n-1 趟排序，每趟交换 n-i 次
' Z- y2 ?8 K% P* y) ^* m# x
; a) m& h( C& a1 J, }+ s, d! L# A$ o- k) |, wO(n^2)
( S2 p7 s$ V) @! h
空间复杂度
O(1)
$ N% ~8 O0 {9 ?# H
快速排序
6 N/ t, v) s7 w* x$ E: T1 f% V. ]思想
0 q+ Z, t/ H' {1 d) d" G分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。
. i1 g$ v" H/ |" R2 z3 O
所以快速排序可以用递归来实现

: J/ t) T* M" U( i操作
有三种单趟排序的方法：

, V7 \5 i- g8 K2 e0 GHoare法
# t- d8 `2 I3 A3 m* z: U设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间

- ]' z$ S3 c* m3 J左下标 L = begin，右下标 R = end

设 L R 相遇位置为 meeti
; K% k* k; |4 m3 j
​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”

1 d  H7 S- ]6 l9 E, S& H- o/ t​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“

选 键值的下标 keyi

左1位置作 keyi，则 R 先走
右1位置作 keyi，则 L 先走
R找小，

* W( a' c' L7 Z' ]" g2 ^, r6 I找到则停
7 V& j4 o" X6 y7 P$ U# Z5 R- s遇到L，则交换 arr[keyi] 和 arr[meeti]
L找大
" I% p# ]% u, }1 h( s
找到则交换 arr[L] 和 arr[R]
遇到R，则交换 arr[keyi] 和 arr[meeti]
9 p( n' x" T; w1 i% r' w$ c. N" `7 f$ G
3 R+ Q5 N: ^6 W! ?; `; g
3 a; m* Q1 Z" y9 Z5 ]1 `  Y$ J解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
答案是肯定的：
: h. M- j  R& l& `% i. V# O
+ {* N2 x7 Q9 B. b2 b6 o, J2 |! h# ~
8 h) p4 B4 e4 @& U: |
+ q  W4 `0 d% f7 p
//[left, right]
int PartSort(int* arr, int left, int right)
{
" B1 r8 x$ D' ^' P5 d0 X& g        int keyi = left;
        //相遇则排好一趟
        while (left < right)
        {
                //R找小
        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
6 ^; G. J# M" h0 M/ g# ~                while (left < right && arr[right] >= arr[keyi])
                {
5 t& b  @; {/ I# ~                        right--;
                }
& P0 `) t) z3 Q2 q4 ]1 L' i& `
                //L找大
                while (left < right && arr[left] <= arr[keyi])
' {. k, z  T& ?% y                {
                        left++;
+ N8 d, |* y$ {# S, A" D                }
               
        //相遇就不交换了
, a/ B$ W2 U' H* L                if (left < right)
3 m$ R  h4 q' O" i' J                        Swap(&arr[left], &arr[right]);
        }
- u6 ~) p8 F, _1 C$ C; u1 `1 e" C
        int meeti = left;
6 Q1 j  ~: \8 [! P. C! e
        Swap(&arr[keyi], &arr[meeti]);
% V+ {4 x# S$ ]" n1 M
        return meeti;
% W8 @! f; X2 h5 ^" D}

1
2
3
+ F9 g* V9 X! l' \& i, E/ k4
5
6
7
8
9
10
11
' f. l' g! w5 k12
13
14
# G' g; v2 Z6 t; F' Z, Z15
16
' m/ I" L/ B) A. A6 h" h; M17
18
: ^9 S1 B7 _' p8 I! a. P19
20
9 r6 b5 a! v, J% j& i% v21
22
23
2 n$ Y/ P& }: g, r6 Z24
$ X/ H, Y: \( K9 b1 j25
; \- d# `* J( S" T26
' ?% j  Y# f: E! ^27
' ~: s' ]9 ^& v1 s4 C28
29
( b  A0 v" K# u- I4 s) ~3 h30
! `) }$ f4 t. T* {. E, U31
0 w6 |1 P& K0 U: D) a/ t+ B, T0 K3 l32

2 l2 |2 F9 V- h! I$ U  c
$ p. h4 H5 r) P& `: ]7 q解惑：为什么key要选左1/右1，选中间不行吗？

  ?3 O9 f1 V* e1 B: D" @# A
" J/ C  t" U/ i' l! H; r* h8 T0 R可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深
5 P9 h) d. S, O1 P
9 y8 |) N; }2 ~8 j7 J
' s0 O0 b, S# g3 h0 K& e
; r* T- Z, _6 j2 M: q  l
5 v, I6 _9 t& w7 `8 J非常容易栈溢出，怎么解决？针对有序情况，优化选key
6 R* O4 E% R8 f  @0 O
7 T6 r# O" \) l$ O优化选key
( p# v- S1 B$ b( z6 y8 d3 d随机选 key （是一种办法，但是不那么彻底）
0 u$ ?1 T3 X/ r( J" C选中间位置作 key
0 n9 ?5 n! K2 ?0 [5 [解惑：那先前实现的单趟排序不就失效了吗！
8 q1 k. N* D4 w9 _5 z：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑
9 v: V! C- L) L) n
: ]3 U% D6 y8 O" W- k3 g- m- c. L解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
前辈给出三数取中的方法
' Y1 v5 c" x& s- Z; A
7 Q+ [/ M2 L" m* G/ t5 z三数取中
在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
2 J" o7 g4 x* G; X这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
优化选key后的Hoare单趟排序：
8 q' `9 K$ N! T4 S' V8 L' i9 h
int GetMidIndex(int* arr, int left, int right)
! L; |( n% r- |{
        int mid = left + (right - left) / 2;
//  int mid = rand()%(right - left) + left;//增加了一定随机性
2 ]8 f9 l3 f" ?5 A" G: e3 o- R        if (arr[left] < arr[mid])
        {
                if (arr[right] < arr[left])
                        mid = left;
                else if (arr[right] > arr[mid])
8 N, x4 n4 _" v# K+ [4 O                        mid = mid;
                else
4 T( K( d% _( r" u% V                        mid = right;
        }
$ C9 Q$ f$ u2 F. H/ W5 K        else//arr[left] > arr[mid]
2 j: N. |+ s% c        {
                if (arr[right] > arr[left])
" t$ |8 y0 @8 d" j( j' `                        mid = left;
2 }  r# @$ e6 X+ B                else if (arr[mid] > arr[right])
9 S  _  a2 R8 Q4 k& J9 z                        mid = mid;
0 P1 E0 C9 l2 \, E                else
- ~4 h! C2 q/ x& P  \8 S                        mid = right;
        }
# b( Q2 e0 m, ^        return mid;
}
% i' y/ d$ g9 `. ^+ u( V
int PartSort_Hoare(int* arr, int left, int right)
{
        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
        int mid = GetMidIndex(arr, left, right);
* e1 O2 N# j$ h
        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
        Swap(&arr[mid], &arr[left]);

# }; x2 C' _0 y+ J) }% F/ E, q        int keyi = left;
! K* W" s* s8 o) t, q. N; T        while (left < right)
        {
! J+ N: V. F4 ^1 J8 J/ L                //R找小
0 |# y' n: a4 O                while (left < right && arr[right] >= arr[keyi])
" H8 e% |! ~/ L( }7 A, f8 J2 p) q                        right--;

: `9 u0 W* o- h$ L. _. K1 d                //L找大
, }1 E+ a  V5 n" V- y- `3 K9 `                while (left < right&& arr[left] <= arr[keyi])
+ W: ^4 M& `$ g- L% j                        left++;
2 B$ f3 r. E" _6 `0 g# ]
4 w- X7 E. a; [0 z. R3 P                if (left < right)
                        Swap(&arr[left], &arr[right]);
0 s6 J$ g1 F& [$ k& A( ?' B        }

        int meeti = left;
% T0 a+ S; b0 f. \
        Swap(&arr[keyi], &arr[meeti]);

3 D9 A. ~* ?% r5 j% S- k" F  A        return meeti;
}

) L. b5 Q" |  E3 t1
2
3
4
" d  ?2 F6 W! q/ G; o5
6
7
0 \7 z% `6 S4 r' Q( Y8
6 R" f6 b/ N! Z  q5 W9
& e* z/ a1 P) m4 t+ `3 O10
; ?2 a! Z0 R! o3 O' G1 x/ p11
12
  ^% e( I# l9 t13
14
15
16
) p, n' n8 B) T* v- N17
0 H  k& h' r8 n0 [1 f8 f18
, ~; e3 J$ b/ x; k19
20
21
  {& I0 B( y* B6 H8 v- t7 b/ |/ {22
23
5 q; r! M( z0 Y. z2 {24
/ J1 n2 K/ o1 x. Q25
+ t1 U) ~, b' M) i2 L26
27
28
2 F1 B- k) B' h! t. t29
% h) W9 D( D) Y7 V* [! N30
% k$ k8 g/ m2 r6 S31
2 F! {" k2 q5 N, p$ T2 a' l! Q32
: G+ G: x) M+ S33
! Y8 Q/ J5 Q* b8 u2 v  G) p- G34
( z: y0 q6 F! H9 {% V35
, S, V) H9 ~4 Z1 h3 W36
37
, ^9 C0 p# Y+ h" B" p" D/ _38
39
+ V! F- g7 [1 C' _9 I: ~" L40
41
- G3 l8 v# P% O7 v, a42
& e* M/ U9 I% [- U  E9 m43
44
45
; K% p, B2 r( `5 O' O, n' k46
" Q# ~7 P' J; G) O* n3 T, [& `  h47
% i* S" k- \" j( _: b" y9 Q# F48
1 r& K9 \6 D/ O" F6 D: A; l" |49
, W8 v; z7 m6 C) Z5 X$ g6 S1 f50
51
52
0 K- O$ `* D! s) e/ [- E5 m& y53
! ?4 T- `( D) m1 ]6 }" c# O! L) @54
5 R( Q& y6 c* `; x/ O; I# p1 I% c5 b挖坑法
初始状态：L作坑，其下标存为key
+ w8 T, y, Z. n7 h2 A9 L1 Y(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
重复 (1) (2)
* a( P8 ]7 R3 l+ @: N最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]

1 L0 v+ A: W0 \* J. W
6 a+ O/ @" S) w. iint PartSort_Hole(int* arr, int left, int right)
{
" d/ g' g5 B4 ~! a, k9 k# O        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
+ t7 @8 m* o8 w: N  F
        int key = arr[left];
        //L作坑
        int hole = left;
& v2 D1 E5 G- Z4 ~7 M: W. Z2 A        while (left < right)
        {
# F$ U! r. j- i' E) t* c                //R找小，扔进坑，R作坑
( ]9 O& {) G7 T% A                while (left < right && arr[right] >= key)
% M$ I- a2 d6 k/ M/ j" S$ D! {                        right--;
& ?0 G& \( h2 `2 [; ^0 l                arr[hole] = arr[right];
, j. W+ N* y2 l5 a) P                hole = right;
' v; w( p7 t# O6 W# N6 e4 P
                //L找大，扔进坑，L作坑
* T5 P6 G# F8 d                while (left < right && arr[left] <= key)
  g! X: e" q2 m9 L1 s  f                        left++;
                arr[hole] = arr[left];
                hole = left;
        }
        //meet
0 g7 ^' r+ F- t! S0 j; c" b        int meeti = hole;
; w: b) q( H+ M) U/ z0 [( O        arr[meeti] = key;
' m2 `1 b; I- r. \  |- w
        return meeti;
; Q2 |6 A3 C! g9 r  {  Q: P}
- c2 u. e! j8 X
1
+ v) G' o4 y! s  T' O& z$ f' w2
3
4
5
( ]+ k/ U3 Y6 l$ b- X) @6
1 f3 [' D6 L: N+ u7 h7
9 S: q+ y1 e- \" k( L: P# G6 {9 j8
9
10
) ?8 C( t& K4 d  K11
12
' A  t8 `+ h, X' [% g13
14
; [7 z* I/ f; C  H' ]8 X% O15
16
% r2 q/ D5 H- I$ t! G: z1 P17
0 V( p- B$ t* a5 I18
19
20
21
22
23
24
- K9 x6 ~2 H7 d/ b. e25
: b- e7 w% |# v- X% j26
7 U% {4 t  u2 z27
9 U5 J/ A9 L+ W$ m28
! [5 G9 \+ Y- ^% L2 \1 f前后指针法
# p: j+ b5 E, X% N, i2 u此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多
% _+ T  S. s% Z1 L) Y: q6 ^
cur找小，找到则停
++prev
5 L) R& g/ \$ q/ @) q如果 prev != cur，交换 arr[prev] 和 arr[cur]
; z7 j( \. e7 q( d如果 prev == cur，不交换
4 w1 p. H& I! g6 u! q& b当cur越界，代表找完，排好序了
( ?5 j# U5 [! `. y) p7 eprev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低
/ o( @* y: X* S" s+ O
6 x. f/ X2 F6 J+ l% F

$ w3 u* r. y( f: `: N1 Bint PartSort3(int* arr, int left, int right)
+ _1 Y4 D' ]& R/ f" Y{
        int mid = GetMidIndex(arr, left, right);
4 H( j' k8 e" b7 q7 a( t9 ]        Swap(&arr[mid], &arr[left]);
       
  //int key = arr[left];
        int keyi = left;
$ h. T3 v! b! U; ^# S* z
        int prev = left;
        int cur = prev + 1;
       
3 K/ c7 H  j7 Z0 ^3 ?. f    //cur越界：找完小的，prev的左边全小，prev右边全大
        while (cur <= right)
        {
        //++prev == cur 没必要交换
                if (arr[cur] < arr[keyi] && ++prev != cur)               
  W) a1 n) K: b% c* Q5 l* [1 L/ D                        Swap(&arr[prev], &arr[cur]);
  }' K; q: |6 P
                cur++;
        }
* K6 |& {8 b8 P/ v" D/ r& F; o
        //键值存是的值：
; Z6 s. Q8 Q$ d4 E8 I" w6 K        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
* Q9 @$ i0 l( V        //Swap(&arr[prev], &arr[left]);//这才对
0 Z. s* |( M$ q! F  t    //键值存的是下标：
2 ]* B) l0 W4 W7 w0 a# e) ?, W        Swap(&arr[prev], &arr[keyi]);
: |. a0 R0 D* Q# f+ l, J6 n
        return prev;
; V2 |% z$ f" U$ k3 }6 |, l5 _: F) K* y}

1
2
" L/ N( [* O" ]3
4
9 f# [/ @0 j4 z# O+ W9 u, X/ j5
! w* y3 \+ m2 M7 C! D! W6
7
8
9
10
11
12
13
2 ~- i+ l. i4 P; T8 _" E7 O14
15
! [0 l0 A% t5 r5 J' H; i16
17
7 ~' X4 P6 Y( [, X18
1 K) p$ s' y' }) c( a8 A' T% t19
20
21
22
' r1 {% p+ A+ F$ k; t* \; N23
24
* w) l1 M) q# ]$ Q; B25
2 ?, [" `" _9 d  t- O5 Y. v8 c26
6 o& `5 H" x+ P' K27
28
29
% Z, M# L$ |3 e6 C# I" M整体排序
递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

* H/ F5 E( d) ^+ R4 M//[begin, end]
: u9 K* }) S; e9 B# wvoid QuickSort(int* arr, int begin, int end)
{
        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
! I: D$ B* b5 a        // [begin, meeti-1] - meeti - [meeti+1, end]
                //1.begin > end:超出范围
                //2.begin == end:一个数天然有序
    if(begin >= end)
  s) ^% y% M1 @/ Y3 ~. |        return;
  G; q4 ?: U9 V( F
1 _3 B% X/ ~+ c/ z                //排好meeti
                int meeti = PartSort3(arr, begin, end);
# w# T' r" `. F! Q# K
" S3 D+ a, p4 v  z5 ]                //排好左右子区间
- V6 Z2 H( ?- Y% x                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
        }
7 e. Q  ]# J. I& m+ z}

1
2
3
3 i5 D, s6 l" S9 z' \& t5 K4
* |% j1 f8 d. l5 B; f/ F5
1 L. X6 {- E6 ?  U( w" u; p6
$ G& W$ N! |: V0 J" G& U7
8
9
2 f' i. w- ]. o( q10
11
, l0 `$ G9 i6 s8 A4 ^12
6 W. O. z0 R9 J1 W& P7 S6 v13
$ `  b3 F/ M4 g9 X" w3 e6 Q. c14
15
' p0 _, W. }- @2 X3 ?, ?16
: r) d, {. n7 i' Z% t0 `8 L; @17
18
7 Y' v$ ]  T; e3 b5 [3 K, a1 ]$ g…

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

优化小区间
7 g) Q5 p# P# Z, A5 Z: k8 M
5 ^4 h; z# g, M3 D5 r& L4 _+ M
4 m  b, F! U2 Z' y" Q- }- D如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序

那什么算是小区间？

其实小区间没有确切标准，8-15左右都可以的
5 `. y' P, Z* B+ s1 b6 j
; `: B4 O5 b: `/ D
这里就把小区间定义为 含有 8个数或以内 的区间
3 Y  p$ L0 O9 V% Y, S
//[begin, end]
' y/ M; n8 x, `5 [void QuickSort(int* arr, int begin, int end)
8 @* Y! `' ^9 D. q{
$ p$ u  T( B  O        if (begin >= end)
                return;
1 b5 N- i4 k9 a2 }4 O* B
        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
        {
                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
        }
        else
        {
: S, x9 `' H) X) ^; p3 s                int meeti = PartSort3(arr, begin, end);
# D3 R% n1 v+ d& S- w, d" s
5 R% G9 W5 d+ Q" E: P4 @9 J                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
. R+ i- g# z4 _" b  o' C        }
}

* }# S3 C5 N0 [7 b1
2
3
/ n2 Y) S5 X' a- n/ w7 {4
5
7 {# T( Y0 P# G1 }) L3 `6
  O$ E0 f# n) V: o5 M" ^( H7
8
8 E' W' r( g) @( a4 _9
10
" T7 P: d) R( Q/ U' z8 V2 Z11
  g- z! i2 S  G4 A12
13
3 o1 a+ _# b- U2 r4 G6 {14
% F7 M9 j: l. H15
4 ^7 m7 y$ I; I7 P- }16
17
18
; g) Q! [% Y8 y2 G; A19
' S2 [! \' Q$ }6 z% s/ t/ y6 G  P快速排序非递归
& a0 q2 J1 H+ ]; g. @1 ?为了解决彻底递归深度深的痛点，我们来试着把它改成非递归

思路：
: q; Z. t, n: G7 E递归深度深，栈的空间又小，会栈溢出…

那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！
& v% f$ {5 T; \1 {" }; p7 m
- N% A* P$ y# g. y9 y2 p核心思路：在堆上创建“栈帧”
+ C. r) l: X1 G- G+ X' J% U# M* E
+ F3 e1 d, h* M, v' Z+ b; H快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的



( U$ l4 q6 y6 P5 P在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：

4 V2 e( {. A- {1 A. C0 H6 F0 |先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
{
8 [  u  W! b+ Z0 q" ]! M        ST st;
        StackInit(&st);
       
    //先入begin
/ U( ~4 G* b2 g$ X        StackPush(&st, begin);
9 H4 m5 t7 c- r4 g" r; i' I, x    //后入end
; a9 |; C9 ~# K7 b5 u        StackPush(&st, end);
5 Z! C0 \. _: w  J$ u" t
1 r& r  x7 L" W) o5 S( H% [% h, F        while (!StackEmpty(&st))
        {
, t2 A# h! E% ?                //先取end
                int right = StackTop(&st);
                StackPop(&st);
; P  \& v8 L) m3 e4 @  E1 V4 ?! k                //后取begin
                int left = StackTop(&st);
                StackPop(&st);
7 ]  c8 J) |  E7 Z% U' [8 U
4 o" H% x3 ~& k' o/ d( P                if (left >= right)//1.只有一个值  2.区间非法
& O6 C8 k  Q/ W9 O5 I& q" _                        continue;  
) G& U5 j# A& x" |# ?. b                               
8 [* ], C6 ?/ f4 p7 z$ v                int keyi = PartSort_Pointer(arr, left, right);
( g3 ?1 [5 m" P/ r( }/ M0 d, e
& ^1 C$ w1 ]) J6 B: f* E: j; s8 M# P                //先入右区间
$ r: q+ u) k  G9 ^* {) e0 ^+ e                StackPush(&st, keyi + 1);
                StackPush(&st, right);
                //后入左区间
. g% P: w5 r2 M' h% w* a; z                StackPush(&st, left);

+ l5 n1 ]( T* D& @9 u( q0 ]7 r8 r                StackPush(&st, keyi - 1);
        }
( w4 H, R2 H# M2 I' X0 _. a
$ A6 Y4 H& y# g        StackDestroy(&st);
}
9 _3 N- l# ^3 V$ n# l$ i
1
2
3
4
5
& m" S  O3 ?, U. T0 Y0 T6
7
7 _# z7 a1 `: P$ f4 ?8
9
+ D' L0 h2 W9 E: _$ ^10
11
12
13
  C: o8 j! A/ X14
15
3 o& g2 Q3 S: M- l- D# c  {$ M9 @/ x16
17
) ^* n9 T! q* ?$ H6 K( |18
19
20
# y5 X3 Q9 [* F# B2 c9 M21
7 S+ a. A9 Q% l; G22
, v2 T8 O' m. F- t5 w+ U23
7 A, q6 j6 w1 Y( ]( Q! f24
6 `. o/ S9 @0 `  _25
! I' D. \2 l# ^  a4 a26
2 _9 A8 E; n* I) W( Q9 @27
28
, r, D) D* \3 c5 I29
30
6 z& Y) p" t/ n7 X31
32
+ A0 ^( j- L- N1 A8 [: @33
  S1 a% n3 c% s7 ?3 m34
* S9 K' q. o- Q) `9 J# v6 F35
* {6 x' `1 o+ t* r( b8 l6 L数据结构栈的实现可以看博主之前发的博客


归并排序
' v& ^! `: }/ {1 k7 }8 G9 Q
…

性能测试
, }2 r  u: @" Jvoid TestOP()
{
; S& J5 P) Q9 |. j  e5 Y! ?        srand(time(0));
        const int N = 100000;
        int* a1 = (int*)malloc(sizeof(int) * N);
        assert(a1);
# e6 N" ]% s" Z  _8 y7 c- ^        int* a2 = (int*)malloc(sizeof(int) * N);
* R% |# d& c3 ]+ g9 H! j; Y4 y3 m        assert(a2);
% F6 P% [6 E& G, ~1 s        int* a3 = (int*)malloc(sizeof(int) * N);
        assert(a3);
        int* a4 = (int*)malloc(sizeof(int) * N);
0 j& ?2 P0 J" W. J; ~3 [* C; }        assert(a4);
1 {9 \' m' y0 g! y' M, j0 v        int* a5 = (int*)malloc(sizeof(int) * N);
        assert(a5);
7 X6 t5 L( d9 v- x# J: i3 H" ]
0 H" j+ w) \, Z: w( j( \+ K3 b        for (int i = 0; i < N; ++i)
        {
# _6 l8 a% @- W0 U) n; }3 `                a1 = rand();
                a2 = a1;
                a3 = a1;
2 X+ @$ Z- o& F" @2 j0 ~8 |( {                a4 = a1;
* @' O8 u- Z9 @. |                a5 = a1;
        }
8 }" v9 S6 g: O; u4 |% V
* C+ x& \% B" M4 l) j        int begin1 = clock();
        InsertSort(a1, N);
, X& ^$ F; I4 c* ~1 J7 `1 T        int end1 = clock();

        int begin2 = clock();
        ShellSort(a2, N);
        int end2 = clock();

        int begin3 = clock();
        SelectSort(a3, N);
$ Q; ^- k* w. p. D- h2 w/ W        int end3 = clock();

        int begin4 = clock();
1 M4 d5 H  j: D& N+ V. B1 q- `        HeapSort(a4, N);
, |1 \1 w. v7 R; O4 c        int end4 = clock();
8 C) w5 T- O! U5 V& j( ?
        int begin5 = clock();
        QuickSort(a5, 0, N - 1);
                //1.中间key
                //QuickSort(a2, 0, N - 1);
0 v: P0 A' p( j8 r" I, n& v4 G                //2.三数取中
                //QuickSort(a2, 0, N - 1);
                //3.小区间优化
                //QuickSort(a2, 0, N - 1);
        int end5 = clock();
2 T5 n% Q) h" K6 F/ L. r: A8 D
" F, f  x* z" a$ I/ z! ~7 Q
" [5 I4 P8 M# Q. ]+ M( e        printf("InsertSort:%d\n", end1 - begin1);
' \1 h- S/ D! a  Z6 l# {8 l6 p        printf("ShellSort:%d\n", end2 - begin2);
1 x7 U; g: @' |/ G' Y  n        printf("SelectSort:%d\n", end3 - begin3);
        printf("HeapSort:%d\n", end4 - begin4);
# ^8 y: t9 L% B4 u  i/ V6 _        printf("QuickSort:%d\n", end5 - begin5);

        free(a1);
        free(a2);
% H1 d1 J9 J# R6 x5 \+ N3 J        free(a3);
        free(a4);
/ o% }7 W4 n! a" J$ W$ }( m# Y        free(a5);
}

. `0 L; o3 t8 l' ], h: y. x" o- K1
2
3
7 K( c8 T9 o$ u7 q7 E  C# B  \4
6 o5 e- J! U$ ?1 i, r5
. t/ c1 x& D0 r: Y4 b: D- ^6 N5 g6
1 W! |- _" W$ K' U1 \2 [' q/ P7
/ d4 Q3 j# R# F$ k3 J1 q. h, P/ E8
4 ~8 R2 o6 r9 U0 s: d9
( q; N, e5 t- @& }: Y6 w) P" E10
11
$ v6 j: r/ T/ u3 `9 f" J+ T12
13
14
15
1 g& X8 p/ j8 p- V5 X2 r16
17
) N. z2 i( I3 z: \5 b! g18
6 d+ C- o3 x9 X" ]2 H$ `* t: t* S19
20
21
0 Z6 p/ h- c. Z) A22
# t; u, r" w4 R; z9 L7 }. `23
24
25
" V0 @1 e9 ?% |- `6 Y4 [; x8 H26
27
! E* O' s9 W1 ]/ S+ C) X28
+ t+ l* U% O+ g9 l& |+ _2 S1 f4 G29
30
31
6 l. y; n: p' ?5 i% W; y32
; K8 C0 O' S* f1 F& f33
: c  u; h$ F. k34
% J' ?( ]7 b& S$ V' E# h35
36
37
& [/ N! K; \3 D+ B: ~38
6 K7 J% ?  K& R8 |3 P39
40
41
' u+ G  g4 n; T3 l42
43
44
45
46
$ l) f! n  i0 G0 y/ _47
48
; V/ Q) u( |, O. k# ]49
50
1 [) U$ f% l$ Y2 V51
& s3 y) w, I! D2 S! w2 f( \52
- x2 J3 _( D4 o' f/ M$ d53
' d) S" U* J; W: g$ b; z54
+ A0 ~# d; K; s$ O: M9 C+ X55
4 w* V/ ~2 X3 w3 W( E# J. s, W56
57
58
59
- q7 G$ x* t  A, T& U8 f60
61
- B& ^4 `- N$ H0 ~$ u62
63
, `  G$ ^5 y* F/ [# d) O9 ^
* {* Z, {4 x; U, U% `9 ]  e
不愧我们费这么大劲优化快排，多帅哦！

差一个归并排序，后续补上！
) v9 l0 q2 z: j  E9 U7 x
不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
, W+ e( [, o/ f4 F————————————————
1 Y) Q2 \! ]" N+ b/ Z) J: V+ y版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
) _# y8 e+ q, p8 L3 j0 E. M原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832
+ ~4 |% G$ q. s0 O
& W6 y, {( r8 K' F5 E
7 H& R: [* {. `0 g