【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选...

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
! S5 o- o% N2 z" T文章目录
6 H# b0 x3 A8 `. S! Q. o% _: s排序
6 i4 X$ B1 t- e% ^4 E0 Q8 ]1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
$ o) T5 r# W: s( E# K时间、空间复杂度
9 W/ [) D( k( b6 d7 X* B（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
) B6 u9 X3 O( O' h3 |时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
时间、空间复杂度
* \6 p. h" B/ l5 h2. 交换排序
0 G# C. }: p- }( P3 R$ \2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
# O  _! A7 z, g! u时间、空间复杂度
* Q' w- F) Y5 u3 m+ t* P- I( ]5 p3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
, N5 Y+ y, B9 R) e  S7 z; k+ M3.2 （不稳定）堆排序
* ?# O" G" }: X4 N8 A① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
/ `) g" W, N1 o/ t② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
) ?, r! s) r, F" Y③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
9 s1 }* W$ G1 D3 r) Q9 }7 L  ^6 _时间、空间复杂度
5 f( ^$ s' ^. z  {④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
8 Q$ O$ d! s7 J# t+ R④ 总实现代码
. {& V1 ?/ R" C时间、空间复杂度
5. 基数排序
内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
2 y& V  i) g, w; \+ ^0 u% r
- \& Q# g* o6 w+ r4 @5 f( P排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
( w3 Y4 Z. j3 b0 P* z( [5 Y
+ v. f; w! f. a4 G2 P算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
, C3 p: a- l% D" S3 \! g+ E% R稳定的排序算法不一定比不稳定的排序算法要好。


5 R' ?2 y1 w$ ]8 c# m排序算法的分类：
; Z" v; Y4 s5 B! @内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
* k" f' X0 ]! ^外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
, \. b3 K1 q5 t5 T! O- O
6 C4 m/ B( \* p各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
; N% _- m; u5 a$ M2 [' A- B
) V, U! q6 E3 z1 E5 O

& K/ u  U- X: Z. K7 M1. 插⼊排序
: B6 W: ~! G7 E* M. [! Q（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
2 l$ ^9 J3 x6 p5 e) V( z  u3 U
算法解释：（从小到大）


算法三个步骤：
; E# J6 Z6 x9 |9 C" `
4 @1 x7 a! k1 G" H0 q/ Q4 B- o2 ^先保留要插入的数字
往后移
插入元素
. x7 Q' u& ]( O: X8 Z/ }& c6 G# n' p
7 q( c+ E% y! r1 I5 V7 @' w6 I// 对A[]数组中共n个元素进行插入排序
3 k7 f$ Y7 b  |4 {& J5 x% dvoid InsertSort(int A[],int n){
( u0 \* u' ]4 [/ N    int i,j,temp;
    for(i=1; i<n; i++)
    {
: h7 r4 w$ w7 a( k- B0 g  h            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
        if(A<A[i-1])
0 N' \; a- p) r$ X8 I  [3 B4 V4 k( V        {           
& ~. {! W; Z( V& Z            temp=A;  //保留要插入的数字

            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪
6 e% u' w% \; u' D" L6 b; Z( H
( @2 W1 u9 Q4 z/ ]            A[j+1]=temp;//插入元素
        }
    }
}

4 D  w9 a/ m" N! J- e0 {& O2 E, W9 b1
  P. P" J& N5 D+ A2
' J! E) q5 ]) i' X3 [6 N3
# ~! G* k6 ^: m2 ~; h6 \8 W4
8 d) @( _- |5 k9 q" c# O5
/ Y! |; @* Y7 U4 w+ s, Y3 I6
2 m; C; X8 g& t( N) m7
8
9
10
% M/ `: ^, m, d8 e7 e8 h& h8 b11
8 v. [" }: f2 B5 p" u12
13
. N7 r4 v/ L# ?) y' s6 E+ l$ L14
15
# E: }8 e9 ~3 m2 i$ b  ?( N16
17
用算法再带入这个例子，进行加深理解

+ `. b( s, ?% G- b5 V
  R1 z: p3 g# C  Z. |# q. T' F( l2 s8 X带哨兵：
/ H1 ]/ t1 ]- j3 Q+ O

' d+ ~  M6 {" ?补充：对链表L进行插入排序

void InsertSort(LinkList &L){
    LNode *p=L->next, *pre;
2 X5 Z  T; Y2 L    LNode *r=p->next;
8 \1 }% Y# Y# v* W/ Y    p->next=NULL;
& W9 X& n/ l9 b* A    p=r;
2 F1 Z/ }0 o( ~. D/ a' M0 O    while(p!=NULL){
$ \# e  E6 H& l4 C* A* K4 K        r=p->next;
        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
        p->next=pre->next;
" Z  ^/ @7 g5 G/ f" y0 q% }& p" J        pre->next=p;
+ ]% G6 u9 G+ r( Z/ w# W        p=r;
4 \  @/ u5 f/ W8 J) |    }
}
) B: p  R0 S+ L: G1
! w) ~8 e3 u" H# q% ?2
3
: A$ T% U" V: l# I. Q' a  b4
5
) X4 J4 U4 Y, P" s, d( M8 V6
9 |* e' M- D0 _+ f" z/ q; s7
9 o- D8 |1 Q- }; T8
% T6 N. T/ S- m  n! E9
' K$ j! U+ v8 E' l! H8 b9 l; U10
11
7 C5 X* A0 \+ u; T0 _% i9 q12
13
14
15
时间、空间复杂度


; A7 ~2 s7 c' v: l最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
最好时间复杂度—— O(n)
' O: U0 ^3 h* I/ q" E$ d; k
最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
" o; A( J# Q4 w第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
) }5 ]$ w0 L& E; ~9 ]$ ~…
8 K* i  }& [% y) v第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)


+ U) V; l7 t$ _

- s, j. @5 ^; g: s' j: ~
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
8 u( w9 _- W6 v1 o" z. k过程：

( Z3 T9 k6 ], ~+ ~0 N7 d9 K

//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
3 H  d9 f! d8 B) ~{
/ Y) C' q/ y) Z. M; E5 d    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
    {
7 T) N: h+ j7 {; ~2 G. m+ T' F        A[0]=A; //存到A[0]
. F( H, G+ R3 B& W        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
        while(low<=high){            
, r4 W" D7 b5 F7 Y: X; ^            mid=(low+high)/2;
  C, H/ ~- {% X' O( f: E            if(A[mid]>A[0])
6 b0 _/ S5 P% I7 Q+ M! _( ]                high=mid-1;
            else
                low=mid+1;
7 W) W7 F: m; s( h" n1 Y        }
         //--------------------------------------------
3 h+ u- x0 y3 o- ~1 O5 f$ u        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];
  s, M! S  E1 b$ A8 G: A" L! i7 V
        A[high+1]=A[0];//插入
    }
}
2 @( W0 F# ~" S: M. `
8 i3 x: E: W) M/ H1
2 \( g8 Z/ Q) @: S# J4 X( E8 J# O2
3
4
5
6
; p8 E( z7 z$ S. u7
( R6 k1 x) z3 k$ e6 [8
( t, ?' ], H7 w7 N" J9
10
1 Y8 w! a0 A: ?; M11
12
13
2 b. g1 Q  B, n' E14
6 ?) O( e; d3 X! ?& t+ J9 K5 ^15
16
$ O6 P3 C5 V. q7 m& x17
+ k6 j& W  x/ K" k18
. }$ o0 A, L5 s5 o; K) F9 B19
20
21
22
23
. ~, G. a) A3 o% Z时间、空间复杂度
空间复杂度：O(1)

& l; ]* f. F3 f2 g; M  f7 t4 `【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
8 c' Y+ z) ^. a7 |' U' O

& r1 T5 M3 @  t6 p, {- ?（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

算法思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
4 N4 D( \: T8 g" _% ~5 i, z6 Z随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：

* E$ O! b, ~% u$ z* V0 m, t: A
8 X1 l# T; u' q) {# f6 S6 T: M5 _
$ W6 F5 D5 g& f3 x" w代码实现：

8 B, L" z# A+ Q4 q//从小到大
void shellSort(int* arr, int n)
$ R& f" }$ h9 b! Q{
3 d6 z# ]) F, n4 @: X! u9 F" }7 t        int gap, i, j, temp;
6 T' e0 }9 @: E  [+ w9 t        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
% |9 c. F; N+ A1 Z/ w9 U        {
            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
                if (arr < arr[i - gap])
                {
                    temp = arr;
5 A+ \' R/ z- r% E0 F  C
- f" z1 o7 a( r$ H0 t7 d- J                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];
& @6 \: ]3 G; S- F
/ \. k0 l# P: Z4 Z' @                    arr[j + gap] = temp;//插入进去
! r- @3 U. x. p- M                }
3 J  s, v; G- R% h            }
            //************************************************************************************
' B- Q# \% M9 ~% }( D; q        }
}
$ ^8 w. Z5 T3 ?: P  w8 N: l1 L! [
* x8 T7 s  _6 C' Y1
7 x9 j) w  u3 |( \+ P% ?7 b: X2
9 ?* A. {' b/ Y' c% _$ }* _5 o8 L3
4
5
6
7
8
3 _( t% ]1 \2 B: _9
6 y# }0 ]/ S& h0 E' ~5 w: b: W10
11
. q9 @3 ~( ~' Q& c12
13
2 ~% `5 E; z6 E# U14
3 r* ]4 l% n6 A15
; `4 l' E8 y+ v$ h- l+ K16
, g. ]: z4 B$ F17
# ]  C& |0 s, J& \7 O. h0 x5 C% E18
* C7 n! m' i( |19
20
+ i/ w9 V# v* e1 a) q6 i21
1 e" J5 S/ K" ], s0 f22
! [. s7 G% M6 u9 D- U23
24
$ W: L6 I4 B5 D; |, T/ H时间、空间复杂度
, n$ {# Z; P- M/ y/ ^! g空间复杂度：O(1)
9 D4 t9 I2 N9 Q$ Q
时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)

稳定性：不稳定！
" J/ C/ s" P1 V/ ~
+ a$ G/ J* w  v  r. Q& x+ Z

适⽤性：仅适⽤于顺序表，不适⽤于链表
" o; H- h  H5 p3 b
. E- R; t' f4 v0 o
) |0 n& [1 Q# M
2. 交换排序
2.1 (稳定）冒泡排序
' ^5 `4 v: X; e4 c* ]4 P/ m英文:bubble sort     (bubble 动和名词 起泡，冒泡)
* z0 y9 P. @$ U! c从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

$ ]" u/ R: H! Z9 l- a1 k4 ?( `每一轮比较会让一个最大数字沉底或者一个最小数字上浮

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
) K5 k* I& Y& U1 O8 \
实现代码：

" F- Y; c1 _/ h$ C. e//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
" p4 ]- o# K) F% L0 L- X" w{
        int temp;
+ T8 J% \9 v  a9 \6 D: A2 G        for (int i = 0; i < len - 1; ++i)//循环比较次数
; A) Z5 K; y, `$ d        {
                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
* w5 t8 O( L+ e& s6 \8 J( O' g                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
                {
) H. S, l2 ?5 f8 T4 {                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
                        {
                                //交换两个元素位置
                                temp = arr[j];
                                arr[j] = arr[j + 1];
. F+ c" ^7 M$ x                                arr[j + 1] = temp;
4 P: Y2 @# s. X! D" a# g  J                        }
                }
        }
) l! G+ V* p; d9 M! ?}

' K% b4 j: {$ M& b5 b, j6 Y  c* G1
. Y% K6 y+ S1 g2
3
9 n) i) g& z: I/ W* k' R9 Z4
5
6
% m2 h. F  X- f, T  a1 P7
# m; y6 |) u( M( x9 L+ ^8
9
7 @6 p" [4 x1 m' T10
' K7 A) G( ~) \11
. }, }( p" f6 P: M' j7 i12
( [6 ~( {; f! n: m, g13
& _8 z  Y: o( i2 ~14
8 O6 Y! ~8 J; K3 @  S! Q. Q8 l15
16
: I+ ], _% `% \! L17
" w2 D' A' m8 w18
19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
4 }/ y# W3 j5 u8 F* K
+ B* ]+ M% }7 c5 O1 {* C/ O+ r//从小到大：
1 ^; Z( z) Q  T* m3 i8 ?; B* _8 Bvoid bubble_sort(int arr[], int len)
{
        int temp;
        bool flag;
        for (int i = 0; i < len - 1; ++i)
; g- ?0 @" ^7 _3 F4 v1 s        {
            //表示本趟冒泡是否发生交换的标志
) B8 x; y' e% o# ^( V/ {& e% o) r                flag=false;
               
! G6 F0 I; [- T0 Q3 J2 b/ C6 j  r                for (int j = 0; j < len - 1 - i; ++j)
; O" |$ |/ A3 s+ D& T3 r                {
                        if (arr[j] > arr[j + 1])//稳定的原因
* k1 d. T) i2 J) e                        {
! Q9 z. u+ E( r% r+ b. c                                temp = arr[j];
                                arr[j] = arr[j + 1];
3 Q% j% Q$ \2 k0 T- U) z: j, M% Q' f                                arr[j + 1] = temp;
1 a2 I' g+ z; Q, S  o7 E' p                                //有发生交换
0 T: I4 e! M! R( X  y                                flag=true;
                        }
1 W$ `; S0 C; Z* y                }//for
               
! H1 E/ t  [: x                //本趟遍历后没有发生交换，说明表已经有序
                if(flag==false)return;【1】
8 h% w. p( W/ W1 p: N! v$ \        }//for
3 U. a! n$ k3 ]8 C8 N% B}
+ {1 J$ v1 F4 q  {7 D
+ U2 M% g6 P6 S* B% s/ s1
& g6 Y% I. W' L0 f2
3
* Q' f6 |9 l- u5 Y0 k4
5
6
+ y* b3 y* q7 b1 ]% j2 G7
5 U+ H" H& o% B1 \, G8
9
10
4 J& F" h0 z# @8 f1 C& Y7 V) B/ C. y11
4 c4 @8 t+ ^6 R* L) H: k12
: n0 [& A  s' Z: t3 }13
0 r, V9 D) G" p* k; e$ H- t14
+ H7 ?" h( w4 ?15
0 u7 x1 ?6 M  j: Y8 x: x' ^# k16
. S7 M( M; _/ w, d( R17
18
0 ?, ?) k! N# c- K& _( s# [19
20
21
22
23
24
, D$ d, c( X! q. x25
26
时间、空间复杂度

适用性：冒泡排序可以用于顺序表、链表
* r% D/ T8 K- E0 h6 r# {  O
4 W4 V! f* J, h; X8 a/ n
$ L8 D( S5 u& x; A1 _, [
/ P; C0 Q9 ?8 y9 l
5 `! ~/ L9 h4 A2 [0 a) Y  O4 J2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
" e' X1 a) p  Y8 l9 e算法思想：
4 x' O4 A# s( Y- x  g  m在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
- L) q; {. t. f( L6 W8 E再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

0 h) V& {6 W* s然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

/ Z$ Y2 \  w0 W9 ?& ?划分的过程：
0 |+ Y$ \, l/ T; H. U) A; U
初始状态：取首元素为pivot，定义low，high指针
; H5 d$ C2 q: L
首元素为49
high指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置
, x( I/ G# A' n


0 R: T6 d8 ?$ k6 w3 l3 x# U
) i8 i5 v% ~  I) I3 q: D5 u
) `) E. x" v! e1 b' t! i6 B9 c// 用第一个元素将数组A[]划分为两个部分
7 m4 X" A1 D% c6 s$ fint Partition(int A[], int low, int high){
        //取首元素为pivot
    int pivot = A[low];

    while(low<high)
    {
            //先是high开始向左移动
% ]1 K0 Q  d: ]8 v  k0 o6 b        while(low<high && A[high]>=pivot)
            --high;
% p% n' {2 x9 s" B6 V        A[low] = A[high];

/ [5 B7 f! K- S" ]) F% g        //随后low向右移动
        while(low<high && A[low]<=pivot)
            ++low;
7 }# c& X6 O8 B8 z- z5 Z# m        A[high] = A[low];
    }

1 E0 e& R" u" `$ Z/ ]! W! @8 H8 t    //low=high的位置，即pivot放在的位置
    A[low] = pivot;

    return low;
}

& p& t. u# u: Q- ?$ Y% Q: ]// 对A[]数组的low到high进行快速排序
void QuickSort(int A[], int low, int high){
    if(low<high){
        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
8 {* Z+ i) e  U5 {% i" s4 F    }
}

: ]6 J# q7 I- B* r: Z* M! P* i1
" Y% i5 i, E; v! o0 ^/ |# C2
& ~# @/ B- A6 S( \$ k2 u3 E3
* d5 F6 ]9 Y1 [# [0 B& W% p! F" U4
5
6
6 I. c1 t8 E- i3 \' m5 j' m7
8
" D/ J! j& @9 |, u9
; A- q; c* @3 u- ^! R+ B0 i10
1 Y' @7 g& p" _. c: L/ D11
3 d% U1 Y& G( L+ n* _* [12
. j/ Q1 Q- P- U+ \) D) Z13
% t  J( T7 t6 e2 E5 N- h14
15
. M+ Z: B8 M" y9 W: }8 _16
17
18
! D' m0 P0 q6 L& _/ ^19
20
21
. m. {7 T  @/ \! D1 p, x22
; m* m4 \- f- x( K23
. W1 d; ?* a: U4 [# c0 r. E  F( T24
9 ^7 m' W& J8 e% h25
26
$ ~# M0 Q( s& C$ o3 d% i27
28
29
* m5 S$ n) u+ j30
0 M* d& k& I* e$ `% T  _( {, X31
32
时间、空间复杂度

, L# Q3 n" }8 w* Y
把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
) m* t9 ^' Z5 U2 \最坏时间复杂度=O(n2)
5 n' C) K. \- o. W9 y( L7 ]- M平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

# D9 `% X9 G& a2 [空间复杂度=O(递归层数)
; U+ ~& m; Y# h! }' p最好空间复杂度=O(log2n)
6 _) _- I% I4 R0 M; H  d最坏空间复杂度=O(n)

, ]$ _: R3 P. ~/ M/ ]最坏的情况



⽐较好的情况

7 r$ D9 l) v4 Q; z: A
6 j: t: W& _0 L) v0 f9 J( m- M
2 x" o/ c1 Y7 Q* U+ Z" }1 r不稳定的原因：
; m2 p: Y) w' |, k  U3 v/ j$ E

) f+ `; q/ t) z8 _% V5 y- n: W/ r
" L% M' r6 F4 c6 D+ d
% G" w0 o, w- f0 b
3.选择排序
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

3.1 （不稳定）简单选择排序
( a6 s. |/ Y2 s: [算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
. a7 _3 v  U$ [4 `3 s" g# u# A

2 Z1 B3 W' X- L7 O1 z
// 交换a和b的值
6 c/ w- Z5 |' [% q( k- y4 `void swap(int &a, int &b){
* ~+ x: M' J! q5 k  }) f    int temp = a;
    a = b;
    b = temp;
/ I5 V( W& S( x}
' d* ^7 S7 {* k. L$ l1 l& L% w
1 n3 }5 y; \  A( r. A// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
{
# r2 a9 H. i, N        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
    {                 
        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
! e3 x& W8 n  D            if(A[j]<A[min])
- [# S: F4 ~# k& q6 }* H                min = j;
# l9 ~9 [. Z  G: d$ `' w( r; S( H2 [        }
+ N$ J; x5 v/ Q& \( Y1 A+ y3 |$ l' k        if(min!=i)                     
1 ?# \7 E3 y! d  p; e            swap(A, A[min]);
+ y1 ?. G  q6 `" A    }
}

1
; s, I+ l+ l7 \) I( {2
4 d( I. @0 v% D7 z/ U3
4 h5 j6 j4 l# l- J4
5
6
9 a( Z; x; x: H3 R  X# \7
7 I1 z$ ^9 {: b8 d8
! z+ D' v/ e0 U" Y$ G9
7 q' T. r1 I+ \9 B9 m7 Q, w$ }10
* e$ g# [2 O8 J, u9 f" e11
  [, f$ `6 O' L4 u% r0 E9 ^" O12
13
  J# {  x: [8 C6 e) P14
15
16
% i! X2 }7 D- Q0 D; P17
; Y5 T9 d+ A( J' C18
19
( ]! e* w& T' _* y% c; d( M5 H9 A20
21
/ {, M2 D" @& u22
补充：对链表进行简单选择排序

void selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
9 S: }& o7 s: U8 O! Y& Z& F! G. L    L=NULL;
+ }$ l/ M' f$ E& y- _    while(h!=NULL){
        p=s=h; q=r=NULL;
        while(p!=NULL){
; F( W% \3 Q1 D7 M            if(p->data>s->data){
+ E; ]# Q. v/ d' E+ `" y7 q$ {                s=p; r=q;
            }
            q=p; p=p->next;
        }
2 |) B1 k* F( o# k& r( p        if(s==h)
            h=h->next;
4 u9 s7 x+ H+ X+ M( i        else
            r->next=s->next;
$ e7 X' s9 g0 y) b: \6 k        s->next=L; L=s;
3 m4 k5 m* q- `' A0 m    }
! T. r2 S1 `) b+ H$ w}
, T# N3 |5 v: }1 y3 X3 r6 l) I
1
4 u- T# K; _- w. k$ U2
3
. r2 a; O! M# H4 {3 Y4
/ v- i% c$ c% z: D; @$ R0 c2 h: g5
  n( K3 N3 o8 p' d) n6
7
# l" C7 x: f. C" H8
9
10
2 R+ V$ d) h7 N7 S1 x11
12
2 V: n2 ]! l8 I, e+ k( A! b, g13
1 s6 A7 c# O$ e" W- L% w14
8 a0 _" M/ ~, m1 J# L5 _& h& i15
2 r- N& X; d  k; \16
17
18
" _9 I: i, o, L3 ?1 h1 H/ M5 J时间、空间复杂度

  F' x2 u  Y, z3 @# R
( B& t4 ]. T0 }7 U1 F

! X3 X* T3 Z5 _适用性：适用于顺序存储和链式存储的线性表。
5 c( p, K0 l' u

' Y' |* v4 ~1 ^$ N$ T( a
9 k& o) e: q& Q2 T+ k+ ~3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
7 X. h# b  S: S, J# H每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
* e( q4 i& l6 b
6 @( v7 R+ l+ \$ C+ K) [, I  O) v# Q0 y
) u9 Y9 _& }1 X& D1 z! n
; j; q* q! b3 h' b" Z- \即：
- k# ]) F9 @7 w( P- V若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
; ^0 h" e0 P  o. O( a- P若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）
7 ?% J- J0 Q1 l, X/ w
  H# I  T  P& y% P  b' E, Z② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
思路：
: `& s4 J3 J0 I& q0 _把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
5 e; r2 `! g: N5 Q5 V
7 Y* y+ ~; {4 M" h: G" ~在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

6 X  e0 _# o, P1 ?' C过程例子：
' r* v  c; `; \% r

5 P3 _0 l' e2 z. A) ^" I. j% o/ ^: ?
6 S4 u2 X% J1 z, {5 [) c. z建⽴⼤根堆（代码）：
: [: L4 ?" M2 _# b
/ o$ B, N2 f, I' c2 D* w! v

// 对初始序列建立大根堆
+ h3 Y5 H" B7 avoid BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
! f: S$ D# I( p4 s$ ], }}
7 Z; n$ a; e6 ^+ a7 u: T2 W. B
// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
2 r5 R: x# i8 C; T2 w9 q        if(i<len && A<A[i+1])       
* L7 O% U' r! [1 l1 S            i++;
        if(A[0] >= A)
            break;
/ E6 a  ]( N9 `+ n" ]( D! A( M8 K1 E        else{
3 B  _* @: d! m7 k, a8 n            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
        }
    }
3 n9 \" G( H$ e5 W" D    A[k] = A[0]
9 z* i; q& j2 Y; [( v}
. Y- Y7 V( P7 Z2 ^9 S- O
, V. J$ M5 @! x; c) N1
! f7 F' V8 [( Z; g9 Y" g& X8 a2
3
4
5
6
7
5 j+ s" s6 `. N( ^1 X8
9
10
11
12
& _4 K6 E8 o4 p13
14
2 Q* @# m( P* d; p( i! J, s3 b15
' t! C  _; z+ C: b% {- K16
2 y) M/ o* p! \9 W  \* B, e7 ~7 m17
2 @) |9 V$ w/ Z( I% F( s/ }/ i9 S18
19
20
+ r8 Z$ M1 n4 _( H21
& m/ t, X1 |) ~* U9 O③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
+ ^6 X# B% a# \, o& r$ Q# x选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
+ r/ c! x3 E/ `2 }: O
6 R$ ~, S( x" D! Z( z堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

过程：

8 Z; [, W, Q+ U2 S9 m) u. n( ~// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
" x+ ?' w# q+ d    a = b;
2 _& T: S) |0 Z    b = temp;
}

, q) g& [7 J6 L+ S// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
8 j  I0 ]: O, a8 F        //初始建立大根堆
    BuildMaxHeap(A, len);                

    //n-1趟的交换和建堆过程
* Q' p3 @( T  n" G. |7 t: s* Z    for(int i=len; i>1; i--)
    {             
" @# ]5 \' A( F; D        swap(A, A[1]);
        HeadAdjust(A,1,i-1);
5 ]/ w3 L5 S' V; k7 ?5 A    }
& i7 g$ t0 h% o$ R7 x! {% i}
# ]* }8 ~% T! p3 v& e9 P
1
9 a; N8 d* P% p. Y- r0 W2
3
4
( q" z/ N7 E9 x2 g5
' F2 _" e* Q& ~! h+ h! G' j6
' H- m+ c& C0 l, M+ _7
  t" c3 e! b/ y) {3 `8
9
' A5 a7 {4 e, o* ~1 m* E. b+ y10
: L; m  t" n6 p4 ]0 u! ^( d11
12
( a. L3 a2 ]! a13
) T4 J' b3 [6 `! |9 k, F/ \& \( }14
15
16
17
18
19
" \% T8 x8 I% ?! q; |时间、空间复杂度
. W8 W7 v" s6 w建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
6 B  ^5 w1 k* q, {6 B+ X故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

9 \5 z' G% D0 L9 O! N4 x9 |空间复杂度 = O(1)
9 ]$ q7 V0 J+ V: ~/ I7 Z5 H
结论：堆排序是不稳定的

1 x4 M( ^2 F* C; N& n. e$ f
④ 补充：在堆中插⼊新元素
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌
% T" b' Z# A; r( U4 @/ i
; ~- W, `. h8 d; U, }. @* @7 ~

⑤ 补充：在堆中删除元素
9 a) T3 [3 s. _& }7 {& w( z被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌

9 _4 y; a# \1 t- b5 e( H7 A* p



! Q$ X9 u. C) \! Q0 _1 `+ D4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个
% J" W6 L" U0 R! v1 X
① 明白什么是“2路”归并？——就是“⼆合⼀”

& q( R- C8 o( u' h2 V多路归并：


② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

. M. l! _" c" B" Q& N③递归进行分治思想【MergeSort(int A[], int low, int high)】

7 R0 A) H' H! V
④ 总实现代码
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
/ j* O9 \* p* W7 M5 D
// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
$ p: v$ l' m; [5 l" u5 r7 Lvoid Merge(int A[], int low, int mid, int high){
    int i,j,k;
    for(k=low; k<=high; k++)
        B[k]=A[k];
    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
8 _! T3 V: @  ^8 J        if(B<=B[j])
+ |# I$ @. f( T            A[k]=B[i++];
        else
1 z" w" o" j' z+ p+ X- @            A[k]=B[j++];
. N+ P1 s, l9 o1 c8 S1 c  p5 b    }
    while(i<=mid)
        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
+ n2 [. _. u# y7 D* T5 Z}
7 A' e( A0 _% h7 Y. |3 o$ N

5 ?. i6 H$ O$ _// 递归操作（使用了分治法思想）
void MergeSort(int A[], int low, int high){
6 u* z- Q! z; W4 c0 n    if(low<high){
        int mid = (low+high)/2;
  x4 W2 g$ h8 _" S' b9 N, |        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
    }
7 d6 M( y4 I' u7 l; [}
( y- ]7 b9 a2 e0 s9 i& i$ i
0 K7 k! U$ C7 U1 @1
2
3
4
  J  G+ f3 H+ P) t5
6
7
8
9
10
11
, q" K9 K7 x4 {- t; T12
13
14
15
  O3 q' k1 q7 X- `16
  w; p7 q- w7 k' H) d1 j. B17
18
19
0 |4 D3 @8 B4 @20
21
0 ]) J# U) q, C2 b, N/ @$ B) W22
23
" w# g& M7 w7 D9 D9 a: Q24
* a% U+ @+ J. J/ |+ n- X: M( D25
26
8 o& }( d4 \7 \1 E( L8 s. ?) V27
28
& H3 `, o# J. F; z* ?; @1 C. i7 m29
30
: z$ X: F6 w' a0 @时间、空间复杂度

; Z( O. z$ I# `4 X' H

' F3 d* |( a4 e' F- U8 _
5. 基数排序
( I# ?/ A# y' D2 Z5 I直接看课本的过程图来理解P352
& M7 C8 R( Y! d/ M8 X% g
再看这个例子：
$ p8 p& o9 i: z1 E

算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
; X# f1 }1 o5 D! a* q) W( }③ 数据元素个数n较大。
算法效率分析：
( C1 x) T- L$ \: \7 u% w9 C时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
稳定性：稳定。
2 K& u1 {' w) i' j

8 s8 m$ n+ G. |/ v" T2 ?# X/ L内部排序算法总结

————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969
8 E) G' y% U& `. j