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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
排序
1. 插⼊排序
6 Q: o  J  I9 `5 G. A% {0 X/ q- x（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
: R; u* p# j0 C6 z0 O时间、空间复杂度
. d7 v+ Q/ j+ `6 Q6 _（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
! N. q7 w1 Z. A2 p8 J: W, e时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
3 {8 L' }( Z/ o- F1 i$ J7 N9 W时间、空间复杂度
2. 交换排序
* V% b6 ^. W: c' B2 {9 B9 Y# U+ h: `2.1 (稳定）冒泡排序
时间、空间复杂度
0 A& A( ]3 @5 }% m9 ?2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
3.选择排序
: F5 b0 C. E% p' U9 h5 p# \3.1 （不稳定）简单选择排序
时间、空间复杂度
3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
0 A2 G# D: U1 N$ i② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
4 Y0 [, q2 ]* c9 h1 w③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
0 x0 `* z9 k' |' a2 L1 k! X时间、空间复杂度
8 T" i$ H, x' Q8 @+ S( N4 w④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
4 l: Y7 Q5 {" H$ b0 m" Y0 l4. （稳定）归并排序
% E& A  R# Q7 A+ F7 m% i1 \; P① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
3 Z6 _! C. ?' t4 ]2 D④ 总实现代码
7 S4 P4 U7 k" H) H) \2 o时间、空间复杂度
5. 基数排序
内部排序算法总结
排序
; z" @& T% \9 C: l# C0 ~! f$ c排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

排序算法的评价指标：时间复杂度、空间复杂度、稳定性。

9 }  D* a4 C* q: \9 d8 e$ j1 o算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。


3 l  d' s9 X# f8 A! {1 t排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
9 q/ u% `% T! M" W! G外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
3 m& T2 r/ U  ?& T' I
* ^5 W, d7 D2 q1 q8 Z- d
# `- P. g  I5 C- a* x$ ^7 b  d# D/ K
* ?. }" e8 V, J1 Z3 o4 v) Z1. 插⼊排序
* Q: L- y7 ?# p4 G（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
5 y0 k2 F) L. Z/ W: g% ~
算法解释：（从小到大）
; J$ x2 m( @- n. b; V! Z
" I4 g7 I/ E9 g7 ^  h% ^2 T
算法三个步骤：
9 M7 \$ t) n% M% |0 u  t3 l1 u) r: w
先保留要插入的数字
4 t# d8 K/ A; _! `/ Z) B往后移
插入元素

// 对A[]数组中共n个元素进行插入排序
9 ?# w( O- [3 gvoid InsertSort(int A[],int n){
    int i,j,temp;
& k7 f7 g( g; ~+ |    for(i=1; i<n; i++)
    {
( ?) O! X, P  e! h4 [  r            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
& B( r% i# i2 }( S$ M        if(A<A[i-1])
        {           
            temp=A;  //保留要插入的数字
2 @; @7 e6 }, Y  h! t% U6 y
+ Q; n# M2 X! _, l9 d$ ?            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪
. X* h9 ^! F8 ]+ j! V
2 e0 k2 K2 M$ W  I. s            A[j+1]=temp;//插入元素
* f6 p) B  h1 Y, M( d$ Z        }
    }
}
" c1 b0 r3 S) S7 Q
; b5 x! ~7 K. Q1 z* z( |1
6 t# i; `! Y) x* ~% }; T2
; j" E4 y; T* x% A6 K) B& E3
4
; ^2 Q; Q' X2 I$ n0 a; K5
# o: R" ^1 s: C, d9 e6
7
8
& M( H, X% G1 B/ E9
10
, _8 j3 m& \4 R, F5 l+ S/ V$ q11
5 z8 F1 H' v8 J0 {: ~1 {12
13
14
' ~$ e8 j7 T2 P15
" Q! t! q) c/ g/ L" Y  j0 t6 U16
17
用算法再带入这个例子，进行加深理解


带哨兵：
4 b( j7 b1 ?$ Y3 s: z2 V

4 l0 j5 [# L9 y补充：对链表L进行插入排序

void InsertSort(LinkList &L){
4 R+ q* ?, [) ^4 N$ Z9 g9 A1 l    LNode *p=L->next, *pre;
7 b3 E. j/ l1 X. r9 M4 H$ d    LNode *r=p->next;
    p->next=NULL;
# N- j% R3 w4 U    p=r;
    while(p!=NULL){
        r=p->next;
1 \# u1 G7 u% z$ D6 v& z* Y        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
        p->next=pre->next;
        pre->next=p;
        p=r;
    }
}
1
3 y3 s2 n9 U! l" S5 \) ?2
3
4
5
" _' X) u" K% n' |" `6
% n5 U' u4 V6 A( B' H4 u) q7
8
* j3 `9 `! D2 ]# p9
10
1 g  T! I' g5 l' B11
12
13
14
5 {* z4 i5 ]  \8 U15
% c- m5 N. g. Q1 \$ V时间、空间复杂度
+ j" A' T1 Y7 W9 Q

6 b# i, ~/ i& X最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
最好时间复杂度—— O(n)

# T( r4 D# L) r, Q$ C9 c5 t$ v最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
: E0 |- C; z% Z5 N2 Q/ h; ^4 r第2趟：对⽐关键字3次，移动元素4次
- \8 Y" `/ S; L  X6 @4 K…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
2 c6 W$ H4 {. ^. F! ^最坏时间复杂度——O(n2)
0 i3 O' K" ^" M% N

/ \4 r3 J" v2 @2 W


（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
; W* L( U- b5 [过程：

$ A( o: Z) H, M* g
' |1 r' W& ~7 e
//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
% I1 ~# [2 }& }, b9 C{
$ Q) g; G0 j7 z    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
7 C' x9 W) x# }    {
/ l0 V) k- @8 v0 Z        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
        while(low<=high){            
            mid=(low+high)/2;
            if(A[mid]>A[0])
, y3 r/ r0 G2 e/ {8 J                high=mid-1;
2 o6 o6 b' a) m" [+ d" q            else
! \, R( K  T% l2 b6 G5 ~. V                low=mid+1;
2 i/ i# _" D) P) D2 S$ P5 L; w& v        }
8 m0 X; F" p; p' R, w         //--------------------------------------------
% x' g* y4 d: a7 G        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];

        A[high+1]=A[0];//插入
    }
6 {* U4 X2 ?' {. V* }" U, q}

1
; E) q5 Y0 ~$ i5 O9 h' w, Y6 p% H2
3
% T: d+ Z# v( `3 r: u6 y* ~3 E4
5
6
2 y# Z4 o' T  r- T6 l# P7
: X& H$ R9 T5 J' M% \0 x& c8
9
4 g. l& p6 R, l5 I) {10
/ s- V4 `) Q* R' i6 Y11
. O, E2 Y7 @! _0 f, W( c1 z6 C12
0 s: w2 d  `% u9 L7 R# C' m13
14
& ]4 F8 j  C3 l+ l: W! m15
/ T3 B2 B- _! Z, O16
2 o5 y0 @2 X0 x7 G8 Q0 \4 |17
" [& P; }; g6 ~4 ~18
0 ^1 O! E+ \$ r1 o7 W+ Y# I" }/ d& _19
: l7 l* Y/ s2 N( i% y3 y20
21
8 z& W0 g! T6 X22
23
时间、空间复杂度
空间复杂度：O(1)

【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)


（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
/ J& @  j4 @# u4 b; ^# `7 Q
算法思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
0 v. C7 s8 ?1 L* {8 y2 I图解：
! x- `% x, Y9 U9 |- A$ `


/ z/ [3 v4 m3 U2 K$ A代码实现：
* C0 f) r& n; h8 O9 _; O$ Y! ]  {- Z" K
) V. [" t6 N; k, s5 `$ t; Y( o//从小到大
& T4 a7 w  Z  Z9 }# yvoid shellSort(int* arr, int n)
{
+ o& W; B$ ^: c# ]3 R        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
% V$ u) W: K7 \6 k* |" k' D        for (gap = n / 2; gap >= 1; gap = gap / 2)
  A% z4 u8 A9 Y( T/ N) P        {
# x5 S$ C' e' d: e# R2 t            //**********************************直接插入排序（只是步长改变）**************************************************
1 r/ r; h0 O$ b' Y" G# |/ l, Y            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
9 _( H4 l5 @% Q' E% }: k            {
                if (arr < arr[i - gap])
* ^6 q. D6 c5 N. \* S, @2 d7 g2 _                {
8 A/ @* _+ J2 r7 x6 N                    temp = arr;
* M/ L% F* i" Z
( S9 g% P- O1 w* p  t7 _9 _3 ^                    //后移
+ a  [$ j, M8 V$ [( S( I+ l) C                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
+ U0 ^! n8 f9 n                        arr[j + gap] = arr[j];
: ^* v3 m2 s2 e! Z6 p) J
/ Z) V4 Z" {, J5 C% ]# `/ R6 k3 u                    arr[j + gap] = temp;//插入进去
                }
            }
            //************************************************************************************
        }
}

3 U: X& e) }; H0 P& Z+ y5 B: e1
9 s( S: d8 t. ~+ }+ b, m( G3 i2
& @7 ^7 C; t& P1 R# j. Q: ]3
6 E/ C) G' n- g! o% N4 ?4
, }- l. p! M! |) ~5
6
7
) e( ?7 }& t5 T6 p0 q8
. Q# b3 B4 P6 g: W4 o: l9
10
# y6 q- {1 Y4 V# a4 S& T11
: \: k3 l5 A  j4 s12
/ x, W) }# q; |# s6 I; A13
14
  t" v* {8 @5 A- O0 t( K15
16
17
# E* w. y9 h- K& v: c' r18
# u* [2 [: j% n19
20
21
% V; Z2 T) g( W4 u" Z) f+ `* a22
23
5 D3 U! U! x! y6 s* v24
  ?% W$ n2 M& l% \5 c时间、空间复杂度
, o' Q8 R, p- e( v8 i空间复杂度：O(1)
9 u$ B* Y) t& a5 W9 G- D
时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)

稳定性：不稳定！
3 r* J/ K# b0 X) f1 d
* F  a0 i. y8 V! y% X
/ J! R4 |( x: Z+ f) _: ^
. l. r9 k' R+ `) H; [适⽤性：仅适⽤于顺序表，不适⽤于链表
0 l( X" }8 K. e. Z# F, s4 u; @. c% V0 B( m
# b4 d2 q5 t  h! L4 k

2. 交换排序
- [/ |' Y+ m5 a, R9 Y& \2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
- e: ?  N) B' N从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

每一轮比较会让一个最大数字沉底或者一个最小数字上浮
( A  R5 d; O) P* a, g6 p% B& F' B
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

实现代码：
* M7 g; l* d% P  A; h- M, E
! r6 E6 B/ c( j# B* g8 v' Z; o- R//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
{
" \3 G6 D/ y# n        int temp;
' Y$ D' _2 C6 |2 E' `5 O, |, ?* c        for (int i = 0; i < len - 1; ++i)//循环比较次数
+ [' ?2 P+ K9 B        {
! |  y: }! C/ R% s! ~                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
1 V8 e8 u9 h* M4 w! `* |6 _4 S                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
                {
$ f  S6 q6 h, X& \/ J* z6 v                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
                        {
                                //交换两个元素位置
5 a! E% k9 U. R- Z/ z$ {                                temp = arr[j];
! {) T. ~3 ]$ b5 q                                arr[j] = arr[j + 1];
" _+ M2 f4 ^7 ]$ v7 s6 t                                arr[j + 1] = temp;
0 V  D! {& N- \& c                        }
                }
3 |( p& Y" E. Z& x        }
, q  ]7 p/ z* @. c& h}

1
2
3
4
5
6
7
8
9
10
1 e. U' ^$ N6 f. k: s) I11
! ]7 C2 \+ a$ `12
13
( H# @( t  `/ a! e7 D# H14
15
16
# e! U6 F" |+ u' E9 ?17
' h1 m1 U4 F) x3 ?18
; N8 L" t/ k% j: e3 M" g! a, S19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
6 E7 M( ]8 h+ _; F7 V
+ d  v- g  s. U* ^2 F1 ~//从小到大：
void bubble_sort(int arr[], int len)
9 F9 t0 O9 H* @3 l1 R, E2 I5 ~{
        int temp;
" b3 a0 C3 J2 A+ A3 ~; o1 @        bool flag;
$ o$ e% x, ?1 i9 f6 D. ]  E        for (int i = 0; i < len - 1; ++i)
/ V; C+ U! ~" P: S: E# c        {
" R* B, s4 T4 P0 N) a            //表示本趟冒泡是否发生交换的标志
, Z$ ?( J: g+ D$ c9 y) K+ a! k                flag=false;
% `  u3 _5 x5 K" V. R. R" p               
                for (int j = 0; j < len - 1 - i; ++j)
( P4 ]! N1 Q8 _, r# Q# m. w                {
                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
, v! }' [- _0 `                                temp = arr[j];
# R  L- k3 w, j$ t                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
1 ?/ ^4 Z& r' _8 w) |                                //有发生交换
' v6 P# {, S8 @4 D1 l                                flag=true;
                        }
2 J- V( G8 n( G4 O2 d! }0 d                }//for
               
                //本趟遍历后没有发生交换，说明表已经有序
, D) ?4 y% d! w; C/ K                if(flag==false)return;【1】
        }//for
}

1
" U3 J. h' A) ]0 y, N" v* f2
3
6 E  F1 T7 f. @  S/ X! v$ U4
6 _+ ]/ N! f1 c$ D9 r5
6
7
8
6 K7 w1 l' x+ u& |6 {) ?5 x& i8 c9
10
11
12
, R1 g' z1 N6 e- z- k13
14
) ?) ?" w+ q4 e15
16
17
) e2 R! `) V, }" M18
19
: J* J" j! A8 C+ F20
21
$ A( A, t' H2 q# c/ e/ ]8 F22
1 `- B, y  r' _% u- I23
2 c8 t1 y6 t% I; c0 h8 \24
! }7 c! ?; u  c25
5 L" J  }) x( O6 Q2 T26
$ E* ?- y- ^- ~5 E- P* T9 a时间、空间复杂度

适用性：冒泡排序可以用于顺序表、链表


2 o  d9 F' o; t: w2 a8 i- l2 j

) i* T8 ~& m. I5 q4 U3 ]2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
! l* f" Z! {- M* d5 G' j通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
7 t# o- \6 e+ h使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
& g$ o' y5 @; B; z$ ^
, d# k- {! T3 h8 X& }3 g  e5 R, B5 ?然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

* r+ ~/ A$ l8 Y! ?, t+ B  O划分的过程：

初始状态：取首元素为pivot，定义low，high指针

首元素为49
high指针指向的数据小于49，就放在low指向的位置
$ v2 h% [2 G4 ]  f4 Alow指针指向的数据大于49，就放在high指向的位置




9 N! M. Z2 S3 A; Y, V% g
// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
0 g  r/ D; U) P" u/ M+ z        //取首元素为pivot
    int pivot = A[low];

2 [( j( L0 [& _3 H    while(low<high)
. i0 t8 H; \( ]$ W4 W1 M' p    {
, L  J# m1 C: ]! W" ]            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
            --high;
        A[low] = A[high];
  ?4 R) S2 d! ~
        //随后low向右移动
2 T, x. i! w9 G' C4 n# ]        while(low<high && A[low]<=pivot)
6 V, M, P' f( D* p( i/ r            ++low;
        A[high] = A[low];
    }

' {0 V" y& j9 i6 C* f! c    //low=high的位置，即pivot放在的位置
* D1 V% m& j- `$ E; k0 W    A[low] = pivot;
' ?# R- J  I* }2 w( e$ \
    return low;
8 L$ B0 H7 ^) L}
) T& W! c3 J( _  J4 I1 u
4 `0 W" ^. k& d9 t6 e// 对A[]数组的low到high进行快速排序
void QuickSort(int A[], int low, int high){
    if(low<high){
1 h% O# C' ?& h" z3 E2 t        int pivotpos = Partition(A, low, high);  //划分
' G7 |7 C' a# D, x        QuickSort(A, low, pivotpos - 1);
% E4 t; E7 G( G  {( J0 J        QuickSort(A, pivotpos + 1, high);
) N0 F- K5 C/ P    }
- j8 j" t" X* k4 u! K}

0 e8 {( t6 N$ [' J1
2
3
4
. Q8 M" n# s, B5
6
7
, p, S) W3 }, ~, u0 s8
9 E; s* B1 z8 ?; b: M. I! t# X9
3 r4 p3 c# B" `* b- b. W# ~+ p10
. d% t' K% [% [$ C& _11
# [8 S5 ?. B+ d) E- a6 K12
13
14
1 M3 G) k+ g- Y/ r3 f) A: D* ~. H8 F15
16
2 B) d6 d9 o  {$ i* i% o17
18
! {9 B. R; N/ P3 M9 k19
5 s" r; a/ ?- i& F0 r" d1 r2 T20
2 t+ Y7 \2 l$ g( S  j21
22
7 Z/ c, I+ e: w2 a3 L* M& C23
24
25
26
; k9 C/ H3 Z5 J* m2 ?& i! w27
28
( @6 l6 F4 X+ i# g0 u) d9 i29
30
. n& y9 {% N  b3 X2 L) o; \31
, n8 C+ {- ^5 }# f3 F32
时间、空间复杂度

3 U, T2 p8 f4 f* Z" z7 b5 u
  f; J3 B( o( r" h( z* l把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
& Z8 T7 |1 ^( f
n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

时间复杂度=O(n*递归层数)
0 a* [8 a: z9 J( O9 g$ W最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法
7 N3 T8 t- {0 T; C& I
& ~& s) C  x) ~# v' ]- ~3 {  J, D空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)
. o# ], k) P7 J6 y( B
# C9 N7 |) O, R2 a: F最坏的情况
1 B' a) E5 W: j$ J


4 V' Z1 k; n9 y0 P& L& r0 H- u+ d6 }⽐较好的情况
& t3 b8 t+ {$ r% `0 f

, O6 Q; b9 D, u1 [% D
不稳定的原因：
. L/ g9 _( i% W6 y" V. Q  \- Z8 x
: L8 v* q6 Z" l( u
% P* C) J5 {) g% i
+ w# y+ X! r! B, G8 T  z/ Y

3.选择排序
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

1 M" j( P; Z7 n9 h/ p" J! l7 [3.1 （不稳定）简单选择排序
' j- p% p( Y: [7 a' \& }算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
: P8 d8 a# M- r/ B; T3 w8 e0 H


7 q3 d* A" M/ K! n2 F6 h1 e! g( N" A// 交换a和b的值
+ S/ ~8 L# ]5 j9 c# y) |void swap(int &a, int &b){
! G9 W7 ?8 g" C3 r1 |    int temp = a;
    a = b;
    b = temp;
' h% M; d8 c( Y1 o  N}
9 r5 O2 A. L1 y) X5 f$ n8 V
// 对A[]数组共n个元素进行选择排序
8 u2 x; G: T  T- J: \1 W$ zvoid SelectSort(int A[], int n)
8 _; \& V+ p3 K$ {{
' E; `9 |. ~4 u1 j: C- L2 m        //一共进行n-1趟，i指向待排序序列中第一个元素
, y; y7 \: V1 f2 L$ l    for(int i=0; i<n-1; i++)
    {                 
        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
                min = j;
        }
7 H5 L/ h2 S" c/ u) Q        if(min!=i)                     
5 G4 q- I8 H; t            swap(A, A[min]);
1 ?7 |: R& Y. T    }
}
1 ~* S  m+ b! a
1
, u2 {% o3 e7 T4 f- A2
3
4 ?. F. @1 @' y: G& W5 E6 h  c4
5 C" o; f& L) Z5
6
7
5 u& }; n* `$ @  w, h; g8
/ W$ |+ q1 R/ w7 k! O9
6 d" a- C: a& {10
% e  r# D" A) H( t11
12
3 b! P9 V! g" i* F! p13
14
8 n% _+ I$ @, m15
16
17
5 s" }9 D! w; l1 @18
: z8 \6 a' T, y; Q% V19
20
5 i1 V: f$ m$ x" L# B* r5 H/ F21
- m2 w7 Q: _+ X* Z: c( e0 I! H22
8 O* C  |9 K7 G) i! B补充：对链表进行简单选择排序

% n+ A; {6 }) M2 U5 ivoid selectSort(LinkList &L){
* v9 s8 E3 E5 E' t6 l    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
    while(h!=NULL){
        p=s=h; q=r=NULL;
; j( q8 c: M$ I) @        while(p!=NULL){
$ e/ W, q& ^/ o& ]; U2 B- C            if(p->data>s->data){
                s=p; r=q;
            }
( s4 ]& J) Y/ x1 L- c4 Y& Z- s            q=p; p=p->next;
( t9 k" F4 x* S7 v$ Y        }
        if(s==h)
            h=h->next;
        else
. x: p3 S; J8 m; G' z" f            r->next=s->next;
- u8 b' r, C2 k1 y8 {/ V+ t: ~        s->next=L; L=s;
9 [& l9 _7 ?# Y    }
9 e8 X% x& |& {) v# D: g}

1
2
# l9 N/ B, T9 d1 ?! ?* G3
1 k* S- V0 q+ ^4
2 o! _, W) V$ _) i5
6
- Z3 ]' S) L: I" }9 y; U/ E7
8
& T6 l3 u9 N, |9
$ m' J* J& ]# x9 w) \: E1 L  c10
9 b& s- U% @3 p/ _9 L- w8 S11
12
13
14
15
0 k8 H5 w9 q4 J5 p& a4 a( P. O16
- S- F: x$ g4 K2 F& N3 z17
18
时间、空间复杂度
& O0 L, m( O% S$ o, n" R
! Z8 z/ P* z2 z! U* E5 Q
" e* H% C" h4 l" t
3 j7 p2 a6 o$ J! w
适用性：适用于顺序存储和链式存储的线性表。



3.2 （不稳定）堆排序
5 a. J5 p9 {" u① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
  d3 _  C  f; p每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
" T( ~6 A+ P3 S! L! g/ |或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
, C/ ]! q  O% ^2 S1 c
9 }. F8 G6 v, _
4 c; p% k0 C& r
即：
* i7 d+ ~3 V! }$ m8 E* X若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）

; y5 V4 V( `5 R6 U, `& o② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
  r9 a/ W0 g' A# F6 P" N思路：
0 W  F! ]9 c  Y2 C: D+ A) o7 i把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换
$ Y6 }1 }4 i( V. Y
! S% t# j: ], }) |+ A过程例子：
+ q, g7 D1 ^! |; g
5 I$ z7 C8 j5 a' N. s

建⽴⼤根堆（代码）：
  K% V$ v7 _4 ]; h
  y. _; U& n. T/ m1 \' e

5 S7 K( h% h: K+ s8 X" x* P& }// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
: E" E) y' ~# Y        HeadAdjust(A, i, len);
- e1 T# G8 q( U; G}

* N5 [4 V) e5 P// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
$ i& g+ S$ [7 r! n' ^0 R1 ?* b5 g        if(i<len && A<A[i+1])       
            i++;
0 t2 I7 B( l& v  Q5 T0 W        if(A[0] >= A)
            break;
. s9 s$ l5 X0 l- h5 K  }        else{
            A[k] = A;                        //将A调整至双亲结点上
6 R8 l) M4 ~& a7 w            k=i;                                        //修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0]
* y# U+ A9 ?% p; C5 V2 V}
( v# {9 x/ O/ _; v) T4 `
0 ^5 \. x( v' Q0 j1 j9 H! _1
2
( }% z/ R2 y. L9 A! c+ h3
- y8 }% o7 K/ g4 k. n: `4
' H2 @/ _9 V% u  T; [# n" Q5
0 G+ u9 ]3 h4 G6 p( s! n* l6
7
8
( w& k6 `' v" K$ `6 ^. f9
10
11
, ~$ w& H' r% ~7 }, m2 g12
+ t" X8 U2 P7 z0 u, r3 w! q13
14
. V' {4 m8 D4 u% [# u+ G% u15
16
17
# K; f+ s% h' H8 N# F% @18
19
" ~( Y* @8 }/ M20
6 T+ {9 {1 h) y, k* K21
4 L0 h/ q+ F3 ]7 H5 w  i③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
$ |9 ?; D! K0 g+ g- t. j- z选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
3 C' o6 A# k+ e8 f) j+ U$ l
9 ^6 [+ A0 w7 @- {6 A8 {堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
8 W+ m; s# M/ Z! u3 u, h- q& l  X
3 f' E" }0 b, A/ d0 o: ?过程：

// 交换a和b的值
" j: _* l5 U7 I  t. ovoid swap(int &a, int &b){
    int temp = a;
    a = b;
' y; @- l  v# i2 Q    b = temp;
}

// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
- d" H! c& a5 }% Q        //初始建立大根堆
4 g2 D- k( J; P1 D7 q    BuildMaxHeap(A, len);                
8 [; W$ a7 a  n0 b/ o$ L! U7 D
    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
0 R$ k$ c" I, j  o/ `    {             
! C& z  l  X; v        swap(A, A[1]);
7 C+ O; g8 Y& l# ]$ V        HeadAdjust(A,1,i-1);
    }
9 B, g: B( Q8 r$ E6 i}
$ n, ^+ Q1 z1 i* a
! |8 N1 n5 Q- I1 n  L1
1 ^% A3 }  I* y8 z) H; e2
! g7 f% A7 X/ |0 Y. b; s3
4
* P9 t( _9 ?/ I& t5 \- \5
6
- M. v& w$ S2 a% l8 T# ^/ w. [7
8
- e7 X7 q, s8 u8 b9 h  {9 Y; b' f9
10
11
9 y/ b8 _) A! k4 f3 c4 N& X12
9 Q7 W: C+ i: S5 S: P+ f# o4 l6 G2 }2 r13
/ t# }! q7 n" l9 ^" n! f5 v0 R# E14
15
16
17
18
- D, X& @) b5 _# l19
时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
/ e' J# R# d5 P6 J4 k4 W故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
/ p& x; j: I1 l  ]( e
空间复杂度 = O(1)

结论：堆排序是不稳定的
( B% S9 V$ J( O+ I) q' J/ ]
. t+ a+ @# T# K& r( F( [. N' q
  N9 F( N- `% I- q' P1 F0 m; ^4 M. j) X8 S④ 补充：在堆中插⼊新元素
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌


1 \! d$ f; K# U; W
⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
* I( y! O# G! R  p  g: k
' D0 s8 v/ b. x. b: v' w
( b( b: A. }9 y: L% u


6 K/ W8 M3 ^# {- P4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个

① 明白什么是“2路”归并？——就是“⼆合⼀”
/ k( F6 \1 a# S% K- ]
5 X  H( E) o3 C# i/ [多路归并：


5 m, X8 q. M' B) b+ u② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
; Z$ P7 ~" \( O, y7 R# O
B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

2 \4 N5 Y6 ]' p, n) D+ K9 A/ k0 u5 s' Z③递归进行分治思想【MergeSort(int A[], int low, int high)】

3 ^7 B8 j3 q$ c* u5 j( t) j. W
④ 总实现代码
3 r9 Y, H! W" Q// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
9 R4 X/ l0 b; D; o# H' [# R8 E
// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
5 B( \0 g5 C) e* Fvoid Merge(int A[], int low, int mid, int high){
; v0 X% _) n- j. `  ~; W    int i,j,k;
. j5 q6 t1 n' G5 c. c! F7 ^    for(k=low; k<=high; k++)
        B[k]=A[k];
1 d4 v- N, P4 y0 @5 Q) N, K4 z) h, y    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
; K6 K0 y& U9 d  H4 n        if(B<=B[j])
& z" z5 R( z; U$ K: `+ S            A[k]=B[i++];
        else
7 N/ J* W0 ~6 L* v/ k6 j0 a3 a            A[k]=B[j++];
. ~% i- k% S1 M! S+ R    }
    while(i<=mid)
. p6 C; q& v7 H9 ^' O        A[k++]=B[i++];
    while(j<=high)
( S/ O7 |! P; p6 Y3 ]        A[k++]=B[j++];
$ z* J. x/ M6 T# k# @}


9 T) W# I; d% u4 l! X// 递归操作（使用了分治法思想）
. W& P) ]4 z2 _3 b1 vvoid MergeSort(int A[], int low, int high){
    if(low<high){
: c, x' y5 I, E  X: I0 v: ]5 v        int mid = (low+high)/2;
! C, t2 ?1 G8 E3 T- V        MergeSort(A, low, mid);
& ^9 a) a0 L) Z6 x9 c! G$ P7 L        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
1 Y' T3 K# A+ W1 K    }
- s% O3 g4 ^+ Y+ i! m' _}

1
2
" b% E7 ?& q( Z' Z3
4
5 J: j6 u% W; Q4 {- v  l* m5
  g4 {# c- J7 z2 b; {3 `6
5 l- E# B$ Q1 g7 v! ?8 u( o- i7
8
9
+ A& g# r* ]5 ]4 e+ V; ?10
11
12
! N7 ~. _; f4 H0 \; s; g13
14
3 e. x$ D$ i6 r/ _' g15
16
) z; u  i7 k6 K9 q17
3 `2 N2 `0 w& _7 X18
19
20
. G! b: l5 f" S+ E; N  `+ y21
# L  {2 V6 J; u) V# T* [22
23
24
6 k; b% \6 d6 B9 k9 p4 g) n25
/ _% V# y: T# X' R9 x% U26
27
' G* o  m5 m9 N# V28
' w4 `7 j  u+ ~9 O, p29
- F( n6 P' F' T, ~( a7 G1 i30
( T  _* @* g. _时间、空间复杂度
1 }! f+ G8 Q. A) A$ O5 ?+ N



( P! ^8 v& d% t5. 基数排序
直接看课本的过程图来理解P352
5 M, [/ Y' e1 V, ]. O- d& F
再看这个例子：
* o+ h1 e: {& u5 U2 r

! Q: x; W. G7 S  o3 C6 x" `算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
) q1 Z* z, e$ P) M分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
: m1 u# f% b/ ^: W' b. {% X3 `基数排序擅长处理的问题：
5 `) Z$ z5 @4 {- c0 Y: y5 a" n①数据元素的关键字可以方便地拆分为d组，且d较小。
  G! X" H# x. |( q②每组关键字的取值范围不大，即r较小。
; r, C9 g  V: j, B6 P0 }: _( m③ 数据元素个数n较大。
算法效率分析：
  b7 r) V. x5 I8 w5 A时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
稳定性：稳定。
0 q5 O( n6 B  y6 E( q' z  Z& k, W6 H

. q8 w* I7 J6 ^' B& ]: z内部排序算法总结
; ^" v; k5 S+ }1 ^% p. J/ f
————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969

8 [& b2 `  d* X3 Z
0 K" h. H4 ?$ F" x  R