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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
( X5 ^/ Q6 ?: V" f; {0 k7 R排序
6 R% ^# F" M0 u  e1 f- y1. 插⼊排序
# N. |1 u3 _1 g7 {, ~2 a. T4 @（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
, P- t& w: l$ Q* w/ n* I4 |1 y% O8 r& g时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
1 `3 [8 f( D+ J% y% n6 b时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
时间、空间复杂度
2. 交换排序
# ?8 x  i1 Q2 k) O7 N% s, k2.1 (稳定）冒泡排序
5 w- i6 O2 k& ?/ u. b时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
. @# ^7 ?% F( M# U/ }时间、空间复杂度
6 k# B& S8 g: I3.选择排序
. T! m) b; N8 _: W; n  S. Z; }3.1 （不稳定）简单选择排序
; U6 {2 R& w  ]7 x6 B4 Y时间、空间复杂度
3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
' B8 ]4 x  K& H0 A, u: |③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
+ Q. e1 W: ?  e4 y$ Z8 O. p8 i时间、空间复杂度
④ 补充：在堆中插⼊新元素
2 D* G+ ]' `" h6 G8 @7 H⑤ 补充：在堆中删除元素
4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
! |; z+ D1 K+ M( F1 p9 b② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
时间、空间复杂度
) O) C( ~* ^% d5. 基数排序
1 K# D6 B0 m# H, M, s内部排序算法总结
! x/ d5 T6 W" K$ K- v8 y排序
5 [$ y: p* W& D. u0 h排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

5 L# k7 t7 \9 f* |排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
6 P, ]+ ^6 V- l2 k2 k! J) L$ K
+ L1 j" [8 e/ z; ~' s( }9 r算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。
" H0 ~- {, C1 q* f% @% \/ k
  j7 p6 R% Y6 w# i
排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
. ^4 e# [4 s! o! j0 ~3 _  M$ G/ ?3 A外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

6 m! X# E. ?8 y% s" I各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

$ K: q, m! `5 K3 n! U0 P
. p8 U3 A8 \- k. ~
1. 插⼊排序
% g! i$ c6 E3 i! Q: p7 a（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

算法解释：（从小到大）

7 O8 S: I7 n# d/ x/ h2 _$ @
. [* P( c- p5 \. ~! o5 [算法三个步骤：
" P8 h+ t: N, U. P' I( ~
先保留要插入的数字
往后移
+ n2 f9 Z" x/ Z1 e  Q插入元素
; W3 p! H% K* r
. i5 H$ X+ S0 y// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
1 A1 |+ ]; n6 ]- O  `6 `/ H* C    int i,j,temp;
2 U2 X& L6 |8 P- p, r    for(i=1; i<n; i++)
    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
        if(A<A[i-1])
8 z3 F( o+ |2 q' }* o, O        {           
            temp=A;  //保留要插入的数字
$ ]2 K5 I( [) i
# F; k$ H0 K6 K; J6 G            for(j=i-1; j>=0 && A[j]>temp; --j)
$ X% F+ t+ O9 Y& |  S                A[j+1]=A[j];    //所有大于temp的元素都向后挪
# O# ?  q2 @% ~) v
            A[j+1]=temp;//插入元素
: U) M- c, z. U4 w% n        }
1 S% O5 c7 v. @& @5 k3 N* o    }
% R! V" b! E* L$ A}
6 k! h* j  L/ b" m2 E2 S5 C
1
2
* l7 u; ?8 e1 |3 {3
4
5
6
7
8
9
10
11
12
8 w8 r3 [6 D! j13
3 N1 \6 m8 ]$ V& a! e4 I14
15
16
17
5 R' s! v! C3 {  B" r6 F& _用算法再带入这个例子，进行加深理解
" K* G; D- j+ W0 e' {
+ C4 _2 r: U+ k; P/ I6 F
带哨兵：

) X* c4 G$ B! g. b# g' [% ^/ w
补充：对链表L进行插入排序

void InsertSort(LinkList &L){
: M9 M. |5 O9 K7 c! I5 L. g    LNode *p=L->next, *pre;
    LNode *r=p->next;
    p->next=NULL;
    p=r;
    while(p!=NULL){
        r=p->next;
        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
/ w, r2 `7 J( c2 C9 M4 Y( ~        p->next=pre->next;
5 V) X$ Q4 x8 g8 `* j1 z        pre->next=p;
0 H" F  W& S9 P' ?        p=r;
    }
}
1
2
3
4
" e8 Z& B8 R- a" b1 `9 ^5
6
& D# Z# a1 d, ~  Y* r4 @- a$ w( u7
8
& [" V3 `6 L: l9
10
11
. z; O+ _8 v. q- o$ L. _% O: a12
3 d; e2 l5 P3 ?, J% @+ K$ _3 U13
9 g, P0 n3 }, F0 t* f* Z) h14
4 g8 {8 ]7 U, k- E15
时间、空间复杂度
) g, p" b5 g& T% h

' o( a/ a4 E+ R. `$ c最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
6 |1 p- m6 S; k: n9 n3 m/ ^! {最好时间复杂度—— O(n)

2 ^! N5 c3 V( o最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
2 s- }+ D9 ^! U. T/ w: e) Q第1趟：对⽐关键字2次，移动元素3次
$ I( @8 I( U3 m# D6 B4 i: _第2趟：对⽐关键字3次，移动元素4次
…
6 t1 _& [0 ~  x: W9 v/ C: l第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)
# Q/ g9 c0 [" p
9 h% N3 m: S: O: W  e

$ \( c* S8 b+ R+ G3 q* Q

% S/ ^* G. S5 i; M9 |* j4 ?; A; o+ u, Z（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：
1 E% R5 h& O' v/ @5 S' f
0 I1 G% r4 g1 L) v4 G! ?4 E3 i
9 y" e. o- w- }4 \$ U
+ O( h3 \0 H2 ^7 T! i0 u8 q! ?+ g//对A[]数组中共n个元素进行折半插入排序
7 s/ U( _) b2 g5 Jvoid InsertSort(int A[], int n)
2 H8 m8 z! |9 w$ T& N0 c{
' y8 c" W9 H( j0 @4 Z" [    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
    {
( G4 l% P& x2 H- q; b* w( z        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
# w% N+ p1 Z2 \3 a1 \# o        low=1; high=i-1;
; e5 e$ x: c/ M7 N( t        while(low<=high){            
6 U* U5 ^% h, r) w0 M            mid=(low+high)/2;
            if(A[mid]>A[0])
                high=mid-1;
4 m% ^5 V0 R" f            else
                low=mid+1;
        }
         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
, Y5 {4 |2 D; B2 T& b) ~# }: q) V, L            A[j+1]=A[j];

. }1 c2 b2 }2 N  |        A[high+1]=A[0];//插入
" z  W1 m, C+ d! y0 R- X: m    }
}

1
2
- t: W7 J2 B. m$ J0 E% q- F( C3
+ D( y; x8 J. }4 t4
! ?7 L. C" g4 e3 O( R7 Q5
6
6 C, G# I4 ^  ^5 X" \2 m7
8
9
$ ?" C4 _, r  x. ~( ?' G10
# o8 D) G1 }$ `% v1 Z( I* Y. [11
! l# J+ X3 s, a* R12
4 Q8 G7 f7 j& [13
* r5 G6 ]+ c3 c14
  [- C( r8 L! x, F15
16
17
' [- {2 ~+ `3 R1 r18
" w5 k- J7 L% L  l# a$ I! m0 W19
20
/ i+ @- k) Y; w. }21
22
3 q2 ?* t. R2 p! f0 o2 Y23
时间、空间复杂度
空间复杂度：O(1)

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


（不稳定）1.3 希尔排序【多次直接插入排序】
, o! {5 G0 k% r# v- m* W是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
7 ?6 D# U! g/ y4 n1 S
2 s5 v1 O* S* b4 s算法思想

3 E6 a# L0 c8 h/ X7 u希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
) h, Q! \3 y% R4 n- P1 v; e2 ~0 F随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
  o) u" f- P. H7 g; Z2 j& C' N图解：

, i0 q7 [6 k6 t2 j3 c1 p* y; n
; ~9 P; c+ [8 h1 [* ^  _% c" I4 |# z
5 J7 s2 R. Z# P& I代码实现：
3 d+ x9 F4 ]; J/ g6 d% x! b) _
( o! t5 P0 J' x) n# v1 f. e1 ^9 {//从小到大
void shellSort(int* arr, int n)
* I% J3 {; P) u) R# q# n5 G{
        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
2 E- l$ A" u" B; Q" X( e        for (gap = n / 2; gap >= 1; gap = gap / 2)
0 ^  A! k9 p5 ~% X# ]3 @5 L6 v. m        {
6 S( _6 v" B' Q. O% J1 z            //**********************************直接插入排序（只是步长改变）**************************************************
) s( L9 i! _3 v            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
                if (arr < arr[i - gap])
" B7 Z, d- {$ R- H( ^                {
                    temp = arr;
* B  Q, P3 K* @. \: M% H
% x* {) Z  A5 s6 K- |4 t                    //后移
8 f9 C$ e( g: \) m                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];
# r5 w) b, U+ P9 {7 J( C# }
9 u- S3 {2 b6 [% B; W9 @, t                    arr[j + gap] = temp;//插入进去
                }
8 d+ \+ p% M. O! I1 y            }
" a- d0 T% N& P( f. F9 o3 H% {            //************************************************************************************
. |+ v: {! H  @- v/ x7 Y& ]        }
7 W0 \: Q% A- [& g- }5 \}

% [( a( P5 K: l$ ~1
2
' y9 {0 N% @; |3 v  E3 m3
. r9 e- N" C5 }  v4
2 j9 q' ?' ?% }" Y2 [5
6
7
8
/ a4 B0 D& v4 B" N9
2 f' q0 L  e5 }. G: b9 T% i10
11
12
0 d" D/ q: n; V! v# W" @9 z9 ~13
/ ^8 @, H% u, q- ^4 N: u4 y14
15
9 f( B9 m5 L" s16
17
% q/ P' a. n* q18
19
20
' ?1 @+ N  r7 C# U. N. d' o. x21
% X, g, F6 Z8 I, E4 m" [22
& x% S& S/ [/ r3 M23
24
" s  ^" q, r2 W$ P1 Y3 z# d时间、空间复杂度
$ _& C- V0 D( m# {' Y# X空间复杂度：O(1)
* n' U4 m8 [; L% f: I5 R: D
4 p3 m9 F4 \8 j+ P' L8 O时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
3 G7 f$ D- o! `1 J2 B
稳定性：不稳定！
. \% S* s1 G9 ~" ~

. {1 A6 V  N& ~* g
适⽤性：仅适⽤于顺序表，不适⽤于链表

. E* v9 U6 x, i" F7 [
4 Z, P" W$ `9 {: u% m" \, y5 q" Z
7 \1 Z4 p4 L& Q; b5 z( D# U0 ]6 _2. 交换排序
4 C. A7 R& N/ |- [2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

# [/ s' V  t+ t8 E6 n每一轮比较会让一个最大数字沉底或者一个最小数字上浮
. a. j7 L0 Q( r1 c
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
0 n# B$ E' z1 m0 l
- O* L- ]) {* T+ A实现代码：

+ `+ k3 l9 y3 Q# m" J2 T* j//从小到大：
# J6 T) h: `# p. ~- ^1 N2 R' o9 r/ Y1 j3 zvoid bubble_sort(int arr[], int len)//冒泡排序int*arr
{
2 @2 {: X0 @8 Y" E5 I. [2 Y8 O        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
        {
5 S6 x. Y* d6 R$ O                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
' h$ {3 p8 J. x0 v1 p" q0 W% @# T                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
                {
                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
                        {
                                //交换两个元素位置
                                temp = arr[j];
2 |8 }% ?6 D  I* q                                arr[j] = arr[j + 1];
5 s6 W4 @, D) T+ I; F                                arr[j + 1] = temp;
2 L) v$ |( |, ?+ I" E( f* z3 t# w                        }
                }
9 `# T4 N% X; c( S" `. h* ~4 q        }
}

1
0 ~& F3 g" ~# j0 P2
3
4
5
+ r2 Z1 D- K; b# Z; O5 Q6
/ A% [% L0 Q  J" {7
8
9
' u, D- j% Q5 b, X/ S10
/ ]; j, v) v# R4 G( B4 F( y9 p" i8 h9 q11
. p( P; x1 Y+ A+ N% `: @8 G: C12
13
14
- V) l4 `9 f! L7 ]15
16
$ m8 [/ c$ t1 o* E- O& A17
7 s: m8 u4 Y+ \8 p5 E18
19
: Q& [1 D0 g, N) Q4 v优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
; L) z7 _7 f+ ?" X
//从小到大：
void bubble_sort(int arr[], int len)
{
: `+ J5 s3 \. [" d) u5 V        int temp;
2 F  @0 x  K/ |- U* n. P3 c4 f" T        bool flag;
        for (int i = 0; i < len - 1; ++i)
" V- i2 b: z" W; L  i        {
. c( \1 {& q$ p" b" |0 `/ L            //表示本趟冒泡是否发生交换的标志
                flag=false;
               
  b7 Y/ J/ m/ x                for (int j = 0; j < len - 1 - i; ++j)
! T/ K& `7 {4 ?) N& q, q/ w                {
                        if (arr[j] > arr[j + 1])//稳定的原因
0 n1 B- m. l0 B/ e: q6 U6 D9 Y                        {
                                temp = arr[j];
  \4 n- f% X- g' O% }" t7 z                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                                //有发生交换
# w! A, x& |- u, O6 p" M' @                                flag=true;
                        }
1 G( t& P# p! n5 o                }//for
4 k: O0 f# F+ ^* u& n" _. w               
- [. P: t" o9 o1 R' X                //本趟遍历后没有发生交换，说明表已经有序
                if(flag==false)return;【1】
2 C: \$ a: y- t9 L* ]        }//for
}

0 q. K1 X  [7 Z7 \2 B2 M! j* o1
  J/ l3 F5 _$ _- Z! b9 V2 T* K2
3
4
( |6 S/ E, L" Y1 Y5
6
7
# `/ o# x7 K' D8
9 p& u) Y, q* ^3 A9 f& Q& |9
10
11
8 m: C# ^2 d, j" H4 K' a' J8 f12
13
' {# F4 t  p! C14
15
16
% g- _) @' n' }4 b3 ~. p17
18
, f) t9 ], a& S1 @19
20
" V2 f" \. L' z2 H8 o21
22
( f0 f, C( u% i  h' C- ^( q23
1 B$ A; z6 A5 {$ c2 X24
25
26
# F- O" Z+ R& o% ~时间、空间复杂度

* L& @+ [0 Y, @; l5 C2 R6 k' m4 U( ]适用性：冒泡排序可以用于顺序表、链表

, F7 r2 S' @5 u; a- M; H

2 k0 k( _' w3 r; G* J) R, C& e9 f
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
- s* i$ w$ M: V' T: W7 Y算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
) h0 i* k0 C6 W8 P7 w通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
: e! N1 b8 H4 x$ g$ A再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
: {" T3 o$ N! d* {" q
然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

& |) O& ~% d# n, c$ b6 V% B划分的过程：
4 b' x$ S  K& g' a. O2 G! J. e
; Y, h- V5 R+ g( K: r3 y/ J初始状态：取首元素为pivot，定义low，high指针

首元素为49
high指针指向的数据小于49，就放在low指向的位置
5 @! D+ E1 h3 h- G& u1 Mlow指针指向的数据大于49，就放在high指向的位置
, `4 Y' ?2 u! _0 U6 N- s/ {; v
1 K: a0 F' }# s3 k) [

1 D/ Y6 D; X( G2 [# G

// 用第一个元素将数组A[]划分为两个部分
' t- I5 t8 B0 v1 fint Partition(int A[], int low, int high){
        //取首元素为pivot
$ Y( ^6 k1 M0 }    int pivot = A[low];

7 w# g: P7 f6 Y0 l& w    while(low<high)
0 B6 M' O3 z; J( K    {
            //先是high开始向左移动
. a( r+ r5 T- T' }2 P% g$ [8 e% o6 T        while(low<high && A[high]>=pivot)
( S7 t! p" }5 s* }            --high;
* O; v/ Y' Q, m5 ~6 ^. b; \        A[low] = A[high];

        //随后low向右移动
        while(low<high && A[low]<=pivot)
; f1 P. z% V. b! O2 T9 ?7 D7 P            ++low;
        A[high] = A[low];
    }

    //low=high的位置，即pivot放在的位置
/ }% x0 M( r+ |( Z3 C/ W    A[low] = pivot;

    return low;
}

// 对A[]数组的low到high进行快速排序
! ~/ B' `( g1 I# \( s# Z+ A% R( e" I1 Evoid QuickSort(int A[], int low, int high){
5 d9 B3 v4 F/ k4 J    if(low<high){
5 _0 O, p# T, Z9 J$ Q3 K3 |; W        int pivotpos = Partition(A, low, high);  //划分
: p" W; A* S1 Z/ D. {        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
( a& h$ F/ k: N  ~* Y    }
}

1
2
3
% X7 G0 v0 _) W4 H* G4
5 F  O" L) V$ `4 `+ Z; C& g6 L6 ^5
% O3 f8 b, ^1 `; G6
7
8
9
' y! g4 v9 s# K4 s& w9 x0 _! H10
" K2 r7 B. i$ y: a11
12
0 `4 V5 g& C1 h+ i13
14
15
' t8 f. I  h$ X' N. `16
/ K/ \& W8 B% X8 e  b17
* e+ ^  x2 r% {  n7 R1 G% ]18
19
20
21
% c! N5 r+ b7 L- B6 Y) ?" S22
23
4 N% x& m. p6 X$ e! }24
25
26
$ e" X6 Z0 n6 i0 i$ m1 l27
28
) t2 H! S+ s$ k$ s29
30
# m) U; {3 _/ K31
/ S4 Q. ^% z9 I8 E( {32
时间、空间复杂度
6 ^* {) d9 M! s: L& P! G/ K
7 U# m# j7 R# ]$ f) q/ R) a
1 Q! o( {) X; `- `7 g/ |2 c0 g把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

" R6 b2 O- @6 T, M' h' k/ W% C- X/ yn个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

时间复杂度=O(n*递归层数)
' B+ H, r5 q  d2 |' |最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

空间复杂度=O(递归层数)
  y" V" G& m( h0 n; c$ o) X最好空间复杂度=O(log2n)
& S5 Y5 e* [* s! s0 ^$ I最坏空间复杂度=O(n)

最坏的情况

: Y: d0 E( E* {! E  n
, |' O7 I5 w% |% Z5 H# L7 C' U* d
⽐较好的情况



6 o# m" o. A4 F2 b# [不稳定的原因：
8 h; X( `( \: o/ L# R1 h; G
1 N/ n. g- Q, ~( w

1 b6 M  T+ ?  z2 [; L$ u6 \1 u
: L: K. R& u: o8 S6 o
2 T5 r9 M8 r$ S3.选择排序
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

" N$ R+ S4 r% \3.1 （不稳定）简单选择排序
8 W( L2 _  h6 w5 @: U" z" z- ]算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
, [8 s; f( b6 }" m6 b; e% F5 t
% A8 |4 q* w( L. P: y' }

8 R4 P: R) Z6 @# J  @, J// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
/ ~9 F3 }2 J( f    b = temp;
. N: E( Z* y/ ~# O" M+ ?5 G}

// 对A[]数组共n个元素进行选择排序
5 }+ e# R( C) T# S) F; xvoid SelectSort(int A[], int n)
{
        //一共进行n-1趟，i指向待排序序列中第一个元素
" S# \- R) f3 r2 e6 {* J    for(int i=0; i<n-1; i++)
    {                 
, U/ Q0 K+ X1 D        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
# ], \1 {0 [) W" i& V6 b+ \            if(A[j]<A[min])
                min = j;
, C. h" h2 q2 v# L3 i        }
        if(min!=i)                     
            swap(A, A[min]);
, N) i2 M9 y  d5 F9 |5 e% N    }
+ C) J# k5 O0 ~! U& u& @}
/ J) i+ a4 t  t$ O) G) v# H" w
1
2
9 m$ Z8 [+ s# I( x: Q8 b$ q3
5 O: E. O* O( H( p5 D4
0 X' D* H) Q6 Y/ j4 b& L+ N, f; ]5
6
  G/ I0 F( W# D+ ?  e7
8
9
& r6 o  G. w! ?% Z* c10
9 l5 d9 Q1 F& R' L0 k) d11
12
13
14
0 x3 k) L% L% N- b2 }9 }15
7 u+ R9 }( d1 v7 t16
17
2 K7 p2 J7 @1 q7 j2 {) k18
) f9 V9 E" B4 D* b* j+ ^19
20
21
22
补充：对链表进行简单选择排序
4 u; N. s. {& L5 G" c
void selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
+ ^3 v4 W" E. I7 {. ^: F5 u    L=NULL;
7 r& r6 Q: _7 f; L5 `; V/ h* L    while(h!=NULL){
+ a& W$ T3 u- y% \- G        p=s=h; q=r=NULL;
        while(p!=NULL){
            if(p->data>s->data){
$ f2 `/ j- `* ^6 U. e3 ?* R, q/ X                s=p; r=q;
            }
            q=p; p=p->next;
        }
, r; D+ m% g6 K. p4 u7 x        if(s==h)
9 U0 f6 Y5 z' T3 O: D! ?5 x            h=h->next;
        else
3 N# ]9 q2 F! v' j7 j& Q            r->next=s->next;
        s->next=L; L=s;
    }
% u4 e3 l* R( Q4 [1 Z* `! J}

- X9 Y" F; a% D! C1
3 e/ [9 q' N- F& U2
3
4
* b3 y( h2 @1 L5
* q. N0 j0 ]4 i2 ~& d3 J7 e0 h' o$ R6
7
8
9 ~* ^; z0 `! @' z/ g, N0 i9
10
0 C' ~! i- U8 F$ w7 U& k! T11
& }" i8 ?3 i, ^) i5 i12
13
14
15
1 ?5 S3 R" [' A' \( b0 q7 L16
* S: [/ X) h/ T- P2 S17
; Y, M, x( J- Q: v, \+ W18
1 {' n* F, P0 v5 R- u时间、空间复杂度
. A! R# ^$ u# n; `: m5 p
$ [  i; w* Z: ]. `$ q) g

+ S4 T: p# i7 ?. Y6 Y, B! N
适用性：适用于顺序存储和链式存储的线性表。
! F8 c6 e7 w. S) r


3.2 （不稳定）堆排序
& H" j; {, ^/ j( S) r① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
" r  q1 y. x- v  X堆是具有以下性质的完全二叉树：
  O0 m6 P. i; g# w- @( k每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
' p: c5 P  s& z# q" ^9 J或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
2 l! E% ^, ?; x( J


即：
% c8 v4 F7 d4 @  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）—— ⼩根堆（⼩顶堆）

② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
- q: i: U4 B0 O/ ?% k
在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

% e& t  ]3 n- b* F' w检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换
- _1 N* C8 ^0 G: t2 l" v
& w4 a& d# S3 y& P过程例子：
: i- U1 {& V0 g0 i, ^: v


1 J6 B; [8 Q" X3 q6 P1 |建⽴⼤根堆（代码）：



// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
0 O: m% s- X! x9 O    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
9 O6 U' u9 M& _/ ~- t}
  @+ B* q: h- p( R
// 将以k为根的子树调整为大根堆
: K5 V/ `  T/ w, _4 P! Tvoid 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++;
8 J5 ?7 W( R. ~# ~) D& y. u( s& p        if(A[0] >= A)
: D! b2 }. y8 S4 h# P; a; m            break;
3 }) Z$ b( x" B! i0 R- o        else{
            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
) A9 V1 |; y1 B        }
3 S% ]( j  V4 D: w+ J    }
    A[k] = A[0]
}

+ T  \, _; n0 L! V. `- l5 j9 k1
, Y. ~" y5 Z/ B* X2
, p  W' E8 c" c+ @& D3
" [7 a* @6 ?9 s  `: Y1 x2 e' R4
5
/ d1 P) U5 c# s6
/ \4 z% f. k0 n1 \$ Q7
) u) w- _+ p- _0 A* K! F1 U: @8
9
10
11
12
13
14
7 i$ J) M0 w- Y0 Z' p15
16
& `! w* C3 k3 D; i. N17
18
1 f- {1 o+ j9 O8 I( [19
3 a1 E; q/ |: v0 m; ]1 X20
4 c7 y+ a; c  N* J; v$ z: X21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
( e- G: d: h- P. j4 d( F0 R# T& q选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

# H3 g7 W+ R" c堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
! C$ e% [: k9 W6 q3 [
3 `  K. ?4 g- m1 n! f过程：
6 ?5 `. m. p7 O: K  n1 ^
0 t/ Q4 G6 l! p8 k) O// 交换a和b的值
# l# D5 l5 Y0 b- }3 b. i+ Nvoid swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
) N) q# ?/ B* B7 E4 z/ C}

" o4 S, H; b) U& x% ^0 u// 对长为len的数组A[]进行堆排序
9 \2 X# N1 A/ Q% D1 w% u* Svoid HeapSort(int A[], int len){
        //初始建立大根堆
    BuildMaxHeap(A, len);                

) ^' {) v/ G5 X    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
    {             
        swap(A, A[1]);
        HeadAdjust(A,1,i-1);
    }
}

1
2
" b4 O* P: l9 P3
! i2 Z+ b2 Y8 |/ }7 ?4
# F/ @/ R( k) {, I8 T, X5
% M  h  E: I( m+ w6
0 f: n' K( C/ j7
4 G+ f" N! L5 @8 T1 r8
9
. Y4 j7 a& g7 [( G  A6 B10
7 U6 f7 v. I/ N3 V* b11
12
4 e9 P# w* D  w13
( C, B( c2 ^. C14
15
1 p# C, Z8 N. Y16
17
18
19
时间、空间复杂度
( o9 E( N1 q& X7 ~8 B/ W建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

) K; [9 A3 r8 x, n' K) V  K9 I- G空间复杂度 = O(1)
! Y7 K, ~$ w$ P; X4 c
8 ]7 K. ]$ [3 F( G0 K结论：堆排序是不稳定的


④ 补充：在堆中插⼊新元素
5 k+ l/ w/ m0 Y  }: N! L. `对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
9 n+ z' D) x+ V新元素就这样⼀路“上升”，直到⽆法继续上升为⽌

5 [, j% j, M8 |0 ]! V

⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌

" B! X, z" f5 Q/ e* k5 y/ Y
" C* u0 K! Y- K/ i( m9 n" w: z+ \


4 L8 U3 K* a  ^9 w4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个

① 明白什么是“2路”归并？——就是“⼆合⼀”
5 J( u/ ^! e8 v3 A
7 p! ~' L$ |! j多路归并：

' I3 C" [$ }4 ]" N
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

+ n; c/ B3 l4 O# X7 oB[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
& @+ i$ |. B1 I5 n" @% E
  b; B1 Q/ W) F! {③递归进行分治思想【MergeSort(int A[], int low, int high)】

, J8 y4 \7 D8 o4 y0 C
④ 总实现代码
0 u% \* R+ h. P" h, ?  z% b# h// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));

" k% [- K2 _8 k( [5 J6 [9 a// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
4 n9 b9 b  X) O; c    int i,j,k;
    for(k=low; k<=high; k++)
" s' d/ R0 V$ K4 y4 ~8 ]( f        B[k]=A[k];
* V/ l; ]/ F0 Y, ?) m    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B<=B[j])
            A[k]=B[i++];
        else
            A[k]=B[j++];
    }
  n$ w9 T0 c, D3 Z    while(i<=mid)
        A[k++]=B[i++];
    while(j<=high)
" i$ H! m! x# L7 n# v6 `+ R        A[k++]=B[j++];
2 m9 w! Q- ]: U7 E% W6 J" o. d1 ?}


// 递归操作（使用了分治法思想）
  Z  A0 H. `3 v+ S! w% qvoid MergeSort(int A[], int low, int high){
( f8 b# F3 H9 @  j  I3 m  ?* j    if(low<high){
        int mid = (low+high)/2;
0 [8 B* D" i7 N5 @/ @, H: B! q        MergeSort(A, low, mid);
1 N. P: \: E  g        MergeSort(A, mid+1, high);
7 x3 Z" p4 w) S( j3 Q        Merge(A,low,mid,high);     //归并
- X3 C& t' @4 y$ V9 j( S0 c% `    }
: _2 I% d. |- K; k3 x+ d}

5 f1 n6 L$ f+ e/ S) G  V( T1
2
/ C: `( R6 {/ e, c# M# z9 [3
4
5
1 N  q9 A: Q/ C+ D6
5 [( ~7 Z' C, i5 R) G/ w7
! G1 }1 e3 E' j. ?4 Q' ?8
9
5 Q! M. V  w1 N, Z( p/ M. _10
% x0 t- f0 I# _9 y0 z( ^11
12
13
+ [4 h' k) a" W% K3 C& R/ T" o14
15
% G' y" j9 T# T8 e16
& w2 O9 i9 v5 J17
18
0 D4 P+ p' D+ \* @6 T' K; K# {19
- J; M- ]3 N5 O) h20
. `8 o  @6 |0 e: x' n/ X21
& T- g7 o% G1 Y  m* J. Q  \22
23
# Y! U& P) U: o, c& [1 t* A3 |24
25
26
27
& d% v- B2 `9 A1 D5 Z! m28
29
$ y& J3 c, C2 ]4 {30
- d7 j  I5 w1 E+ @4 G时间、空间复杂度
9 w0 i/ z2 H8 q# z! i
- P/ u& {; i+ M6 P/ E+ B- Y

3 \6 Z2 E% N4 a1 P  Z* w
# u1 G( I" l7 U; e, m% z5. 基数排序
直接看课本的过程图来理解P352
9 z, L. A- m" K0 n7 l2 r
再看这个例子：
0 l5 g. c6 k% J: M2 @

0 h+ `& C& A5 f! U; @算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
①数据元素的关键字可以方便地拆分为d组，且d较小。
3 }! g9 H; U) ]; b5 S7 ?9 A1 s②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。
算法效率分析：
! p6 n7 j& Y. @+ z时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
1 L6 b) X$ j) ?稳定性：稳定。
; o. C8 D) P7 y2 E! j3 x

- A& l* F- U- ]内部排序算法总结

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


1 W* F0 `  g9 E2 Y& j4 h  w2 O( j