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

杨利霞

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

前言
- ^) h6 x5 s+ |5 G4 F3 N5 [本期分享经典排序：
, X% N: e) ^+ `! m
插入排序
直接插入排序
希尔排序
选择排序
直接选择排序
8 S  h1 @; C5 ~, X7 p( L堆排序
交换排序
; @3 I) T4 A# i1 Y冒泡排序
# k1 t5 i' l2 Z/ c. w: {% z6 w快速排序
注：讲解时默认排升序

插入排序
直接插入排序
思想
& C- |& n& @: H. ]1 I插入排序，就像玩扑克时，摸牌的过程：
+ ^8 w8 p2 T3 H* N& X
+ a; L& A$ y$ q1 o" K# n9 m: n最开始，左手没牌，右手从牌堆中摸
右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
如此一来就能保证左手的排始终有序，摸完牌后也就排序完成
. s* y, N8 r& o. J6 o# x* X  ]$ q
. B% i8 k2 y. A5 ?3 ]
# u/ B1 w+ ?- v1 m  V* Z- d# F: f操作
设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
3 N# d1 u4 n- L0 m单趟排序：
3 i6 D* ~5 m  J7 @每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
是正确位置：插入
/ i7 \; H& |. `% a& ~. l不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
整体趟数：
* n* _- `& S: Q1 d2 V" |7 _若元素个数为n，需要排n趟
void InsertSort(int* arr, int sz)
% M/ D% \. t9 ]0 F{
        //end + 1 < sz
        //end < sz - 1
2 \9 b7 W6 K4 O" F& d9 t0 ^        int i = 0;
$ @4 A( l# c1 K& B: y        for (i = 0; i < sz - 1; i++)
5 w; i/ c1 L1 t7 x2 k; `        {
                int end = i;
3 A7 @; e7 s9 S/ T) z# U3 I                int tmp = arr[end + 1];

                //找插入位置
3 A% v0 R5 e. P                while (end >= 0)
0 d% N* C% t3 J6 p. f                {
                        //不是插入位置：当前数据往后挪
: m: F& m1 G$ J$ |                        if (tmp < arr[end])
                        {
                                arr[end + 1] = arr[end];
                                end--;
                        }
" b; P) b0 E' _/ L8 _1 j                        //是插入位置：跳出循环插入
$ F3 q' R' g+ I9 N1 @% a                        else
/ N, }" m2 g/ e7 x1 F8 G& f                        {
# ^5 B1 d' s) U7 N+ `                                break;
                        }
                }
, q" J0 E, p& X/ H                //插入
                //1. 插入位置是[0]，end == -1，不合循环条件跳出
, w/ v7 e0 ~" \2 u( I                //2. 找到插入位置，break跳出
, q6 u3 |9 A. Z3 i6 x# T                arr[end + 1] = tmp;
        }
}

( |5 z: `& i& H6 T+ ?: w6 X* N1
2
3
( e& z, U* K/ U3 _& X4
5
6
, q  Y" T, r( G3 y# W" }' F7
! y2 k6 u0 c' W2 H! L7 D' ~8
( ]! A6 B* {& ?. C6 k$ x9
10
11
12
13
14
5 t; V: D- l6 U7 r; B1 M3 Y15
16
6 `6 H: q. L3 m9 N( P" h% m" @& b17
' t% F+ H# }* I18
1 g: d" i. T" l  G3 b# _19
20
( h; ^& z+ b' O& t21
22
23
24
25
6 ~5 G0 A% E: a26
27
; T: O! m; _$ [( i0 T3 S28
29
: ~" [7 n6 H" N; _5 l30
31


: X8 B* P8 \$ H6 n! C  \稳定性
插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以

直接插入排序是稳定的

1 X  v# V, G# b2 m, I3 u1 r1 I复杂度
时间复杂度
最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）

O(n)
, b2 y. i  o' `: a0 M
最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2

" |9 K, B5 Z( ~4 ~0 ~9 UO(n^2)
0 v& l5 {! ]. O( B  v' }
! K( \5 Z+ R# W- s空间复杂度
O(1)

! _) K  E) `, d2 O5 D希尔排序（缩小增量排序）
希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序

& ]* u1 e. A# V& }+ n优化思想
# C* S5 N. ^$ j: R) @1 c: {0 D4 \增量gap不止用来分组，也意味着数据移动的步长，所以
9 i4 m+ Y5 Y; m* k6 L
" a( G. x2 W& p8 agap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高

$ n3 n. b3 J# `" M7 C' F
" f: I0 U: c/ @! }操作
: b% b6 o) c* J% J6 L5 H  f单趟排序：
4 ~4 R8 ~4 V+ l3 Z1 e% s  Y
设定一个不断减小的增量gap，也是元素移动的步长
7 ^6 V, l0 `6 X6 p2 C9 F. O1 Z" S6 i+ B以gap对序列分组，并对每组分好的序列进行直接插入排序
" u/ I- g" V; |不断缩小gap，并排序
*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
  u7 i; _. D, R4 v* _2 H整体趟数：
4 A1 Z, }  N# U' U2 |
. n8 z) {( y) V- n由gap决定：当gap = 1，排序完成
注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。
* n' c$ T% k8 |2 y+ L
void ShellSort(int* arr, int sz)
{
        int gap = sz;
       
    //gap > 1，预处理排序
+ I! A- A" o( j    //gap == 1，直接插入排序
        while (gap > 1)
        {
                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
                //gap组
8 O: O# p2 z! l  ?8 v6 \4 k                for (int j = 0; j < gap; j++)
                {
            //end + gap < sz
+ `  j+ b0 I. m0 |8 u# ?                        //end < sz - gap
+ z; d; C) D$ R# a/ I! m                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
                        {
- q2 k6 r4 v$ }' F' c( i( \                                int end = i;
                                int tmp = arr[end + gap];
                                while (end >= 0)
+ T; y( ]" G# L5 g7 t' V8 l                                {
                                        if (tmp < arr[end])
                                        {
                                                arr[end + gap] = arr[end];
                                                end -= gap;
; D+ p  U% J0 k: Y$ ~' Q                                        }
2 M0 `* @9 h7 I1 }$ q                                        else
                                        {
" L/ E; c9 K* m6 t: o$ g) D9 a5 @                                                break;
                                        }
9 `! |: U4 Q+ j3 i+ T                                }
/ I9 A( a( S# G+ O/ P  V0 R                                arr[end + gap] = tmp;
                        }
8 L* X+ P4 C& y) Y3 Y/ b- ?/ I( P                }
        }
}

& C" ~6 A- s6 c4 Q7 B6 L1
# d( @; t; |$ h8 B+ w2
3 V" }9 ?/ N0 T$ b( }3
% _: m1 Z- S9 a4
& d, q+ A7 W8 q3 z6 f5
" M+ V* t- f# I* y( g* ?6
7
8
" T/ N3 d5 x% ~4 @! Q# n9
10
11
4 Q  Q, E( Q/ t& i: K: }$ r2 |12
13
- V; T4 O& F* {- x  M. h, W14
15
8 W+ K, g$ y0 \8 u: o16
17
8 g! r  z& f$ {$ J18
19
20
$ i7 L$ @- V1 P# e4 ]! w$ f21
22
; U6 V! ^& w! G$ R0 O23
1 d  T  L( o. \& m24
25
" r7 O& ^/ j5 x* I! `4 P26
8 L: y$ T, X- j. _$ p' e27
; x+ Q- f* l: x1 d3 C% ]28
2 L7 k5 [3 b* }1 d7 H& q. D29
30
31
# X/ @4 f+ G+ J0 c32
33
$ n' O( }8 `: \5 V* z. Y) \34
0 _! M' }0 Z3 U4 g' ]4 D35
其实就是套上”缩小增量“的直接插入排序

4 ^  b& Y6 C8 j) j' n6 u% U9 S
稳定性
我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以
1 \9 ^+ C7 W# n4 b
希尔排序是不稳定的
: M) {3 x: ~: {& f4 b
& A& a" ?, q+ M1 I复杂度
时间复杂度
希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：

+ f$ X) [4 I9 k; W& dO(n^1.3)

空间复杂度
O(1)

选择排序
直接选择排序
) ~! ?6 K4 s( h, d思想
2 B$ R  v( U5 b% w% U4 N% V, D选择排序，遍历序列，选出最小的元素，交换到左边

6 y5 P- x, i& i: ^, [
9 _" _( [* v% q0 ]: Z' t
优化版本：
& R7 h$ D$ s* T( u* b2 G
: W# o- `- ~, f0 F. J5 M每次选出最小元素交换到左边，选出最大元素交换到右边

操作
设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]

. Q- O3 b( B* x' o设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标

单趟排序：

遍历选最值的下标
交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
（修正）
. W* k' s& N/ y/ v整体趟数

1 ?4 g$ d. r7 N+ u" e. n  P若元素个数为n，趟数为 (2/n)
) N2 ]; c5 H: U' x# O5 {修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标

2 X* v8 ~- V, v' qvoid SelectSort(int* arr, int sz)
( B; H& E8 ]& V7 E: @. |  b{
        //闭区间: [begin, end]
* X8 ?+ [. C7 T9 y( {        int begin = 0;
1 a, e- K$ I2 s* ]- o7 }6 `        int end = sz - 1;
        while (begin < end)//begin == end 最后一个数，天然有序
        {
! j, Y4 Q3 V  u$ {7 K7 C7 U+ [8 b                int mini = begin, maxi = begin;
8 z) T) O( Q+ s3 _5 p  T) T                int i = 0;
) M4 s) X! v' e& r2 Q                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
  M/ b+ x4 {9 b: J; S  j! S5 I8 J+ a                {
% B6 J" E, h9 ]0 U4 h+ a" Q                        if (arr > arr[maxi])
                                maxi = i;
                        if (arr < arr[mini])
5 D4 H: ^9 G6 y. B# m: O8 k# U1 `                                mini = i;
1 m! m; [+ j$ l9 ?                }

7 k9 d. p' b# u6 h$ ?1 a# X                Swap(&arr[mini], &arr[begin]);

: ?  e- _- j# r) l' D                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
0 f/ c& @. n9 q3 S1 J$ G7 K                if (maxi == begin)
                        maxi = mini;
                Swap(&arr[maxi], &arr[end]);

                begin++;
                end--;
( l  q; M7 d2 T! Q  l/ ~9 S        }
/ ?  w& i7 Q5 h1 P8 l0 {; Y}

1
2
3
4
5
6
2 i; p5 ]( `5 W% P7
8
" G& F4 U1 x# O' c! }9
" E* }. x- ]. e' `: a& W3 Y$ o6 s10
3 b4 u3 c# a! l( z11
12
13
14
15
" t- @5 ~. Z  D3 K3 g( O16
+ s0 }; o2 M0 C! n' _- K17
: }7 O4 E1 d* K3 z$ V: ?- Y18
19
20
21
, H/ z1 m6 G" G8 O. [" D22
23
24
25
) g7 E( L$ S( f$ X( h3 J26
27
28
  v* d: _& x) y+ Q  [/ h
, k% W2 J5 Q! c4 i! m
3 I! ~# b& _. x+ T) {: B1 U( |稳定性
选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以

% a/ c5 `/ B' N选择排序是不稳定的

  d+ a: w7 s3 F% e6 Q+ \) W复杂度
时间复杂度
8 u4 V6 R' I' H3 b9 m& I最好：

比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2
' i. r8 g/ T/ T4 l# k# d; i
交换次数：O(1)，有序不用交换

O(n^2)
* v# ]5 v! W4 g" Q) n. x2 Y% E
$ _' C0 @; o- ^  M. l2 F最坏：
9 H' \% J( \; ?
$ ^; ]4 E  T  ?) y+ O比较次数：O(n^2)

交换次数：O(n)
$ e& w7 B1 I  h  G& H
O(n^2)
' ]1 o' M7 t+ d3 r! B8 z" Z
4 G  O! ]5 s- `2 E8 Y空间复杂度
O(1)
$ ?* P+ E1 |! H3 u
& m0 x* C7 T$ s" \/ H堆排序
思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆
+ X: w" D8 L5 r" q) g* _


操作
建大堆
2 k4 Y0 U0 @/ p单趟排序：
选堆顶和堆尾的元素交换，则堆尾的元素排好
每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
整体趟数：
若元素个数为n，则排n趟
1 v/ n. r# X% L0 I5 ?4 r) Nvoid Swap(int* e1, int* e2)
& K+ U2 p* L4 V# e5 u2 G{
        assert(e1 && e2);
+ h3 _; N- v: y1 m/ i
        int tmp = *e1;
; T( c$ V9 O% }9 F% v        *e1 = *e2;
        *e2 = tmp;
}

void AdjustDown(int* arr, int sz, int parent)
2 f( W9 y& E# _. d; B. ?{
. C5 P3 b) C1 W- F8 j3 Q        //建大堆，排升序
4 @% P$ q7 i/ g& X+ v6 m  I* L2 E        assert(arr);
       
    //默认大孩子是左孩子
        int theChild = parent * 2 + 1;
        while (theChild < sz)
        {
        //如果大孩子是右孩子则修正
6 E8 m" b! k$ Q+ M" h, y# l" N# G7 F" g1 s                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
2 N8 k( E8 m7 N* J' z2 N' d                {
                        theChild++;
) u8 y5 x: p- S. v3 B+ n8 K                }
                if (arr[theChild] > arr[parent])
                {
( Y, H. K  ^! p' o4 ?                        Swap(&arr[parent], &arr[theChild]);
, b0 I% `1 {7 I2 i, l            //迭代往下走
                        parent = theChild;
                        theChild = parent * 2 + 1;
: F. Q( T) \; s                }
; [+ B4 |! _% V; o  R, Q3 x/ N5 m                else
                {
7 K' O6 D) r6 h- `                        break;
                }
4 t& l, `5 J5 t( A  _! x        }
}
2 p- Z1 {1 t5 v( R) }1 l% m
void HeapSort(int* arr, int sz)
/ B  W+ |3 Q$ w5 u# a. F+ N' z{
        //1.建大堆
3 {. K" l: k( L5 \        int i = 0;
        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
$ G0 I5 J* e; T1 Q        {
' @& ]# o$ A; T& R+ [# x, @                AdjustDown(arr, sz, i);
% F( p# W/ W1 h* V# s        }
$ u) Z* `  w1 {# ?( w
        //2. 选数
! W  v# r2 _9 v- z$ n7 \- N        i = 1;
6 J0 [: \& S4 d  E0 M3 _7 _        while (i < sz)
) F" j$ W2 C, L3 p4 U) }        {
                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
                i++;
        }
1 `' ^0 i  a/ I: |" N! K/ l7 B* h( b}

1
2
3
4
% k9 a+ ?3 R: q6 M* h7 u) E7 d' s5
6
- l4 e- K7 w8 |' ?6 C7
( L5 }. ?3 ^0 B" M% `4 m- ^2 R8
9
- k, T+ R2 _. w, s' z1 z10
11
( j6 t0 {0 I  o$ O12
13
14
% o% i4 j+ g1 H! C( R15
% f7 b. f# N+ F. g9 q# s16
2 R5 A2 }& {- Z2 i4 l6 _' k2 L8 Q17
18
0 e5 r' F% ]7 _' z" g+ _1 V: g- O19
20
21
22
23
24
25
26
& ~, u$ i8 x8 ^/ ?7 _27
7 G# P( k& b( q28
29
) I6 E9 _. f/ w; _# U6 V30
0 _+ f, Y% t; G5 ]31
/ c8 F% S+ i* [9 B$ C, h32
33
34
35
) G- }5 i7 u7 i- {$ K+ _36
9 @( x/ J& n  {2 I0 O2 o37
38
39
  W9 i. _# n" r8 w8 X# p40
! N1 C% u% Y4 m) t5 |41
" l" Y) Y8 d4 k  d  A- ~42
43
44
45
46
47
& _! r3 x6 G& i% E* [9 n48
5 |: P  r" c  a1 Y" {1 _49
1 T, f* ]3 h0 b& [0 v8 U50
51
, I% c5 n' G0 S- u5 ]52
2 @) ~/ A- _$ f0 c53
' [4 }* @# `$ u3 q7 M54
# ~+ ~0 _: z. ]# \: U55


' k6 F2 e+ C* f  `稳定性
建堆和向下调整都会打乱元素顺序，所以

" {2 o# R$ Z8 I3 i; c- L堆排序是不稳定的

5 k2 n" p( l' Y% u2 |; F* x; O! P复杂度
时间复杂度
单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为

O(n*logn)
/ Y  M4 c% P6 D! ?' {
/ a9 g/ @2 S; Y2 ]" c& Y- ?6 ^1 }空间复杂度
原地建堆
( P" k2 V4 I% N1 D
4 u" T6 k6 k4 C4 m& F. S/ J5 A1 y6 vO(1)

交换排序
冒泡排序
思想
冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素



操作
: c- x1 {! C6 \, F! d单趟排序：
# I& A+ @. m$ _& D) _% d( k. }4 f% l每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
, w& i. B+ N' `1 ?" E每趟排好一个元素，所以需要排序的元素每次减少一个
8 V+ \1 N2 a! m9 }  Z- J' V整体趟数
7 n$ W; ]" a5 q, O若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
void BubbleSort(int* arr, int sz)
# |! u+ G4 F: n  C2 q1 }9 s2 T" f  K3 z{
- w6 q7 B; I) }: }0 t$ @        int i = 0;
) L/ b& E! g: c; [% e        int j = 0;
2 e  d9 N% _% [  P! G( R        for (j = 0; j < sz - 1; j++)
        {
                for (i = 0; i < sz - j - 1; i++)
# z5 ?8 v0 L6 r7 N, u                {
5 M: R( m3 ^# s- ^$ Q2 b                        if (arr > arr[i + 1])
                        {
                                Swap(&arr, &arr[i + 1]);
                                flag = 0;
                        }
                }
9 S6 O5 s0 }$ I! ~# b$ Z8 B- a        }
}

1
; O# W+ S7 c& a) s! T. @6 w& F0 q2
3
7 r2 c( Y/ d7 a! z6 B6 _( L4
5
6
! h4 {" F3 T" h7
- _. i. X/ H* O% C: c9 I1 y8
  C( L  L; D1 `# U4 w9
" V" h/ o1 h# l( G10
11
9 R4 Q* q* u- ]12
13
  X  M6 y, o/ p1 X8 R" s" ?1 R+ ^14
15
16
2 n( U% ]. v( C2 O( k. ~优化
当遍历一遍发现序列有序，直接跳出
6 {2 g* i% e* v
void BubbleSort(int* arr, int sz)
; L( U$ V' l* x( F7 B* k+ i2 z{
# H: D" m' Y3 ^$ T+ Y( B6 m9 G        int i = 0;
        int j = 0;
        for (j = 0; j < sz - 1; j++)
        {
                int flag = 1;
% E) E& p5 v# w/ h3 U, U, C                for (i = 0; i < sz - j - 1; i++)
                {
                        if (arr > arr[i + 1])
" k- _4 ?) P) a& U( v8 V                        {
                                Swap(&arr, &arr[i + 1]);
! Q! C2 P: N* m5 m( e: S" d                                flag = 0;//不是有序就置0
( L# H% A, y7 X" B% ]) u/ ^                        }
% M: _+ z8 i$ d                }
8 y2 D& U2 @3 Y7 R- p6 A& {/ k# H                if (flag)//如果一趟下来还是1代表有序
" W7 U$ M# Z! t7 }2 l6 L* _                        break;
        }
}
9 Z' i- h9 h/ N. C! B6 r8 {1 _
1
$ k; R. T( s( Z2
/ G' E& T0 k) W) Q, z3
4
9 [. v9 L4 u: c0 h/ z7 I& G& H# o5
8 s( W5 M7 v1 T/ Z1 |6 z6
% X& p, `. G; I/ O7
8
. w* g, [! t7 V8 a9
10
! v/ |5 R+ H1 K/ D11
" U$ g5 R! z7 S3 A2 z12
- J- s* Q1 P4 H1 `: P, L13
14
/ f7 Q& b0 O3 P. K( W. g15
16
17
18
19
; v7 \; i) i9 |4 G. v3 o5 P

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

3 C+ q7 F2 T* `5 a; m4 W( J冒泡排序是稳定的
. d0 ?+ W- K! h1 E' G
4 c9 {5 f6 |4 w复杂度
+ s- k0 R; Y9 Q* [; N4 r4 Y, h时间复杂度
7 V* D8 ?5 |0 T) D' h& c3 z最好： 当序列有序

未优化：

O(n)
. A# O1 |* G) f# ?3 s- D, W) Z' O' b- H
优化：

6 P8 b8 L! D3 t- H! b& t4 F! ~O(1)
- j, N- G' r( g5 S) H- u( O
1 M3 f% z% R3 \" H( o6 l; d最坏：要进行 n-1 趟排序，每趟交换 n-i 次
. j  b$ i& {' U! x( k* ~9 _; M
O(n^2)
' D- N) |; y7 H; e* n: i: T( Y
& ~& x$ r' |. Q2 U空间复杂度
O(1)
4 X! L9 i& Q7 l/ j* Z
* _3 a, Q: I0 Q) }: M' Q: g5 j! F快速排序
思想
  @! L# f. h+ R9 I7 d8 S! s( R- T分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。

所以快速排序可以用递归来实现

9 J& @& C9 E2 t2 s- E8 e$ \操作
有三种单趟排序的方法：
( \  ^! ^$ `. u4 b
8 C$ m0 C) m0 x$ EHoare法
5 s4 ?2 ]8 B) \设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间
8 ]* ^. t  j( ^& S- a( Z
左下标 L = begin，右下标 R = end

设 L R 相遇位置为 meeti
, P/ o/ r, m% F( G  h" i
$ S5 ^: z; P# k. G+ {​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”

​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“
9 v$ c, n9 W; Z, t; K2 ]" @
3 r3 ], g  E7 }/ Z  F' x" f选 键值的下标 keyi
9 _* G) }- p7 Q+ a; R" B
左1位置作 keyi，则 R 先走
右1位置作 keyi，则 L 先走
" z( _+ b9 a5 Z( ~( VR找小，

找到则停
$ F3 O" ?4 d4 i2 m; R! ]遇到L，则交换 arr[keyi] 和 arr[meeti]
* z' y6 y( D, y* f3 J. F1 S/ U5 fL找大

/ {5 j! x) L6 k, q0 Q- D8 Y找到则交换 arr[L] 和 arr[R]
遇到R，则交换 arr[keyi] 和 arr[meeti]

5 j: Q8 G3 c/ t
- V* v1 L' t/ O% m( B; a! `解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
, v4 ~& K  W0 }! a# \- E答案是肯定的：

- K0 f) ~" E8 V: J# `7 b' F2 E5 h, K
8 |" ?: A5 [1 h+ w# f  ^  f9 p

//[left, right]
& s/ Q5 c- _2 V1 K$ x' Eint PartSort(int* arr, int left, int right)
6 Q9 `8 K* ^" R: @2 l" j9 x{
        int keyi = left;
' r" F9 w2 h6 ^! [+ t        //相遇则排好一趟
1 V4 g3 K) k6 a& L5 Q1 [        while (left < right)
        {
) M; \* b' y& z: b) u) E- g                //R找小
3 J, U! }0 H$ t8 E        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
9 ^; d( W2 W. O  s4 B8 A1 ~                while (left < right && arr[right] >= arr[keyi])
                {
; p( S- K, ~. G' e8 I0 q2 y; ^' E                        right--;
                }
7 D9 x& o9 t5 @  s* Q8 d' `
# r  w3 d% s* c! c7 b                //L找大
) ]2 o8 K6 C$ b- D$ a                while (left < right && arr[left] <= arr[keyi])
                {
# Y1 }! s; K8 P/ t( B6 T                        left++;
1 d8 y* `: ]6 X/ H. v                }
               
$ J: b4 Q1 S& h4 h* `        //相遇就不交换了
                if (left < right)
6 M' x( I4 d+ T$ G% M* |8 i                        Swap(&arr[left], &arr[right]);
3 z5 \0 ~. K* H: k1 C  K6 s        }

        int meeti = left;

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

$ M; S- L6 I$ |' B: }; M, W2 c4 f        return meeti;
}
/ V- ]  v( L4 j
1
" |. ~- Z4 h$ z% ]2
+ w& ^7 ~, c$ E( p7 o3
8 P' ~) d7 H) i8 P1 u4
3 W  A1 F2 Q8 a6 U1 ~5
+ r' N0 e" I) l$ ^" b% r6 P6
$ u$ T' {$ h: L# n7
8
6 \' k) o) h5 C* @+ T8 v5 @2 G8 a9
) p8 Z3 s" y8 O10
11
12
13
) z) [  ?# `) T14
' D) q8 D  Y! J6 D( H15
1 v! }: r1 D6 D+ X5 c16
0 ?$ a5 Z& |: w' y17
5 A# `/ I- [' a* N. X% T' f18
19
4 j; d3 C. e6 W1 M20
21
22
23
% }! J% {2 a2 R  G24
9 m6 ?9 k- u' i: L4 H6 s25
26
27
28
3 s, F: T. V7 d8 n, \29
30
31
32
4 S/ }% ~$ {- o# ]/ W( j

解惑：为什么key要选左1/右1，选中间不行吗？

% u5 T5 w' H" t7 K! T2 P0 U$ u
5 Q0 H( F% `# `1 K' |可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深
8 ^3 S6 Z( i0 h9 Q9 ?& T- Z- l
2 Y6 _0 }) V# ?+ W$ G' V+ L5 d3 l4 k# o' C
6 A7 `$ w& p/ k
( V1 N: x: B. I8 A* R; M
非常容易栈溢出，怎么解决？针对有序情况，优化选key
& u8 l4 x* p7 s
优化选key
随机选 key （是一种办法，但是不那么彻底）
选中间位置作 key
解惑：那先前实现的单趟排序不就失效了吗！
1 Y9 v7 S3 r, k* S1 Q5 v：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑
7 T, w  \$ s4 v7 w+ s* m
解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
# s1 c0 r, C* [前辈给出三数取中的方法
; A+ H8 k0 S( h0 G$ |) d. i7 {
三数取中
5 x8 C4 N& ?3 R7 S5 {6 ?在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
" X  t$ C% S: s! u* W: {# t这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
3 y! ~6 p! s( q优化选key后的Hoare单趟排序：
2 t5 l: G9 R7 u1 Z
int GetMidIndex(int* arr, int left, int right)
9 r* O2 W( T( E  h8 d3 C+ Z* T( ?4 j{
        int mid = left + (right - left) / 2;
//  int mid = rand()%(right - left) + left;//增加了一定随机性
( q: P9 ~3 U; q        if (arr[left] < arr[mid])
        {
6 }0 @- o. H2 V3 h. ^                if (arr[right] < arr[left])
                        mid = left;
                else if (arr[right] > arr[mid])
                        mid = mid;
                else
+ t  u% R2 G" D% V0 W                        mid = right;
- O  k# K" _3 r- X6 G7 L        }
+ I+ B/ W0 j/ L: Z, Z$ o        else//arr[left] > arr[mid]
3 F% s4 z( S5 V: K, N        {
# j: a% \' w9 N2 O                if (arr[right] > arr[left])
                        mid = left;
3 E5 |/ h# ^/ E) D2 E( _                else if (arr[mid] > arr[right])
                        mid = mid;
                else
                        mid = right;
1 r2 X- P0 i& m: u( K6 x1 N* b# I        }
        return mid;
# J+ N. k, ~1 D& N}
5 w' L& V9 j# n0 p% O
int PartSort_Hoare(int* arr, int left, int right)
! Y  Z7 `& [# U1 g9 \$ |( F. V* ?{
        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
- _4 w7 U7 M* G( Z5 a( T3 o        int mid = GetMidIndex(arr, left, right);

% K9 M. e" I4 _        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
1 Z! J, S3 i. L: H2 c: l! b0 ]        Swap(&arr[mid], &arr[left]);
! a2 ]& i. C8 D, E! z
        int keyi = left;
        while (left < right)
. a5 @9 A$ K: t  Z8 ]        {
7 F6 ^! g! r; E5 D                //R找小
+ {& R- D7 G: o8 e2 r                while (left < right && arr[right] >= arr[keyi])
9 A2 x, V' _4 Z( i) ^: L2 N                        right--;
, y) e, _' Z/ K! {4 f. Q8 G: t+ B
: A4 D& t& \2 B                //L找大
                while (left < right&& arr[left] <= arr[keyi])
" i7 h. [; Z, d$ z! N$ Q0 h0 J                        left++;
$ x1 E! f" ~! d/ W# j  D- ]. j
! ]; K- M* j1 a7 a                if (left < right)
% n  H( N4 ?  z, B3 x7 q                        Swap(&arr[left], &arr[right]);
        }

& l4 o" R6 l3 [7 B0 W, v2 t        int meeti = left;

" ?2 e& s3 w' A3 K5 R        Swap(&arr[keyi], &arr[meeti]);
' t) p) j9 p' T
8 u7 Q; k9 K' U( X2 Q9 F& k        return meeti;
}

1
/ {: u8 T5 T& q+ {2
# @7 c( Y2 C5 `6 ^7 \! T3
4
5
6
7
8
3 K1 L9 I' B( V* C2 S9
; \, n) J% q# J9 N10
11
12
13
) Q' \3 H2 H6 P% n4 \14
15
1 t  i; a' v: K5 F; u. [16
' A) G6 g8 y; Z. O17
18
19
20
21
22
23
24
25
26
' H% ~/ e/ c1 v. |27
28
; Z/ J: V  n+ C; p29
0 |: r! a# k' v: X30
- g( s2 ?2 ]( e31
8 Y9 J9 F8 w$ G" Y32
33
2 ]! }. h9 C! I0 {: c$ \34
* |, C7 l% V% \0 s0 h9 m35
7 ^. T6 l! e: V4 l36
37
0 D0 \0 M/ y# x! I4 v38
39
40
41
42
43
0 o* I5 x: h* @' t: g/ k44
: m7 a* S6 [; w8 Q+ _- A45
46
9 U2 N" P4 [, X& t47
48
: H) d4 l) W2 `% R3 D0 j49
50
51
52
53
0 ~& I# B7 T# a/ {# k$ P. ]. u( Y54
: T( e. f# T: O9 e/ F* y) W; j) ]挖坑法
初始状态：L作坑，其下标存为key
(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
9 \; }! R, F) W1 R重复 (1) (2)
最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]
- d, m; i5 O; J1 ~
3 p2 b7 }, E7 ]0 ^+ s
  p$ w# x9 R/ p; I6 H0 pint PartSort_Hole(int* arr, int left, int right)
6 {/ F6 G0 p. B. Z2 r6 k4 F{
' y. X2 n1 E' ~) j5 E- H        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
7 ]1 f1 T4 n' ]
4 ~/ C  A: \1 o) V+ k$ ?        int key = arr[left];
        //L作坑
3 t2 m9 v! S0 p# n        int hole = left;
* s, @7 l6 I, `! M* k  h        while (left < right)
8 z2 \4 u2 T" ]7 ~0 O        {
+ n  j& i* z3 x' `$ P3 O' W1 g) t                //R找小，扔进坑，R作坑
                while (left < right && arr[right] >= key)
                        right--;
1 D6 \3 Q3 s9 {( u/ L4 d* W                arr[hole] = arr[right];
: W  Z8 X  G+ C- c7 }9 x: M                hole = right;

  L. q6 Q# r$ J, N                //L找大，扔进坑，L作坑
% G& T9 g. o$ U0 y/ g                while (left < right && arr[left] <= key)
                        left++;
                arr[hole] = arr[left];
$ V+ @6 \  C6 N4 x                hole = left;
' f0 D  o$ M8 K, A3 K: Q* u. o        }
$ Q$ e6 U2 Z/ R; A* t  Z: W( T0 m& I        //meet
: L/ P6 }6 w: V# c$ R        int meeti = hole;
1 z- G( A- l0 B3 H: [) h1 K# e        arr[meeti] = key;
0 R4 |% J( |9 w  L9 ~$ `5 K! {
- Q* H  d/ u0 R( o( \        return meeti;
}

1
2
  g7 h$ P% r& t! H- r0 R3
; q$ E9 T& W9 l- I4
5
. c( B* H3 ]! E% i5 T6
% _4 N' _  @# f. [! U6 ^6 X: |; G7
8
' v7 l5 S1 D% c& f7 S. Y9
10
. {5 m1 }( @% a3 o& N6 n& ^11
) h* p7 m! v) v4 q: q( t+ @! Y12
% y/ S. h2 {$ }13
8 o6 ]0 B* T7 M1 c" F' R3 w( A14
( q* p; n+ i% @! h3 X* p' b: Y15
16
17
+ }) q& s1 Y/ U& ?18
2 i1 ]) T( I8 a; E! f: ^7 ?$ M19
0 {, Z( W& s! ?" ~1 }20
21
6 y# M3 |' ?' b  A1 O5 a22
23
24
25
26
27
' a3 `8 Z: {$ H/ Q3 H# D28
% b- {8 N+ a# w" g% x9 {前后指针法
# [  X+ U6 n' J9 F; }5 ~' p此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多

  t: P1 w% s! n5 Y- Zcur找小，找到则停
++prev
4 ]4 h. H; {$ p/ U如果 prev != cur，交换 arr[prev] 和 arr[cur]
如果 prev == cur，不交换
当cur越界，代表找完，排好序了
, \! S8 _8 A6 f+ |prev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低
; T4 J6 k& \9 F+ a# |! l
, g& y4 x; W. N. Z8 N
  p; M2 V! W9 Y2 x5 X; k* U5 a! m
int PartSort3(int* arr, int left, int right)
% {1 Z; d. a$ w0 G{
        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
       
  //int key = arr[left];
, z  u* }# Y3 |, [' ?        int keyi = left;
) L. @# v- O# U& {
        int prev = left;
7 M2 |! F/ V' k5 W        int cur = prev + 1;
/ u$ h! E* W$ E3 [3 @       
    //cur越界：找完小的，prev的左边全小，prev右边全大
5 x% {0 W' Q3 H8 {8 s$ n! a        while (cur <= right)
. r9 i3 r, L4 T6 P+ d; j        {
3 ^" G3 i4 o+ A( ^3 x+ j" |( B        //++prev == cur 没必要交换
                if (arr[cur] < arr[keyi] && ++prev != cur)               
# }$ ?& }5 s7 Z7 A                        Swap(&arr[prev], &arr[cur]);

& K# A; f4 a8 w% i; F                cur++;
        }
7 d; s$ Z( T$ S  ~0 v
        //键值存是的值：
+ d$ i: G& I2 g        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
        //Swap(&arr[prev], &arr[left]);//这才对
) j: g: u1 v+ y( k    //键值存的是下标：
4 h. E  Z" u' d5 U  b        Swap(&arr[prev], &arr[keyi]);
6 q0 T$ V% h8 b
        return prev;
}

1
3 H0 [/ @+ c- n2
! s) G4 h6 f* h, Z" _3 O+ Q+ G3
/ B4 u3 u& _& `4
5
5 |' r/ e7 ~# k5 X6 A+ u% [6
! |1 H  g9 d( O7
1 i: {  H: \( }- P8
" r, m, Z7 Y5 X7 [& n6 X9
/ J3 Z' b( u4 n) {! T/ j10
11
12
13
  W" T+ c9 Z2 c% _* Z' i14
15
16
6 Y. o) e) N( X/ u; Q9 U) ]. T17
. t2 g) z+ i' J: B. a$ O18
19
0 r4 E" Z- J  c, |6 w) }20
$ U) h6 R, l) F: q5 j# V! x7 e: R21
- r4 ]! b9 d& i- @8 s3 T) d22
23
24
25
26
27
- b: j2 L' P! F% q4 c28
29
整体排序
递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

- h( ~* w+ L0 Y. d//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
# s( E" y, V' M3 ~# e        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
3 S  D, j9 P$ @  Q3 L8 B9 |        // [begin, meeti-1] - meeti - [meeti+1, end]
                //1.begin > end:超出范围
                //2.begin == end:一个数天然有序
    if(begin >= end)
        return;

                //排好meeti
4 L5 m- f9 P8 E. K" M& R6 y1 i                int meeti = PartSort3(arr, begin, end);
. W6 H) Q2 H, d' o- A/ B  {6 X
                //排好左右子区间
                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
; H% A) t! ^% W        }
}

. |& N' P6 R% E& O1
$ ?6 R; @& t9 \1 b2
3
) J) o/ d1 A; ^# g. L4 M4
2 s4 [, F* F& K4 R- [1 `5
6
1 H) r7 X/ ?# Z, R7
9 b) M$ q$ V  D, O, d5 u8
& F9 ~, O. j9 D# ]9
2 u& R6 x& j& y5 }# A1 u6 s10
11
/ z- U% F+ z6 N! c: y! l12
13
8 V( o2 d' P4 c4 E14
. I$ x! }! R" }( \+ p15
16
17
4 i# V7 ^& a. p/ a/ b" ]18
…
6 `. j! i" M8 V9 T
1 p6 l# C& Y0 H: W6 Y: _没想到吧，还还还还有可以优化的地方！
) c& O* |7 A& p& d; @0 o. x7 w- H
优化小区间

' a$ _. d  o! ?2 |
1 Z5 P* j! I, Y如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序
8 V4 Q! [- h# @! l( ?' v, O
那什么算是小区间？
3 D  ?& X9 g9 z$ K7 a1 }
4 ~2 M& {0 ~7 _其实小区间没有确切标准，8-15左右都可以的
9 z" A* p  a. ~; z" D/ l

5 D- \2 E( K) ~  G% X这里就把小区间定义为 含有 8个数或以内 的区间

//[begin, end]
0 ~: T# n6 ], Q$ Q7 zvoid QuickSort(int* arr, int begin, int end)
) _. h) K$ R, w4 o9 p8 N{
+ q) G  p% W0 d0 _3 N) Y        if (begin >= end)
                return;

        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
        {
$ \% H! \! ]- N/ `3 V; T                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
' o# h# c. A; n" ^; v                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
9 x# D* V6 N1 W- P: G# u( E) x        }
. \: K0 {& x8 @# l        else
0 H' @) Y0 R: N' p* G; w+ L        {
8 M3 U! j9 a) F! M* |, {                int meeti = PartSort3(arr, begin, end);

                QuickSort(arr, begin, meeti - 1);
+ [* M. }% k# }5 {                QuickSort(arr, meeti + 1, end);
        }
: s0 B8 x" d( g8 e}

1
2
3
5 N8 F  n# d1 _4
* s9 ]0 w0 L; b3 i+ b1 `5 z: U5
, \2 Z" g- v/ L: i6
7
8
1 Q. B- s( L1 e# n+ X9
10
11
12
2 ~' i' R$ v* }! O7 E0 j& n% P) P% \13
14
15
4 c& f6 P% `5 Z' s16
# @# O8 P( b, s, m17
9 z" K  v$ ~8 [+ I+ V18
3 n) G7 s/ K' J- A$ d- |19
/ Z* T4 n* j, E快速排序非递归
: a% y6 ], y6 R8 y# v0 ^% G为了解决彻底递归深度深的痛点，我们来试着把它改成非递归
  t. K9 D+ W* g6 p& x: ]6 D/ h
思路：
递归深度深，栈的空间又小，会栈溢出…

3 X: h5 g- H4 C/ Y" l0 W那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！

6 ~/ v1 U8 r; j# ]: x; z% E核心思路：在堆上创建“栈帧”
, \' Y: `3 Z# r
  F7 w- Z1 l: c% u! }. c3 L快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的
% r5 `$ j2 ]  k

( ~) S: y3 u& d' X4 `
在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：
- B8 x% q7 W- q. B
先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
{
        ST st;
        StackInit(&st);
       
    //先入begin
        StackPush(&st, begin);
! t4 c5 n1 a; Q2 c; f0 o, a    //后入end
5 k+ {9 V; R: A4 ]/ i  j        StackPush(&st, end);

        while (!StackEmpty(&st))
3 F0 b9 x& L  o* V7 d        {
                //先取end
                int right = StackTop(&st);
                StackPop(&st);
2 u  k' {% B7 X5 c  ]! g6 }4 ?2 o                //后取begin
                int left = StackTop(&st);
                StackPop(&st);

) a" \. O& `9 E( Y                if (left >= right)//1.只有一个值  2.区间非法
1 Y8 o& }* H* f$ X2 B/ p                        continue;  
                               
1 s$ C1 @5 m6 R# w# T6 B9 `                int keyi = PartSort_Pointer(arr, left, right);

                //先入右区间
                StackPush(&st, keyi + 1);
- L& {% o" Q% `( r                StackPush(&st, right);
                //后入左区间
  H$ r( X) g# Z' d- P                StackPush(&st, left);

                StackPush(&st, keyi - 1);
        }
% k; _3 m' J; Q7 G3 P8 \3 C
% \; f( S2 w! @9 x" n        StackDestroy(&st);
}
% l/ H5 ~5 W/ L: Q
- n5 a3 B' z! }- E& J& u1
2
3
! L1 d. g+ E8 K6 T4
5
6
7 k/ @# K8 e$ b' ]( Y# K  i) O6 B6 j7
# D- Z3 K5 ~& U( t  q# t# N8
9
10
11
12
13
* y- O$ u9 j. T' b- {14
15
16
17
18
19
20
21
22
) y4 v3 X4 u# r$ W2 U1 S23
24
25
26
27
28
! o; I! J( e& `% n; X29
30
31
32
& z2 x+ j1 Z4 G; ]0 O+ i2 n33
34
+ t  Z7 v+ I+ ]- k7 B. e7 a5 x" t35
数据结构栈的实现可以看博主之前发的博客


6 |/ s! w' {  @& W3 f/ L: F归并排序

…
8 S! k! l( W! W# j0 k( e- F9 A1 O
性能测试
void TestOP()
- D, b% @' x) J/ `5 K3 E{
- U/ i8 m7 d! h* E        srand(time(0));
        const int N = 100000;
7 ?; g; m- f  m. [9 x; m  H2 G5 v, m        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);
" m$ V7 e2 p- L$ w& b. X        assert(a3);
9 f. K8 J* k9 Z, y$ R: f4 b( s& v        int* a4 = (int*)malloc(sizeof(int) * N);
6 C/ E& ]& k( N/ H        assert(a4);
2 y! x8 w5 {/ k; o& ^, @$ O        int* a5 = (int*)malloc(sizeof(int) * N);
; I- Z4 F# W5 B  u9 _2 ^        assert(a5);
2 g: |$ N. H4 X7 }4 @
        for (int i = 0; i < N; ++i)
        {
, d5 R2 w# X. B* C0 R# X) o0 b                a1 = rand();
/ L# n) C8 @' u# u9 \" X9 c                a2 = a1;
                a3 = a1;
( o) s; D; e+ E  O                a4 = a1;
1 [4 x2 w  z; _9 b                a5 = a1;
        }

        int begin1 = clock();
        InsertSort(a1, N);
. |  E. x# B. F5 c+ J  L        int end1 = clock();
: p6 F! k: Y$ M, ~' @
9 F: r/ C" l* z5 l+ Q+ E$ @        int begin2 = clock();
        ShellSort(a2, N);
        int end2 = clock();
, E6 e$ E( w0 \! k3 |. h
3 V% o+ o$ }& @5 s+ o* ?        int begin3 = clock();
        SelectSort(a3, N);
        int end3 = clock();

        int begin4 = clock();
        HeapSort(a4, N);
0 m2 I7 q6 M' o        int end4 = clock();
, ~4 \) H- I- b3 p$ S' E
4 `& Z: A  r- |& b        int begin5 = clock();
        QuickSort(a5, 0, N - 1);
                //1.中间key
                //QuickSort(a2, 0, N - 1);
                //2.三数取中
                //QuickSort(a2, 0, N - 1);
                //3.小区间优化
                //QuickSort(a2, 0, N - 1);
        int end5 = clock();


        printf("InsertSort:%d\n", end1 - begin1);
& K5 e! D- m; s. S7 _7 Y" l/ d" P        printf("ShellSort:%d\n", end2 - begin2);
* i# M7 [- L! c1 D9 W* A6 e( i        printf("SelectSort:%d\n", end3 - begin3);
2 I3 D0 b$ a2 T9 R: `$ j3 F        printf("HeapSort:%d\n", end4 - begin4);
        printf("QuickSort:%d\n", end5 - begin5);
) {! Q! `" M4 T9 c% D
        free(a1);
        free(a2);
& A6 ~3 P( v$ c5 n$ h+ ^        free(a3);
        free(a4);
        free(a5);
}

5 H7 ?% g( A3 R9 {* R: N" P1
" z; _; y8 `+ z  y- l6 S2
3
; X  C  k  s- G4 b) r' F4
5
6
7
8
9
$ ]' D; j! w$ p& J( e10
) D+ A* K/ g# d; Z11
12
) S8 c! ~3 o$ M( Q" _13
/ d7 ]3 G+ w  F# F) Q/ ~14
( p% g2 m/ |" @" z3 x1 C3 \15
  F, s/ @5 a) x7 r0 c0 Q' E16
17
5 c' T2 I2 t1 V: k18
19
20
; S  k( t4 P! Z; [: [21
0 e7 c! ?/ G4 L' o22
/ \' O3 O& o  {- a- g/ C- N23
24
25
9 B  K! \: e3 a( }6 D26
27
2 z3 ^' J- |, t: z/ G) ]28
29
( k" d; `, b) b% y: A0 E3 c30
31
32
33
34
& A7 D$ O- I" c) c  D2 d35
36
9 X& I1 x0 h9 D; |) H1 r- D+ E5 z37
38
2 D: x( @) {9 N( [) v9 C39
40
% X3 h3 i, D5 M/ k6 R" l41
42
3 b% M" q3 V& K43
44
: @: y5 `. ]  D2 t45
, r0 W1 f) M- ]# |& h9 O  m& @46
" G- j+ Q+ O6 F2 ?: T47
48
49
3 ]" x: t! v: w+ K- e50
51
. r, L- u2 f0 U" |8 F52
53
3 U+ V/ G0 M! O; @54
55
56
) b) {7 g1 w" ]1 ?& {, f7 b3 P57
* R! B1 t' ?2 c" b58
59
( N& R! `+ T$ G0 v6 a0 k60
61
, i- V6 i! l& E. _4 I. T' ?62
) U, N0 N% \$ ^) k: r63
6 r3 A& y3 D6 ?/ v

+ V' {# o; G- S) O4 m; a  r不愧我们费这么大劲优化快排，多帅哦！
4 Q% g. i# K5 c: e) I
差一个归并排序，后续补上！

+ p2 X9 v4 u/ C. Z- ~: d不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
% Z2 Q# T  j! V8 c: C! |, G, Q$ t6 e————————————————
! _. c$ d0 l, J8 w" Y3 |( i. ?版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! v; n% c( s) g. W# o( c原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832

/ h  Y: y, c5 ^8 [) ~" T