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

杨利霞

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

前言
. u# ?9 t) O  N! ]1 i' K本期分享经典排序：
: F1 m# f, I+ c+ Z" F, H& ~" N5 O
插入排序
0 P% J1 }2 ?" D2 f8 E直接插入排序
希尔排序
2 C8 d" v8 h% g& u$ N7 D  t, l/ V选择排序
直接选择排序
/ C* X$ n' P/ }; V堆排序
交换排序
* C# `6 F9 f( T( k9 C- P冒泡排序
快速排序
+ i. H. }+ T6 h: L( n3 C* s1 ]注：讲解时默认排升序

插入排序
直接插入排序
思想
插入排序，就像玩扑克时，摸牌的过程：

) F; O5 @, ^7 b6 [( ^5 w最开始，左手没牌，右手从牌堆中摸
右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
如此一来就能保证左手的排始终有序，摸完牌后也就排序完成

  o0 C7 W2 Y5 q5 v. J
% i- R" o! B% `3 J, ~0 N3 @: o* K操作
设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
单趟排序：
7 L" T0 |  b3 [6 S1 T- G每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
+ ]+ k1 j5 N5 [- F( G. f7 C! M是正确位置：插入
不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
% e  ~- y" @  I0 s  y' D5 T: `: O* H整体趟数：
3 F# c5 [& Y4 l" G: V若元素个数为n，需要排n趟
void InsertSort(int* arr, int sz)
- V. u# I4 b, q  I3 D{
* C1 Z9 H' a& Q  s: p4 P$ b+ N        //end + 1 < sz
) U  m$ E. U' u$ B' \        //end < sz - 1
6 D, T3 ^- T! o- j* S        int i = 0;
        for (i = 0; i < sz - 1; i++)
        {
                int end = i;
                int tmp = arr[end + 1];
" V; v4 d* g( g5 D% J
                //找插入位置
1 F# X0 X; S& ^5 Y3 ]% H                while (end >= 0)
, r8 T, e4 Y' `6 |/ Z) X+ \                {
8 i! \% a3 ~4 X! `9 Q. A/ W+ F                        //不是插入位置：当前数据往后挪
                        if (tmp < arr[end])
                        {
! b9 U5 Q6 c* B                                arr[end + 1] = arr[end];
                                end--;
7 Q' j4 _, N* L( }6 _. X" D3 j                        }
                        //是插入位置：跳出循环插入
8 u- Q' l2 ^- M- o. {2 F; a; c                        else
0 l) [+ f2 g- {; O! ~# `) i# H9 x                        {
                                break;
                        }
5 U5 N- N1 f$ v% Y4 ~                }
                //插入
1 b9 [0 w* p( F  V3 a                //1. 插入位置是[0]，end == -1，不合循环条件跳出
+ G+ ?  |- d' `. t, _                //2. 找到插入位置，break跳出
                arr[end + 1] = tmp;
# C% w( z( b' t9 |! c" d        }
}

1
& T3 U+ r2 g- t1 s& C! `2
3
4
5
6
7 V! @9 W, [, V- B3 B) f! ?5 W7
8
; ?( u0 k5 t) h# h) m) c& f9
- [5 P: k6 |# O9 Z10
% N/ V& o8 m9 H; f8 b) a11
! u- Z  f* B! F: E, X/ d12
& X' z! O5 W* ?2 x8 M4 |13
/ s) W/ [% a5 \& y# U$ \14
" V1 X  V+ Z, J' ^) y* J15
5 i# w" F: V: r( s$ q% J16
17
18
; f* S- P' i) A# ?19
20
21
1 Q; F( c' Z" c; }* a" ~22
8 ~& X" v9 [1 r3 p3 j23
. {, R. d9 ^. S& v- n24
25
26
27
! x7 `1 f9 }9 r9 R. e! G! \28
1 B8 I5 Q! w4 `0 B( T29
6 ?+ {2 c8 w: Z30
6 G1 M8 |3 }. u4 r% a5 j31

5 w- t$ ?: x2 y7 N9 S* L0 u
稳定性
% x- R7 y# M$ W/ Y2 A4 h( w插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以

9 W2 S6 v% O- x; O1 E直接插入排序是稳定的

复杂度
% y1 a1 @5 z- f0 O( w  x时间复杂度
最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）

O(n)
) B7 @4 o2 K3 V1 z) M8 f8 G
最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2
+ M5 p" q% j1 w8 [0 Z
O(n^2)
& b9 q6 x( @7 P+ c( V
# i8 ~& d$ K0 ^) y7 b) J) T8 M空间复杂度
8 ~1 ?8 R" |/ Z1 t& z6 o# AO(1)
1 U3 S$ W4 q, ]) S3 w( P
: i, k5 j0 m2 O) Z7 k( i希尔排序（缩小增量排序）
8 P( ~6 k7 D$ u希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序

优化思想
增量gap不止用来分组，也意味着数据移动的步长，所以

& U' }$ ^  W& u+ j% _gap很大时，序列很无序，插入排序的元素少，移动快
0 i/ l% s9 o- m+ x' g7 jgap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高
! m2 C1 j/ K- i- P3 Z! `+ `

操作
单趟排序：
% E5 z$ c2 W3 I0 t5 |( ~* @
设定一个不断减小的增量gap，也是元素移动的步长
% A- X/ s5 l* i  k0 y" `4 G以gap对序列分组，并对每组分好的序列进行直接插入排序
* e: I$ n* t+ k, g' x* p: a+ c5 a不断缩小gap，并排序
( K/ o4 G. x: j+ ~; z# }*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
整体趟数：
5 n7 m- A/ r2 f& [4 R
6 B) s4 t$ K; J由gap决定：当gap = 1，排序完成
注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。

0 h+ X0 S0 ~. m! p, T3 Bvoid ShellSort(int* arr, int sz)
/ x8 W+ H) M" D/ u* A, L{
% @& W  S5 b( e8 @* y* t9 ^2 _, o$ E        int gap = sz;
       
0 H4 [  [: y$ c4 s9 h    //gap > 1，预处理排序
& M7 ]" M  _) [7 ?" E* i' U% k    //gap == 1，直接插入排序
, x! U& D- [5 J# Y5 a, c        while (gap > 1)
        {
' a$ W( G6 F6 g" ]                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
4 N0 @6 y# l4 E$ T                //gap组
                for (int j = 0; j < gap; j++)
5 R1 i& L7 M- J& ]2 Z+ y$ B                {
; v1 `. P& [. `0 H/ H) t            //end + gap < sz
                        //end < sz - gap
                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
- w/ {8 t; a5 b8 U$ x8 k/ B* r% x                        {
                                int end = i;
8 e  O/ ^5 V) a% ^: e9 t                                int tmp = arr[end + gap];
                                while (end >= 0)
, Z. u2 d5 ^+ @5 S0 j& t5 {4 R                                {
. U0 ?( |: k2 s& k' d7 H                                        if (tmp < arr[end])
                                        {
, @5 `8 U, I3 U, l. J4 G& b                                                arr[end + gap] = arr[end];
& y$ N# T+ G) B5 g                                                end -= gap;
+ G! J! a9 d% z( f5 A                                        }
4 k; b5 I6 C2 {! a, D, p4 k8 H                                        else
2 a: j! X6 c" R/ k2 o- d' y  N( Q                                        {
( B( G; R) K/ G, H+ g                                                break;
                                        }
                                }
6 z6 x3 J5 R% A6 ?* k                                arr[end + gap] = tmp;
                        }
                }
6 d' @' d/ W0 s. w        }
}

4 X; l2 ?) `: E" l- J: _1
5 W9 g$ \" T" p( M1 a% ^" N2
9 ?* u, v; R: s2 Z4 Z3
4
5
* A7 Q6 x5 {# {& [( L! J6
. @- a- e# k4 W3 u7
8
% i8 @/ A; S& c$ K9
10
11
1 h; s4 P- K) S9 m12
13
% L, r3 o  b5 t# F14
( l* s3 a* l$ S5 P7 [15
1 B9 Z* y! w& d8 x16
  `+ V3 R" ]+ I) O17
18
19
20
21
22
6 s& Z  Y2 w) l& H; P23
24
0 S3 p- o4 \  ~) j' o- T25
6 K. b" p/ i) W9 Q26
% h/ t, l; H( A: u27
2 I9 k( c8 E9 C% Z0 z! V28
29
* X. n. ?4 L6 K$ y8 |. T30
31
6 K3 ?# H& q- U2 ~32
33
6 q+ C, Y- K% N) g34
4 y  y" {& S* l8 B) R# Z0 t$ j35
8 Y2 j# O* f- s- X其实就是套上”缩小增量“的直接插入排序
9 e; z- c5 W4 Z6 V

; X7 q+ j$ O* W稳定性
我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以
" ?3 g9 b. U0 L# E! q8 U. f
希尔排序是不稳定的

; U! c# I$ T3 E复杂度
, F- }/ {. e# v& S$ s% h时间复杂度
希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
+ Y" @# C; C, c2 Z$ w* O
O(n^1.3)
+ `8 Q0 ?% Q+ e# u" ~9 }; H
空间复杂度
) c- _" z7 `" ]/ [/ J+ a! Q# yO(1)

选择排序
直接选择排序
思想
选择排序，遍历序列，选出最小的元素，交换到左边


- U: U- b- h- G( V$ a
优化版本：
* w' O) b% {- n6 P4 E# n( \4 ?" l4 |
每次选出最小元素交换到左边，选出最大元素交换到右边

. Y% K0 W' L+ \# B( F6 g- @操作
设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]

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

, V/ D" |2 S' m: g  Q' X4 x( L单趟排序：

遍历选最值的下标
% d, K5 M: e0 S& U3 \  k( |) I交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
% c' D  t- w' C3 r1 q; D$ x- e& p（修正）
整体趟数

若元素个数为n，趟数为 (2/n)
修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标
* y: L9 T/ K; h8 v6 Z0 p" ^  x8 v+ l
void SelectSort(int* arr, int sz)
{
$ p* n2 D- S: S& M. i        //闭区间: [begin, end]
! D4 g' h6 ]% L        int begin = 0;
3 o0 [% }3 ~8 ~* x2 a        int end = sz - 1;
        while (begin < end)//begin == end 最后一个数，天然有序
        {
; A& O+ g" E! R  d- e1 p0 q                int mini = begin, maxi = begin;
                int i = 0;
& C$ n8 |) w$ N9 E! o, ?                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
) q4 c) n8 P* p$ S  h( g                {
                        if (arr > arr[maxi])
                                maxi = i;
. e. ^; ?, B; I2 @0 D, y3 F6 W                        if (arr < arr[mini])
                                mini = i;
                }
3 Q7 F  @' e0 j
                Swap(&arr[mini], &arr[begin]);

                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
* g. I+ R/ o7 ]9 A                if (maxi == begin)
                        maxi = mini;
! h( A/ h: B1 U7 p                Swap(&arr[maxi], &arr[end]);
9 \  O& s1 w# t' n
* @* U% @4 O; Q; q; k5 T$ B                begin++;
$ S6 m6 B3 x& q- t* c: |                end--;
        }
! E. e- d: e* {2 [5 l}
6 J9 P) s+ T' i  G+ s
& f8 k) W  t- R1 z6 d1
2
3
4
7 _: p. G7 p, V$ q3 Z5
6
7
( p8 |% |. E. ^+ ~6 R  r8
6 c1 f" S( v- a4 j9
10
$ k& Z; N+ w0 G- v) y0 T11
12
13
14
# y8 X* B( g, d$ v" P15
16
$ J& A# K# g% K) t' y! m17
18
* z/ Q4 H$ X- s" d19
20
21
22
3 I! O$ a, d/ {) w" f+ i: Q23
24
1 I- c# A; U; @6 T$ J: k. |, O25
26
27
6 e1 o8 }$ S/ ^# F) Z, |28


- q( }$ [$ t" Z+ d稳定性
选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以

选择排序是不稳定的

* V$ ]. X% j  T, l5 D复杂度
$ }" c1 Y6 o$ u8 q  b时间复杂度
$ L8 }9 ^: t  a最好：
/ a" k. ~: M7 d+ C( o) O
+ Y5 H6 M3 l, S! W比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2
6 I) v) K, Z' I$ m
交换次数：O(1)，有序不用交换
$ e8 R. z6 ^, {7 N
O(n^2)

# f  Y* E! E/ l最坏：

' Q/ l, k* @- t) P% T, u# [比较次数：O(n^2)
1 W" ]+ Q. t- o$ K3 r  V! O' F
交换次数：O(n)
: J! K% U" |4 c. v; ], @
O(n^2)

空间复杂度
O(1)
, l2 m  m" J7 a, O4 n: b. P
$ v' p$ Q/ ^1 [4 M: n! O堆排序
思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆
2 p9 C5 [1 h4 y7 p
/ m% Y. ~; ~2 r

操作
2 @! I& a/ r4 P$ N9 I& M建大堆
* R0 z- N. r0 Y( O# ?7 L  W; _单趟排序：
选堆顶和堆尾的元素交换，则堆尾的元素排好
每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
整体趟数：
若元素个数为n，则排n趟
' U- b( j$ t1 X0 G0 ?7 n& zvoid Swap(int* e1, int* e2)
& f. j# n. v! N) s{
1 L  f$ z; u1 G' K! V; R! B) Y        assert(e1 && e2);

3 L. r' L- S' _8 c' V        int tmp = *e1;
        *e1 = *e2;
        *e2 = tmp;
( s+ L0 }& h$ e- m}
* T# g+ M6 i" [& N" |, K: ~5 w' O
void AdjustDown(int* arr, int sz, int parent)
& Z+ }: z2 T2 \{
        //建大堆，排升序
        assert(arr);
       
) b* ~2 |! ]% d    //默认大孩子是左孩子
4 ]9 p) D3 B( p5 P) ~+ e9 k        int theChild = parent * 2 + 1;
        while (theChild < sz)
1 |4 J6 I1 m& s& \0 X7 L        {
        //如果大孩子是右孩子则修正
                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
                {
                        theChild++;
                }
  F  {8 E8 v& i8 J8 f                if (arr[theChild] > arr[parent])
/ h9 Y, [0 _% e# S0 V7 J9 N; u                {
+ ]( `* y6 d* ^5 G                        Swap(&arr[parent], &arr[theChild]);
  U' t$ l7 k$ b( o1 W            //迭代往下走
                        parent = theChild;
                        theChild = parent * 2 + 1;
                }
                else
) Q2 g/ d( k. L! ~1 t' x# v3 W                {
: X- K) f; C1 z5 e                        break;
                }
        }
% w# w4 x5 F& Z}
4 S& {2 o- B; i6 p" V2 y
void HeapSort(int* arr, int sz)
' m) a7 a2 f) V{
        //1.建大堆
        int i = 0;
        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
  v% l' K5 u3 [) Z        {
                AdjustDown(arr, sz, i);
3 @2 D& J/ B8 g) B. Q        }
5 a( P  _* i! q" t
        //2. 选数
+ O# E% t2 l0 x) a3 S2 r1 R        i = 1;
        while (i < sz)
        {
                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
6 d2 P5 b! U5 h' ^* B9 \8 ^                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
! T" `- l, `: o; Y3 Q8 J$ C                i++;
8 }+ \) Z3 Y8 K1 f: r        }
4 w1 i: M5 k, N; f1 w}
  m0 c" x4 U6 Q3 V0 g8 Z
8 x: t: d0 W$ @+ C4 h9 U1
# f2 M. g# R0 k* t  A4 P- U2
. ^/ l, Y2 w% N7 K- S3
4
5
  D: W7 r, _2 h' H* c% C# Z" ~1 ~2 B6
& \9 K& u! s6 x7
8
9
( T% A% H) g8 |3 j10
11
12
# j7 `6 @) Y5 h4 v, c) E9 v  P; r13
- @& b. X9 `) ?14
15
16
6 a# X5 h' z8 M17
18
19
3 O& K& j! c' @- H1 I* T; J20
21
22
1 t1 C) y7 @( O& I23
24
, g2 }2 _& f5 y25
% t+ c: G7 d$ x8 g+ X( Y$ O- k26
4 [  f1 F4 n7 n+ D7 p2 Q! h27
+ T& F$ c& W1 I28
; |) y6 c! r% d# Y29
) W! f. P' w  g30
31
32
) S2 w4 f  H4 Y1 C  E+ H9 |33
( ]6 @9 l5 x7 ?1 ~) a8 Z1 ~/ p34
  D) q  D" ^) |35
' n# ~! p8 ^5 y, x36
0 k2 j4 d* |3 e4 G8 L2 F: A37
: F  A  l1 P7 u" Z; G1 \% F38
/ K5 d8 q" K  S7 i- `+ \1 |39
40
41
3 H! j( s: r) {! C2 n$ h42
: G- \' y6 S, Q+ K* }& Z4 {43
44
45
46
47
48
49
+ @9 y3 V( b1 f; N# {5 `" a50
51
52
! a4 K9 y6 n5 U' M; w53
54
55
) A8 G8 m. L( R" q2 B' d, p
2 g1 p( R& d- s' ?" Q; l
稳定性
建堆和向下调整都会打乱元素顺序，所以
; p7 \5 }% v1 a) H" j# h
" T* [8 f1 Z4 u; R" b堆排序是不稳定的
! n, J! E" ~: J! E
复杂度
时间复杂度
; X% _" F5 I* i; B6 a. n4 A6 y单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为
4 t3 r4 o" P! |' V! Y
O(n*logn)
) C8 v6 e; c$ }$ d$ i( d+ k6 X
! y% H) i% T9 K7 P, [0 h4 }  _) d空间复杂度
原地建堆

# w5 F! @& M- H9 YO(1)

交换排序
1 b5 d0 s6 `7 x, I  v1 y冒泡排序
思想
冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素

8 n; @  T7 t! q5 p; H9 P8 G
. c8 X! o) t3 j1 u
操作
单趟排序：
0 C5 }) Y( m2 f5 ?1 }每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
; Z0 V7 V8 ?0 Q/ f! u& W& r) m+ u每趟排好一个元素，所以需要排序的元素每次减少一个
整体趟数
6 C' D9 \, _+ }: P' m5 q; t若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
void BubbleSort(int* arr, int sz)
{
        int i = 0;
        int j = 0;
; w$ A7 w& ^0 e/ q7 Q2 {! c& Q        for (j = 0; j < sz - 1; j++)
        {
                for (i = 0; i < sz - j - 1; i++)
* ]; U. i; K! m                {
                        if (arr > arr[i + 1])
                        {
                                Swap(&arr, &arr[i + 1]);
                                flag = 0;
4 t5 I$ \6 N( p                        }
. s  h6 ~$ n* r( o7 Z5 e                }
        }
}
  ?/ [# b9 J1 z/ C
& b; M5 D+ a8 I1
2
3
4
7 k) _. o' D5 \& N, g3 u5
6
7
7 t% ]3 C9 l& L  ~8
9
10
11
12
13
14
6 H; [6 p9 b- v* Q15
16
优化
7 {' b8 C/ _2 ~3 `6 k. \+ D6 _3 z3 l; V当遍历一遍发现序列有序，直接跳出

void BubbleSort(int* arr, int sz)
{
        int i = 0;
        int j = 0;
        for (j = 0; j < sz - 1; j++)
        {
                int flag = 1;
                for (i = 0; i < sz - j - 1; i++)
                {
                        if (arr > arr[i + 1])
6 n; a: D/ u3 W4 h( B5 d- P                        {
                                Swap(&arr, &arr[i + 1]);
                                flag = 0;//不是有序就置0
                        }
                }
                if (flag)//如果一趟下来还是1代表有序
: H' j& Z& N- M( a                        break;
        }
: U" t; U2 f8 y/ p$ q$ Q! t}

1
2
4 Z( X' O: D. `* F) o3
4
5
, @/ _; T# s8 [; T4 P* e6
  W# R" T' _: O6 v7
8
2 |$ v9 i  u; ~, S/ }9
1 c" C. R$ B/ g5 N2 E( |5 c10
11
12
( e* B$ ]+ e$ ]# ~' ]+ g3 Q" u13
14
15
5 S8 R& x* m( U$ x/ Y6 S8 j0 \5 [3 [16
17
18
( T) P. R3 c7 S; G1 ]- V5 d6 m19


稳定性
: U/ f- w" ]8 k; N0 y相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以

冒泡排序是稳定的

: K' a+ V4 X7 T: n复杂度
1 N& q: n# u( ~: o; T时间复杂度
最好： 当序列有序

未优化：

O(n)
$ {, S9 w, V) G
# M8 [; D+ i" U) B优化：
. C' y+ i1 U8 K7 \7 m1 T9 m
O(1)
. C( [2 O# n" a# x( k
最坏：要进行 n-1 趟排序，每趟交换 n-i 次

2 z3 ]9 U. z7 r4 O" bO(n^2)
5 I' g  _5 c: t' |+ U* q. y" {
空间复杂度
O(1)
9 K) U1 s  i' O9 X+ k1 y
1 V" T# g7 {% T& d1 O快速排序
思想
分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。

& J) N% }% Z4 y% v. _1 R* L所以快速排序可以用递归来实现

操作
$ i+ ?% B2 W1 h. O/ [% m有三种单趟排序的方法：
4 s* s( l3 ~5 y* g8 |
  ~: c6 v+ P6 r" a; v) {Hoare法
设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间
" O" K+ j( o# p+ P; f3 a+ p
2 B0 z# a& Y4 w1 O. @左下标 L = begin，右下标 R = end

设 L R 相遇位置为 meeti

​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”

​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“
0 ~0 a6 }9 I/ q9 u% d
; ~9 H! h0 \3 X( d7 m2 B; b  \选 键值的下标 keyi
7 m& J: r: G6 ]
' n7 ]( S$ ?! B8 h" S左1位置作 keyi，则 R 先走
8 I( k" E  A$ o右1位置作 keyi，则 L 先走
R找小，

找到则停
0 X, j# I1 l( }7 V$ E遇到L，则交换 arr[keyi] 和 arr[meeti]
: |( `) a' T6 B4 U4 F, `% LL找大
% V- Z. \6 ]0 i) M+ `
1 o, ]2 T* K7 a+ S% V) h3 P  P找到则交换 arr[L] 和 arr[R]
遇到R，则交换 arr[keyi] 和 arr[meeti]


解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
答案是肯定的：
" I, g* B- U  m7 K: w0 q

. X3 ^1 g8 ^" n" a
, @. b7 Q, i, Y3 C
- a- B" F1 G( D4 A+ @- O6 M//[left, right]
int PartSort(int* arr, int left, int right)
{
2 Y" L+ z3 v% l0 T9 K0 O0 F, L        int keyi = left;
, T  Q+ O. y8 N        //相遇则排好一趟
8 F" v& F' _; o& K" }        while (left < right)
        {
+ ~( c( f9 T2 M% i8 ~2 ]: O1 X                //R找小
        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
                while (left < right && arr[right] >= arr[keyi])
                {
                        right--;
                }
, P& o, w$ F8 Y
                //L找大
                while (left < right && arr[left] <= arr[keyi])
4 s0 D9 X+ _7 g) F                {
                        left++;
                }
               
        //相遇就不交换了
                if (left < right)
5 Q- m! ]! {7 B, _: D; C* {" N7 {                        Swap(&arr[left], &arr[right]);
2 d) k, `" S  P2 K3 @        }

        int meeti = left;
( `  \4 S! X8 N7 [/ ?6 j
        Swap(&arr[keyi], &arr[meeti]);

3 d6 o6 f' }+ V. S( [9 v& _+ q        return meeti;
}
* @( a6 w7 ^2 Y4 o
1
) m# U+ ]9 k6 R' x. X. a2
# [! _9 P& N* ~3
- b2 J' S# C; E, e) g, ^4
7 T" i4 p  B! R4 g, l5 ^0 ]5
6
5 s, z- f! A$ m( Y* N7
8
1 Y1 W! m' K/ Z0 U9
  Y: d9 g+ k) [% r. C" K10
11
12
9 \) x$ e0 W0 W8 F3 Q13
0 W7 ]: i% E% E8 j7 n, v- L14
5 b  J/ v; ^' ^4 D0 E: Z. ^8 q& g15
" Q7 L, u7 M3 v16
1 |& h! q' l! v# u" G7 u17
18
% s4 I% g- z/ _" q) t/ d  _19
- y) i3 }% [& J; y+ d, ]. E20
21
1 l4 p) X  A6 D22
23
8 z2 k4 V( @: z. K( `24
/ M: ~( |& M0 H& `$ J' U25
26
8 m  g, N$ i& L: S$ d* f$ E27
4 B; l% `( ]5 q9 L  h7 c28
- K7 N# Q/ q3 D2 T) V" P- m, I29
$ B2 u: E3 c* P4 |) D30
+ l9 S; D. N0 S# S& k- I31
32

" e  ?! j+ Z3 G
解惑：为什么key要选左1/右1，选中间不行吗？
5 p1 E/ \; J/ o5 r; S4 W9 v9 B

可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深
9 B0 B0 N& P! L& z1 A2 n& A



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

$ B. R& X' g! w+ Y  H  U优化选key
8 [4 E, {* K) h随机选 key （是一种办法，但是不那么彻底）
选中间位置作 key
解惑：那先前实现的单趟排序不就失效了吗！
9 I7 V: @8 K. Y- s0 l/ y9 a：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑

解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
! ]8 L1 Q& \( T* i: {前辈给出三数取中的方法
. q2 O- P% o5 s; B+ A& l
! u6 j5 s7 Y- W0 v& J9 T" P' y/ y5 y三数取中
在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
/ V$ g+ P0 }4 I5 G+ l这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
2 {' Q$ m- B' Y' ?3 q0 N优化选key后的Hoare单趟排序：
, d5 i  R3 d8 A1 U$ M0 ^
int GetMidIndex(int* arr, int left, int right)
" H! D6 E- G" u{
$ v) o) |( E* p% h' M9 f3 }        int mid = left + (right - left) / 2;
  I) ]7 Y! m: \9 P//  int mid = rand()%(right - left) + left;//增加了一定随机性
7 i- _) N5 k& G( x        if (arr[left] < arr[mid])
        {
                if (arr[right] < arr[left])
                        mid = left;
                else if (arr[right] > arr[mid])
' b# @1 F2 Z5 [, N  {8 z" C                        mid = mid;
                else
                        mid = right;
3 M* Z, V. s: `: l        }
  s" O  S1 o: p0 p+ V! P% D( k        else//arr[left] > arr[mid]
* H& N4 x7 [6 g/ f3 a5 g. W        {
7 M* v& e) S% J9 |- T& M7 r0 O                if (arr[right] > arr[left])
' K8 |6 ^* c4 K: B                        mid = left;
                else if (arr[mid] > arr[right])
9 u0 m7 O# `1 \2 E- Z                        mid = mid;
                else
                        mid = right;
        }
        return mid;
}
  O7 z+ n& r/ s
3 Q; m$ R. a. ^4 d; W* Vint PartSort_Hoare(int* arr, int left, int right)
2 z; h4 b8 |' r. U# Z# T+ X1 p{
        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
# J0 z6 r; H" V9 o) h- T        int mid = GetMidIndex(arr, left, right);
" R4 w( r6 F" |* g; A2 R& c
        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
        Swap(&arr[mid], &arr[left]);
* s% S# W' [9 E# c* w8 U- {9 s
        int keyi = left;
& ]- f$ x/ C! J+ j- n        while (left < right)
* |9 Y( P+ R. e/ u- s( a- j% a0 z        {
                //R找小
9 T5 I5 L4 F$ M/ @% D+ I                while (left < right && arr[right] >= arr[keyi])
( t! ^. E. v& x4 K4 U                        right--;

+ I5 {& j1 `* W+ ^4 B+ X                //L找大
                while (left < right&& arr[left] <= arr[keyi])
                        left++;

                if (left < right)
                        Swap(&arr[left], &arr[right]);
& z8 g7 N" \, Z2 ]* I        }
0 q# Z1 k* x" J$ O. V0 L$ O
        int meeti = left;
4 z: k1 E) A6 G* Y" a5 A
* |3 v2 u1 @" m. t        Swap(&arr[keyi], &arr[meeti]);

8 v" L0 ^( Y- _1 w3 w' F) y        return meeti;
6 U8 T$ o3 k9 w5 v& \}

1
2
3
4
5
1 m( z! e; P3 N7 A3 h6
7
' ^; e% |( t! [! D8
6 Z+ C! l0 d6 v5 A. e/ Z9
" S0 p/ Y+ k- W+ G! L  y" n10
- S- w' N) r1 o9 u. t11
12
  p1 T/ U. [! P: ~) b! l4 u% R13
  I. V8 T+ Z' J. J, y14
15
1 R1 [4 c3 _+ d0 \$ L16
8 A. t) A3 h  `4 x( y) f& ?8 K17
: t1 V. q0 ]4 _% y9 P8 ~18
- u" p: |$ X5 c: l% \& Q& Q19
9 |/ b: W# o+ ~* S- F. _20
4 q5 e3 c* T: ^# g7 u! D21
! A; N6 D& n- H% V# V# j22
4 y0 K2 m; S( f23
# X' t% n  P6 B  I: s24
9 ]5 f5 l; F7 v* m25
26
27
28
29
8 y* B9 m* p; m' M  v30
31
9 ?# E: N8 ]3 P32
, M6 y- t/ V) B. C2 @, L33
, T# j5 r& b% h, Q. n34
) b% h" l' B% g: N9 O35
36
37
1 q" V& X+ K( N5 B  ?38
39
40
0 f8 e, Q, R5 Y' M% v( \+ d; T41
. `  V3 j2 G) o$ _& F! n$ _$ W. v0 j* }42
' f4 x: Q$ Q; z- |. P9 D43
44
+ \  c2 S/ `! n( P45
- L9 x& o/ k0 u$ C5 L. n8 \+ C46
47
3 Q" O: y1 J5 Y& @: p48
; z& ]/ T: b7 J. a# W49
50
51
9 e& n% @' s/ C; q52
53
54
; H% t" a+ q5 w7 ~+ I. i7 U挖坑法
2 D/ k+ \9 C0 y8 i4 R, a初始状态：L作坑，其下标存为key
5 y. f9 u+ G3 S(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
重复 (1) (2)
+ p; {5 Z2 x3 g! Q6 ~最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]


3 q+ ?4 g2 q" Oint PartSort_Hole(int* arr, int left, int right)
{
        int mid = GetMidIndex(arr, left, right);
9 K* I8 z6 ?: f- R1 A- o: v' _) L        Swap(&arr[mid], &arr[left]);
" f  m7 i& H) ~# `; f  O
: E% m) I& `4 f! S6 V% z        int key = arr[left];
+ g8 k: r: g) [5 a+ j+ ]8 }        //L作坑
        int hole = left;
' j# r# Z# t# _, I        while (left < right)
. t2 {7 G: A) ?; @. o0 q& i3 h        {
/ H% |7 Y) q: R; P- `/ r2 M                //R找小，扔进坑，R作坑
                while (left < right && arr[right] >= key)
                        right--;
8 Z! O8 W6 D; _) O, z. Z$ n$ M9 e1 J                arr[hole] = arr[right];
                hole = right;

                //L找大，扔进坑，L作坑
; o; z( O$ y$ S$ z. q                while (left < right && arr[left] <= key)
                        left++;
                arr[hole] = arr[left];
$ c1 t9 {& s9 o. \                hole = left;
3 N. O& E$ W( d9 O. X3 c7 F        }
        //meet
        int meeti = hole;
; s% F7 {' j+ b! _4 p        arr[meeti] = key;
! g0 `1 b# d" |) V$ a* c2 F
        return meeti;
}
; a7 O6 w" H$ f- p* g, b  I6 ^7 C
1 T. e. ]. G: }1
# G/ Y' r+ q1 {' A& z' d2
3
4
5
6
7
3 G* O& ]# h" a) a) u8
) x; n8 O6 y7 N+ u- @+ g9
: ]1 B6 t! H. g" N) ~2 W8 Q10
11
12
1 a9 l; H, T. _1 ~% h) c& j0 p- w13
14
15
16
17
+ K. u/ F+ Y5 u: S' c8 Z18
19
20
21
0 w3 t5 I8 T8 [5 {1 @& `22
: j; i9 c7 V' o* W( |1 l- y23
7 h; i3 [1 H) A$ A6 W. B24
25
6 A2 ~5 C7 h. @3 J- J26
27
% a1 B+ g7 o4 D28
前后指针法
此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多
3 g& w2 a& a1 c' |, D0 z* C
cur找小，找到则停
++prev
如果 prev != cur，交换 arr[prev] 和 arr[cur]
如果 prev == cur，不交换
当cur越界，代表找完，排好序了
prev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低

' z5 x* w. G/ q( T
/ z7 v) E. M9 @- n& S
3 T- n/ A' s! L3 q$ `& b! Yint PartSort3(int* arr, int left, int right)
{
. ~/ x: y  H/ j7 V: U/ C        int mid = GetMidIndex(arr, left, right);
  n+ _, x+ i- r' w        Swap(&arr[mid], &arr[left]);
       
  //int key = arr[left];
9 T, F0 d1 b+ l4 j9 f        int keyi = left;

+ A, D* P( e( p3 N( {& `        int prev = left;
9 r( I! t; G0 Q' ^: g3 G/ E! w        int cur = prev + 1;
3 V6 M0 a/ i/ _3 ?  F1 o+ B       
' n, y' z1 F6 T  j. s    //cur越界：找完小的，prev的左边全小，prev右边全大
" S. Z6 S4 m, T- P+ [! k        while (cur <= right)
* S, ~  [3 z$ e        {
6 l: g2 Z( B# u' n' K1 t        //++prev == cur 没必要交换
4 X( f  @  Z2 e( d  w" T: T/ t                if (arr[cur] < arr[keyi] && ++prev != cur)               
9 a7 ~9 _. b6 M* I+ Y8 L                        Swap(&arr[prev], &arr[cur]);
$ G/ |- S/ G5 ^( J' @$ q7 t
; h# X& ^3 b8 d  k( G                cur++;
        }

        //键值存是的值：
        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
( v1 C& F5 h, y$ h        //Swap(&arr[prev], &arr[left]);//这才对
    //键值存的是下标：
& |. M: b! l. `$ o        Swap(&arr[prev], &arr[keyi]);
6 N- z! Q4 w9 {. [" g6 g
        return prev;
2 W0 \- X' c6 x# b  e$ z}

1
2
8 u0 a3 m, x* Y- `9 A3
4
% v# X  c& |5 [- [/ ?: z% I5
2 W/ L! M$ ?1 J3 x7 `) z0 R- C, Q6
) E# {- v% H+ [+ n# Y3 G+ i" S* l  j7
# L0 f; k8 p/ Q, ?8
9
' x: a8 ^0 u' f' ^+ K10
' S9 f" ?4 L" L, ]/ Q: {" ~11
12
13
14
8 U8 d  c' \+ O7 \1 y. f) L15
16
17
* o8 [4 k& s; A% o. j- J18
19
20
21
22
23
* ]9 F9 d9 U) D) A+ F; w; D24
: H- u& ]3 b8 i; c6 R( B0 a25
6 M2 Y% L5 m' q- v6 i26
27
6 F! ^( h. a6 s- p( V" B" I28
8 h/ z& y6 [5 C: S& {29
整体排序
递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

0 a6 W& f- A) z' G* H//[begin, end]
" \* k. O8 O  N7 t* B8 Uvoid QuickSort(int* arr, int begin, int end)
{
        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
! K+ w/ E8 R4 h+ H- O' G! f        // [begin, meeti-1] - meeti - [meeti+1, end]
                //1.begin > end:超出范围
: I3 D7 |7 d; \/ \, y* X# J. S                //2.begin == end:一个数天然有序
  x* f  r8 v* G    if(begin >= end)
4 i, V# a: a8 L2 @5 }( L2 z# h        return;
7 `+ w6 h: c, s% t- p4 j5 r
                //排好meeti
. s! J1 |1 A5 t, V* f6 J% v                int meeti = PartSort3(arr, begin, end);
+ W5 i! E) `. @/ E
- [* v/ T2 V/ v5 g0 ^( \" c  J2 u                //排好左右子区间
                QuickSort(arr, begin, meeti - 1);
+ c+ F& Z1 S2 Y$ O/ j3 @                QuickSort(arr, meeti + 1, end);
3 ]7 t4 g" Z# d/ Z" D4 ^' ]0 {        }
}
: S; D: @. l4 f- L3 t" i( \( N
. j" A/ f$ }0 v1
" }8 z" e- C$ W# a% e+ {2
3
, O, I  O' L+ k) t0 J/ Y1 D4
0 i: q" M, A. W) E1 p- a5
6
7
8
9
5 j5 {9 E% A* Q8 O5 X10
11
12
" y- s' D1 f- D' R13
14
# p+ n- ]& i# U( j, j* _6 x8 m15
+ _  I5 m. T6 J2 \16
6 P( V% S; A8 H17
18
- l) K& X1 Q8 u: _3 {" ^…
# T( w( ?1 r$ e4 e6 _* |( o0 l. E
没想到吧，还还还还有可以优化的地方！

优化小区间


7 ]+ R% y3 X  Q4 N- n& @如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序

& `4 y1 B( E# k" y, B  V( y那什么算是小区间？

5 Z5 n$ i! n1 p9 _0 H% a* A8 w其实小区间没有确切标准，8-15左右都可以的
3 m6 J7 x' t* G

: r7 B/ x* F+ K. g, ^6 Y: @' U; {这里就把小区间定义为 含有 8个数或以内 的区间
; y, V% I# E# B
" {' O% [4 T4 Q1 g: _% X: a* s. G5 L( s//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
        if (begin >= end)
                return;

        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
        {
# M+ S! t7 |( u0 u" d                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
        }
0 u' K7 P% R" E. m8 {        else
; R6 e% e% R. L+ K        {
1 u" I4 [( P  m                int meeti = PartSort3(arr, begin, end);

& J; @$ z/ W$ ^( \9 u3 u( @, q6 p                QuickSort(arr, begin, meeti - 1);
$ [  F2 _/ W  g" k# }2 [+ P                QuickSort(arr, meeti + 1, end);
        }
$ E3 l0 L4 Q0 C7 {, C+ t}
9 k- [, K4 u" I3 `* @
1
5 S# J- ^# d4 R/ C; h" t2
3
4
# T% D5 q; L- V# C5 ?" Q. }5
6 I: H# F1 e; ~$ \. P' s6
7
8
9
1 B# z* E: d, k4 {2 N; @- a10
11
% L$ z1 O6 `9 a. S0 e* Q' W12
$ x* D3 z: Z" W$ n) i+ i13
9 G1 M5 L% H2 G1 K& W! G14
15
- `4 W! i5 M* X8 m  B16
  |; Q; g7 ~# ]17
' |* r- E- Y; \5 q# ^' U" }18
) s, l5 O, x: d19
快速排序非递归
为了解决彻底递归深度深的痛点，我们来试着把它改成非递归

1 X! _, i, L, e! D# d思路：
* E( t8 A4 V  o  A+ N递归深度深，栈的空间又小，会栈溢出…

那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！

& s2 F' _: J. F核心思路：在堆上创建“栈帧”

; X' q& z: \( A快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的
6 ~, n+ W! Z5 r0 @- d. y


8 Y) u! r' e) `- X/ Z( ^* C. Y在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：

, e, G4 m" T/ g$ K# `$ ~2 G先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
先取end：先入begin
1 h; p, K! ~. c4 v$ Mvoid QuickSortNonR(int* arr, int begin, int end)
. W% s# \" D2 L0 U& f- h  k6 @) m{
9 X& w* }3 A. R9 D1 m6 l  E/ A        ST st;
: o3 f$ x* s" E# U        StackInit(&st);
       
9 j% V8 T) J4 y$ N+ A" T    //先入begin
8 i* U4 m) l3 x1 T6 Q1 w, J0 h        StackPush(&st, begin);
, F2 M- q! E% r7 l) z+ m% ~    //后入end
        StackPush(&st, end);
$ x6 Y- |& T& e, o7 }: b
        while (!StackEmpty(&st))
        {
                //先取end
                int right = StackTop(&st);
                StackPop(&st);
% \- Q: F3 |9 D4 ]8 O                //后取begin
$ ]; {4 Y1 ]0 i                int left = StackTop(&st);
                StackPop(&st);
2 \* p$ `5 K* P# h  E
. B: O, c" b4 K% y                if (left >= right)//1.只有一个值  2.区间非法
                        continue;  
                               
; `; e, P/ r2 Q3 e                int keyi = PartSort_Pointer(arr, left, right);

                //先入右区间
                StackPush(&st, keyi + 1);
                StackPush(&st, right);
, l4 s) K$ r6 j' |$ m. J9 c                //后入左区间
( A* {" q8 y% A8 i3 [                StackPush(&st, left);

                StackPush(&st, keyi - 1);
        }

0 x5 Z3 X  z: d$ t2 l        StackDestroy(&st);
) ~/ o" U$ v  _/ Y' p0 L( H}

1
2
. Z* u5 x0 b( w4 P" u. e3
% O$ u- @% D* X4
5
9 d" U* H4 L6 @5 y# e2 q' Z. f6
7
8
0 D3 ]: M: O3 x3 {" i% P6 b" i9
10
11
8 P% L8 L! s3 Q4 w12
8 a$ h$ C; j7 S. K+ e13
14
: p. n6 z9 ^* R0 {  s: e15
16
17
18
" l! S7 ~' K  O& q19
) I4 H- S  m# _5 c% A$ d$ |0 d20
21
22
( ^  V$ ?# J+ Q& D7 \23
24
25
, E" J8 e0 A. U26
27
# \: K( |  M" H* Y# c: F- B* k' ?28
& G  H5 c# O- A2 b% n, M" y. H29
30
31
! B9 q0 M( K  K2 u, p# o/ t# z5 |32
33
* D4 J. j  v! n8 C" S34
& W, \' S9 A- }$ s" e5 a# n6 r35
- u& ^/ b4 _& Z( |* }0 y( k# ~" Y数据结构栈的实现可以看博主之前发的博客


% E; K$ ]; Q5 W归并排序
' y; f$ G" N! a
…
( |! P. e7 k9 ^7 L$ f: v9 a
# j1 Y& g# x% R! Y/ m4 ~2 Y: W/ ?性能测试
void TestOP()
{
7 V  l$ ]+ q# Q, [: V3 G/ O        srand(time(0));
        const int N = 100000;
        int* a1 = (int*)malloc(sizeof(int) * N);
2 S5 ?$ D' F/ Z% X        assert(a1);
  |0 P; @6 y6 x; Z5 U$ J, M        int* a2 = (int*)malloc(sizeof(int) * N);
        assert(a2);
/ w# b- M7 m" r# o8 w% M5 R        int* a3 = (int*)malloc(sizeof(int) * N);
! _5 k1 P- p: @- [        assert(a3);
5 v7 U9 G! {! o! Z5 e        int* a4 = (int*)malloc(sizeof(int) * N);
" [$ x3 Y, w; c7 g) p7 L5 t6 G        assert(a4);
        int* a5 = (int*)malloc(sizeof(int) * N);
        assert(a5);

' a9 U8 P0 v9 G/ c        for (int i = 0; i < N; ++i)
6 K9 F6 M& u. c0 w( n. P        {
                a1 = rand();
                a2 = a1;
                a3 = a1;
                a4 = a1;
                a5 = a1;
& t* f; M' ^* s! i        }

# k% u3 N, e  J        int begin1 = clock();
  G$ b, d, c8 ~  @3 U" X& o        InsertSort(a1, N);
1 S) ?  l( T; e" T3 @        int end1 = clock();
4 r) Q3 b/ d) y$ P0 v2 ?
5 F" H* |/ a+ [        int begin2 = clock();
, c3 v! ^* z% _9 e% x* t7 p        ShellSort(a2, N);
" G+ p, ^, @5 |        int end2 = clock();

# d5 C% Y4 G; J/ h6 {. r        int begin3 = clock();
! u" p. S$ A; @7 v/ b) r        SelectSort(a3, N);
5 ]/ @% @1 ?& ?  j; G; J% }5 o) p        int end3 = clock();
" _# N7 q' ~& D2 O  @
        int begin4 = clock();
        HeapSort(a4, N);
        int end4 = clock();

        int begin5 = clock();
( R; u- ~' O7 ^: ^; u        QuickSort(a5, 0, N - 1);
                //1.中间key
                //QuickSort(a2, 0, N - 1);
9 I- ~% p; d( d0 q" ^. `2 Y1 f                //2.三数取中
7 F( q5 ?% ?8 c. |* {& H                //QuickSort(a2, 0, N - 1);
5 M+ k" f# C6 V" j; E$ U                //3.小区间优化
                //QuickSort(a2, 0, N - 1);
        int end5 = clock();
1 D8 O9 a& p+ T" {  j, N

! q7 y- ?& F$ ~9 k" I# z        printf("InsertSort:%d\n", end1 - begin1);
        printf("ShellSort:%d\n", end2 - begin2);
+ f5 f" F2 A: k( |- S        printf("SelectSort:%d\n", end3 - begin3);
        printf("HeapSort:%d\n", end4 - begin4);
( X: T7 F) W* s3 S! S! {4 t# h        printf("QuickSort:%d\n", end5 - begin5);

  h. v0 F( C: E% H# h4 a        free(a1);
# z; `4 y! |* Y: l1 \        free(a2);
        free(a3);
% V. Z8 E2 Y. _/ E- M( s        free(a4);
        free(a5);
6 b  T7 j7 W8 \1 b8 P8 u5 Y( j& y: u}

# ~: n, F7 {- O+ J% k1 F) ~1
2
+ p  W; D4 [7 l  Y+ S! K3
! Z! ]. o( [  X+ b: t4 n4
+ J3 \6 X( V( T1 y5
) Z( V% \( ?, w9 \- r6
7
8
8 B0 N; I5 X1 \+ y7 l4 D* k9
5 a. h+ s, M" [' @8 _  N8 R; n. O10
" p! N) C. f9 H, I* b% ]1 J* B11
/ C5 }$ u+ r) U* g- N12
13
! K' ~2 Y, L$ X2 e14
15
16
# d0 }: R/ U% R2 @; y; ]3 m2 r17
18
19
5 ^6 S' T+ g6 b* G' F! Z+ l20
21
22
23
! v7 o( W% }5 ^2 S24
# W4 ~# e5 ]( O& @  g6 X0 c25
3 k" W: N8 C! V26
27
28
29
30
31
: W$ ?' s# ~! y2 d( {, q32
33
  e1 ~4 t5 ^7 M: Q, _1 I# X3 N, o34
35
5 c1 Y& }* C9 D' x0 x; x+ P2 {36
' Q5 ?. n( m1 B- t* J8 ?( ^37
38
5 X2 r! a  v/ c" G" Y" s8 |% t39
40
% \- h0 I/ m) u  ~- I41
42
7 w) d- M& Z8 x43
44
# c0 _" V: @% e45
  C' m, ?( a1 Y# q1 P6 z7 X46
; k: d1 `) S  B" S47
48
, T: L& e8 J/ e- J. J49
8 x) x5 g. X  R; T# v50
; h: O9 N- [4 L5 a5 K# |51
52
53
3 b$ R8 [+ r/ c$ K54
55
5 q: t3 F: ?/ P9 }- K" X# Q$ h6 P5 e56
( a  T# b: o3 t57
4 f/ x9 r0 `/ x' i, F% g4 i: F58
59
$ @: C4 ~2 j6 S1 L# _& `2 l8 L60
  E- h5 \# a  U4 R' [) a3 ~61
* D0 O) ^  H% D2 A7 R62
63
, M4 P1 d* Q$ X8 \" E% D
3 m2 M3 O- w1 {  A3 d3 E! @
: W; p' ?) G% d0 z7 u# f不愧我们费这么大劲优化快排，多帅哦！
2 l: l0 ~8 K5 x6 b' m' S& w. Y
9 c" ~* g  N% X8 r3 b% x4 l差一个归并排序，后续补上！

$ V7 r/ k" J1 e: M6 w9 n( W, F不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
————————————————
版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832
' w, _& i; a, T