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

杨利霞

【数据结构初阶-排序】经典的排序算法，很有趣，有没有你不会的呢
" t( n: b! O, ~  `
8 X1 u: U: k# f+ A! N% O前言
本期分享经典排序：
; h6 }1 W2 h3 Y8 W: N0 }
4 Y8 ~3 @% J5 ?插入排序
直接插入排序
希尔排序
选择排序
# `1 r* X5 ~2 D# k" L1 j" |9 h9 Y直接选择排序
% c) n( ^$ g% ^$ `- s# D/ U' L堆排序
交换排序
4 ?/ M! s+ L! v/ I冒泡排序
快速排序
: q$ L  ]# [0 i* n) ?  q! Y. E注：讲解时默认排升序
% P, o; W% f6 A/ k. Q; v
0 R' k+ D4 x) ^( v1 q- t8 J4 I; r2 m插入排序
# W+ s% ~# Z# G9 f/ O- R  e- n, y直接插入排序
* r# \1 B9 G2 V: M! i思想
" m' F3 s' s! C  T. T! o+ I9 j插入排序，就像玩扑克时，摸牌的过程：
. P3 z( ?: f/ P
最开始，左手没牌，右手从牌堆中摸
; M$ Z/ n: `2 [右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
1 m5 M. r2 f% B& y如此一来就能保证左手的排始终有序，摸完牌后也就排序完成


  ]; h1 {9 X9 w2 s8 w" l操作
' C& J6 S/ t- }3 Z, q% a设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
单趟排序：
每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
是正确位置：插入
不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
) V# G2 d& u3 u4 Z) E整体趟数：
6 v. D( U. r5 C: `- `若元素个数为n，需要排n趟
void InsertSort(int* arr, int sz)
{
        //end + 1 < sz
        //end < sz - 1
        int i = 0;
        for (i = 0; i < sz - 1; i++)
        {
7 D; H' O9 T6 w+ z: O                int end = i;
                int tmp = arr[end + 1];

                //找插入位置
$ t6 P' k8 q  G! m* N$ Y                while (end >= 0)
                {
$ u+ _- x" Y2 r                        //不是插入位置：当前数据往后挪
+ u' p. m) g( R. Y1 Z" R- G7 ]                        if (tmp < arr[end])
1 e, |2 i2 k& I! q0 n                        {
                                arr[end + 1] = arr[end];
                                end--;
                        }
                        //是插入位置：跳出循环插入
                        else
                        {
# e: u: N+ v& N7 }% e& @                                break;
3 r" p0 b/ [! @3 B% {6 ]. W                        }
                }
) B4 Z9 T' z% T2 q2 O8 S- Z                //插入
                //1. 插入位置是[0]，end == -1，不合循环条件跳出
! S0 M+ v: r! `* s                //2. 找到插入位置，break跳出
                arr[end + 1] = tmp;
4 h( c4 R2 W5 U3 g' W        }
) ], U1 k8 l9 L  `7 d0 H}

2 T  \/ R5 \% w. _2 J" D' ]0 F7 p1
2
3
* d9 n' |6 H# L1 M2 P6 G1 d4
2 f4 k% n9 A; ~5 c2 P3 ]8 A5
6
5 K* d- u! N, m7
8
/ L( f8 {" N- e- \; D9
10
( u, M0 B7 P! N7 }. w11
$ Q# @0 b+ _$ ?7 E12
  Z4 A% O+ @2 @) h9 b4 @2 ^13
$ A2 L& O' h# ~, l. p) T14
6 ?3 W2 P; K- b15
1 w3 D7 U4 k) E( L3 p16
: t" O- p6 @4 `7 J; ]4 N* F- h17
1 w- p8 K; v! F18
19
  l- i( f# G% l0 D2 B20
& _8 E2 Q9 Z- L4 f4 r8 U; Z21
22
* v5 ?; x9 @* f- w23
' C2 U) z: f1 w- c9 `24
6 f6 i8 o- i7 }8 |0 j) L$ o25
# Y5 X; B( \7 ^0 _26
) m- f0 p" Q6 D27
28
29
30
3 I% t# X1 k0 B0 {0 R& O0 g- n31

0 m3 Y. c9 ]' S: s
) o4 |9 I4 [7 g/ f* E7 j, L8 ^( }稳定性
插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以

4 q( Y  y% n. h) I直接插入排序是稳定的
, R3 h( F* D6 o) |8 D0 A" c9 v, s
复杂度
4 d. j' G; q* I" g/ |% d1 `1 y时间复杂度
8 p6 W+ L: J4 m9 o  \6 n* ?( o2 Z最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）

O(n)
6 }5 [6 D+ o/ h% B) x
, L8 D' Y, H, s5 w最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2
2 J# v( R* s0 s
O(n^2)

; |, g0 |, d- t8 X" l& O空间复杂度
O(1)
. @; \- n5 ?! w; D- s9 g- \
希尔排序（缩小增量排序）
希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序

优化思想
增量gap不止用来分组，也意味着数据移动的步长，所以
( P/ m) @: ]- m" _" D
gap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高


4 T9 T: A+ j" M1 n6 o% i* m2 U操作
* v2 s: D: X' q+ W单趟排序：

设定一个不断减小的增量gap，也是元素移动的步长
* u6 _0 y9 ?/ o3 ]8 [& l7 N以gap对序列分组，并对每组分好的序列进行直接插入排序
不断缩小gap，并排序
3 P! l' b8 z9 u*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
整体趟数：

由gap决定：当gap = 1，排序完成
注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。
1 D. C6 [) h0 Y. I4 z0 J8 \. Y( O! z
void ShellSort(int* arr, int sz)
{
        int gap = sz;
0 c) `: K( e. d       
- {9 L+ M1 m0 s  j8 p( g& Q    //gap > 1，预处理排序
    //gap == 1，直接插入排序
0 @! V0 X, S$ _- F        while (gap > 1)
) M. r7 Y4 A/ r, Y1 U. e        {
6 E0 F( ?% Z0 C7 Y7 N6 i                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
                //gap组
' y: v4 W; n7 G& U4 E6 Q                for (int j = 0; j < gap; j++)
& R6 I2 w# z. o                {
            //end + gap < sz
& c& A6 z. O# P                        //end < sz - gap
                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
* ~$ S5 e1 A* y* b. e                        {
                                int end = i;
                                int tmp = arr[end + gap];
& `' `+ `% }+ _5 Y                                while (end >= 0)
                                {
                                        if (tmp < arr[end])
. f5 S3 r4 T2 p. v  L                                        {
% T' n4 R3 E. g                                                arr[end + gap] = arr[end];
6 @! W4 h2 h% y! U; I4 R& t                                                end -= gap;
                                        }
$ @! m% X. l5 L% J                                        else
                                        {
                                                break;
+ ]4 b4 v+ S, _; r4 f5 Z                                        }
9 w$ s% L( ~( x: }0 D                                }
& k8 p. W2 |! n) s0 v                                arr[end + gap] = tmp;
+ U7 @0 X4 F( V$ ]+ H  s+ F                        }
. I$ v7 p' `4 w$ P+ q: D                }
        }
- W& \) s7 `; P}

5 a7 m7 B8 q' {7 I% d1 F1
3 [7 L% y7 R+ P$ _/ c2
1 V5 I0 @8 [& U+ o% B) I# v: K3
3 E/ {/ n3 ^& D  H) r* |4
5
6
+ t, B  ^# I' u1 W- U2 Y7 G5 J0 n7
8
0 t4 U* q6 n4 t9
10
11
12
1 H% i) |5 B* c( ?7 g13
6 r. n+ F( n4 E  y5 B" ]; d) ^* j14
15
. ^1 m" u. V. y1 R( o, Y- Z" k8 P5 d16
17
18
' H2 @" S, x; m. X* @) @19
' z6 h' d& x" ^/ r20
21
5 Q( {( \; C! y22
* N3 d& F! B1 _23
24
25
3 T8 R2 B/ E$ U9 D1 T1 \3 x) Z" `26
1 J  T( R% J. T9 z& w# `" X27
2 a6 E9 o1 t) g" [$ G) J) h! }28
29
30
31
32
6 D6 v! I+ \' z7 V" I/ b; Z33
' ~1 ^1 |0 h. o8 u: {1 v34
) T, i+ F3 \- W( N0 f. K35
其实就是套上”缩小增量“的直接插入排序
, ^; }+ _1 R/ k
2 K, L: P8 p) v, U7 ^; P, k& n
3 |& u# h8 r7 l1 C6 e5 _稳定性
& C! t/ U: q$ B+ ^( S7 J+ g我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以
2 s$ _) W* c" E) d( n9 S! L/ A
  q1 ?, [. T7 s+ ?2 H. [# y3 f希尔排序是不稳定的
* m' D8 e: q  [% d
7 l% y5 R  |9 e9 ?! a* j7 Z& P复杂度
5 L& Q) [& n+ L时间复杂度
希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
! D# o* L) [4 R* X- {0 I/ [
O(n^1.3)

空间复杂度
O(1)

选择排序
2 J$ J. T) f, l* z3 @& V直接选择排序
+ \6 y/ b! a  |) k9 a; l思想
选择排序，遍历序列，选出最小的元素，交换到左边
8 a$ s3 s8 y8 y/ R
# s4 x& j- E1 T; l# t

优化版本：

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

- \; Y! x$ ]$ i# D+ q6 c5 o* g操作
设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]
$ Z, c7 m0 Y2 Y+ u& b( I/ @% b3 v
设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标
' B5 y0 B9 c; J
5 A6 a4 c# ?" ]2 E单趟排序：
. {: I1 P0 o9 E! q( t' @4 t' S
4 B/ {+ J5 I6 O+ s遍历选最值的下标
% M! d$ b' k7 x7 R交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
" t* O$ K) s4 m0 p) m- w7 D3 Y（修正）
1 p8 u/ D. x) q: x整体趟数
6 j4 h4 C3 w5 v) Z% j
/ Q' t" B) S3 e. M! c, C5 v: f( {' ?; a若元素个数为n，趟数为 (2/n)
  R' |5 f% b% F" l修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标
. s, P# k; a6 `- P5 ^
8 K' k  F0 Q6 R% w  Vvoid SelectSort(int* arr, int sz)
{
* Y  P9 b4 E) p& Q, f        //闭区间: [begin, end]
# r  z% ]7 b$ U5 X        int begin = 0;
        int end = sz - 1;
        while (begin < end)//begin == end 最后一个数，天然有序
: ~# e' C% J) P( q* L3 B        {
                int mini = begin, maxi = begin;
                int i = 0;
0 H. Z& }  n6 w$ Q5 |+ B2 b                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
/ P7 }2 B* Q' s9 y                {
                        if (arr > arr[maxi])
                                maxi = i;
                        if (arr < arr[mini])
                                mini = i;
                }

                Swap(&arr[mini], &arr[begin]);
4 l+ \1 y" J) e* W# K! B0 ]% S
                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
0 }# T7 y0 l% D9 Q% v4 S1 H                if (maxi == begin)
; S. S, k. \, l  a2 Q                        maxi = mini;
                Swap(&arr[maxi], &arr[end]);

/ Q: b2 Z0 u8 k- q; ]2 c4 N                begin++;
                end--;
! Q2 T; K% v$ y+ h' m        }
) k' n3 V) E. T0 T1 x  m}
/ C% J$ X& d0 M& Q6 ?( W
0 m1 `7 g& ~" L/ j! D1
2
3
, v: M/ Q$ S% o5 A$ I4
" w; p- Q3 ?$ O  ^5
2 J% T4 j& I* e# Z3 q: X/ v6
7
8
$ \3 q8 v. v/ P3 c. j3 Y! f9
10
% ], ]) P3 R% v  e- t7 N& K6 ~11
12
3 I. G8 B5 t7 s5 T/ {13
8 c' U# k5 H) C' n: @5 a( Q2 y# M14
( f8 _% K, \2 [" L15
- a" E4 f5 ~; `& [! H4 Q- w8 W2 x- W16
4 X3 U( u+ h% }+ o17
2 T* g, j# u& I5 S# d) j' t) o18
, f" U  z) B+ _2 w; W19
1 w: n  u" o2 Z; w' J# ]+ ~5 n: j20
8 K, x% d% U, f3 v+ \; ~21
22
% k. S& S; n7 |& a% D23
24
9 j6 [+ F9 p: S  ^) W4 }25
26
! S1 F, Y+ ?2 H3 x6 e; Q9 M% u! g" q( ^27
6 Y+ W) w. r: Q# c/ O0 c8 p/ Q8 q; V5 g28

# v5 G, Y7 q5 K; z; K+ P* \9 j* Y/ d
稳定性
选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以
- W* ?* `6 X7 o& ~0 @! y5 x
: F+ ?. A% o% d$ l% `! O" S选择排序是不稳定的

3 k( k+ G0 \$ D) Z复杂度
时间复杂度
最好：

2 ]& O( o4 p' w' `2 |% \5 Z比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2
4 p; |; O& P, F  q
交换次数：O(1)，有序不用交换
. d, H+ p, v: S0 Y) x
3 N: L7 I0 Q. q" Z: `; TO(n^2)

7 S% ?( V% h3 C3 J! V5 k+ H8 f最坏：

比较次数：O(n^2)
% L# K+ E/ j  ]4 o! ?9 z
交换次数：O(n)
! S6 c2 A6 o) [; T' }. a' ]
8 O4 e- S! i  j& m0 r; Q# V2 KO(n^2)

* T% F6 O9 y9 F. m5 B4 g# q% q- Y空间复杂度
: _: |7 T' Q. s* oO(1)

, d1 ]( m& R4 f- Y5 s8 X堆排序
2 ~1 j0 j% P4 x, S# e思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆
9 F: U7 p# o$ W
+ t3 ]( {3 @4 E  `+ H# }, N, o, n& m$ D

( T, X; ^2 Z5 z( S5 h# d/ p: Z操作
建大堆
单趟排序：
选堆顶和堆尾的元素交换，则堆尾的元素排好
: w! \5 Q, Q9 S每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
$ F8 [8 i) w, [$ ^9 o$ U整体趟数：
若元素个数为n，则排n趟
* n4 e9 k+ L, |. D, @; w. Dvoid Swap(int* e1, int* e2)
{
        assert(e1 && e2);

8 {7 n+ m' ?( D0 A, M        int tmp = *e1;
        *e1 = *e2;
        *e2 = tmp;
8 J! W7 T/ L: a1 C8 S5 c9 Y5 z: B5 T}

* ^) |0 |4 B1 c# evoid AdjustDown(int* arr, int sz, int parent)
  h: T$ P) J9 y{
        //建大堆，排升序
0 J3 n6 X( \$ K8 g4 U        assert(arr);
       
    //默认大孩子是左孩子
, i: E* l5 }2 O        int theChild = parent * 2 + 1;
        while (theChild < sz)
7 Z: m: n3 r& [. @5 }8 n3 T        {
        //如果大孩子是右孩子则修正
                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
( [% o1 A' O- j9 c; V                {
                        theChild++;
                }
3 V8 u6 D+ u; g8 y                if (arr[theChild] > arr[parent])
                {
                        Swap(&arr[parent], &arr[theChild]);
* b5 D1 ?" B0 k3 w2 |9 Y            //迭代往下走
                        parent = theChild;
' l1 h$ I( ^- J+ d8 J8 P                        theChild = parent * 2 + 1;
                }
                else
                {
2 b; U1 e+ f7 n                        break;
                }
        }
}
$ E) e7 u% e& L# m! `
* s4 a) C% Q  D2 a2 c& uvoid HeapSort(int* arr, int sz)
( W2 i, `# c8 |{
        //1.建大堆
        int i = 0;
$ ]/ }/ `8 D& A        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
        {
- C6 `, @$ ~: t. I/ Z) m                AdjustDown(arr, sz, i);
! K/ |; z" p/ ^' v; a, c        }
  k9 T! @4 Y4 s3 V1 S3 L- O
        //2. 选数
& x! t8 I+ [, |. b7 \        i = 1;
  z! X/ i3 T: A' Q4 v        while (i < sz)
- b& v: i! h- p4 y9 V8 V        {
                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
                i++;
        }
; V, J3 T) t; f. d}

: N& A* y' M( a" a7 a1 K1
2
3
- K; W4 u- c4 ^" w; {4
9 J3 _0 u8 X2 e2 i; Q5
3 k# C: x1 K3 n. z2 D6
. X) }$ m+ g6 f- ^6 t+ y7
/ ~4 m, \  Q2 [* M9 B' E8
* G1 |2 Y2 G4 w& g% r; n9
% Q: Z# H* A- @3 b- ~0 z6 y10
& f: ]6 }# \- \" S/ H. B& k: ~11
12
8 t( f2 u: y- G. D! W: L- G& c1 I13
14
15
16
6 V) V! O/ c  Q- ^8 Z17
18
19
20
21
22
23
24
4 }6 v( L) g$ S7 |25
+ W" i9 R6 i! y- o7 F26
27
- v0 ]" E4 U! P0 C. p  p" u28
29
: J1 M- W( h7 I0 a5 \7 v6 G30
31
2 w$ F7 l+ A/ m, C% M8 P32
33
/ t2 c+ ~$ X/ ~$ W34
35
36
5 \# h% w- m8 h0 t, b6 n4 h37
38
39
40
41
42
43
44
: Z( z% }4 x2 Q7 ?( ~# v45
46
47
48
49
9 d1 A& U* s+ `6 c  K) U50
51
* U* h" K8 l, X5 }5 C4 v- n" f, n52
9 y* x6 J+ R2 X! ~7 `53
# @& O: J+ X- B54
55


4 o( J2 m3 t. ^& k/ Z稳定性
建堆和向下调整都会打乱元素顺序，所以

堆排序是不稳定的
8 ~& [4 ?4 A5 J- U9 j5 `, u
. d9 Z2 X% t) h' ?/ t复杂度
时间复杂度
单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为

4 I* k( H9 f6 o# O% V: ]O(n*logn)
+ n2 k- Y" V' M" `" L& S
空间复杂度
' c* y- U4 B5 Z3 Z- X* I, R原地建堆
* v6 E6 K5 {( f+ A5 C1 f
O(1)
. K- ?3 y5 u+ r% `" A
& b/ v" }' ?  `' R- t3 T交换排序
冒泡排序
思想
冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素
: y% b" X: Q' n0 W) S  ]# p  y
3 p& q- g) u2 Z1 @$ e) [

操作
单趟排序：
每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
每趟排好一个元素，所以需要排序的元素每次减少一个
4 Z# `- o6 {2 e- Z整体趟数
( m( W! |: A" K& b) d! ?! e若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
# B4 `5 z& M  s1 E7 l' h( X8 tvoid BubbleSort(int* arr, int sz)
, Z7 B* o  \5 m, s3 \{
        int i = 0;
/ ]& I3 W0 \# y" \- Q  j  \        int j = 0;
# @7 y/ l5 p% r4 v$ w- f        for (j = 0; j < sz - 1; j++)
% G3 ]; z0 q9 C9 a. C        {
                for (i = 0; i < sz - j - 1; i++)
8 d4 {" f% t6 F$ z# {                {
/ D2 h) y6 S) T8 _                        if (arr > arr[i + 1])
                        {
; u, h0 j: O- ~% L" r7 ~& L                                Swap(&arr, &arr[i + 1]);
% v5 e* D0 \- D3 J; Q                                flag = 0;
                        }
. G. X3 v4 B. R. Q                }
* D- [/ O5 n, \- m  M; n        }
}
1 P+ @1 m. M. D* G
1
2
3 Y; Z! H% b% l3
% H$ i3 u% k+ x4
5
% k. r8 I% M1 Y" T* F0 X6
0 i4 s! _: `8 J. ]( @( M' o7 i6 M  ?7
" B, X% X1 z) y- a0 q8
9
  N1 S3 S+ M9 w- Z4 F  p. {10
11
12
1 z9 s* e; s+ t/ M1 E13
6 }: o0 D  j; W0 i3 n3 {( C14
15
5 ~. z9 ]: D- C3 s- j16
优化
当遍历一遍发现序列有序，直接跳出
) D/ p: M2 B3 F6 H; }, V% y
0 ?  J' }3 a# y4 Q* T* B+ qvoid BubbleSort(int* arr, int sz)
) V& F& h, c; o4 W3 _) |{
        int i = 0;
        int j = 0;
# C& ?4 L! X# f3 d9 g        for (j = 0; j < sz - 1; j++)
        {
                int flag = 1;
; O! T3 I* x( g, ]5 |                for (i = 0; i < sz - j - 1; i++)
! I; z' u5 q9 g/ r/ B                {
6 u% ?! b) T) b                        if (arr > arr[i + 1])
5 D" T( N* _4 k1 V- Q. K1 ^% [& F: u                        {
  U( S4 u) f) Q                                Swap(&arr, &arr[i + 1]);
                                flag = 0;//不是有序就置0
9 V! h# U& e8 x: b: O" k                        }
                }
) L; ^- Y* \* X% S" E3 Y, X                if (flag)//如果一趟下来还是1代表有序
                        break;
        }
}
4 v) \( ~: B. k; Y- t' g; C
6 H5 l, V9 p, Z5 u, H: ^1
3 n9 N& F8 v5 d2
' I7 X$ s2 R7 \% `- a4 D3
: e/ y1 _0 _, m, V  _( C$ P4
- t2 J4 ?* T! x4 C/ T1 J# @5
6
$ r; w$ p) P3 M8 q  X% \7
8
9
10
11
12
13
8 u3 j# t/ I0 V14
7 |  X: Q6 u# l7 K7 U0 \9 O15
. {9 k6 j+ U: t5 z5 Y8 c) Q8 Z& T16
4 @; ?; b- @+ c. c17
3 X" h- ~; ~' |  S* m5 n4 |18
19


4 A: C$ K9 \) W, z) g# b稳定性
相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以
0 B/ g# E6 k# R
& l& ~) Y& r2 `( D8 o8 ~  F) M0 F/ s! `+ j冒泡排序是稳定的

复杂度
时间复杂度
最好： 当序列有序

未优化：
: ?8 p+ X: f. c& Z
O(n)

优化：
# P. ~. R% b0 }: a* v
4 @$ ~, [9 q" M! ^! HO(1)
% s8 ^* E* I  L4 ?
最坏：要进行 n-1 趟排序，每趟交换 n-i 次
. |! p3 O7 A  O% k0 x
6 k4 k7 p- y$ k* ?! g; @! HO(n^2)

; C: f/ ^9 L5 q) q( {9 i空间复杂度
O(1)
  r6 m0 d+ H. P) _  \4 a8 \
9 P) Z7 N: c' x. Q, I3 X快速排序
思想
) n+ G4 E/ |% r分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。
. X* |1 S7 |& {9 s) F# N( u5 f2 A* M& p
/ y4 {3 Z. |5 ]8 e8 _所以快速排序可以用递归来实现

操作
有三种单趟排序的方法：
8 t; ^0 m3 H3 T0 y8 z9 z: `
Hoare法
7 t1 x& |5 M2 t* B设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间
5 Q& h3 c9 ]% Y* C3 S- g9 ~( z
左下标 L = begin，右下标 R = end
5 M$ l/ E" J) S2 M( s
设 L R 相遇位置为 meeti
3 \- h1 i, e4 o; y3 T
​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”

9 L% l8 y" ]+ s​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“

- Q& S1 m! ^: k选 键值的下标 keyi

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

找到则停
遇到L，则交换 arr[keyi] 和 arr[meeti]
L找大
7 o) ^* {! |7 d2 n$ H
找到则交换 arr[L] 和 arr[R]
$ t/ R. {6 M# l7 ]' Z6 E8 L遇到R，则交换 arr[keyi] 和 arr[meeti]

, b* p3 q, J- p& J
解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
答案是肯定的：
# C% K* {& Q) Q! `5 L

8 H# h/ w: i& J: w2 l
" K  z2 Q& U0 T
3 K, \: A5 N/ b//[left, right]
; p+ ?9 \' X/ A, b' S. B6 N- mint PartSort(int* arr, int left, int right)
# Y7 r  N$ w. ]{
        int keyi = left;
        //相遇则排好一趟
& q6 Y5 g1 @" `/ c) U/ u        while (left < right)
        {
                //R找小
        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
. ~* G/ {1 e' p1 i# D        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
. U$ _* e# o5 }( n3 W- d                while (left < right && arr[right] >= arr[keyi])
                {
                        right--;
7 W0 u% t) W5 J5 B                }
3 K! q* C9 ~: z7 g( h& \
                //L找大
                while (left < right && arr[left] <= arr[keyi])
                {
                        left++;
                }
) J7 h$ o4 f2 ^! L6 {               
        //相遇就不交换了
' P7 L7 ^/ a" R                if (left < right)
9 `5 I: M9 f6 q2 p                        Swap(&arr[left], &arr[right]);
. \+ e  V0 p  J2 [# d1 H- p& i        }

6 W7 ?) n+ s* Y- n        int meeti = left;
, V- O" D6 z6 j
        Swap(&arr[keyi], &arr[meeti]);

# v. y+ T) o1 k. _8 R        return meeti;
! W% G' O) R2 D# H2 m4 d}

& \3 n" G6 O0 N1
: h+ e' x( N5 r9 R2
3
8 W& _# w: D3 J& {4
5
/ v5 V: g: I: J; M6
! Q7 _9 N& Y5 y1 i, K. G5 D7
8
0 E1 Y6 s8 s+ r* q4 p; H1 K9
" L: y0 F2 D7 z) v* L10
11
12
0 B- x; `+ R! C: v8 c$ n6 }6 ?13
14
15
16
17
7 N6 J5 Y0 |$ T4 e18
19
20
21
22
23
24
25
/ Q: }  a  o! L1 e6 o26
27
28
29
30
$ ?, B3 f7 j, P7 j3 k2 {& M! p31
  j2 ]+ B2 t) M# u9 _/ P& w32

6 U4 e/ f; L9 Y3 a! r- D- W- Z  L' }
解惑：为什么key要选左1/右1，选中间不行吗？

1 r# u" I* x. I0 A
* W# _4 s$ `% c0 k$ a& x: n可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深
: F  e1 @8 c9 S  ]5 m* e7 }+ D' ]9 G
* o9 ]" N) p+ b% k* n" m& C
3 a" q$ w6 s# \7 f# q  T; q) V  d
0 X- R/ u2 r$ t: X
非常容易栈溢出，怎么解决？针对有序情况，优化选key

优化选key
随机选 key （是一种办法，但是不那么彻底）
) @  z) P) `% Z& p选中间位置作 key
解惑：那先前实现的单趟排序不就失效了吗！
：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑

解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
- q3 b# }( i; ?9 R* [9 {前辈给出三数取中的方法

三数取中
在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
( m( a# x/ J# o. f' ^8 P这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
优化选key后的Hoare单趟排序：
" V' h7 F1 T$ M- ?; Z& i9 P
) S2 `8 W& G$ A5 z$ {int GetMidIndex(int* arr, int left, int right)
{
( M& |6 `1 V; f9 a        int mid = left + (right - left) / 2;
5 |. d  k/ R  F* M//  int mid = rand()%(right - left) + left;//增加了一定随机性
        if (arr[left] < arr[mid])
        {
0 c4 [+ x( k7 W& X' v7 ~' M                if (arr[right] < arr[left])
                        mid = left;
                else if (arr[right] > arr[mid])
                        mid = mid;
9 v: k" H. I8 v5 ^0 J  m                else
* y5 o7 ]  Q" y# m; ]  s                        mid = right;
        }
        else//arr[left] > arr[mid]
        {
8 V; C" Y4 d7 b                if (arr[right] > arr[left])
                        mid = left;
7 ]& F+ B/ i5 k# [0 R2 ^                else if (arr[mid] > arr[right])
                        mid = mid;
                else
! i- y, k; ^$ J  O) Q                        mid = right;
        }
! I: V& C6 ?+ w- x0 a        return mid;
}

int PartSort_Hoare(int* arr, int left, int right)
3 J. w8 H0 X8 Q1 X. Q{
9 `) w% K; T) d2 |( e) `) R        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
( M  k: J9 j8 L% A- e  C        int mid = GetMidIndex(arr, left, right);
5 p1 U! ]% h" j* B" J* b! s
% u) t2 y, \6 a$ M/ u- k5 X        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
        Swap(&arr[mid], &arr[left]);
; j: ^- y" D3 I( T1 `/ i) L
0 d" A) R  K/ k  Q        int keyi = left;
        while (left < right)
        {
% r5 H; r; O" U9 y: D3 t3 W- J; {                //R找小
                while (left < right && arr[right] >= arr[keyi])
                        right--;

; t0 b! y( M, b& d5 s9 s" l                //L找大
- _$ s1 |. [3 z; @& s) e" l/ R                while (left < right&& arr[left] <= arr[keyi])
' s; n; F; P* O0 J+ [9 z                        left++;

) f  B% S  o, m: P4 i! p  S                if (left < right)
                        Swap(&arr[left], &arr[right]);
        }
( t; n& I- u; n' d
        int meeti = left;
! K/ v$ D; @& Y- I
        Swap(&arr[keyi], &arr[meeti]);
; Y1 t3 b& q% q( E
        return meeti;
}
) i; W9 Q& E$ U1 t! n4 M0 k
, n! f% i- q9 j# W, E3 D/ `1
2
3
' s+ H3 ^1 j" D6 \! K2 U' A4
5
6
3 z* _. S  a/ Y( |) [7
8
9
. p  R4 g+ m8 w4 P0 \3 T' r$ d10
. p! j+ F* c; G11
% w  a7 d( K: |" z$ n0 \12
* ^+ a" l+ V0 t" Y1 R. W6 O7 s" F13
" R! o6 P0 c& L9 P14
15
16
) s  M3 v! T* ~+ U1 v  N7 {17
18
0 O+ u- B# n* K19
" B" n- S4 [7 n; I; a9 ~. a+ g20
: x0 [' N2 ~0 P' \' D% @21
22
23
# m5 s, |+ w8 e7 r2 s, K/ J24
3 r  k5 I! d% j$ T" u: ~! B9 ?8 P4 p0 W& x25
26
9 a2 N) I: ?0 x' y' x27
28
* @) K# n6 [* Q1 k: [29
: J" B9 `: p, b. r, Y" R' J30
! [0 T& V! J$ j+ h9 I31
! d# d1 z5 Q& s3 n32
# Y( j  x' K. @& Q4 L- ~33
1 |6 D) O! Q) [; ^34
/ Z/ D+ H/ `+ |/ n3 e; W) d35
36
37
5 \  |7 t+ s; M0 m( r# z  h38
' [: |. ~  o! ?" K/ L39
# {4 Q$ e, j$ a" l( ^+ g40
  L5 U5 x' v' l/ c% G& J41
, `7 M  j' t/ Y. ?42
& ]+ y/ M' R3 j  Y43
+ Y' D) t9 p9 a# r5 }( u( r, M44
45
46
47
48
2 d+ ~! d! S+ u7 J& R7 k: T) i49
/ d2 ?( @1 S+ ~2 r50
51
52
3 p" Z/ E$ M. V- n53
9 \, L4 Z4 V# e$ w9 u  b6 I54
- X+ l; l- Z1 I, N/ _8 q! U挖坑法
; d* ^( d* l, L* u初始状态：L作坑，其下标存为key
(1) R找小，扔进坑，R作坑
2 a. F, O; z) L0 X; k$ {4 ~(2) L找大，扔进坑，L作坑
重复 (1) (2)
最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]

$ U* X' g- P' O7 w3 M3 O
int PartSort_Hole(int* arr, int left, int right)
& I4 X7 V* y9 h/ d* L3 i3 E" z: _- S{
$ X( c7 O; l* ~! I        int mid = GetMidIndex(arr, left, right);
* F8 M7 W' Q2 ?        Swap(&arr[mid], &arr[left]);

        int key = arr[left];
9 A5 L/ M" P1 F8 u# [. I# ~        //L作坑
% C0 {, O+ x" E  }        int hole = left;
        while (left < right)
        {
                //R找小，扔进坑，R作坑
                while (left < right && arr[right] >= key)
                        right--;
                arr[hole] = arr[right];
                hole = right;

                //L找大，扔进坑，L作坑
                while (left < right && arr[left] <= key)
                        left++;
                arr[hole] = arr[left];
5 P" d3 [( x  s% l: s                hole = left;
        }
5 Y* c+ r, p! _        //meet
0 J' [$ }$ i1 F! z  E9 w# ^) D        int meeti = hole;
        arr[meeti] = key;
3 x' ]0 n8 {( |
        return meeti;
}
9 _8 |# i$ d1 H* q
# K! b; g  R5 J1
, z+ C2 }9 N# A/ {; f2
+ v# x) j, u1 d" F' }8 ~3
4
7 Y  F# ?* R' e% r1 ?$ L5
6
* e0 ~5 Y9 f  Z7
8 ?: u+ N) F7 `* M" G8
7 [+ [9 |) p, h0 Q1 `# o1 ^9
  I- k! s5 r( h9 o2 [1 I10
11
12
13
14
$ R) }- j% Y% [% b2 G% V15
16
17
0 _/ f. e& }8 u. i( u1 l! [5 q3 K18
' `, `% ~  I2 k5 W2 r7 D: I19
20
21
" k! W( h% X  I" \22
, ^1 s7 H0 ?  k/ H23
1 v$ t. _* b$ o. w1 O& f  ^# Z24
25
26
27
2 s: W* ^, R+ m9 J28
& o" z! q4 r6 g/ ^, w8 T( K2 a前后指针法
此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多

1 E$ @3 P& x0 F# a2 Bcur找小，找到则停
++prev
如果 prev != cur，交换 arr[prev] 和 arr[cur]
: W' b! C  \* S. E; E如果 prev == cur，不交换
当cur越界，代表找完，排好序了
prev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低
+ k- P$ e' ?2 Z+ x8 k) L, ]


int PartSort3(int* arr, int left, int right)
2 l, c* x  Q7 b7 `; h{
        int mid = GetMidIndex(arr, left, right);
- B3 \1 e1 Q% Q1 [8 @! y        Swap(&arr[mid], &arr[left]);
       
  //int key = arr[left];
" a% {+ x* J& u( N; ]: f        int keyi = left;
( b3 a& m3 U7 J1 u" Y: R1 b
4 M* j% o, Y+ B( K        int prev = left;
        int cur = prev + 1;
2 Q3 x& b$ ^9 [" m0 P1 r       
    //cur越界：找完小的，prev的左边全小，prev右边全大
        while (cur <= right)
        {
0 u6 T4 _' E: T( q        //++prev == cur 没必要交换
0 B7 Y5 {+ o2 S* S& L                if (arr[cur] < arr[keyi] && ++prev != cur)               
                        Swap(&arr[prev], &arr[cur]);
% F5 I8 Y- ^& A5 p  K2 h
                cur++;
- K; Y: E/ e! Y% S4 X4 Y0 a3 a        }

4 k1 S0 E* z- |4 v" J* o        //键值存是的值：
        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
# {9 h4 L7 y: `" d. g        //Swap(&arr[prev], &arr[left]);//这才对
    //键值存的是下标：
        Swap(&arr[prev], &arr[keyi]);
6 v6 p( P* g# \
7 i. o1 L2 {6 [& K* K        return prev;
- A" ^( _/ I& q0 U}

% T7 J" y$ G8 ~1
2
3
4
7 Z) J7 H% D9 @* y* P5
6
7
8
9 k! l% z& K6 @8 G' q* f9
, U) x8 u$ G" x' g4 b4 }6 p10
11
12
13
0 M+ G+ U8 I$ V2 o14
15
5 C$ d( z( t% H0 f. W, [/ Q" m- W- |16
17
18
19
1 H1 E7 ^+ W" k4 \20
21
6 `5 i% I+ s1 K; a1 C7 g) Y" v, ~6 h22
& \5 F/ p* X2 J9 C. v- q23
24
25
& a. l2 ?' _6 }0 ?4 W- p1 ?, h% W26
3 L- U$ ?: U0 h$ d8 \  w  m27
# k% h* y) n# I8 c8 w28
, x* x* s" Q' ], h5 G$ l29
& n' _9 R; W+ A整体排序
; l$ h( ^. k7 L, f0 c; V递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

8 {0 r& j6 K$ b: P//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
9 X! l* J8 o& p) k1 m. M% C        // [begin, meeti-1] - meeti - [meeti+1, end]
  y  q9 t# A. B# c% s                //1.begin > end:超出范围
                //2.begin == end:一个数天然有序
    if(begin >= end)
        return;
2 T7 J  h0 K$ `3 L/ _# K
7 W6 j1 T3 @1 A/ d$ `                //排好meeti
                int meeti = PartSort3(arr, begin, end);
0 d/ B# W: R5 N2 g3 D
5 @  r2 F" Y. v& a. v                //排好左右子区间
; S7 {( S& {, F; x. U# P6 `                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
        }
( p) {4 c# X% H% d0 q: A! v% ^' r}
! c# b$ `, \0 t8 E1 ]3 x
1
5 Q% v$ P# U' ~# d  [, {2
3
4
5
6
" l& H. c8 M4 l" P9 C7
8
. o% O9 `% p6 _% V- {9
2 r# c1 Q( j2 ~- k4 y# A10
11
12
13
) A2 r  ?( U8 @. |14
15
16
17
1 l# g1 x$ h# l  B" `1 e18
& b$ {* f0 n; ^' K. B6 @…
. }  B7 e! s2 }0 J1 v* |5 Z( S
8 ?1 ~& L2 z# l没想到吧，还还还还有可以优化的地方！

0 e1 l; D7 t3 y* j/ N优化小区间
) L5 G! M+ C+ e& h

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

那什么算是小区间？

% [4 X  {- }" U7 p( M% ~其实小区间没有确切标准，8-15左右都可以的

. G" S3 n6 @. H. t" G
, q; ]  L4 d0 q. D* \这里就把小区间定义为 含有 8个数或以内 的区间
, @! `7 }9 @" J2 C; _
+ t8 {9 I# r# T7 ]* T' R6 a. f" H/ \//[begin, end]
void QuickSort(int* arr, int begin, int end)
# }3 P# j" j; x{
/ D1 n6 N2 I4 V* e* `        if (begin >= end)
4 X0 d+ C% y' W5 c* P8 p. |% N                return;

; S6 V+ a8 w8 G- k6 S' _        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
        {
, j- k1 I/ p+ g# O  U                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
) R$ r9 j$ d+ y! b/ Q* o        }
/ C( d! ~7 {3 V+ x2 m* m        else
( q1 |) q+ g! r+ q        {
                int meeti = PartSort3(arr, begin, end);
. u" k8 n; W8 t/ d
                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
        }
' |( T+ g$ S- E8 [6 Q}

4 o. t  H6 m* I% Q8 j5 V1
  R4 z) y' T+ z! {+ V% O( w2
3
4
! g  e, [& j5 r( K7 _/ ^0 O, \5
6
- k- C3 F' d& e7
! R/ U# M! h) U7 _; ?( ^2 Z/ x9 d8
9
( c5 C+ q$ X& z9 p* U10
11
* @- P/ }4 l( V" @0 o12
13
  d7 J  b- U: S/ c1 p14
" Z) l  Z& T" y' Y- P6 K1 G7 o- t15
16
17
' q2 M1 H4 j: \. v+ E3 W" }2 f2 J18
19
快速排序非递归
6 m* G; O/ u' b1 T/ P0 `3 O' \  T( n为了解决彻底递归深度深的痛点，我们来试着把它改成非递归
7 Y( O8 E; c6 q6 B6 ]$ X8 C
0 F9 c+ u- R+ D( t+ l' J6 ^思路：
" Y  ?1 b( E9 W0 d- T  o递归深度深，栈的空间又小，会栈溢出…

那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！
  t. P, H% P6 |4 q( Y4 A9 [
核心思路：在堆上创建“栈帧”
1 }* O2 [& A; T- w
* b7 U) u$ T- J! i' s: {6 r( \快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的


' N% L4 P2 a! x& D2 l6 ]: @- l
在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：

先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
6 a) L! F# w3 D) p* t+ Q先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
{
        ST st;
5 M$ m- Y: v7 u8 ~) w! E$ @7 }        StackInit(&st);
       
    //先入begin
" M1 F6 {4 j/ `1 z0 r- u, z        StackPush(&st, begin);
- }. ~' [0 k6 g1 a/ t' ~& h+ a    //后入end
) [$ `' r% G; u7 Q$ B# k        StackPush(&st, end);

# l# j/ b6 r, x        while (!StackEmpty(&st))
( R) y: _# o1 C# N) M4 _        {
                //先取end
) {- P* R' d& M: M' z                int right = StackTop(&st);
0 N" Y( W  K, f# _( l6 ?                StackPop(&st);
$ v: Z7 V" k( V                //后取begin
' j2 I, ?, K6 _% Q; D, ?% S                int left = StackTop(&st);
( C5 H5 a, Y4 D- ]                StackPop(&st);

                if (left >= right)//1.只有一个值  2.区间非法
8 x/ y/ i8 Q2 t. F4 e                        continue;  
. p: E9 X: w5 L. @7 Y- K: d                               
1 P# ^2 ?# T$ @                int keyi = PartSort_Pointer(arr, left, right);
4 c. M# K  d, C
                //先入右区间
                StackPush(&st, keyi + 1);
. p, C# h! c  l5 r( n6 {/ e                StackPush(&st, right);
                //后入左区间
) D" t3 {! u, i3 X# `' Z" ?6 }+ [                StackPush(&st, left);

                StackPush(&st, keyi - 1);
        }

# p0 ~. a/ Y8 A0 U        StackDestroy(&st);
}

1
% [) x" L  X! `& n  d8 m! T2
3
# `/ c! P8 ?/ R; N4
6 n5 G: a9 T) w# Y2 {; Y4 v5
6
! l0 E: ]' ~8 F7
8
9
4 G2 P8 n9 S  \( k10
11
8 A; }3 k: Y. j/ P" c12
# N0 v0 R6 V+ q) L13
6 ^' u9 K; p% o) ~" Z6 u14
15
16
17
3 ?) B8 {; F- B* w! W* V/ F, U" C18
, H4 O( k* [5 P2 B1 Z19
& Y: ?6 Z1 P' y+ `) h9 ~% {$ b20
21
22
23
24
4 [% w9 Y4 X/ c$ e6 \" D* H25
26
* k/ b. V9 C1 J3 W, N7 T; ?! T27
' u4 S: f/ J1 v7 Z2 G% D5 E28
  }1 Q$ M3 {) `, m' f29
+ D, v6 p1 Q3 j! P30
; @/ S; D! ^# c7 Z; L31
32
% x& V* }# y% ?: S9 \9 T' c33
0 j0 Y4 l" K2 k! m& }2 X& C34
; k% s1 d" b6 c4 Z9 d" |35
数据结构栈的实现可以看博主之前发的博客
3 V# m4 u& l  }- w

归并排序

* E. p; U9 `: S9 E7 ?. N…

6 r" z$ \& ^! o8 n7 h6 N性能测试
8 P  M% d! T, N" g  ]void TestOP()
{
        srand(time(0));
        const int N = 100000;
6 u, u6 g0 s: p1 R' Q4 c        int* a1 = (int*)malloc(sizeof(int) * N);
        assert(a1);
        int* a2 = (int*)malloc(sizeof(int) * N);
        assert(a2);
        int* a3 = (int*)malloc(sizeof(int) * N);
9 k+ P" o1 U; b+ m" \1 z# z, {% v- ~        assert(a3);
1 U% L/ z. l# _1 Y5 \5 N0 G- Q4 r        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
6 e1 k) i9 j5 u8 D+ j) F5 j        int* a5 = (int*)malloc(sizeof(int) * N);
/ b. Y) a  J) n! r) b0 d9 I        assert(a5);

        for (int i = 0; i < N; ++i)
        {
! X4 b+ U1 _  E" ]! @( @                a1 = rand();
8 {! ^+ o, `: O5 ]$ v                a2 = a1;
                a3 = a1;
. U0 q6 S5 ]6 k% s- ~                a4 = a1;
                a5 = a1;
' a- K/ J8 s5 n1 G        }
1 \6 E5 u2 y/ X3 l& w. v' e
$ {5 ?0 Z3 ?! @* x0 c. A        int begin1 = clock();
        InsertSort(a1, N);
        int end1 = clock();

5 l  m( H( ~* r) e& T( @        int begin2 = clock();
+ `! c1 p4 d+ g3 {        ShellSort(a2, N);
        int end2 = clock();
+ Z& ?# S* L2 Q; ?
        int begin3 = clock();
- n! c) A- W% u( R: z        SelectSort(a3, N);
        int end3 = clock();

) @5 I4 t* F4 }# D; y        int begin4 = clock();
        HeapSort(a4, N);
        int end4 = clock();

        int begin5 = clock();
        QuickSort(a5, 0, N - 1);
8 B- b/ F' k* y& S" `6 t                //1.中间key
                //QuickSort(a2, 0, N - 1);
                //2.三数取中
                //QuickSort(a2, 0, N - 1);
                //3.小区间优化
0 P4 D# U( l/ w5 a7 t, B                //QuickSort(a2, 0, N - 1);
        int end5 = clock();
; k5 I) i$ R; G% w
5 \: T8 Y7 t' K1 ^/ `* J
+ c1 \8 a- f* ]. x" o$ T( [% k        printf("InsertSort:%d\n", end1 - begin1);
2 V5 f  H! ~0 M, s        printf("ShellSort:%d\n", end2 - begin2);
6 C% W$ X/ ^) k% N. g        printf("SelectSort:%d\n", end3 - begin3);
        printf("HeapSort:%d\n", end4 - begin4);
        printf("QuickSort:%d\n", end5 - begin5);
8 [, n8 C/ [$ h* J$ d
        free(a1);
        free(a2);
        free(a3);
        free(a4);
9 p8 j1 S0 h5 X# Y+ k2 L9 w4 C' u. W        free(a5);
}

% r& f, A- P$ s$ x1 g6 e, e1
0 n& c9 S) p  W3 Q' f2
; G; B( \* h9 E) X( Z. h3
4
  H# |1 {0 x0 a8 ]  d$ r$ S5
6 Z8 S/ K! ^  v0 {4 N6
7
8
9
10
11
! R& {$ f* I) J$ `8 Q* f3 o12
4 \- u) z3 O7 J( m  C  t13
0 {. f4 ~* Y2 q/ b14
15
16
17
18
19
20
3 l8 U2 Z3 o& M3 Y21
0 _) y  R* u' R  m6 D9 |! g/ v22
3 ^; m. H" C) g: M23
/ g" O  L- X) N4 i& a24
( S% N, R* Q- e2 X* V25
- E. P5 o3 a2 `6 I26
27
28
29
30
* s; B4 [4 G0 ^6 s4 e& w( h31
32
33
34
* @, t" a% E* c. F9 x35
9 n4 Y$ Q1 @+ ]: m8 m4 P- G7 T36
37
38
39
40
+ d4 Z" B* [+ L+ a: z8 Q% H41
; m+ m3 P0 @+ z/ s: E) m42
. p1 b3 [8 j, ^7 T8 z' z3 [1 E43
* t; ]9 ^( i0 ~44
45
46
47
48
0 ~! V: f& {/ r& H49
50
51
9 v' v- Q, ?3 E2 @! q8 _52
4 k; m( a0 _1 U53
54
55
56
4 h! a3 q3 ^4 {4 j# _57
$ _' C/ R% E9 b) P8 e9 m1 j58
! ^0 V6 V2 v$ {2 u" `7 m% S0 _59
60
) U; @& v* \5 M" B61
62
63
3 l2 @4 g( ^0 ~. e) j
# p3 ]2 M6 d4 Q) P  S
不愧我们费这么大劲优化快排，多帅哦！
& X: N4 X1 T" O# q) R8 U+ {9 x- c
差一个归并排序，后续补上！

不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
$ z7 g9 Q5 |& a( v————————————————
版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832
5 L6 d& a# i3 ]- O
4 u4 A4 V# S1 S* ^5 i# f* M# u7 T6 p