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

杨利霞

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

3 Z9 T- H! F3 E7 J/ G% F6 u前言
本期分享经典排序：
8 c8 k. n  S# O
插入排序
直接插入排序
; l! k, E5 d# X, M$ W/ z9 J8 X4 z( w0 ?希尔排序
* [. w# M+ a; X: s3 k选择排序
% V4 }& u& J$ _9 i直接选择排序
堆排序
5 e0 f6 G. p" v$ v1 o0 q交换排序
& c$ E% M4 M  }6 V" Z冒泡排序
0 S& |& ~; k; \# A* _2 t5 B快速排序
注：讲解时默认排升序

插入排序
直接插入排序
3 M, I3 z: v8 u/ z思想
# n, S; Q; J$ _+ Y7 S4 e0 _$ y3 Z插入排序，就像玩扑克时，摸牌的过程：

最开始，左手没牌，右手从牌堆中摸
右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
+ L5 b" ]' K* g+ e如此一来就能保证左手的排始终有序，摸完牌后也就排序完成
8 x3 g) ~5 {' x6 k% g% p
6 W# r- _: V) Z6 U9 s
$ a8 h6 u0 m) {" u8 Z  m7 J操作
设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
单趟排序：
每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
是正确位置：插入
不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
整体趟数：
5 f# t1 S- |5 @+ N4 w- t& \若元素个数为n，需要排n趟
: y; ]- u( I- Z- x  t: S' rvoid InsertSort(int* arr, int sz)
{
2 G' m& G( F3 `, q# `# R, s        //end + 1 < sz
" O$ a( z0 h5 Q        //end < sz - 1
9 F: }3 q7 ]7 O        int i = 0;
5 C7 T4 J5 D6 T' D, `8 c) X        for (i = 0; i < sz - 1; i++)
        {
: O, n& _+ B2 ]+ f4 T- U$ @; F                int end = i;
                int tmp = arr[end + 1];

6 G/ c7 ^! @- A9 T" V' Z9 D! \                //找插入位置
) Z/ G( y& o& f( h% e                while (end >= 0)
                {
' y" ^$ m8 H" R, [: q: L: N                        //不是插入位置：当前数据往后挪
                        if (tmp < arr[end])
% P  t7 D" m8 f& z' W% N                        {
% s0 o) M% ?  ~; c5 T                                arr[end + 1] = arr[end];
% K, l# d9 f$ W; t% g                                end--;
2 D7 k8 F/ m% |5 f# G9 `& j                        }
                        //是插入位置：跳出循环插入
                        else
, w9 \; N  }) V3 V( y                        {
                                break;
                        }
                }
                //插入
; P! I5 y+ I; w4 V" {) z; w                //1. 插入位置是[0]，end == -1，不合循环条件跳出
3 p4 `# ?) a+ @  F- b* y                //2. 找到插入位置，break跳出
" C) c# r& c& `- m& _1 B. ~                arr[end + 1] = tmp;
0 B$ o. M* c7 ~7 H; M        }
+ z  `1 f+ U# L1 c: E}

9 e8 ?- M, y  F1
6 M# W9 b4 E: l* U0 c4 k2
3
$ i* [8 |. {. h9 T7 ^# ?1 Z4
5
6
7
+ D& U- K) ~6 z2 n8
9
, K' l5 S  ~7 M10
11
12
13
" r/ j. a+ C. e- m$ k6 Q6 V& G) D/ B14
, ^6 f* w  i# Q6 l15
/ ^( O$ g0 b2 Z4 z16
9 j1 q* i" i: [; |17
18
19
- z2 U) V  [3 n9 ?* ?! T20
/ _6 y6 R9 S$ k$ d6 z. E0 z21
7 e3 m' r3 @4 F. V9 b22
) e# m2 a- i  v3 J7 K1 E23
24
+ {0 L3 e. ~/ d* O3 I25
+ b% F" T  w) U+ u8 S26
9 X" k$ d' v! E2 w+ }5 c27
# I3 ^7 Y) m9 i4 N5 |28
29
30
8 b4 m0 z  U5 b  j) T31
: v" O" i* s6 ?" ~

稳定性
* F# Q# ^4 ^) u+ _+ O插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以
! v/ `7 ]4 J6 u  R. V. Y- _2 i
# r. _0 E9 _0 O/ v直接插入排序是稳定的

复杂度
, H* B! n4 T/ n) V' G1 ]: B时间复杂度
最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）
, l6 n8 T# _: D6 M1 O! I( E. D
/ n1 b  q6 s4 qO(n)

最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2

O(n^2)

空间复杂度
O(1)
# `0 c; r* G. Q1 H, c3 T4 y
! \( }/ q- b# d& n( D  |8 ]$ c' h希尔排序（缩小增量排序）
# w# M, {& u! C* m希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序
7 l/ c8 }+ B% C; z% ^6 q; M
1 ~8 a! M0 c& D- J优化思想
增量gap不止用来分组，也意味着数据移动的步长，所以

; A3 S, i; U0 k! b3 g' V: ?9 xgap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高
8 ^) n9 m0 |" q

操作
单趟排序：
( e! T( c" ^7 I
8 j: x# r+ M2 y设定一个不断减小的增量gap，也是元素移动的步长
以gap对序列分组，并对每组分好的序列进行直接插入排序
3 L5 i: |* m' X* m7 m不断缩小gap，并排序
4 p* Q2 H: _3 P) v* [; j; s& A*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
" L( w% l% {7 F$ _6 g整体趟数：

/ \, g" P5 n* Z* j3 Y由gap决定：当gap = 1，排序完成
注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。

6 N& `8 f3 _0 x* n4 qvoid ShellSort(int* arr, int sz)
' p4 R& H1 U; i& |/ [{
$ I0 P  |- h/ C, \8 \. `        int gap = sz;
       
    //gap > 1，预处理排序
    //gap == 1，直接插入排序
+ X' q! A% C) ^6 y) a        while (gap > 1)
        {
1 [3 B. j; F' s                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
0 q7 ^# c! U8 V- @7 A                //gap组
, c% w/ [* I1 _( H/ M" h" N8 c                for (int j = 0; j < gap; j++)
                {
            //end + gap < sz
                        //end < sz - gap
                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
. T% K! m, W; _  d* R                        {
3 }% @  H4 C% C7 {3 g1 {! [                                int end = i;
0 M0 _, ?3 D, @                                int tmp = arr[end + gap];
1 F' k2 w# \' c' I9 ?' Y2 i1 o                                while (end >= 0)
                                {
                                        if (tmp < arr[end])
/ p: U: U: b. U9 D) ~  H                                        {
( w3 O: J* N' D5 q6 \* r# e                                                arr[end + gap] = arr[end];
1 f9 c& e; ?& k6 ^                                                end -= gap;
/ K  {& R9 A0 c+ `  _( W- _                                        }
                                        else
, B' c( P5 ?6 L9 R+ t8 V                                        {
; I( F- N5 {( a5 M6 D                                                break;
                                        }
                                }
1 W1 Z/ L! m8 x                                arr[end + gap] = tmp;
8 \. E2 I: U5 ]                        }
                }
        }
8 p8 s9 f' _' b1 h  z! K; L}

1 g% s) I; {8 L% f& @0 U. D; d1
4 R8 @$ P; d8 ~$ W+ Z! Z2
; k# b7 a) w5 h7 g$ C. f6 g3
4
5
6
7
8
- F) r2 Q5 K- z. i4 R" @9
10
3 `6 _% J  b/ \* h  \11
4 K- G' ?/ q5 R; P( O1 A* t# b& g12
13
' ]4 I4 l! [& R  l& _( M14
1 @1 z3 D8 s$ J# K1 O! \. v/ {15
16
17
18
* V7 T1 n1 S5 A19
20
  n$ |# f6 Q/ h4 p0 ]6 a21
& F+ k. F! y  M# ]0 Y2 t0 y22
23
; v9 o! C) `# r8 d+ n24
4 R5 n3 S- N# V0 ?. t, d' W25
6 W  e! v0 g# E7 |8 D26
27
; @7 O" W$ L$ t, e28
29
30
31
32
# e+ B' g4 ^1 C8 S# F/ H  a" K; u33
2 Z5 N5 o0 C) y" l# E' h$ D. ~# x34
35
其实就是套上”缩小增量“的直接插入排序

9 \8 }: Q* Z5 u, b9 m  w
稳定性
6 x/ A/ s7 m- |3 `我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以
6 O9 }7 _% _. V: F" u' f# x
希尔排序是不稳定的

复杂度
时间复杂度
4 ?  p/ J6 N# i' U希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：

) |' V1 X; F* ~  mO(n^1.3)
# D! u( }* c+ u# o0 F
9 x# X2 F) }% p1 V7 Y空间复杂度
O(1)
, R% ?7 P3 O+ q: ^3 Q
选择排序
, `5 n' m$ C0 C直接选择排序
+ E% A) D& I; t- s- o思想
选择排序，遍历序列，选出最小的元素，交换到左边
* v1 H, O& M& T* v


优化版本：

每次选出最小元素交换到左边，选出最大元素交换到右边

操作
设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]
6 B% s+ M7 ]- I3 J3 j
设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标

单趟排序：

遍历选最值的下标
交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
（修正）
整体趟数

( B3 r8 H, \; ]若元素个数为n，趟数为 (2/n)
/ I7 ^: E' R% b! s0 W修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标
! X# e+ x: c+ L* |9 y( }' g! h
void SelectSort(int* arr, int sz)
$ P* D2 D8 S, v# l9 Z# a/ q{
2 M$ a: g0 [. K' i: x, a        //闭区间: [begin, end]
        int begin = 0;
        int end = sz - 1;
        while (begin < end)//begin == end 最后一个数，天然有序
# g% Z/ C/ s' J. t5 {/ z% [        {
                int mini = begin, maxi = begin;
0 x' l$ Y: Z5 |; }1 V3 \                int i = 0;
2 @2 H, E  @, t5 S                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
/ }# `: @- Q0 Y1 B6 V: n6 E                {
                        if (arr > arr[maxi])
                                maxi = i;
                        if (arr < arr[mini])
                                mini = i;
) q8 X3 x( a3 }                }
5 _6 g/ z+ O+ d: a( j" T
                Swap(&arr[mini], &arr[begin]);

; W4 C2 l: t) J" L9 N                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
                if (maxi == begin)
                        maxi = mini;
                Swap(&arr[maxi], &arr[end]);
" G3 b* d2 ~/ d* i  V& G/ l# [
  z# |; Z7 K$ T. J3 p                begin++;
                end--;
        }
}

# M( t4 k# v3 V. P4 ?1
2
3
# V, V! V) _! n- e0 c% c4
5
: `" L# \  {  B6 O6
7
  S- D& {% w% y: O# A8
& v  P; i" h" _; V+ I9
/ @& }0 k( _: ]" K3 x8 Y% ]6 c10
11
9 O, L' K1 g* {12
& p6 A- _, c2 x! S13
: a7 o9 p' I" c. z. g; a8 F0 |14
+ X& b) @9 F! }2 A& W& s% t; g15
16
17
" `7 a0 E9 }+ Y. R5 N18
19
% E% |. n$ ^- f8 M) |$ N! h, K3 b1 S20
21
22
23
. X( I6 ?& m" r9 k24
9 J, \6 t/ N3 ^% v& i25
26
27
: t4 a% ?! g2 N7 T; D28


, d. m* s  S( Q8 e! m, Q稳定性
8 O4 a5 R7 q% G* Y! S! S6 C- z选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以

" j% Z% o0 Y2 I/ b! {- V3 O0 H选择排序是不稳定的

* u  X0 Z6 ~: _- T复杂度
! Z* j" T) F" G0 P' [时间复杂度
  q% z" q0 y2 ]. o" Z最好：
8 K3 J& w1 k! O/ ~
比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2
/ r+ q2 M( R- o; j+ W, n
交换次数：O(1)，有序不用交换
7 d; ], l+ x% Q/ @
O(n^2)

/ G* g! Z! l, H& x# R/ _3 x; h最坏：

7 K, }& W9 r/ P: Y* i- N3 L; K比较次数：O(n^2)
  l+ L" I1 M% h" A6 _8 ~7 @
交换次数：O(n)

O(n^2)
# |0 L5 d. B6 f
空间复杂度
O(1)

# H/ Y% o4 Z- X% j$ R$ w( T. I堆排序
0 E) \4 F, u6 C* S  `1 S思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆



, T0 M9 Z* g* G; m0 S操作
建大堆
单趟排序：
选堆顶和堆尾的元素交换，则堆尾的元素排好
# E* o) W+ `; A6 @9 V* ~每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
- u" E# v9 U& L0 w2 @& V4 d+ L整体趟数：
若元素个数为n，则排n趟
) H# x8 _  J2 p3 \: |) [% {6 bvoid Swap(int* e1, int* e2)
{
) I$ {% ~: S; f& _4 E! o        assert(e1 && e2);
) O2 M7 V9 u- o# [+ X2 j
& [2 Q8 B5 g3 a- u0 |$ W2 b        int tmp = *e1;
        *e1 = *e2;
+ v- P8 m( H2 \9 ]+ ?        *e2 = tmp;
}
6 G) M2 r- e+ A/ o" h
void AdjustDown(int* arr, int sz, int parent)
{
$ `" E- ~5 J; Q1 a% D) C        //建大堆，排升序
        assert(arr);
       
    //默认大孩子是左孩子
/ y$ z" ^0 K3 x5 C        int theChild = parent * 2 + 1;
- R  d" @8 j  W* p% N        while (theChild < sz)
        {
        //如果大孩子是右孩子则修正
5 T7 j; }0 H7 h- U. H4 r/ }) o                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
7 j. U4 C5 }+ [9 b7 t$ F, w) J% X" |                {
                        theChild++;
                }
6 q9 N( G. j) ?* |0 D, {. _                if (arr[theChild] > arr[parent])
- v$ \. x) i0 d5 X# C                {
                        Swap(&arr[parent], &arr[theChild]);
0 t4 q+ ?. \, v2 h$ R* g; B            //迭代往下走
                        parent = theChild;
                        theChild = parent * 2 + 1;
5 W; Z+ B+ G; `" o* X7 g                }
0 u, W2 `+ z- Y                else
                {
                        break;
# F) f) V. C. b) b! S% E                }
+ y2 ]% N8 j; D, w2 C7 `9 ~        }
# y1 I1 x1 r' {/ A+ D, {}

) O2 y+ @, R! L4 O9 w' uvoid HeapSort(int* arr, int sz)
  u" ?+ u! Z* V/ q{
        //1.建大堆
        int i = 0;
0 X0 V/ x" J; }* _  [5 `2 w        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
        {
0 j9 N+ h! [" U) ]4 C: b  h                AdjustDown(arr, sz, i);
$ |* _( }0 p6 E% `" s8 {        }

8 ^  x$ g" Q% l, z' E7 J        //2. 选数
: B+ `/ Q: ~0 U7 }9 b  N8 L( Q0 y        i = 1;
- y' I9 X& S6 l4 ?0 k# }- N        while (i < sz)
        {
) d) H1 q0 ~+ B2 M                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
8 ], |' y/ W) v% O                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
8 ?+ l+ p0 g/ x0 L5 R# V+ x                i++;
        }
}

# c' }8 n4 ]! G/ Y. Q' `8 {+ H- \1
2
& i) A; \: t6 H, R! j% l0 U; L3
+ Z( I! I5 `) D, V# V4 i4
5
( g  q( F6 M, M( Y$ D6 O6
7
2 R/ ^* W3 [) C. C2 s' o. A. u! m8
5 C& O! G; ~, P, L  g  y. d  o1 f2 {$ ^9
10
& H1 a, B: h! _( [& C& R; S  R11
12
13
5 W; a. Q& S. X1 ?+ i5 K14
; L' c: s# W' z/ O# i/ q15
16
17
- M; u# W- q; x18
19
- d- [4 T" k* n  z20
! c8 T  K" u& ]. L21
22
$ b+ y1 Q5 `+ s$ z6 a; K9 [' l23
24
+ P2 N) i  k/ `25
5 n3 |4 O# z7 k0 L0 @6 \26
. P* E! s% P* M( q27
- ?- p( c- ~# }+ O, ]28
29
5 L1 k; _! ^9 h1 b4 F* C30
31
32
33
34
) |9 H% i3 f8 y) S  _2 J) v2 E35
36
" G$ @& Q4 [, l37
38
39
40
& b9 w9 M, x, Q0 b2 X* S. ], {1 a1 }( u41
42
43
1 o! L8 `0 w; Z1 n5 H44
45
) V" \; x7 V- x& u4 H* p46
( K0 N: n+ z1 e% a$ c47
48
49
. H/ F1 |, x/ J- q: g8 j4 u50
51
& t: r8 Y/ \6 {8 L9 s52
. P) l% L/ m* u3 j8 y3 O53
4 y2 \, p, r" s5 B54
55
+ V" g6 W- Y8 Y1 y1 l

稳定性
7 M' `3 i* T4 I4 r建堆和向下调整都会打乱元素顺序，所以
1 g3 ]* x, U+ d5 P$ h' d  v
2 V) D5 ^& I. H3 b/ P堆排序是不稳定的
- ?) F7 B2 h  t# S4 P. o
4 w5 J, }  ^/ P# V; u复杂度
时间复杂度
单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为

1 r5 r2 x/ J! aO(n*logn)
: L0 B# e  {, g
: x6 s- I' C0 o4 d" Q4 w空间复杂度
原地建堆
) Q6 b) S* P2 O2 t; g; V
) a% {/ C. W7 u( DO(1)

交换排序
& W( G; E2 g/ t) I4 S, Y冒泡排序
6 D* F: B* F' a  V5 \; u4 E思想
冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素
' O, {9 W4 p! Z' l' a9 z
3 z5 }! }* Q- ?# N( U
/ i, l5 a+ T) {2 r
- M) L& z& b0 x操作
2 L1 W2 k8 ^6 ]& X单趟排序：
每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
每趟排好一个元素，所以需要排序的元素每次减少一个
) i- H1 Z6 Y) v8 S  m整体趟数
$ R' Z8 e: [4 w4 v2 ^) D若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
3 G, m( O$ Q& S: i# jvoid BubbleSort(int* arr, int sz)
' j( A; u" D; T( R{
        int i = 0;
' I) H, l& k1 B/ Y- [        int j = 0;
        for (j = 0; j < sz - 1; j++)
        {
                for (i = 0; i < sz - j - 1; i++)
                {
                        if (arr > arr[i + 1])
                        {
3 B% d' W! R+ f* ~5 a" q( e/ |                                Swap(&arr, &arr[i + 1]);
9 r! e: y' C( ?; k- c9 l                                flag = 0;
- o8 K" p7 u% {" F* O7 G& ]5 I4 t                        }
" Y, S$ ]2 i+ X7 ~7 r% f0 I0 n                }
- f" h3 N1 ^3 F& C        }
}
$ {5 `& b; o9 c2 `
2 ?# P/ e% r  m2 E0 Y+ r- Q* ]1
# g' K. c+ K6 c6 a# B, ?2
3
/ X4 J7 C8 K/ W! O  Y4
5
5 q& `$ j( v, z4 `0 q( `) ?6
7
8
9
9 x$ L4 q+ `" i6 k10
8 }) N) F* X! e9 V. r! h11
! a# [  L( o" V" D$ [4 N3 r# y7 I$ ^12
0 b1 p& q9 ]  o) _13
14
4 i3 {# Q* f1 t7 ?+ Z( Q15
& W5 n' g" k& M( ]& D16
优化
( S4 d9 }& R) w4 z当遍历一遍发现序列有序，直接跳出

void BubbleSort(int* arr, int sz)
{
        int i = 0;
1 B( G) C" U  m/ \# x6 S; y        int j = 0;
! y% {! R( g0 j* ^4 M, Q        for (j = 0; j < sz - 1; j++)
% [" m( M  k# u. `  Z0 d& X3 E        {
9 H! ]$ v* A* `# t                int flag = 1;
8 y. q2 A! `* [' ~+ f                for (i = 0; i < sz - j - 1; i++)
5 r# T% I# |# j! f0 h  G, R8 e                {
1 E: g1 D% H! a- i2 h& h4 F                        if (arr > arr[i + 1])
5 B4 m% m3 u0 f' z: {                        {
$ v& c( L4 x+ Y. N' @. n                                Swap(&arr, &arr[i + 1]);
' j& [/ X9 y" k; L$ Z. _2 M; `& z                                flag = 0;//不是有序就置0
                        }
1 L( \7 I; b9 p: {( f                }
                if (flag)//如果一趟下来还是1代表有序
! V/ A1 M4 a+ m5 P1 h                        break;
        }
$ n  y5 Q7 {( C, l6 D}
7 `! D0 P# L6 V" f/ ~/ g" t
1
2
2 |2 U# m2 I" c) @3
4
5
6
7
; q/ H( ^0 ^2 V# _8
9
8 \, Y6 K' U4 K0 I1 Q/ m" D10
; h- N  n6 N  d  O11
12
13
7 i) r. k$ j3 }- J# [& X14
8 V& r7 q2 n$ V/ a: W; V15
& k9 Z* w; C9 d# `16
17
! R$ {! @: k2 y* s1 C2 E18
  I" ]' P7 ]  L+ p! a# J6 |19


/ R2 O1 y; ^4 ?! ^9 F5 t稳定性
相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以
7 Z% w7 Q; M' ^$ C( ?" M- s
# f: d$ W" k: u/ ?$ t冒泡排序是稳定的

复杂度
2 A& n0 X: x2 Q& {" l* A时间复杂度
最好： 当序列有序
& t) C* Q8 a2 q9 V, {
0 J# q( G% {, M未优化：

6 D3 S- Q  j" J$ aO(n)

优化：
' }) m  e* i9 S
6 Y; h' }' p: k5 Y- h8 k' J* LO(1)
. }5 D; F! E$ t$ k$ o: ^
9 i: A0 B) u1 h, L- \最坏：要进行 n-1 趟排序，每趟交换 n-i 次

% p. E& \* f  i- E  b+ e9 ^O(n^2)

空间复杂度
O(1)

快速排序
思想
分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。

( @8 M) K& b' s所以快速排序可以用递归来实现

0 C( y, C/ R9 O1 c" _操作
有三种单趟排序的方法：
, K/ a1 P. F0 _& ]4 c1 ^* a
Hoare法
- L  s; A" G" P! ~/ a# e设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间

' C) e# o$ ?6 N左下标 L = begin，右下标 R = end
( s- E- C+ Y& j: Z
( I5 ?" F; x3 N# U. r9 z设 L R 相遇位置为 meeti

1 t, S" Q! R& q9 A* J* f% \​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”

$ {( X5 }0 g$ A; [​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“
! Z. M- V( F1 V
8 d' G& G) M/ d+ E, ^) k6 B  `. N选 键值的下标 keyi

8 @' P/ U% S! E" x/ f左1位置作 keyi，则 R 先走
右1位置作 keyi，则 L 先走
R找小，

1 @' B0 k. B9 \! A2 V找到则停
7 a# u: h9 S* |9 ~, |9 n* U遇到L，则交换 arr[keyi] 和 arr[meeti]
2 Z: r9 f( ]9 l4 W8 h% UL找大

找到则交换 arr[L] 和 arr[R]
: Y. h% |1 e5 X遇到R，则交换 arr[keyi] 和 arr[meeti]
  p) [9 L. m$ x/ m7 ?1 d( `
1 b+ W6 q2 T' ~; {0 ]! H
# m! g2 W  _8 ^- K& }解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
0 T" |6 A8 A0 n4 o答案是肯定的：

) P" m9 s2 Q4 M7 O2 S2 N& D# I

( |1 S4 h* ^$ t, e/ B: U
( ]) a, F- \3 S/ x; U" O//[left, right]
5 v9 L- M9 u! K* H3 \( [: Z: I; eint PartSort(int* arr, int left, int right)
{
- v: o! L' v, Y1 p) F1 r        int keyi = left;
  t$ j8 ^2 V% g/ r+ J5 q        //相遇则排好一趟
' h1 I3 c2 O- d/ E' `, s1 o        while (left < right)
        {
* d. q7 M) G; k5 X- f, J$ X+ h                //R找小
- b7 k2 R! l; }1 o: k        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
; i! A' C( e+ }( O# ~' n        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
                while (left < right && arr[right] >= arr[keyi])
                {
                        right--;
                }
: w& j" k; M6 G" E; V& m
                //L找大
& o) `8 T7 ^& o  L1 z0 F9 F( v3 M                while (left < right && arr[left] <= arr[keyi])
                {
                        left++;
7 G# v5 Q3 P( i# j6 T' q                }
0 Q# k* n0 Y2 |5 w6 Z7 S# B               
        //相遇就不交换了
                if (left < right)
$ S( y2 ^# O- Q1 W" p8 J                        Swap(&arr[left], &arr[right]);
2 U( x* Z1 S6 r4 _( E! L" S5 S        }
$ I4 x, W/ G8 O% N- Y
        int meeti = left;
" U2 y# N* i) x0 x8 V! T
        Swap(&arr[keyi], &arr[meeti]);

2 T5 P! G5 _9 y, h6 A( T; w  n# ?/ v        return meeti;
}
8 \. ]8 X0 z: j
1
2
3
1 Y# P* o* w( J- e$ O4
5
) ?7 W! d* y' k% q2 `  _/ r6
8 x  ^& k; D4 ]+ i9 ], \7
& Y6 Z+ y* I* U9 |2 B& m- N8
9
7 _. q! T# E% F10
11
! _% s( x" v. Z12
13
14
% _$ Z/ G) u$ f5 [; x( e4 P. ?+ d15
16
17
- t: F3 N% }, L" s2 I' I18
' `2 W0 h9 U0 E2 Z3 K3 Q1 ~19
) S0 k8 e) V7 f. l20
21
22
23
& ?  p" Z* F) t7 X8 M24
* L- I; E4 j9 ~) u1 G25
- Q5 [4 X" A! v: D: A26
# ?# F: ]! Y: l  C27
" F$ j' Z5 e+ {. F1 p1 p2 |28
/ W6 G2 ]) v" N4 x4 i  [" z29
30
; z# ?  Y  V; a6 f9 q31
8 z8 d  C; N3 \5 g& u& [$ `" l32

6 m6 M- ^& g' C, S2 V$ z7 R# r% @
解惑：为什么key要选左1/右1，选中间不行吗？
  v' K( q- D2 O. T

* Z. z$ S: Z1 y6 P6 I: s( I* E可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深
# R, H# N8 n; m+ A; ^
+ q8 l* P  M+ ], E  X: a
/ l" }0 F1 @$ ?( g7 t. g  }

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

优化选key
3 r- M( X! ]4 d) Q! O# u随机选 key （是一种办法，但是不那么彻底）
选中间位置作 key
. A" `7 i8 m6 \3 s: p0 Z$ F+ I0 O解惑：那先前实现的单趟排序不就失效了吗！
# y7 z% I9 j, B! p( I：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑

解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
前辈给出三数取中的方法

% c/ K/ m8 K, E% v* |; N三数取中
在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
5 m% l6 O2 R7 I这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
优化选key后的Hoare单趟排序：
5 m7 {  H0 [: L, l9 ^! E" ]
int GetMidIndex(int* arr, int left, int right)
{
7 b5 o8 ]  |( ?/ E        int mid = left + (right - left) / 2;
# f8 I+ Q; B  {0 T: x/ Q0 y//  int mid = rand()%(right - left) + left;//增加了一定随机性
5 s8 n, t  s! z. z, P; c/ c, Z        if (arr[left] < arr[mid])
6 Q/ ]. ]! L* _9 b        {
                if (arr[right] < arr[left])
. O5 B" A- _* U& E                        mid = left;
" I+ o$ S2 t1 E, r0 y- H                else if (arr[right] > arr[mid])
0 T, o; I8 `* g8 ]8 X' s/ e, K                        mid = mid;
                else
                        mid = right;
        }
        else//arr[left] > arr[mid]
5 u4 e7 {/ _( A* p9 U% W        {
9 I8 J  W" T7 a                if (arr[right] > arr[left])
+ X9 m1 g* V. s" P: {6 s                        mid = left;
* }1 k2 b# I/ k. k) ^0 c                else if (arr[mid] > arr[right])
3 g8 V& S, l$ E. q                        mid = mid;
                else
% q6 i5 C% t( c( n1 p                        mid = right;
        }
  Z$ ~0 a2 p9 l: x( S$ p$ L        return mid;
. W6 f) m/ w9 M) W: |+ w}
6 q5 I, l9 K, R/ i6 `5 y' }$ B. B
' ?# H" a( F0 U& qint PartSort_Hoare(int* arr, int left, int right)
{
: S' w+ `: E! k$ P        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
. R5 ]* b) t1 D: |) l) @9 ~        int mid = GetMidIndex(arr, left, right);
  H% W8 r  d+ L$ J3 [
        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
        Swap(&arr[mid], &arr[left]);

8 r0 i5 d$ Z/ Z; h. i        int keyi = left;
2 ]+ O0 f. k4 D        while (left < right)
        {
                //R找小
                while (left < right && arr[right] >= arr[keyi])
                        right--;
# x0 _' U8 F; i. X* K
9 g, R6 W( h6 E$ d+ P                //L找大
                while (left < right&& arr[left] <= arr[keyi])
% Y3 Q6 H' T; W; d. U, b; ?' [2 u$ W7 O                        left++;
& ?) ~% v% b; D7 y
. Y" |9 L/ e: c, z) l4 A                if (left < right)
  b" `. C' `7 g$ n6 u0 {) x2 T( @; @4 w                        Swap(&arr[left], &arr[right]);
        }
, s6 v& X* l) I! T0 ]
        int meeti = left;

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

. l* N  s5 X5 n        return meeti;
1 u  h# ]+ X- K) u' @' h}

1
2
3
3 F/ y  w, R( ^! o; L4
8 s$ T* _# X$ S9 R, S2 M; A9 ?5
0 ]: u3 k6 V$ Q. o$ m6
/ G( }% z/ A7 p  r8 C8 ?' f7
8
9
10
11
, h3 U  T3 u$ r* h12
) s4 J; e5 e6 P( D13
14
15
# z& P5 A# R8 m16
17
' s* a5 G# v9 e7 M( b3 P1 x& e18
0 k5 ~& V/ r' w' N, E19
' [; W) D  G% b2 b20
21
22
23
24
25
& t8 ?8 ?5 q% j3 C; b26
4 i7 u: I7 _8 @- t0 e. U27
- u+ [$ [4 @  u5 B8 I5 U! o, U4 `28
29
30
8 G$ A) t6 V- J31
32
3 g3 F' R) M$ T" c6 O/ O% _33
34
35
36
: X+ K2 w1 D$ `' r  `7 ]37
- N- o/ h6 L8 g$ @( p38
39
& [, M# q% {, o3 T4 ^- V( o* ]40
4 O) t8 V5 L* k+ z2 U+ T41
42
0 k, k2 o; ~" V43
; T3 [, c7 J, J( r) k% w* @3 S- N, I44
" @+ ^- ^# m; s' l$ x6 D45
46
47
# ?; x! i, ]/ \3 Z48
49
50
51
+ Y& Y1 Z% b+ p4 U- K52
+ M/ a2 ~0 T4 x; u5 e$ B53
2 S4 G' @9 Q( Q* F: p54
* x0 ~( w  b/ v  G4 q6 p3 P挖坑法
9 s( }5 t0 O- B" A+ L初始状态：L作坑，其下标存为key
(1) R找小，扔进坑，R作坑
4 Q6 ~* a0 ]% u# I(2) L找大，扔进坑，L作坑
/ V8 P7 h* b$ W9 d$ X$ k重复 (1) (2)
5 z: x; |4 G' l" x最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]


int PartSort_Hole(int* arr, int left, int right)
{
) Z. ?( t6 n& K5 K        int mid = GetMidIndex(arr, left, right);
5 c/ E# J/ F6 y8 Y) t- ]' S, p        Swap(&arr[mid], &arr[left]);

! ?. x- s+ C0 c- ~        int key = arr[left];
' R# N! }# E- w5 U. @& h        //L作坑
, t+ W4 ~) s9 s, v& Z        int hole = left;
# f# @) n* m, h3 W1 V; n" ^1 g        while (left < right)
( o% }/ H8 f& X( T# |' \        {
                //R找小，扔进坑，R作坑
                while (left < right && arr[right] >= key)
- N6 L4 {; r" y, O$ }                        right--;
                arr[hole] = arr[right];
7 j- Y+ s/ K, m+ N" u                hole = right;

                //L找大，扔进坑，L作坑
                while (left < right && arr[left] <= key)
                        left++;
                arr[hole] = arr[left];
" p( b/ l1 U6 _# O. o- \                hole = left;
        }
8 N9 }; S0 Q  x6 m: h        //meet
# ^5 ~8 S8 v2 Q6 S9 A        int meeti = hole;
- K5 I: _5 T+ u+ _+ e, ~        arr[meeti] = key;
: J. G4 _& j% @8 V2 \
        return meeti;
5 }3 E! x( ?% Z7 Q3 l' \( B}
  j4 r+ a, \, u  q
1
2
0 k- y" F; H9 N2 N3
- Z" ^& A- N  N4
5
5 R9 K% R- q$ e3 v& A0 Q& e1 K  n6 Z6
7
8
9
10
11
12
: f6 F3 a: s. |. G0 i13
14
) k  U; |  n1 l15
0 k: S' K1 k' n( a. h( l% q: v16
; a) }0 P/ z# R6 U17
18
19
" I, N: C) _0 m" n6 M' R+ {20
21
5 D: K) N( X' Z) D9 h4 T2 |0 X22
23
5 W0 p' q6 G5 f7 a4 s) z24
25
2 L5 t& I( A$ f* F$ d26
27
28
0 O( D1 K0 n- s0 z- ], a/ s前后指针法
) ]. ~/ Z6 l  n0 v4 H' x* O& s* x此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多

cur找小，找到则停
: z- O) q- J: V+ T( E# k: _++prev
如果 prev != cur，交换 arr[prev] 和 arr[cur]
; F/ h8 ^/ t! |2 e如果 prev == cur，不交换
8 Z; p* h6 X5 c; _: n当cur越界，代表找完，排好序了
# P& v0 B2 R' w, }% i# F2 ~prev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低
' `& L2 m: v6 H. }* K# G+ I
  X- O$ P8 g" M* I& }; z

int PartSort3(int* arr, int left, int right)
{
        int mid = GetMidIndex(arr, left, right);
; F' e) P9 P# ?        Swap(&arr[mid], &arr[left]);
       
" ?% \% P4 n; s8 D/ a( n) Y8 z  //int key = arr[left];
' t! \. U! ]" I1 L9 a        int keyi = left;
7 m2 M3 m9 A) |1 r
, X1 D7 F9 r2 U5 Q4 E        int prev = left;
        int cur = prev + 1;
1 V/ K8 {/ f9 }* T" B       
9 i/ x$ B9 V& D4 i    //cur越界：找完小的，prev的左边全小，prev右边全大
        while (cur <= right)
  f) \- n+ U3 [( B% R5 g        {
) W2 O" C* j& L2 R0 T0 g; }& C        //++prev == cur 没必要交换
                if (arr[cur] < arr[keyi] && ++prev != cur)               
                        Swap(&arr[prev], &arr[cur]);

* _* R, k9 g) \8 {5 d                cur++;
        }
. |2 P& ]% f! l# I4 Y
2 ~6 q8 \/ }: T/ J4 J5 F        //键值存是的值：
) Q5 x5 w* {9 E        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
. g( l* M5 K5 D1 s, N# h1 w        //Swap(&arr[prev], &arr[left]);//这才对
    //键值存的是下标：
1 m9 [) o$ \* Z9 z/ h        Swap(&arr[prev], &arr[keyi]);
. ?; r0 Q/ N9 o+ n  {* N
( {" s9 q" i  F  {9 @        return prev;
5 }0 \" w! v% D}
6 _5 g+ p8 o0 V' n
+ f6 C" s' R; a' t- O1
2
) V# ?* U; b1 p( X# k7 z$ A3
4
( R2 P0 U: u5 u4 [% g9 y) c5
6
* z+ z, l! X/ C; K1 g7
: a3 K) m8 a& w. ]& V" i* w8
# a( w, ]! [9 G9 k( D  J) z9
  a7 p( y$ Y, B- F. k- |7 h4 [3 k10
11
12
9 W* R; h. v  d13
; c5 h. n! l" M+ n, W" l14
$ d8 ?) o- @: y. G8 u5 h* p15
16
17
18
19
20
21
: {" U# y5 c9 q6 l% u! D22
23
24
25
26
/ t! y6 J0 U( S- l, Z" E1 z27
4 Z! O6 L* I; y4 S, m* @28
29
+ Q( k; d& Z& j整体排序
& L. _" v' {, m) i" U6 a4 y; B+ [递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
1 U- s. Q! P  P- M        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
: \# d4 n5 m6 \: G        // [begin, meeti-1] - meeti - [meeti+1, end]
                //1.begin > end:超出范围
                //2.begin == end:一个数天然有序
    if(begin >= end)
9 n* q9 q1 q1 L6 N# M* m$ ?1 Q        return;
/ j' @1 Y6 I$ T' k
                //排好meeti
% m- y' Z& d6 f  A4 x: @. e                int meeti = PartSort3(arr, begin, end);

                //排好左右子区间
                QuickSort(arr, begin, meeti - 1);
9 T, u1 I% y( Q" @3 ~                QuickSort(arr, meeti + 1, end);
8 d5 Z, A! t8 N  n5 F  W        }
& [# L7 O) p1 f8 `( E0 d}
, N$ A4 @% V: g, V; @% W
1
) c3 a, T3 D" _/ ?# q2
1 r# |. ?, \# ^9 w8 t4 H1 f& H3
4
8 ]  Q0 |( V: ?) [9 S" `7 J5
6
7
8
* a# b) C0 P1 J/ i$ n9
: u- d( w& e2 p. I8 l' B% L10
+ p5 ^4 }, a3 p$ R/ O+ G' ~- p9 {11
12
13
# r4 Q; h* A: ]+ ?) z14
15
1 v6 g( l- Q0 E  p* }8 m5 R: `16
17
7 ~% y# P" N; z( Y" @+ }18
…

1 q- l' ?5 R* }1 \# H* Y没想到吧，还还还还有可以优化的地方！

优化小区间
/ U  k3 O, ]& [% ~7 v
0 O! @+ o7 y- s" A9 ]" E# R
; G' V* N1 _  |: d) v7 }如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序

" x- g3 J4 v0 ]1 \: U, d那什么算是小区间？
; f) k1 }- N8 T* F1 `0 ]
3 r  p. b2 T" v; u7 n" Q' \5 T: `! I其实小区间没有确切标准，8-15左右都可以的
# p7 ]$ |3 e, ]/ n% K
3 e3 d1 m: p8 W
* V, Y2 k+ c% V8 e0 e0 I+ x这里就把小区间定义为 含有 8个数或以内 的区间
! W0 [3 m; i8 j* D. J1 J
$ }" h. c6 s7 J' R//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
+ y; Q# \* n) u+ T$ w; u        if (begin >= end)
                return;

        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
4 L0 e' m5 P2 e* ^        {
                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
. Y$ h7 T! A9 |6 r. _5 a  }        }
! S, x% ]4 f5 Z- n$ Y/ h5 X        else
( i9 _/ V3 t) g$ a* |( k6 d        {
' A3 t7 K) h! ]- \% U                int meeti = PartSort3(arr, begin, end);

                QuickSort(arr, begin, meeti - 1);
6 b, p$ ^* y; x2 G& ~1 r& u                QuickSort(arr, meeti + 1, end);
        }
/ |" q% e- c! [( n: Y2 ^; N}
5 w. l9 Y( o) j( r' I5 C& s
1
2
3
4
5
  O, e; o( c3 m; B  p5 }8 [6
7
8
& S, y7 ?  M' O( _/ d* X9
8 w! ?8 g& @) c9 n% n8 Q10
* f  a# I3 x: J+ l2 T) b11
12
13
14
" c  Y$ [/ s3 S! f15
/ A* w, w' }6 L. s) d) k; O+ s16
6 R* V9 e1 n; R* ~, f0 w17
18
( l$ E$ l. n8 Q19
快速排序非递归
3 `+ y( j' P% a; {为了解决彻底递归深度深的痛点，我们来试着把它改成非递归

! m5 l! p9 {" M思路：
递归深度深，栈的空间又小，会栈溢出…
8 u3 ~% e, R* n5 ?$ S9 c6 G
8 V( N% ~  G: r! u8 n4 t% }那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！

核心思路：在堆上创建“栈帧”
, W4 V  m5 [8 r' p( g- m
( q; M6 O. l& @. r, y& U3 e快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的
. \1 i4 ^9 V5 E* B
1 U$ x( W# I/ h# A8 W1 c$ \) X
3 _. c8 l5 z8 N: `5 q8 V6 M  T
在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：
$ A# T; m) J3 B6 C: u# ~
  o7 b; o6 J$ u先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
9 S. p+ J- e  c, r2 U( S{
        ST st;
        StackInit(&st);
5 K; [, _2 s% B' F# e+ ^       
    //先入begin
. ?! W: A2 F- X, F        StackPush(&st, begin);
    //后入end
6 {9 i& b/ P: b9 Q! Y" U        StackPush(&st, end);

        while (!StackEmpty(&st))
        {
                //先取end
                int right = StackTop(&st);
$ k- f5 H% P5 G3 n4 H) D                StackPop(&st);
                //后取begin
0 }+ Z& j; f5 O2 P                int left = StackTop(&st);
                StackPop(&st);
/ c: \- {4 R, L. R% g' t) }
4 M, `, }' g: h                if (left >= right)//1.只有一个值  2.区间非法
1 e3 O2 R; J2 j+ Q7 e/ o0 i! g                        continue;  
                               
- R. ~; o. ^7 {                int keyi = PartSort_Pointer(arr, left, right);
% r4 d( s- e' V
  O9 t$ M5 X" [                //先入右区间
; y1 T. t: g9 |+ c4 w1 y  b                StackPush(&st, keyi + 1);
/ g5 {: C0 d7 N2 Z3 v                StackPush(&st, right);
  A( H1 ^. D0 [+ s7 G$ y                //后入左区间
8 m4 _( G  R" V  r$ p, L; A1 f. k                StackPush(&st, left);

! {3 {9 r# D/ U- p8 ?( h9 B                StackPush(&st, keyi - 1);
        }

% L" b' Z; k* a" `! M        StackDestroy(&st);
' T  z3 r" [$ B+ d}
/ G2 z5 g* `) g/ A
1
% L+ i: k# w; b; ~' o" W2
3
# F, v. W; E+ I. s1 ?! B# D4
5
- M5 m/ L( p8 o  p  o6
7
# C9 X4 ]8 m( q8
* S4 `0 i4 J. n* P9
. H, }/ k, h( C1 @10
11
12
& j6 ^" k* w, a+ a+ ?( `/ I0 K2 m13
14
5 ^% E9 t7 b9 k6 ?15
16
17
' Y2 _; W8 l2 P4 b* o18
19
" a1 W3 O5 p0 i20
21
& e" L) L: r$ O3 N# {22
" X8 |/ Y$ }) w1 f) }23
: z0 V6 q9 |1 B$ r# V5 T2 N24
25
26
27
, M5 k3 `/ `' N28
$ H, r  \: ^* ^7 T! T29
7 {; h+ M4 @, M1 H( c6 Y/ Y30
31
: d& }7 k+ q* A% T. Y32
2 Y9 q! ?+ x5 \+ C+ {33
34
, K5 S- L2 T& S. Z8 t35
+ S1 v* B) R" K数据结构栈的实现可以看博主之前发的博客
! Z# M/ f6 O# ~" k$ x# C  }

归并排序

…
1 n' D. N2 a$ Z& @) ?
# k4 G6 C! z4 s# q: N性能测试
( X( H3 x: m: c4 Zvoid TestOP()
{
        srand(time(0));
/ k+ I1 v* [5 ^4 a& u  ~. W& @        const int N = 100000;
        int* a1 = (int*)malloc(sizeof(int) * N);
        assert(a1);
3 _2 d- f6 e8 ~  |7 ?        int* a2 = (int*)malloc(sizeof(int) * N);
        assert(a2);
        int* a3 = (int*)malloc(sizeof(int) * N);
        assert(a3);
        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
        int* a5 = (int*)malloc(sizeof(int) * N);
% _/ R$ |  G. t- y0 _; W) F7 u        assert(a5);
/ {* Z+ z/ p9 t- l* w' w- f
$ T8 f9 L) c! O        for (int i = 0; i < N; ++i)
: q3 I# m, q9 l! A) l+ D        {
, c2 m. W" a: V: z# R/ i' P                a1 = rand();
% R! q. H7 }* h9 p  A                a2 = a1;
                a3 = a1;
                a4 = a1;
2 B% c+ f+ ~" U* C' S& |7 H$ `                a5 = a1;
        }

0 B  N/ S# N+ u$ F" T( J% }        int begin1 = clock();
        InsertSort(a1, N);
        int end1 = clock();
0 |  N2 q+ c4 f/ w
        int begin2 = clock();
        ShellSort(a2, N);
        int end2 = clock();

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

, e0 }# m+ p* G- m& e+ M        int begin4 = clock();
/ k/ a& U- N. ^2 W; \' z2 S" ]        HeapSort(a4, N);
' D( K1 D1 l! K5 D. q0 U$ W        int end4 = clock();

7 Y# y' K6 T* v$ J& F( r3 Y& v$ Q        int begin5 = clock();
% W' t6 e" q: B* n0 W- H' u2 |- S        QuickSort(a5, 0, N - 1);
                //1.中间key
: B, Z# M7 \  c' ?( Z                //QuickSort(a2, 0, N - 1);
2 X# ~6 F$ w: M1 m+ L( {                //2.三数取中
0 ^& r% t3 |% k4 J; z: Q8 h                //QuickSort(a2, 0, N - 1);
                //3.小区间优化
, N% q4 p* ?/ ]  u1 \% ^( C0 {                //QuickSort(a2, 0, N - 1);
; K# g. }' T: Q; x( m        int end5 = clock();

2 }) D! ?+ h2 G) l' e4 E* [1 z5 K! N# s2 ~
9 G$ Q% Z; l9 h9 ?6 \        printf("InsertSort:%d\n", end1 - begin1);
* N, A' e* _; b* f3 R5 \        printf("ShellSort:%d\n", end2 - begin2);
        printf("SelectSort:%d\n", end3 - begin3);
1 O, N; H! x$ R. E- @# J' Z  }: B        printf("HeapSort:%d\n", end4 - begin4);
        printf("QuickSort:%d\n", end5 - begin5);

! U  Z/ A/ y% O: ?, q( r        free(a1);
# P& k! A' z) ~" L$ ~        free(a2);
: A  {7 T. V4 M( x: `! t% |0 R        free(a3);
        free(a4);
4 N# `. E1 b, c. v2 W/ g/ |' l4 k        free(a5);
}
; `( C2 M0 j+ U6 }$ t: B' q
2 U7 Z4 w& C6 ^" e/ O% J1
" X: g; W+ h) G/ x2
% q; Y- }2 v+ D1 i# h# v; `7 T3
4
2 G* ^1 ]+ ~% Y: {5
: K/ I: e5 Q8 a9 T- @" y! K6
! ^8 ?9 V, N+ m( X7
2 \2 R7 n: A7 v8
4 S9 g% E5 N, ^% C/ w; D. K2 \9
7 r# c+ F! x+ N! f, b10
, f* f. L7 }+ M11
12
13
14
15
16
4 n( I7 _* ^# u( j- B9 B$ a17
18
19
1 V5 ]2 G( e! ^. K( R9 D20
21
22
- Q: `. z- M+ m* T23
24
25
26
27
( C1 o2 \5 v8 U0 s0 E; l% g+ V, `" |28
! i% Z8 A4 {2 A* M( r29
; g( e, W+ I8 M) v* D1 ~30
31
32
8 [6 k( m% u& K& L" @6 E33
34
35
36
37
38
39
8 N5 k2 V- H8 c5 g40
6 h2 }8 V% V8 w. v  z/ d41
42
43
44
" ^# ?; @1 {4 c* P9 s- t45
46
2 W4 Q) M1 Z6 h1 Q3 K8 B47
! z  S4 Q) n3 ?48
49
; \5 }' p( o" B1 ]' M" U8 @  ^5 y1 @50
/ u* z2 G) Q/ Z: K. y9 _51
# ~" o! s- p' l) g$ J, ^52
  u6 |# O2 s% I3 q( V5 i53
2 K8 a5 b4 ~$ e. s. A  t4 _8 N54
; u  `' `0 G" l0 [! c4 B8 K55
56
57
  ~) x6 m* e# m$ d( ]4 t58
59
60
; i  k  a' Q1 g- u6 R61
62
' @0 a" B! G. C63
, M) D/ y% z4 I8 [; c/ S, L

不愧我们费这么大劲优化快排，多帅哦！
$ Y, N4 m" J4 n1 O7 r
差一个归并排序，后续补上！

0 `& ?( p" f1 F不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
" Z# S4 d* R% h, j: f* y) @————————————————
2 F, s; T$ R7 e6 q! y版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832
) `4 C& ^% ]6 T" ^7 h! u; ]% Y