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

杨利霞

【数据结构初阶-排序】经典的排序算法，很有趣，有没有你不会的呢
# N$ s% ~2 z8 a: `$ S8 j. j
; f0 w1 H# N) B前言
本期分享经典排序：

  P) i8 l9 ]& [" y* s插入排序
. C, [: F9 `8 {8 ?直接插入排序
希尔排序
选择排序
直接选择排序
堆排序
交换排序
2 ?; L) G. Y3 }$ R1 |  }; J冒泡排序
; V( }1 J. p; f# c# W  l% @快速排序
注：讲解时默认排升序
/ Z! {" C- V$ l) U( x3 n
/ _/ B  r* S4 p0 e! k插入排序
4 f) Q. F4 [7 J; L直接插入排序
; v& [6 s) }# Y8 s思想
插入排序，就像玩扑克时，摸牌的过程：

8 \; i' |% P! R& E' n最开始，左手没牌，右手从牌堆中摸
6 m0 J$ u- H( f/ L右手每次摸进一张牌，都从右到左比较，找到位置插入新牌
# M2 E) p1 K9 g* C) h2 Q如此一来就能保证左手的排始终有序，摸完牌后也就排序完成
/ p- y( p8 E: x! d6 [; W2 z
& R4 ]( T) T- n) D, V. y2 A
( k" M" E6 S' Q* G9 z8 b- L* p操作
设begin为已排序序列 arr1 的左闭区间，end为 arr1 的右闭区间，则有 arr1 的左闭右闭区间 [begin, end]
5 q' y1 P& P/ X- l4 \6 X单趟排序：
每次保存起未排序序列 arr2 的元素 arr[end+1] 为 tmp，从右到左和 arr1 的元素比较
& ^3 \+ R0 P9 z8 W0 D8 \+ D! x是正确位置：插入
& B* o6 i- G8 q. y  V( J) D不是正确位置：arr[end] 往后挪，tmp接着从右到左和 arr1 的元素比较
整体趟数：
若元素个数为n，需要排n趟
void InsertSort(int* arr, int sz)
- R: h1 }2 ~; i7 F; A: S{
        //end + 1 < sz
        //end < sz - 1
5 w* e0 _2 a, ]+ L9 h6 R        int i = 0;
        for (i = 0; i < sz - 1; i++)
2 T7 f. }7 A7 s        {
/ [4 d* v4 A! l: A                int end = i;
  H) c* L' F# S, R# P                int tmp = arr[end + 1];

                //找插入位置
9 y, |0 u( |& k9 m4 c, b                while (end >= 0)
                {
6 O9 f/ J7 E) G7 g4 C                        //不是插入位置：当前数据往后挪
6 W0 v- @/ f) Z" Z& ~! ?                        if (tmp < arr[end])
3 n# {1 ^9 W% Y+ m, Q                        {
  H$ l' g# }: c$ h5 O  w8 K9 ^                                arr[end + 1] = arr[end];
+ ^+ ^6 m2 H9 p/ ]6 q                                end--;
/ l) q$ D  e6 m3 r" g                        }
) K  G1 o. c3 a+ |6 g0 g                        //是插入位置：跳出循环插入
; k" k8 T3 C4 ~8 E                        else
* n+ s' W/ K, e& \                        {
0 u2 k& K: t* V" z* \                                break;
3 o4 m5 \% l) X+ M8 V1 k7 v                        }
                }
; t- M5 ^: {$ A' U                //插入
                //1. 插入位置是[0]，end == -1，不合循环条件跳出
                //2. 找到插入位置，break跳出
                arr[end + 1] = tmp;
: v. ?& z: }8 J/ m+ q+ Y, B, s        }
}
' s4 _- c7 R4 ^$ ^  ]
& X$ Q3 T  q8 s# H$ |1 D1
2
3
4
, W& @7 ^6 k9 a  v; o7 n* f- U5
6
7
8
3 t! G& x& B$ X3 u4 \- A  J: ?9
10
11
- p7 {7 V) `' Z4 f  h7 S12
13
+ O- q7 @" H5 H  A, w/ |14
15
& d# S- [; b- w/ D( l+ _16
17
: t- {' L' N2 ^- ~8 r18
19
20
$ L2 c1 P5 I! v+ A7 L/ m; q+ p( e& |21
22
6 k: W' \) _( b9 H& x  [23
. x5 p% j2 Y# X! G. p, o$ e4 m$ E24
25
26
% [5 C, |: d4 I9 t2 s27
0 P# Q3 A& R& S- [5 [' f28
29
30
31


稳定性
; C' _5 k& h4 j) O; i, U. ^2 v6 w$ J插入排序中元素都是单一向右挪动，相等的元素不会改变相对顺序，所以
: U5 w! e# O6 t2 T
直接插入排序是稳定的

; h9 l8 W' L. J$ r2 ?$ [# n4 t复杂度
- J! V. \" E6 M! @  O0 B0 K时间复杂度
最好：当前元素只需要和前一个比较一下，这时需要比n-1次（最后一个天然有序）
1 F3 q; o; w, Q4 D: L/ g
2 {8 ^% z1 c9 g3 E: CO(n)

最坏：逆序，比较次数：1+2+3+……+n-1 次，为等差数列，数量级为n^2

O(n^2)

6 P$ @. Z9 j9 R0 G( N" e9 C, S空间复杂度
: ]8 l3 U( x  c' ]$ l/ ^O(1)

3 Y. f; d$ d: N希尔排序（缩小增量排序）
& j* k5 Z* t4 e9 K1 G) ?希尔排序是直接插入排序的优化版本：按不同步长对元素进行分组，再进行插入排序

优化思想
- H% D% G  ^# M5 s增量gap不止用来分组，也意味着数据移动的步长，所以

; ?/ L/ P5 X8 N. @( S# B% H2 ^gap很大时，序列很无序，插入排序的元素少，移动快
0 ^  R8 n- ?* x- m# Y, `  ~gap不断变小，序列有序多了，插入排序的元素多，但插入排序对相对有序的序列效率高
; g" u- @" m; U. @# ]" t0 G& {

操作
单趟排序：

8 r" U! ^& y$ j) r* V6 L' @, I/ w设定一个不断减小的增量gap，也是元素移动的步长
" F' G/ s1 R; I以gap对序列分组，并对每组分好的序列进行直接插入排序
5 M+ }: G# J3 R. e# y3 v不断缩小gap，并排序
) _3 B( u. H+ R' t6 K. i9 |/ {*gap>1 时，进行的是预处理排序，gap == 1时进行的是直接插入排序
& u/ ~; Z, n" b" S0 ?$ i整体趟数：

由gap决定：当gap = 1，排序完成
2 p3 b8 n9 v, O# u. G" S' ~4 g注：增量亦称改变量，指的是在一段时间内，自变量取不同的值所对应的函数值之差。这里指自变量取不同的值，不同分组间排序的差别。
: A5 h9 n( W# Z2 j5 l) D( @
' e; {. c! [' A1 a; V( Ovoid ShellSort(int* arr, int sz)
{
        int gap = sz;
       
5 h0 H2 r: A% I3 Z$ l0 O3 L    //gap > 1，预处理排序
2 q+ H; M5 p9 ^& {1 y    //gap == 1，直接插入排序
        while (gap > 1)
        {
                gap = gap / 3 + 1;//保证最后一次gap==1，进行直接插入排序
0 u* O( E* G1 \/ w1 H6 z                //gap组
% z2 U9 y: |+ g) \  ]                for (int j = 0; j < gap; j++)
                {
            //end + gap < sz
                        //end < sz - gap
                        for (int i = j; i < sz - gap; i += gap)//每次跳gap步
* L0 b5 {/ ~# @% Z                        {
8 N+ T/ ]: `% y6 P' L                                int end = i;
                                int tmp = arr[end + gap];
6 Z5 S  h5 l1 q, j                                while (end >= 0)
                                {
8 O0 v" @8 Z1 O" U                                        if (tmp < arr[end])
                                        {
                                                arr[end + gap] = arr[end];
  k6 J0 X7 L- H  k                                                end -= gap;
; {' r  k$ D' \                                        }
% D  s9 f- _5 v. \4 G4 K                                        else
- i$ d8 H: J1 u: A% n& e* i# u' ?0 u! _. f                                        {
( K) D2 j1 v( o( Y9 d                                                break;
                                        }
7 b# j. c5 {6 e: l) P                                }
0 u& S; f7 l% z2 |. L( [                                arr[end + gap] = tmp;
; W6 q/ [6 G: d( K4 P4 {5 @; G                        }
                }
        }
2 u! L% v3 |$ N}
9 w: u4 c$ I# T4 h3 C' R% ~
1
2
3
4
1 v" n$ o/ P0 g5 v7 O! G7 T5
3 V. u) O+ f+ T4 Y8 V6
7
3 q1 k6 U- ~4 j0 K. x8
9
10
11
12
9 m+ F; C8 d+ j; o13
8 m5 m2 [4 q0 d7 v6 }2 I14
15
16
17
18
19
! d: q1 x* u' x. f8 y6 f20
21
22
23
  F# r2 i) X7 _1 i7 L4 |' H24
25
% l( V( @3 |/ `5 l/ m& y26
& n2 G, c7 F* B2 B& i2 T27
28
: H; W; L/ q7 f& t; q, p9 G29
30
31
. Z0 `/ D8 H3 z  V32
33
% f1 x- T) i: B7 H1 R- ]+ F" B34
35
: V% a) [7 N, F- K: y( D# Y, ]. }其实就是套上”缩小增量“的直接插入排序
8 h3 k9 {* }2 @! A+ i6 @% c: Q, [$ M
$ n0 b& Y7 l0 ^
- K5 D; l' T7 p6 X5 ?6 v, s' v稳定性
我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以

希尔排序是不稳定的

复杂度
时间复杂度
希尔排序的时间复杂度随增量的变化而变化，难以计算，根据某位前辈大量实验数据能大概估算：
5 k  O# ~- y! q
3 t- ~' x: j( H. R! s9 {' ~O(n^1.3)
+ r' M( E- Z; @0 Q
8 M, t# c8 x, W, [/ Y. m9 ?空间复杂度
, P/ y, C3 `" c) h# AO(1)

选择排序
直接选择排序
思想
) Z, G6 p" M: H, p选择排序，遍历序列，选出最小的元素，交换到左边

5 E2 q$ m6 y5 `1 p

/ u" H4 B0 A# {: r3 i7 }优化版本：

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

- O% f$ j3 ^+ }9 ]# y( e$ ^操作
' Q0 E5 k2 |2 J* t设 begin 为待排序序列 arr 的左闭区间，end为 arr 的右闭区间，则有 arr 的左闭右闭区间 [begin, end]

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

6 X  w! X; y) ]- Y7 X9 L+ p单趟排序：

$ \$ K# |8 i) W- a3 Y* m: a- @遍历选最值的下标
- O  G! B, H; X交换 arr[begin] 和 arr[mini] 、arr[end] 和 arr[maxi]
（修正）
整体趟数

0 S" u; b9 ]+ a4 g若元素个数为n，趟数为 (2/n)
- L3 v  E- z7 S  N9 e# N修正：交换最值到其位置时有先后顺序，如果先交换的元素交换后，影响了后交换的元素的交换，则需要修正后交换的元素下标

8 [! H. X' D/ R  T% o5 `void SelectSort(int* arr, int sz)
{
& q2 @+ O. ^6 P, V' Q/ ?( d' j, V        //闭区间: [begin, end]
        int begin = 0;
        int end = sz - 1;
6 r; i2 Z3 A  Z$ _+ m9 O  z6 p        while (begin < end)//begin == end 最后一个数，天然有序
% F- _# p9 l& e& e2 [2 @        {
                int mini = begin, maxi = begin;
                int i = 0;
0 E- ?* H" `2 ^7 Z: U' t4 f                for (i = begin + 1; i <= end; i++)//俩下标初始化的就是begin，不用选第一个
                {
6 K: O8 u, w7 d( k                        if (arr > arr[maxi])
                                maxi = i;
                        if (arr < arr[mini])
- s( a1 U1 C1 r# C                                mini = i;
9 s6 {3 j. {4 N5 T& t& q" \                }

                Swap(&arr[mini], &arr[begin]);

, Z) D) f9 I9 v) B# {" d                //修正（预防）：如果maxi == begin，mini的数据到begin，真正的maxi的数据其实到mini的位置上
6 J! @2 w2 Q% I8 Q* V( H1 b4 U4 ^                if (maxi == begin)
                        maxi = mini;
                Swap(&arr[maxi], &arr[end]);
4 A$ x( r2 a) _2 ^# Y( R
                begin++;
                end--;
4 l" O, \7 Z+ Z, B3 \$ ~* `) ?, i        }
5 N/ P- V% L  t$ B" b}
$ V) W3 c) i6 f7 ]# ~7 J: x
/ S6 O/ u8 U) R' g, |. P1
4 E8 T$ z+ g( o* O. y  P% S0 o( o2
3
# l  c# ^& V; \4
5
) ^# N1 }; o0 k* C' z6
7
6 I& t  k$ Z7 M8 S5 K; N. ?, n8
9
2 z- `7 d8 Q: B5 ]" T10
11
12
$ W4 k# f3 o/ {8 M) L% c2 T: s! f13
- |, x. L2 N7 G1 O+ N+ X' E; F14
4 Y0 g1 H* U4 N2 d' V15
" C$ x( X4 N! ~' Z* [2 k. B16
) {4 X: g1 z. c& Z17
5 s/ B$ v( T1 r+ z. |$ N+ f2 A+ ]18
19
20
21
! T& S1 H5 }  w7 U22
! J% D+ z2 _6 k. p' w. _. r( B5 B23
, ]! b* G8 S  i* m3 \24
25
26
27
28
% a9 h6 ~! }1 n; O1 Z/ V

稳定性
选择排序，选到最值后交换，会破坏相同元素的相对顺序，所以
. Q+ \0 ]% a* x9 x3 C
选择排序是不稳定的

2 a! J( h# m) ~2 {" _( h复杂度
3 K5 K* F5 Z  K- X时间复杂度
最好：

比较次数：O(n^2)，只选最小的比较次数为 (n-1) + (n-2) + … + 2 + 1，每次选最大和最小则快一倍，但数量级还是n^2

3 f3 S/ M- y( X' g& P% l交换次数：O(1)，有序不用交换
( X: ?! n( e6 ?. r0 N
3 ^& F8 {7 D( b  Q% oO(n^2)
* X3 w: O' L4 Z$ h& E& _
- K! I/ }) Y; M! D" q最坏：

比较次数：O(n^2)
( \: J- o. L+ \! R. J
/ f8 ~0 w% O* Z! c; R) h交换次数：O(n)

5 Y  Q) C. `1 C* o4 o0 L* gO(n^2)

6 ]2 X: Z6 y% Q( ]; L2 |  @$ P空间复杂度
O(1)
( F) ~0 Z& R# [, I
堆排序
思想
3 Y' U4 R: t: A: y利用堆的性质，每次交换堆顶和最后一个元素，则排好最后一个元素，再把其视作堆外元素，最后对前面的元素重新建堆

  f  {# |" z. Y$ g$ `3 ^+ h6 g8 t
3 v' _& _3 q, ?1 G# U# a. i( q
7 `8 e' A! {9 f" j操作
建大堆
单趟排序：
选堆顶和堆尾的元素交换，则堆尾的元素排好
3 l7 j1 K3 \1 ]' F2 z; W每次把排好的“堆尾”元素视作堆外元素，并对堆顶重新向下调整建大堆
9 W! t1 b& Q* r& ]1 J! z- H; T整体趟数：
若元素个数为n，则排n趟
void Swap(int* e1, int* e2)
{
4 f  |( T6 v+ U2 A2 p        assert(e1 && e2);

        int tmp = *e1;
3 g1 ^; s1 Z, S; o3 t, J9 G3 f        *e1 = *e2;
: T( S: N" e8 Y, ^8 z- z6 O4 a8 R        *e2 = tmp;
}
& C/ `2 ?, h$ h# H7 t1 j
void AdjustDown(int* arr, int sz, int parent)
9 v& I6 W; Z4 y* e{
        //建大堆，排升序
        assert(arr);
3 f' F" f, m! C. m  I       
4 F( X# Z5 e9 D    //默认大孩子是左孩子
5 Q0 u- T; o7 u        int theChild = parent * 2 + 1;
7 ^& G$ M# |, H5 c& Y        while (theChild < sz)
4 P& v/ V2 C! c) Y/ F        {
0 M; A8 m2 V$ i        //如果大孩子是右孩子则修正
' x6 T  K* g$ d+ t/ c                if (theChild + 1 < sz && arr[theChild + 1] > arr[theChild])//注意右孩子下标合法性
4 _+ T3 c% m9 y" q                {
) a  ~! y6 d% Y6 g                        theChild++;
                }
                if (arr[theChild] > arr[parent])
                {
                        Swap(&arr[parent], &arr[theChild]);
1 ~8 l6 O$ Z3 j/ ~% {            //迭代往下走
8 s- N" {1 h4 Y7 i% X                        parent = theChild;
                        theChild = parent * 2 + 1;
# `7 I2 q- k# b; A! C' f% p                }
                else
                {
                        break;
                }
        }
}

void HeapSort(int* arr, int sz)
# g: w. ^5 n/ z5 s  r{
        //1.建大堆
# D1 Q2 i( h0 C( {& \/ Y        int i = 0;
  C* a) j; [) Z# {1 ]$ \        for (i = (sz - 2) / 2; i >= 0; i--)//从最后一个结点的父节点开始（最后一层不用调整，天然是堆）
  G; o- h1 n; H) i        {
                AdjustDown(arr, sz, i);
        }

. N* Y1 W8 M# M' S7 B, i! t( @5 s        //2. 选数
        i = 1;
) v' }6 W5 W6 U        while (i < sz)
        {
  }5 \, l% P+ z" k0 n                Swap(&arr[0], &arr[sz - i]);//交换堆顶和堆尾
: @2 Z- ?2 Q6 \0 y                AdjustDown(arr, sz - i, 0);//堆尾视作堆外，对堆顶向下调整重新建堆
                i++;
/ m4 [; ^, L6 Y4 [        }
, s5 g% d5 D/ A}
; z4 F8 Y6 e: p  k4 o4 B
1
  n2 U* p) J( q; G4 m: V5 M6 p3 j2
8 \( o: D# L& F+ M3
4 ^  s8 F& ]9 @' `" a" n& h0 C% o  X4
5
6
$ t1 Y' [6 l2 i! v7 |7
8
1 a" N) j- R- D1 \: Z9 W9
4 G( w# a( l& ~- U( s10
+ o* X$ O" c/ S; X$ Z4 X11
6 C7 h( q9 C. D) N( D' ~12
+ n4 X7 o' w$ m! P7 ]2 i  |13
! R/ a7 w6 B7 T2 {& Q; Q14
15
16
17
5 |0 v0 ^* f8 d5 S: S6 o18
19
20
* a; y# e8 D9 u' c/ `. k! U21
22
23
24
& d3 V( E1 Z* x25
+ M, G8 k+ l, Z4 K$ X& K26
27
/ f: q; ]. F, {5 Z, ]; L3 d28
  H. X1 @' d; W% O$ K29
30
31
32
33
- X# n: `, a4 i34
0 x; }3 I6 U3 e7 F& w; F! ]35
36
) x% u) W% n) G- O& g. h37
1 ~( p; K: ^! u0 c* l38
! E6 a" U( g1 F+ \# m" u0 g: V39
40
41
) ?  r, K: w5 r' C* @# t! Y; }; [42
$ J, K9 Y6 `: n1 ]3 {: U1 B* u43
+ h* D9 _! k: Z8 {44
; a6 [% U5 o+ K5 {- g45
46
47
48
* o& Y  T) h9 T5 J1 L49
1 O* V  c' ~- Q+ |50
+ H# C& I3 [; w  o1 b: S5 y51
52
' e% Y/ b9 Q: z& d" Q53
" q3 Z: n" _% `* a- Y7 u, E54
55
# k! F4 ]. U- r& O% S1 V

稳定性
0 Y: `6 H6 a; h! ]/ {% n建堆和向下调整都会打乱元素顺序，所以

堆排序是不稳定的
6 P: h0 C: C, e$ U& B1 P% k6 u: y
, k* A# Z, o! Q; G6 U  `0 ^/ z' u复杂度
时间复杂度
单趟排序，交换，并对堆顶向下调整重新建堆(O(logn))；趟数，n趟，所以堆排序的时间复杂度为

: a8 [1 ^, J9 y; ^& nO(n*logn)
8 H5 b5 W- Z- {) A
+ e; u- V& B9 [7 p空间复杂度
/ k* N6 [0 }+ C/ N2 D0 y6 L原地建堆
4 a" t" z9 u1 _4 I
$ h0 ~9 n) }* ?0 v' V' S2 U0 uO(1)
9 ?" x, ^# r1 @
交换排序
冒泡排序
思想
& O9 R- U( Z; Y  @冒泡排序，左右元素两两比较，左大于右就交换，一趟排好一个元素


8 a5 n) v1 B' X( l
5 S; Z' _5 v& H& x操作
单趟排序：
; {  F4 o( A, m/ i每趟排序从左到右两两比较并交换，直到走到已排序的元素就停
5 H, w; b* z% d8 o5 ~. l6 L' v/ c1 N$ E每趟排好一个元素，所以需要排序的元素每次减少一个
整体趟数
; l. Q! T2 ~8 l+ P若元素个数为n，总共需要排n-1趟，最后一个元素天然有序
0 ~1 W. K5 h& J& qvoid BubbleSort(int* arr, int sz)
8 b: o. i2 ^+ v' J- ~{
        int i = 0;
        int j = 0;
0 r& E  W9 x& _% i2 N1 l4 v# k        for (j = 0; j < sz - 1; j++)
        {
4 k- V& N- U9 X8 e" F' e. I                for (i = 0; i < sz - j - 1; i++)
                {
! x+ }4 M* y- J) s  _# @                        if (arr > arr[i + 1])
3 U8 @# y! b! T5 r' ^                        {
                                Swap(&arr, &arr[i + 1]);
4 f3 y! n# v* n; _; _                                flag = 0;
' }; Z8 M$ O) d* a/ k* q8 @/ ^# q4 G                        }
1 J+ Y3 R8 v" a( Q+ q, t# g                }
        }
}

1
% U% D, t& `) b- V+ }: Y- Z2
$ A, ]& k2 W0 r+ F3
4
5
6
7
8
9
10
: A; U' H! G" O11
12
13
14
  k4 `4 I8 C" a1 U. Z" Z15
16
优化
当遍历一遍发现序列有序，直接跳出

void BubbleSort(int* arr, int sz)
{
+ |9 w6 \5 ]+ X  Q) N! u) t        int i = 0;
        int j = 0;
- y. |" |4 n" A# I        for (j = 0; j < sz - 1; j++)
( e( S6 ~  v0 z0 N) f5 z        {
% q7 g* h, u, F3 l$ C# f7 K. x0 S                int flag = 1;
5 x. P3 v9 C- u                for (i = 0; i < sz - j - 1; i++)
                {
                        if (arr > arr[i + 1])
                        {
# i" t0 ]  C5 B  x+ P9 c                                Swap(&arr, &arr[i + 1]);
- c4 e: O8 F' F+ n                                flag = 0;//不是有序就置0
4 W2 Y# s7 K0 k9 E9 H. u                        }
3 y4 r) `2 d" c6 t, @                }
                if (flag)//如果一趟下来还是1代表有序
                        break;
        }
3 D! ?  S8 x+ h  n}

. I/ d$ A2 V7 W1
0 H8 P- B1 l; u) F2
3
2 z) F" l& N' o* C$ k0 j4 C4
2 s/ W  S* K/ m. P) v5
' D: k5 j0 u/ a0 N' A0 ~  X( O: d6
7
' x5 ?# t* g# W: J9 C8
9
10
11
' c* x9 n+ Z' V8 l" U( @  y12
13
14
15
16
( c+ C6 j7 D  I6 R2 l- ]17
18
  v; s- ^) ]  \' Z, T/ a! G19


- Q% [' R% _  B4 T稳定性
相同的元素不交换，即使相同的元素不相邻，排好序后也是按照原来次序相邻起来，所以
  O/ @1 o9 T  l2 t0 C0 c/ s8 Q/ R
. h; w' O* ~8 C# Z. R冒泡排序是稳定的

复杂度
时间复杂度
最好： 当序列有序
( i8 A4 M, t" ]( J5 e6 ?7 O, ]
未优化：

O(n)
* T- F" t# M' f9 K9 o
6 ^" k7 A9 s& K0 R! V- J' S优化：

O(1)
$ q. t( l6 m% M: p7 Q
# v4 ?1 |: O- V% X% B8 T* ^/ J最坏：要进行 n-1 趟排序，每趟交换 n-i 次

' a0 |: Q  f5 q1 g% Y0 K) }O(n^2)
  l! Q+ J$ ]& W% z5 v$ N
空间复杂度
3 r" l8 [/ z' `O(1)

1 f; T3 {1 h! @  O5 D9 S% n快速排序
思想
. E9 e1 X  R; S, K; A9 K/ X  h分治思想：单趟排序排好一个基准值(key)，key的左边都比key小，右边都比key大；再对左区间和右区间进行同样操作。
4 o7 T' ?) ~; ]2 ~
2 i. k5 `+ W8 U" g' D所以快速排序可以用递归来实现
0 x* L) @& M+ `8 }; D  o
) M6 P  n$ j6 o# A4 [- ?0 T操作
. l# ]# J6 L8 e$ r& g& |* Q- F有三种单趟排序的方法：

& F6 N5 U( a; }* H6 z' ]Hoare法
设 begin 为当前区间的左闭区间，end 为当前区间的有闭区间

' I1 m9 M& j1 k左下标 L = begin，右下标 R = end

设 L R 相遇位置为 meeti

  J, ^2 D0 z) P$ M​ 称 比 arr[keyi] 小的元素为 “小”比arr[keyi] 大的元素为“大”

7 [& v* R7 s6 t% F; S/ h​ 称 arr[keyi] 的左边都比key小，右边都比key大这种现象为 ”左小右大“
7 I; h2 o) S& y4 i; f2 b
选 键值的下标 keyi

1 R8 g) Q# v$ _, Z$ D* `左1位置作 keyi，则 R 先走
右1位置作 keyi，则 L 先走
7 j$ _: x! g2 ?1 u# w5 T6 mR找小，

2 J9 E  {' |& C5 I& l找到则停
2 o: Y+ W2 ?  U$ x5 E% B5 x& T遇到L，则交换 arr[keyi] 和 arr[meeti]
L找大
9 z) z8 _8 N4 L0 Z; J
' _. ^; N+ G% E找到则交换 arr[L] 和 arr[R]
遇到R，则交换 arr[keyi] 和 arr[meeti]

3 K5 W7 K( [( h2 \
解惑：arr[meeti] 和 arr[keyi] 交换后一定符合”左小右大“吗？
3 ?1 F  E# v) R- B1 V/ W8 j; Y答案是肯定的：

  O9 g: D7 o: {


//[left, right]
- j% b7 v1 l: _; aint PartSort(int* arr, int left, int right)
, U; F* ~+ S- F2 t0 Y{
( e1 [% D" z: Y* k6 c: z+ {        int keyi = left;
" S- H8 f& y0 ~1 C        //相遇则排好一趟
) n9 h7 I) i- w0 A        while (left < right)
3 G3 M' H% V% k        {
                //R找小
+ z' b. o- F9 _        //left < right: 1. 这里也有可能相遇 2. 以免left和right错开
        //arr[right] >= arr[keyi]:相等也要过滤掉,1.相等的在左边右边没区别 2.不过滤会死循环——(88888888)怎么排?
0 X5 R5 @( N1 R; |" R                while (left < right && arr[right] >= arr[keyi])
                {
                        right--;
8 p% T' F* ^8 m/ o9 Z8 ?                }

+ s7 H% m: L/ _# ?+ u                //L找大
                while (left < right && arr[left] <= arr[keyi])
                {
0 C! {" f1 W" J5 X" T1 p  S                        left++;
7 t1 X# G! ^3 v* o* d                }
               
        //相遇就不交换了
                if (left < right)
) Y6 @0 D& S1 @7 Q" L                        Swap(&arr[left], &arr[right]);
        }
( i, u" b8 r; i2 q- ?4 m0 i
0 h; A* Y) ?( S  f        int meeti = left;
# @* R3 n" }" J  Y: C
( q0 X# F' V2 p) o+ V2 j, n: D; V        Swap(&arr[keyi], &arr[meeti]);
& z0 d( Q  a; D2 X8 a9 x
        return meeti;
}
( U5 U& r' B; H- ?* R8 r! B; P1 d
' Z: N& L( V. F6 [0 p# A1
, F* E* q2 T6 D2
3
' o9 t' q5 W& x5 h& A+ X1 N4
9 [! t2 I& o' H/ |8 `4 T7 J5
8 v& q# H* x% p9 J' x7 L6 m& I. r3 Z6
+ }0 r& a. y' e  q  l, |( `# Q+ w% Q7
& w, |' t2 Y5 g+ b8 ~8
9
10
11
12
# A. r6 n! R5 q. g: r# g: {7 M13
% n# v1 u! o) w' _( `14
1 f* I& d  s6 l* }15
16
17
18
19
20
* k" q1 |7 i6 P+ A% ?21
22
23
24
3 j! s2 q5 ~7 S: F25
26
27
" t8 S  U% T/ h8 l% Y; g) i28
29
! E$ B8 w) }% t; w/ p30
7 _' n2 Z" x7 ?6 {% f: x31
6 y2 ^# c0 A; |32

1 @0 x% N) w7 `+ j2 `8 `
' [% e4 H9 e' c% i$ r解惑：为什么key要选左1/右1，选中间不行吗？


& L; o# f. S1 e% T& @) ]: G9 W可能有朋友已经想到了：（接近）有序情况，选左1/右1就出问题了，区间会分得很多，递归很深
  X: p! x$ z  e3 E+ r) E


  B; B4 a0 T- L" [$ r6 n9 A& u
' ?# T1 G8 y( N1 a/ E3 w2 a6 A非常容易栈溢出，怎么解决？针对有序情况，优化选key
, x+ C! o+ z1 W) O3 |& ~
1 R: p( p: Z7 f! H' Z4 Z1 H优化选key
随机选 key （是一种办法，但是不那么彻底）
选中间位置作 key
/ B' N. x1 p3 `: f9 Q6 R, @解惑：那先前实现的单趟排序不就失效了吗！
" L- }. Q2 V4 B/ l6 I：选到中间位置作key后，arr[begin] 和 arr[keyi]交换，逻辑还是能用原来的逻辑
& J# H8 D- ^. d2 B2 ~
9 l$ ^3 w1 T( q; C" U7 R解惑：如果中间位置选到很小/很大，换到左1后，还是会导致”区间分得多，递归深“的情况嘞？
前辈给出三数取中的方法
; v* _6 {$ X# i! X! J1 d
1 y6 ~/ b3 x8 i5 ^' _: `; `三数取中
: W, _5 b6 \  c" S& Z在 arr[begin] 、arr[mid]、 arr[end] 中选出中间值
0 ]$ E+ `. M( J* r( U1 G. a这样一来，换到左1的最坏情况也只可能是次小/次大，缓解了“选中间作key””区间分得多，递归深”的痛点
优化选key后的Hoare单趟排序：
; w9 M5 O0 p9 i( U0 n# a! _6 A0 O1 z7 P
: I6 P, M$ T$ u7 u% o/ j8 Zint GetMidIndex(int* arr, int left, int right)
6 G# ~& `- m% u% b! Q/ ^* L{
; j) {  ?6 M1 Z( Y  s: }        int mid = left + (right - left) / 2;
//  int mid = rand()%(right - left) + left;//增加了一定随机性
        if (arr[left] < arr[mid])
( b: ]8 L! g! M1 N0 g1 X! m+ K/ `        {
                if (arr[right] < arr[left])
                        mid = left;
                else if (arr[right] > arr[mid])
0 R2 n* [: C1 q$ z: A+ m, {                        mid = mid;
; ~! D* b9 q1 Z                else
; ]8 G9 ^0 Q8 d+ S5 q1 h                        mid = right;
4 L: W+ f5 X6 E2 `1 R+ N+ _7 Z        }
! H# `' }. m; ~7 }, _        else//arr[left] > arr[mid]
2 z! o$ ?1 z! Z- O/ A: r        {
                if (arr[right] > arr[left])
, K( J- t! G4 {* q  E4 W                        mid = left;
                else if (arr[mid] > arr[right])
                        mid = mid;
                else
  k* V% z( X) N/ q6 k$ a                        mid = right;
        }
        return mid;
' P) `7 J8 j- [5 [- ~' S}
0 D2 R, \5 I6 ?. Y) P3 y0 T
int PartSort_Hoare(int* arr, int left, int right)
4 D2 L, z- P' ]; W: ~) b# f{
        //中间作key，优化排（接近）有序数组的递归深度：O(N) ==> O(logN)
        int mid = GetMidIndex(arr, left, right);

        //单趟排序走的还是左1作key的逻辑，才能保证单趟排成
* E  G, m* D' K) N  p        Swap(&arr[mid], &arr[left]);

0 T* g' O  a1 }7 J8 x1 E        int keyi = left;
1 h9 r& M. p% r. j- [! d& @! H- O        while (left < right)
        {
4 I. y8 X, X5 d9 O1 P  G' `                //R找小
                while (left < right && arr[right] >= arr[keyi])
                        right--;
$ f' V0 {- y3 J* P& }% O" C
                //L找大
                while (left < right&& arr[left] <= arr[keyi])
                        left++;
6 w  j$ D0 Q" K
                if (left < right)
                        Swap(&arr[left], &arr[right]);
- ?& ^' U$ }, W- h# W# N- ~        }

' [$ P2 |0 ?8 k) f7 H; f  K        int meeti = left;
- X5 v+ q. k3 w" r! B
7 D5 \5 a, Y* a; K6 {  C        Swap(&arr[keyi], &arr[meeti]);

        return meeti;
}
- t7 B) w2 |- t4 R( P" ?! S
1
- C5 g/ K% n, K7 y2
7 y5 i8 q1 h2 r& X" L) ^+ X3
" z4 n9 |, r# D* X. O2 E4
$ G! `* ]- _' D5
+ ?4 }3 w: z: M. c& w: k  [. G" |6
7
8
9
10
, V( a! H  ^& C8 n2 e3 C0 \3 b6 n9 x. O11
12
13
14
15
* B% S3 g8 w$ V( S2 W16
17
18
8 n+ m, m# g. z19
$ m# c$ d* f, Y8 [1 \! P6 y20
/ a1 p) B1 Z9 z7 A1 Y9 N9 G21
/ |" @. o4 d, E22
1 U- F2 m( N- z) @9 e  ^# x9 c' R& T23
24
" m) z' n2 c/ U25
3 I: T3 [- ?( q/ ?# ^; u26
27
28
( ^) C% k: z: J( P' G) [1 |% G: K29
+ l( Z2 Y- t0 G! Y- ^1 g30
$ \- u% F- \, \1 R, e. a4 M31
1 i; L9 j( K6 U8 h32
5 F) W- J/ a$ x5 O7 t6 ~, Q/ W" r33
! |! U# F( X* Q& j8 V- I- T3 `34
  w2 H: @8 n6 x+ |, U: ]35
36
37
38
39
40
+ l' S  T" e3 \( r41
* M' D" X: R+ b9 r: j. y9 {42
43
+ ?% i9 @  y) d* o/ {44
45
46
47
48
" F9 F- H7 i: j9 j; z  E# t0 ^. b. @- f49
50
& \" U# p7 u% w$ _& l4 f. Z4 j51
% u, U% t+ s0 z' Y52
53
3 s# a8 F. f. B) Q% P5 Y$ f* W54
; |: K+ C' v3 t- [挖坑法
初始状态：L作坑，其下标存为key
+ \4 l+ x8 \- w* F' F(1) R找小，扔进坑，R作坑
(2) L找大，扔进坑，L作坑
重复 (1) (2)
- h$ z4 p1 a* f$ S最终，L R 相遇，交换 arr[keyi] 和 arr[meeti]
% J4 p/ I4 e" s2 U* I# Z  A

int PartSort_Hole(int* arr, int left, int right)
{
        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
% |- _3 t$ }; a2 H& m
        int key = arr[left];
6 r/ C  J0 \3 o- t        //L作坑
. S6 V4 ~5 Y5 j$ \, n! e        int hole = left;
0 v4 Z- z% ]2 I2 f' F        while (left < right)
        {
0 R+ }- [. Y  _' t6 n+ `                //R找小，扔进坑，R作坑
+ L! ^( g  \9 \                while (left < right && arr[right] >= key)
                        right--;
                arr[hole] = arr[right];
4 @7 n( I( t3 K+ O1 X                hole = right;

                //L找大，扔进坑，L作坑
, i6 l/ N+ c9 F8 m  B8 _' N                while (left < right && arr[left] <= key)
                        left++;
                arr[hole] = arr[left];
" |2 T' D' G0 b                hole = left;
4 \% \6 }5 L" p; ~" u        }
        //meet
1 M: t2 {& k; {7 A3 a' ]5 s        int meeti = hole;
# q0 ?* ~, D8 g5 D3 F7 S" x3 r; Z" E7 a        arr[meeti] = key;
: b( `) G; G3 p' }: e! Y
        return meeti;
+ P0 N/ u' ^$ U: p}

8 w& t7 x; V: ?6 P8 c8 V1
5 {2 g; f6 Z! a, W) }2
- x8 V0 n7 e, v: Y3
4
: D' B2 V& a0 H3 ]$ K# w# s, L9 {5
6
2 b) K5 ?; E. ?# E+ z7
5 p  M; T4 w: }8
9
10
- ]0 P: h6 C, ^* }9 g11
12
13
9 z% e9 ^4 }; E% r14
% c' L; C" o$ `' }6 h' W, P. L8 Z( U15
4 t# o) I* O/ B( N* E16
2 _% O3 q0 f+ U3 v5 g! @8 D1 ~17
/ w8 @1 R  C, c7 o. q8 `18
/ y9 L, [" K9 w+ K7 m0 h" y19
5 b5 V- I8 N  o5 R9 @" U. A) u20
1 z% x6 M: |" u) m21
7 T. K" G0 h/ A+ B6 L22
23
24
25
26
27
28
前后指针法
, A) K) D. M1 g0 [. W5 Y& F此方法理解起来较为抽象，但写起来十分简洁方便，不像前两种方法易错的地方较多

cur找小，找到则停
++prev
如果 prev != cur，交换 arr[prev] 和 arr[cur]
: U6 s8 w" I1 }+ [) c. E% g如果 prev == cur，不交换
- T, l. k- j8 P! ?当cur越界，代表找完，排好序了
prev == cur 为什么就不交换呢，跟自己交换没必要——比较一下和交换一下的性能损耗相比，肯定是比较来得低


, S& Q( `$ b9 p- u  d3 a3 Z
* T- l9 F  |8 J9 I! m1 uint PartSort3(int* arr, int left, int right)
{
        int mid = GetMidIndex(arr, left, right);
        Swap(&arr[mid], &arr[left]);
       
6 e4 ~2 T# ]8 ^2 G0 b  //int key = arr[left];
        int keyi = left;
4 v+ w. I8 x+ y1 N6 l6 [9 Q% _
1 V8 M5 S9 ~6 c, z3 J6 w  l        int prev = left;
* r% L1 M  f" a: c6 N) M6 Q        int cur = prev + 1;
) x. B5 k' ^# _; U- P       
' [* z9 [2 B0 F2 p; B# h    //cur越界：找完小的，prev的左边全小，prev右边全大
- I' R# p, [& A$ }3 D        while (cur <= right)
* Z0 M2 o" O  w( l        {
7 d' W, \6 x2 _+ c        //++prev == cur 没必要交换
! A3 q" r" a$ v, |8 }                if (arr[cur] < arr[keyi] && ++prev != cur)               
                        Swap(&arr[prev], &arr[cur]);
5 ^. D! c) g% X: T. n% b+ e8 h# l
                cur++;
. Q+ P# T3 {# d, S) P        }
6 S- X1 a% g, A! {7 U5 b! F  U
        //键值存是的值：
        //Swap(&arr[prev], &key);错！key在这里是单趟排序的局部变量，我们要和arr[left]换
        //Swap(&arr[prev], &arr[left]);//这才对
  U% P5 q: L. X- E2 t+ ~    //键值存的是下标：
: J4 X- p8 j) U2 V        Swap(&arr[prev], &arr[keyi]);

8 B# ^1 e9 b% Y, V        return prev;
}

1
9 ]4 n7 f6 ]7 w; `# K, P  q* @* @% f2
1 M2 h, k% E0 J3
# V7 R: R, w& h2 n; P5 S1 U: k4
, f' t& w' k0 d; P& T5
6
) U; [& }2 Z8 e5 y5 V1 M8 H7 A7
8
9
5 {0 D) r# y6 R4 C" r10
11
12
: p/ x! _1 S( A13
  S" J8 F! |5 p( m: l  _' e" u14
15
( C; N$ r: y9 Q16
17
! W1 ~6 |9 i5 m! `* t# U  J% \18
19
20
21
22
23
24
$ H7 V. R% P  w* Y25
26
: S/ J; V" y) A27
28
29
整体排序
' E$ w& |; g: e4 b2 E递归——每次排好 arr[meeti]，分出左区间[beign, meeti-1] 和 右区间 [meeti+1, end]，再对左右区间快排

//[begin, end]
void QuickSort(int* arr, int begin, int end)
{
* r! g' Q& B/ Y4 A1 ]( ^) @1 F        //meeti位置符合有序 + 左区间有序 + 有区间有序 = 整体有序
8 [; k- B3 t: b9 k        // [begin, meeti-1] - meeti - [meeti+1, end]
. k# W+ B2 H0 g% T/ R0 k                //1.begin > end:超出范围
" c7 E. J, z% M  T9 y                //2.begin == end:一个数天然有序
    if(begin >= end)
        return;
' u+ x0 J# S+ X- y
+ j/ m7 E4 F8 a" z. i  ?                //排好meeti
3 p! H+ ?4 `$ ?* A1 I, e* v1 ~                int meeti = PartSort3(arr, begin, end);

  V7 t# A" i" y1 `                //排好左右子区间
1 g8 K& X, k2 |- |                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
$ V6 L# D! d6 o9 B: @9 b        }
- j' z0 i  w. I7 ?% t* }}
- i/ M% l  a4 M. j3 ]$ R
1
2
3
: e' F0 i% x* W6 c* \: B8 ^4
5
6
( q$ Q! a: `; b6 k7
2 I  ?3 S5 _, N8
9 S% b4 M1 K6 l( @* I4 }9
10
! B# t. G; x2 `( h4 e( m) ~# h5 x11
12
13
, q( h7 `  R" S  w14
15
6 U7 m* H6 `6 M! J0 H8 C; q+ L16
0 P1 Y9 q: v3 I& B, w17
- a. m5 d  h+ B3 a18
1 e- R, |, o+ X5 R3 \0 `…

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

优化小区间

  }" i* j' t$ o8 v+ ^
& M- |! h8 M4 m6 f3 W  K( t如图所说，小区间内数很少，却消耗巨大，不如粗暴便捷地直接调用插入排序

7 i2 ~' W; {$ L那什么算是小区间？
4 g# k/ e/ Z8 m) e
- K4 {2 e( L2 F其实小区间没有确切标准，8-15左右都可以的

& u; j6 W) W0 ^' v" G+ S+ a
这里就把小区间定义为 含有 8个数或以内 的区间
* e+ K* s7 c0 M# z9 s
//[begin, end]
% @8 J! R" N2 ?$ \5 N+ rvoid QuickSort(int* arr, int begin, int end)
* ?8 x% g0 \5 m( Q# @{
  K1 Z: j2 Q$ Q9 {/ O        if (begin >= end)
/ G, f" B, _3 H2 G9 @0 {# M" I: b                return;
$ x: S, b5 Y$ L3 h
2 w7 E& S6 g5 y        if (end - begin + 1 <= 8)//小区间优化：后三层直接排
* G1 A% r0 [5 `* E* t        {
/ S' n/ M1 W( f& T* M; h1 y, G                InsertSort(arr + begin,//可能是上一层的左子区间/右子区间
                        end - begin + 1);//左闭右闭，如 [0,9] 有 9 - 0 + 1 = 10个数据
        }
        else
& Q8 D0 g2 v+ x. I: H% N        {
+ W6 `) O; l4 f% E; m                int meeti = PartSort3(arr, begin, end);

                QuickSort(arr, begin, meeti - 1);
                QuickSort(arr, meeti + 1, end);
        }
}
' @7 A, p8 Z5 x) N, I7 L6 O1 Z
* g- k, S1 s$ s2 c, @1
+ C3 K5 c0 R1 {8 l2
9 a: x' w' S3 i! \# Z3
, O+ l. l. j- G4
) b  y$ G9 @* |) E: I! \5
6
  B) w& b, x. ^" }9 m3 J7
8
9
$ }* o/ z' n* ^) {/ v9 P; d10
, O5 _/ Q/ a% {11
  }7 t+ S3 a/ o' g: @8 o12
+ ]: R( P4 D) n. x2 ^# @% y6 Z13
- _6 b0 w# J) z& |9 B" \0 R, G14
8 v5 E2 c/ I; \/ i! e' ]15
16
17
9 k# n5 G4 L2 G& G; B7 U/ k18
19
' h, ]. \! a! a) i4 C快速排序非递归
+ ~% ?1 R2 _9 B6 ?7 F为了解决彻底递归深度深的痛点，我们来试着把它改成非递归
5 t1 |$ B5 I7 P- Z
思路：
8 k, `$ P( ~1 `递归深度深，栈的空间又小，会栈溢出…
' \# j9 w* |3 `, V' n
: u1 V( j% K) ^, t. Z那不如把函数递归“载体”换一个，在堆上手动开辟一个栈（数据结构的栈），栈帧里存什么，我们堆上的栈里就存什么！
# G; C# t+ W# I+ o+ j
* h: `& |8 e3 w. Q核心思路：在堆上创建“栈帧”

' m: Y/ B- ]$ r5 _5 ^快排的递归，栈帧内存储的最关键的数据是什么？区间。有了区间就能不断排序、分区间，排序、分区间…keyi都是可以算的


9 i+ C, M, H6 f1 f/ Z  [6 B( f
在用数据结构栈存区间的时候要牢记 后进先出 原则，贴近递归的写法：
3 j8 k2 N  c* k0 Z: A
- o9 ?% ]9 X' h, t& h先递归左区间：就得先入右区间，后入左区间，这样才能先取左区间来递归
8 `" I# m: C0 s" [5 [' w) D7 ]先取end：先入begin
void QuickSortNonR(int* arr, int begin, int end)
{
        ST st;
        StackInit(&st);
$ b2 z& p# U  Z4 f8 @; ^: H6 t       
    //先入begin
        StackPush(&st, begin);
    //后入end
7 p& n9 @  `" c5 ^+ C4 w        StackPush(&st, end);

        while (!StackEmpty(&st))
        {
+ G& `9 o0 g& E# f                //先取end
) s7 G+ G3 O6 y, y% B                int right = StackTop(&st);
$ h/ J; `: T, x$ j+ k: a8 e: }                StackPop(&st);
                //后取begin
                int left = StackTop(&st);
                StackPop(&st);

                if (left >= right)//1.只有一个值  2.区间非法
                        continue;  
                               
                int keyi = PartSort_Pointer(arr, left, right);

                //先入右区间
                StackPush(&st, keyi + 1);
) z: }, O# L; ~2 B- G                StackPush(&st, right);
% T6 B2 D: N2 K9 V/ r# F; `6 y                //后入左区间
1 J5 J: V' h. M3 H3 @                StackPush(&st, left);

$ A9 w1 O2 j7 R1 n5 _3 m                StackPush(&st, keyi - 1);
0 h  V7 `' ~$ n, i4 V        }

        StackDestroy(&st);
! l7 |4 j8 s/ w5 n" Z& G" @0 x}
/ M0 }4 T8 o) Y
0 i9 b  C" [# {1
4 [. T# R  l0 z( u; }7 s4 k+ g( r2
3
3 w" b) ?# E/ w! e( z0 ~4
5
6
7
8
+ g1 n5 g( W7 K# o$ R! f2 Y/ r9
* ]/ e  l" V1 X. v) u% e! q# @1 s10
0 t* g, y5 l( B. T- Z11
12
& u9 T0 L$ c6 F  T& R$ _" y7 y5 u13
14
' p; F  x) U3 l6 o5 [15
16
17
- \% z: V# r% _. a0 i& S. m$ q& Y18
; i, D0 g% k9 @7 j1 [8 T19
: ~& u1 K# w% r2 h+ L7 w20
8 x9 M  \9 e  e8 {4 g* W21
22
6 [3 }. h. ~" i! k, L; v" I* U* j( Z6 r23
24
$ ^. I" p/ |7 f! I25
' Y- x# t" j( z) w26
. t' N  O( ^/ v4 J' v- T27
/ p0 i9 l! [- d- v  S5 r28
29
30
, o3 H0 I  y& R& m7 B31
( D) ^1 D# E! x* F( |32
3 O5 g5 j: c- r# J+ R. W+ \33
34
) i: r9 C6 D% a/ d* I4 o) a35
9 J2 ^2 B$ F2 J! T" ~数据结构栈的实现可以看博主之前发的博客
8 w9 H& |: C9 S, B. |) b: Y

0 a$ h1 x1 Y; l* d$ Z归并排序
1 a4 S% Z/ z8 j0 H
…
; R3 q8 l+ }2 E9 d9 V, d) r
性能测试
void TestOP()
( A: c0 S5 d1 V# V' K: |{
7 Y+ a( m& |. o) e/ n2 V% r        srand(time(0));
: O5 C2 [- s& h        const int N = 100000;
0 U  _) x" c! a( o/ |3 `        int* a1 = (int*)malloc(sizeof(int) * N);
: i1 f% C7 s8 p        assert(a1);
        int* a2 = (int*)malloc(sizeof(int) * N);
! O& [  X+ `+ |$ r2 @( Y        assert(a2);
        int* a3 = (int*)malloc(sizeof(int) * N);
        assert(a3);
        int* a4 = (int*)malloc(sizeof(int) * N);
        assert(a4);
' n9 \4 v4 |5 m* g: ~) E        int* a5 = (int*)malloc(sizeof(int) * N);
        assert(a5);
7 a( O3 x* v  ^: Y' _- ?$ U- c
        for (int i = 0; i < N; ++i)
! ~9 g- x/ C+ b* G0 S) V$ @  G        {
                a1 = rand();
% t) U9 L5 w6 V  l& E, D4 n                a2 = a1;
4 H2 ?9 ~2 k& @- z* g$ u) v: Y                a3 = a1;
+ s) j1 m( I* `2 V                a4 = a1;
! L6 {, }7 z6 n& u% k" l7 b                a5 = a1;
        }

: L1 Y3 h" u" ^        int begin1 = clock();
$ Z  g, m4 e1 e6 y3 f        InsertSort(a1, N);
0 H5 t" B/ T" f0 s8 ]% R' T5 A        int end1 = clock();
, \: ?; o1 x4 D0 _7 Q0 O
        int begin2 = clock();
        ShellSort(a2, N);
) l- Q7 o% R/ `* K0 I        int end2 = clock();
( g/ O% a0 R/ I  F
& |. n8 O$ B) }( V) O& x        int begin3 = clock();
        SelectSort(a3, N);
        int end3 = clock();
5 G0 V% S5 M$ |$ e5 e; w4 a
4 |; M6 Z8 R) N+ |1 K1 Y        int begin4 = clock();
* L% C# a5 a5 \2 m- Y        HeapSort(a4, N);
: Y6 p! `0 C6 R. C3 D/ B! }9 a        int end4 = clock();

        int begin5 = clock();
  {' [$ |/ l2 `/ ?' M; F        QuickSort(a5, 0, N - 1);
                //1.中间key
* K7 t. \6 Q; q! G) N  {                //QuickSort(a2, 0, N - 1);
9 U7 v3 T. n3 \& _1 K6 E+ D; v+ u                //2.三数取中
                //QuickSort(a2, 0, N - 1);
                //3.小区间优化
                //QuickSort(a2, 0, N - 1);
        int end5 = clock();
7 T' m+ N. D& T
! o5 N' r2 A  _) ]7 m' U% G
' `( r5 {* L, k2 P        printf("InsertSort:%d\n", end1 - begin1);
        printf("ShellSort:%d\n", end2 - begin2);
        printf("SelectSort:%d\n", end3 - begin3);
        printf("HeapSort:%d\n", end4 - begin4);
, K" H, P( J2 n        printf("QuickSort:%d\n", end5 - begin5);
# F9 O$ d+ Q: `5 ^
        free(a1);
. I1 H8 e5 g) t1 G( N8 O1 f        free(a2);
5 V9 D1 w. P2 R6 Z% [0 O2 B; E# y        free(a3);
( r' l( N- |9 J+ B9 x$ i        free(a4);
+ J: W2 V. _: l2 v! Y        free(a5);
}
' B( V+ e0 ~; `; W4 ?; F
1
+ Q& |. \, c; X8 C( A" r2
0 f2 Y2 o7 A+ D! o5 I2 H3
- W0 }1 D( Y2 z3 y9 o5 I& B9 E4
5
6
4 X# T1 ]4 U/ N, Y* Z) X7
' Y- R2 ~* o+ {) C/ O- g8
" g- i) ]6 a4 ]' u1 L* I9
10
11
12
13
  ?6 i- F3 y" V& x% K! t14
15
16
17
18
19
20
, L( [- m$ I) w21
* k$ y( `' R  j" d7 K- U22
7 H3 |+ r0 _2 B: z7 C* c23
" q! R$ t2 J5 q" P0 c+ B24
3 V  a1 ^) T  z: ]25
# a9 ]/ ^' T0 c26
27
28
29
9 ^5 q5 y, w4 R9 Z30
1 M: U" i6 ]3 u0 k& G- K31
( D2 i: u! W. @. `32
6 B- M' f* z: w8 t33
" u0 N. J) v  I0 P+ Y+ y2 n( b34
35
# S" L+ f! w! X" x& M+ J36
37
* ^( L7 \: ~. Y+ ]38
39
( o* Y8 J/ f  M" I+ |4 i& G' r3 m: H40
* h& [  M) N* Y; p/ C41
$ |- B1 i2 x( O) l42
43
7 P$ b/ U6 x7 d, _2 _8 {0 b44
, P! W+ Z; N1 F6 ]45
# e7 z4 F3 j  Z* Q( L' z! g8 B46
6 Z3 l4 ~  h) a/ d8 r' P, a47
- @. _; y8 V- F3 z) `48
49
50
51
& O6 l  Y: z; W" k  {$ {3 H52
53
54
55
56
57
) K  v7 m' x# {& D; h: d58
3 V9 g/ }: m  S; S59
60
61
62
63


( p5 w/ y2 t2 |( I5 T$ A不愧我们费这么大劲优化快排，多帅哦！

差一个归并排序，后续补上！

: u. H& \' T" y  u  \3 A& Y不知不觉数据结构初阶就学完了，不得不说这东西蛮有魅力的，继续前进吧
————————————————
; E% D2 |8 S- s( x; E: J版权声明：本文为CSDN博主「周杰偷奶茶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/BaconZzz/article/details/126740832