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

杨利霞

+ x: F4 g! G2 X【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
! `# D% S  ~  Y排序
  ?: f6 C7 s4 Y5 u6 p1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
4 |6 {: L8 {6 ?% ~2 i* X7 Z时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
: d% \4 G4 a. S时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
2 N0 o$ Z: l: c* u% b1 W时间、空间复杂度
6 @1 {, e& ~0 s; H  L: _/ h7 U; i2. 交换排序
2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
3.选择排序
4 r8 x3 ~$ Y6 B4 X3.1 （不稳定）简单选择排序
时间、空间复杂度
3.2 （不稳定）堆排序
0 e) J/ I+ l$ [) ]8 J- t① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
% W  D8 f2 A5 X( r: [4 g+ \③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
1 N: U0 a* J% `9 `! n" d. r# z④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
4. （稳定）归并排序
! q8 f+ _# J5 B1 e& J7 e4 m① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
时间、空间复杂度
5. 基数排序
5 K, A5 D$ x# {0 Z6 K. e. p内部排序算法总结
3 `3 M, s+ K+ }6 v$ }1 e排序
5 U2 `1 o& q2 I排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
- @3 b  F! M  p9 ?8 e' }# ^
- M- P# a9 ^' `- S% D* R& _0 K排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
) C  O* v9 ^! l' r5 D2 Y0 k9 ~6 I
+ ~2 F# o' B* [2 f1 V" ]; Y- O9 U0 I算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
, j# [) z( D9 z8 D稳定的排序算法不一定比不稳定的排序算法要好。


) M  s  A$ a- d' x5 O# x6 Z; t排序算法的分类：
4 M5 M( a+ _6 I$ e! `5 _( t6 H. ]内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

0 N# [2 Y$ d1 C0 p) Z各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html


9 _7 [1 W& A% V& C- y! d; Y5 A+ \
1. 插⼊排序
: Z5 F1 b8 N/ @  S$ O: g- V1 I（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
- r2 ?3 ?& j' M! O, O
6 r, ?0 V& @5 E% `3 I: |& M9 G9 P1 E算法解释：（从小到大）
* N& D# X8 M" Z0 u2 h2 Z/ w, A

6 [2 p, x. T5 }9 V% H7 B" ^- v算法三个步骤：
% B+ x1 B) E9 @9 i2 m! `' [: X
& {8 a/ W, N. F1 ]/ C) e先保留要插入的数字
往后移
插入元素
: P. {' u, k8 p. y) J, N! r" e/ t
  i* s+ H. \, r// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
# m$ g5 @# j4 _/ e+ X8 b    for(i=1; i<n; i++)
    {
- Y* N: R0 K/ M7 m/ D            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
        if(A<A[i-1])
        {           
            temp=A;  //保留要插入的数字

) i; D6 V, b! G  \4 z/ H            for(j=i-1; j>=0 && A[j]>temp; --j)
0 D( v/ p# V9 t* H* J                A[j+1]=A[j];    //所有大于temp的元素都向后挪
5 \5 D$ T& r. k  G8 x" y
4 x# v0 X5 S6 ~! G! n            A[j+1]=temp;//插入元素
( J  \( }, p6 C        }
' R* ]& |5 G* D" f' H, s# ~    }
6 \/ J8 p6 L! i6 B}
+ a; i9 e; W. Q; C) B* v- Z4 T  l# c
& @, s- u: m; O/ P1
6 a* ^* c4 @6 I' a! F2
, J' [( ?" C. `5 ]4 \0 O: o& E/ n3
# N  e/ P& G6 ~! Z. U' q, H: |( }4
5
6
7
/ M6 h* _3 M; Y$ d8
9
# Q2 U$ e* k7 T: P2 \; l0 s10
11
0 S: R8 y0 A4 U7 @/ D0 d12
& b8 R, N0 q. o' S) e13
14
2 M6 A0 W! V6 L2 T' G6 l15
$ w5 }9 Z5 L; o) P  _" s16
" E, |+ L" b/ n17
用算法再带入这个例子，进行加深理解


带哨兵：
$ c2 O/ y8 A* U; y% \
( r# E8 y$ k8 Z$ q" h
补充：对链表L进行插入排序

void InsertSort(LinkList &L){
- F0 `/ m/ |. c* e    LNode *p=L->next, *pre;
    LNode *r=p->next;
1 p3 D- J$ h- y" i2 C# u    p->next=NULL;
    p=r;
' L$ b3 L% l/ W4 T( T! V    while(p!=NULL){
        r=p->next;
$ b4 S. r! `# Y1 M8 s; @2 X% V        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
        p->next=pre->next;
6 n) {* G4 {6 X- \; x! h        pre->next=p;
# N8 y. m7 d0 d% G- {0 R4 U        p=r;
    }
}
* t' b* A5 w1 Q" C% W2 e0 b1
2
3
4
) @% T2 y( P# S5 m" b, u+ y& K5
6
4 |: S; T0 U# Y7
  G! o, Y. t, j0 [' X, y! y8
9
* P5 O" l6 o. f' G10
11
12
$ j5 X! g5 B0 a  U6 O& v13
0 X( r5 h7 v& F: I- t4 S' B% W14
9 T/ D8 V! @' i& J+ e# _$ d8 Z+ a. m15
时间、空间复杂度
" K- f/ B2 p1 c% f

6 g* Q0 v+ H3 N' \最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
8 X8 u  h! N9 W5 h4 s0 E0 Q最好时间复杂度—— O(n)
8 E+ N0 f3 p) d+ U- K/ h; o! _
& z! q8 [5 e% [& e/ ?最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)

! E# l- w4 H- Z9 `; S' M2 M0 H



* n6 J9 Q! U; q4 A( h（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
' m( I2 C3 b. l) w' o+ Z+ h( H7 P过程：
& h' L- a0 @' h- X7 B3 j3 w: j% b
) H( I/ S3 o2 u, h. h

5 I0 H4 j- w. V2 q3 W6 p( m7 i//对A[]数组中共n个元素进行折半插入排序
! f5 w. E* _' N  l" ivoid InsertSort(int A[], int n)
{
    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
% m0 h" \+ S3 W' C    {
# U% J% T8 Q. o# C0 K( H        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
. O; e1 W- N/ n* e/ C        while(low<=high){            
            mid=(low+high)/2;
  e4 w, B( [  R6 w# Y/ J            if(A[mid]>A[0])
' _8 J! F6 ]3 I3 Q! J                high=mid-1;
0 t( W2 e0 ~. f, k  [            else
" J& D( s# J: j                low=mid+1;
        }
- G7 ?5 \+ t- z- A         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
# _% k& T$ ^0 T+ k" f) Q            A[j+1]=A[j];
/ y* k- O) W/ r0 M1 ~
        A[high+1]=A[0];//插入
    }
* ]4 J) ]0 n: I}

' l5 T4 d. G2 I4 v& Y1
: ~+ H" R) h5 ^- v# i" n2
3
4
3 s) o' f* i+ h( ^+ x: L9 w4 z5
6
7
7 z5 y" J9 f" c7 }" }7 e8
. r; c2 t7 Q& E# X& j2 W9
/ m) e7 S, w$ i% G3 @' ?- c+ R10
11
4 q4 N7 o4 Q1 ~- V$ P12
13
14
15
16
% Q' m7 r6 J0 \) {9 ]0 y17
18
19
20
0 V/ |0 ~9 h9 w( H; |, j21
22
% j' t' |, P( J) S+ V% {: c+ L4 \23
时间、空间复杂度
( R9 O9 E" W. x空间复杂度：O(1)

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

4 J" D9 v! m! \$ w& ?* G9 V/ d  x  W
4 ]! a2 s) x0 c( D/ e7 t（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

3 w- }5 I$ f( T8 P/ X; O/ L算法思想

: j5 P+ q: U" \; ]$ @( ?希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
6 [4 i* U* q7 y" }3 u图解：

# I) ~% {1 W8 b, d3 t
$ J+ M) M8 o. S- U/ O! V: g$ K% R1 p
9 {: \6 P3 S0 |; ]3 d代码实现：
* c8 f$ S& U: `3 S" y$ u
//从小到大
5 d2 W" }9 ^+ c: Svoid shellSort(int* arr, int n)
% r# I: O$ O8 T3 L{
- K, P4 f$ [8 t8 W        int gap, i, j, temp;
  f5 B. @7 D( W" C9 `7 a+ ^        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
1 _# ^' C$ v! i5 I. @4 o        {
            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
: h6 s7 w, |1 @; G# v: M0 O( e; [5 _            {
/ l- F+ D1 {) U# \5 [, Y                if (arr < arr[i - gap])
                {
                    temp = arr;
1 f+ l( T- H# `; S; I2 d( g& I( Q, U
                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];
: H% Y" t8 h4 d
                    arr[j + gap] = temp;//插入进去
2 ^) Y: A# d  A+ X2 P+ X3 ~                }
" t  ^1 Q1 Z! P# L: M4 H            }
$ V3 V+ |( N! V& }' _            //************************************************************************************
8 o6 H# V# f' L1 K8 }- t        }
3 k! g8 s3 e; g8 X  `6 c# W}

1
2
/ D( e" I0 e8 f- W( I7 }3
4
5
* Q, q& i9 ^9 a3 H+ d9 ]- M6
7
8
* U0 }3 H8 _, q3 b3 a! ~9
5 ^' ~2 Y, i" r. g10
11
1 ^& G" e9 j2 s6 R' @+ I12
13
" l' D7 P2 j2 a* T, T" P14
2 _% y7 I/ S$ v15
16
17
( x+ y9 Y. k/ E1 Y/ P% a) _3 g18
9 O* m7 S4 N' ^3 P5 ~$ ?19
20
4 F" @7 t6 }* f) c: g21
22
23
6 i5 q+ G. ^5 z24
时间、空间复杂度
. T8 ~1 ^/ {$ n4 O' }/ ~6 c空间复杂度：O(1)

时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
# |4 g; D& E' K6 y* B- S
稳定性：不稳定！

6 q$ q" U' Y" C% w1 h' Y! X2 o

: i/ T6 M5 _. t9 w4 K8 k+ u; G适⽤性：仅适⽤于顺序表，不适⽤于链表
% p$ }1 d& ?+ U) n3 z
$ J: I* u' E; ?1 J" P( R
3 V4 [0 t/ m( X' n2 J, J" b5 `7 r
2. 交换排序
2.1 (稳定）冒泡排序
3 Z" H6 o8 O& h; H英文:bubble sort     (bubble 动和名词 起泡，冒泡)
& ]6 m7 |1 \  }. Y8 m$ p6 N& F$ D从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

/ s8 X+ s$ `  w0 U每一轮比较会让一个最大数字沉底或者一个最小数字上浮
( j* _3 g1 D5 u; J& q5 w( u% V9 J
: T: I8 F) Y9 X这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

实现代码：

! E0 w% t* a' T//从小到大：
1 r6 s! |4 x1 b+ n* E1 ?2 [' Zvoid bubble_sort(int arr[], int len)//冒泡排序int*arr
{
        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
        {
                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
                {
                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
                        {
! m& Q. C0 ?7 Y  J" N, N                                //交换两个元素位置
: X. d8 j6 U: U/ F                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
! I# C8 p! r/ `- N                        }
                }
        }
: a" D' N0 t( g3 a, s7 Y6 U# r4 V}

) c' ~1 E9 V/ l1
2
! M  X/ Y( R) J" o- m7 V3
4
# t; J9 S4 E* B2 t5
6
7
8
2 M5 Z! P9 K! c+ g9
10
, i/ h7 q' N# @* O3 k' ?$ a/ y; N11
12
13
14
15
3 e' a! Y7 Z6 H  S. r# D- \16
17
6 L. A/ |7 N6 O6 K3 q- w18
& S0 @; M, [+ k! c% N0 U19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

3 T- W( r2 z% J& P! l: M% x//从小到大：
; k* G0 s( u2 ~* wvoid bubble_sort(int arr[], int len)
6 b5 s, C5 k2 m* @* Z{
        int temp;
4 V4 J, F5 Q- f6 `        bool flag;
% I0 |  B, t' l7 B2 d: {7 d9 l1 X        for (int i = 0; i < len - 1; ++i)
        {
            //表示本趟冒泡是否发生交换的标志
" y& B' b( f! B) M3 ^/ x                flag=false;
               
                for (int j = 0; j < len - 1 - i; ++j)
; X- a) T! e5 b" |9 k6 y                {
1 ]9 q2 B5 z+ f                        if (arr[j] > arr[j + 1])//稳定的原因
. |1 T9 W4 |# N1 ~! M" ?9 U. D                        {
                                temp = arr[j];
; R' d, V4 L( l9 {- u  W                                arr[j] = arr[j + 1];
" J+ G+ O4 V/ D& ]2 c, a                                arr[j + 1] = temp;
2 z% c  Y4 @3 |- o                                //有发生交换
                                flag=true;
                        }
6 M  I8 ]% N5 J" c3 X2 o! _) U- L                }//for
1 L" ^' S" q" d& T* d4 a. }               
9 R& c. D: L  c( c2 r                //本趟遍历后没有发生交换，说明表已经有序
; M( r7 g/ c3 ]9 h* ^                if(flag==false)return;【1】
4 F. [) A+ r: o6 e+ p        }//for
}
  ]6 e6 @" \0 g! B, E* s$ K( S
: L& ~2 j/ T- }6 ^" N; x9 d1
2
3
4
5
: X0 v4 o6 v5 A6 t4 k6
7
; F4 n4 f& f- g8 u. h! Y# x' f' K8
0 ^2 ^" s3 p( d) z9 {8 ?9
10
! Q: P& t, F2 F( x( c11
12
9 M$ e+ V8 S* v7 w4 u9 X- l13
14
15
6 \; M) v, N: u8 ]16
17
' F- m& `$ r* D* B: S4 r' G18
$ Q7 H/ O5 @' D2 {" S  T19
6 _- l1 z8 D$ N( V  s6 \20
21
" @9 l, X  t4 ?0 o8 n+ p22
* L6 ^( R$ G( d6 j1 S23
* n! Z8 u+ [# }4 Q( b24
25
. C3 Y5 a: I$ ?, v4 `% c; i6 }26
时间、空间复杂度

+ X( _/ T! H( p% G1 D. @4 i& I适用性：冒泡排序可以用于顺序表、链表
% }$ J+ r3 ~2 A6 p8 Y5 z



3 s" Q. e$ Q$ A' W2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
9 o! a) V' j; R5 W算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

6 o( N. W! V! m' t# D+ g/ c然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

5 T8 c3 U* ^  p! Q; V- R) X. s1 _划分的过程：

$ r& S! O2 H: T3 p9 F初始状态：取首元素为pivot，定义low，high指针

: Y8 i# Q& U6 ~. u% x, A, ^首元素为49
( A0 K: J9 _. ~! h0 c7 Phigh指针指向的数据小于49，就放在low指向的位置
9 j9 Q% @, N' J. [low指针指向的数据大于49，就放在high指向的位置




# H6 g$ c2 ~+ r
// 用第一个元素将数组A[]划分为两个部分
1 J7 R) H; B) M+ s: u9 zint Partition(int A[], int low, int high){
        //取首元素为pivot
    int pivot = A[low];
% [4 N* H% k" m4 f7 c/ r/ U1 p: c
    while(low<high)
( N4 E$ k4 ]* A; g$ \+ c# B    {
9 z0 k" W# j3 \, |8 M% G6 T            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
; Z) L1 B) F; u: D            --high;
8 u0 g/ K' f. }! ^# d+ A: }) M0 v        A[low] = A[high];
( `8 ^& X) o7 H1 c, `. Q/ k# V
3 j7 O! s$ |- }% D( U4 T2 [        //随后low向右移动
        while(low<high && A[low]<=pivot)
- \2 M! o4 m- [            ++low;
: @. s" p5 L* ?. M! Q+ [        A[high] = A[low];
! U" `, O  M( X; n: A0 D    }
4 E4 h# b$ ]6 c2 e7 Y1 P- \- h
    //low=high的位置，即pivot放在的位置
    A[low] = pivot;
: @- p. j: k5 R: E/ Q* N
  M3 z2 i: \- f2 C2 k* d    return low;
}
/ J% q  P- P  k- {
// 对A[]数组的low到high进行快速排序
9 G3 n  u- @$ W4 h9 j' ~2 \void QuickSort(int A[], int low, int high){
    if(low<high){
        int pivotpos = Partition(A, low, high);  //划分
' ^' m* w1 c8 I5 u/ e4 D        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
    }
}

1
2
3
3 j8 k8 k! H* ?4
5
2 ~, P. S% r$ T5 |& V6
$ P3 F# V  w9 y( }7
  x9 {7 e! @/ c- A; T8
/ n% h" N- V6 h% N+ F9
10
11
12
13
* [% I  S: Q0 B( v$ r4 A. a14
15
5 ~, a" c" Q. z- \( p2 `9 Y. U16
17
18
1 B8 o8 L% {! E" z8 T8 P2 M: x19
  Z1 a" f6 v+ v+ X20
" i! Q7 L1 B' I( a$ f: ^: h% u21
22
5 M. A4 o! U9 W1 c/ ?( ?9 [) g23
( N; v+ h) D+ U1 @- N" @24
25
. @  v  b" T: p6 M26
27
* v8 \1 m) \: v7 n3 d9 c28
4 X! D& s1 C7 {8 U29
30
31
' M- D0 J; f" e- T. Z# V7 N2 {32
* b6 ^) j8 m! H7 U时间、空间复杂度
" e/ m2 W: O( F3 h) L- s
+ V; c+ R( u- \$ Y# R3 {
把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
: @6 l# r1 n6 I3 Q. L
n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

时间复杂度=O(n*递归层数)
! K, Z2 A) D$ R. g% z最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
3 P+ s8 S4 b: h. _平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)
: X' i& K. v" D8 _- m9 `$ p0 t
最坏的情况
  [- \! Y4 x( x: {, s, m3 M

4 x8 ]1 F5 F& I; \
⽐较好的情况
& p( ]& S( N# b: x* X
! q+ h# N, N. P- V. B+ X# {% u
7 A& H1 h- Z# l& \. ~- B: {% b
不稳定的原因：
+ S5 B# Y% D3 n0 w0 d1 G# @, s




+ }* z7 \1 U+ ?( q; e3.选择排序
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
9 i) Z0 D% y' ?6 t$ l( U  T' n  U
3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
0 q) a2 E2 A, O  z0 |* g" l7 |! y
" p& K/ ]/ N# G/ [) Q1 z$ [

// 交换a和b的值
6 Z9 C) k1 v, @. I  i7 Kvoid swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
: m7 `; V( V. Q4 M7 S}
# T0 N$ x& V8 z: K; C; x$ ?4 B
// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
1 r6 v7 b" Q% H2 _6 `; y{
        //一共进行n-1趟，i指向待排序序列中第一个元素
- a, s8 g3 d% X% W$ O# H: q; B2 k    for(int i=0; i<n-1; i++)
    {                 
, f( [* D' }+ G: ^. e2 Q* ~; \& K        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
                min = j;
+ U7 f; J" n9 E2 p$ l        }
' z; @+ Q, D, G1 @        if(min!=i)                     
            swap(A, A[min]);
+ M. H2 j! Q) b" z& {4 z    }
}

3 M4 s( I  W5 d1
2
3
4
5
$ C) |9 Z# X& ]5 Z$ X6
% b8 d4 W7 Z( f5 V+ F7
8
9
10
11
5 c/ _0 k# y4 y" ?12
; R" f& I- W& N1 [3 D! A. e13
4 O, U- m( X2 @) ^14
5 C+ u1 `3 G! C# x15
16
17
: S7 T9 }9 [1 ~* w0 G18
! i. @- t1 [8 Z19
. |$ R; ^  o8 q20
21
8 u9 l& V* Y% s22
. C8 [4 N( D" i2 W7 \! m. I补充：对链表进行简单选择排序

void selectSort(LinkList &L){
2 K* R! h0 N- U) U. @$ Y    LNode *h=L,*p,*q,*r,*s;
- V& R2 S7 A' _" D4 O    L=NULL;
; Y; \* |* u3 N: l/ e3 d! I    while(h!=NULL){
        p=s=h; q=r=NULL;
5 S- I0 d* N! V2 k        while(p!=NULL){
; L# [/ l: w: R- @: b3 P            if(p->data>s->data){
9 A2 C/ j& y" t7 y/ i) }                s=p; r=q;
$ x: F8 z+ ~" ~& Q6 x            }
. h3 U- M/ V" J- O            q=p; p=p->next;
        }
        if(s==h)
            h=h->next;
; N- D; l" G5 ]% H        else
            r->next=s->next;
        s->next=L; L=s;
9 d8 E6 K6 ]% i2 ~, L8 o    }
: H2 b4 y1 S* l( J! D" c}
) r! F; h3 l" s8 r1 O! Y
/ t5 b( u+ S! ?3 z! v2 X1
2
3
4
: O# C5 ]& [9 n9 u9 D5
6
( X6 g! t* ~8 E8 X9 K% i8 ]7
6 p4 f% w  T; Q4 }& a4 j' m+ A8
9
10
11
% U8 v0 J) M; `9 |# d12
; z* j/ B5 F( a) Q13
14
15
# F6 S* D' E, Q& I- t16
: K8 }, m5 U3 o1 b! u17
18
& _; v; A' C9 g时间、空间复杂度


. Q# t1 A: |0 j, h/ O) }

适用性：适用于顺序存储和链式存储的线性表。
2 Q3 b; V) r9 K
9 N5 T, l6 h( _2 O2 ?( s7 Q
  [+ I! A) H% @# H/ k* J
3.2 （不稳定）堆排序
  e& T& S7 G+ U( _7 k3 U① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
) C6 h/ O$ q3 B% ~堆是具有以下性质的完全二叉树：
- y8 K8 O7 o( c# \  P每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
2 G0 }8 a) x' V或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。



8 y7 G* G/ d& l- E! G. O即：
若满⾜：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）—— ⼩根堆（⼩顶堆）

: Z0 |& u( h( p8 Z4 g+ `② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
思路：
/ Y  B$ R; a5 r把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
+ e8 ?2 t1 C  k- X) ~
6 s8 w8 m" }+ R在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

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

" |) G$ H1 z+ e2 O过程例子：

, ~& r' z; z% |+ y% ?# {
# ]  a: e; O4 h! u; e1 A
建⽴⼤根堆（代码）：

* N- }4 @, I8 ]. a, |

; u5 o7 v6 g5 j# d( r% p1 u$ w& I// 对初始序列建立大根堆
3 k+ p0 m! }) ]: h' ~$ s% y' ovoid BuildMaxHeap(int A[], int len){
# N( L9 x& d  ~6 k- ?8 ?: t    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
3 s. `6 v# M: t2 o; a  |}

// 将以k为根的子树调整为大根堆
/ c, P& a  v$ \/ c+ [void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
            i++;
' O! U+ S; ?3 K        if(A[0] >= A)
            break;
9 t8 E! R8 |  I* p4 o        else{
            A[k] = A;                        //将A调整至双亲结点上
" L2 R  S( E9 L) x) f            k=i;                                        //修改k值，以便继续向下筛选
  U5 L3 M6 [' P; V1 E        }
6 a0 U0 d6 _4 E' D    }
9 }! G. X. j5 ^( y; h    A[k] = A[0]
8 X( k! h8 X6 ?, l1 t}

. q$ T3 z6 A; T6 z6 Q5 S) k# g7 W1
4 K; s% J, {) v7 B4 P, \% L# E2
3
4
5
" |! h" K' P) W8 m6
7
7 c2 v7 o. v# F+ w+ Z8
9
  G& D1 p( O1 G% Q4 K10
3 d" p! f9 C$ M0 B. s+ E4 E11
5 ]. Y' Z' s  G9 `; I: b2 n12
13
14
  L; i" @& r7 E: d: X1 H1 _15
16
17
, `" l2 p4 f. e* ?$ ]18
3 @/ ^' N. N2 R$ W* C) B$ }19
* N# D9 n" P+ ~% j6 @6 g  d) a0 C20
21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
/ m6 K) S  F+ d+ @7 t6 Y选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

过程：
: v4 m" o& {5 ?" j8 ]
/ l0 G5 \5 D- @& T. W: L" y/ V// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
' Z  \! E; |- K  R" \* ]4 i}
9 W1 d/ V- `7 h! \+ O8 Q$ W" e% f& `! y
// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
        //初始建立大根堆
) }6 l/ I% t% O. f* N0 A& s, P* p! O    BuildMaxHeap(A, len);                

) D. [( K' S% q2 @3 |  i* f2 w    //n-1趟的交换和建堆过程
- ]* n% `4 n% t' q    for(int i=len; i>1; i--)
    {             
$ e! }0 G, {' P$ E4 |, h# f        swap(A, A[1]);
        HeadAdjust(A,1,i-1);
3 u! {: R. X! K- \    }
) W' c1 ?* x1 j' {/ I& A2 O}

1
2 y+ a- u- u' ?8 E& M2
/ j4 ^. o- D. y3
) z. m! k- i+ ^% C4 k/ }4
5
& Y6 }1 P6 b1 E; e3 A- f1 j% X6
7
' ^% O( @) S: O$ S& U# C+ C( n7 A4 Q8
0 p2 y. q! z2 I5 n" `9
" a/ }2 B6 Y" K: P! t1 k0 k10
11
12
3 j' s, a! ^) I; c13
3 l/ v9 q2 x& P4 T, P+ |/ j14
15
16
/ a* ^+ |# O3 L3 a& }7 P& F8 D% ~17
5 g8 Y* C; S2 S) f18
19
2 F% c: x. H# f% [时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

空间复杂度 = O(1)
- I  N) w0 h# z* K$ q
% f2 R8 Q0 q9 g' q- v+ @% A结论：堆排序是不稳定的
) B  i* s' _; b* d3 {7 F( z- _

④ 补充：在堆中插⼊新元素
, R. X& q( G) P4 S* F0 o对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌
; C1 U% V% w. I
4 T& x7 g: {( k/ \) {

⑤ 补充：在堆中删除元素
# Z- {: G3 b6 M# ^被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌


: X; F4 O3 F- z2 T( a: ?# t

( X: a+ t1 ^( Q0 e+ T! p* b6 y
4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个
1 o% T5 Y6 {3 v1 G5 d( ?
6 H1 H7 z6 J5 g3 K① 明白什么是“2路”归并？——就是“⼆合⼀”

多路归并：
$ V! }  h9 P; @; W
3 ]9 Q; E6 V. @+ P' s0 q6 w! d) z& p
( {8 Q0 r* {6 R2 f7 X% u7 U② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
! B% J- j1 h- \  \# q0 v
B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

' M9 C  n4 j( D1 G# ]8 P7 o③递归进行分治思想【MergeSort(int A[], int low, int high)】
# n( i' H" j( J; q

; Z( ~7 C% f) @# W" n8 o4 n④ 总实现代码
// 辅助数组B
, c- ~! F, X" J' z  C, `int *B=(int *)malloc(n*sizeof(int));
8 {4 `1 G( z, ~* a8 m* A
. n: \) I4 I1 w( l* I7 y; }// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
! m; L& r- _( ], d3 H/ p/ _2 u& P3 i; Yvoid Merge(int A[], int low, int mid, int high){
- _# C' E' c6 k3 o    int i,j,k;
! w6 H9 E  B2 u) y# h. B; f    for(k=low; k<=high; k++)
/ ^6 V0 `+ U$ N% W. f        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++];
5 [- V5 ~: p4 X1 T! X" e: b' Y        else
, S( |% V3 I/ r2 M: z            A[k]=B[j++];
& E% k& r& ~8 [3 q    }
    while(i<=mid)
        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
' y5 C( ~6 y+ P8 @" M}

5 ~; E+ j9 q( g% [1 ]
// 递归操作（使用了分治法思想）
void MergeSort(int A[], int low, int high){
    if(low<high){
# y7 P' C3 m7 P! w6 ^% @; X        int mid = (low+high)/2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
; q- f0 V( P7 X5 |* ?- L* G5 G4 g        Merge(A,low,mid,high);     //归并
# S: t  X3 `) Q7 C    }
: H- H4 `4 T" f5 ]/ y6 S}
& [- S0 G1 V6 j5 ^% t# F+ u8 Y
1
1 o4 Y& R" u! h( t+ S  W2
- a* E; e6 Q" t- i3
1 Y* b/ Y1 C/ h$ E* m8 B9 ^: C4
5 U% H2 \5 d: l' l- @2 Y) D5
% |! H! F' a. C& Y6
7
8
5 `% _( ~9 e% |4 Z1 w6 t7 d9
10
11
12
13
9 A1 X) u- f4 W14
  R9 M* I$ p3 p# F( B8 r3 q15
0 |7 [( I1 G* E  Q! [& x# K16
17
18
6 y, B" [  h- e, `' x19
$ s0 ~3 H' {; e- o' s20
: T0 _" t9 A( ^21
6 \3 B/ E0 o1 |- R6 H- |5 t22
* c& g* T( k+ R; E23
  Y0 o8 f( k- K% y24
$ n4 W9 U7 j; Q4 O25
  ?' F! g& ]' x3 e  P7 H0 K6 y& i26
27
0 u# ^$ g+ n3 u5 ?; |; [28
* Z$ s# x& \% x8 L8 O29
30
& {& W, x7 ^* T4 B时间、空间复杂度




6 f9 P6 a* q8 U8 F7 L9 F5. 基数排序
8 x. s7 S5 C3 L! J# `$ a直接看课本的过程图来理解P352

再看这个例子：
0 T' ~* I, W& {' L7 a- x6 i

算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
7 W) g2 L* W) a0 O' }基数排序擅长处理的问题：
①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
: |1 ^9 P5 {& ~" a③ 数据元素个数n较大。
算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
4 H/ g( h/ M% J5 b5 U+ v/ j  m空间复杂度： O( r ) ，其中r为辅助队列数量。
) |" I' w. v6 |9 g/ d稳定性：稳定。

* b5 Q% g! l: l3 w& e. P
: y5 X1 o, A7 d& F1 t内部排序算法总结

0 e1 S/ W) X! G6 {% H————————————————
( ~, J3 T1 s( [2 V版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
, S" D  K- a" o+ u, v; e原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969

6 E, @9 b$ t& s7 K% @4 ]