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

杨利霞

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

: P8 u$ B. ^; z9 J前言
本期分享经典排序：

插入排序
直接插入排序
. k  k9 q" @. u4 Z+ D希尔排序
$ D, Y# R) v# ]( ~. F; k, f6 E选择排序
直接选择排序
堆排序
  P9 z% p$ k0 U+ _- K交换排序
冒泡排序
7 n+ n% [; k) k! t) z+ H7 _; g快速排序
注：讲解时默认排升序

插入排序
2 j3 x( v0 S1 f4 m4 @直接插入排序
" b/ }6 D; j0 ?$ E! Z( r  C1 M, H思想
插入排序，就像玩扑克时，摸牌的过程：
( G6 x4 N( C* W2 _
最开始，左手没牌，右手从牌堆中摸
右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
0 u: z0 S6 j7 x5 y! E$ L如此一来就能保证左手的排始终有序，摸完牌后也就排序完成
3 P6 m9 n) O3 s
; r+ D2 x( }* Y4 f8 }) ~
操作
设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
- S/ T& c, D% V: u) `单趟排序：
2 m1 P  [' \4 ^9 O4 C每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
0 T1 T. P" t- }: x) s0 Y是正确位置：插入
3 E& ?- A/ A* V不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
$ n2 }4 K& s2 m$ W. U3 }. ]" q# A整体趟数：
& q$ i) x6 B9 t6 |* J若元素个数为n，需要排n趟
8 m. f0 S7 X' Z- wvoid InsertSort(int* arr, int sz)
{
2 y* v# }' \' K# J7 K' t        //end + 1 < sz
4 D- s1 S0 }% }4 o5 r        //end < sz - 1
        int i = 0;
- f; ]$ e# F* _& u+ U        for (i = 0; i < sz - 1; i++)
  z$ N( O: R5 f3 i' _5 |        {
                int end = i;
5 V4 B8 F& L" q! a                int tmp = arr[end + 1];

                //找插入位置
                while (end >= 0)
                {
) q3 o! e0 `# u* v                        //不是插入位置：当前数据往后挪
* n( \; o2 y1 H' g$ D; n6 B# h$ ^                        if (tmp < arr[end])
                        {
" A) j* q7 g7 w/ Z# o                                arr[end + 1] = arr[end];
6 y0 n3 o2 Y9 _5 E0 h8 D                                end--;
                        }
6 K. k) E: J5 z  H) x7 f* @                        //是插入位置：跳出循环插入
                        else
8 K- |- K" \* @; \; M2 r; a+ c                        {
1 U# d! G1 n, d6 ?1 G                                break;
' Y1 b0 K. @1 T2 j3 H8 J                        }
                }
. G9 l, T1 p% s/ [  t) H+ W                //插入
2 H- e! d6 a+ e: ~" d! s3 y                //1. 插入位置是[0]，end == -1，不合循环条件跳出
6 y% P7 s8 o0 Q1 \                //2. 找到插入位置，break跳出
                arr[end + 1] = tmp;
        }
: m4 n, \- j0 V) U# v* X! o}

! R* A) ]$ Y+ T2 E1
2
3
9 d3 y$ d1 \" R) H; W. M8 W2 C9 o4
5
$ R5 P. |$ E# ^0 x( h6
0 H: K  k& o) {3 \; B& u: a3 `7
8
9
10
11
12
13
% g, v" c9 ?9 L8 r3 e14
. i- O9 k7 C3 ?% o, c+ p15
16
17
18
& ]0 _, @# f) X0 ~1 z19
20
21
22
23
" B, T% a' d: p$ y8 J24
25
2 P# s  K% Z6 k% `* }( P1 v26
- z3 S  M6 E0 N, H27
28
( w9 s$ d; \9 a/ C1 x& m% a29
8 [% j' J7 D6 q9 `30
31


% Q- K( N+ q& ?. h/ G稳定性
插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以

直接插入排序是稳定的
! ~5 T- ?$ O, b' H. n
复杂度
+ t7 u9 g& e8 }时间复杂度
最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）
7 X3 Y+ P0 T% Q% N  N
) T/ @8 w6 R; ~' [O(n)

" m; @& u7 i: q0 V  ?- t, `最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2
5 V( ?" M. \9 |) c
O(n^2)
( p1 P  z3 j6 F5 m# G0 B
2 Q& b' B1 ~- Y空间复杂度
4 U* l5 s; P2 G  SO(1)
' N) B# N9 v  M' j! P/ b$ [
6 g4 {. Q, @! r) K希尔排序（缩小增量排序）
, i" i& l: F* }/ u4 z! h; E希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序

优化思想
; ^9 u2 T. U% g! L8 n2 g8 d) O增量gap不止用来分组，也意味着数据移动的步长，所以

gap很大时，序列很无序，插入排序的元素少，移动快
  m; ?  t9 V* f5 Q$ E, fgap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高
; @. _3 d0 L# W! B7 m2 C; |3 p
. f" A8 ~8 A0 W, @& y& E
操作
1 ?- Z5 E7 ?! J1 _% \单趟排序：
/ h" ~6 C8 W; s& f/ q. D
7 D& S3 I- Y* ]# U& I: z  R设定一个不断减小的增量gap，也是元素移动的步长
以gap对序列分组，并对每组分好的序列进行直接插入排序
3 {$ c. D9 q: w! A不断缩小gap，并排序
5 R5 Q* I" u" i3 Y/ l*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
& j. m& I$ ~6 h$ c! j整体趟数：

由gap决定：当gap = 1，排序完成
注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。
& H' J0 N  o/ P: n$ e, Z6 u. X2 L3 T
% s2 ^3 _: ^( H* K( m! r' Z" j7 nvoid ShellSort(int* arr, int sz)
: t* F$ }6 Q: B/ S' s{
" l9 {) ~2 H* D* k# [+ \        int gap = sz;
" m+ m9 g$ U7 r0 L! U3 v5 @       
    //gap > 1，预处理排序
    //gap == 1，直接插入排序
        while (gap > 1)
4 }& q3 R- E7 W! A        {
                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
2 Y5 `) T, \( b9 ^/ }7 K: U                //gap组
# {4 j9 x1 _4 U# p2 m* D                for (int j = 0; j < gap; j++)
                {
            //end + gap < sz
                        //end < sz - gap
                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
                        {
& \, B! j# Y9 h7 I7 {; }9 d                                int end = i;
                                int tmp = arr[end + gap];
0 Q6 C8 I$ E, x8 |8 `2 C) ?                                while (end >= 0)
                                {
                                        if (tmp < arr[end])
                                        {
* N4 F# y- m4 Y' J                                                arr[end + gap] = arr[end];
                                                end -= gap;
                                        }
                                        else
, a, ^! o, W: l                                        {
                                                break;
                                        }
                                }
                                arr[end + gap] = tmp;
" D; Q4 H( \$ o$ ]- @                        }
                }
        }
+ W2 T* |, K' @3 W}
# Z/ t0 q/ u, q
+ n6 \5 _  o/ G6 b1
2
3
4
5
: {. A9 W9 `+ z! j( l6
7
8
2 T' }. Q, v) k6 u: A9
2 {" s5 M* c& J; T- B% \10
11
12
* Z: _# [  E3 K1 b$ ?; ]7 \/ G13
14
7 Z& x. o+ Z% S$ r15
16
( J8 |8 Y; X4 }3 `( U3 G) J17
18
7 R2 F2 X/ t3 E0 ]9 \! _  j19
20
21
1 O; T/ D# a) `. D+ \: Q22
# g4 s2 W( H3 {! ^  X* }23
3 m. O& d$ E5 M, D7 c24
2 I  p: ~3 H( n7 E+ Q5 D1 t; |25
+ V! l4 ~. o/ a' C/ ]2 R26
27
28
9 `" m+ s2 \% g2 E9 A) q; \29
30
31
4 f1 G  [2 X# x8 z$ e32
33
! Y( S& U' J+ Z& q34
35
其实就是套上”缩小增量“的直接插入排序

) W+ Z7 z. J: x9 d+ @- J9 ?
稳定性
我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以
8 d9 @( m) ]+ n
( {( w/ O3 m/ L4 T* [希尔排序是不稳定的
( d, f- N3 R3 {6 }0 T5 a
复杂度
时间复杂度
6 D- d2 b8 q, a. l# I' r  R8 p希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
& w) `% o5 H. g
O(n^1.3)

空间复杂度
. `# |/ _( q8 q8 J5 J$ g/ V% MO(1)

选择排序
% s6 G3 c+ p( R* A, Q4 h直接选择排序
4 `' j2 v* Q7 _, L/ O) Q思想
选择排序，遍历序列，选出最小的元素，交换到左边
; o9 [4 _/ G( n3 W) |" o
# X" h3 Y, K" O& b2 i
2 W3 u  T! z. W* y2 f
6 T. Y, h7 e' m  W5 A3 e7 {优化版本：

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

: R4 z& V: W6 U+ w& {! ]操作
设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]

设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标

9 G) b0 t: H' r5 w0 [" n单趟排序：
% e5 S4 @  P8 F; d
遍历选最值的下标
交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
! d% B: h* V/ P# t/ j. K（修正）
整体趟数

若元素个数为n，趟数为 (2/n)
修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标

" m& C* y! K0 Z0 B$ z) ~8 Dvoid SelectSort(int* arr, int sz)
1 |0 N8 i( }. P* Z; p# w+ O5 x{
        //闭区间: [begin, end]
/ y- B0 I+ c# e0 ~/ j( Z; O9 Q        int begin = 0;
" E0 i0 j. x0 ]' l* c        int end = sz - 1;
& |4 l& a  v3 o5 |9 N        while (begin < end)//begin == end 最后一个数，天然有序
. e# ~) r5 i! Q' ^. o$ \' b# L; g        {
                int mini = begin, maxi = begin;
, {$ Q0 ~( w" o" F- y7 L( Z  g; c0 g                int i = 0;
# g# O7 v9 Z# g                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
0 t4 u: J+ ^% i                {
                        if (arr > arr[maxi])
                                maxi = i;
* @) `) v& _$ x) [; g                        if (arr < arr[mini])
  E, o' e( a3 a3 j/ E, S# c4 e5 P                                mini = i;
7 ?2 I; f) ~% C$ l, u+ i                }

3 X; Z8 ?! R; M                Swap(&arr[mini], &arr[begin]);

, E( x7 W0 `& L, D1 w                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
                if (maxi == begin)
                        maxi = mini;
                Swap(&arr[maxi], &arr[end]);
  F/ F0 [3 G, Z! e
0 d2 `2 H9 P* Y3 Z: }                begin++;
" ~/ m  P1 _* L" g! u; j                end--;
8 k4 L+ z$ H+ _  j; o) p/ c9 U        }
}

' ?$ G7 u0 ^/ _/ {1 Y$ Q1
8 p( T7 @% e3 G4 g* C2
3
2 }0 C% H& d) \9 N# C4
5
9 ~9 {  f6 G9 G7 _  J' {  |6
! O8 V" K: H, g! g' h7
8
9
10
11
4 H7 B3 F+ d2 Q- E+ @1 l7 {) |12
13
14
15
16
17
18
19
20
21
22
23
' W# @7 [5 h' b& M$ b- H4 n24
! d; D/ C3 K1 Y25
26
- M) o# I% ?+ h1 N9 R, P27
28
/ T" r6 ?7 R! p" u' G0 l  F

稳定性
选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以

. O+ V" \, r% e0 ?# `5 M选择排序是不稳定的

+ \7 K  z4 Q& E/ T1 t复杂度
时间复杂度
; B) e" T/ v: u2 c8 l: S% k. ^最好：
0 `# U% R3 N7 }3 D
( z# d* X, Q& I1 h( D+ ^( O3 T比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2
- b) ~- G) y" D. t9 O. R
3 Y; r/ B& i" k; D0 B  o( t! P交换次数：O(1)，有序不用交换

; L2 V' M# b" ?6 x' ]- R0 C5 K" J4 GO(n^2)

% O8 p  y  ?. D7 @最坏：
+ V3 y/ g: L' @8 A# b
' C0 }( C- q" `; I) C4 r比较次数：O(n^2)

# z. Q" Y( Y- e7 t: @9 ?交换次数：O(n)
+ S' d# k: O9 r9 w! H
O(n^2)
  O& P9 o6 Q  k  q* J4 h
空间复杂度
O(1)
' d3 N, j; j2 q; j
: k( M; T0 o/ L+ Z堆排序
思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆
& m* w# a7 i1 g2 R; y
/ j) i/ E5 }; g# L' ^/ I9 T. o
* @+ J( U5 P  I3 z  e/ E
' t9 u0 }: A% e) M操作
  ]0 X* q* c# A9 B/ V建大堆
单趟排序：
) S/ x1 s9 p& Q6 }选堆顶和堆尾的元素交换，则堆尾的元素排好
: d" ^; p2 z0 l/ b: X每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
整体趟数：
9 W6 L. ]( U6 H5 z. t) \若元素个数为n，则排n趟
void Swap(int* e1, int* e2)
{
$ i7 Y5 d, _/ A% O. E# H4 c        assert(e1 && e2);

        int tmp = *e1;
        *e1 = *e2;
        *e2 = tmp;
5 S# F( z0 j3 T$ P0 s5 i}
; c" ~7 S( t9 M" U
void AdjustDown(int* arr, int sz, int parent)
: b2 w7 c4 z& s* e% n2 C{
        //建大堆，排升序
- I  m& m4 D4 \0 H' j7 T# p7 w5 Q        assert(arr);
       
3 g0 B1 T" j* r! R. d" s    //默认大孩子是左孩子
3 h% F  }- ]1 B6 r        int theChild = parent * 2 + 1;
: q5 o7 ?2 f1 Y        while (theChild < sz)
        {
8 Y4 Y" a7 v/ z        //如果大孩子是右孩子则修正
                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
. o' U! b4 [8 }' N! u                {
                        theChild++;
                }
- j# c3 b, k8 ?5 r9 z# t2 c- }                if (arr[theChild] > arr[parent])
                {
                        Swap(&arr[parent], &arr[theChild]);
            //迭代往下走
                        parent = theChild;
$ w+ @: [9 l% \3 L3 [5 T                        theChild = parent * 2 + 1;
                }
                else
; _$ B7 d( u1 ?9 r; \" p                {
, o8 T, H6 y( M7 b1 o( S5 Q                        break;
& C3 b6 q: p# ~7 H. a/ H1 E                }
        }
* B( z8 M# E5 i, h6 L6 d4 Q! [: ^}
* a2 D: m, B0 R8 @4 H  G8 ?" h
  [% k( H$ L# Cvoid HeapSort(int* arr, int sz)
. H6 K/ Q7 Q: N8 B; @/ t  i{
        //1.建大堆
' ^2 D, g$ z+ L" @9 u* E* S9 i2 R$ w        int i = 0;
        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
        {
                AdjustDown(arr, sz, i);
        }
7 X' [2 [0 _0 e/ c
* I9 q! w& m' }" `; j' p        //2. 选数
) q) X# O: e3 j. n        i = 1;
: p1 b: S' l2 k* t  \6 O* ~        while (i < sz)
8 n1 L' L. A* [2 C0 m; C/ q: f        {
                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
; T- F4 F. Y/ I: k( r2 {' B                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
" B4 p0 A/ r. f6 w* b& n! j3 t7 K                i++;
        }
" j% t, T2 O' D. N$ Y}

1
5 Z9 [4 I6 Q' [. d2
1 X: y1 `0 V3 R7 H+ |3
4 h8 O4 r2 V& \4
# ]- h1 i5 @5 C; K2 G' Q& R5
6
# |. H/ Z% U" Z$ A1 y! n7
8
9
; k. F! q7 [! h' R* C+ l# O10
" `( v7 l* w$ I! ^11
12
5 u+ Z% t4 V8 H7 X6 y) \13
14
15
16
17
18
19
. |; n; p7 g" a8 s. d20
% o$ o3 z# p# x7 X9 n" _+ e+ ^21
( j8 o1 r0 Z4 w4 \2 i, l22
23
) r2 n; ?: n% B# g24
25
26
27
: F0 F# y; u9 j$ ]! J: I+ m0 z28
29
30
5 h$ A% {" m0 m3 _3 i0 A31
32
33
34
35
: w1 T' _5 C+ s- x: n3 m  L36
$ o$ \7 x+ y8 j- }; Y9 ~. s37
38
39
40
. _0 `+ H$ x: N41
42
( w  ^0 y$ o% B  I6 `0 L43
5 M" s6 E# c  U# T7 K0 a9 {- S44
6 C, y( K6 v, u: `. s' q4 f45
46
4 G! I) h( g9 n/ C47
48
7 z$ y% a& g2 c$ M) ?- t49
1 ]( z! W7 ~" v2 G3 W50
7 \/ \5 a: Q$ _7 i6 E+ x51
) m8 ]( Q: F" |52
1 F3 F* V  ?, A/ h53
; f7 H9 A7 e( k5 B54
5 z) E8 a6 c' m55


稳定性
% s# L# Y+ |  r' X+ y$ p( M建堆和向下调整都会打乱元素顺序，所以
3 ~4 V& @% t; L" _$ ^; Z- X3 z2 A8 ?
: f# `6 n, Q7 G1 b堆排序是不稳定的
! U" g- K7 k  o1 W  }
% @6 {0 V- ^( P# g8 x& S2 \: I) {复杂度
时间复杂度
: J0 f0 p6 [0 u单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为

O(n*logn)

) w2 G) D2 [# S9 j3 o) h9 c空间复杂度
原地建堆

: {3 x( O7 K' C. U( uO(1)
" a* _  C* W+ Q. j. S# Z8 y
" X& v1 \1 A% Y2 u4 z交换排序
  C$ u2 B. J$ u冒泡排序
* D1 a% v6 z0 D; @0 d# \# |' \1 D思想
( J' t* ?+ U# @冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素

: W. _4 _/ ^/ a, v0 m

; M8 @  {4 G1 N: \: M操作
单趟排序：
每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
每趟排好一个元素，所以需要排序的元素每次减少一个
4 ^% E/ P( m- N7 b8 |1 W整体趟数
若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
6 P  R; @( T% kvoid BubbleSort(int* arr, int sz)
{
        int i = 0;
. N# e8 @/ j4 {        int j = 0;
6 ~0 J1 b7 d: b; C/ M6 y8 e        for (j = 0; j < sz - 1; j++)
0 ~9 i1 ^0 D9 D        {
                for (i = 0; i < sz - j - 1; i++)
) D4 M# u3 z! f/ S                {
# O. I0 u5 ]/ w                        if (arr > arr[i + 1])
( P( J( }# d$ U$ S4 l                        {
0 `$ p" @# f6 \, L+ x                                Swap(&arr, &arr[i + 1]);
                                flag = 0;
! R; e$ z! m0 X2 ?- z                        }
4 s; G% j# r$ q& M  u6 l: e2 D                }
5 G* @6 X) h) \. G        }
7 j+ z# P6 e' c}
, {3 }! o# G/ P1 C8 O' i/ T
4 a& f( S3 }& |6 a1 P# \1
# k9 \5 J. H( o' P2 u8 l/ v" A2
/ h2 j1 R( G2 g* x' K1 l3
+ h* D1 I- Z+ ?2 h9 |4
0 Y5 _" M% O. P7 Z" G5
6
7
; ], A1 D  d- l' W4 ~* p$ A. w5 T8
+ v9 Q6 O! |: ~; ~8 N1 n+ h9
10
11
+ D( L' N4 L9 Q' N12
. W, o# I4 I# g$ O9 n2 {13
! p. V5 Z8 E- I. d9 J% V5 i2 R14
* i' G5 F, v6 N( e% O15
16
7 f8 `( Y% h2 {4 K7 M. t优化
1 V# t# o  }' B( o4 W5 o当遍历一遍发现序列有序，直接跳出
: g; K# c+ c# l8 o2 V/ P
void BubbleSort(int* arr, int sz)
" w0 Y2 ?: r% U1 Q1 u3 l{
1 ?3 d4 t8 \: E        int i = 0;
        int j = 0;
5 M% q  e' r) A, i        for (j = 0; j < sz - 1; j++)
        {
) U" C; i' K# h$ V  z# h% N' E                int flag = 1;
                for (i = 0; i < sz - j - 1; i++)
                {
8 z4 X9 @! x  O4 O) v# ^& Z                        if (arr > arr[i + 1])
" J9 _, r2 _7 [* P                        {
                                Swap(&arr, &arr[i + 1]);
5 P% w5 A0 W9 x5 D) F6 L( L+ T2 a                                flag = 0;//不是有序就置0
                        }
+ c; V) v% O" Y: Z0 S                }
                if (flag)//如果一趟下来还是1代表有序
                        break;
" `7 d0 D4 V: `  [+ E* M$ B        }
* U! A1 w3 f  t# y}
  }2 ?4 E  z  X& j0 ^, P
1
6 \/ x# P% H: K& N2
6 D: I) F2 f% ^! C5 k5 A8 I/ F3
4
% P, ~2 R# J5 X' T/ |2 j9 ^, J9 N5
6
8 u2 Y  K& ^  {( ]3 x9 ~7
( [- {4 V% g" j2 S& C7 Y8
9
3 ]. p0 Z9 b( W10
# h; i* i9 ]$ y) }- y11
, \* x. Y' G% H# \8 m2 \- c$ N12
5 L* b" u; X, G13
14
15
16
3 r9 a0 V, j1 g2 G  T* u17
18
" X9 [3 x( E# E$ K19
" s# [5 z( B& x; n
2 l: U+ F6 [7 W; t0 X. b
稳定性
相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以

. ~, v) D# k% A/ {冒泡排序是稳定的

# {/ P( e; S, J- U1 V9 `: l复杂度
$ c1 r# B- x7 M( U# K; l& X( X时间复杂度
6 O1 K! q0 f, O0 r4 u( ^最好： 当序列有序

未优化：
4 I- d. u* E' b' J) q+ j
O(n)
1 j  Y: d1 i0 Y2 X2 r5 ]- R1 [9 o/ ^
0 |% x3 P9 V7 I* j8 v$ N3 @优化：
& I! F) e/ X. o  U( v4 r
2 T: b& ?1 L8 n0 c! U- `: uO(1)
; n' g$ O( \; m0 [4 e
  }( r5 O' j: b! t0 \' k# v最坏：要进行 n-1 趟排序，每趟交换 n-i 次

O(n^2)
" B/ |4 X8 C8 S; X' W
; ^5 [, I4 d3 ?% S3 H3 j空间复杂度
* Q8 k4 Y1 P: l9 z* tO(1)
7 S) A) e5 h' T& q
) p+ }0 e% ]6 x! ?快速排序
/ ~' R9 m5 F' ]3 _9 l& [) }思想
6 _3 I; ]; K. W+ t0 x* K/ y分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。

4 x9 P1 f( {  b, Z3 d0 k所以快速排序可以用递归来实现
' {# ]/ T/ j: K  L
操作
有三种单趟排序的方法：

# K6 f8 t1 ?: I, @  Y2 t7 [Hoare法
设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间
) r$ {& m2 c8 L8 \9 F! U
7 S& o/ p/ N  m& N" r左下标 L = begin，右下标 R = end

$ u0 E5 D' F  R0 ]设 L R 相遇位置为 meeti
) r( Y  j  S0 V2 s. N
0 Y; L6 U3 p: j​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”

​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“

选 键值的下标 keyi
$ W' F# i& e7 A: T6 H
  O# q5 m* K% p- f, e  W左1位置作 keyi，则 R 先走
0 b5 W3 U/ ]( S/ y右1位置作 keyi，则 L 先走
) |& L# ~1 A2 t7 h0 i5 ?R找小，
0 f, F6 B; K% {% N% _# f7 _
找到则停
遇到L，则交换 arr[keyi] 和 arr[meeti]
L找大
6 G% q! F6 r* [$ j" ~
. P7 r* z! ?4 ?" ]+ A# B6 Z$ B找到则交换 arr[L] 和 arr[R]
4 f! b8 T7 W: F4 B4 h, x- C' @遇到R，则交换 arr[keyi] 和 arr[meeti]
% i4 F) P* u8 n& s

5 W7 H; r+ s6 i$ n4 F解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
$ u( e9 y; g) W2 y, b答案是肯定的：
0 k7 J8 p3 `- K
" Q. a" J3 M; `' k  {  P/ N3 ]7 T2 F


//[left, right]
int PartSort(int* arr, int left, int right)
5 d0 I9 x, H; m. `* i6 ?" j) P( U{
        int keyi = left;
        //相遇则排好一趟
        while (left < right)
( E" P% {* E0 C9 x1 j        {
                //R找小
, X- F; p) X- {' K! O" H, c+ y        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
                while (left < right && arr[right] >= arr[keyi])
! R( p6 E+ j7 R                {
( J0 F' L* R) B" U6 C2 Q2 ?                        right--;
                }

                //L找大
                while (left < right && arr[left] <= arr[keyi])
                {
                        left++;
                }
               
: c( l* t  _" p5 r8 V% S  k        //相遇就不交换了
( d, I& ^6 m% Q2 Q0 W" y/ G                if (left < right)
                        Swap(&arr[left], &arr[right]);
, f0 u4 c& r  {6 q1 L& L        }

        int meeti = left;

" j% F2 Y1 M7 M6 O2 g; m* @+ Q% A% E        Swap(&arr[keyi], &arr[meeti]);
( I+ V) J' v& `1 z4 W+ r& R: N6 P3 K
        return meeti;
}
1 G3 ^% |$ b8 d; x) ^% p* S
1
2
" U' O( H6 ]0 Z: l0 e& \3
4
5
6
7
8
9
* V- F. G2 A9 L! W5 u* _' V10
11
12
/ w5 J3 r  ?' c13
+ Y" U# m) t( o; }14
! C7 }0 k) ?0 s% z" T8 o15
16
17
18
0 W% X* J) E" d, B1 X) k$ [19
  M5 G3 M6 l) |20
, K  G! V" e* t) f% p4 j. N21
22
* k4 u3 g! |) N% S23
2 S* [# t8 }2 O9 i% p6 I. f, ]24
3 ?$ ?$ Z0 F% v( P3 D8 N25
# Z. t' u4 R$ D; x% g( Z26
27
28
29
30
, V7 @. R# ~( d  z( C' V31
32
- l  ~; k" {1 q- G2 X1 Y
5 r* {4 E9 E; l7 ?. [) S
/ g+ s8 a0 r  u+ z解惑：为什么key要选左1/右1，选中间不行吗？

: @1 t/ P3 a& {' K) j' t9 F
可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深

& i7 H! w4 q- X$ R: x
, I% l- g" m! `, A2 n% T: p
, N9 A: N" V3 r6 A1 }
+ x: p' [4 T+ S% q6 \非常容易栈溢出，怎么解决？针对有序情况，优化选key

优化选key
  x0 r) |* n9 Q8 C3 v" r4 v$ \随机选 key （是一种办法，但是不那么彻底）
0 O% q3 a  N9 L选中间位置作 key
* i: n+ j& O4 \- j解惑：那先前实现的单趟排序不就失效了吗！
：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑

# o0 G! w( f4 h9 b* x6 M解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
前辈给出三数取中的方法
( I" `' B8 o/ R
, Q0 H7 U+ l& i$ I# j+ k% j三数取中
- O1 w% z. H+ c& p0 D+ j在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
# k- b  T& k) C" m. f这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
1 E& @, H8 H0 Y优化选key后的Hoare单趟排序：

int GetMidIndex(int* arr, int left, int right)
; y/ E0 U8 E* @" a' h( o( L3 a* ^3 B; ^{
        int mid = left + (right - left) / 2;
//  int mid = rand()%(right - left) + left;//增加了一定随机性
. Z; L6 W+ P1 u4 h        if (arr[left] < arr[mid])
        {
7 P) X% l- `- S) K                if (arr[right] < arr[left])
0 q; M$ K  B6 x6 t0 S' S# Z7 ]                        mid = left;
                else if (arr[right] > arr[mid])
                        mid = mid;
                else
                        mid = right;
* G; \& [8 X6 e2 u7 |, H9 c        }
; ^& ~( S9 J2 ?' Z5 n        else//arr[left] > arr[mid]
        {
                if (arr[right] > arr[left])
                        mid = left;
                else if (arr[mid] > arr[right])
                        mid = mid;
                else
                        mid = right;
7 S- z$ Q% @  `- M: i) W1 ]        }
        return mid;
, E( E/ h4 T$ [! Z1 y4 }1 W& k}

$ u- z5 v" i/ iint PartSort_Hoare(int* arr, int left, int right)
{
4 w$ T) _2 X/ g5 Z) x% ?        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
        int mid = GetMidIndex(arr, left, right);

        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
: s: e9 e6 z& y9 g5 e5 @5 {        Swap(&arr[mid], &arr[left]);
  O5 p: S+ [( y( x. z: G, {; j1 d
        int keyi = left;
        while (left < right)
/ W& }0 A9 n4 J8 ^, \0 E1 y# y. e$ {        {
                //R找小
+ Y2 y$ I8 W4 r5 r. N6 q; Z. N4 O                while (left < right && arr[right] >= arr[keyi])
                        right--;

                //L找大
) z7 _! U* y1 s3 C; N                while (left < right&& arr[left] <= arr[keyi])
                        left++;
: @" {% i$ D2 `( ]. d6 X9 i
                if (left < right)
                        Swap(&arr[left], &arr[right]);
        }
# d! v5 w# i3 [
        int meeti = left;
# `( l9 M- D$ V! {2 B0 r
        Swap(&arr[keyi], &arr[meeti]);
' C* i2 r0 N) v  W. a3 k5 s
        return meeti;
/ T, f# C* h6 {. F1 E5 @}

% u: ^/ C6 x" S1
6 l, d* |7 G  i  V: O2
3
9 m( }6 ^* a& y0 @4 i* }$ G: y4
+ o4 v" M3 C9 H# _5
' x( y' {& ~2 O3 w$ [1 ^* X( E6
7
  \2 @* `" ~% @8
1 K) W7 a8 [; |* v, w3 C9
3 p6 B, H( K6 i+ p2 d10
' @0 }, ~; S. Z" X) S11
12
13
14
15
6 i" `& m6 n6 z: E  T( @16
17
2 ~/ u/ Z6 \. L8 d" @+ C: z0 y7 I% p18
19
20
! z% p% H  [3 E+ u" [- n( Z$ p% b! K21
22
: _6 ]7 q2 J6 ]- a; d6 H23
24
$ g6 V) \3 J; f/ n! H; }* l25
" ~& ?; L: Y' Q1 Z5 w1 T26
' s- Z7 D2 E) D% h& Q& j' d; T27
28
4 |& ~* K" q4 J6 A8 Q# W29
( \0 L3 F* @7 E" S30
31
32
1 a7 d7 C) W0 B5 x: F/ `33
+ I/ ~$ X3 U. }1 N0 W, C/ ?5 Q34
4 |: _8 k$ J- L% I0 c0 d35
36
37
4 n8 ], ~+ B$ D7 o2 U1 b1 y2 c6 }: z38
39
4 o4 z0 I" @/ X; j$ m$ H2 C40
41
2 ?7 ]* {. `5 P3 A$ M42
43
( N+ [  P" w% o) n44
45
% O7 V# x% X: u46
47
48
49
50
51
52
0 a" J; b9 U" o! s/ f4 P0 g53
1 Q( t. W$ _( O: R4 k$ q* f0 a54
挖坑法
初始状态：L作坑，其下标存为key
' I! y$ O( {. G9 ^1 a! s- \+ d/ ?1 T(1) R找小，扔进坑，R作坑
  n: V" d$ `9 t- {" }$ M2 P6 ](2) L找大，扔进坑，L作坑
% y2 x5 x6 u' e3 ?  G重复 (1) (2)
' I/ P* u% K" \# |最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]
0 v1 l: C4 g, }

int PartSort_Hole(int* arr, int left, int right)
& n0 L, g/ z4 G% L9 ?{
        int mid = GetMidIndex(arr, left, right);
* {' h6 M- l# _$ w        Swap(&arr[mid], &arr[left]);

: P4 W9 B/ f% J8 z. ^        int key = arr[left];
        //L作坑
( q, n0 N! K3 v7 S; l9 Q        int hole = left;
! M* q0 t, K) E1 F        while (left < right)
( U8 o# i! ]  s- h        {
$ ^2 ?/ I4 M: X5 Z! K                //R找小，扔进坑，R作坑
                while (left < right && arr[right] >= key)
2 M. c% w2 \" z+ A6 b: p. _                        right--;
% H' l6 }& ?, ?: p4 }                arr[hole] = arr[right];
( J( ?  @1 D& Q7 `, X" {# N0 V                hole = right;
! D1 o; J* e+ H- J  P
8 J. i2 M5 R) p! W$ G                //L找大，扔进坑，L作坑
                while (left < right && arr[left] <= key)
                        left++;
                arr[hole] = arr[left];
3 `- N' W2 [- O                hole = left;
$ V1 I! M1 ], u  z        }
* `& e7 ?9 b! r) ]/ \! g        //meet
        int meeti = hole;
/ s- ~- l( l7 [8 F0 H/ F' J8 ^; |& b5 ~        arr[meeti] = key;

# s7 c' [3 \) b- {        return meeti;
}
8 o/ ?- I4 J7 w# M* b$ g  F1 s
% Z0 T5 r3 R+ d* a+ G- h% h9 x1
8 N9 A7 q  i- |& B& _+ a2
3
1 L# E8 y  y/ ~# q+ j+ M+ f4
5
6
7
8
  ^6 f- k8 m7 X8 Y& o9
6 G- |/ L3 b% `8 }10
11
% r7 X1 O9 _, c12
13
- g' }' K$ d$ Q14
15
$ d+ ~& B! m6 [3 O5 C16
17
18
19
' P- p$ c. o9 q4 _* B20
6 P+ |. P" c" k" ]7 e3 {, p21
22
23
24
6 {7 M( |$ e& }0 e; _. h5 z6 l25
0 k* s# {# o  b4 w: ^& m8 C+ l26
" `- r5 v) `! X0 _9 }; I; J! O( u3 E" H27
" ~; Q* o" @6 f9 `( V$ {% N  b% h28
前后指针法
3 J* y' \& L5 `& O此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多
5 d* V0 B6 g( F* \
cur找小，找到则停
++prev
如果 prev != cur，交换 arr[prev] 和 arr[cur]
! a( [! ?! ]7 O& O4 N# z如果 prev == cur，不交换
当cur越界，代表找完，排好序了
+ O1 `9 J3 ]( {' Mprev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低
! A! u% V# M2 ^5 c5 ]6 K
3 J/ W4 L0 u+ j! }+ |

int PartSort3(int* arr, int left, int right)
{
        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
       
/ C( u& v1 s3 B# {  //int key = arr[left];
0 T% D9 }5 T9 g9 S8 z& l        int keyi = left;

        int prev = left;
        int cur = prev + 1;
       
* O* N% z# ]/ u2 ~# y5 h    //cur越界：找完小的，prev的左边全小，prev右边全大
        while (cur <= right)
        {
$ c" G% v$ w' t$ _        //++prev == cur 没必要交换
                if (arr[cur] < arr[keyi] && ++prev != cur)               
3 A; q& l4 A, U9 K% Z+ d9 A                        Swap(&arr[prev], &arr[cur]);

5 L/ M$ c& V! Y( M                cur++;
        }

( p+ Z- M2 q# \1 _  ?6 Y* p        //键值存是的值：
5 g' a" B0 K7 m0 J, M        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
. b. _, V* s/ z& Q        //Swap(&arr[prev], &arr[left]);//这才对
    //键值存的是下标：
        Swap(&arr[prev], &arr[keyi]);

        return prev;
}
: b5 d: T" S6 C- d: Z. O: `6 _
1
2
3
: t- O& Q2 Q! {9 I' `3 B4
2 S  w9 f+ j  }5
6
7
: T6 t/ ^# F- J' B1 U; ~8
9
10
3 |- d7 X8 Y) B6 ]11
! G: m1 w2 I  p! A. F. f6 {, h- H5 X12
13
$ m4 ~/ j0 z3 |8 M14
5 U1 d3 F$ c% c% O5 T8 u/ H4 m15
16
( `' R$ I+ M3 {6 o  ?17
18
7 c! J; D4 Q1 E19
20
21
22
: l8 |  v; Q" k) o$ }- w% U+ _23
0 o, W3 \) c/ Z7 P; Y4 X/ |24
25
. I, u6 [) o; q" e4 r( B& r26
: y( U# g2 A: ^' i$ K# Z& f) U  ]27
28
29
( v7 c4 ?, l! @4 L整体排序
- o0 E  C- ]) ^7 H递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

  y/ `, ?& f$ i# {//[begin, end]
0 Y& h1 G8 V8 r$ cvoid QuickSort(int* arr, int begin, int end)
{
        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
2 \! Q7 O/ L" M' \5 Q8 T        // [begin, meeti-1] - meeti - [meeti+1, end]
1 k9 i4 e% V9 q2 a- j5 Q                //1.begin > end:超出范围
. v: b4 |5 _& x! `, i! a                //2.begin == end:一个数天然有序
7 `+ K. Q5 {8 G9 h: W    if(begin >= end)
        return;
# F( Q' `0 ^6 C1 w% u; F  @. c
                //排好meeti
' t  t8 j5 Q) |                int meeti = PartSort3(arr, begin, end);

                //排好左右子区间
! R/ |3 ^( Z  g" u8 C6 m                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
0 K0 p% ~! M/ l        }
7 U, D' D8 C2 b* U, l, |}
9 M( ?, l* T" f8 E3 D
- b( D3 M, H) `' d1
+ T# x  ^6 `4 W% L7 H; v7 u2
. k/ j5 i7 @5 k  H  L) @5 H3
4
2 _4 d3 \% S- _5
8 ^# A1 M7 S6 _# a& S" h6
7
8
  m5 J$ i8 y+ `+ I, ]9
/ c5 L9 W, o, p9 ^: w, L" }$ j( ]10
. G8 q& v5 e- Z: j11
3 w2 I0 T, F9 k4 ?7 L12
( {0 d  K8 I5 M6 m13
2 @, R) J5 N: g- W, J# Q1 f14
" z# i9 A  z, I- V  f5 Q15
. A- P/ F; s( l$ o16
/ x  ]7 Q# U" g7 \17
$ |9 h1 t3 d; b1 K- G. T. e18
+ y! J8 O- s3 J% ~- \6 Q…
5 w- c; {2 d4 H" d
没想到吧，还还还还有可以优化的地方！
! Z8 e) |5 ?; ]
优化小区间


+ P) U* ~, f/ ], X' C+ N如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序
8 P* g2 `) W5 P+ g5 v
那什么算是小区间？
3 Y3 ]7 v) n; T. ~+ X* |- o5 H
其实小区间没有确切标准，8-15左右都可以的
, N  x3 E5 q5 v' l9 \8 T7 V3 R

2 P: F+ I& k, h7 m- W这里就把小区间定义为 含有 8个数或以内 的区间

4 t6 z; w! y  h//[begin, end]
void QuickSort(int* arr, int begin, int end)
( v9 q0 n- G1 G! [9 E4 v! y{
/ X! y, P, V* D! \6 U        if (begin >= end)
7 F" j: F' }- U% w8 p# N- j3 }                return;
. F9 z" `9 P% ~7 G7 U
        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
9 D  v9 s" j% k1 u        {
7 T9 A) a% F2 f; f                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
. ~. N7 h, N0 S% }                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
" e6 H6 u9 D1 U8 I' ~        }
- W: x0 Z9 x5 j! J3 |% B        else
% ^0 P/ O, a1 z% B! Z        {
7 B* F% E' w2 E) C" L" G                int meeti = PartSort3(arr, begin, end);
3 ^( x) L# o7 J$ W! J! g
                QuickSort(arr, begin, meeti - 1);
! T# W5 ^. R5 q/ x$ R. y                QuickSort(arr, meeti + 1, end);
' q5 f" i4 W/ S        }
}

' [% E$ ?$ x* N9 K8 _1
) ^3 [: k' Z. n& @/ x6 M2
% W4 D  C5 u3 C  b6 P3 ]! l/ [3
7 j5 t: E4 J' O# X* z: \' B4
! ~0 C: |; Q. g6 t# R: j' g! A5
% K- `3 q& i+ r1 ]* Z6
7
# P$ I6 u1 y5 T& j% B, Y1 c2 H! j8
3 T  j6 k. c' e& ]* v" l9
6 {, T4 \8 ^3 k9 s& y0 `+ w/ j10
11
2 z; H( u5 ?+ ~- Q  {" A9 F, T12
1 W- E( b/ n! Q2 I13
* r0 _" N# @0 [6 g( n14
9 m% E6 p! d3 b/ u, W9 {3 f/ u2 ]/ y15
16
7 F# `/ o+ t* H+ k# Z17
+ C4 g! f+ i* u% d4 U18
19
快速排序非递归
! D. r0 H* Y3 [1 ]为了解决彻底递归深度深的痛点，我们来试着把它改成非递归
2 x' [: J5 C, l7 h9 {5 W, p; T' t
! o: o' Y* Q9 s: L4 `* S思路：
4 v- d( @' q  d& j8 e4 u! y递归深度深，栈的空间又小，会栈溢出…
5 U9 h5 ~- `) [: A2 {5 H) I
- F" @7 D* I. {" l' k那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！
' o" Y+ b& G# o. n; ?. ^
核心思路：在堆上创建“栈帧”

( j- c7 X0 [$ e7 _$ Z% k快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的


/ t+ m6 H4 D8 D( }$ ^8 ^
在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：

先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
3 G( a+ P6 ]& [9 i+ w{
, C) U1 e* s& k1 g# G4 i        ST st;
; m# V1 t* ~8 f' d; n) y        StackInit(&st);
  }$ x  f. B! y* c! m       
    //先入begin
4 ]$ ^! {% ]3 s6 b        StackPush(&st, begin);
    //后入end
        StackPush(&st, end);

8 C; w0 c& _% a        while (!StackEmpty(&st))
( m' G/ r5 j' @2 ]4 W% Q        {
                //先取end
                int right = StackTop(&st);
                StackPop(&st);
                //后取begin
                int left = StackTop(&st);
                StackPop(&st);

  e; x  F: o0 O' R5 k# B, p6 q                if (left >= right)//1.只有一个值  2.区间非法
% L+ g1 y7 ~7 D8 v1 [- t' u3 J                        continue;  
                               
                int keyi = PartSort_Pointer(arr, left, right);
3 p: P7 K+ x1 g- ~; K- U
                //先入右区间
                StackPush(&st, keyi + 1);
                StackPush(&st, right);
                //后入左区间
                StackPush(&st, left);

- D8 Z' D5 v/ h: z9 E6 K% `8 z. c                StackPush(&st, keyi - 1);
        }
$ h6 U% e( }7 j2 ~4 x4 F
        StackDestroy(&st);
}

1
2
3
# Q, }( B, ?/ [. ~5 j4 |4
5
6
7
: C) y$ Y4 R* U& X' X. E8
9
10
# S& I9 r/ v8 e! d4 L! y+ r11
' S! D, P2 z/ ]' e12
13
14
6 x  ^4 y% I9 T1 ?, P# h( ^15
16
17
" c. G9 {( g8 f/ z7 l18
* P7 e% X! t* _% I19
9 N  Q1 Y3 R8 \$ T  }7 v20
21
5 u! ]) y' k* Q) I) d1 O; m22
; C! O# H8 `2 H5 R4 Q+ |+ y* k7 ?& j23
9 j' O. i1 ^& U; O1 S# b24
8 b& r% X& T' I$ E25
26
- c% z1 ^+ m! B6 ~# u27
28
29
' ]; N5 K# a' b7 \# `& B30
# B5 G: G" M. K31
0 J' _0 l* G$ {* U% F) P2 ?% g! C" p32
33
34
35
7 ]0 ]3 b; L6 j* M0 U数据结构栈的实现可以看博主之前发的博客
% g8 C! \/ l) N' S0 `
4 S6 F1 X$ \& z6 y! L1 Y2 ?! T2 R
归并排序
5 O) ~1 X7 x. Y( @+ ]/ o3 o; j# x% _7 ~
…
4 `+ g+ V( i6 D3 T: \4 m5 n
性能测试
void TestOP()
' S, N0 H( m( Z6 S, ?5 z, d- \{
$ A; x2 J% g8 o+ H* [; i! z( @7 ?        srand(time(0));
) v, z) R$ l7 [5 t+ a        const int N = 100000;
4 [/ O: \2 |/ s! x- @6 ~        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);
! ~$ u6 a8 \- q8 G8 q/ ]( S% D        assert(a3);
        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
; @  i. x+ d% {: z0 t  G        int* a5 = (int*)malloc(sizeof(int) * N);
; c" f9 s( {: j- K  y7 d8 }' Z        assert(a5);

        for (int i = 0; i < N; ++i)
        {
                a1 = rand();
                a2 = a1;
                a3 = a1;
9 n. C3 O% [8 i/ s3 o                a4 = a1;
1 h& x% M8 E# u, ~/ X. K( o                a5 = a1;
        }
, j5 Q% W& h  u5 Q
        int begin1 = clock();
0 n) m' l% \# F        InsertSort(a1, N);
5 I' ~$ L3 k+ C" ^9 Z        int end1 = clock();

        int begin2 = clock();
        ShellSort(a2, N);
( y& R8 k) a1 |6 H/ t+ @# b        int end2 = clock();
2 M# m3 L) R+ y6 J
$ F6 i+ h" ?5 {. |+ p- n        int begin3 = clock();
        SelectSort(a3, N);
+ Z' d+ x7 r1 ~7 d( u        int end3 = clock();

1 O3 v6 I; |% Q, g  e) \6 U: _        int begin4 = clock();
+ T; a) `) Q! W: W; C        HeapSort(a4, N);
1 t3 A! ^7 S& J) P! R        int end4 = clock();

. K7 E3 I1 k9 l! e6 W        int begin5 = clock();
        QuickSort(a5, 0, N - 1);
5 h' e, r' m# y                //1.中间key
" Z- k4 T: f; B6 |9 |. z                //QuickSort(a2, 0, N - 1);
                //2.三数取中
                //QuickSort(a2, 0, N - 1);
                //3.小区间优化
3 F7 g" }' Z+ J$ z0 i                //QuickSort(a2, 0, N - 1);
        int end5 = clock();
# W1 k+ q+ k$ q5 A  n7 g3 `
& W! ~: x2 b) }2 c1 v: k+ m
: H4 i2 ]2 l' a( M/ ?. q5 }/ Y5 v        printf("InsertSort:%d\n", end1 - begin1);
        printf("ShellSort:%d\n", end2 - begin2);
; o0 g0 @0 e  W1 K- c) w- B+ x        printf("SelectSort:%d\n", end3 - begin3);
9 w, y) z& H6 g$ T; C+ B        printf("HeapSort:%d\n", end4 - begin4);
3 |, [3 g9 Y9 u. t# b* _3 u: Q# n        printf("QuickSort:%d\n", end5 - begin5);

        free(a1);
* ^3 S, T+ R# F. N, [3 W4 I        free(a2);
7 t9 L% X( A( o7 i, e3 D- l        free(a3);
        free(a4);
        free(a5);
}

1
. n  q! C3 q1 z- ^) o1 z1 \4 A' d2
3
4 z6 r0 b: `, ^+ r4
) i6 y2 N4 O! Y) ]: N5
3 r! G9 p6 g4 O. A9 H, H6
7
, S* F$ E! Y8 Y7 a# t8
9
10
+ M8 u/ V0 l9 F% m0 k$ g5 h11
12
13
14
15
16
6 k( Z. k% D, o/ N% f17
8 Q$ @& p# x  G$ C18
19
20
21
22
23
% z8 r$ k- t) {9 N24
25
26
27
- ]7 h) r. [, |28
( T: ^6 b, I" ~$ V: L- J% o! @29
8 ^  G9 _* `4 u30
31
. v% v. H+ o3 I. G32
7 c& k1 E4 k' P- Q7 F3 g! o33
34
35
: {* P6 D1 R9 x: c2 |  D36
/ D4 q  P* m! c0 c+ l5 c37
38
39
9 x4 [6 e7 \; C" u5 j- S7 h  W40
/ X5 r9 T4 ^" _* {4 R) Z41
42
# \: K, V$ v9 L: _3 A# ^7 d43
) j9 b6 R3 s6 D44
45
46
, H3 c. r9 l6 _$ k- m4 T47
48
49
5 H8 w$ Q$ S* E9 b+ k50
: j' ?$ m2 X3 k& v; \4 u51
52
53
) p- [; @9 J3 k2 }( G% h- M( x+ j54
55
% O% V4 @2 \7 C  b) t% s4 m56
6 p7 U3 F# ~% U3 q! h57
58
59
( @$ w* h" |4 |0 C( }' p. r60
61
62
63
( T* G0 a3 W1 G: ~* J' A

/ e/ c6 f- I! e# j$ \% z不愧我们费这么大劲优化快排，多帅哦！

差一个归并排序，后续补上！
& E! ^5 \) n% q1 z+ y
0 Q, j- Y/ {7 N) Y2 J. j不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
0 S+ y( d: f9 [! x; y; S————————————————
版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832
) ]0 v5 O) x  {
3 ^1 v$ C. [% V  `( O, s
. t" g5 l% M8 T+ g) a- v+ Y