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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
# Q+ |/ g7 {1 M文章目录
. ~3 o% M4 c( _7 O7 n! |排序
1. 插⼊排序
2 e6 y% O# @7 x5 i' B; G( {! W% `（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
时间、空间复杂度
: V/ w6 x# Z3 U5 t) \, e( N（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
时间、空间复杂度
& U/ U! O- Q# q0 ^/ S2. 交换排序
( m' g) g: s1 w5 A2.1 (稳定）冒泡排序
3 _% k9 w+ L/ r! O  T7 B% z' Q$ r时间、空间复杂度
% l, n9 S- A7 ?7 J' s2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
  B4 ^  U8 f  Z7 U+ Y! k! ]时间、空间复杂度
3.选择排序
3.1 （不稳定）简单选择排序
. M; o( u% r& H  @: I时间、空间复杂度
, W( k  Y4 b+ z3.2 （不稳定）堆排序
' h+ _8 k/ z5 o& A! c' X8 _8 `① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
7 q7 Z  ~6 S- q$ m② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
8 W' @" C+ B9 a) L4 N' \9 ]③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
! f# j; H5 ?- ?  k. q时间、空间复杂度
2 ^5 o# N8 W- ]: J+ c- D& e④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
- e; \& Y! g2 L2 A' M4. （稳定）归并排序
! a0 F( A) Q  ]① 明白什么是“2路”归并？——就是“⼆合⼀”
5 _. M! i: h" O6 O: V1 F② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
时间、空间复杂度
5. 基数排序
内部排序算法总结
: r( Z& y/ `6 |' z, F排序
0 p# u$ e; |, ~9 r排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

5 U! F: D& W% K# u5 k9 n排序算法的评价指标：时间复杂度、空间复杂度、稳定性。

) p5 B- [/ O2 j% g4 b) t算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。

& E5 y% a& q+ t
3 s* C, X# T+ {- c# D: g排序算法的分类：
0 q. P& C9 }0 F' U0 t! p' q内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
% ~6 T, L6 X$ _2 @1 u  M! e; E
/ n5 e8 _# L( l* Y: b$ y! d; x各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

  M" `6 i3 D0 k4 y/ R
+ \: Z3 [6 B3 ~  R1 b
1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

& X0 R0 f  d) @8 d算法解释：（从小到大）

+ j/ \9 P" Z* |7 t% m8 T; x
算法三个步骤：
  p  b5 t3 [' }3 r' u
* e& r1 f. o# s3 ?: b2 c3 r/ f1 d先保留要插入的数字
8 f2 ~- W% N- m往后移
插入元素
( q- x% _1 l; |- q' a
/ l6 a! P! @" `* m* R" _6 r// 对A[]数组中共n个元素进行插入排序
" w# m. [6 @3 q' K! k) S, \void InsertSort(int A[],int n){
    int i,j,temp;
0 |+ I* A- Y7 E9 `! c" G' H    for(i=1; i<n; i++)
0 L' c; \' `+ S9 a    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
5 J$ t9 K$ p5 T5 P$ v/ i        if(A<A[i-1])
        {           
0 z$ X( \+ s. A9 R3 D            temp=A;  //保留要插入的数字

            for(j=i-1; j>=0 && A[j]>temp; --j)
# P/ F# l1 c% n* n) j; ^8 a; r                A[j+1]=A[j];    //所有大于temp的元素都向后挪
. ?4 M' O% h3 N
" T- d. c+ T! s  d  L            A[j+1]=temp;//插入元素
        }
    }
}
: @' Z: z& ~5 Q8 @7 K
" ~* h' m; O! A. F) I; C1
2
! ^3 a. M5 o& f# t# N' n8 B3
4
5
6
8 v+ k6 q& k0 `  ]  M5 \" ~7
; A) L: Y# n6 A$ Z; x! Y8
9
& k% d) y/ `4 f; G1 G" L10
11
12
! t( }8 w/ _' \7 }) z3 T7 |  l7 \13
14
0 |* p5 ]- y( m; U2 c+ c& [8 @( T15
; ~- S" |4 p9 G+ K) ?% ]16
9 E1 }- O* D) }$ [3 }+ Z17
1 x$ Y& u% q" l! q! c1 J) y用算法再带入这个例子，进行加深理解
* j9 U% E; x6 ~7 q' g0 M6 X
# z: a' [7 f- R4 v$ j
. w8 c6 I1 n' b6 {, k8 k带哨兵：

& J0 M% ^1 M6 O1 q3 j
+ W* z0 C4 i, S# B9 Q) @" z补充：对链表L进行插入排序

- B5 r/ E: w4 w9 Wvoid InsertSort(LinkList &L){
6 e5 o% ^7 G! Z# H* n    LNode *p=L->next, *pre;
  k7 Q% ~) @' F    LNode *r=p->next;
# |( @- k4 X# l  T# ^0 t  P    p->next=NULL;
    p=r;
    while(p!=NULL){
" Q; Q" N9 E  o1 L        r=p->next;
        pre=L;
0 z* }. z' r: o8 O" p1 n        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
! [8 N  a/ b% W# C+ X' l        p->next=pre->next;
        pre->next=p;
3 y" _) |* [: Y6 \. n, [        p=r;
) @  z* ?9 c7 @# B# W: v    }
! S% q3 ~5 ^( I) [}
- C9 x7 [# _, o7 i$ g- ~  U! o1
  x( {& w" S+ Q9 O0 V( |! _2
6 I* U$ [2 S6 W' N3
( c' G0 Q6 E9 H* e% F& Q4
' ^6 o! }' O) d7 P5
6
) C4 X. B' p* E* [" V7
% M5 }* x  _1 R. x1 n+ X' h8
9
10
11
4 p0 X2 [% K+ p' h1 }12
: f! `" c- z/ S13
! y# W7 a  z, |0 @( U9 j+ D14
8 t4 G, D" G3 E" A4 d% H; J15
时间、空间复杂度
# _5 y) N. n5 v- d- N3 L# ]
- N! h# s6 S" q/ ?
最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
8 l% q0 b. Z0 W3 Z# s. q最好时间复杂度—— O(n)

最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
6 x7 K/ M& R9 H/ t% q…
: x" w, _+ }" `8 U第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
! r' M6 c' }! L1 w# a$ S' E/ k4 s最坏时间复杂度——O(n2)
) H( k& l3 k& M

6 I% g- ?" X9 a9 S$ w- c3 ]9 C


（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：


. V( q' E: Z4 C& g. {- m
1 Y- w  r* A8 e7 \" N, e4 M0 z% j//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
" |( ^% t8 Y3 F2 k{
3 y! ^- X. o( G6 G: u8 c    int i,j,low,high,mid;
, |6 [6 Z6 m' R1 [( k0 o: I. S; \    for(i=2; i<=n; i++)
    {
' c2 h5 B" G% S$ g0 a' G+ |$ F0 t        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
& v# A) z/ c* C5 z        low=1; high=i-1;
4 i& Y+ H/ e/ x8 B        while(low<=high){            
            mid=(low+high)/2;
6 r0 v# M# {& |- o3 y% G. [; b$ t            if(A[mid]>A[0])
                high=mid-1;
3 d, p: g/ c, y/ ^6 j            else
$ B* O) b( l- X& ~% S$ _                low=mid+1;
% D6 `5 s5 K/ h1 \3 `$ @8 i) N        }
         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];

        A[high+1]=A[0];//插入
/ s9 ^4 }/ ~0 b$ ?1 }% U  e0 |) H    }
' [) Y# a  T2 Q7 A4 `( W+ z}
& h& u: c2 |; n5 d# g
1
% H  J$ Y7 Z6 V$ r0 M2
3
4
3 |4 G4 c0 r% r, V- p& D; b# M# q5
" B  X, y, x0 M% z$ d) o. ^6
7 r, j- t/ E6 T0 T5 J7
8
; \1 [% _) \4 z3 [5 F1 @4 F9 k) `9
4 z+ X+ r8 H5 O% |10
  ?( C$ g2 o/ D! v" Y2 n# h/ ~1 h11
12
- G1 |7 s! K  u( @4 G5 f3 B13
14
15
4 O# {6 i& A* i, [0 ?2 B& E16
17
18
19
20
. r8 M# [0 W& x! m+ ?( C21
4 j: o; |- q2 q8 t6 y. [" |22
23
时间、空间复杂度
空间复杂度：O(1)
! v+ B& q9 u* M# o6 D
【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
, E' w6 u3 A& S: _6 L! l

- d6 H! o. J7 W) {( G% p（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
6 R) K* d4 {! p' d  s  v, E
7 y) w* U+ p! T& [2 k1 L8 T# A( A  i算法思想
% v0 ~8 f! O1 @! k0 G* i7 Q( t
6 J, m6 A6 q. y希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
% m6 L, `! ^* P7 t图解：


# u, b' ?% O. I3 U
9 b1 z0 @$ z; v. P4 x, w, c代码实现：
5 ]* \/ Y4 p$ q+ v
1 g+ a4 I( b: ^3 M# B//从小到大
void shellSort(int* arr, int n)
{
) e  W* ~  r/ g' u2 ?( b1 D8 k8 V        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
& w: E" p* T8 F6 A        {
& |$ D' g+ e  R& ]            //**********************************直接插入排序（只是步长改变）**************************************************
. b6 F& j& _0 O" R' |; \7 R            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
& L$ L. D' X: e2 c                if (arr < arr[i - gap])
' ~+ U1 l$ q. f! _                {
% B3 B" ?5 z0 h2 o+ m8 o0 T                    temp = arr;
- [7 T% D- I; \. [0 t# O* |  e
# z; D) o3 n1 s7 I1 B" z9 k1 s1 D                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];
4 X2 {* v) ]4 A0 K# @- r2 X
                    arr[j + gap] = temp;//插入进去
                }
8 S1 D, R) D( J( P            }
            //************************************************************************************
        }
: d, Z; }, m$ m4 i0 @( V, ?7 ^}

  G$ m* l% y5 f; \8 s+ |1
, k" ?# X" l! \+ ?2
9 F& {- t0 M  y, J) s: y: z3
3 n2 j: \/ F+ l# K4
# Y+ U% s1 w/ F! K- p5
6
7
8
9
' m- k) K8 b, P! C7 ~; U10
3 P# n, E: l2 K, m+ h7 b0 l/ o: F: L: F11
3 d8 v6 z" ?$ q& v12
13
14
$ {  D, J, Q3 K- t7 c8 h* b15
/ i% L* ~/ Z+ d/ Y. |16
  P1 ^+ p) @; R) J: {17
0 P; d; t3 D# N) a18
19
  T8 x2 Z) z* Z4 H! J8 N! j; ~# f20
6 D" C% k  u) r% Q1 W# y/ `21
22
; r% g& M8 n7 M0 w4 T* ]' o( Y23
24
时间、空间复杂度
空间复杂度：O(1)
  }- i( n* E' D1 s0 E1 F! `
4 c$ _# v' B2 m  b  ~3 [% H时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
+ ^: @7 O! [+ o0 v$ _; ?
& Y1 E& L4 z$ A7 d3 H- _稳定性：不稳定！



适⽤性：仅适⽤于顺序表，不适⽤于链表
: z/ V3 T' o# ^9 `! `$ {2 l  Z% E
, \7 N( ]6 l8 t0 [9 Q2 |" l
& P; w8 b1 B1 `$ l& s$ ]  F
2. 交换排序
3 E: L8 a7 w. i4 }2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

每一轮比较会让一个最大数字沉底或者一个最小数字上浮

) |2 F" a* H; r+ @9 o这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
) I# `& e: G+ [8 |0 B1 \
9 }" E$ X: C( n; V实现代码：

//从小到大：
' w5 @& E; a! S! }2 b3 ?0 K/ h7 Wvoid bubble_sort(int arr[], int len)//冒泡排序int*arr
/ e+ `+ Y5 X% r+ _) N5 H' w{
        int temp;
) p8 H. ?9 f" B        for (int i = 0; i < len - 1; ++i)//循环比较次数
        {
                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
& ?0 M7 i; l7 |' @( b- ~3 ]$ S                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
1 V# A3 U8 m6 }# y" E6 c4 S* G                {
: {$ @& X' o1 t: K                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
% }5 C$ A" K) }8 |0 Q                        {
                                //交换两个元素位置
                                temp = arr[j];
& W/ ~) v7 G4 k* G( m                                arr[j] = arr[j + 1];
0 p5 a4 b  @2 b                                arr[j + 1] = temp;
+ N* C, {1 o" r                        }
+ E; C5 \& }$ S9 f                }
  o2 a1 T" ]0 j) k1 [8 d' b        }
}
" E6 M) z* i) h) S* P; Q
1
2
3
4
) r6 W# S3 h! L+ }! S; T5
6
7
8
, |0 p6 j, k7 M" I3 b9
! n7 C# Q( P, _10
! p8 S7 M. H( ]11
12
13
' l- y+ n0 N' Z3 M  Y* J14
15
1 v" t6 k& w# @7 t16
) J, G. ^% X! d) C17
18
19
  K3 K1 R/ |( `2 o- V' b# a优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

//从小到大：
2 r! L. k/ ]1 r% M# Hvoid bubble_sort(int arr[], int len)
& R. C+ o& P! I1 J' _; M: h{
        int temp;
        bool flag;
        for (int i = 0; i < len - 1; ++i)
  C* e* h" L, M1 I% _% u" }        {
            //表示本趟冒泡是否发生交换的标志
- N# l& {# v9 O, p2 ~" \                flag=false;
               
                for (int j = 0; j < len - 1 - i; ++j)
. t& ?! Z  j* P. z# j& J( a                {
- b+ P9 d: v% O4 B3 M( S: H                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
/ n/ \/ S) @3 W) C1 t$ r1 t- N4 b                                //有发生交换
: C2 {0 H- G" n. b                                flag=true;
                        }
- Q% Y/ c! u% Q2 o* h9 h; x                }//for
               
                //本趟遍历后没有发生交换，说明表已经有序
7 d$ Q& i2 H# z* A                if(flag==false)return;【1】
7 ?& H" ]3 N- W4 n7 I/ J        }//for
}
& H9 [9 d, Y; ]. `& ]
1
/ t: ?& j, F2 i3 X6 a2
3
) y3 G6 ?( A2 c( f; D4
5
( y& l% X+ M4 H8 R! b6
% s& E5 z. O+ @) ~; v7
8
9
9 I! h! l. {0 X10
+ Q: V9 m$ i# O5 D4 Y1 y. U11
12
13
14
15
% e* p5 |1 l6 Z7 ?" \16
17
" a# q  P) K- Q+ i# n18
19
20
21
22
1 @' `( q  ]% ?7 m, D23
) W3 Y2 f: s* v2 t+ A( u( v24
25
26
时间、空间复杂度

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




2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
: e9 h. s9 g  S- s在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
. a) j$ _( f3 l$ d. d通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
; {8 X$ S: D5 F6 _  ?( d( f* O使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
5 ?  c* }% y0 c9 N* d& o1 v再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
2 a. Z- |4 N0 @1 W; ~; f# K
然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
! I) x1 s5 s: O! D6 l  u
划分的过程：
/ o# W% v, a! H% U. {
初始状态：取首元素为pivot，定义low，high指针
* u& J1 G6 ?1 |5 W& n
首元素为49
high指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置
, V( r9 ?) ~( \: w4 {5 U2 I" ]
- ~( H# d$ Q/ x3 K  i, ]


5 \& b! p1 |$ {4 H. y+ Y
// 用第一个元素将数组A[]划分为两个部分
  W7 D  n# L8 u& z4 C" B4 }int Partition(int A[], int low, int high){
        //取首元素为pivot
9 p% v# `& e. g! u$ U* {6 S    int pivot = A[low];

    while(low<high)
/ R6 @% o% p2 l    {
) a* T# N) Y3 S/ H- w. J            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
8 N; F. v8 w5 G! t1 k' {            --high;
        A[low] = A[high];

: Q8 O! |. U2 ?+ Z1 h; U        //随后low向右移动
3 {' i3 V/ \$ |$ a3 x5 U6 c        while(low<high && A[low]<=pivot)
            ++low;
        A[high] = A[low];
2 Q6 o5 k# c9 W' p3 i. X8 h, @# i    }
9 F( ]2 p# ~4 {$ R/ @8 u2 r1 W
    //low=high的位置，即pivot放在的位置
( N& n6 c& ]: G    A[low] = pivot;
" X& W2 I1 ]3 T' q: M$ N
    return low;
6 }5 }- e5 g7 i' _% U}

, |7 O/ W. @7 ]; U5 s# q// 对A[]数组的low到high进行快速排序
void QuickSort(int A[], int low, int high){
' \* J/ g+ o- e3 j' B* x    if(low<high){
2 Q( T) }, S, a        int pivotpos = Partition(A, low, high);  //划分
/ f9 r7 B9 W! Y; ]! {7 L        QuickSort(A, low, pivotpos - 1);
' a) E5 @2 x9 G2 x& G        QuickSort(A, pivotpos + 1, high);
    }
+ H* i# z" @% y7 t" X: ]}

" H" M- W$ @" G! f! H' o2 H5 I) n4 j1
2
3
( Y: N  W- `% ^+ U5 v3 p4
3 [4 Z# g# ?3 q2 e5
- ^$ U, W5 Y; M* M# E! C# t6
7
8
6 V( W3 i2 L0 u* I% n2 ]9
10
11
8 w* ?0 k: k6 V12
13
14
: h0 ^$ x; q: a5 k/ m) W" m15
16
$ I8 q2 q# A) W, N0 L. T+ H- u17
8 \5 A& Z* ^. F8 ]- h: k18
$ v1 a8 U/ A; z6 u: f3 v19
20
21
22
& G0 u8 Z9 E1 n, I+ B23
24
25
26
: \! Z. ^0 R( |7 ]27
' ?: s  d( n$ Y$ X28
29
; m/ p0 s) v0 ^0 d7 Z30
31
32
3 u- c$ M% K" I& p时间、空间复杂度
% w3 i! V4 G' t  X; I% j

把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
1 ?8 i# J! g0 l. x6 y  {& |
n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
% f6 x) V! i9 S5 y最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

% S" J) r7 {/ ?+ g2 E7 H* e; c空间复杂度=O(递归层数)
3 h+ r1 C. u  E最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)

最坏的情况


3 Y" ^/ i/ y8 A  P. c
0 v$ ?1 H" }$ Z6 Q⽐较好的情况



不稳定的原因：
/ @: {+ Y! I$ b3 n
8 K8 H% Q5 u, `* B' U, V8 m; ?* U

1 G: X$ O% C( ?
$ w. Y) E- z: z# I7 O# [8 g4 Q2 ^
0 L7 @$ h+ e* f0 W$ W5 {3.选择排序
, S" }$ f4 q4 z. J, M6 h7 {选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
* l- [' Q, ]4 _
3.1 （不稳定）简单选择排序
  m& H9 q; h5 J) C8 \$ k算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
# ]$ e! l4 X/ P7 U# V4 V8 v# R

8 ], Q8 o! ^. F2 `7 {1 j5 k: L
# r- d, ~% N7 t* ~; x/ k// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
# v% z# r. _) [$ f. j+ R* W    b = temp;
4 f$ h- l4 f: _1 x4 c: T3 B}
( j# v+ ]) o) H9 }( y- q; [* z+ O
# h) E1 e( X, g9 f: H// 对A[]数组共n个元素进行选择排序
- w: k& m# s" S- L5 Q& wvoid SelectSort(int A[], int n)
* V3 k1 X2 o$ B9 T{
. S; G9 g6 p( T4 A- E" x        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
6 n- y3 X& N( u/ z2 D    {                 
- m3 ^$ ^. ~. V* R! x6 Z$ @/ j        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
6 ?% |9 {# N/ E7 q. p* m            if(A[j]<A[min])
                min = j;
/ `) F, J( b: i" ~        }
        if(min!=i)                     
6 o4 b3 o1 l3 X2 k8 _) X$ Y            swap(A, A[min]);
5 {2 P5 a- l6 @! [# L( n    }
}
, E5 E: j. y9 F% H  T9 T* ?) ]
3 N- ~' f) C, e! K1 W1
2
3
4
5
" G4 |& U* t# e" k$ p( N3 k6
7
1 m' p  i4 _, f7 q1 W. M2 [8
9
# |1 }. D0 x( W& |+ P10
. u- n7 P& ~, V/ K2 ~* z/ p/ a11
# I3 m; ?, U- ?9 j12
; f. J* O9 }! M* n13
/ F1 |4 m( P; S! F  t) [14
' b2 a; s6 _4 x* X! q15
2 m7 n2 {' s5 D* R16
: u' p4 Q( `5 n0 l# a. [9 v3 ]% I17
  B2 M, |. H5 f* `1 t18
19
' N. w" g1 ]& y+ @: e. Z5 Y* W20
7 b5 q  [$ y; v9 X3 B21
22
* K8 M) J: X1 @补充：对链表进行简单选择排序
4 f2 v  d. C4 ^1 J* H; ]6 F; y2 H
- W) |) T+ p, wvoid selectSort(LinkList &L){
3 t' h- V; R8 c) N! B" M1 n    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
+ f6 g( `) }, ^0 S. O) W6 Y2 d    while(h!=NULL){
        p=s=h; q=r=NULL;
        while(p!=NULL){
            if(p->data>s->data){
                s=p; r=q;
9 I3 r+ ?! P9 t: N! s- I            }
            q=p; p=p->next;
  G5 u) l9 |+ a        }
5 K( H  n2 s" i, J        if(s==h)
            h=h->next;
$ }- s) Q  O" Y        else
            r->next=s->next;
        s->next=L; L=s;
, Y' v' _* l  \+ D/ m+ s+ c6 D) A: N0 |% U    }
% S# k! h/ O+ l0 W0 t- W& {( Y/ h, m}

1
2
9 _( i2 \6 x  Y8 K$ X3
5 t0 @  @- j( f3 a, v, o" X4
$ X8 ^# b9 R% y5
6
7 N; P2 j2 q+ o6 i7
# d5 ^- ?5 h! }4 }/ Y8
2 ^% S: l1 c3 k  s' w6 g3 g9
10
1 e/ c, r1 _& H: Q1 C5 e11
12
13
( i- k/ B7 o% `/ b0 L& K% o14
2 D3 r: m' ^5 O" a# x% d, O. m/ Z15
$ D, u" H7 M# k* r% K. u7 X16
17
18
时间、空间复杂度

8 ^, m8 Z8 h- u% N; g& A& {

( `2 p% {1 B/ ]. w# P6 P3 d
& L4 A( q7 o  W% }  a, V适用性：适用于顺序存储和链式存储的线性表。

- P" {' j8 v0 l5 p3 o: {" u3 g
& Y# U4 W  w/ i+ d0 h# G
* G3 v; F( \+ R' h8 A' |6 K: x# t3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
$ g7 J( S/ ^7 a# F" B/ Q4 m5 T每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
/ F  A3 @. u, }" G  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）—— ⼩根堆（⼩顶堆）

/ \( w! q; j5 q  S# u② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
" s% b5 ^+ g3 [, V思路：
* n  M" m3 z# O把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
  L& L. a9 S/ l7 @' J
; G5 P  K' ]6 V' _" S8 w+ b" t在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

7 D: I! X8 w9 S. x. B( z3 E3 b3 {检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

* E8 U! b+ p- f过程例子：
) d6 J/ f' U0 m1 k! U, O, b
( [4 `- W+ t! J7 [; g
) e# L( E' j) P' m2 u- B& t
建⽴⼤根堆（代码）：
0 t4 U* w4 G4 @

! ^8 G) A. e2 O" d, r  i
// 对初始序列建立大根堆
& U- R' L1 x- ivoid BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
6 Z9 e, _: _% |: ^8 K        HeadAdjust(A, i, len);
}
& }" ~" d# {+ }9 d* H1 D
* F( J* n+ f3 J5 K  t. i// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
0 C) W/ k2 Z+ r1 g& j, F        if(i<len && A<A[i+1])       
            i++;
        if(A[0] >= A)
. _3 q! ^: Q7 t7 ?: q            break;
3 h+ n( y: u6 ?1 ]4 h        else{
. f- P$ a4 n, y4 T- D; o            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
        }
    }
; ^# h8 R0 h6 A" A. }) j    A[k] = A[0]
}
/ K0 a- _9 |5 Y
; }/ [5 f8 o) e& k6 T3 ~  d1
2
5 R0 @$ C' x( b& p' I6 t3
5 s* L: O  d3 T4
5
% ?; k% ~% W" K& ^6
6 f) t/ E" L5 {! H  y7
8
9
10
& S; ?: @/ T. y; F8 s: o! t2 Y11
12
13
9 [2 ?) d. C6 _: ?14
15
16
17
18
19
$ ~: S8 l" K8 m+ U* X) P- }20
! I1 R2 N; }1 F5 [8 \21
* d* ?' G8 x% G; E* S③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

5 A7 E+ x4 @0 D" F/ Y# e堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

过程：

1 k* ?; I& i' F. h+ q) J// 交换a和b的值
" O* a& ^( B6 `4 `# Jvoid swap(int &a, int &b){
    int temp = a;
: f" v: _7 D# u# f- @    a = b;
( i6 R2 Z" \  C    b = temp;
}

// 对长为len的数组A[]进行堆排序
: r: r/ Y+ \" f: @void HeapSort(int A[], int len){
        //初始建立大根堆
! d4 V8 o4 i6 j' r. ]& C: D4 j    BuildMaxHeap(A, len);                

    //n-1趟的交换和建堆过程
1 g' l: b, x2 @3 ]2 k% S) F    for(int i=len; i>1; i--)
( y) J. J# {' w) Z- B& j8 `) h) E/ J* P    {             
4 Z7 }1 a2 p; J        swap(A, A[1]);
        HeadAdjust(A,1,i-1);
4 Z" D" I. r( c" f  P( E$ k    }
}
: H+ W. E3 q- X' e) O7 H) k5 i
  w; w7 g$ z, C3 `& ^, k  Y0 m1
' j( k) z: r( E2 z2
2 O2 w+ H, z0 {/ {3
/ v( J' {7 P: Z  n% u4
5
# C* v/ e1 d5 U. Q6
7 s* r+ p: w+ {1 L7
8
9
$ i$ m8 k8 t6 E; N10
/ x5 o. J1 w: Q11
, {1 V7 a/ h' n  ?! @$ S12
13
14
$ n' t- `3 q8 y8 `$ \* e3 i15
: \4 t$ E1 ~9 w1 C0 b% W" s! h1 x16
17
18
19
时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
6 [' _; q8 e# W# n1 j% J故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
. k, v* H+ d* y
空间复杂度 = O(1)
8 K6 S& H( W/ G$ l# v
" {1 g: K6 s7 @! p! V9 |% i结论：堆排序是不稳定的


3 W: [2 V: m3 r$ s④ 补充：在堆中插⼊新元素
# B* W4 d. P$ t6 L* V* H对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
' T0 w) l5 O" _& O1 ]/ p# t新元素就这样⼀路“上升”，直到⽆法继续上升为⽌
3 P3 `) j9 ~& B, S0 j  }, W% ~7 [
) g. e0 k6 }9 H5 U% J% _. n( F

⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
4 R! Z5 T6 t4 l6 N" a1 x

, a# s4 U) ~! P" I) t4 h3 L  w

! n8 u+ m5 w' c5 ?$ f
4. （稳定）归并排序
2 g) ~7 h6 \6 m0 p归并：把两个或多个已经有序的序列合并成⼀个
& [! g, D# u" v+ }
; K5 _7 U1 k) A4 M. Z/ K- ~8 d① 明白什么是“2路”归并？——就是“⼆合⼀”
. i7 O1 Y0 y3 ^; |
: V8 j' `5 C3 t. w9 Z% y多路归并：
* S4 I/ ?) [: H8 q9 {! {$ G2 @

: Y8 U. A  U0 R$ s② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

1 s( L: R* O6 a! v) S% h  HB[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

③递归进行分治思想【MergeSort(int A[], int low, int high)】

; |* b+ q. t/ Z- v
, M/ A4 Z4 K7 V6 Z9 e- m' F) @( t④ 总实现代码
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));

// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
  S2 W( [! w& m( S3 V' lvoid Merge(int A[], int low, int mid, int high){
    int i,j,k;
2 k7 c$ q- {& l) I6 V  q    for(k=low; k<=high; k++)
        B[k]=A[k];
- X% h$ h( c# ^( M0 T  v    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
% n5 |  {' z- ]( l% b  Y* _        if(B<=B[j])
            A[k]=B[i++];
6 j! S1 N) B2 W1 E        else
/ ?/ x2 {) h, _% `            A[k]=B[j++];
/ r) `& y7 _$ {2 q8 d  k    }
0 S2 S5 i* B5 n- L# I$ b" q* s    while(i<=mid)
        A[k++]=B[i++];
4 X. \" M1 M( O: m7 X, o    while(j<=high)
) G  p( m8 f! y        A[k++]=B[j++];
}


" `6 y* y7 `7 u+ i4 K6 }3 R// 递归操作（使用了分治法思想）
  D+ c' W* G& _/ Xvoid MergeSort(int A[], int low, int high){
" _9 X( i. u* j6 _$ K% b" t7 T" u' A    if(low<high){
        int mid = (low+high)/2;
8 T: Q# ^" B( t, j5 _        MergeSort(A, low, mid);
) q) ^* P1 ~9 N/ b1 g% N% D        MergeSort(A, mid+1, high);
2 \/ [& D4 f& a% v7 m        Merge(A,low,mid,high);     //归并
    }
}

1
2
' G+ B! T9 E# H; k' n3
4
5
6
* ]& d  {$ P" K: |; W) P! @" B* S7
8
9
% I$ c3 a3 x" B10
' {& R& n+ j) ]11
12
13
14
15
16
17
) W5 J2 [" \3 y8 |18
19
20
" J# D- g$ E5 Z" H# @4 k4 }1 d21
22
23
24
" F) A) ~3 n& o( K" `9 _1 k25
3 |$ @3 J2 L4 e/ N+ {5 p26
27
" u% g& n+ \) V1 _* s28
29
' Y/ G1 w$ D2 b* q30
时间、空间复杂度
- H1 p6 ~) B9 _% t) x
2 W% K% A8 m3 I7 A' f


5. 基数排序
! N' G4 D9 D# d1 J直接看课本的过程图来理解P352
- \3 S$ i* c3 ?# o1 |
  M! l# i8 r( P5 i* y再看这个例子：
& r+ P% l: C( ]+ e
. x% f  r  F  ]3 w; ^
算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
4 N6 e% X9 `8 ]  z# u收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
①数据元素的关键字可以方便地拆分为d组，且d较小。
) l! M' I8 N* z$ b②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。
7 X; C' ]5 b0 S, f算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
: L2 O9 O% W$ O, V( E- A2 D# F0 Z稳定性：稳定。


内部排序算法总结

# W5 V: @2 T# U————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 |! j6 i+ g1 f5 s$ J$ A原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969

9 @; Z! j5 J5 {$ Q7 R" P
, Z5 F, l( a( I9 Z9 [7 F