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

杨利霞

【数据结构初阶-排序】经典的排序算法，很有趣，有没有你不会的呢
2 A  `: X9 }* _) F  Y
5 U6 G) H& [9 K! T7 U前言
本期分享经典排序：

插入排序
直接插入排序
( N9 Z4 C6 @/ A1 F- K希尔排序
选择排序
直接选择排序
7 A- L; [1 h0 Q$ w堆排序
: B3 {4 ?9 `* ]: m! F" y/ x交换排序
冒泡排序
快速排序
注：讲解时默认排升序

插入排序
' g) [% h* @- W; y2 D+ [直接插入排序
思想
% f4 X0 q; e2 V9 j+ I# T/ P3 @* F插入排序，就像玩扑克时，摸牌的过程：
& |. O8 ~* U- o! z
最开始，左手没牌，右手从牌堆中摸
右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
如此一来就能保证左手的排始终有序，摸完牌后也就排序完成

( n% ^3 L2 a3 N# d9 f# z
操作
设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
单趟排序：
2 Z3 \% J8 ?8 a3 t4 a每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
是正确位置：插入
不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
整体趟数：
若元素个数为n，需要排n趟
7 e/ O1 \( F2 p9 g7 pvoid InsertSort(int* arr, int sz)
/ W0 ]; a4 N5 P* d; _{
        //end + 1 < sz
& a  Y3 W4 y2 S" R$ z* j( r        //end < sz - 1
        int i = 0;
: v) T9 @, W1 A& O        for (i = 0; i < sz - 1; i++)
        {
                int end = i;
                int tmp = arr[end + 1];

                //找插入位置
0 |6 N$ g+ {4 N% s                while (end >= 0)
0 d; @: N1 i* f: I. t                {
3 W- F, m" U5 p+ J                        //不是插入位置：当前数据往后挪
% @! M: ]% }7 q5 z3 P                        if (tmp < arr[end])
, n! z: x& L- |: g* O                        {
                                arr[end + 1] = arr[end];
8 H4 z! \* v4 [! m                                end--;
! I# v% k( u* U; B                        }
( b) A' J( K6 k% v* K                        //是插入位置：跳出循环插入
                        else
                        {
3 P0 S) _# Q) e) [3 T5 @/ N5 o/ u! P                                break;
- Q4 N7 F3 a! [. H& W8 q+ i" o                        }
8 M7 G) ^4 u% z" ?                }
                //插入
                //1. 插入位置是[0]，end == -1，不合循环条件跳出
2 B6 q3 u5 a1 |5 e# v                //2. 找到插入位置，break跳出
                arr[end + 1] = tmp;
% Y$ I6 Z) w1 W0 M( O) y4 ^        }
}

1
2
2 O% s! i* M( j9 M' h. q3
  K! o% n$ ]7 c# f4
; x) G! z8 o* {& f. M9 h5
: d. R3 R- n1 F9 F% d6
7
7 H$ j/ [, P0 l! h! C# l8 }8
- m# \# z5 j; Q! R. ^+ O& l9
1 |# `! b  q3 ], |3 u10
/ D$ S; |' K* u' @) k) ]% \11
% n/ e& a" B2 w# Y3 K6 {& f12
) t( q7 c% u" E" z13
14
15
16
17
5 I- z" p8 M8 S4 A18
- v0 \2 |. H/ a1 m7 L19
2 L* s0 _. v+ y  j1 ~! z! i20
21
7 I# L5 k  M' }  j! t( {7 z22
23
4 [( L3 X$ D/ e3 F4 T' t; O- W0 c24
25
/ P3 F6 L3 z* N$ u( m4 T26
$ Q2 t- |: t0 q9 A: I1 a4 ^- A& O27
28
29
30
0 R4 L/ _9 d; B. u4 _# L" Z" D31
5 y/ ^# y$ T5 o# x, X3 a
3 U7 g- V! x" [. [8 _# z, y
稳定性
插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以
2 F1 t: u- Z+ N% p  @, y& e* C' S+ p
直接插入排序是稳定的
$ X. `* {" M9 p: {
! F, H% B6 |6 D4 b8 o复杂度
1 G; j; Y5 b8 J4 W时间复杂度
最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）
) D; p2 ]; u1 U  f/ s, H
O(n)
8 F. y( q. h6 K. s! q) j. t# C
最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2
2 l6 [. F3 _8 C+ `. ], }
8 e+ F& ~8 n; E1 n) i( rO(n^2)

7 j) [4 Z7 U' v空间复杂度
* H) g) X1 O  e$ ~! x" w+ |3 zO(1)

" e& J! g" T. {希尔排序（缩小增量排序）
$ H1 E! H) I  b  F4 e2 x希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序
0 Z6 a( ~* s5 M* ^8 ]% f, L6 A8 j
优化思想
增量gap不止用来分组，也意味着数据移动的步长，所以
9 n& i4 q  P; j1 k. P" t% S' ?
; b' G2 n# x, Bgap很大时，序列很无序，插入排序的元素少，移动快
gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高
: E3 O% }: \5 C3 ~* D. T. e

' w5 E5 U8 J: k9 [操作
单趟排序：

设定一个不断减小的增量gap，也是元素移动的步长
1 q% [  [: t7 Q4 S! P以gap对序列分组，并对每组分好的序列进行直接插入排序
9 O% j; i: O6 x$ o4 X) A2 e3 t不断缩小gap，并排序
*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
整体趟数：
; p- z* z, i6 q( v9 j- H
由gap决定：当gap = 1，排序完成
: x" M2 u5 R& s- l+ a/ U! x' d注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。

/ f0 C' n! ]  _2 m, z, {( mvoid ShellSort(int* arr, int sz)
{
        int gap = sz;
2 O4 [$ u8 A# N# @) A       
    //gap > 1，预处理排序
    //gap == 1，直接插入排序
. l* G) C0 e5 D$ j( S0 I9 P        while (gap > 1)
        {
                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
* u, g* G! s2 S- t7 Z5 q# D9 v                //gap组
                for (int j = 0; j < gap; j++)
6 f% \2 Z3 F$ m. ~" M                {
9 ~& q6 F8 J% f- z            //end + gap < sz
$ v9 H/ u# h1 W% @- o                        //end < sz - gap
                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
                        {
                                int end = i;
                                int tmp = arr[end + gap];
                                while (end >= 0)
5 j7 E" y( G+ k% A                                {
                                        if (tmp < arr[end])
                                        {
                                                arr[end + gap] = arr[end];
                                                end -= gap;
# K2 A5 S( G" N: f. s( O+ Z. ~+ T- x                                        }
                                        else
                                        {
                                                break;
6 h7 H% d- x  p# T& C/ c$ c0 V6 K                                        }
                                }
- x- e2 W( S2 A4 E                                arr[end + gap] = tmp;
                        }
                }
        }
}
( R. w! Z6 ?0 J
1
+ z! J+ t, D6 K3 G6 O3 P2
) d% f6 g# i5 n. I3
& v5 X1 _3 \* G$ g4
5
6
: {# V; ]+ P: W7 s+ ]4 W2 r7
( T0 W# {% M: s8
: J/ H2 F# y) Y+ Y) p5 F' N* X9
9 u. m# V/ s4 Y10
5 C  c5 G7 ^3 \: z, q" f11
12
13
14
  Y6 V5 j6 L( s, e# h$ U15
16
17
18
# S4 a- @1 ?+ t7 h1 n. r19
20
21
; B. G: w) d0 k8 g% Y22
( t8 B6 Q5 p! S% Z23
  E! v7 a5 ]5 s7 C% @. h1 O. p24
, ?' c- s% H9 i25
26
) N" f* V  A8 s5 k; n27
28
. Z  z9 j6 Y" e! r29
0 N7 Y' |$ L. w( d1 o( h30
1 ^' M$ T4 R' g4 ^31
32
33
34
' [8 j. N& V7 u1 _' N  c8 W% Y% A' l35
其实就是套上”缩小增量“的直接插入排序


稳定性
我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以
2 v6 f  u7 w2 @# Q! @' ]
( p. K6 q2 u8 E2 o$ j6 I( S希尔排序是不稳定的

) h. H8 K+ S9 J7 ?9 `复杂度
时间复杂度
希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
, }9 J8 }8 q! \- q
O(n^1.3)
) i3 x8 `% T1 _" s
空间复杂度
7 x4 t5 S) W; L5 e' m* }/ @O(1)
$ L6 K  U, P0 F
选择排序
直接选择排序
思想
6 s, d; M; |7 h, U( ?1 G# g选择排序，遍历序列，选出最小的元素，交换到左边
* `- Y6 d/ S1 j$ L- X5 c
1 l3 }8 P  y( K5 |6 W

2 Z" `# ?* H6 H5 r优化版本：
% h1 |" l: C8 c5 N7 O
# H' G+ x# D+ a* x; _/ r8 \每次选出最小元素交换到左边，选出最大元素交换到右边
6 L. n, o: [1 c; j& ^# |
操作
4 \. a) }8 ]8 K; u设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]

设 mini 为单趟遍历中最小元素的下标，maxi 为单趟遍历中最大元素下标
+ m( p# v& S+ W* P/ l2 m
) s9 e& [1 x. t! M/ [单趟排序：
0 C( G0 i' ^5 V
( T" j2 z; w7 g  E遍历选最值的下标
交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
/ K3 s: N5 i; x: M2 B6 q（修正）
整体趟数
6 }: I4 `  {3 C
$ q+ }' O% Q, C  R# H# I若元素个数为n，趟数为 (2/n)
) l! A% d6 ]8 E7 K, A) ^$ \修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标
% [' p1 ^6 w9 F
void SelectSort(int* arr, int sz)
{
# E6 J* p6 D3 K! P! r        //闭区间: [begin, end]
$ Z9 F; }# f3 b  Z! x- j        int begin = 0;
2 J) W( r8 ^; {3 H* W) y/ E/ W5 `        int end = sz - 1;
        while (begin < end)//begin == end 最后一个数，天然有序
        {
                int mini = begin, maxi = begin;
- v( f+ ^5 ~4 @9 J8 S2 K                int i = 0;
1 f! D7 B" u" s# k0 C9 D" P                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
                {
                        if (arr > arr[maxi])
                                maxi = i;
                        if (arr < arr[mini])
                                mini = i;
                }

6 t/ f0 n+ e$ @: @* L& s                Swap(&arr[mini], &arr[begin]);

8 @; e. ]0 }" A/ p. m7 n. \8 e* S                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
                if (maxi == begin)
                        maxi = mini;
! k8 H) W$ \3 ~2 n1 M! ~3 G                Swap(&arr[maxi], &arr[end]);
7 t* |0 ~8 L8 d) C
2 S$ t) Z& e+ R. V  x! ~                begin++;
                end--;
        }
, w/ e$ n4 s1 m% Y) g}

! V% l; \& i* T2 j+ D- A1
2
3
4
- D0 s1 `9 ~" B# U  e5
6
7
8
, z! G8 Q4 K  J: w, D! `5 S2 Q9
10
11
7 m# i) U( I: g2 g* {1 ]12
: {& V- ]/ z! q13
14
+ q- y3 S3 |! I" |* |, ]1 i: o15
9 _3 Q7 F4 f+ `, N% M/ v16
: |( |+ Z0 \" u7 C17
18
19
20
21
7 }4 [1 `* x$ @4 H$ x9 }22
! T/ n8 k7 n4 V23
24
6 i0 @0 R! q! e25
7 X9 P. E& }- S& |+ x! j26
27
' C- k1 x& a9 |28


# H0 q' H; a- o8 u稳定性
选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以

选择排序是不稳定的
* k3 K  G, Y: F+ w: _* ~
复杂度
时间复杂度
最好：

/ H, i: n! A/ m; k* d. G8 ^比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2
# S0 _+ c# Y& y% W* B6 h+ I
# H% v- p5 \! r交换次数：O(1)，有序不用交换

& y. x) I0 [3 K8 K" t1 JO(n^2)
$ o% ^$ l9 l' N1 d; ]( k2 v+ S: N
" v& a1 O1 \; ^) Z0 F最坏：
; g$ o, v- Y# T. q* A( j5 |3 y4 O
6 @: m% g- K( x比较次数：O(n^2)

' B( p/ G  g# `! Z( q- |交换次数：O(n)
8 B: |  V$ u( R' k) R
9 ?4 l. X$ n, o2 C8 S$ o( M% P. c/ ~% EO(n^2)

空间复杂度
O(1)
$ O4 w- m' ~* l3 y" Q' J
2 c  V/ z; G- O& c2 m- N堆排序
思想
利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆



0 e( _* n* `& D* q* z6 t( U0 \8 C操作
) N" h  M3 X1 _  N- U建大堆
1 m1 Y9 l" l" J5 f! H0 g单趟排序：
% l4 n. t* H2 _8 m/ S) h# {5 M选堆顶和堆尾的元素交换，则堆尾的元素排好
! D9 [; i1 b5 x% s2 c6 i+ X每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
  r3 Q: q* z" z2 D6 W' x3 S整体趟数：
& y  S0 j+ S' [" }2 `5 V! K若元素个数为n，则排n趟
void Swap(int* e1, int* e2)
{
5 h  E8 [2 M/ w. ]        assert(e1 && e2);
/ e; s9 t! `" `2 m; V2 \
        int tmp = *e1;
: S$ `; y: @: ?; m        *e1 = *e2;
        *e2 = tmp;
( `% t) [9 v( _}

void AdjustDown(int* arr, int sz, int parent)
{
        //建大堆，排升序
& y" }( x0 x( E9 J! w1 {4 S        assert(arr);
       
    //默认大孩子是左孩子
        int theChild = parent * 2 + 1;
        while (theChild < sz)
) Y% X/ U0 e& G! \6 B8 H        {
( j  v8 ~8 ]% ^        //如果大孩子是右孩子则修正
                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
                {
! t, z4 U! r- f/ d- q" P                        theChild++;
                }
5 l+ G- f( }7 f: K; h7 D                if (arr[theChild] > arr[parent])
                {
8 t3 R  R; z8 v  ^! g2 K) n                        Swap(&arr[parent], &arr[theChild]);
5 B1 B! k. a* p3 F            //迭代往下走
                        parent = theChild;
0 |/ z* v( q, D' C: |3 C1 p: _                        theChild = parent * 2 + 1;
$ \' c1 X( M- P: u' |) N                }
                else
                {
                        break;
0 v5 m$ Y! t; ^                }
        }
}
" y4 h0 [8 R8 L8 B8 R# L+ d7 H
void HeapSort(int* arr, int sz)
3 w  U3 \4 Z$ y, `0 @{
        //1.建大堆
        int i = 0;
) B. f$ L% p& x4 A  v        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
        {
: M/ z+ C% U( P                AdjustDown(arr, sz, i);
        }

        //2. 选数
1 f- T6 e: t( i- b* e- n4 ?        i = 1;
        while (i < sz)
        {
                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
2 R& W1 p- i9 \3 q% K# Z                i++;
        }
}
- j! `) J" r3 l4 z: l
1 ^1 Q/ w" F! f0 X* Y0 Y1
2
; Z/ |# G" d' ^2 ^/ X3
4
5
% M( [; j2 f' {3 h; d6
) ~0 J: A0 [* E" j' t/ \7
8
3 A8 M7 c8 B$ Y9
10
11
12
2 |* ?3 L) o2 {, n. z( f3 h  @13
) S7 L) j2 J2 S4 D' l14
15
! _1 W4 o+ s' Y0 }16
/ v' S, H: Z% U+ v% M  F17
18
. \9 m" Y% j; _/ K) k, {6 l19
20
2 o1 b. s' u$ {/ V! B0 G9 @21
$ @2 L6 t0 w0 P22
23
24
7 S- }* [( }9 `* w' e5 G9 O1 r) \25
2 y' c/ K6 a' z. y26
27
28
29
* H5 T) d9 M* R8 Q! x, c! a. S7 k& G) E30
- ?& q! W5 o+ e1 n! o. z! [31
32
3 p7 `% V% ?/ x( t3 _* g1 q33
34
( p+ l* W/ k5 L* {6 ~+ A5 v35
1 w0 ^3 D" r" w' I! y- v, C- G36
* K6 r0 q. \  V0 C* b, _37
) C$ P4 v) m2 k2 m( B; D( E0 T  \( K38
( z+ U) K6 S) Z+ f" I, A39
. H) J' r- f  K5 f40
: u1 T  r: L$ a7 \3 [+ E41
! d6 v3 ^6 v4 H- X8 d/ ]42
43
: c: B9 ?8 w; Z" q0 Y, g" v44
45
46
47
. }. i* v. z2 H7 y6 q4 @48
8 Z/ `& j; {9 v4 N49
50
/ E3 h3 E4 `, T1 l5 Q) Z  c51
52
53
& v7 D) R' o8 H: S% S54
" r5 H4 h1 w" K8 ]7 J  R( n' C1 R& Y55
% R! R  a. I- X
* t6 R3 J. d. w6 g" F
稳定性
建堆和向下调整都会打乱元素顺序，所以
2 F& H& \4 ?9 Y+ H- {8 a! A1 k! d
& s4 Y! o0 x/ J, P9 @0 d+ M堆排序是不稳定的

9 g( ^; A; s" l: I9 H& D复杂度
时间复杂度
单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为

2 r) p- u7 t0 B. h; h' C2 y. QO(n*logn)

空间复杂度
原地建堆
; ^( Z8 G& x% Z! \& k
9 E2 z4 q# s. x0 t4 z$ EO(1)

交换排序
, U& s0 \( w, e( @/ ?8 v冒泡排序
思想
冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素
' f2 Y' ?5 i8 Y7 n3 p, v3 @( o

* b8 Z, o$ R& r* X, r
4 D1 Z& d  u- J$ `* w8 p操作
& A8 N# I% F) S单趟排序：
每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
# b4 [+ q4 \7 R$ v# X/ _每趟排好一个元素，所以需要排序的元素每次减少一个
, l0 b# H6 t0 n8 z整体趟数
9 r7 v/ t( r7 L. U5 k& f' x$ r7 ^若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
void BubbleSort(int* arr, int sz)
% \5 G0 d- F6 ?% S, i{
+ h- u3 [6 ^3 D9 l$ O; f        int i = 0;
        int j = 0;
        for (j = 0; j < sz - 1; j++)
        {
' F0 \- u  M' _- [% i' _( d$ b                for (i = 0; i < sz - j - 1; i++)
                {
                        if (arr > arr[i + 1])
                        {
. h. T& n  S6 O& E, o5 B                                Swap(&arr, &arr[i + 1]);
" K# x; a3 b" U  m9 s+ I/ x                                flag = 0;
                        }
                }
        }
}
8 b" z/ ?( C, i5 D& z6 h
1
2
# f8 ^- ^! u7 q! I- t3
4
5
6
7
8
9
10
, E! u+ X5 L0 u3 Q  c8 }11
12
" b3 G7 U2 Q' o$ e13
! S. w0 W" ^$ E2 H6 V  B14
* q, k, T5 z* Q0 A) Z4 x- D& N, U15
2 U* o0 w8 [! ~- M16
优化
当遍历一遍发现序列有序，直接跳出
. G4 l% F+ J1 g3 o* e# Z, p
void BubbleSort(int* arr, int sz)
{
        int i = 0;
        int j = 0;
        for (j = 0; j < sz - 1; j++)
        {
                int flag = 1;
4 F# k+ S4 R! R5 V                for (i = 0; i < sz - j - 1; i++)
) O+ p4 @+ x/ T8 E' n! e( U                {
                        if (arr > arr[i + 1])
                        {
                                Swap(&arr, &arr[i + 1]);
                                flag = 0;//不是有序就置0
                        }
                }
1 G) S0 ]4 S  R1 ^                if (flag)//如果一趟下来还是1代表有序
                        break;
        }
) ?0 c0 v0 A+ A- @' q: f, k}
  A9 E$ Y' o! y2 G: n! s
1
2 L, ^$ {. N4 C1 @2
- N- {( |1 I: g' P, y2 X1 S3
$ Z" l& M5 z1 i* D2 |4
3 Y9 [' ]4 _* Y) s5
% d' Y1 G1 R8 [+ I' w, c6
# F) ^7 H# X% I, P; P6 {, }7
; a) H( \4 g* _0 K+ E* q- |" _6 y8
9
5 ~  e. c* I9 C' a. v10
% M) S, i) d3 t/ |, Z; Q11
12
13
14
8 @# T( d9 f, e) p8 }9 I- x! F15
' q9 M- c8 m2 l# L6 W& r( R16
, }4 i2 y1 V+ u* Z, F! A17
8 [- q4 p. H) O18
/ B) z. ]" U. s& U' P19
( d7 l! n; v/ J4 S" }- a% ?/ }' J3 M
- r5 P/ {" d; j  r4 T4 w( A0 i
0 T- q5 }$ O' m. }6 T稳定性
相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以
! z2 O) n1 u+ h( ~' Y4 i& \3 f
冒泡排序是稳定的
" f0 L0 h7 Z5 ?) ^8 }. D7 u, @
" Y# E. N+ M# @- {6 _复杂度
时间复杂度
最好： 当序列有序

未优化：
8 S" i# z+ b* w3 R+ t
5 C4 r  t; G- M$ y; ]$ G4 n5 VO(n)
, u/ w$ @6 b+ c4 h- F* K
优化：
' _& K% n& T: \; v
O(1)

7 ~3 S; F, L' G最坏：要进行 n-1 趟排序，每趟交换 n-i 次

. f) P. v' V0 v* \O(n^2)

3 ^# r" I1 k+ B空间复杂度
# H: I" u8 P+ g3 C1 xO(1)

快速排序
: f* }$ u+ v! ^思想
! d5 H- S! f0 a& e分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。

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

操作
有三种单趟排序的方法：
9 V3 t0 x0 n8 n
Hoare法
设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间
" g$ M& t6 s! K
左下标 L = begin，右下标 R = end

设 L R 相遇位置为 meeti
; l0 N; j) K. l& Z2 L8 }
6 L0 D: V6 m+ m! Y8 w( d​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”
. }$ A3 {1 ?. @
  \! |* _$ t$ Q/ L( p8 T2 g​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“

, m7 g& `/ t' S4 G5 i选 键值的下标 keyi
6 t% ^0 O; k5 y% n  P/ Q+ N
左1位置作 keyi，则 R 先走
右1位置作 keyi，则 L 先走
R找小，
4 t7 f4 W8 Q( m, c  f* J
找到则停
遇到L，则交换 arr[keyi] 和 arr[meeti]
# Z( Q+ y- {7 Z9 S& W5 \. L6 LL找大

2 f& O6 l, V4 }/ x. s% W* J9 X% E找到则交换 arr[L] 和 arr[R]
遇到R，则交换 arr[keyi] 和 arr[meeti]

# Z% K& {' ~# ~
解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
答案是肯定的：

- r7 d# @6 b7 d
/ A8 s1 }8 [  w5 A1 I. R
* _( m! I4 K& {& a
, x# ]% I9 L7 z//[left, right]
int PartSort(int* arr, int left, int right)
! j. Q8 O, f' M. B{
: E$ z  l, D6 }5 z+ U  K        int keyi = left;
3 N* z  {! f% r" l! n- X' m        //相遇则排好一趟
        while (left < right)
        {
                //R找小
. G2 r7 c. K- H" t0 r        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
                while (left < right && arr[right] >= arr[keyi])
                {
3 Z$ u! H9 w6 @# z                        right--;
9 _" L) N, ^& P5 r: z* H. o8 p$ t                }

! D" F. p0 L1 z- M# h( t                //L找大
                while (left < right && arr[left] <= arr[keyi])
% E6 g1 D: O$ h; ]9 x                {
+ Z1 a  B3 _  o( Y( g$ j) I                        left++;
                }
9 y# s% I6 ^; x8 w4 M               
* g4 q, K8 m  g' T* I        //相遇就不交换了
                if (left < right)
4 r7 ~6 V" `4 L6 O# R                        Swap(&arr[left], &arr[right]);
        }

! O2 G9 ?2 c( ^& f6 x        int meeti = left;

6 d4 q1 g  i1 {# W  C) H        Swap(&arr[keyi], &arr[meeti]);

* X, E# }1 ?( u$ v        return meeti;
}
9 J; P0 M. w$ I6 C
: _# g+ j" x, ?+ [" f& J1 c1
2
3
4
5
6
9 v4 L/ W- C1 i* r% h) a7
% Q8 G! \9 M! @9 R8
+ V6 A! _5 _, @, B1 T" e9
, x. j3 @: \8 _9 t. v( Y10
& A0 W' ~* z7 g5 M11
# N, n& E2 h, I2 V  X12
13
14
15
9 I$ a: f# {2 ?5 u16
17
0 q0 ]0 y/ Q: }# z18
1 c" n5 b9 X& m9 ?/ r1 i19
) `4 K  G/ C! t* Z* w6 U& X5 @6 o20
21
; o  B5 _1 U/ s7 Q' A- r22
9 I  E6 W' N: T* `% D: X) C; W. I23
$ G6 p( O- ^" f& e  \0 ?) z24
25
26
* @: q. C' K. J27
28
29
30
( [' I: |+ M: q5 W7 T- [5 b31
32


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

) z$ t7 S7 Q4 {" z; e4 ]2 \: k
$ J1 r0 `( g3 B0 g$ U+ V可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深

  V! Z* H. H: A$ `
  T" p) r3 q6 e2 s( D

非常容易栈溢出，怎么解决？针对有序情况，优化选key
" b' u" X. ?4 P( M5 D' u1 q! f
优化选key
随机选 key （是一种办法，但是不那么彻底）
6 Z0 e* L8 H' D选中间位置作 key
解惑：那先前实现的单趟排序不就失效了吗！
  H1 @, a$ m7 m* j) [1 |6 L) H# \：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑
; y, M9 y5 `+ q: v/ G" @, V
* F" u  Q+ o* o- d' W9 z. |* |解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
9 d: J5 j+ c' R6 w) r4 r前辈给出三数取中的方法

- a3 H5 J; ]! ~# ?8 p9 s三数取中
在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
优化选key后的Hoare单趟排序：
7 [7 T+ p2 r- D' T8 ?
int GetMidIndex(int* arr, int left, int right)
{
8 u* D, D8 t, R- ]: X' _        int mid = left + (right - left) / 2;
+ G. r' }, z9 ~; k2 @5 ~+ p//  int mid = rand()%(right - left) + left;//增加了一定随机性
        if (arr[left] < arr[mid])
        {
& X3 \: ]0 g- U: `! ]- y                if (arr[right] < arr[left])
                        mid = left;
* h; Y* |$ P* t' \4 ^                else if (arr[right] > arr[mid])
0 G0 V! f9 r$ M& q0 v/ I                        mid = mid;
* Y! |8 O" X8 L% G) }8 c                else
/ w2 h  i3 E: @                        mid = right;
" x) P& r( B, ]* d+ Q        }
! A6 t1 P! O& M4 L        else//arr[left] > arr[mid]
        {
" @# g5 z6 h% o* }0 s                if (arr[right] > arr[left])
; k' i3 d* ^. H1 i7 \; H" @                        mid = left;
% [2 o( X6 e1 {7 z6 O                else if (arr[mid] > arr[right])
                        mid = mid;
                else
4 t& Y/ B" y' B9 ?( H: |9 U                        mid = right;
+ D- a1 L  l9 L9 _        }
        return mid;
, W3 C9 U  O5 G! O}
& a, C* U) C; `/ M( G8 o1 ~7 R
; M* x7 ~- v! w0 Pint PartSort_Hoare(int* arr, int left, int right)
" n! Q5 W! a! B+ d% P$ b: K{
        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
        int mid = GetMidIndex(arr, left, right);
7 d% T. H  y$ T" s0 I2 D
        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
        Swap(&arr[mid], &arr[left]);

( C% g1 S+ \+ O( U6 R        int keyi = left;
        while (left < right)
        {
                //R找小
                while (left < right && arr[right] >= arr[keyi])
7 B8 Y" `% X+ N# q6 T3 L                        right--;
9 r% ]) F* M7 q7 h9 E
2 S4 n+ y) o& V$ V6 c                //L找大
* y5 z. ?$ U+ h$ o, N9 ]                while (left < right&& arr[left] <= arr[keyi])
3 `% n% L1 `3 O$ O$ f                        left++;

6 {: ~% q. B, L: h2 e2 ~                if (left < right)
                        Swap(&arr[left], &arr[right]);
        }
/ L% Y8 g" m$ [
( N0 h3 e; A1 e. a/ o        int meeti = left;

        Swap(&arr[keyi], &arr[meeti]);
3 `% i9 M+ Q+ G+ l  e
% e( C9 X# \9 \  r) }% @        return meeti;
}

) l3 {' t, \: E  H! l4 S1
2
3
: f, a( \6 A0 ^8 c- Z# z4
5
* i: {3 Q7 J/ C( h6
; q5 r- \6 x. d7 x7
8
* j9 _0 P' }" Q. g* a4 Q* c9
3 ]; {# n: y& P. b& ~% c% _10
& ~, V8 f6 o! }0 H3 P3 r0 [  v11
# E2 F# Y' v6 f12
; o! j( y! n: D) G! p; f% M5 y13
14
! u: E7 E1 t* p; t  [15
( r- y0 w; J/ i+ ]3 B: e16
1 s9 L8 Q' ^# i+ k# }8 W- \# H17
18
19
20
2 C1 S- p! {' h7 c* Z( }21
, c$ T/ j1 j" w1 h8 r5 Z7 Q22
23
24
25
, T, q+ c5 ]& c2 J/ X26
27
28
29
30
) F9 H* {; i0 x0 [31
32
+ r4 q; H; Q2 X! o33
34
35
; @/ a8 B5 P2 R2 R36
6 }+ F& g( F# K! y# a) O37
1 [9 }) R1 C. c  b8 ~. e. R- Y% n38
5 C4 V0 Y; _& w2 p39
  o+ b  K* I- K5 s8 j40
" o9 G) a5 D+ E41
) a* Z& D; g3 ^6 t8 y# [42
' @. f* h/ B! ?% ?: V- u43
4 Y7 R% `9 U% n# D8 [44
45
46
# Y. J0 n! ]+ p: r+ Y$ A47
48
- V9 N( j9 k: s: N2 D49
5 O4 h6 \7 W% C/ d# C50
51
' j0 Z/ [' l. W; i# ]) C52
( D! o3 @/ F. @. C/ L: H53
54
) s7 `! O8 s$ z% r% I  u- ?; }- e8 S挖坑法
$ n/ W' H. b. U/ P9 O" V+ ]( h! W* i初始状态：L作坑，其下标存为key
/ [! B# F6 X0 Q1 A2 q! Z0 |, @(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
; @. G) u( }& T( c3 ^重复 (1) (2)
) w, O; V6 J4 C: I2 n) a; {+ ]1 z& E最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]
+ C' E) [% V7 z# c+ k
1 t  X  z4 y  a3 _2 N
- `9 l% y8 u. U( Kint PartSort_Hole(int* arr, int left, int right)
{
        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
, W9 o- ^" g( U" E9 f# @- ~
        int key = arr[left];
        //L作坑
        int hole = left;
        while (left < right)
        {
                //R找小，扔进坑，R作坑
                while (left < right && arr[right] >= key)
# s# n+ ]% ^( Q                        right--;
                arr[hole] = arr[right];
/ ?' A; r" z4 m& S7 D) p                hole = right;

) n6 v$ G/ r) j- p' [  y$ ]                //L找大，扔进坑，L作坑
                while (left < right && arr[left] <= key)
% g9 N( E! `0 s7 ~                        left++;
9 \; p/ f. n0 X$ x                arr[hole] = arr[left];
                hole = left;
3 F+ h; e  J2 D        }
+ j" d1 q2 f8 @- c8 e, w        //meet
        int meeti = hole;
7 h& u: f6 U5 F) e8 K% t2 I        arr[meeti] = key;

! \: t: v. z; j1 `+ r& ~        return meeti;
}

1
2
3
4
5
6
7
! D! ]4 ~8 {# C5 d, o8
9
10
11
12
7 i. w4 W- w% f' p% z1 ^3 `13
9 d7 @% C* g/ r4 X14
1 n( W  M, c+ {3 K$ j2 `5 r* ?' _15
0 x1 w  V, t7 a# u: b7 r! X16
17
18
. Y2 Y8 D; h' l# u6 S3 s# z19
20
21
22
23
% F3 m! |7 _3 ]1 t$ }  ]24
% w2 {/ z* r8 z* `* G8 ^  n( G25
26
27
28
前后指针法
. g% S; F8 D' m" h3 e: Z/ |9 d此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多
" i$ Z; ]: ]* Z: ~2 H8 `. ^
, a7 ~8 o: F. o& ^- Z  ~8 h) Pcur找小，找到则停
++prev
如果 prev != cur，交换 arr[prev] 和 arr[cur]
. P- Y' }; P: M0 y0 r. i+ i如果 prev == cur，不交换
当cur越界，代表找完，排好序了
, U/ F, e6 z/ L2 j( u9 mprev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低

" d1 P. M4 K. Z6 t+ |! P* g

# a' X7 J* o7 mint PartSort3(int* arr, int left, int right)
3 `3 X5 O5 Q! D0 r- ~{
        int mid = GetMidIndex(arr, left, right);
& Y( `+ _" d3 F5 @; n" X        Swap(&arr[mid], &arr[left]);
       
  //int key = arr[left];
, V3 F' y. J- \# Y4 O        int keyi = left;

" \6 H7 I8 f+ a. H- J1 t& y. c; t        int prev = left;
        int cur = prev + 1;
       
; q% |# y1 z. S! g6 `    //cur越界：找完小的，prev的左边全小，prev右边全大
        while (cur <= right)
        {
* a7 w+ s1 G& H- i  ]! D7 T        //++prev == cur 没必要交换
( H8 k# x3 \1 B' Q' A( c( g0 D                if (arr[cur] < arr[keyi] && ++prev != cur)               
2 r- B$ Y: J4 t" E, E# n0 y                        Swap(&arr[prev], &arr[cur]);

/ `9 ^$ W) ^# Q& x( Y+ u                cur++;
        }

        //键值存是的值：
4 F) V. t, _, B* @- s; u        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
        //Swap(&arr[prev], &arr[left]);//这才对
% R3 X. X& ~0 q0 I5 d! d2 w    //键值存的是下标：
7 r; w5 O* z* l) m0 g! @        Swap(&arr[prev], &arr[keyi]);

3 F/ }, ^) R9 }& s) R" a) \        return prev;
6 K$ P# I3 h8 M9 l, y* Q8 K}
: `0 H6 z9 d. b' y( n& j- Y: X
; R3 S) ~) t( r3 p1
2
3
4
( \3 G6 A, g2 \: u4 ^1 {+ b5
6
. D1 |9 I% f6 I" k7
8
9
10
11
12
13
14
15
( U* ?) q& O7 ~5 I9 x3 g0 y16
17
18
0 [) w4 ]7 y6 m1 m/ l19
1 p6 I# x! s8 f$ e% c20
21
22
23
& f+ T# v- u1 K% H3 ^( z24
25
26
: {! W) G! A4 Q& v. y% X. b27
28
6 _3 |  T! J) R+ ~29
! Q- N* x" U' U整体排序
递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

//[begin, end]
void QuickSort(int* arr, int begin, int end)
/ b4 q3 A, u) w& i, P) N2 u{
" [& Y) m  t" p; O6 v. ^+ [7 M        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
        // [begin, meeti-1] - meeti - [meeti+1, end]
  ?% L- }' y4 H3 V% ?                //1.begin > end:超出范围
' n0 |) o. C6 ?: g2 B" }, y+ s                //2.begin == end:一个数天然有序
    if(begin >= end)
: A- \8 k  A9 t8 _. z4 O        return;
  ~0 E0 ~" a+ Z
9 M4 F9 [9 |/ F2 {+ U) k                //排好meeti
                int meeti = PartSort3(arr, begin, end);
8 V( _5 ^  }  o: g. u1 j+ @: `
                //排好左右子区间
                QuickSort(arr, begin, meeti - 1);
; F" l) b3 G5 {                QuickSort(arr, meeti + 1, end);
$ W" Q1 w) |4 _, o9 y' I        }
% B2 g7 N& u' t1 a}
) ?3 x2 I) t3 Z# ^+ `
, {$ a1 E* `  Z0 X! @1
; M: q7 t, M/ @/ a; n2
+ j9 M9 R, @: s8 A* _3
4
5
6
7
" C2 g+ I/ n* q8
* B8 B0 x& d/ X9
' k+ H- q0 R0 q4 u# L# e10
( Q9 P2 m2 [& w' W- y8 |8 ~11
7 c; u& [3 [: Z/ u* u12
4 N0 l: o- }6 |( I% z13
2 B+ f  f8 b9 |/ z3 G2 I# i14
1 z# w( n, J  M; R- Z15
2 c8 C$ U( g5 H4 _# i  M16
17
8 x6 }3 M! ]3 n0 s& F1 C5 K( |18
…

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

优化小区间

1 Y" t8 v& ?4 e/ N
3 d* U/ _! I! s: e1 E2 _如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序

那什么算是小区间？

其实小区间没有确切标准，8-15左右都可以的
  ?. V" m  h7 d  N1 ~# ^

/ t( h2 k/ y8 W! o7 u这里就把小区间定义为 含有 8个数或以内 的区间
( F) ~* N2 G! M% H5 O
7 C/ N! w, T9 `0 H& \//[begin, end]
void QuickSort(int* arr, int begin, int end)
* |) A! C* Q* J+ w% ?3 a{
& C; X- U$ V( ]& G- [% v3 D8 D        if (begin >= end)
                return;
; q/ p/ Y3 ?" f
        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
        {
9 J# e- t' s: ?/ D                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
( D; C( T' ]2 x9 i/ |0 m* N                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
/ K. M) B/ G; W* {) K        }
3 e6 W% Z% q  \' c7 p% @& @0 s. [8 B        else
        {
  e2 }' |! K  u- \                int meeti = PartSort3(arr, begin, end);
, P$ U% z/ B- a8 j5 z- E5 H
8 l- |1 c* [1 S. l( y                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
4 n5 G' F+ S5 ?+ O        }
}
* H. W( B1 U" Q+ ?8 w
1
/ t7 ^+ W. ?( A, f2
0 m; Q2 z2 c. a/ P3
4
( ~# r9 q& f  T) I" P$ O5
6
% u) U8 B; l" \% @: f7
8
9
10
. W! ?5 A7 ~* C3 X0 C: _6 L11
12
13
14
0 O2 @$ E6 ~9 {! D( x- R% e2 I15
8 a7 X! e$ Y, }" k1 ^- ]9 `6 S16
# i' [6 G& A+ n- F' b$ s! w17
18
' M" _# P# @, o" \. A" A# e! I6 Z19
, n# V1 F1 }9 [' s+ H快速排序非递归
  I) ^* f6 c/ Y为了解决彻底递归深度深的痛点，我们来试着把它改成非递归
5 I* f2 T( O- Q: _
4 f9 s! g; [  d, C' L- e! Y思路：
% `" x; O; U5 w! @6 @# p4 s2 T/ z递归深度深，栈的空间又小，会栈溢出…

0 _  Z: j( G3 h3 x# ?1 P8 e. ^那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！
3 }( p  l* h4 l! _% a- `5 g7 H' S
# a4 q6 J7 p9 x3 w1 a' D1 E核心思路：在堆上创建“栈帧”
' s: P9 W5 j$ D8 Q
快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的
) V1 {, L) a" E3 ^- |9 j: C% P: C
1 j' @/ N' G/ l) j% h2 ]
* Z4 A0 U& `7 y- F( T) i
' y, ]( K3 O( F: |( j在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：
  l: M& a5 S# q) u3 H
% |/ \3 e' J9 t7 i; ^* A先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
7 ^  q) d9 t' x5 G8 S$ O+ |6 a0 V先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
0 @; s  t1 x0 ^7 r: r{
        ST st;
        StackInit(&st);
, k, b1 S/ X$ A0 G# w7 S       
    //先入begin
        StackPush(&st, begin);
% Y8 U7 P/ v; ?; I, h    //后入end
        StackPush(&st, end);
2 ^- I7 r# h* ]1 B1 X5 A
  d; f* p6 l9 |3 v2 F% M# Q        while (!StackEmpty(&st))
6 S* F3 _9 k6 @4 n/ a        {
2 H0 e& }  M* D& R                //先取end
                int right = StackTop(&st);
, ?" t2 t% z) l8 l! |  Y                StackPop(&st);
( ^; r$ @! n7 ~" R3 s& E                //后取begin
/ A$ [+ t4 U6 T( _3 Q) B$ v. U                int left = StackTop(&st);
                StackPop(&st);
: j4 j! H0 `, P% K  F2 z
( K5 m. \+ S2 i$ `                if (left >= right)//1.只有一个值  2.区间非法
4 m1 `6 d! H6 E/ v+ c/ ^% _. t                        continue;  
                               
+ q( }- g' @3 p# s* M' `/ @                int keyi = PartSort_Pointer(arr, left, right);

* w3 Q9 g! R0 `" d* S  ]                //先入右区间
                StackPush(&st, keyi + 1);
                StackPush(&st, right);
                //后入左区间
                StackPush(&st, left);

9 Q: D3 }/ x4 |$ M9 e                StackPush(&st, keyi - 1);
6 V( B5 T4 x( I        }

, t# k1 }. P( D1 U' c+ v        StackDestroy(&st);
}
0 t) `: {+ E8 [- l3 z. ]
1
; M, h: x( D6 x9 k* g9 g2
# S# o1 B: F8 B3 J8 D( u) ?- X( ~3
7 P/ [: ^, T/ H2 a  u+ ?* D4
5
4 z' \; i' v3 c7 b# Z" k' i6
7
8
9
10
7 Z# f* V; Q, V- o4 _% P) Z# d0 S, [11
# F6 \+ U0 H! `4 {. W$ r: N8 W12
+ h  f7 H! v2 V' N4 [13
14
15
16
17
) Q6 b0 h2 a  O' i% f' I" n; o% E18
. i7 e4 m3 I" G* |% J0 `1 o8 k19
20
21
22
- @# @" p2 H) c7 B( T23
24
6 y: O! u' ?4 ^( Y- N3 O25
26
! y9 ]3 ]0 j9 L8 D27
28
29
30
% f) F6 K7 ~* J31
5 ]3 o  m; V2 c7 t# r; A32
33
34
35
数据结构栈的实现可以看博主之前发的博客
7 t6 Q/ u1 Z% c4 k* i7 s

6 }2 J' q& h0 T* o归并排序
3 e. e% ~* x& G) R5 _# z3 B
…

# A1 {+ ]$ f3 h性能测试
  x; |  P' D% Q9 Q/ A! fvoid TestOP()
{
        srand(time(0));
4 [& d8 |  s( L% |6 N( L, d: y        const int N = 100000;
& w) [0 Z2 u+ J2 P9 v0 D        int* a1 = (int*)malloc(sizeof(int) * N);
        assert(a1);
        int* a2 = (int*)malloc(sizeof(int) * N);
4 ]0 m, ~) z# ^! J  f$ _6 J        assert(a2);
        int* a3 = (int*)malloc(sizeof(int) * N);
  I( f$ Q; a& d" T  u0 X! U# q        assert(a3);
5 f; F! x" d1 V0 O1 e8 f- l        int* a4 = (int*)malloc(sizeof(int) * N);
( l. P+ J" U+ V7 R: @: x        assert(a4);
$ ]$ l* r% l4 Q3 q- r9 m        int* a5 = (int*)malloc(sizeof(int) * N);
+ h8 ?: I5 b7 Q% h/ ]        assert(a5);

        for (int i = 0; i < N; ++i)
        {
+ o* ?+ J( m! h. i6 {. t                a1 = rand();
                a2 = a1;
& Y2 `' |: J# h                a3 = a1;
                a4 = a1;
4 j; h. j) w+ [/ B3 I                a5 = a1;
4 _" D+ }/ i5 G  E$ j8 @        }
( m1 E+ e, }& P! b4 v5 [
        int begin1 = clock();
; |$ F0 e% G" w0 |' \5 K; G        InsertSort(a1, N);
        int end1 = clock();
9 x4 b0 _3 h/ _7 J8 w& x. J9 T
7 N. ^$ \7 q% n, n        int begin2 = clock();
* o1 P1 X. K6 U9 K7 I  }5 \* g        ShellSort(a2, N);
        int end2 = clock();

        int begin3 = clock();
( ?  Y4 z/ g1 K+ f' x3 ]- m: Z        SelectSort(a3, N);
) k+ S! U5 Y9 z  e; V. K: ?# Q        int end3 = clock();

        int begin4 = clock();
4 ^" e  I6 R6 O1 c        HeapSort(a4, N);
0 ?, c/ T, L1 \& v        int end4 = clock();
1 u$ G. F9 _4 D% l9 P, K
        int begin5 = clock();
        QuickSort(a5, 0, N - 1);
9 s7 w" ~8 x, q4 c! d2 g2 C                //1.中间key
                //QuickSort(a2, 0, N - 1);
                //2.三数取中
8 q. E7 R+ l' T' C                //QuickSort(a2, 0, N - 1);
                //3.小区间优化
* w; b6 s( a+ }8 L' x                //QuickSort(a2, 0, N - 1);
        int end5 = clock();
8 d8 n; n2 L& y
1 M. K# d2 t4 n7 J% \% m/ b
        printf("InsertSort:%d\n", end1 - begin1);
        printf("ShellSort:%d\n", end2 - begin2);
0 h5 U6 e# K% o3 H2 Z6 ^        printf("SelectSort:%d\n", end3 - begin3);
, Q! _' r) L, \) v        printf("HeapSort:%d\n", end4 - begin4);
% b- b' ?( s  e8 e/ g        printf("QuickSort:%d\n", end5 - begin5);

5 n* R. Z% Y5 F  v2 d% B5 C        free(a1);
* [9 K2 H- T7 i, S* L$ j        free(a2);
        free(a3);
        free(a4);
' D* B: x" s$ X6 i7 P        free(a5);
) p/ R0 O% M2 F/ H+ p% I2 f( n}
: ]! g+ Z: I; ?7 Z1 J5 m0 z
3 K0 z! C% M2 z# W1
2
1 N$ t0 I4 t- q9 x3
6 ~6 k- S- J( W; S$ P! C4
# q# g$ R/ ]& |% l3 \6 t  j5
6
4 N. Z! d7 v1 r$ [+ m( C7
8
9
10
) F7 V+ z7 [5 e$ E4 y, d11
' E) I* ^5 C6 i2 u- P/ R% b( K+ y12
13
14
15
16
17
18
19
20
" L, r3 E2 _& N0 S. `% C21
, d# W: ~7 L& _. A1 x  H22
9 @, c4 z) f( Z- y1 T4 s) M23
24
25
26
( ?7 v9 z, e+ q  i% b( d! U. _27
28
29
( R3 w$ K" y- E9 `5 A% u. @30
31
6 K% {  u% j5 `7 _' T6 Q32
+ K$ \! o8 U. L" e' i1 d33
34
( N$ J0 O" s( D, W1 }1 h7 F2 Q35
" V1 I6 r3 ^4 ^' a, u* \36
7 Y1 w+ |( ^8 O: b; e# U& {37
38
39
40
41
42
43
44
45
46
47
+ ~5 ]) r# u9 b- A- U48
* k; X7 b$ }+ A0 ^/ R49
' f  K; ?4 [+ u3 E3 N50
9 Q% ~/ T' x$ ^$ W. k  Y4 Z- e51
& m" ^# C5 |5 o, H52
53
0 a) `) m( A. Y: i, i! d54
55
5 _/ `0 h4 G& s6 {* r7 O' c56
57
3 p7 X3 C8 T- A+ P4 N( z2 O58
6 W; v/ {& l# Z# Z9 Z59
60
3 \7 g6 ?9 I4 C) {% a# m( p61
62
- S' D" |  a* \1 y8 i+ D63


' E1 x7 J/ i' m; b  U不愧我们费这么大劲优化快排，多帅哦！
* s7 A+ [; P* k% o
5 @) [5 z+ U" X# m0 k# F, @差一个归并排序，后续补上！
/ o5 U; y  x+ B2 H' B
不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
————————————————
: j* H- N. v6 G* u& V版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% p/ r  o. e4 l; `4 P原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832
2 F- N6 z2 q, i: m
  u  n. Y8 z& m6 X5 {$ v. X
& f2 w8 h) e! E+ y9 W; k* E