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

杨利霞

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

前言
本期分享经典排序：
6 L# Q$ H7 T+ u$ [0 j: B/ j" P; Z
插入排序
) t( u* U: I' `  f; B3 {) u+ A8 S直接插入排序
% ^# x% ^& W# Q- @希尔排序
' H, E6 J' j) _" R选择排序
直接选择排序
9 Z0 V! X1 b% N( E) Z7 E堆排序
, ^2 |1 m$ E6 ?2 b交换排序
  {' v9 p- Z7 N; z- N冒泡排序
快速排序
注：讲解时默认排升序
0 N1 E* X. y: J/ |
" J( `, j8 ^" l! ?  M" r插入排序
$ K% [7 O3 b; z1 K. h直接插入排序
) C% u8 ]& b' C% ~思想
插入排序，就像玩扑克时，摸牌的过程：
7 x9 R/ }' P- @' z* ?( p
4 i2 B$ F3 Y+ T4 i; E最开始，左手没牌，右手从牌堆中摸
) c9 |$ g5 ^9 D& l, p3 \1 c& E右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
如此一来就能保证左手的排始终有序，摸完牌后也就排序完成

  M( T) U7 f. Z8 y! y8 U
操作
+ k7 m: O* D! Q; F  q0 J设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
% h$ r3 Y8 ^/ `单趟排序：
每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
是正确位置：插入
5 E& o7 [/ C3 b* V; _+ J$ L3 W不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
整体趟数：
1 g9 `) J6 H' y若元素个数为n，需要排n趟
6 q% x/ {1 q6 ?0 [) _% yvoid InsertSort(int* arr, int sz)
{
        //end + 1 < sz
        //end < sz - 1
        int i = 0;
        for (i = 0; i < sz - 1; i++)
        {
                int end = i;
                int tmp = arr[end + 1];
9 W1 A5 I. m) _9 U6 g
                //找插入位置
. l, E5 c8 E( I8 e3 q0 {' E                while (end >= 0)
                {
: q+ W# r; E- {1 g( @% S( l, b. c                        //不是插入位置：当前数据往后挪
                        if (tmp < arr[end])
1 p/ C- z7 o8 M* j% [8 J. q5 W                        {
- V" ]& T! ?* I' `* ~8 M  [! v                                arr[end + 1] = arr[end];
                                end--;
* G* T) ?( y3 t' K8 K                        }
+ `9 a* r5 s1 `1 f                        //是插入位置：跳出循环插入
, R$ o' \  c2 m, f; p* {' u$ ^                        else
                        {
                                break;
5 v6 L: L. q4 M+ z% x$ n                        }
' z# C4 D' a9 d2 d. l                }
                //插入
                //1. 插入位置是[0]，end == -1，不合循环条件跳出
                //2. 找到插入位置，break跳出
                arr[end + 1] = tmp;
        }
}
+ f$ |! S' b/ w
5 d7 [6 {/ q( r7 r" R( j1
& @8 m$ Q# x! S5 M6 P& S* X2
% `# ?$ L2 T# r# S" j* q3
4
; ^9 P& ~, z6 y# _5
+ K. M. j" }3 L  F) n7 D6
( E( i' X6 e5 O3 I) G7 t2 D7
1 o" Z8 c" W: b8
9
1 i% ^7 Z' u4 g10
11
4 z. [/ b! u9 |' J$ W8 I& R! [  s; q12
% l' s/ X% e2 \! ]: u( z9 ?13
# E1 G& u: M* H) [14
. o% q* j9 o& F9 g. O; F* N$ u15
16
17
18
19
: G/ k& S) D: R20
21
- O4 [; u& |& K, A" D/ f1 u7 V22
23
- d$ N* s. }+ _, b% [4 p: r0 o- |24
25
/ M6 _3 e* g3 D& @2 v; Q0 B8 N1 H* e3 |26
27
28
29
30
31
6 r+ r" c7 N/ Z
$ G1 q6 F: t7 Z% c' V! o8 `4 V2 f
稳定性
) V+ J2 d' P& M- p- O插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以
* E: H- H) z2 F/ ?
6 b  \0 t# H) f3 K2 u! W. D直接插入排序是稳定的

5 b) f& v, m! E% J) p# w2 Z复杂度
% b" \' J  r; i3 u' Z1 Q  x时间复杂度
" f5 Y3 W) Z4 h. G' X最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）

; y4 J4 }( h7 i- P( N" ^O(n)
, r' u! s/ B1 U2 F7 N
最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2
6 w! v8 a) w* d( C" {1 ]
O(n^2)

空间复杂度
O(1)

希尔排序（缩小增量排序）
希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序
0 e$ K+ {6 C7 q3 {0 y3 X
优化思想
增量gap不止用来分组，也意味着数据移动的步长，所以

3 q; v& Y4 a0 x2 O% `. h1 T. Egap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高
; W" A( l0 P' K! T

操作
单趟排序：

# ]  |' r& U8 m/ Y5 C+ l设定一个不断减小的增量gap，也是元素移动的步长
以gap对序列分组，并对每组分好的序列进行直接插入排序
2 j8 L5 w/ Y- E/ N不断缩小gap，并排序
*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
整体趟数：

由gap决定：当gap = 1，排序完成
6 z( G1 N0 x, Z( N2 _* ]注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。

void ShellSort(int* arr, int sz)
{
1 W7 ?) n6 \) ?$ c7 P- ]        int gap = sz;
5 i9 `# T5 {- x2 g1 b' t       
    //gap > 1，预处理排序
! {- t. R2 g( Q5 {    //gap == 1，直接插入排序
        while (gap > 1)
        {
5 q' h& L5 A2 ~$ }) @                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
3 O" m6 I1 Q. Z" S+ I6 w/ @0 s" D                //gap组
; y& d* I. `3 p3 ]1 p  }                for (int j = 0; j < gap; j++)
) D! U1 C- N2 F- O  o+ l8 o                {
) U# D7 ]( z7 v$ ?1 H. l9 V3 G1 O            //end + gap < sz
                        //end < sz - gap
* s9 H8 F5 u3 R+ h                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
                        {
                                int end = i;
                                int tmp = arr[end + gap];
4 j$ w- e* x7 L5 l' O                                while (end >= 0)
# t5 g2 M* D2 h/ W2 ~, I+ \1 |                                {
) O# F' |' A1 ^3 }$ ?$ [                                        if (tmp < arr[end])
. z( J3 _- J/ d0 v" E2 m                                        {
5 J/ V0 _- p# i6 Z                                                arr[end + gap] = arr[end];
                                                end -= gap;
7 w2 [6 M/ ~  f% T2 h                                        }
; q1 {( q$ x! w5 c. j                                        else
                                        {
                                                break;
9 G, @1 b) l8 ^! O                                        }
                                }
                                arr[end + gap] = tmp;
                        }
  b; F, a3 V/ ]. |% `                }
  u2 f) Y! z0 I( u: {: i7 R+ q        }
}
$ m- N& v2 y2 j  ^+ m6 C
1
2
3
& G% ]/ T4 B8 F3 Q4
% A* K" ]! ^$ F9 b5
4 u! C& [! d  g8 x7 ^- Y! {6
- O, N8 L8 e: C- ]5 J, J3 q1 M7
' {; s6 o4 {& X4 O& _7 Q8 F8
8 }/ s* B2 g; s8 a5 `# [/ J6 Q9
10
3 x1 v( n- O. I! Z" n0 l( d11
# r! w4 ]: E6 T9 r, x12
! @$ ]4 H1 g  ]2 Z: O  P3 B. ]13
14
15
/ ]" E+ J. S+ z( B: I( {4 N4 e3 G  M16
17
18
19
6 n; Y1 Z) A. n20
21
' G' E" m" v8 Y  s7 q22
: f: ~3 ^3 m6 A; l2 `  w23
3 ~4 e4 F$ |' ?9 V6 V  e- m24
- Q1 J* e& ?9 D- Z/ h25
26
27
28
29
. d5 [! U( a. y! ]) w# |' l% [7 Y30
31
" I5 \+ h. ~' S- ]! F1 R: O: |+ x% W$ w32
33
34
! \- Q; O; @/ @1 f/ B35
其实就是套上”缩小增量“的直接插入排序
$ K4 P- a! i# D( z4 q

' z/ a) g' l$ y8 V" O* i稳定性
我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以

希尔排序是不稳定的
0 d8 g6 c! c( U' S7 F/ U- f$ c2 H
5 n5 K, x! p3 K7 ]2 o复杂度
时间复杂度
) [& t6 j4 m2 s* {: o希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：

O(n^1.3)

空间复杂度
/ H- r6 z7 ~' D) `O(1)
, \- x- k+ a5 g# Q+ H
7 l3 D' o3 T0 V! A% R0 t0 S$ H* \选择排序
直接选择排序
思想
选择排序，遍历序列，选出最小的元素，交换到左边
7 X+ Z3 I/ Z& p9 a9 I
! e+ ]; d# h# r' w9 W4 ?

优化版本：

4 f% V0 q% Y/ Y6 g每次选出最小元素交换到左边，选出最大元素交换到右边

" C; a9 z; D% E" o( u操作
5 N, c4 _# E7 _+ @# I+ r7 k% ^& i4 r设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]

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

单趟排序：

遍历选最值的下标
: y6 q9 K0 {6 _, E5 i% v交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
（修正）
' V, b: _" D, x% R" \整体趟数

8 d6 A4 G7 w  p5 T- e若元素个数为n，趟数为 (2/n)
: F6 Y$ d2 l5 |. g0 F% \修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标

void SelectSort(int* arr, int sz)
{
        //闭区间: [begin, end]
        int begin = 0;
7 V( F/ Y" t9 W2 ]        int end = sz - 1;
6 A& n) }% u4 F; h$ \        while (begin < end)//begin == end 最后一个数，天然有序
        {
                int mini = begin, maxi = begin;
3 T! N! J; c! u* p' w. T                int i = 0;
                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
8 r3 U4 K9 q3 E" }. G                {
& C! e, r" r  W                        if (arr > arr[maxi])
                                maxi = i;
6 L9 h6 f6 `4 K                        if (arr < arr[mini])
/ E4 R$ m9 w% I" n, S6 E& Y                                mini = i;
                }
5 E5 k) r8 L- A9 u& l
" D4 b! j6 r" _3 |0 P                Swap(&arr[mini], &arr[begin]);
- n! B4 [' s8 @* P2 f& R" L
                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
                if (maxi == begin)
                        maxi = mini;
                Swap(&arr[maxi], &arr[end]);
) ?' U4 A5 m3 s1 N% t
) Y1 R) f1 U$ N, A. q                begin++;
; k% A* S& |4 F( W) O                end--;
        }
}

& F5 z* M+ z( q2 g4 F2 Y* X1
2
3
4
5
6
3 q  ]4 J; n  d3 q1 I" ^' Q7
8
9
10
11
12
13
14
+ ^: a4 C9 p% e6 y( d* E15
' g3 `: x- ]; H, }3 V16
17
' U' o6 D, ^3 z  H; U6 I' g) |) t" j18
19
# ]3 U  \# Y% d$ w! p5 @3 q20
21
22
23
9 J& I% d+ d* ~/ }( ]& I! e24
1 h! V/ ~, \: I  X" ~/ v0 X25
3 Q. \, P2 q( M6 i26
4 r* }  c9 @/ U) H7 v! ~9 \  T27
28


: }+ h, P" C; _% ?. u& s稳定性
选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以

2 b: P6 q4 Z2 w; z5 ~) g4 D选择排序是不稳定的

  M- i% u7 l  I% W复杂度
% L) x" s2 _) j# A6 H: H时间复杂度
最好：
  P# Z8 X: V6 `; {+ t- S# [9 k4 a
: k' @9 i8 c8 N. t, f0 c, Q  ~# ^比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2

' c+ e% S$ o/ h0 [! o6 @7 V交换次数：O(1)，有序不用交换

O(n^2)
& n0 {. a7 n, Z- o1 N# ~$ c
3 H4 F' O% h1 J  Z最坏：
# N5 i( G. d) ]/ R4 g
比较次数：O(n^2)
' f- n4 Z$ n% P2 D7 M
交换次数：O(n)
4 A/ n  ]2 v: s5 U0 @9 ^. i
O(n^2)
/ I2 E6 F' I. {
9 Y, t% F; B1 o" W; _空间复杂度
8 o# p# k$ |' OO(1)
0 y6 O2 s( R$ C
9 h8 L, U  U  F# ?6 F堆排序
6 J( F" Y: D1 T6 R8 p思想
& |9 b/ O+ t6 l" Q- S6 G- m" q利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆
" ]' W% X1 ^; ~5 `/ ^


. S/ B; [! v. A: r' z% l操作
建大堆
4 [3 v; |% N0 f+ _+ y单趟排序：
选堆顶和堆尾的元素交换，则堆尾的元素排好
# e( y- o! L- U3 h每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
整体趟数：
" j- S/ m  d, u! N若元素个数为n，则排n趟
void Swap(int* e1, int* e2)
{
- f7 w/ ?1 H7 @# J7 c        assert(e1 && e2);

        int tmp = *e1;
        *e1 = *e2;
, M7 f# j7 m$ ^/ k9 R        *e2 = tmp;
- T9 H- `6 X" c3 Y2 @: G9 C+ Q# c}

void AdjustDown(int* arr, int sz, int parent)
8 ^2 \/ L2 F) d- O{
        //建大堆，排升序
        assert(arr);
       
    //默认大孩子是左孩子
# G7 U4 u$ R& d" |        int theChild = parent * 2 + 1;
7 I. e9 p; e/ z5 c* W( ]( k        while (theChild < sz)
        {
        //如果大孩子是右孩子则修正
+ x& T, l- I+ U- L                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
7 N$ U7 @3 Z5 s5 m! X                {
                        theChild++;
! W  V, U6 F3 `' @1 W4 V2 [* A                }
                if (arr[theChild] > arr[parent])
                {
4 C) @# {5 @- d                        Swap(&arr[parent], &arr[theChild]);
            //迭代往下走
                        parent = theChild;
5 K, c- U# _2 O' f* s                        theChild = parent * 2 + 1;
                }
                else
                {
; C. y. J, {, M                        break;
/ D4 i1 L) c, ]  ]! G! p                }
        }
' I& X1 h* q) K* r' \. f8 w( O}
4 V) o3 W, M; x7 l' D& L  a
void HeapSort(int* arr, int sz)
{
* t" O; r$ o' M5 d* V) M& C0 p        //1.建大堆
        int i = 0;
        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
        {
. c% b0 K  q1 d# B                AdjustDown(arr, sz, i);
8 \6 @! v: f; r3 r! F# p& H        }
1 w* Q( d5 D/ O4 @2 c1 t
' u( @- T3 y2 |  Z/ i; v        //2. 选数
        i = 1;
        while (i < sz)
, U7 n' n8 m% M$ R+ r        {
: J2 m: U6 d- Q                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
9 ?3 R/ G! k) R# N* j  z- T  \+ `                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
1 h$ s7 v1 X  Q+ K) |                i++;
        }
9 y6 H: S7 ?4 o# k& \% L: X}
; x9 i! B1 ?5 e/ A- g0 z6 x
1
% Y4 e* K" a1 T, w2 W  z! S( f% Q2 k2
3
# Z7 w- o9 Z0 M0 a6 o4
$ |8 g3 B2 S9 a7 s+ a- r5
6
" L# w9 n+ s* O  Z% Q/ F  H7
$ \1 I0 l* Z" z9 Y% n* M8
$ J: r# H6 z+ P  h$ @9
10
% ~: D3 ~# U, r( \: E: W% H11
( u* X6 y1 F& }( G) F12
13
8 u9 ~- g# o- _/ o6 y/ W& B14
15
16
# U' a' {" b1 t4 V, ~6 E17
18
* l5 T& N; H0 X; A/ A5 ^* v19
/ j* N! n0 y* C  j( l/ H* C20
& K: a! ^; Y5 E$ j21
22
! C) N+ f) j9 j/ F# V4 l+ s23
7 W! d. r( H. s6 T9 O$ a24
25
4 l' w( ^& k7 m/ Y" W3 l0 l9 q( X4 {26
# k# J9 k  r* F0 q3 ^27
28
29
30
$ H: y4 u; V0 l1 b8 v31
- r- B% j( x, Z3 c; t! x32
33
0 @( U4 S% a) ^+ a6 n- H6 D5 B34
+ N$ u- @. |: V1 I$ ~+ S) q35
36
/ e7 K) Q, Q/ x% W* r37
2 {0 [; ?- j+ P( t+ P# k/ l38
2 x- Y9 Y+ O, s# Y2 t1 Y0 |39
) p9 Q( S$ v9 r2 e; k3 X) Y40
* S- m% G6 H% A5 o) _9 J* \  _; y41
42
43
! ]2 S8 O  J  ~8 l; A9 a44
# e# T. b, ^# s3 \) `5 a45
4 b" S. }& B9 H) [4 P46
* [/ z9 v- P- A& [47
48
) X3 r+ h. `, C& _! f49
50
. j4 ?2 i* o4 h# S8 B  X' I51
52
53
54
55

9 Z+ ?& ?% i& m0 u
* V& c* a2 _  {* O6 y8 t稳定性
! X/ ^7 H3 V8 k; j建堆和向下调整都会打乱元素顺序，所以

3 n2 e7 G% d) j, x7 F' Z堆排序是不稳定的

1 {& W- J$ s& v7 k0 ^% ~复杂度
$ f6 [6 F# E' ~# J- H2 M时间复杂度
9 R# j* `2 W3 B) K单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为

O(n*logn)
" l5 y) N# f! _) L
0 K0 [% ~0 Z2 B4 I- y; H空间复杂度
, z/ `3 J# D+ l+ W% M; ^! N原地建堆

8 `# G& {3 j& ^+ U1 }7 n: nO(1)
' O# i# Q$ C5 `* j
6 ^' g8 l" g% u/ j6 }, i* d交换排序
冒泡排序
思想
冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素
+ R  Y* `# n5 u$ B: S( r! h
4 Z+ m; Z$ a9 z* I' h1 |

/ i+ K2 @6 ?* C. H6 k" H操作
2 f% h6 b- `/ n) H8 `7 d" z$ e单趟排序：
每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
每趟排好一个元素，所以需要排序的元素每次减少一个
整体趟数
; Q( Y2 X, c+ [" g若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
2 U. |, k0 |+ G! D! d" w- ~6 mvoid BubbleSort(int* arr, int sz)
{
        int i = 0;
        int j = 0;
        for (j = 0; j < sz - 1; j++)
        {
                for (i = 0; i < sz - j - 1; i++)
                {
( C. Z+ q$ U% {; G0 {& |/ }                        if (arr > arr[i + 1])
  W% u2 \0 w6 ?                        {
6 V' V2 J" y/ `4 J                                Swap(&arr, &arr[i + 1]);
: }- D4 S  ?$ w( B; w8 }( d% M                                flag = 0;
                        }
                }
5 f, G. W0 {( _' k3 u/ C        }
9 B" z) ~! [6 Q- Q- ?2 b, R}

" P1 ]  s/ h* P2 n5 m' P( y1
: v6 R4 \3 F9 D6 Z* g2 A. I2
5 \- e3 ~/ k$ \0 i& s; w4 |3
4
/ u* L0 r' ?- M  n5
9 D& s2 p# a8 x0 T% j9 R6
7
8
1 q0 I9 J1 G' V$ F9 |  b, u' `$ @9
10
. e5 N. \1 E/ w. t; a$ }9 a11
12
13
8 J6 A% ~, A4 [8 B, n( A14
15
, W, M+ `- }/ m6 L1 Y; I+ G. P16
' w1 @3 e. K3 C/ {* {优化
当遍历一遍发现序列有序，直接跳出
; Z/ s9 h( A! S2 L
void BubbleSort(int* arr, int sz)
- {; p; d* B+ B) L: \+ o{
+ |) B( d/ }( h1 t        int i = 0;
        int j = 0;
        for (j = 0; j < sz - 1; j++)
2 q" f( c, i7 E' T3 S. {6 @* W        {
                int flag = 1;
8 M6 U; ~0 \4 O                for (i = 0; i < sz - j - 1; i++)
                {
                        if (arr > arr[i + 1])
                        {
0 R0 e1 S' ]3 i; @$ g5 ^                                Swap(&arr, &arr[i + 1]);
                                flag = 0;//不是有序就置0
                        }
                }
                if (flag)//如果一趟下来还是1代表有序
' v* W: D$ D8 _$ }9 L+ \" |$ J                        break;
        }
- g: H7 Q. }1 j6 C}

1
5 d) w2 B. ]. ^, y% _  }% m' e2
1 d8 c( s" B+ Y1 W; {9 S, |3
4
5
6
7
8
" L- z3 _' E: Z3 z3 l" V4 c9
3 i8 j2 M  W% c6 W( M10
11
3 K$ }! N. V" C  W; I12
13
2 ]) A/ T% k3 B4 I14
15
3 B% X, C/ \+ K8 w2 q. q; I16
17
& C5 z7 v0 {% x, B( h2 C! s3 Z18
19
) Y  f. U3 E$ u3 ?1 E4 c

稳定性
相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以

+ {' J: q5 i5 \5 s冒泡排序是稳定的

( v1 J* s% q1 x: k8 t- n* D复杂度
时间复杂度
最好： 当序列有序

0 q+ a8 [9 N+ u3 l/ b: r3 `  i" a未优化：
1 S8 H2 o7 W# U# [4 r3 K' h
O(n)

优化：
5 {; @- D8 n. ?$ }
O(1)
7 \5 I# ]( ^- V7 H' f8 v: `
/ _$ y- h  h  H% T( a2 I最坏：要进行 n-1 趟排序，每趟交换 n-i 次

O(n^2)

空间复杂度
5 V. s) U/ _2 Q/ C3 FO(1)
8 d- ~8 F, K6 x% y
+ P3 A* g  ?; p- `8 Y( S快速排序
5 n8 B# q# \. F1 E. T" C思想
分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。
, a9 ^; z  _- {
所以快速排序可以用递归来实现

  b' p: Z: _0 j7 _2 C操作
3 ]& Y! r+ Y6 L/ `# a有三种单趟排序的方法：
5 L1 A6 u" N2 }) c
Hoare法
设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间

, U$ k9 ~6 \; M5 u) U' `, @左下标 L = begin，右下标 R = end
5 t1 u/ J+ ~( S! I. w! C1 b& C
设 L R 相遇位置为 meeti
/ T4 A+ m# z* P, A) v2 Z+ |
​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”

8 [3 m% ]) z) Y​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“
2 E6 N( u1 r) p* v7 J; s( `
选 键值的下标 keyi

左1位置作 keyi，则 R 先走
8 M$ N8 \8 r# i  h" x/ M右1位置作 keyi，则 L 先走
' f+ d6 S& d% S' ~( e' tR找小，
" G; Q" G7 t. i$ l
找到则停
% e4 l0 b) c" Z  F% l0 w' ?+ B8 O遇到L，则交换 arr[keyi] 和 arr[meeti]
2 o( S1 V$ C3 H" Q$ I7 KL找大

找到则交换 arr[L] 和 arr[R]
遇到R，则交换 arr[keyi] 和 arr[meeti]
: y/ }+ v/ x/ y# X6 |# _
8 h9 i: \; J, K' O0 r8 T! T" Z
解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
答案是肯定的：


- ^6 O; v& I5 t# x+ Z0 Z$ P

//[left, right]
int PartSort(int* arr, int left, int right)
{
; W5 s1 N: g$ e0 O        int keyi = left;
        //相遇则排好一趟
, h. l7 ~8 e0 ^3 x! v( r/ m        while (left < right)
        {
                //R找小
        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
                while (left < right && arr[right] >= arr[keyi])
+ V2 d, X0 e9 Q* l( g) @                {
' a7 E4 x5 _) ^: W* B) ?: M0 g                        right--;
( J3 [. t% e! M0 ]                }
. E/ |: b$ y" J4 {8 N5 h
                //L找大
$ Y; S+ z' W* a) q; j3 M4 x                while (left < right && arr[left] <= arr[keyi])
                {
- Z1 s% v4 {1 Z) Z- ]                        left++;
                }
" w3 _( N1 `' X0 z* M& Q- T2 Q               
        //相遇就不交换了
, K, l6 l; `5 X$ C                if (left < right)
                        Swap(&arr[left], &arr[right]);
- z4 C- f- }) }% _' |3 I0 e        }

        int meeti = left;

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

; V# v- V" Y0 H5 ~! Y% ?        return meeti;
}

1
1 m8 d+ D" T4 ^' o5 I! S2
3
+ w: u7 w. V6 o; Q4
5 p. M1 p1 t8 F! o5
( D4 H% D1 _! v2 F2 B6
7
! F: h* x1 L# n# }" G& j0 _8 u8
9
* Y5 V( K; \6 Y5 R5 S: p7 \# _10
9 W! K  W# B* \* p0 W11
: c- O$ t! b! q12
13
14
# D0 m" V9 Z# e% G) Q! |; h* ~15
  b# y0 s- ^/ d  d- p3 ^& `16
8 v3 p/ r/ t7 y* B( k- b17
) G: c3 W, [* {& U18
: O- U3 q" m9 ^8 B0 ]$ q19
20
21
* m1 H  Y6 p- ^& s/ M1 @3 T22
23
24
( [) s0 c. Q4 }  C# i25
26
27
! I/ Y5 y/ h% ^* g! l! S28
29
30
! K5 ]3 Y' x7 X/ r) P2 T7 p0 t5 ?31
" \2 a" H$ e; E+ @: L+ k# Y  j/ c32

; L/ S1 r+ P5 H3 p6 [- ^
4 S- a! H" @* L" ?6 o8 p, l9 B解惑：为什么key要选左1/右1，选中间不行吗？

6 E* p4 x& Y& U  _, L
可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深

) ~9 J* F# K" i' O% I- [! |
: R8 P4 ^+ t7 y1 A7 C" w3 Z/ o

& D* X, t/ M1 ^, [7 X非常容易栈溢出，怎么解决？针对有序情况，优化选key

优化选key
: ^% M- w$ A5 C# X/ _. X随机选 key （是一种办法，但是不那么彻底）
选中间位置作 key
8 \7 m* C+ l/ z9 Y解惑：那先前实现的单趟排序不就失效了吗！
：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑

解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
2 o  M! S. u$ Q4 m- @前辈给出三数取中的方法
  D) ?* g( o$ E
三数取中
  T. d: G" @9 R! t' S在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
! d7 l* {7 ^; l8 Z这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
% P! C( t% Z9 w3 ^* i2 R/ K) o6 T优化选key后的Hoare单趟排序：
5 u/ q1 M4 d! v! I! E4 {
int GetMidIndex(int* arr, int left, int right)
$ l$ A: e+ w  L. r/ A  \* O9 z1 \{
3 u- j& ?+ v  y        int mid = left + (right - left) / 2;
//  int mid = rand()%(right - left) + left;//增加了一定随机性
        if (arr[left] < arr[mid])
        {
                if (arr[right] < arr[left])
                        mid = left;
                else if (arr[right] > arr[mid])
                        mid = mid;
                else
                        mid = right;
6 U% i1 l8 `. L/ c$ i$ r6 E% J        }
! H  x5 `- c9 k5 |$ G3 H* f9 v        else//arr[left] > arr[mid]
. y$ n" L& p& H        {
& n; J- @2 x4 P7 @1 c& `  ^; }                if (arr[right] > arr[left])
& f# V+ [& X2 G! C6 _                        mid = left;
                else if (arr[mid] > arr[right])
                        mid = mid;
. S2 c( _& M/ P                else
. ]' h# x1 n1 l& P                        mid = right;
) x% W( O# k; L2 T5 L        }
        return mid;
; \4 o( s; r8 N0 P: a}

' S  N. f% h  C  N- [( E( Lint PartSort_Hoare(int* arr, int left, int right)
{
  A( k6 C& i( n* j, H" f5 A        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
        int mid = GetMidIndex(arr, left, right);

8 }; T0 |- M. f8 N1 P1 ]+ P+ w9 G$ D        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
( X. h/ a) B4 Q5 |  t/ U7 u4 a        Swap(&arr[mid], &arr[left]);
: D: p& X9 G# [3 S( C" A3 @
9 V; ~" i& u8 Z3 n, V        int keyi = left;
        while (left < right)
        {
% o+ C$ W- @5 s" a* O1 J' j                //R找小
                while (left < right && arr[right] >= arr[keyi])
9 f: L, t! ]$ a  Z; U2 C' `                        right--;
- C- d5 u" S3 _
                //L找大
; |" a" g0 |% c, }4 J" p6 J% k                while (left < right&& arr[left] <= arr[keyi])
. d: S8 I& o( M                        left++;
- E8 T+ L% U  M. Y# c# p$ P9 Z
5 u; e- m& ~' K# d- A: Y- ^                if (left < right)
" G5 Q" F$ N$ T9 r' d$ b                        Swap(&arr[left], &arr[right]);
        }

        int meeti = left;

$ E! _7 m) z# M) v3 j0 H* m9 K        Swap(&arr[keyi], &arr[meeti]);
) u/ c0 ]9 [/ e+ |4 e
        return meeti;
}

1
3 e/ V7 i' @: e0 f. c( W3 L2
3
4
# ?' V0 w7 ]: G( a; _. H5
4 @3 H6 y" b* h  _- }; B/ n; e2 f6
7
8
9
# C, \4 Y7 G, w* a. Q+ n10
11
/ a- f. x/ f7 I/ X( @, D12
13
; @  q3 |% ]9 s0 r; K) G14
15
* H$ _% x+ L+ Y8 v16
4 ]; E. ~$ ]. `6 R# x; a17
18
19
/ n% z" E  j8 R- ?0 [+ F8 ?20
4 Z. K5 O: l: V+ e21
22
# P# |/ }  B3 [$ U; H3 L23
$ I4 [7 W* b+ f6 j+ A1 @5 e8 {24
) o  f( n' F, i6 Q: G( K/ m25
9 S& N* M3 W+ K# U: |3 _26
27
6 R- f; r8 Q- @  U28
29
30
31
$ i9 S7 \# g) Q. |% O32
33
34
. k- v7 d- o# ^; {5 T% @2 t* R" b7 m9 ~35
+ q$ D7 b8 E6 O+ ~$ c) `36
37
38
% k) p. Q. H& C. ~% [* b% T* a39
40
: X4 r, _8 b( o) F3 U& k3 S2 S41
# f2 W# h7 g" Z1 z3 {5 {42
43
/ B  m& Q/ R( C' [/ Z! g6 C* z44
45
* V* [/ Y0 n* G# n# f7 q: n( \6 Y# M6 y46
& c2 h2 ~1 v( R4 B47
  z. {8 [3 n; |6 y, Y48
49
50
' V7 T4 Y' t' i' w  @) X51
$ Z* I* O9 E- P0 U# `52
53
3 Z8 v! |9 p, f) S  F6 V54
挖坑法
初始状态：L作坑，其下标存为key
2 x$ s1 j, L2 D& Y" x; J(1) R找小，扔进坑，R作坑
, ~4 e! d7 I* k! q0 X(2) L找大，扔进坑，L作坑
; {2 T! o: R' r1 N: B  }1 I  C* _重复 (1) (2)
最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]
8 @# C0 q/ b/ g& A# G8 q' _8 w

- r$ M' |! l, B6 z3 Aint PartSort_Hole(int* arr, int left, int right)
# m: P2 p, {! W: n{
        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
7 g8 B* [1 G1 h6 R. O1 ?! i# v6 f
6 I5 a, j; m7 a0 g' |) h: T        int key = arr[left];
        //L作坑
        int hole = left;
7 E" E" c+ X; K        while (left < right)
" f3 c2 ^- u4 l+ ]* T1 w+ D        {
                //R找小，扔进坑，R作坑
2 j/ q/ ^$ @: _& p. M! g- \( J- r                while (left < right && arr[right] >= key)
                        right--;
                arr[hole] = arr[right];
" e7 G! s' }) P                hole = right;
" ~, L7 N; W5 u3 R# ~1 o1 e
+ _8 G6 [& v* o% o8 ]1 k                //L找大，扔进坑，L作坑
! f1 B' C7 L! G( }- f% ?                while (left < right && arr[left] <= key)
; @1 L7 I- k: N. t4 x2 {3 N                        left++;
                arr[hole] = arr[left];
& ]& y: L2 v+ ~7 `- D$ m2 A                hole = left;
4 u; \6 p9 I+ A5 M        }
$ y" K+ _8 e8 i6 K        //meet
: W. V( P7 G9 l4 P        int meeti = hole;
        arr[meeti] = key;
; r# m8 k/ E$ D. K' r
- [3 R& y2 b9 z' }+ N) v9 ~        return meeti;
}

1
2
- p; h% R1 k7 S- ^+ Q) g5 M9 F  v- m3
4
5
6
7
8
- }" d9 B; O/ U1 t% X9
" u8 |" I/ ?1 F10
11
12
) K+ e( d5 S3 u: Q13
14
15
2 I" A4 R1 Z: d9 c+ @& ?16
17
& P# J* C  K; a9 @18
# @3 ?2 ]+ P2 H. [! D* {19
20
! R) N: n3 E- m* ]- M0 e1 V" p- C% E21
22
23
24
25
0 T- W' |% Q4 z26
6 p3 J4 l- |3 |/ {' e+ J27
1 F* Q) q' C1 Z9 C" E8 L1 ^28
8 E8 a7 J) |, I$ \+ f" n* Z前后指针法
此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多

cur找小，找到则停
++prev
如果 prev != cur，交换 arr[prev] 和 arr[cur]
如果 prev == cur，不交换
! N. s* c4 e; J& o当cur越界，代表找完，排好序了
/ |) P. K9 z" }  k+ x2 Zprev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低
3 w# X' C3 M& l
, G. X0 |0 D( v9 J2 R  B) ]! q
! k' _; o$ r- h; R; d4 f. S& s
; a8 x3 s  J8 `3 q( B$ }int PartSort3(int* arr, int left, int right)
{
, y1 s4 T* ~: F        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
       
  //int key = arr[left];
        int keyi = left;

! Z, J; i  k) ^0 J  p1 S/ T2 Z        int prev = left;
        int cur = prev + 1;
       
    //cur越界：找完小的，prev的左边全小，prev右边全大
        while (cur <= right)
        {
        //++prev == cur 没必要交换
                if (arr[cur] < arr[keyi] && ++prev != cur)               
                        Swap(&arr[prev], &arr[cur]);
5 m; k. O8 ~/ }# E) \% {2 I
                cur++;
        }

        //键值存是的值：
* W) H8 Q5 P2 G5 o% ^        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
, h/ p% B; b3 m6 d. Q7 W        //Swap(&arr[prev], &arr[left]);//这才对
2 T: N! t/ t" [1 f8 w    //键值存的是下标：
5 i# g0 R/ F) z% ^6 W        Swap(&arr[prev], &arr[keyi]);
; a: |! |, E; E: z& v, c/ ]" Z
        return prev;
+ u9 J( N0 D9 L4 |( W. C}

+ c. k  }* B" p6 P* m+ q# b& y1
2
3
& N4 k3 |; w, u6 ^0 o4
5
  y8 O# l2 X, \2 ?6
7
" {5 a8 }. E9 k4 \2 @+ d. l8
9
: ?  S) Z. M5 C10
11
5 }) P" `' i4 |1 J12
9 P+ X! Y2 B, u8 S13
14
15
( n* ^0 T4 u+ F16
! o! W" m& f' N* i2 U3 ]7 \& }17
  q( e' n. R  S; R4 _# P18
7 |) [& [7 g; q' |' j: y! }19
20
6 ~0 T& I2 a, l; L& I# O21
$ H& O. v9 I/ I* k& m& N4 J22
23
5 B8 y* \  }  j' }$ C9 ~$ c24
# l* P1 V. ^9 Z/ V1 z; [; M+ _25
* B/ D' K" P5 K( o1 K7 X) ?26
; K+ N& ]5 L; e; X6 V) p9 l27
28
29
& j- T8 R0 p& \, T整体排序
递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排
, m1 h) `+ H% w0 m5 R) L
3 V7 K  N: E: ^, X//[begin, end]
void QuickSort(int* arr, int begin, int end)
! X: I/ j/ M/ @) }{
# v# U7 T' J* v* ?4 x( M. Z        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
        // [begin, meeti-1] - meeti - [meeti+1, end]
6 z2 H5 M: t6 n$ ^% X: ?                //1.begin > end:超出范围
                //2.begin == end:一个数天然有序
    if(begin >= end)
$ O$ ]- f# Y& c, P1 O- w+ N        return;
9 ?3 k' s, X/ b1 K/ g
/ x  m8 V3 d& E                //排好meeti
                int meeti = PartSort3(arr, begin, end);

                //排好左右子区间
$ Y8 C8 m* c% J& @+ U                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
& \+ S8 d7 p. o  ^" P2 p        }
- m0 ~1 j6 F& j) z  w}
0 e# z. T( C/ P, u
( E1 i. w0 L3 }1 L! h1
0 t  q! B% {# B. O' @9 {2
3
4
& Q+ p* ?9 q' G0 W; {. l5
6
7
8
9
10
11
12
13
14
15
16
17
18
…

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

优化小区间
# \) i' W* g, M! s* W

如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序
- L& n0 l* @" j% O1 M! W; |! K
那什么算是小区间？

8 a* K; b( N' I% H% z其实小区间没有确切标准，8-15左右都可以的


这里就把小区间定义为 含有 8个数或以内 的区间
( O& X1 q4 ], r5 Y
//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
        if (begin >= end)
% S" L$ p  S8 S0 G9 o! v                return;

+ d/ ~  W1 d+ O$ R  C& l1 D        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
& ~, o( I* M0 ^* w: R        {
                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
: e; e5 y' E) ?                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
        }
        else
        {
  ~' C, e8 `9 A, q) n. v1 E# {                int meeti = PartSort3(arr, begin, end);

                QuickSort(arr, begin, meeti - 1);
1 Q- K+ A# f* b" C$ U) m% q0 B                QuickSort(arr, meeti + 1, end);
        }
}

1
1 ?3 s# U$ i4 {" d2 C2
3
0 C5 F# v1 d6 A; B" j+ V" W3 V4
6 p% q/ Z) ^3 P5
7 r- x% L# Y; z% u6
) P, n' [) v0 f& f3 g" y7
8
9
5 ~& S! a! v3 B10
11
12
13
14
15
16
17
. ?/ l  x" ]0 E& U18
8 L5 J* A, F% A- \5 B19
* u* v: }' r; u3 p" j, {" j- l; ~快速排序非递归
为了解决彻底递归深度深的痛点，我们来试着把它改成非递归
# u8 f5 G+ z4 i& N% \4 I; r
思路：
递归深度深，栈的空间又小，会栈溢出…

2 F  G* w8 o5 f: U2 X那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！
$ n# @# r$ i( C# g) h
) B; g* M+ C4 v4 _" n核心思路：在堆上创建“栈帧”

. \8 m- U8 M& r  i5 ~$ j! j快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的
8 O# Y6 r& c1 n


在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：
+ a1 a+ [- I3 g* y! i
先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
{
        ST st;
* }, s7 ~0 M. Q* @. Q1 }        StackInit(&st);
2 q: b6 m4 @: R- K/ z( W       
    //先入begin
        StackPush(&st, begin);
: Q# P* N1 M; @. n  \" N0 Z5 m    //后入end
& I$ f" e  r0 [" B1 f. h- ^        StackPush(&st, end);
+ _1 T/ Y4 n% l* r
# y- F5 N  {: ?/ J0 ~        while (!StackEmpty(&st))
        {
5 ]% H. |, S# d                //先取end
                int right = StackTop(&st);
- d( p0 D3 w, k                StackPop(&st);
                //后取begin
                int left = StackTop(&st);
, T" [4 z" I4 ]9 h                StackPop(&st);
0 e: o% H1 d( F- x% S3 g
                if (left >= right)//1.只有一个值  2.区间非法
$ W: L: S( D4 \- |" Y( R                        continue;  
                               
# K  r* ~4 M( u- y  H! ^6 {                int keyi = PartSort_Pointer(arr, left, right);

, c7 O! z  g# Z/ p8 q/ @8 a                //先入右区间
                StackPush(&st, keyi + 1);
                StackPush(&st, right);
  V5 R6 p8 R% z* h+ E                //后入左区间
/ J; w2 \, t3 ]6 Y                StackPush(&st, left);

, A' C( L+ G* n( N) y6 ~                StackPush(&st, keyi - 1);
        }
/ B) F& l, M# K) ^7 S2 E; F
( V4 d: r: B" G        StackDestroy(&st);
9 k4 _$ v& A# U% V; A) D, D4 B* t}

1
2
5 ?7 c# ]8 H/ V% y$ K3 y7 J: q3
4
( |6 w2 x3 F6 T# x8 z8 J  D7 K5
/ U2 G: X: A1 ]6 V) `0 s. M6
9 y; `6 T! a& o) E; x2 {7
8
2 O! t* Z9 e6 z5 S  w  C9
& @: _. ]- O0 Z1 |10
11
12
4 ]- Y; k4 Q9 P. g  h8 X# W% T' [13
$ h3 a. M+ r8 q4 g: P2 a& Q14
15
: }" V6 P: C0 \+ V, n& _16
17
18
0 |4 V0 ^9 N5 p+ V' \" A% f9 b19
20
21
0 `! c* S4 ?( `  a6 `* y22
23
24
25
26
3 h, e. C; d" U0 a6 n27
" k6 H2 P% [' f* G4 L, {( a0 A28
& v7 D* m2 `( c+ L, n+ w+ c+ \; {7 a' }  o29
30
31
- k) d  o( i6 v& [' q  ~32
6 P& k) n3 t! b33
; w9 s& F9 O" `1 p7 ]) ^: P1 H34
35
数据结构栈的实现可以看博主之前发的博客

8 a3 \  g" O& M- l! T
归并排序

7 T! |$ X- y3 b+ \5 {- i0 Z…

2 @8 x2 q* s/ W性能测试
void TestOP()
$ q; L7 A3 ~% }3 r7 T{
        srand(time(0));
        const int N = 100000;
' t7 k$ i6 p; Q, v' s4 |        int* a1 = (int*)malloc(sizeof(int) * N);
        assert(a1);
        int* a2 = (int*)malloc(sizeof(int) * N);
        assert(a2);
+ S$ @" @  ^* J0 {: G8 b, ]        int* a3 = (int*)malloc(sizeof(int) * N);
        assert(a3);
        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
* R6 p$ o9 A1 ?! i3 }" |        int* a5 = (int*)malloc(sizeof(int) * N);
        assert(a5);

6 h3 i' k; {1 L1 w, D; f        for (int i = 0; i < N; ++i)
        {
                a1 = rand();
( b: C- y/ |: Y% B- U0 L7 H. N: a                a2 = a1;
                a3 = a1;
                a4 = a1;
* M1 ^7 y$ Q. \9 u% V                a5 = a1;
- g& y9 }) x3 u' q3 `: U& W        }

        int begin1 = clock();
        InsertSort(a1, N);
' Q$ s# K8 J0 h% D) I4 |4 U        int end1 = clock();

% C) M0 a6 Z* J0 W        int begin2 = clock();
# f3 `3 m# Q9 I7 ?# s        ShellSort(a2, N);
* R* s3 i# }  f: |" o' B7 i/ z5 Z        int end2 = clock();

        int begin3 = clock();
- h, F  N1 _3 y/ H& J3 F        SelectSort(a3, N);
* t. t- y' e; R8 v        int end3 = clock();
9 R% M. I. ^9 U$ S( t0 X0 I
! B7 `  \' T$ D( `* i        int begin4 = clock();
        HeapSort(a4, N);
9 q9 z# f/ z0 u/ Q        int end4 = clock();
9 l! O& z) k9 z9 M
7 D0 e8 i' r; m        int begin5 = clock();
1 {3 Q* E" i' ?5 f7 w        QuickSort(a5, 0, N - 1);
& p. O9 e3 f# x- U                //1.中间key
6 G5 C. P$ k; a6 F7 m7 S# E. g                //QuickSort(a2, 0, N - 1);
7 B+ r- e: I; J: _* Q2 Q* u% Y                //2.三数取中
4 n$ i* p+ E- T8 x9 K                //QuickSort(a2, 0, N - 1);
                //3.小区间优化
                //QuickSort(a2, 0, N - 1);
        int end5 = clock();
* f& y, a, g6 g  \
3 f, c+ A' N( j; h, E$ k' R: U  M
        printf("InsertSort:%d\n", end1 - begin1);
        printf("ShellSort:%d\n", end2 - begin2);
, M" t( `4 q2 z8 Y        printf("SelectSort:%d\n", end3 - begin3);
        printf("HeapSort:%d\n", end4 - begin4);
        printf("QuickSort:%d\n", end5 - begin5);
! i. o& ]- T4 q5 r0 U7 C( v' A
        free(a1);
* a  P' T- H! r( d+ U        free(a2);
        free(a3);
        free(a4);
- A! S5 W0 i: `3 Y$ O* R9 Z        free(a5);
  }" G* g3 E! s, v}

  \  J3 o$ h  T/ ~. d. J+ N1
; k6 c* U* }2 T1 P2 g2 j, O4 v2
1 R5 h. \7 R0 ?1 y" j& l3
5 u! o+ [# ?$ c! u4
$ W9 @* j( Q: u' M7 y. I2 H5
8 |! K8 ]2 q' L6
4 n% {9 z2 P% v5 M+ F5 q7
8
9
10
11
12
- `# f" c' U. ?2 M3 G13
0 G1 k0 Y# o$ h  r! U$ u: _14
15
16
17
18
19
9 I/ g3 c+ N+ D. |20
6 V* m3 f+ \" b21
22
6 P' L$ v( K+ g* f23
2 Z0 V- s) N3 W6 ?24
25
, Y" Q( f  k: M/ B7 n26
$ ^  U  @% d# @6 y' j27
0 G8 d6 I% a7 f4 r) q! T4 m4 L3 g1 ~28
29
+ N! Q) _8 E* t, y2 R30
31
32
33
34
+ [7 ~/ e/ X% r* U* |& K35
36
( S) ?, z! m( i0 z9 u* P37
38
39
40
" h' [  P; S% \& `! T' d41
42
6 ~  H  x# K* u43
44
  x6 ~2 a: e  I+ b  x/ P2 Z45
  u- A' q* T  F( D' @. r* f3 _46
1 g5 I, X9 p  K7 ?- n# }$ z/ V47
9 L  ^4 x* y+ D7 M2 P48
49
! s2 ]8 j0 N6 d; o4 ~' B50
3 K& T8 q" W' W" }9 J% c6 A51
! S" \( S$ F) q+ Q6 {+ |4 e52
53
54
55
56
57
58
59
60
61
62
! s1 J  O) z# J- J0 U1 c63


! t- K2 X0 \+ D4 X2 V& h* p) O# ]不愧我们费这么大劲优化快排，多帅哦！
! N, X8 z# {7 D% Q& s& U7 ?
差一个归并排序，后续补上！
7 X$ m' O* D' w5 f% T( }
不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
  m& l+ y: K- d$ _* L————————————————
' m* p7 L- M6 i; I0 f* Q& p  S版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832

0 s6 \1 ]! Y" P
4 C! j0 z# N: o) {7 ]* ^