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

杨利霞

4 c" P) D( j8 q+ }4 ]& \【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
8 a* e+ p4 e, g7 O/ K排序
1. 插⼊排序
" j4 [. l; Q# C; @0 ~（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
; _; t% h! t* z' \时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
5 W7 M) f9 T; @$ }  k0 ]时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
时间、空间复杂度
" f1 a" W. e* Y: G6 l  [9 P2. 交换排序
3 z; w- C6 Y3 i6 }6 H5 A2.1 (稳定）冒泡排序
5 w' ^1 b# a: m) P& b) _时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
4 p6 F$ L% D' V5 v3 M  A3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
3.2 （不稳定）堆排序
8 X) W& `. T- s8 V4 V① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
3 i8 M* u$ X9 Z* N9 B③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
$ c. \/ i4 U0 r5 s4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
5 P5 c& Z2 r8 X② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
+ R! N0 }7 I- d2 y* z9 i& ~; n④ 总实现代码
时间、空间复杂度
5. 基数排序
, i& [3 @7 g; o% _( T7 I( P内部排序算法总结
排序
' z- S/ z; V4 j/ \$ I7 _2 C排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
$ |$ C5 t- ?7 E+ G
' P9 H5 @7 y: l( `' u+ Y- \排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
9 }' ]  \/ j" Z5 z
算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。


3 k7 j2 z6 d# I2 [( {& \: \排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
3 T- \; u6 u( V. j& F) P$ N

6 I( v' Z+ i9 R' p; P+ ?4 k
$ H$ O. F0 A' c2 K7 u1. 插⼊排序
) f0 y# \7 j. C, }7 C' p* u（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
$ L& I3 z/ a/ u基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
8 T. }" D6 ]/ R: A( S3 P1 H$ T
算法解释：（从小到大）
4 `9 b2 P' {8 s4 K

算法三个步骤：
" j  e1 A& J- F% F7 `
先保留要插入的数字
6 N! Y: H9 c5 j" L; i( L往后移
插入元素
* `6 Y, \' d: _6 `
1 x; e. }; g- W2 E# n' X// 对A[]数组中共n个元素进行插入排序
  N: I3 c4 h4 ivoid InsertSort(int A[],int n){
6 d" E( @. P, a2 X1 z' }    int i,j,temp;
    for(i=1; i<n; i++)
    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
) Y. \; j; Y9 z2 y( A        if(A<A[i-1])
; ~4 ~+ K3 v) y2 R2 L6 }) w        {           
* N/ d( p, Z9 J$ v4 |2 r            temp=A;  //保留要插入的数字
+ H+ _% l1 B# v( M: o. R: e: s
# t5 ~$ V0 {# G0 p8 j6 V6 W5 L            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪

1 Y2 r! v2 @# Q2 Y9 {/ `! z; s            A[j+1]=temp;//插入元素
        }
    }
}
# S: U3 G0 _& ]9 c1 X& y/ T  c
1
, w7 G1 g9 D1 P/ g( ~6 i2
6 N* ?% K: p5 e/ E) O# n/ p4 h3
4
( ?8 c. S! E0 `5
5 [% d( s3 k$ X; Q- U6
7
8
9
10
11
12
( x" P6 r9 o! K13
14
15
16
1 I7 i& d1 Q9 @& Z4 w0 S17
用算法再带入这个例子，进行加深理解

5 B4 @7 o: N: v6 z( A
带哨兵：
, C9 g' ?0 b; l9 @: O, l
, d/ u- F$ e* C; w+ K
补充：对链表L进行插入排序

void InsertSort(LinkList &L){
  m" n! e% H: l" P    LNode *p=L->next, *pre;
    LNode *r=p->next;
    p->next=NULL;
  }0 j" t4 R. C7 V& w' l; I    p=r;
, r6 {; y( X" a3 K. {2 {    while(p!=NULL){
4 _! R/ ^" ~; ?6 B3 q        r=p->next;
2 |4 `$ N, D! _* f. j) z8 N- |( P2 k. g        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
/ p. c+ f9 K8 U! E5 f            pre=pre->next;
/ }9 `" d- A$ A) m        p->next=pre->next;
0 u1 U8 |2 {# B: Z        pre->next=p;
        p=r;
& b. D- R3 z+ \; p    }
}
* t& N9 R! {6 y/ U  F7 P1
9 q' h9 t, W+ X9 j# K, d1 D% W  e3 x2
+ o; }- K1 K, q: ^' _3
: M. V7 ]9 O6 e2 v4
5
; U; }, x1 O  {/ t' `; M: O6
7
8
% n2 ^( G1 C+ D9
2 l9 t" J2 L0 V# M9 D! f10
11
12
13
  Z0 l3 m* o8 J$ D  f9 V( h& l14
1 ]" p5 m; _/ Y) y3 S15
时间、空间复杂度

! f+ K7 m; @1 X5 W) `1 i
最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
最好时间复杂度—— O(n)

% `. o* U. c5 [; W6 O9 B9 P最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
4 D+ O  `/ ]0 ~第1趟：对⽐关键字2次，移动元素3次
0 ^: [0 \2 i. }第2趟：对⽐关键字3次，移动元素4次
, y, t$ B) y. }8 f  B, ~% i8 \…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)



0 U9 h, A' Z5 ~. R: ?4 ^

3 H! ]7 j+ L$ f# J! m（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：


$ q/ a' A4 M1 I% I6 N; D. b
; O3 f- R; g: H# R//对A[]数组中共n个元素进行折半插入排序
/ n# c7 A" c& W" `) o6 f$ vvoid InsertSort(int A[], int n)
{
; A0 m8 v. |. v% F+ ?+ F    int i,j,low,high,mid;
0 S4 G' |2 ?$ k2 t4 ]; N! X. {% S    for(i=2; i<=n; i++)
$ U! u4 e8 P& R7 W7 b, P& k5 Z/ V; z    {
: E6 E! l& G8 `5 c9 l        A[0]=A; //存到A[0]
: @4 M' L5 H8 C        //-----------------折半查找【代码一样】---------------------------
9 R" _0 g6 ]  B% T  i, \0 S1 i, d& x' d        low=1; high=i-1;
/ c( E6 C, a. x& [% g# p" U        while(low<=high){            
            mid=(low+high)/2;
            if(A[mid]>A[0])
                high=mid-1;
% j8 M* F9 c* }7 P            else
9 F! x; {- R# {                low=mid+1;
6 T% A6 z) U, I; @: Z  p% C        }
         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];
) k1 l$ L' N, ?* X3 j6 H  Q! P
- q1 N4 l) ?7 z        A[high+1]=A[0];//插入
    }
  [1 x6 F7 W/ N2 N( v}

1
2
  t( d+ P# G* `. m& R3
4
( b6 ^3 i$ W  G5
6
3 N  [2 W; ?5 {7
8
! r  Q) f  D$ S9
10
  v5 l6 C. g, g11
6 w2 z, c/ @) l12
+ q! K3 \& e0 Y5 m' P, L4 Y# C" o13
14
/ D& n, P1 }1 w# u15
16
" A" }1 r0 n& Y7 {: J3 x3 r* P8 E% c! D17
18
# P' B" U' H+ }0 N$ L19
+ w9 `, w# M* E" r8 Y; I, q20
7 }5 }+ O) v5 h# d21
22
1 G7 m% z- n/ M& e' d. z: }23
时间、空间复杂度
0 M: n. ?2 V- W0 b1 s" Y4 I空间复杂度：O(1)

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


（不稳定）1.3 希尔排序【多次直接插入排序】
. N, k7 H, ~$ _$ R" d0 O0 R是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

) w4 |7 Y  D% S; r1 {9 y& H+ T算法思想

8 d' X. K( Q* o3 w$ p2 \: w希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
) Q3 g" m! j8 K3 l7 k+ B; T随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
4 T9 H+ p/ i. F* m/ b$ _- S) \" Q' R图解：
6 R5 {% Z; P0 C* ?


0 {+ b2 y2 ^$ f& s- D代码实现：

( o* _& h' M8 k* h& O//从小到大
. u1 O  l* F1 e1 B8 C& Kvoid shellSort(int* arr, int n)
{
5 Y& ^- q) ]. \3 a# d! T2 v        int gap, i, j, temp;
2 J' }0 o% d. c        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
' F0 ^* D1 n* R1 i4 A$ B        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
* [, D' R; o; L+ Q2 v- \# F' A  l            //**********************************直接插入排序（只是步长改变）**************************************************
9 Z# l( g+ v% x            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
' @- [: @& O5 X$ g                if (arr < arr[i - gap])
                {
                    temp = arr;
6 q5 ]+ J% a+ I2 U
                    //后移
0 z/ N* w$ h' e# g                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];

- r7 q% ?. d2 c+ ^, T% R' L                    arr[j + gap] = temp;//插入进去
                }
. i: u: v1 R  W/ ?9 `3 Q2 e            }
            //************************************************************************************
* |! E" i0 @- R+ G        }
7 V2 p4 H. [) |}
& s  M# f) T$ z) |2 l& @- R
2 c' W. s  L3 }( O% @1
7 L: O0 y1 c" L+ p% O1 N2
! z/ u1 S1 u& P5 t$ o3
4
5
) g* i; D; I$ R& _2 Q( l6
* F  P& A2 L+ N. c7
$ p2 ?$ f9 h0 n; `; m8
2 J) ]2 m9 M' y1 i/ t9
$ }/ n' r, d4 ^' C9 O1 y1 k10
11
& Q- R4 m1 F1 l) \12
! S3 h1 R; k2 x9 g2 B) Z$ \13
3 B2 i8 O) ]5 T9 C! T/ c14
15
9 Y0 l" D( E7 O/ |7 q" g16
$ [, P* X+ A+ t  D17
. d7 L5 P* I" N; ~18
19
9 g+ ~  h; ]. f8 F20
21
4 X/ k- E5 Q. e: a3 ~6 W; h$ \22
/ E' M: Y3 k, G. I  `2 e1 {. S23
24
& w& h; r1 p6 T7 J  P. ]' V0 p时间、空间复杂度
空间复杂度：O(1)
% {& I$ |7 S; \8 e! e* h4 p
时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)

稳定性：不稳定！

( R6 J% \4 G. c3 y- Q. ~' L
5 d5 s/ n& `$ c4 Q3 e3 g
& E0 I! H9 z6 l4 r6 k适⽤性：仅适⽤于顺序表，不适⽤于链表
0 ]& ~  o) n  X+ Z, W


2. 交换排序
2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
; o; I1 e1 \$ K1 O' W; P+ f从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

每一轮比较会让一个最大数字沉底或者一个最小数字上浮
# E6 R4 A2 B1 |: f3 J+ D; k
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
( z* D% j, i  h2 s2 y# n: U; |
实现代码：

$ B5 `/ l4 P0 s% y$ ^//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
{
        int temp;
* _# M4 A& r, Q7 B        for (int i = 0; i < len - 1; ++i)//循环比较次数
1 }- V7 x: r1 x        {
% K. T0 a: e. L8 ?, b  s! r                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
  m( W4 o/ ]4 p& {9 n) ?  k                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
                {
& ^3 A' }. @# K0 Z' |                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
                        {
                                //交换两个元素位置
                                temp = arr[j];
. H6 a# D7 K" @1 V0 s" I- U                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
/ o, Y1 `) z6 _. c' u                        }
2 J' B' {2 V) x( S$ `' d6 M- \                }
        }
$ F; Z0 _4 a( s& ^6 {}

1
2
. h; F3 {; d+ a; p/ t- T: h3
4
5
$ m) @4 e% M' x% v+ n6
7
8
9
$ c8 O7 L: O8 X# e10
11
$ `1 a7 d) u1 _; g& H" ]. \; T. P) E& x12
  |9 U: W* _% P6 k: d/ L- U2 T13
14
8 F) ], P. y0 n5 s15
16
17
18
19
" u* P% W& o/ @* j" G优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
' l" Q3 T  s. A- D6 Z1 j% l  x
//从小到大：
. p1 n2 }) O# S+ k) z8 h) M0 Rvoid bubble_sort(int arr[], int len)
1 S2 N7 G, a4 D. w7 \6 {9 |( ?{
        int temp;
' T3 O) M+ O7 M: V$ m2 R        bool flag;
+ d6 _3 ]- C  s4 K4 z5 O( H        for (int i = 0; i < len - 1; ++i)
        {
            //表示本趟冒泡是否发生交换的标志
                flag=false;
5 R* n$ `& d1 k' q               
                for (int j = 0; j < len - 1 - i; ++j)
                {
                        if (arr[j] > arr[j + 1])//稳定的原因
% ]  ?$ j# w0 B! h# t  |  h                        {
5 P+ s; @" y5 B0 m0 @) k                                temp = arr[j];
; K0 K- W6 O' t  z* |! \                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
& v- e2 z' d$ M3 M                                //有发生交换
                                flag=true;
                        }
4 [5 e" R' v9 x8 g; `7 X                }//for
4 u* X2 c% Z; K( w% `9 r               
                //本趟遍历后没有发生交换，说明表已经有序
                if(flag==false)return;【1】
        }//for
0 B: ]0 a% d& j4 I}
1 Z9 L2 u& v% M$ b1 h6 d
1
2
3
4
5
6
, s% F, v" x; @3 N. @8 I7
8
) a! M8 x2 W% t. W9
10
11
12
8 R* G7 o( r+ U) J) U' J13
. n( Y( c/ |+ G' E. A- C14
" _* p0 q6 o- x  d15
; ~4 U3 B! ^8 o1 K16
17
18
19
20
, J! |; L4 B% \8 R! u& p- K21
22
23
1 b" Z  Y4 k. w* H/ ~* ^9 H8 E24
9 q+ |+ K' Z# p. m25
26
时间、空间复杂度
1 N' t6 z& C4 k0 ~0 i5 y1 [
2 q8 }0 C4 o8 e& e' ~适用性：冒泡排序可以用于顺序表、链表
* Z! e+ P) W5 Q  y% t3 f6 P5 `
) f( O' a' ~4 v* t# X  P# V5 E
$ t+ b( Z( m; U( h! Z$ T! q6 ?: [

2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
6 _1 k0 b/ x# b- F. S+ g0 J在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
, Q+ H* X& f  U6 E+ U4 V, O通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
9 _' K2 S9 {) y/ _8 f  U  K( L8 `使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
# y( @) }+ [: r9 Y再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

! B! A7 W; }* [然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
8 X; ^) _. Q, G! U# @
划分的过程：
! [- j% h5 g- T: A, Z
初始状态：取首元素为pivot，定义low，high指针

$ C" ^" F/ a- J% c) O4 P首元素为49
+ Z$ Z& S: {* {3 U7 |) Jhigh指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置

1 w1 v& }$ i- w/ C2 P8 t6 o6 v
0 N% [$ m- l; h3 ^" B


// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
; I/ L' F+ T" |, X9 I        //取首元素为pivot
' O5 B7 T: f8 ?) I/ y7 I    int pivot = A[low];
& D5 a# L1 x6 A& H3 q  A
    while(low<high)
    {
            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
            --high;
% H  L! H5 |2 h. V: l0 v2 N% `  p        A[low] = A[high];

% F  y$ L) v) r- ]+ N. z& X        //随后low向右移动
        while(low<high && A[low]<=pivot)
            ++low;
% j! c6 k  G& b* h' `        A[high] = A[low];
    }

' v) J' M" P" o    //low=high的位置，即pivot放在的位置
    A[low] = pivot;

, t! L/ V) O" B5 f- Z& s, y    return low;
}
4 O9 Z8 o2 a2 h7 ?) o3 J
// 对A[]数组的low到high进行快速排序
1 t; Z( u* g9 U) _* Lvoid QuickSort(int A[], int low, int high){
    if(low<high){
6 K. v! D- l6 g' m        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
, H# [4 @2 k1 y, T        QuickSort(A, pivotpos + 1, high);
    }
}

1
  J- B4 y2 }+ i( X5 _5 Y2
: T% O2 G5 n* T9 r: p$ M3
4
5
6
: m, X1 M5 T& \$ m( X/ h/ c7
' T9 K% }! N, ^8
9
5 Y% p; |" h3 A( M8 ]9 N: m10
11
; W) K- w8 q! \9 g' w12
13
14
15
  y: d8 z) s4 w' g9 a) c5 ~16
: w7 X/ ^) f# v9 d17
8 ]# q  y" [' S, |0 e2 u+ Q& _. {. G18
* U. }) a# g  d- k0 }5 w19
20
21
1 F3 a, @4 R! B7 N22
23
, U0 y, a/ m! `9 Y24
25
: u8 ^9 T& }6 [" c: q( Q26
27
28
29
30
31
32
! t0 J# t% ]4 ~: K0 T* C  |8 ]" L7 J时间、空间复杂度
; E' _% Y* _* r0 B
! L- N! g' f7 i5 }# _3 F, ~& S
把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
" O' b% T8 c& i" R0 E
n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n
! m. a& o/ g( W
9 T" G6 t, ]! n8 @3 c时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
0 w8 n9 Z/ E1 O3 o: t; o最坏时间复杂度=O(n2)
  r- h* q$ W% `6 J平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法
0 w1 o- N" Q) p9 m' t* k
4 L: N$ d8 {% G8 d9 z2 a9 U空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)

% S7 r, f* m% C9 I' t( G最坏的情况
. y0 a7 p9 B8 F% L  Q5 c

% S8 G. w0 _: ^- t
⽐较好的情况


: ^5 E0 d. f3 j- w1 q
不稳定的原因：


3 I/ R/ \! P4 U, P0 J
8 ^' e6 q- _2 }$ y# x
, E1 l. D& }' L' C
3.选择排序
7 J" R$ v4 [2 Q选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

3 f! [" m& _( e( d: q3.1 （不稳定）简单选择排序
/ M% v9 C' S; o5 c* J算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置

! Y( ~5 s! N4 v' P
+ s2 r. l2 l9 S  N$ v
// 交换a和b的值
6 D- P2 b) F1 ^! c0 Q5 qvoid swap(int &a, int &b){
- P# m* S% `1 q$ K    int temp = a;
    a = b;
    b = temp;
}
1 O3 z, _+ `& b
* [, U% Z+ d$ c- \1 A" z// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
{
9 x& A5 x) Z2 j( C/ {# V7 e! p& N- `        //一共进行n-1趟，i指向待排序序列中第一个元素
1 a4 R' x7 i8 {- o( @/ H/ U    for(int i=0; i<n-1; i++)
    {                 
        int min = i;
$ A/ F0 D5 ]8 u        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
                min = j;
        }
        if(min!=i)                     
1 J: h' J& W5 k            swap(A, A[min]);
    }
}

1
2
% a* E! M- u$ o3
+ g4 X( I7 {0 d3 s* s( M4
. P* e: ^, l( j/ g4 f" ]5
" s" ^; E8 n( q* m6
! N9 \9 s' m  T" [# N! T/ u7
" p" o& }  p: F/ t8
9
10
11
1 Q' j6 ]. s# l+ y) {2 A& s. r12
13
1 V5 G! M* S+ o  S. I) k1 S14
15
( R" e  S5 f# N% w/ g3 q$ N) H16
17
8 \. Q- `9 f3 N9 R18
% B6 I4 z& g: F$ S/ j19
20
21
& u4 S, l0 ^, ]( t4 z; O1 F22
补充：对链表进行简单选择排序

4 `6 q6 ~( `% qvoid selectSort(LinkList &L){
0 u; E$ N  B* N! Y8 y    LNode *h=L,*p,*q,*r,*s;
9 `( z9 ~- O6 x    L=NULL;
    while(h!=NULL){
        p=s=h; q=r=NULL;
0 R$ ~" V  o: W7 n- O        while(p!=NULL){
$ D$ z, s1 k$ q# k( i            if(p->data>s->data){
3 C- S$ Z! w7 ^, {& i, a1 x                s=p; r=q;
, C/ {4 X5 y  ^: y$ F3 D            }
            q=p; p=p->next;
        }
        if(s==h)
            h=h->next;
7 r1 c$ P- M- B' m        else
' F  A6 x5 d% }8 h5 x+ K5 C; C            r->next=s->next;
        s->next=L; L=s;
" ]+ w( J8 W0 c    }
, Y+ b6 F0 A( a/ F}
& C+ J  m0 F  y4 `; [7 K7 p4 f
/ S+ f2 J. v- J* v$ v% Q3 G# [1
7 w3 `) K3 z1 X2
3
* Q. R  K: F5 \3 M) ?$ i7 ]4
# S0 y' ~' R" h) r. h5
6
7
8
5 k. q" r; x% S9
! c4 U* @" {4 O& G( T10
11
12
1 D, O7 B& ?( z  k13
6 E3 X" b9 D  R8 k14
15
16
$ g7 v0 G. ^8 `6 B3 H17
8 p) p, H/ M$ M: o, K/ r18
时间、空间复杂度

2 I& f3 n1 y; k& N& m0 F/ X) v
; H( w  g, k+ ?& M3 c

适用性：适用于顺序存储和链式存储的线性表。



3.2 （不稳定）堆排序
8 G& E" ], C3 k' c3 \+ |1 x+ B$ L① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
  n8 g5 \- X0 G9 V+ X0 c堆是具有以下性质的完全二叉树：
7 ^/ Q) N8 b1 t" b每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
! u/ J9 ~3 X1 z( Y. Q) g, P8 N2 b/ t或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
0 c) t( f! `( d* A% X- L, {

9 p4 V' B# d& D8 J+ H  ^! D7 h
+ Y1 o' d7 Z7 s* Q即：
若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
1 P" B! B' B" Y% H  z. S若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）

② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
- t; M2 R! ~, E8 v思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
6 h& G1 F3 O' P4 E: m; a: q
+ c& @3 `9 t( `! `9 M1 n* N在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
) U5 V  E3 O' G9 I  F8 J9 O6 Y
* x3 [6 W5 d- j1 W3 u检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

7 o+ t/ F" ?" j过程例子：
# }5 C" K. _2 O9 E' Z- K" q

- Q) C( J2 `6 u9 G* `
建⽴⼤根堆（代码）：



// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
+ _. q1 a6 X1 C9 N}

  a3 F1 X6 ?/ f  }1 C- H, z// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
  w$ B  `5 p2 D    A[0] = A[k];
2 Y% s" o& {7 c) Y+ L    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
' t4 L4 \, E- }5 ~        if(i<len && A<A[i+1])       
            i++;
        if(A[0] >= A)
            break;
        else{
            A[k] = A;                        //将A调整至双亲结点上
& i7 W! M, \$ o            k=i;                                        //修改k值，以便继续向下筛选
        }
    }
, _, {( X0 j8 h) K1 n2 L/ M4 U2 @& `    A[k] = A[0]
}

1
( u4 G0 `- X: \# o2
! R2 E- a/ c  q/ \& H: l+ r; ^3
/ p. n. D5 S! U# Y8 q7 a& o4
# ^, o1 V( ~/ g3 B; Y/ Z7 ]5
  A7 y; z$ @9 i% A: C1 k1 ]# d6
7
8
1 D' E7 V4 a: C7 |) B+ w9
$ |+ @$ e+ m0 [( J8 u10
: Q4 S( r7 R, e7 @11
12
1 W/ X$ m+ @% e) U& r1 h13
14
; ]; \, l' o; l4 n15
; m$ O- \0 C8 H- c16
17
18
19
( b- V5 y4 o7 U, ?, \+ |* Y/ j4 _20
21
. v" G4 F8 m( H: T' h. M③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
/ y4 ~7 U# T+ w8 J" R+ X" q选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

1 W7 P) z/ m4 ~$ R' ^堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

过程：
+ g8 n- c9 \7 S' J  `2 \  }( t
// 交换a和b的值
7 x7 ]* }8 v# e* T8 C3 t2 z# hvoid swap(int &a, int &b){
    int temp = a;
8 x* ^- o/ S, b" u% f    a = b;
5 d# D1 m- _5 S, ]3 Y3 Y    b = temp;
}

// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
        //初始建立大根堆
    BuildMaxHeap(A, len);                
$ P7 o3 X3 S( H. t/ M0 j
0 }- B$ M0 Y' `( X2 h# s' A5 s9 k    //n-1趟的交换和建堆过程
- S6 r) V- V6 \8 y4 |/ {    for(int i=len; i>1; i--)
( i6 ]* E. J, b" l    {             
        swap(A, A[1]);
1 d1 m- e! Z& r; p+ {" G        HeadAdjust(A,1,i-1);
    }
}
4 _, i/ U1 N+ {" c; Q- F
  H" J7 D! A: ]- ]: l* R1
+ {/ Y& S; @/ ^" r8 l2
3
& b$ i8 k2 Q( A7 J" ^4
, O8 c6 n+ N# Q' q! ^/ d5
6
7
& P: i& y4 V. p/ m7 Z8
9
" J' S! {8 U" L" u10
$ I. b. O7 ~' I& s  z8 R" r/ H. n11
8 J" i9 _& D. [. a7 b  E12
: p+ |2 }! ?9 R, c. [: d$ G13
14
15
1 l7 K5 M7 t; d6 G) o; D+ N# q% {16
; s3 |3 N) _" y3 L( R5 x5 E17
  V' D& q8 }$ t. w& y: R6 ?; y18
5 R4 G7 `6 V/ E5 e0 K$ p19
时间、空间复杂度
0 l" R8 X) K3 y9 ]: h建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

空间复杂度 = O(1)

结论：堆排序是不稳定的
) h+ h$ F) W1 q2 o

. j6 F& V2 V; F+ }; U- U( N) J5 R( g④ 补充：在堆中插⼊新元素
: D# s$ Z" N. G3 s- J: T' ]/ d对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌

6 K# z5 z+ i% [* M4 q

* }3 u3 z) P3 E; C/ N⑤ 补充：在堆中删除元素
* o$ a' A: S! a+ W' a* {被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌

9 |+ ]' \% ^/ |, z3 u! D

3 D# z) `0 H. T9 g

4. （稳定）归并排序
4 l3 P- M, ~1 b" _& x归并：把两个或多个已经有序的序列合并成⼀个
" m# k5 r$ d) i7 S( S
: e4 z1 |4 m) E+ X7 g- S6 u① 明白什么是“2路”归并？——就是“⼆合⼀”
4 A7 W3 T8 b' D
多路归并：

' Q! e9 G3 L" d2 Z
" i- H, E% ~) g, e' a) r+ R② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

# U+ |. H; z+ U0 B6 y$ A2 _B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

! C- c5 t$ i  E/ e( N* W/ W) Z③递归进行分治思想【MergeSort(int A[], int low, int high)】

+ g% O, }& _; {& P& r+ L
④ 总实现代码
. M" ?2 J6 Y  y, o$ a& Y4 J// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
$ O/ t" [; {" [0 ]5 y
// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
  A5 y: _  p( C) tvoid Merge(int A[], int low, int mid, int high){
; |1 W; `* P& c! r- U0 a. x+ g    int i,j,k;
    for(k=low; k<=high; k++)
: F: Y3 s! k5 Q2 v5 u: |9 g0 E) y6 Z        B[k]=A[k];
    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B<=B[j])
            A[k]=B[i++];
3 a' y! W+ W! p3 X6 ?        else
            A[k]=B[j++];
    }
) Y. i* u& G4 G0 `    while(i<=mid)
3 p+ \2 c: E3 A4 h* ~& H        A[k++]=B[i++];
# }( q, q8 w# k, e1 x8 i    while(j<=high)
        A[k++]=B[j++];
; h$ e4 e9 H0 S$ K0 J}


# r- W) r8 U- s. _6 E, t// 递归操作（使用了分治法思想）
. N+ v1 u! ]; J) \void MergeSort(int A[], int low, int high){
    if(low<high){
- ?, k6 e( R2 a  ]- H" I% b        int mid = (low+high)/2;
        MergeSort(A, low, mid);
9 D; ?! ~$ C# u        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
    }
}
6 c; F3 U0 p$ f& w" o+ k5 J
1
2
3
' y# O/ ^, b* i/ b! B! a4
; h6 ^: p5 Y6 R) {) w5
6
7
, j- z, Z2 E4 X0 I8
, s# }  d+ l3 t7 _9
6 `/ R. f+ x9 G- [10
11
8 |8 k$ a; w% p2 k12
9 y* A  b; `0 b) W' {' X13
! M$ X$ z$ _7 z5 {6 ?1 U2 D( Y" s14
# d( M  }. A. U5 {15
4 [) G$ g5 [) q9 Q* @9 ^8 X; U) Q* t16
17
& ~3 \. x5 {% \5 ^) `18
19
20
21
6 P0 r& Z8 o1 g22
23
( Q7 v. w) J, }3 X) D& T' W24
25
% J/ c5 S* L  v/ ~* @3 h26
% h2 v: s7 C. w" }* e" v6 m% R; `/ m27
9 F$ U3 p' c5 k28
- c2 K; h; _# P+ w2 q. T  c" Y29
3 M% C6 W- ]$ T3 ^; O% w30
+ U1 R. ^" _8 W' t5 ?/ r/ a时间、空间复杂度
6 {! K0 v9 G. u- L4 ]7 H5 c
( W, w1 ]# v" j$ y1 O1 q. f
% c  P& F/ g9 B4 `0 `

# e6 w: q' Z9 _8 K% T$ [4 o0 A5. 基数排序
直接看课本的过程图来理解P352

再看这个例子：

/ y% a( p( g& [0 O( A- ~9 Y7 D
9 u" v0 p* G5 Y算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
1 l; ?# m7 @: \8 o* P2 a分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
9 t5 G& N6 q5 R$ m8 e: A: C- Z" E& R收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
; ^! E9 C" v, S9 J基数排序擅长处理的问题：
①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
0 k) J- x6 v0 U. d! S9 X③ 数据元素个数n较大。
算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
+ P1 P6 _+ X, Z. E9 j' G空间复杂度： O( r ) ，其中r为辅助队列数量。
, M" J6 h1 F3 a8 x稳定性：稳定。
9 m8 W0 b4 [8 \; r; x" k
" R) A* v  ~+ y
内部排序算法总结

————————————————
. P( C3 S4 p% q$ i, s# P3 ?版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969
- u7 z9 r, c2 ~6 p2 t, k
$ U+ v  C0 [% I. o) V