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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
2 t! P( @. N+ f! W" x5 Z8 q' B文章目录
' L. A# A6 T0 ~  Q  N/ A3 r- [排序
8 I! K( q* P0 j8 c; h1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
时间、空间复杂度
3 t7 |) |# s7 M4 W1 X（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
2 P: [) Z7 m% o- P/ S9 z" _（不稳定）1.3 希尔排序【多次直接插入排序】
5 w9 p2 ^7 n  ]  x# J+ f) I时间、空间复杂度
0 P# m7 G( V: G) ^9 p. W2. 交换排序
) ^4 T: q5 c; @7 s" ~2.1 (稳定）冒泡排序
& ?+ d& _0 K& a+ A( e" \& \, i时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
! r7 |, D2 x) L- S! u! i时间、空间复杂度
3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
3.2 （不稳定）堆排序
$ q3 t- V" h  Y; B① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
. C% h; }4 S& L6 M② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
3 u/ p5 t! Z$ ^' \③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
) |3 T5 ?$ @- m- F! A/ y/ X时间、空间复杂度
④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
7 k0 Y" K! E# d( b0 L/ `( u1 Z3 E4. （稳定）归并排序
. M" U$ h8 s( t2 q% E① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
5 K) T! q2 v- z. v% o' V③递归进行分治思想【MergeSort(int A[], int low, int high)】
. U; w1 L3 Y5 Q) j$ W  Z④ 总实现代码
时间、空间复杂度
5. 基数排序
, E6 H. Z% r8 o; g4 Y5 q: N9 Q/ t内部排序算法总结
/ E  H& K8 M8 u! V; c排序
9 O2 J% {( n7 ]% |排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
( G2 C5 W' ]; ^) E2 d
排序算法的评价指标：时间复杂度、空间复杂度、稳定性。

: V* E" f8 s8 n0 j, i. _算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。
0 `) e6 g8 e7 o, P# F6 n7 C8 @
' L% ^6 c( z) U% I
, _' P. j" F2 P% a: ?- ^排序算法的分类：
' I8 ]$ h4 L6 s5 i, u内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
) Y6 ]6 G5 n- j& L* g4 I1 d" h/ Y
8 s. l2 S! C( d! j7 _0 ?! v各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
5 A/ _; {* r5 S4 a% g1 V9 S
6 C% b3 T, ?3 Z& t

1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
* Y4 o8 p8 X% v0 ~, \% G. i基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

" G$ r5 [3 g: q! ]# H3 e算法解释：（从小到大）
1 V; I. q2 o, Z/ m
: w1 J3 O0 H7 k; ^+ R/ }! d/ |
' c, W: X3 x+ l0 i& v算法三个步骤：
0 A. s" [2 N) y+ f2 L
先保留要插入的数字
往后移
插入元素
$ u8 \. _9 B0 [' A& T
5 T% V; J6 j' g" p5 H, {3 i// 对A[]数组中共n个元素进行插入排序
; P3 ~3 M3 ~) J; n1 _void InsertSort(int A[],int n){
. V% i4 B; |1 ]6 m  ]( x    int i,j,temp;
+ D0 c& x: m7 i1 @7 Y    for(i=1; i<n; i++)
    {
; C8 m; L" D0 ?+ t5 G; s            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
        if(A<A[i-1])
; y9 H6 i  P5 b1 t5 t        {           
- a, [4 R! v1 s  @            temp=A;  //保留要插入的数字
; |% Z5 f7 x$ V8 z" P* M. _
            for(j=i-1; j>=0 && A[j]>temp; --j)
0 ]* g% ~6 m! S& ?8 g2 b# F0 u* N                A[j+1]=A[j];    //所有大于temp的元素都向后挪

            A[j+1]=temp;//插入元素
        }
    }
- J& [$ i) c, W. x}

! D- I6 q/ N! e4 l- [1
2
8 p0 O8 s( |& X3 C' w3
4
1 p/ @* u" m( X# m+ I5
; {4 |$ x/ }7 F5 V0 n/ H6
7
8
; H: J" V  Q6 X  c! j3 {) j9
1 q' @; {  D, ~" |10
11
: O' |( J+ j3 `" S! z12
13
14
15
5 m8 D- v. G( `1 W9 b16
17
  p" X1 N& p; ~9 Z( V/ d; o用算法再带入这个例子，进行加深理解


带哨兵：


. j6 O- [9 C8 y8 b5 e# M/ M& x' f补充：对链表L进行插入排序

void InsertSort(LinkList &L){
    LNode *p=L->next, *pre;
# G0 R6 \4 w5 x6 j" T% @% Q- h    LNode *r=p->next;
    p->next=NULL;
    p=r;
$ I2 b+ S- ?. Y) K" n/ i1 p+ \    while(p!=NULL){
6 I9 ?' m/ @/ u' _        r=p->next;
        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
  v# `( Z  l$ o! Y% x            pre=pre->next;
$ u  L! m, A/ Y; `) s/ t" J        p->next=pre->next;
1 \9 |7 Z* R' `# G6 o& i        pre->next=p;
        p=r;
    }
}
1
0 w4 a$ P- h8 V; K/ T0 F3 @) x- ]& P2
3
* @; C( {# N  z4 u# U3 F+ E$ e2 [4
5
  h& u" G0 ]  D7 z7 h6
0 R: e8 L6 q" Q* e$ F6 w1 |7
, \/ j8 `6 S/ o. n9 a8
! i2 M  h' P& J) Z9
, B; }# |) z' D. k! T10
11
4 V1 F% Z" p, y12
13
14
15
时间、空间复杂度
9 z9 A6 E0 e# w" S
3 m: n! P* S' }$ c. k' @: d
最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
最好时间复杂度—— O(n)
4 f8 z) T# ?7 C6 s1 j: b$ y. J+ E2 N
最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
, s8 _. }0 h  Q* O  K$ K第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
* X- z' [* q' o2 F…
7 m7 D- N' ?) N( n: Q1 a1 n第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
& }7 p# G7 g' x9 f% L- B" ]& p最坏时间复杂度——O(n2)
7 v, G$ X! f. L3 C% B& o0 ^
( p$ Z/ A) j: t9 W$ N: }6 c
' _0 o% H. N2 X0 p
) x# b; N1 D& B* ^" l7 t* D

* f  j& o; q: D3 c（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：
8 o+ M: V# X5 z5 |7 L- ^' Q
. u8 w7 K4 p1 M% I& r% l' J; K

//对A[]数组中共n个元素进行折半插入排序
" e$ Y& `4 x3 I8 t$ X  tvoid InsertSort(int A[], int n)
{
, }5 F9 r# t7 H8 \) ?    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
    {
        A[0]=A; //存到A[0]
& J+ ^& i- U, q. q* r* g# ^/ M8 B( o        //-----------------折半查找【代码一样】---------------------------
% C2 e5 |* p# ~        low=1; high=i-1;
        while(low<=high){            
            mid=(low+high)/2;
) K7 m* ~* A  [+ @* Y1 t            if(A[mid]>A[0])
5 W+ f& ^" {) R% A                high=mid-1;
            else
                low=mid+1;
- j* w2 X9 v4 ^& {9 t        }
& U2 A( E- @& [' q$ u# {         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
# C; S9 n* U1 v: R- H$ |+ e, C            A[j+1]=A[j];

  G! Y" x* L3 W" O. ?/ O: c% a9 Z        A[high+1]=A[0];//插入
: ?5 D2 V! E0 M) X1 p8 S8 @1 p) k    }
}

1
2
2 I, q( }* H" g1 |$ X3
4
5
6
2 B% z+ p- v6 D/ O, N% N7
; H6 N4 P2 R; f/ Z" j' k3 ~8
% Q" E7 {3 g, I* Q# B: F9
10
( u3 R. o, N" l- [( P1 t' U- e# R11
) k2 v( s. o: E' ~12
13
14
15
16
17
) J9 s0 t& S$ ]18
19
20
9 V, s" l8 _+ m2 V21
22
1 J. y, z% Y- ^% i" h+ Z23
0 J, ^; B4 P: y3 V5 C时间、空间复杂度
5 e6 U. L7 N: l" n, a' M% r" M空间复杂度：O(1)

【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
) K' c; E, P7 y0 z1 F1 m; R9 R

（不稳定）1.3 希尔排序【多次直接插入排序】
) A* _* H3 j: ]是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
$ E, I6 k3 O+ ?; h  O5 L) A
9 r" Q& x% B% V算法思想
$ B( `3 o- s0 Y6 t2 ]+ j- O" j# U
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：

% R* a! I9 _# z0 l# @3 `: ?# c
# |% W+ o# d1 r5 g8 `
代码实现：
; r* A6 N4 j8 [9 v- v0 y
//从小到大
3 o0 m. |/ {/ m- @8 hvoid shellSort(int* arr, int n)
: y; h1 b7 _" H8 R9 N& E$ G{
5 n- b8 ]) ^6 @+ D- x        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
. X9 @0 c! n! K/ @            {
                if (arr < arr[i - gap])
* R( t7 G, P1 q                {
5 G1 K: h7 R6 ^+ C: x8 E( z                    temp = arr;
4 m- b+ u1 l' A0 B1 L
                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];

! m% M4 n- H+ w3 U5 R                    arr[j + gap] = temp;//插入进去
                }
            }
            //************************************************************************************
4 U5 n0 Y$ N6 X        }
}

1
3 L4 x0 N* u: d' i$ x$ P+ [* d2
3
4
& l9 }! @) o. p5
# q2 l" p$ X4 o7 }3 u8 |6
' g$ r/ T  p2 {+ d! O7
1 e7 s* I# `8 ~. A: A8
# O% K: x+ N( R% h  e& T' W& |9
( }0 J( c  V6 g$ \' G: d  S10
11
12
8 E* O8 G! g7 w13
: `1 \! }8 N) o( }! o/ c14
8 X: \) g- {+ O( p15
7 ^0 D  g+ N  h' G1 |0 f16
) [  @/ f5 i5 K17
1 p) g# I) I' C$ M% V' @: f- A18
) v# n% ]8 j4 n1 R" }5 z7 |$ T19
: d- |) S, R* _; P20
$ e6 W/ W6 @! I7 c21
$ ^$ y% a& J3 K7 [% U22
3 v+ o( ?! d, u' m1 g" R4 U1 i23
24
5 Y  E8 q* n( `/ d8 @时间、空间复杂度
空间复杂度：O(1)

时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
4 O+ d6 X: S- [$ U
稳定性：不稳定！
+ i6 b4 g2 O- H- v  q& [

4 k4 G% @4 Q1 Q$ n+ J* ~( j
适⽤性：仅适⽤于顺序表，不适⽤于链表
6 C1 G' j; Q7 C9 W6 L5 d# X% a
5 ?. N8 X" Y6 W! T, l8 r0 j% ~! ^

2. 交换排序
2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

0 I6 d- r# \2 I; c: z, e: K每一轮比较会让一个最大数字沉底或者一个最小数字上浮
# j1 T+ z$ O9 o: U- J  r8 `$ @
8 a. q$ `* D. b$ B+ g/ `1 p& y7 Z* f这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

实现代码：
" j- l2 ?8 O: U% R5 B3 t
5 p( P. i5 J  A//从小到大：
5 V) a! Z) z( X# }" Evoid bubble_sort(int arr[], int len)//冒泡排序int*arr
{
        int temp;
) m& I5 ?: ]1 c3 c        for (int i = 0; i < len - 1; ++i)//循环比较次数
        {
$ }/ _/ B- W& ]- ?2 [5 B6 @. D: X                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
; P+ B7 x# p) M7 F$ \, }                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
2 X, u0 ~8 D* q. F                {
  u; k, |" \. ?                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
& ^* g2 x* p4 C6 t% |8 I( T( d9 S5 V                        {
% ]7 b! X( @6 m% w0 V3 G* D8 T                                //交换两个元素位置
  \4 K6 |3 H$ U                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
$ t- S7 _% F9 h+ t: i+ `5 b                }
1 q* h! x( o7 X1 G) y7 t& ?        }
( S' e7 a/ M. _9 T" ~  F}
% O) N. N0 d- E! `8 U  K
, z! ]6 C4 T& Y6 Q1
5 `, V" y* P# ^/ x2
; d" y' [$ ?& _$ \3
4
5
/ [  I0 G4 o9 E; d6
3 Q; ^" d& E) `1 O9 M0 T7
8
7 H% z+ g6 f, `2 ?9 N/ |9
10
; R- p% `- q! T, J: d' B11
12
2 @3 W' O. l8 R. i9 [; Q$ u, D# [+ Z13
14
( X# ^( v& i' A$ }/ g15
16
17
7 g: e. `- d6 T$ F  |18
19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

6 F( A7 n; C' J' S//从小到大：
void bubble_sort(int arr[], int len)
% C8 \. {* A7 t& o8 h{
        int temp;
3 Z3 T& l+ N; c        bool flag;
* w1 Z+ r6 w" Z/ X4 z: [  b" w% w        for (int i = 0; i < len - 1; ++i)
        {
            //表示本趟冒泡是否发生交换的标志
3 F' c6 r8 k* o& n" C                flag=false;
+ X9 A2 p* G' e1 n5 V& m               
6 d3 k6 [3 J- a4 }) ^$ W                for (int j = 0; j < len - 1 - i; ++j)
' O- c$ x- p- v1 }                {
5 H# o6 ?: I5 o( G) A# @9 I                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
                                temp = arr[j];
. E4 T1 g3 R0 P0 Y                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
. W: S( f, C& i% u                                //有发生交换
0 }- @! q7 G0 A                                flag=true;
                        }
4 g# `: ~! u$ O                }//for
, D( [1 b* G+ v9 r5 }3 H" e               
                //本趟遍历后没有发生交换，说明表已经有序
                if(flag==false)return;【1】
        }//for
}
6 M9 ~$ [7 v4 i/ Q  ~+ y" o/ @
# f5 i' Z& }8 a* ]# K' c$ F, ]1
2
2 N( N/ R& t9 W- X! ?3
' C# I* C* [! n' u, `4
5
6
# f6 F- f; F) c* f; _% [) g7 \7
- G* I1 r3 v4 U2 X8
9
  ^8 H* X1 {7 M: n: G, o. Z10
& n* k0 M# {: H4 N2 [5 W. n11
12
: s* P, E" ]0 F2 {13
14
15
. S: }/ G$ x$ ~$ B3 l. `: G16
% J* K2 c& R8 G7 e# {7 r. Y0 d17
7 e* {1 l7 K/ T1 B; ^0 c18
$ D  h+ I% E  m2 V6 T19
3 V7 j2 r- i+ P( J20
; K7 |8 h$ u9 P, H/ Y' \* a21
6 s1 q% B: o' C" N' D22
23
24
/ f; i+ ]$ e7 \) ?* a* m- u/ B25
26
时间、空间复杂度
8 t4 g  b$ Z% N3 E! h0 w
适用性：冒泡排序可以用于顺序表、链表

9 d2 s8 g" H" b' y4 s0 C9 g

: b4 b1 k- m$ V: X. |
2 `1 s# q8 i8 U9 q# ]1 B2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
. G; @0 Z+ s& G2 F- `使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
0 w7 k1 i  d# l& c* }5 @再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
1 k/ F: A% ]7 x4 B# [- t
然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

划分的过程：

& C3 i8 x' n+ A7 m) S$ Z初始状态：取首元素为pivot，定义low，high指针

- S7 o% _, L* n5 }首元素为49
high指针指向的数据小于49，就放在low指向的位置
. a! T) U6 B" e. {8 C) Klow指针指向的数据大于49，就放在high指向的位置
5 A; x5 ^1 d* n1 {. J


9 z: I* E+ l+ m4 m# W

// 用第一个元素将数组A[]划分为两个部分
% H) q% f2 D- n! D. Fint Partition(int A[], int low, int high){
        //取首元素为pivot
# q2 B, `9 b$ |$ _# ^; j    int pivot = A[low];
  I4 v6 C& D8 u
% r  |, G. q* ^8 {' l  j    while(low<high)
) J! d! d- q( m* n! J( U' q/ S* b4 L    {
            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
7 o  N- P4 O$ n8 O8 I            --high;
        A[low] = A[high];
) W7 N( N9 k3 b
        //随后low向右移动
        while(low<high && A[low]<=pivot)
# Z7 `& g3 m0 n+ T$ p7 \8 \            ++low;
        A[high] = A[low];
* I+ p8 ^& E: [* @5 V    }
2 b" h( {9 b* x
    //low=high的位置，即pivot放在的位置
! H- }$ o/ U! R" J    A[low] = pivot;

# o9 F1 R5 V) v* I, z    return low;
}

// 对A[]数组的low到high进行快速排序
) A3 V3 H4 u2 P, Ovoid QuickSort(int A[], int low, int high){
    if(low<high){
& g1 u) L7 G# K8 |- s. m+ J        int pivotpos = Partition(A, low, high);  //划分
0 u/ L5 z+ |9 v9 B: U* m        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
    }
}

3 q+ K( Z' l# K* Z1 _: i1
- ~2 Z# x* y2 X" B8 s+ z2
3
$ V/ @* B  O0 Z+ U! d5 A: ^4
0 b, a+ R$ w, }4 B! h5
6
7
8
0 x0 j2 w) G* x# t  i9
4 R! q. K  [  K10
11
12
13
14
( ?; i8 S& D0 I0 c' s" r' n15
1 d. C, W+ T9 X0 g) J3 ~16
% i, g2 p5 b. w2 l6 b; f& v. D17
18
19
' p+ s- g+ ]; }, l' @20
! n- |" X' r2 j/ K21
22
23
24
25
26
) D7 ]3 G; \! }$ j& e9 b7 ?27
28
29
30
( Y7 A# b% \6 ~: J6 Y2 t- q31
" O% y; r  m* e. y: g  Y32
时间、空间复杂度
( f; Q# ?2 H0 w8 ?* O

  O% n/ w+ n; {+ T% o把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
! I! q3 g( o& p
n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

7 B8 o- b( x- y% W) A; f" T时间复杂度=O(n*递归层数)
. t9 O) w8 J- z9 x最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

! H$ _. I/ E7 B, y5 f9 n/ K* [空间复杂度=O(递归层数)
' ]0 e, e3 ?- K0 z! `4 T$ [最好空间复杂度=O(log2n)
. C& k+ j7 i& F) h最坏空间复杂度=O(n)
/ a( q9 n  y; s" W& N9 O! Y7 m
最坏的情况

) I- w* z. q$ H3 h

⽐较好的情况
' O# V+ F7 s* N2 N% @# o
' A, ?1 R7 x- S( d
! h3 i3 [- E1 c
- u' c" o+ k! L& E' i* }0 Z+ l不稳定的原因：



1 C) s7 P& Z' [& h
6 J6 u# A% T' f$ C; G1 @' y
( r' L( ?& s0 N7 e3.选择排序
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

; ]' O* o; n) d; s8 L3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
% K7 v0 J1 ~4 p! N/ z

3 o: q) \" Q; A) e
, g6 g. ]/ b% q: e( \) o// 交换a和b的值
! m5 ?3 C1 a" c8 b7 g6 }$ A7 ~void swap(int &a, int &b){
    int temp = a;
  ?# _& m2 c' r- F0 z- Y, s$ U    a = b;
& ~5 Y4 ~- V. x1 X7 E6 T0 M6 o    b = temp;
}

// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
# S9 Q7 w# z, X5 U2 G0 b! o{
. U% T0 j. n4 g: C: V        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
    {                 
/ n. E1 G" z! ~8 v# Q        int min = i;
% b& I: \( l& O1 a# A        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
* ]. t8 Z4 b% G+ s, Z7 E                min = j;
        }
        if(min!=i)                     
            swap(A, A[min]);
1 K( U% k4 @8 z0 D    }
}

9 ^( d0 J7 X7 d8 N1
2
3
4
5
6
  f) E: {. j% a, Y. J2 I& V; |7
% Q5 ^" j% P4 ^; a7 W8
5 ]* G4 I2 L3 x7 P! r9
10
7 ?) V! g1 S* w' C! k: @" S11
( \$ j  c6 Q3 I12
13
14
. }/ D' N7 I+ J& I15
0 \2 F, J5 b( |- }) H16
8 G: L3 B3 z6 Q+ B" P17
18
9 D4 T0 r9 L# J) p9 g4 d19
20
! [- g3 N+ Y: G21
+ K* G0 k2 c  p, @* M+ M" `6 f22
补充：对链表进行简单选择排序
7 k3 z; g4 Y8 a0 d
  U" X# F9 o* A: jvoid selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
1 l) f4 ^% D) y) [5 N    while(h!=NULL){
        p=s=h; q=r=NULL;
% [$ u* q* @& s# o9 {        while(p!=NULL){
4 o. S$ p4 q; Y! X            if(p->data>s->data){
                s=p; r=q;
9 |0 T2 r- U5 B: H            }
            q=p; p=p->next;
        }
( D. d4 X/ `; p* v6 z        if(s==h)
            h=h->next;
6 W- h, ^8 c) I, R1 l2 ]! W- a+ k        else
            r->next=s->next;
/ e! l/ k, F* X8 i2 m; x        s->next=L; L=s;
    }
0 }6 i3 O( _; s: p}

) K5 ?8 B% I) Q% m; o1
2
3
* }+ P9 A; I0 Y, u8 `9 d. A0 ^% _1 {4
# Q& e# E" x+ {0 H5
0 d- F* L& y- v* p9 F- J! t9 e6
" j6 a& I, f! {+ N8 Q7
8
9
10
11
$ |; l7 [& w1 a% L$ f& `4 w12
) v4 x+ _: W/ V5 Q! w13
5 O, Q: b1 q4 l. f6 m. W* H14
15
% o' w! c' i5 L7 V3 m/ k8 A16
17
* _, {# S7 |0 h+ u18
- j. U6 \( I7 k8 u+ Q$ ]时间、空间复杂度


: M: h  t& b- N: e& u/ N: X

6 k1 c9 d& T* j8 z$ T适用性：适用于顺序存储和链式存储的线性表。

0 b7 m9 K( l% ~$ R
3 \( A9 c1 v+ L
3.2 （不稳定）堆排序
) }1 ~% ^3 q+ b① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
% `5 H: X; s# W% Q% Q堆是具有以下性质的完全二叉树：
# y" w1 ~) v5 A' }每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
" ^' E- A7 H) G' W+ s- Q或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
9 P. c6 u+ i+ ^0 }# m7 N
# i: b' A; A8 Y0 p$ O

即：
2 z1 J2 b- Y# j9 h! q4 g% R若满⾜：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）—— ⼩根堆（⼩顶堆）
0 ], u2 m+ E$ _3 R9 k0 ~" U! {6 w7 c
+ X1 d( `& [- R* ]② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
思路：
6 f$ O# N% ~3 D' i. V( _8 o& a把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
& Q6 i* a. |3 g, }; c# h, N- D
' ]! X$ ]3 J1 h8 h在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

( o* u( B6 `2 a: [- C& U0 c检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

过程例子：



建⽴⼤根堆（代码）：

6 _( |, i( Q7 L5 ~  P
" j- p& V1 ?5 [
// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
1 Q! W% {/ d9 X! _* u3 i    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
2 F4 ]4 b5 ~. X3 C}
% f  V, `7 o5 }
// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
3 P6 K0 E0 N- L) ^        if(i<len && A<A[i+1])       
7 |+ T# S  E: A- }& _            i++;
        if(A[0] >= A)
6 h, Y; o# X4 \7 N2 C- g            break;
) e1 n/ O- u6 X  c# U1 O3 A        else{
( M7 w: T3 u( y2 R  i6 c            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
  S: ?8 B7 ~2 |; O) K        }
' X/ L' a- c  p    }
, B" x6 |5 M, l3 b9 A" M) a    A[k] = A[0]
, e0 T$ T  l0 P7 d}

& J" m& H! B' D' A* k5 L0 A1
2
2 u+ \, ?! f( U  F% [3
4
5
6
7
7 L$ l& x: @! b" ~8
) C" O1 ]; e  R: K. `9
10
11
12
13
6 Z" w+ f$ y/ a14
: u6 z3 ]- X% W0 D15
16
17
18
19
* `% w) o3 f' r20
. a; o& z+ y% T6 U! z; k21
; |. b2 w, m$ M  M③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
/ n, a# @6 L( k选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
& e) K  k% k$ c0 f; |* _8 u
堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
1 r( E" w9 d/ e$ E/ g# n3 I
! x! `! r3 _  O0 Q9 f( Z过程：
- j; e& c! k! W; z5 i6 B8 G
// 交换a和b的值
void swap(int &a, int &b){
. P- ^( O4 F+ l' e. O) g5 [    int temp = a;
    a = b;
0 l( `# N: v4 M0 I, ^    b = temp;
}

// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
& m6 C( _+ ^7 p6 o( z        //初始建立大根堆
    BuildMaxHeap(A, len);                

' {! L  V: Z* y, E  }1 t- E    //n-1趟的交换和建堆过程
2 v: T% p% L5 _! k' D! p& u! }    for(int i=len; i>1; i--)
1 \; d5 `8 t) R3 ^    {             
        swap(A, A[1]);
        HeadAdjust(A,1,i-1);
/ O* t. s, I1 m" p2 K& |3 K    }
}

1
: e6 p  @- @, v0 s  _+ F2
3
; g  O& P7 t. V+ O4
  U9 h; l- T. s( W- r0 \9 o) W$ S6 A5
6
7
8
* N$ H* I) |% T9
- N, @% o- r$ h( w- \10
11
* c+ f) s3 V3 S  I5 [) g3 v( U& p12
/ ^% i8 A. |, q6 I% }* L. V13
14
* h) c/ g. {6 Z) {15
16
  C, N4 J" @# A3 L" [1 }: F17
5 L6 J! i1 R' [- _) p# q18
7 z: i, z1 I+ m0 o19
) m1 i; |: a6 o2 c; l; Q时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

空间复杂度 = O(1)
8 r: r4 L! A; S
" X! I7 h& u" {1 u+ z0 C6 e结论：堆排序是不稳定的


④ 补充：在堆中插⼊新元素
4 k* f. q4 _( e. ^3 ~对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌

# V7 ?+ c5 K7 b5 `% R0 b7 }

⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
2 E- W! o$ }3 B/ }/ b4 D


% S1 Y6 l' @# a! S6 a$ @1 {2 E

4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个

① 明白什么是“2路”归并？——就是“⼆合⼀”
7 \3 T7 t0 U% E0 A) x2 m
, Z7 Z. L. O( q: o' r  ~多路归并：

! R  O# v' g% m. Q6 G/ c
* ^( ^% [* _: g8 u, z1 z② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
6 R' H% [- U! S1 q5 @1 J
! n; P, K3 l/ E9 EB[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

. P' q0 h8 N0 l3 S- C1 Q- j③递归进行分治思想【MergeSort(int A[], int low, int high)】


④ 总实现代码
! L% g* b+ s2 E3 _& u// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));

// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
+ k; S. A6 R9 Y6 \    int i,j,k;
    for(k=low; k<=high; k++)
, i5 W  R% I# j' g8 m$ S( K        B[k]=A[k];
2 B; R0 Y, G$ K) J" g: G    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B<=B[j])
# }6 h( \. v* t. y# Q1 {, x            A[k]=B[i++];
        else
" P6 p  _9 ~4 d6 W- f' G5 W9 u7 |; h            A[k]=B[j++];
* L& L+ M* v' s3 H% a/ S! Z    }
    while(i<=mid)
4 j# w5 K+ I4 s3 O        A[k++]=B[i++];
    while(j<=high)
) U# F9 ?+ `. _- F- e        A[k++]=B[j++];
' n, D7 j( l4 }5 B  J7 a}
- R# s, u% i1 c3 T+ o+ {+ D# X
6 |& u( D7 W5 H1 c% c1 b
  E4 t, J! d4 i  E// 递归操作（使用了分治法思想）
void MergeSort(int A[], int low, int high){
    if(low<high){
0 C7 `* f. r2 B6 O  T" F# `+ d        int mid = (low+high)/2;
. E6 z1 q- z. K8 C        MergeSort(A, low, mid);
* z3 J  n: z0 O4 X. c2 c        MergeSort(A, mid+1, high);
3 j) q, n6 L8 J' t        Merge(A,low,mid,high);     //归并
# P) D; P9 _$ j    }
; J; F" M8 j1 M' i; M. ?}
( N' f% }9 P/ l5 l6 v
+ i( A: Y, ?+ S+ r  e8 u! C1
9 p5 o; Q' F$ C. V  W7 p. q2
3
, Y4 E8 z+ a% y% }4
! z0 B9 Q2 T( b8 H: h. P1 D' u5
6
& U/ T% W4 Q" V3 J6 A6 l7
: r! x+ Z0 h+ o' V2 b8
. D  B+ O& ^0 k# y+ |% w9
" j" e5 u" u8 l: J' [, I6 Z+ S( u10
11
12
' y) g+ p# r) b) l! i13
; Z* G0 `, S+ V+ l+ w- e1 ~# M14
15
) h) P! N! z4 Z' V16
17
18
19
20
21
22
9 A/ M4 m; k# T9 O23
24
  L4 I+ w' }7 F25
26
27
$ a) O4 |9 t2 Q0 C28
29
( N0 B( _0 J8 V3 {7 h7 j30
% r5 y+ l8 h; a/ U" K: N时间、空间复杂度
# n: W' v  J, o6 `


+ V, \$ G/ @$ _
8 E  R- F" S) y0 ~+ ^- n& S5. 基数排序
直接看课本的过程图来理解P352
& ?) o1 M; @$ K: ?
2 A" m1 Z7 B6 ^再看这个例子：
2 X! j, o+ R( M- C) b  |
( U3 S! a% \" H" S
- T# s& I/ K, T& z算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
1 x' j' ]3 V( K* R分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
1 J5 n+ u- |+ }基数排序擅长处理的问题：
; Z5 C6 e* @+ W9 l6 j# R; m' d①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
/ S1 W: y) o: v/ p③ 数据元素个数n较大。
5 f# ?+ Y* v2 I$ p算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
3 @) k9 I, m' c. D$ X/ c6 T5 G' F空间复杂度： O( r ) ，其中r为辅助队列数量。
- ~! W6 ?# D5 R% @稳定性：稳定。
2 {" p: |, B. J1 \, P& u7 e
' i4 ~8 H" h4 h- a5 e
内部排序算法总结

. n2 ?" s3 _  z————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
& B& }$ j3 _) C/ F: f$ K2 g- v- N5 ?原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969
' T9 l/ p! x% I