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

杨利霞

【数据结构初阶-排序】经典的排序算法，很有趣，有没有你不会的呢
; v! G. F. `! U  R& t$ m( \
前言
本期分享经典排序：
. k5 U+ p7 w9 e2 U) `9 H
1 U: s* i* e& K5 @插入排序
% B. @, o  ]7 {6 f- U1 ]% L直接插入排序
希尔排序
5 j4 ]& J1 x% {) j8 Z选择排序
直接选择排序
1 {! b( Z6 `; a) I堆排序
交换排序
4 M) w1 ^- g: ~$ q1 K2 P冒泡排序
快速排序
注：讲解时默认排升序

$ M+ a. s: c  L- g6 P# D插入排序
( F0 R# a; q' x/ I+ Q直接插入排序
思想
插入排序，就像玩扑克时，摸牌的过程：

" B9 V6 F- N% z! ]3 K, h6 X7 y2 @最开始，左手没牌，右手从牌堆中摸
3 o2 N: x' R' O6 j5 Z0 j8 I/ p: H右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
如此一来就能保证左手的排始终有序，摸完牌后也就排序完成

, Q0 n3 r1 z4 I# D# |6 f
操作
8 [# G/ `' ]8 r. ~5 k& d" H  u设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
  q+ t3 N" A) z% c2 @/ ~" W单趟排序：
每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
7 J# x) M. ~7 |- |9 r是正确位置：插入
不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
% {' i5 m6 _. @4 \3 ^6 K, D) F$ @9 W整体趟数：
若元素个数为n，需要排n趟
* h+ o# e5 w9 }  Q1 y- xvoid InsertSort(int* arr, int sz)
  G( m: A8 _; Y# |{
6 T: o8 z3 x( l. E4 t        //end + 1 < sz
/ M9 A. C9 S8 E$ b, `5 L        //end < sz - 1
        int i = 0;
* m/ E% m, ]! x( l2 R. {7 c8 C        for (i = 0; i < sz - 1; i++)
5 r+ H% H! h1 [/ s7 E; i0 U        {
                int end = i;
                int tmp = arr[end + 1];
  s! C" V: |$ I8 V+ y% R! j9 ^
                //找插入位置
# W' e% `: k: f7 o5 t0 |                while (end >= 0)
# F8 w. o7 @& T" \7 }) B                {
                        //不是插入位置：当前数据往后挪
                        if (tmp < arr[end])
. s; y, z$ Z, ]                        {
                                arr[end + 1] = arr[end];
' {4 h0 b( N/ F3 r                                end--;
0 n* N, C! B5 _& G0 t                        }
* Z" P% Q4 e. h$ {, o                        //是插入位置：跳出循环插入
                        else
; ?# c5 L+ P6 I/ W0 ]                        {
                                break;
                        }
                }
                //插入
                //1. 插入位置是[0]，end == -1，不合循环条件跳出
                //2. 找到插入位置，break跳出
2 q8 Z: ^9 ]# ^) l3 P8 c" c3 m' P                arr[end + 1] = tmp;
        }
$ u3 \/ d3 a. d}
" }* ?2 C( v; o) v$ ~6 T" I
1
$ T$ u8 q  Q: V! ~2
. f# f! I4 }9 J/ D% L' S6 F3
! _3 t8 r( s1 n# K" D( b4
5
6
- }% y. K/ h5 V/ i3 j7
8
9
7 z, s) C! g" e+ K( W0 \0 q5 N10
. }1 t- g. ^2 F3 {: q11
12
1 f% n: I+ O# |. x/ t4 y+ m13
14
- }$ c8 k3 b* Y15
! F) y8 F+ N. x16
17
18
% }6 T1 ~  a) p$ J8 x) g* P5 Y) B6 m19
20
21
22
23
24
25
26
27
28
29
30
4 K8 m2 z- b9 o6 c9 s31
0 x& g# N$ g* j, ^9 P2 Q5 X

% c1 q3 q! ^& H; I; C稳定性
+ ^8 [% @. N( J5 x9 o8 P( G. A插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以
$ d$ ]; e6 u# ?; R2 j& `5 H7 x
! u, |+ _+ H+ T/ X  ?& G直接插入排序是稳定的
: @' S$ V2 \3 R' X( G8 H* U+ E
复杂度
* Z! u, M3 q8 x; [  L时间复杂度
/ R" W8 m+ O9 x- T- v8 {最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）
2 K: o+ ^; K( p
! F4 ]% U' T' J( B0 ^O(n)
& A; T- p$ W1 |& d4 A( G' Q- w" @
最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2
/ I! w/ s: H9 Y4 S4 m
8 x. ~' u: ?2 b0 [5 QO(n^2)

空间复杂度
! |+ o& C9 X, J! AO(1)
9 J3 v+ L" u% z" k1 w
希尔排序（缩小增量排序）
希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序
) T3 H2 s: L6 W3 {
优化思想
增量gap不止用来分组，也意味着数据移动的步长，所以
8 D0 ]7 C  r" o# N1 |3 P
& |. n( y0 U& lgap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高

. K9 ~' U8 o* K( n# S6 c
; m" @) q4 J: G. G; ~操作
单趟排序：
2 Y! a- d7 R+ r" ]
* w& j* x& G5 F! [& b设定一个不断减小的增量gap，也是元素移动的步长
" _# e# L6 u5 i/ l( v2 e5 C以gap对序列分组，并对每组分好的序列进行直接插入排序
# S+ _) F' e) S9 T. {9 a不断缩小gap，并排序
  m$ d+ J. f- j5 Z9 w( ?*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
整体趟数：
& M4 B$ B1 {/ b3 X
# D5 j# ?# k' U9 W, N* j  B由gap决定：当gap = 1，排序完成
注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。

void ShellSort(int* arr, int sz)
0 f$ W7 Q) Z3 ~{
        int gap = sz;
; ~+ L/ q7 F4 z6 o" T0 A       
) B$ Z  G) R/ A' _6 Z    //gap > 1，预处理排序
4 u9 o1 m  O. B9 a! d7 y/ f' L    //gap == 1，直接插入排序
/ o6 B' L/ S& j1 U4 w, w        while (gap > 1)
0 e' U) V  j6 w3 Z5 E) P" B        {
6 W: ~: I% Q- u7 v; f                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
" A" E& f! T: Y# r. l                //gap组
                for (int j = 0; j < gap; j++)
                {
0 P2 J. S9 |" O& h            //end + gap < sz
( J, M  _* Z, n( J- P                        //end < sz - gap
                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
, f, h  m* h4 T( ^6 B1 P                        {
                                int end = i;
                                int tmp = arr[end + gap];
                                while (end >= 0)
                                {
                                        if (tmp < arr[end])
                                        {
( S! U9 ?% u* V' ~" H                                                arr[end + gap] = arr[end];
* ~. V  L7 O* R; Y                                                end -= gap;
6 b6 V, F3 t( {2 {* N                                        }
                                        else
                                        {
, L5 U; j% L$ v                                                break;
( E. h1 h2 |) B; g                                        }
  m! t* V6 l4 b                                }
                                arr[end + gap] = tmp;
                        }
/ p, r/ }2 \5 ~, A                }
        }
}
" C  q6 N9 c& E! \
' G3 t3 t( t! \% P$ B( n! Y1
2
# m1 Z9 [+ k0 a# @8 G( x- x3
4
6 L, O& I6 j4 E- E+ _) M5
! f: w4 F# f; e5 }3 y6 U  L9 R6
7
$ \( E/ x4 T' _# X& r  t6 l8
1 M3 N. c& Z8 b$ a* M9 \5 \6 }9
10
" H. F* R. d6 r# Y0 O11
; W$ f5 Q  V; x/ i12
13
9 c6 P0 Y) L- [& a14
+ `& G: r  X: A; @+ q15
% x0 b. J2 {9 X$ d' |# n16
17
18
3 X  \- ~$ u% ?5 k- o19
2 m+ j& X5 N0 F: b) ^( V20
1 O9 G+ h) p2 M9 |2 K( O0 X21
22
  Q2 J5 D# S# c7 i9 e! }- q- X2 H9 G23
$ r. a4 p/ z4 d2 G; S2 K24
25
4 b& i' r3 P; t/ I26
27
28
6 g1 f. ]# b" c7 E; r% r' R$ G, G29
30
5 [7 I& B) G' g* S0 K9 S0 P: w: T8 W31
32
33
! q' j; v4 |4 B* `2 d/ l5 Z34
35
, V2 ~$ l% F. i6 N  S" k其实就是套上”缩小增量“的直接插入排序

5 R7 ?* P- z! |, c& [
  s' @5 Q: `) j1 C8 v; |1 c稳定性
我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以
( V: q8 d$ l4 |" z% u; O
# u3 ~$ M, H) R; s希尔排序是不稳定的

复杂度
时间复杂度
希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：

O(n^1.3)

空间复杂度
( D/ I6 G! Q* r( {* X+ W- nO(1)
# {6 w, A. G5 W' A5 E# J
3 [, L$ K8 c- ^. ~0 j选择排序
+ n$ h0 V4 [6 _) n8 K+ q" D直接选择排序
$ }* W" v3 w7 S1 H9 h! s思想
2 x0 f1 y$ z+ I% }6 J4 q选择排序，遍历序列，选出最小的元素，交换到左边

* u$ `, o5 e- J6 [7 v

9 s8 {, v, X: ]# T. ?) g优化版本：

0 h& r1 k3 Y! `/ E! g; p每次选出最小元素交换到左边，选出最大元素交换到右边

操作
% D3 Y2 S# j: ?/ f9 u, \% ?$ _7 Z设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]
% \* R3 ]( X: p% f" V  ~% e& w
设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标

单趟排序：

& e% E# d- V+ i( g3 O1 v4 a遍历选最值的下标
2 G. P% T) @( c+ M交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
（修正）
整体趟数
$ s. i- a: S- Y  u8 B, R. [
  c+ X7 x9 c0 z& B4 d若元素个数为n，趟数为 (2/n)
1 Q2 w$ X5 m5 O" c修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标

void SelectSort(int* arr, int sz)
9 j) ?; ~0 P' B{
        //闭区间: [begin, end]
7 B1 p( e5 u, f        int begin = 0;
        int end = sz - 1;
* f+ ~7 E; Z- v& |# c        while (begin < end)//begin == end 最后一个数，天然有序
$ \/ ~( d' B+ ~& m        {
8 b7 C. {; d: Q0 `+ R( J' x; |                int mini = begin, maxi = begin;
                int i = 0;
7 _6 X& y# D7 e% S  u2 j                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
, {& K& {9 U% w* B+ F! V                {
                        if (arr > arr[maxi])
                                maxi = i;
- Z7 f/ {& Q0 z9 R5 B4 {$ t/ s                        if (arr < arr[mini])
, v7 `4 l, n, n9 a+ u                                mini = i;
                }
0 c! x1 ?1 k8 K7 n0 f
% R0 }2 g1 g  |1 X- `                Swap(&arr[mini], &arr[begin]);

                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
* i. B$ {9 J2 P; h                if (maxi == begin)
- K9 c6 a9 N7 ?                        maxi = mini;
0 n+ G/ f2 ?# [/ c) q                Swap(&arr[maxi], &arr[end]);
" W; Z3 @# n' {% K2 S0 s
                begin++;
/ Y: ]& `' n; H/ s5 N5 ~) B: I                end--;
        }
}

4 T! f, ^5 m+ W, l  [3 B: O8 S* H1
6 K0 f8 P' R( L2
3
2 d& k% _. }! {4
5
6
7
8
9
10
8 R: S  u" h! `$ {* H! S11
6 L* n) E8 w, ^# |* Y+ X/ A12
+ D' ^3 G: D# b# ?13
14
15
16
17
18
4 F" }8 k& n9 f4 d6 Y6 _9 e19
20
& S* Q; K7 L, J/ t5 l2 U21
( W6 f0 ^( m5 V, a: ^& U; L22
23
7 E- E! H+ q1 R/ p- Q. j8 |24
25
26
0 l6 W( g( @: t# I. V; I$ t27
28


& m) ^& m1 i2 r. y. F% i稳定性
9 `! G2 l$ l8 z" T& e选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以

5 B: c7 r2 Z# @  L, m0 q  S; t选择排序是不稳定的
3 K$ q9 w8 {+ \; J% i9 X
! U/ [( r/ v# u* i复杂度
7 k+ F$ Z/ V  ?% G- w' ?  g时间复杂度
1 A" Z! P4 D9 R% h最好：
+ u  `  R. J( ?6 V3 y
比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2

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

O(n^2)

最坏：
- n9 E5 f4 W9 e" U; I4 Y
比较次数：O(n^2)
$ [; e8 e) H, B# L- M/ o. l
. K; S' W5 ?7 K0 O7 F8 l9 R$ {交换次数：O(n)
- ?0 C( U0 _: N
( l' u2 b/ J$ t2 h- j5 e8 ?% MO(n^2)

空间复杂度
O(1)

3 s$ V- ?5 l! F/ `% y) W堆排序
- X- F+ P: ?0 s$ F( l思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆


% L/ c, V$ H+ ]$ ^, U  w
# F  [9 F% _! ^: s+ B2 v1 N操作
建大堆
单趟排序：
6 P; ~  d+ r4 ]选堆顶和堆尾的元素交换，则堆尾的元素排好
8 u/ z' [( \# j9 o5 N每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
* H- N! ?# {: ^0 p: `. Z- ~整体趟数：
" C* l" O) H* a. l  L若元素个数为n，则排n趟
+ i" A3 k  R& svoid Swap(int* e1, int* e2)
{
; |+ K5 u+ X) `3 K! q* J+ m        assert(e1 && e2);

        int tmp = *e1;
7 V, X+ k, d+ a        *e1 = *e2;
        *e2 = tmp;
! x. e) h5 i  J, \; `" k}
1 Q- J* L. B) a9 Q3 w$ D( A
void AdjustDown(int* arr, int sz, int parent)
' D0 ~" ^' ]0 F! L- y9 I( c{
& q5 J9 v% M: `! n        //建大堆，排升序
        assert(arr);
       
    //默认大孩子是左孩子
  c' E! S  }. U# U2 q        int theChild = parent * 2 + 1;
        while (theChild < sz)
        {
        //如果大孩子是右孩子则修正
                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
                {
                        theChild++;
                }
- H  _! b, q* J3 _5 {                if (arr[theChild] > arr[parent])
2 S5 L3 t  S( r: p8 |1 X/ t0 k                {
3 ]: c% G! W  [5 [                        Swap(&arr[parent], &arr[theChild]);
9 y+ V8 V# ^0 e0 e- p* m4 R) p            //迭代往下走
' I# {3 j& i9 r, u, ~2 S: n" h! _                        parent = theChild;
                        theChild = parent * 2 + 1;
                }
                else
                {
6 }( b1 f. @: e+ o; G0 x                        break;
                }
3 L7 @9 s$ K* E+ J  S; F3 [        }
. f6 `; Z& R1 `! t: ~}

% J. {& X# p' v3 b) z3 O9 {) nvoid HeapSort(int* arr, int sz)
{
        //1.建大堆
, k2 X- P; o7 I        int i = 0;
/ q; ~5 V& b( x8 h4 ]        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
4 K- e. S0 o( J  K- n5 d  a        {
" @( |  E6 J  y1 Y% P; ~8 d                AdjustDown(arr, sz, i);
        }
$ F( s" }- U; p* w
. b+ r( W$ y/ }        //2. 选数
        i = 1;
        while (i < sz)
        {
9 m9 `' s- c3 g! q7 p. W/ n                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
                i++;
        }
$ x' ?: l% r2 f: {$ J}

6 W8 W9 r& v/ I6 s/ l4 r9 j, ?  }1
( h8 J3 u" `3 o8 N2
3
. W. M" F4 T% t2 N, j0 e3 C4
5
( I, ?, K1 `3 C  D, b; g6
7
4 Q# B4 D- x1 p7 ?8
  |3 B, j/ Z+ y9 k2 w, G( O9
3 D$ h0 L" _, T10
11
12
13
14
0 \* v1 V9 w, ?& Q" g! d" O15
16
17
3 Z& W# y: C  L- B18
' O. |8 q% n7 G1 X  B2 B" g19
20
21
! }& J( u8 ]4 [; s22
0 k3 `& D0 o8 ?, Z0 |23
7 L6 p) e* y5 S' }8 I; F24
( e/ |: u0 i4 {: B25
# T& L$ R9 C: x& f9 K) L( ?: a1 m1 P' h26
27
( d" S3 b& N. j5 O, y28
29
- e' ?% y- P8 M- n) |% U5 D% H30
7 V% C0 A7 J% o: |: S6 \7 W31
32
33
34
35
' q2 t3 V' `2 H1 o* p& X9 c36
& [2 \9 h! V" e1 b8 Y8 M37
0 q( [& C; k* \# A/ n3 ~38
7 g7 j( L+ }' R2 x  y# d) [39
+ l2 E, o3 ]' v5 k7 V" B' {! Y- z40
6 r5 t6 v- k; T3 W6 L( S* K+ E41
6 D" q. a! {2 P1 R2 V8 v. y42
7 S, J. |7 p% @43
  M# U, X* ~, \$ l44
8 a' r, t6 `# h3 S45
46
47
48
49
& M/ U1 c. V" X( L3 A% N50
! a! ]- B( \* J( k( L5 X$ V51
9 T" A4 }: s  F/ k6 g52
53
6 z" B: v# l4 @54
55


稳定性
建堆和向下调整都会打乱元素顺序，所以
$ r0 D; C8 x3 S2 D* C
( N: r2 ^$ E' u5 K& z7 x堆排序是不稳定的

复杂度
5 \# r* A3 d, `% Z5 l! k. `" i5 u时间复杂度
单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为

6 E  m# I0 H9 l/ B9 L$ hO(n*logn)

空间复杂度
原地建堆

O(1)

' l$ I' M+ W) U+ u交换排序
# I& v, I, ^0 Z7 N  K; K冒泡排序
) R9 x+ Y# p+ ?% a( ~) p思想
冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素
, ?) K8 ~: Z$ m$ g$ T


& C& g7 N& Q8 ]操作
单趟排序：
( d/ M) o7 c7 |# a) Z4 O; p0 P每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
每趟排好一个元素，所以需要排序的元素每次减少一个
整体趟数
若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
2 s1 ~9 o4 I/ K& z2 f1 Nvoid BubbleSort(int* arr, int sz)
; U7 h* W" h  }4 G* N6 G+ P" ~{
        int i = 0;
' k9 u$ d8 ~: d9 g+ {        int j = 0;
: L5 w$ E# O$ e! X! A7 M* L8 R        for (j = 0; j < sz - 1; j++)
        {
# [9 H' x4 J; K) d3 Q                for (i = 0; i < sz - j - 1; i++)
                {
$ S& I2 q4 g/ _; E                        if (arr > arr[i + 1])
                        {
                                Swap(&arr, &arr[i + 1]);
. ]* v% y) x: s% q; l$ K$ I                                flag = 0;
1 G: L0 ], C& a1 `6 A! T7 T                        }
# g7 M4 n' e; `. \# Q+ `9 a% U9 O                }
        }
$ H( f& ]6 n  G! l3 u/ c}

1
. e' T. v: O: E2
3 f& i9 x  V) M- Q- U4 g3
9 u" E7 R* p$ K3 \( |8 V# \: k3 r, Y" ^2 D4
5
3 A* h; `7 w2 l% i. c6
( s7 J/ k/ Q" g6 ~0 l; @) H5 P7
8
; V0 d  B: M9 O9
, b. Z8 d  x) `10
/ W2 |" Y: m  s6 ^11
3 n, e) z9 q! E/ s" n" U12
13
14
* P  ?5 G, [7 @# \% m3 Y* k15
16
- q; J6 T. Z0 c8 `4 X6 m* B优化
当遍历一遍发现序列有序，直接跳出
9 ^+ N& P% Q' k# A) m3 K& ^" y/ k
void BubbleSort(int* arr, int sz)
{
* L7 ^& O( _( d' H. f- F4 X* W        int i = 0;
        int j = 0;
) D0 j, b6 _2 M/ L$ ~' X6 `        for (j = 0; j < sz - 1; j++)
        {
                int flag = 1;
                for (i = 0; i < sz - j - 1; i++)
% ]9 l2 V4 f2 R- e) B* v                {
! |: h1 k" Q) }, K) Q- w! ^8 e4 d2 m                        if (arr > arr[i + 1])
0 N( v& g; ?% N4 B                        {
* X: g. {& ]9 F  i  T  i                                Swap(&arr, &arr[i + 1]);
) R; O3 R2 }; J# T                                flag = 0;//不是有序就置0
( h) ^8 I" Q: `) }6 p! M- X* p- I- ?                        }
                }
0 @. B3 s& W: t) M' W* K5 L; x                if (flag)//如果一趟下来还是1代表有序
1 k% j! ~; R: A# _! n                        break;
        }
9 b3 N: l! G* Q; u( `}

2 z( v& g: ~1 N/ {0 e+ R5 K1
2
- @/ o4 N! F3 u9 i7 p3
4
) L" O# Q5 W, O3 u5
6
* A; U9 q" {! }  y& J! r7 d7
  l: M" }- b0 w8
9
10
# p( T1 v. d2 r8 [0 G" }11
, O; T! y* {1 g1 s* w12
13
14
2 X2 `) w* e0 m# ?+ c15
$ `9 j" h" s' z2 b) y; X7 y. |  E16
2 i2 t* T4 `( h9 D. g- g17
18
19


稳定性
9 Z) n9 p, z0 X4 y& K  j7 a; j3 j相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以
. w: [9 `  u5 U: w
6 s3 Z. P% s2 ?8 ?7 A! J$ J冒泡排序是稳定的
7 M, o! s) k; Z$ Z
复杂度
时间复杂度
最好： 当序列有序

8 [. m$ O; y3 I4 v# _3 i未优化：
0 f# I! \* A; z
O(n)

优化：
4 k% U/ l& Q* r* x/ Y
: \4 e. W5 A4 S* b! \$ X; J+ c7 ^O(1)
% v/ ~% i0 l" ?% B; G- a/ K( z' i
4 I1 Y4 q6 R  p% I: J0 _最坏：要进行 n-1 趟排序，每趟交换 n-i 次

! _% ~* `0 c) E: U9 J; _9 v7 gO(n^2)
8 `5 v; \% W% L/ G; F4 i
空间复杂度
O(1)

0 y6 B' \- t. }快速排序
思想
, q4 m3 \( B$ d( r9 Q分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。
6 U$ _3 Z' @8 J7 k( _' j
5 @9 d2 k, _5 Q) S所以快速排序可以用递归来实现
* r0 Y0 m# h; }9 j+ r$ `' {0 R2 C
9 `2 V& A; A' j$ Y: I! l操作
有三种单趟排序的方法：

3 D9 J4 ?+ x3 z( IHoare法
3 {& Q' k2 H( u. |+ `- L( Q设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间

左下标 L = begin，右下标 R = end

& h  z5 m" v2 I2 g! }/ Y1 L设 L R 相遇位置为 meeti
6 x4 W' U0 ?8 R8 ^  t* f; J+ u: g
! \- r0 y1 s4 r3 N  ~$ Z+ ^* z" r0 B/ V​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”
- q2 G$ I  P# B  X& _
& W- a; L6 I" k​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“

$ b. m  b) E0 Q) A- [选 键值的下标 keyi
- H  H# w# d* m; l
左1位置作 keyi，则 R 先走
: M, S$ H7 ^2 C0 N& }5 f右1位置作 keyi，则 L 先走
R找小，

找到则停
遇到L，则交换 arr[keyi] 和 arr[meeti]
, r* G2 s' U; j; E: O# gL找大

1 X: m. m: `. |0 N; I; ?; s找到则交换 arr[L] 和 arr[R]
% Q! _9 e5 V: J- B遇到R，则交换 arr[keyi] 和 arr[meeti]
- m( U1 J% ^6 I( ~  f& a3 ]
+ H5 A$ Z0 H- P. G* y9 l
解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
答案是肯定的：
. Y5 {% I/ m; P0 y* p2 ^2 f& q% c3 ]
( A1 X% z/ l8 [# M% c
7 ~  [8 n) u; ?; H) j

( d& U1 v6 u! j# i' y& {//[left, right]
7 v# m! M1 ^& H6 ~0 Yint PartSort(int* arr, int left, int right)
{
        int keyi = left;
% z1 P0 P. g  {0 J7 p% v% J        //相遇则排好一趟
        while (left < right)
        {
0 }3 p/ @$ E6 Y- j: z                //R找小
        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
. u! \: ]/ b' R' N( ?        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
                while (left < right && arr[right] >= arr[keyi])
                {
                        right--;
                }
; }. N% M9 s8 C7 D2 P, d
7 o7 e9 U9 U6 x, l) V                //L找大
  c: V+ \8 V4 p6 f# L                while (left < right && arr[left] <= arr[keyi])
                {
                        left++;
/ P1 V. D8 M& f+ o( P" y" W5 z                }
* ]5 t3 J4 {' t               
        //相遇就不交换了
                if (left < right)
                        Swap(&arr[left], &arr[right]);
8 S, z+ ]# Z) r. D* J3 k$ y        }

, x( s, B# H3 D& V        int meeti = left;
" c1 l5 f, i4 F4 J4 r# B: t
        Swap(&arr[keyi], &arr[meeti]);

4 l  \" D( X, P# |3 d. F        return meeti;
}
/ B+ L/ Q3 {6 s: N* c2 Q1 J
/ E, J; S! C5 u" a; e5 Q) I1
2
3
* `+ ]) Q: I' r5 d9 i4
9 B6 v) p' ^% u! B  n5 ~3 M5
$ S& ]. s- ^" X* ~: {. O0 S6
& W5 I) Q- A9 [# i2 Y7
3 t5 W# D# {- T5 r; k8 [: D8
9
! S1 T7 Q4 [' \. o6 {7 N3 u10
" K  U4 K7 v8 l11
8 _; `( y0 N; v. z4 Z' C& M12
13
14
15
6 |& A& I1 g. G* v16
17
3 D0 a$ J7 E2 I1 i/ U+ Q18
19
9 U# x& q# _/ T" s+ x4 W20
21
  L: U- [) U' x% H( M. M' _22
6 A3 M  O0 H9 L2 ?23
24
25
4 q5 \" Z2 i# _7 K$ q/ \5 j& `4 }26
27
28
29
/ |3 o9 F6 q7 ~" l30
31
32
% i5 N& W7 V( E. n2 K

8 b0 s7 v0 Y( f# |' t解惑：为什么key要选左1/右1，选中间不行吗？
2 C" b. Y( w  ^

7 H4 q6 a' D2 F0 k& b可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深
5 F" ?; I$ Q% I1 a7 V


5 E: M9 Y) |& N6 V% o3 M
8 r: t6 s) u$ {: {+ O  y非常容易栈溢出，怎么解决？针对有序情况，优化选key
* G: g7 U: B5 l+ a" f% N
优化选key
随机选 key （是一种办法，但是不那么彻底）
选中间位置作 key
解惑：那先前实现的单趟排序不就失效了吗！
：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑

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

# a, R4 l. ~+ ]- E三数取中
# g$ W9 S" n- F7 Z* D8 f在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
优化选key后的Hoare单趟排序：

; }9 t2 J7 D% oint GetMidIndex(int* arr, int left, int right)
{
1 i: Q, g8 E4 Q3 t4 B- E3 ~% m        int mid = left + (right - left) / 2;
# e0 ^4 @% S! ^0 J//  int mid = rand()%(right - left) + left;//增加了一定随机性
8 |0 D/ h. [* ^! R% ?3 J        if (arr[left] < arr[mid])
9 X0 a, V- Q* j  k        {
3 j/ I$ o- w2 m2 t9 M4 n& y$ q                if (arr[right] < arr[left])
4 j2 _) s& B# f6 _; O: k9 S/ G                        mid = left;
  i$ l; P3 M% r3 }' @, L) u  D                else if (arr[right] > arr[mid])
                        mid = mid;
                else
7 d1 {3 u. `$ k$ N                        mid = right;
( e; b$ G$ Z  w& P1 G        }
) ~, @! n% T3 h8 M        else//arr[left] > arr[mid]
' D! n0 D- _$ }7 v$ n# i        {
+ k2 [% q$ P0 h# O  l5 h1 \# |) U                if (arr[right] > arr[left])
% n  c: i( @0 j2 _) L                        mid = left;
9 J- X" v7 W, o/ D' D- m                else if (arr[mid] > arr[right])
* E2 S+ S! j8 M% E& d                        mid = mid;
                else
+ y3 `+ X5 \: O5 P- @                        mid = right;
        }
7 ^  |7 M. q+ P: N: |* W) ?        return mid;
& }& ~; Z2 o, U% ?7 {}

) ?% D& U, p; m6 Zint PartSort_Hoare(int* arr, int left, int right)
& ]$ u: {& X# n6 S{
        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
        int mid = GetMidIndex(arr, left, right);

0 Q3 I# y/ c1 M2 p' I8 e        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
, {6 F' I- `6 P- O4 v: q# z        Swap(&arr[mid], &arr[left]);
8 N/ ~" X( W4 l' d
        int keyi = left;
        while (left < right)
        {
9 X4 ~2 n2 h! ?/ U, a4 N  X6 @, e* D  ]                //R找小
. g% G. `4 c6 z8 a* U0 F* |: \) E                while (left < right && arr[right] >= arr[keyi])
4 d5 P: N! U: P7 \                        right--;

0 Y! y7 B  I8 S' Y  Q! y. {4 j* I                //L找大
                while (left < right&& arr[left] <= arr[keyi])
- s. D9 `  K' i" j1 G7 V) l                        left++;

                if (left < right)
& O- ~" [* v/ K7 o                        Swap(&arr[left], &arr[right]);
, v, F* p: B" m3 ?7 J/ |: k) O        }

        int meeti = left;
$ x* O; W* Z, U& q6 P* R  C
& V3 i% S+ V8 ^5 E. x        Swap(&arr[keyi], &arr[meeti]);
& k8 A* F$ F( w2 T, L0 T7 ]
7 V' a% I. c: Z3 M- ~% T2 ]4 l5 N        return meeti;
4 m) O4 q( D# q; p% i) [% H}

4 P" G# D* u1 `+ h1
% \$ r; g2 }- [4 Y/ q2
3
4
5
7 n/ Z- @: S" Z1 y. t6
7
2 t  [. J$ l; Z$ ?- }) A8
9
10
11
4 L' F/ v2 k0 ?: E& _9 L: S12
& {9 M9 a7 V1 r# r( W/ L) j13
14
15
) J8 N  ]; {; E, s# t0 Z) M16
2 V- R- H3 c6 A2 I4 h17
7 j) O. p2 Y& f% O" l18
19
! B/ y8 ~4 b. v  v! Y$ }2 U+ G20
& p* G- i+ w8 p6 d( ~- t7 U/ M0 R2 ~21
22
23
9 o# ?( S* h8 a; X- J) p24
1 P' n2 n2 b( y7 \, `25
26
27
28
7 b4 L1 Q: H& h  z: z5 J5 d29
30
; A& ?$ e) C' u) h31
" T' ?% q( N" x; V3 l32
1 b7 p8 z' A/ h+ A7 w$ ?6 C) Q33
34
35
36
37
38
39
, ^" d! W9 h$ q2 g2 X7 H40
41
( _. {0 R1 C: x/ k9 n42
43
& ^- U1 x8 O1 {" E44
45
# s9 J9 t# K  v2 h( [) X' o46
47
" D4 i4 l0 _* A; L! U48
( ?! u- |. O8 Y9 h  K49
' i( i& ?8 ]1 o0 g# v$ B: t% z1 y50
1 s: W5 F* s. v1 k$ K( {. v, k51
52
' n* ]7 R' o8 `8 |9 b53
6 {2 ^, \  j4 k7 M54
1 u" B/ T- \6 o挖坑法
$ Q+ X  p: L# b初始状态：L作坑，其下标存为key
(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
重复 (1) (2)
/ L# T8 j- U- x, x最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]
. ^* @3 S8 @; B& G
5 B! ~! W& Q! l& X
int PartSort_Hole(int* arr, int left, int right)
! `  C$ |6 {, p# r, F/ R, o{
6 }0 w8 K: q' a        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);

        int key = arr[left];
7 M. C* z- e: ^% e& s. O        //L作坑
        int hole = left;
9 _# b  P8 D. P# J+ |; P* O6 z        while (left < right)
7 M1 S0 V5 P* W0 p        {
                //R找小，扔进坑，R作坑
* ^4 ~# E1 Z5 E9 z9 _                while (left < right && arr[right] >= key)
                        right--;
; y7 H2 Z. C0 n( E: m- w                arr[hole] = arr[right];
                hole = right;

                //L找大，扔进坑，L作坑
                while (left < right && arr[left] <= key)
6 e4 y* M3 t7 N/ c) _6 S3 W5 E                        left++;
! Q8 ~. ~2 t9 ]+ r                arr[hole] = arr[left];
4 a8 U* N6 E: I5 S0 S, Y                hole = left;
        }
        //meet
" g( Z6 h. q+ V! @        int meeti = hole;
, l% i/ K6 x7 @3 _& s1 \        arr[meeti] = key;

        return meeti;
3 O: v3 c0 T6 d3 U8 y; F8 m( n/ `}
7 B; u9 x0 d( A7 o4 |9 s
1
5 a; i. n; r: {9 a' G2
2 s: [. N7 G( S0 V; |2 A2 g: L# C3
& z3 O# G  |5 D  w% P4
/ b. p7 `- m$ s# }5
6
/ M2 q1 K4 f/ V7
8
7 s. g$ J; r- K- |' {0 a9
10
11
12
: j( _) m0 U9 R13
14
* p6 E( F3 Y8 H15
16
17
: e  s$ D' v$ _! S2 J6 {" f18
19
20
21
- f) r: K- |6 f, {9 U; l) j22
23
24
25
26
27
28
前后指针法
; S- }! T' l" u# ^) N: m此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多
" L' x1 o) A# n6 V8 P# ]* P: N8 T4 N
cur找小，找到则停
++prev
. X: [& o8 x+ `# H+ e- K; z如果 prev != cur，交换 arr[prev] 和 arr[cur]
! a! c5 Z% N  `# T4 j" x7 d如果 prev == cur，不交换
当cur越界，代表找完，排好序了
prev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低
2 I: ]$ e( X. l0 v
4 u- J7 W) g, }0 Q) R

int PartSort3(int* arr, int left, int right)
{
6 }4 s" y2 J. Y$ p* o4 r        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
5 [. V( v5 B5 X" G4 f       
  //int key = arr[left];
        int keyi = left;

/ E. K7 z/ e  M" r- A! g9 L        int prev = left;
/ M, n" ?2 @- H: a# ~        int cur = prev + 1;
; L; M% h" o! Z2 U" V" N       
    //cur越界：找完小的，prev的左边全小，prev右边全大
        while (cur <= right)
        {
- c2 L5 c( j% w2 m        //++prev == cur 没必要交换
  X7 F8 T; u2 |; \. S% s0 P                if (arr[cur] < arr[keyi] && ++prev != cur)               
$ [2 S- h4 T; Z1 w+ ?1 f4 ~3 w9 H                        Swap(&arr[prev], &arr[cur]);

                cur++;
        }
- G( n( l- s7 ~7 c7 ?, e$ ?! k9 y  I
9 }+ S! }  i; t* p, u        //键值存是的值：
8 h& }2 g6 m8 Q, k. p        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
5 }6 {% S  a* @* {* Y4 E7 O+ |; J0 b        //Swap(&arr[prev], &arr[left]);//这才对
    //键值存的是下标：
        Swap(&arr[prev], &arr[keyi]);
, m8 C2 M, c9 C' p( v
        return prev;
}
% p7 b1 r/ t% `5 ^; @5 z4 W
1
2
8 v6 E9 @+ R) b# q0 v8 W% Q& `+ {3
) X3 Q- b% X. J* j4
5
/ x6 j* e# k( f6
7
8
7 y/ I; C7 ]" ~* l$ X9
6 T7 O+ \. j2 B3 X) N0 o2 K% S2 _10
11
12
13
2 U5 w1 G& c* s& `) B& G7 D14
15
3 V; c8 I! v" L0 _16
17
18
5 s/ n! L# M1 y0 t19
20
21
22
23
24
. `4 r' ]( {3 c/ x3 ]25
3 p# w/ J9 s+ I, C26
' d: r- c( R- [$ D1 K27
6 K7 f) z' B% S5 T8 P( v- U28
" a9 ^# {" d; E. P  H29
- i$ I" w9 ^; a0 g# v6 [整体排序
# b- x0 {' {1 J. R. |9 \5 j; H递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排
2 `7 i4 c0 L; z. T+ @; [
# z2 [  ^. l9 W4 `6 H7 y9 _% Y' S1 W//[begin, end]
void QuickSort(int* arr, int begin, int end)
4 g# b6 I- J: G2 n" w{
        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
        // [begin, meeti-1] - meeti - [meeti+1, end]
                //1.begin > end:超出范围
1 `4 w* M* {" A7 I9 Z4 L" _1 t: T                //2.begin == end:一个数天然有序
    if(begin >= end)
        return;
& W/ ~7 G& ~9 ?9 H1 G. W: H  i5 |
                //排好meeti
                int meeti = PartSort3(arr, begin, end);
7 y9 E& W7 R9 f  f4 L
                //排好左右子区间
                QuickSort(arr, begin, meeti - 1);
# f& s" X. J# F' K                QuickSort(arr, meeti + 1, end);
        }
- K0 L; l. o6 W- ~}

1
+ Z; E8 E" D2 v0 F/ j2
2 o+ {3 v4 t0 `5 }! W3
9 x( }+ E8 Y" v: l4
5
) w3 W2 ]5 p+ w2 i+ l6
7
9 x1 G* H+ z9 m: D6 ]5 b4 q! Z8
5 p) X/ x$ x; S* Z. D2 E9
! y: p, {( |* g10
11
12
% g' N- D6 A8 S* L6 _+ ^% }* y13
14
15
16
17
18
…

没想到吧，还还还还有可以优化的地方！
( u% Y+ o/ y9 @( `0 n
优化小区间


如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序

那什么算是小区间？
5 `& \4 y3 X$ \: N( t
其实小区间没有确切标准，8-15左右都可以的
8 N  O/ z5 h7 v3 j! C- @& J
! Q! s4 Q$ @) b1 M
这里就把小区间定义为 含有 8个数或以内 的区间
( @9 F/ w* A5 m" I0 j2 V5 N# @
//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
$ _4 t0 G2 I/ H' b" [* v) u        if (begin >= end)
4 z, G2 V3 J9 R" |9 F* \# V: _                return;

  k8 G! T! {* H, @0 N        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
        {
2 M$ T7 g2 p5 b; @( t' S                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
) ]1 w) v* \1 P* ^* l                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
  \4 x" r% }, I# ^9 f" M        }
) B6 B+ p. c, t/ X! }        else
        {
                int meeti = PartSort3(arr, begin, end);

% R/ W0 d/ y& p8 {: |                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
        }
}
! ?2 O) ^; ]' @$ A$ z: w
! Z* I1 i$ z5 S- c: }4 y1
7 O# r% L: p6 F- h2
3
4
/ X! ^5 P. ~$ W9 V: g3 H9 q- U& K5
6 E* S0 _6 c/ t5 [5 ~6
: l6 ]$ G; G  k( l; y3 V6 `7
7 z0 Q8 G& H* [/ Y8
9
10
, p6 v4 z. G0 i7 _/ E. o11
12
% b: K2 s' ~( U8 S! z6 q0 ~9 P# c4 S13
% i& Z( P+ x6 }4 t# s7 H14
; w+ N! d7 {( M: d( a# e" C/ i15
! C$ e( h8 ^  w* f% f, t8 q4 o8 N/ V4 X16
2 u" k+ X1 b7 i17
$ u2 k# \* a2 e/ v0 c) ?4 D3 Y18
19
快速排序非递归
为了解决彻底递归深度深的痛点，我们来试着把它改成非递归
; |" I5 G! e- I9 p) C: s
' g( ^9 u- Q* j思路：
递归深度深，栈的空间又小，会栈溢出…

那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！
; o3 l( P5 y7 E8 b& b
核心思路：在堆上创建“栈帧”

* c' C7 g; J) A& Y" }快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的
5 p5 |! |% v2 I

2 g# `5 v7 S# |
在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：

先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
. o% j6 K' q% x, R+ q, o% A先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
" G$ f; N, g) B& u{
        ST st;
        StackInit(&st);
       
- Z4 q% Y, K# L/ T  ]    //先入begin
        StackPush(&st, begin);
; `+ Z/ y7 o+ x# A    //后入end
; v. Z* ]/ R8 }        StackPush(&st, end);
6 B3 c3 z8 O$ q9 V2 I
' z% D4 y1 C) U  E4 c7 U        while (!StackEmpty(&st))
        {
9 I* X) w, g3 C                //先取end
                int right = StackTop(&st);
) P; L- V4 ?- f. P                StackPop(&st);
3 U& z5 H$ W. t' _! g  C+ @) M                //后取begin
                int left = StackTop(&st);
                StackPop(&st);
( B* _& }  S0 M" m
. r: s: h1 X" d& r) w7 f* I2 Z& I* l                if (left >= right)//1.只有一个值  2.区间非法
/ ^3 P/ {+ n  h& K$ C; q                        continue;  
                               
                int keyi = PartSort_Pointer(arr, left, right);

                //先入右区间
2 T0 \) a' J, u, ^                StackPush(&st, keyi + 1);
                StackPush(&st, right);
                //后入左区间
1 ?1 s7 Q0 P; j$ b8 \  f; w- p$ Y6 A                StackPush(&st, left);

                StackPush(&st, keyi - 1);
2 I+ }8 N% Z9 k        }
. ^0 P: S# Z. B) \0 l
        StackDestroy(&st);
}
3 E8 G% z6 e! O$ }6 ?/ s
1
2
3
' G7 `9 `/ C2 P$ z; u4 C0 w$ k4
4 M& G) ~* ]9 l, X$ b5
  {- q6 V. r$ \# v7 Y+ ^- k6
7
8
: `  M9 G* r  a- F9
8 M# N# X; H5 I3 g6 J! v6 P* _10
% j! t( [: L$ s! T# `' T& Y11
12
13
14
# z! y) E' q/ f. d15
/ W- {: ^+ z! @5 e3 i/ v) b8 N16
# w6 U0 [: X+ @% v% I) B17
- S$ j' l$ c) V18
: R$ V9 V1 A( O9 P19
20
# f- z$ }4 N% {$ b21
5 @+ g, D  n. r! ^* [/ k& ^1 U22
23
* B! A( z7 h2 k! q; ]% Z24
% z9 h' R" M4 E25
26
27
3 g; h5 y, G* G7 R. Y28
0 Q7 l+ y3 s. Q3 d( p: h29
( n, m- G% a" J0 v. G( Z30
31
32
33
34
35
) f, C1 v1 ^. D9 n$ t3 v数据结构栈的实现可以看博主之前发的博客
9 z5 ~. `% u7 z" h1 b" I

: w5 Z' N& ?9 d  F, c归并排序

…
# p2 G9 V! o6 D5 n/ X- V+ U2 Y5 w; ?; X
性能测试
void TestOP()
{
        srand(time(0));
+ G' n7 }8 y# |( @9 v        const int N = 100000;
6 s% ^, a" W. ]+ m) \& r) Y9 v        int* a1 = (int*)malloc(sizeof(int) * N);
! V0 T& W, c% }8 g) Y( Z: y        assert(a1);
        int* a2 = (int*)malloc(sizeof(int) * N);
# p8 b# H: N! I" ]& f- R* `        assert(a2);
        int* a3 = (int*)malloc(sizeof(int) * N);
        assert(a3);
        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
, w8 e' P' E5 R8 w6 ]' l        int* a5 = (int*)malloc(sizeof(int) * N);
$ A) X' ?9 V6 d+ }        assert(a5);
2 F4 |2 `- }9 v
        for (int i = 0; i < N; ++i)
5 G1 q" U: p  F; P* ?- E; ^        {
                a1 = rand();
2 ^! S' c& |: G, ~* p4 q7 ^6 T2 W                a2 = a1;
& P2 F3 i5 g" ^; |2 Z1 V+ @* X                a3 = a1;
                a4 = a1;
                a5 = a1;
        }
! W" z) s: I" z$ q! J2 a& }) t
" r  P& W0 }2 W! a        int begin1 = clock();
        InsertSort(a1, N);
4 \% ]- [7 W) n( L6 W. L4 i4 b        int end1 = clock();
4 T- c  N. j- {' Z" ]
        int begin2 = clock();
        ShellSort(a2, N);
        int end2 = clock();

        int begin3 = clock();
        SelectSort(a3, N);
, X) ?- L) R# v1 J4 j$ `        int end3 = clock();
8 L3 A" J, ~+ }
$ V( l8 O  F* a& f; x        int begin4 = clock();
        HeapSort(a4, N);
5 P3 ~# s- F. t7 \4 p        int end4 = clock();

        int begin5 = clock();
* H0 g6 H1 M2 a) b/ x        QuickSort(a5, 0, N - 1);
; L( T. ?! k2 i% {  |$ [                //1.中间key
! I+ X9 `& M1 O& D' U( b7 w                //QuickSort(a2, 0, N - 1);
                //2.三数取中
                //QuickSort(a2, 0, N - 1);
# {1 y( r3 Q  E4 t                //3.小区间优化
                //QuickSort(a2, 0, N - 1);
        int end5 = clock();

' p5 {- S/ H) l$ E. s2 Q
        printf("InsertSort:%d\n", end1 - begin1);
        printf("ShellSort:%d\n", end2 - begin2);
        printf("SelectSort:%d\n", end3 - begin3);
( D: g0 {. y& S. ^! C' G        printf("HeapSort:%d\n", end4 - begin4);
& e0 k, Z" F# x, ?* |& x5 Q) \8 I! c        printf("QuickSort:%d\n", end5 - begin5);
; y8 x6 C/ a2 l- O5 _
3 d5 L  W8 z- ]1 C$ }        free(a1);
        free(a2);
        free(a3);
        free(a4);
        free(a5);
: W2 F  I$ ]) w; Y) p1 m1 \+ g}

1
2
3
4
, j- j% q; `  G- X5 Z5
' B5 h6 t/ y- E3 d& N3 r+ V5 S6
, p8 w/ g* G! N+ e* j8 H7
8
9
10
11
12
! k( j7 H& G0 \13
: O/ N* E1 k/ y( x9 D$ s14
15
16
17
18
8 O. t8 e) b/ U+ J5 _9 ~19
20
4 a4 x. Z% n0 p4 }8 m% i21
8 X% n& o6 n# w* h# C4 J22
! D9 q, z. w% O& J/ T3 J23
. V1 s6 L4 ~* k24
" R* u& j! x; Y25
8 U) q: X0 I3 \; j: V$ T' c26
0 a+ @5 p# J" [0 _- w, B2 ?6 K27
5 Z0 z5 s- s2 k' x0 H7 B( {+ \28
, J7 d0 u* J/ q# {. e7 c' l% k29
30
31
32
9 m: E2 g; p5 V7 N3 S1 w33
34
! u7 D  M9 }7 P1 s: F6 T35
6 Y( L9 ]! N( L% l6 j36
( ^* C6 m% V- P% j37
38
39
4 N: x$ q% d6 S: M40
: G+ ~" l" o( ~+ L' \) s& \41
+ H& {! B2 y) q' ?0 q2 M  p+ e42
* r$ w  H  k. V; W$ k43
1 f% V) ]# b9 h" W44
45
5 l" T3 n; o* ^9 ~9 L3 ]% [46
) g1 e; g6 ^2 k3 `: N3 Y) g8 T7 [47
0 D% c( [$ o6 O! g5 r' ?4 Y48
. H) x- d# E# J+ c& D2 I/ o49
50
51
52
53
6 ^' f3 Z  x" T" t54
5 L+ @! d* e+ u6 R55
56
57
58
1 H7 R& _/ M% s' z59
6 U+ h4 B+ L( z60
61
' u. u3 c2 ^" ^" G) w1 S  Z5 v62
63

* L* ~5 y) t9 n* F: B9 q; @
8 m. F/ X' i* _8 d6 X. C不愧我们费这么大劲优化快排，多帅哦！

: M% `- q5 m. S! f; Y: {5 K/ K' U, t8 o差一个归并排序，后续补上！

不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
; n7 v8 i. H  l0 S/ W7 h. o————————————————
版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
- u7 `, G; N! @: E  `# s5 J原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832
, w/ }. C; m. O: O0 w

5 m! X$ [+ _/ z8 n+ X$ X