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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
& A7 M. k4 ]1 \" e7 @! n: s文章目录
排序
: o: F3 |8 U0 T/ q! C1 I! Q1. 插⼊排序
  l- r  g' ?% V( [' V; g（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
$ Q+ M. c* ~% L8 M! L时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
! j. F- S6 f( Z+ _3 x8 K5 z时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
6 `0 b, a9 c* O! i7 U时间、空间复杂度
, Z1 D" P+ U4 k* u2. 交换排序
$ Y1 a& c! W3 @1 Q- j2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
- Y: }, P8 p. q0 d+ D% E* z时间、空间复杂度
3.选择排序
3.1 （不稳定）简单选择排序
' q8 b# v( l# _1 V2 _时间、空间复杂度
3.2 （不稳定）堆排序
1 q2 A3 m8 y/ V- J  d" J0 D  c( Z① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
) w9 u0 \. _4 M0 ]& \② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
% g' O: d$ t" p7 E# E② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
时间、空间复杂度
5. 基数排序
内部排序算法总结
/ m0 J  t; ?' S7 Y1 \& Y3 @7 E排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
6 x! R$ G2 s( r8 i) @
; Z0 d6 M5 q/ q, e- p2 a' o排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
& A: L5 S' W# }
算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
; f1 x/ X1 X0 u2 N稳定的排序算法不一定比不稳定的排序算法要好。

: [& ~, W% d* v) c+ M  d# u# g# Z2 o
排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
$ Y* t* ^7 e  ^: m% U1 a外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
$ i, d2 f0 `. `" `
各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
2 R9 o, `* |0 ~& A! N

0 q! O. s9 W1 T9 r9 v6 q
1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
+ W6 m& m! v) l/ @% r8 m6 M
* Y: u- H8 Z7 ?3 a$ Z算法解释：（从小到大）

/ Z: q" C9 ^6 b1 Z
算法三个步骤：

6 b1 e$ L  S, f先保留要插入的数字
往后移
  o4 t  O. r4 K/ h2 p# O* z插入元素
9 e2 v6 {  d" C: W/ m
// 对A[]数组中共n个元素进行插入排序
% Y1 h/ v" j7 dvoid InsertSort(int A[],int n){
5 I, F. g, v0 H: e3 m& Z5 l6 Y    int i,j,temp;
% Y2 P6 j9 X% q. q0 E: c: v    for(i=1; i<n; i++)
1 u. g1 I& d% C5 Q! I    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
+ K* P7 N- w; p" A3 z        if(A<A[i-1])
, h4 h$ {% t: I3 ?! F0 d        {           
            temp=A;  //保留要插入的数字
" V" I& ?/ @; Y0 D; P0 N
            for(j=i-1; j>=0 && A[j]>temp; --j)
6 ?# W' @+ \# ~7 M. {                A[j+1]=A[j];    //所有大于temp的元素都向后挪

4 z4 I+ \4 N  S, K9 Y1 F            A[j+1]=temp;//插入元素
        }
1 e9 ~) _  }+ {! c: o' G2 E7 A    }
}

$ D1 @3 Y7 V5 G3 b4 ], f1
% @; }; i: h2 U  M& }2
3
4
5
6
7
: `- h8 Y# }7 }8
9
10
0 H. d( R! V2 Z/ u% j( W11
12
13
  l' Y) E- B7 _, K4 t' i14
# q% x; s& u; I15
- ?1 o9 E4 C: `' U+ Y3 o$ ]16
17
用算法再带入这个例子，进行加深理解

0 {- }$ |7 Z& `4 R! s
带哨兵：
* f0 `+ U! E0 ^& P( g5 F
; S: b; G( \' n; I% c0 _1 `
补充：对链表L进行插入排序
# `9 e3 A& |& f
0 R8 g" U- Y+ V  ?! G* |/ U! ^void InsertSort(LinkList &L){
    LNode *p=L->next, *pre;
* K9 v' C. k, G' a: }    LNode *r=p->next;
* u2 i2 z( W+ \) o, w5 Y6 {    p->next=NULL;
' p" t: X2 }0 u6 p; J+ G: b2 O    p=r;
6 [7 G' W& c$ G3 b    while(p!=NULL){
        r=p->next;
# _( O" ~& O+ V# L        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
+ E0 Q. B; k6 H! w; x* b  H) U            pre=pre->next;
        p->next=pre->next;
        pre->next=p;
6 |3 c1 P3 p( `8 F        p=r;
    }
}
' S9 D9 h6 I9 `! x1
* x' L# i  \& D+ e6 S2
' R; @6 l2 E( [0 c2 J/ x; o3
4
5 t; B- |0 i1 X, [5 e  i. s5
' |% u8 _( U7 j6 [! H6
7
8
* j6 R% w5 T6 ?9
10
11
/ f! L: O8 {( p9 y+ i12
13
, z2 g; ^. k& r  a14
8 ^$ H' `2 a& a( s- ]; y( [# P/ h! n! R15
时间、空间复杂度
, ~" S) t) w4 E" S# i

最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
最好时间复杂度—— O(n)
* M$ r) b, |  x3 _# ]( \
最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
+ z  J% @2 m" e9 Q4 H4 T7 G第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
; _6 D" h  M* F6 A; E/ ]…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)


0 {. ^# n2 F4 g: e
6 L  a6 T% F  j: y, o! ]

5 @# Y! G. `1 U$ L% k$ L& g  T0 ^0 H（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
; Q+ E6 [* H8 |! g$ F8 M过程：

# o7 Z6 Q8 [: L6 I% O
+ j! D1 X4 A9 e5 f3 c" F! V
  G& B) c8 _6 T' {//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
{
    int i,j,low,high,mid;
! G# W2 r" q& e# M    for(i=2; i<=n; i++)
    {
. d% Q5 C. E% Z9 i6 X        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
        while(low<=high){            
            mid=(low+high)/2;
            if(A[mid]>A[0])
                high=mid-1;
            else
                low=mid+1;
        }
         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];
+ l. s  Q! X2 t, R9 y5 _* `
        A[high+1]=A[0];//插入
    }
}
, s) q6 Q: e* h( ]* o; U
6 e+ ^% T% F" j* A" ^1
2
3
; ?+ q/ Y+ S. h9 b+ S+ U" w4
5
' y; Z6 \7 p: T6
7
8
% i  K; _' J) h, A' C+ o9
! o7 Q4 G# b. C% \! p10
0 w: f, p9 |& e! Q+ g2 H7 A11
12
13
14
15
16
* n; s, g+ z. {2 h* b0 U17
/ X. U" i: W+ w. n3 c' I7 R18
# t- ?; b8 j0 C. h6 X4 H19
20
/ E0 x; `1 u$ t& }9 \% r21
22
# K7 o& F6 _: K* n$ l23
1 ~( ]9 d3 |9 b+ L/ C! }5 `时间、空间复杂度
& ]6 _( ]! P/ h8 Q% ]! z) e空间复杂度：O(1)
8 }" k0 H, @- a- U8 s1 r
' s7 k! a$ i0 S7 o  I- G! I【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)


（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
4 l) n( ]. \0 ?" j+ V9 m2 T
算法思想

8 B! m' q, S- d4 K( [; Z3 O5 A$ V2 \希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
. }7 D$ u' k1 V; N0 D/ A3 S' m+ w随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：
3 k- n/ t) b! e# j+ v" x8 n
' f$ _: y) S# b; y+ d

: D" V+ s) s; q' b代码实现：

0 ~% c: c1 r, b% l2 O8 m//从小到大
; w! M! f) O. R. v- r& o0 Tvoid shellSort(int* arr, int n)
{
        int gap, i, j, temp;
8 H- t/ A1 H# R% {& ~3 }7 ]        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
; N3 c) L: T- P/ k        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
; V! r# |4 g, N+ e! h            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
( x2 S1 i4 z; N3 b            {
5 L, Q( V1 C. r                if (arr < arr[i - gap])
                {
                    temp = arr;
6 e. y9 P# A' J: d6 r. q5 |/ |: I
8 r, K+ B" X! Z' V7 a3 X                    //后移
1 M4 R, M. v$ y- K8 l* N                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];

                    arr[j + gap] = temp;//插入进去
( A9 T  {5 e' o8 Y                }
% L: [2 P9 _: o, {( r" y$ v9 ^            }
8 |5 P( }) u. c& c- J            //************************************************************************************
. Z5 D& u, l. L5 W# q* |  u        }
}

. |5 x  S3 n$ [/ }8 t) h: H7 X+ H) v1
2
& q2 H( n7 f, y3
4
' d; [( e6 d' P  {, k5
* d. i! B( Q4 C2 u' t6
+ b% I/ m, Y0 V9 o( c7
8
9 G* d, O' p2 x! {9
4 t7 u- A2 Z: M) ^. p; q8 Z1 R10
6 W& c$ I  W8 \6 ~11
5 s7 s1 Y' x* F! q$ }' [12
5 j1 J: w0 F# s$ _2 F5 |1 h/ T13
0 A) |4 \/ ]0 y14
1 {  a# Q. T* M6 e5 F/ x$ O% \15
+ _6 R* `# u' T4 [1 X3 d+ m16
17
. u+ c" T7 N- K+ [18
* g+ ?( k- t7 W7 f+ T) A1 A7 \19
/ ~+ F+ S! ^1 h8 [. b$ v- k20
0 Y$ W1 I: N: \0 X21
22
- e, A2 j% i; ]4 S# Y5 U23
24
时间、空间复杂度
空间复杂度：O(1)
' A4 b9 ], i5 Y, @$ V! A  H
! D: b$ N  k! @7 r时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)

稳定性：不稳定！
% {, y; X6 Z7 Z" J( K! S  W7 z- N

5 K& v6 L3 M  y' w
% m4 {( N! w2 M( N5 w: K$ a适⽤性：仅适⽤于顺序表，不适⽤于链表
, j. ]7 {9 S" @8 y( J7 _9 Y% j

9 d. e8 I0 \5 _% P- ^7 {% k
2. 交换排序
2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

; T' r0 d8 l, m; F' Z- f每一轮比较会让一个最大数字沉底或者一个最小数字上浮

- ~% M: o& l" J* T% W- \1 o5 R这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
& E. [6 V3 s& \  L1 R# Z' ]
实现代码：

//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
{
- H/ |6 P$ r+ O! Q' i6 `5 D        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
2 h8 V! H. @( ^2 ]        {
) Y, a# [! `# O( t2 |                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
  l, L3 S' A# S8 n! E; l# R                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
                {
. w' ~9 k  n* b% p! ^( ~7 y                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
                        {
' L: U! G) U' q                                //交换两个元素位置
2 J1 q  z% W2 }" a  w" e                                temp = arr[j];
: f# b4 Z, F7 v  |) i! C6 @0 l                                arr[j] = arr[j + 1];
( V9 p# K4 m5 i6 m5 y                                arr[j + 1] = temp;
1 e3 u  ]. t! T$ k) r& I                        }
                }
        }
$ M( c) v( H7 _0 K0 j}

1
2
0 P9 W1 d: g' v! C0 X, e5 f3
4
5
6
7
8
9
1 }4 ^7 u- [6 y4 o% C10
11
8 E8 o6 A! k+ M( E0 d9 ~12
13
14
15
16
0 ^/ j" W6 G9 _6 X& T% j# r$ Z17
18
19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

//从小到大：
/ X2 B+ \' t- y) L+ b3 C5 g: b$ Kvoid bubble_sort(int arr[], int len)
{
        int temp;
8 t2 k- b: _* J1 G* h% J        bool flag;
        for (int i = 0; i < len - 1; ++i)
        {
% r8 p* {0 I9 W8 a5 o            //表示本趟冒泡是否发生交换的标志
                flag=false;
: @. U; G0 ]$ I) a5 ?  L+ Y               
$ R1 i6 l% P6 \6 C2 K                for (int j = 0; j < len - 1 - i; ++j)
                {
1 }# v3 `8 E7 F3 a+ G9 a1 i                        if (arr[j] > arr[j + 1])//稳定的原因
9 x; N. B( Q( K5 Q8 V/ P# H) F6 `                        {
! u& C1 w1 H# Y. {+ a                                temp = arr[j];
% C6 E7 e1 F) s8 J9 Y                                arr[j] = arr[j + 1];
2 y/ m5 u5 ?$ T% K! \' ~& T; L                                arr[j + 1] = temp;
" I* r# N& }& H; Q                                //有发生交换
+ y! R/ Q0 T% L2 J' \4 k# s+ C                                flag=true;
                        }
% t: q  z3 z  {* ^7 M: s1 j. q6 l' t                }//for
- v2 h5 b: C2 e7 u8 f$ S, s  T               
4 R% z, K4 M8 [5 N' Q4 ^                //本趟遍历后没有发生交换，说明表已经有序
( S. X9 h0 R+ ]$ X% B' E5 v5 ?                if(flag==false)return;【1】
1 F8 l) Q( o$ F2 D+ X0 c        }//for
! p& @! \$ ]4 |2 c, `5 {+ |8 G}

1
2
( `) `; J2 s) ^. _: z0 X3
8 F  Y1 d3 k1 a. {2 A; o4
5
6
7
8
) x5 P# Q; Z) O7 [5 e) j% [4 f+ h9
$ F: P9 m) Y& D3 e/ H, E0 m; F* ^  r10
11
8 l% w! \3 N$ T12
13
5 ^6 c8 p  k/ ^2 b& l14
15
16
17
% }) P6 J' A% ]6 b" g18
8 i- h/ V9 {4 W5 u0 V5 v8 `0 K0 }19
20
% O: W1 z5 ]1 M& X: D( H, a9 Q21
) M- J/ A$ J3 J$ y0 Z22
23
2 [0 g6 h1 h; h% G24
25
26
  e2 O( l, T* u  _# A时间、空间复杂度
9 ~2 @7 b" i; a3 G2 \4 n
适用性：冒泡排序可以用于顺序表、链表
& A' [0 v1 L+ x+ f
3 L/ H9 |; D& d4 o
1 o: a, q/ v) {* e/ {4 m
- O' P  [8 L" O) D
& J: c% S0 o: T2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
4 s0 C: d) ?1 H, l1 G$ l) s3 ]% F/ K算法思想：
) X/ o" Z1 R: k/ `' F; I9 i  [在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
% i- J0 c2 t; ]; Z: S2 I使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
3 R. V8 C- w5 t. }2 f再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
9 l6 F  v# e4 ?  }5 E; B
1 U3 P# y: S: L  R划分的过程：

初始状态：取首元素为pivot，定义low，high指针
0 _3 S# z+ N: o1 j0 S0 L0 V% Y
首元素为49
7 z3 X* r" G# P# shigh指针指向的数据小于49，就放在low指向的位置
6 v9 ?6 d7 g+ l' ^- T- xlow指针指向的数据大于49，就放在high指向的位置



4 K) s6 C% {$ d) ?) m

0 x. [8 Q( B( m/ i// 用第一个元素将数组A[]划分为两个部分
* v  i( N" Z8 `7 w' j" h# Fint Partition(int A[], int low, int high){
+ f  q) z7 ?  Y        //取首元素为pivot
/ s. D+ k2 g7 y3 D9 e    int pivot = A[low];
8 I& p, `' F/ b: ^" w
    while(low<high)
' D* q# T2 ?) c$ }    {
4 i2 o% o, A* i            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
            --high;
        A[low] = A[high];
7 e; F: I  x+ {8 v) Q
- ?5 f& M6 v# i2 }! z& `2 w        //随后low向右移动
: g& Z% \5 i1 v  q# z" G        while(low<high && A[low]<=pivot)
            ++low;
: |' r* K% q4 Z        A[high] = A[low];
) ?( e  R& K/ I1 y9 X    }

    //low=high的位置，即pivot放在的位置
9 F% n. ^' c: o/ N2 `    A[low] = pivot;

    return low;
}

// 对A[]数组的low到high进行快速排序
7 Z( f3 G' P) tvoid QuickSort(int A[], int low, int high){
    if(low<high){
        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
9 ~. t8 B& t# q" d8 o; ~        QuickSort(A, pivotpos + 1, high);
    }
0 t) p6 }2 ]9 H8 `* n9 @# b- ~}

1
2
3
& o& h! }, D* l4
5
6
7
2 d& l- B; }7 |7 H) ^) ?3 v" @8
% e! k  \8 B& P2 w- C+ N' t. _9
10
- _- w4 A) U' `+ M. Y1 l  R( }11
12
13
14
% L- V- u" m& O) ]15
16
, c2 C& X3 f8 ^% P" z* ?, ?17
" S; f* \2 D3 G8 g18
19
20
21
+ g3 K! m/ j% j3 M6 Z# m0 @. z5 Q22
& k0 ]: u3 J) \5 r1 Q5 s3 r23
  I/ {+ n/ _2 E8 o24
25
26
27
  {" W  M  h# L# X# I28
29
, A) v" o' L2 K30
31
32
时间、空间复杂度


! z1 M! o) a+ n! x5 T/ C把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

" U' n" \2 E; T3 Ln个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

时间复杂度=O(n*递归层数)
9 s  u- D& V% d0 Q最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
& n) p' s1 A  V# F* W- }! W平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法
- n" j+ U9 o/ L) f) B, Z9 f
1 G! A1 _" C9 S" g空间复杂度=O(递归层数)
7 f5 I; k% d* q4 p最好空间复杂度=O(log2n)
; h5 z; M5 ]9 R" t. X* b6 w: {最坏空间复杂度=O(n)

最坏的情况

( q' S0 ~4 Z- v9 P
6 T, `$ c2 p, \2 X9 I
* l1 ]; ^: Y) B2 d& P7 m5 |⽐较好的情况
% W% e3 o0 u( N2 e4 A& f
; D( M" b4 F# P0 X, I

9 @# N( h4 m* @1 O不稳定的原因：




+ P. i2 q% G7 \' f$ N  L7 d, _
3.选择排序
: W3 N, M4 j1 o选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
; w$ D  h* P; a
' J, m5 K0 b( [4 G- t3 w3.1 （不稳定）简单选择排序
) x* c+ X. I& F' f& J算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置



( e# q% u3 {9 L  q9 D3 t7 o+ u: B// 交换a和b的值
  f1 [+ K- I$ p  L  K4 ]void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
{
        //一共进行n-1趟，i指向待排序序列中第一个元素
( e2 P& y3 {6 r    for(int i=0; i<n-1; i++)
    {                 
        int min = i;
( n9 P& p  g9 P; x9 Z: x, B        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
  i7 `1 Z6 Q& l' \  b+ m            if(A[j]<A[min])
                min = j;
* t' k& h8 d6 J) R- d/ S. O4 U        }
        if(min!=i)                     
            swap(A, A[min]);
    }
$ z/ w  E  n: h: N, t' b* M" O}
. g- A, p* ~+ X
* @% p/ M; ~" Y$ G$ {1
" ]" n" z! M; v  B) {2
3
4
) p  G! n8 [' B7 ]" r5
6
7
8
. M7 V# N- M5 i, V9
10
/ N1 I; s' H8 K8 O11
12
  [; y$ m( U6 u# _13
14
15
' {: }* e8 ?3 o) w% C16
" L3 g: E( t& K# k* o6 X  {9 X17
) @7 U6 S4 L9 c& i( E18
19
0 a9 L- k) e& g1 F7 l& [4 |8 C20
21
22
8 e/ d8 J' F, u5 e) B; W% T补充：对链表进行简单选择排序
! H  x0 T: B; c9 h3 J6 |0 t5 y
void selectSort(LinkList &L){
4 @: J$ M" _4 [8 S    LNode *h=L,*p,*q,*r,*s;
4 r7 `# S! o* F  S8 I/ z1 G8 d. t    L=NULL;
    while(h!=NULL){
  w9 n( l- Q- e- n  N% O0 `        p=s=h; q=r=NULL;
        while(p!=NULL){
            if(p->data>s->data){
                s=p; r=q;
            }
            q=p; p=p->next;
: K  F, O% m) u1 B        }
1 S" ]. t. y# H; x        if(s==h)
            h=h->next;
        else
0 e7 g$ b# N2 ~            r->next=s->next;
1 [/ D$ f% ?& M6 o( A# y1 ?        s->next=L; L=s;
    }
* ~5 P" }# C3 v1 s; O; E  w}
# t5 O( n! }2 q
1
2
3
4
5
1 L1 X1 u& a9 N7 T2 ?6
7
# C7 ?. S' D! k9 M# y8
. E3 o* s$ J& a) x; M9
" i  R7 P7 T2 e/ t1 M8 X; Y8 V, x8 a10
) J9 j6 z3 |4 \' [4 U3 X11
. ?+ {* z2 e" I12
" b$ C% n4 E& J/ Z. U3 M13
14
15
16
8 L0 b; w# h* A  K* S- }17
* [0 v% D- _; ^7 m* h4 I18
时间、空间复杂度
) ~# \, M. b1 W# t
( r8 l" s: S; h$ |; g

, ~. g, }/ T3 M* |4 s1 U
适用性：适用于顺序存储和链式存储的线性表。
' X) M' w$ B+ `/ ~, ]) j/ T
- K$ l+ P! q  V4 q: n. K6 _5 u" P

3.2 （不稳定）堆排序
. r' k/ M1 ?" \" J① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
: Z- p/ C8 q8 w$ a; V! M8 D1 W堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
) {7 _# S, H( i$ Q

! ]6 x  l5 j4 C. d1 x
1 G3 o9 w; R7 C' H# y即：
2 B, P+ F7 V; |1 a6 X; d0 ?若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
# h5 |3 c, X& z# ~若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）
/ O$ A& ?  J! f. l# J! J
. s9 V/ h" s/ u! r0 A7 N1 d: s② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
; [( c4 {! S/ u/ g' G: D: E8 i
! R9 i* o6 L! b, H5 U在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

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

5 L& R. |6 Z  ]( X5 L  l过程例子：



建⽴⼤根堆（代码）：
: [, {" H: j* A% B
8 o  T& v7 E3 w, g# n; t" I
( _2 R0 z" T2 A; T7 w
+ Z7 \0 ]- M' O! T" _6 H% `* U// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
& \5 ]4 n/ L$ ^! _5 P; a3 g4 M    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
8 C# P7 _* g* X}

; O9 ^$ y& B& v8 F// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
$ \7 m. l0 i% B! P! c0 }    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
            i++;
        if(A[0] >= A)
1 j7 v! j( ~# R. _6 K# `' b            break;
) w# F/ l6 H3 [        else{
            A[k] = A;                        //将A调整至双亲结点上
: T: c& T1 a5 H            k=i;                                        //修改k值，以便继续向下筛选
8 b: g' \, S+ b5 X        }
    }
( P3 Z/ B' O3 Q7 ]0 r" m    A[k] = A[0]
* |% z8 i) ~0 F}

1
2
9 T$ b8 D: n+ u1 y2 i; J( d3
4
5
/ `/ a* J! x3 Q/ c" X) H: x6
8 ~& Q4 l5 _# A. q' S7
8
9
% M9 x3 I5 X1 V10
! [& }4 l+ p1 R7 g1 H: }0 l2 z/ H0 |11
12
  m8 B! \6 h/ U: s" V. Q+ c13
14
0 J3 \. _  }' o# f. Z" f15
16
17
18
19
# I) N0 h. m4 S& q7 c20
21
2 `. T+ @9 f, J③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

9 q. l$ S; x8 {堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

, [$ h( \8 x; R( Z% g; Q6 a过程：

8 S1 N+ A8 j. q; S$ u! g// 交换a和b的值
' s* B' Q/ q3 F! O: n, {void swap(int &a, int &b){
5 t9 U7 B* A5 Y: @, _7 l8 X    int temp = a;
    a = b;
$ }! L' e& M! }1 O2 Y( D    b = temp;
: H3 v4 v& x2 ^9 j5 v" E4 f}

// 对长为len的数组A[]进行堆排序
: v! k! g* T6 @) ]  t+ @/ H9 E# bvoid HeapSort(int A[], int len){
        //初始建立大根堆
! g, p. ]' s1 b3 m3 X; P    BuildMaxHeap(A, len);                

    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
    {             
9 w, n6 ]" {" w% ~  \% E: h        swap(A, A[1]);
: S+ l! z/ U) h" ]9 o( a        HeadAdjust(A,1,i-1);
    }
: ^' o( [% C" k- H' H}
# b0 j8 m. H2 G/ [$ D5 E' c
' ?  \- N  d) L$ W  I8 t1
! m: @$ V& G0 t. H" T1 y+ }2 R2
3
; L% @6 @5 b! H" U3 o+ h4
3 N& N9 I1 \" R; V0 ]" s8 s5
6
7
/ h3 M, {- d9 v2 [7 [- s, G3 K8
+ b* `4 i" u$ j) U7 {9
10
& g- Q( p! @% }; i! o# c2 z& P$ X11
12
13
14
' D' H$ M6 B7 j" \2 ^15
16
" g  z& W& I# ]- A. l, F& K; P( j17
18
19
时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
8 a6 e8 |+ X/ S
空间复杂度 = O(1)

) v9 x$ ~$ l4 e1 D4 ~. w/ ^结论：堆排序是不稳定的


* D% \/ N0 R5 }+ ~! H. ~1 P. N* r④ 补充：在堆中插⼊新元素
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
: w1 B+ \! w& t, g新元素就这样⼀路“上升”，直到⽆法继续上升为⽌


. Z" W$ e' T8 u/ l
⑤ 补充：在堆中删除元素
; u* V# a. K3 C0 c) q5 b被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
: q$ e+ u+ y5 T# y; l0 L$ u4 s
3 x6 r7 h/ e8 I, E+ W. q5 [& r

' x- ~- S, ^2 M% J

% B/ l* {% s* u2 F4. （稳定）归并排序
8 o  @0 }$ P2 v归并：把两个或多个已经有序的序列合并成⼀个
& [$ H' \- A9 q+ z* f; I, p
2 ^$ |/ S, ^' j9 Z$ H$ W① 明白什么是“2路”归并？——就是“⼆合⼀”

+ v8 U) A( |4 J; }# r' o多路归并：
& ^  z& p: {& I# t2 H8 a3 o1 o4 s

② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
4 P' W2 i0 v4 E6 G# v- G
B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

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

8 y5 r( m; t& |  L/ ]
2 u9 c0 c. |' z0 Q. `2 O④ 总实现代码
' L. {6 H) ]3 L$ Z: `: O) ~) k// 辅助数组B
+ d" w" \8 x2 T! P2 Oint *B=(int *)malloc(n*sizeof(int));
/ j$ z! Q" F$ G3 C1 R
// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
' W! H0 B2 F6 A8 j, s/ N$ Q    int i,j,k;
9 f: o1 ~% p) @7 k    for(k=low; k<=high; k++)
        B[k]=A[k];
    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
% t) L: L' Q+ e        if(B<=B[j])
9 i; z$ [! K# X, D8 V            A[k]=B[i++];
1 q* e2 v- [2 d" R( s  t: l        else
            A[k]=B[j++];
    }
    while(i<=mid)
        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
; }0 b+ j) l4 X+ b1 B) M}

# G$ e* W. z6 K2 E( T
// 递归操作（使用了分治法思想）
void MergeSort(int A[], int low, int high){
    if(low<high){
: e4 J! M$ |4 `$ P/ H- |( b        int mid = (low+high)/2;
        MergeSort(A, low, mid);
/ b0 I. t6 |2 D        MergeSort(A, mid+1, high);
# y: Q' o; L0 Z        Merge(A,low,mid,high);     //归并
2 m2 b: B/ G  h! B5 p) W0 `$ L  D    }
% }7 K( [8 t+ N- Q- g}
" A0 [/ ]; O  m  f/ g) V
1
2
% _7 G' q" n- T' e3
4
- m9 W/ J- e  ~2 _4 r5
6
7
/ n. Q2 {5 ^. k! s8
9 P9 Q4 @8 X" P, p9
) q, s: _6 P- J: j" M# Y" o10
. `; C2 `" [4 U2 |1 M, l5 z; z# P% P11
12
3 N  p8 f: q6 E13
7 y& r; ]  m; F/ l9 J, i14
, }; U  }8 l0 z4 X8 B8 Y15
3 o6 S; {: L- [3 ~7 E  \16
17
18
7 g: s7 l; E  O19
: J+ ?% J8 Z6 i+ |$ U! S+ R/ R9 a7 b20
, F& K4 O' [9 X5 w  u6 h21
22
8 K6 n& Y% d; {' @$ D23
( c5 Q' D% n  \9 p. S24
/ M% u6 D0 h* b1 k9 W, t; k* K6 ^% R25
26
; C2 n7 _. U! u& _, o27
28
29
30
时间、空间复杂度

8 R7 y4 a/ v7 R

0 d7 D) T3 l% c2 v8 C
: P: O9 W* W% c9 E5. 基数排序
直接看课本的过程图来理解P352
8 X& }, ^8 q: _) [0 `
7 }* }1 o3 e4 c0 c再看这个例子：
' m6 I# }0 _' ^( k. P; ?

: p4 n1 o( j/ h% O9 I8 K6 I, a) H) F" e算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
6 }: m& i' N; U①数据元素的关键字可以方便地拆分为d组，且d较小。
; ^- {7 ?- n  J2 |1 K/ ^8 k, l; n②每组关键字的取值范围不大，即r较小。
7 ~0 y6 _$ ]2 k7 O③ 数据元素个数n较大。
$ u6 @" z) Y( Q' R5 o* V算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
稳定性：稳定。

1 r0 M$ s; O) L9 G& }8 J
4 T. x6 \% }7 p8 W# m: M0 a1 z* [内部排序算法总结

4 X; ]7 l. ^( ?, Q4 |$ q5 ?————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# r& T/ D9 Y8 Y. V原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969