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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
排序
( W' T! _" A" p: R9 ]' v1. 插⼊排序
" n. {" \8 o7 p1 c# ]$ l（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
时间、空间复杂度
, X; N/ [9 a8 D) p/ V) j6 w（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
$ J; R4 R# U3 G1 `$ I/ T5 d' f时间、空间复杂度
; j- l8 \" Y* X- N2. 交换排序
2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
/ w' ~/ Y& p* N! U9 {" @( p, g3.选择排序
& m  p1 I+ y, B6 e3.1 （不稳定）简单选择排序
/ X( T% g1 G* E; b时间、空间复杂度
3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
" E7 P' u) m4 D$ E② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
) i8 w  s" k% C( W③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
" c4 q1 Q# O- ]) ~' e' E时间、空间复杂度
④ 补充：在堆中插⼊新元素
, _6 j2 A$ D+ w. _, M) P; d⑤ 补充：在堆中删除元素
4. （稳定）归并排序
( i: M, z* p: }9 [, \① 明白什么是“2路”归并？——就是“⼆合⼀”
6 G3 y8 J. ?7 Q/ r* g0 P0 X: a② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
3 L& w6 p8 Z# k  s④ 总实现代码
& y5 q/ n( n; n5 S! Z: Z# n* q时间、空间复杂度
" z! {- P, F8 m8 Y3 Y: r5. 基数排序
! D% }5 w. B4 l- L( l4 D' p( r内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

排序算法的评价指标：时间复杂度、空间复杂度、稳定性。

算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。
7 S( U# g0 @- D& Z0 t3 z8 K
( ]: g. _" }% s0 a* d
排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
( m: b" E' \8 w% n; x
8 j2 A9 q. ~, A" b. r& u各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
. e& r" Z) h) ^7 H

, a8 R% ~7 m7 Q5 K
6 g/ f! b/ e! \1. 插⼊排序
9 n; z, u( ]9 p$ d$ d' q6 a* k（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
# L) r8 h4 T$ o' M/ n5 Z& D/ O  h
算法解释：（从小到大）
5 D3 ?# x* H! [" Z4 \

算法三个步骤：

先保留要插入的数字
往后移
插入元素
3 }5 R! p( {5 T1 ~
// 对A[]数组中共n个元素进行插入排序
+ w9 j# D* E' e, Vvoid InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1; i<n; i++)
    {
! Q& B3 `6 g5 G' R" N( u2 \/ n  _            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
        if(A<A[i-1])
- ~5 {& Q( K! }. V        {           
6 T  |. t% |( ^8 e% F            temp=A;  //保留要插入的数字
9 V' T9 n1 T; i; g  R6 v
            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪
) u: v0 E, M; g' V
' b" p/ U9 L  u0 G: C            A[j+1]=temp;//插入元素
        }
7 K% Q6 l( X( p% z    }
}
7 H% c. a  N" N" c# L6 W
. ?! u& U1 o: G  a1
2
8 ?" u8 A: o3 k" _( f3
+ `! K, w" }5 r0 W3 s8 @. x4 S' ]4
% d, m, L% b" t; h, ~- E, W: g5
8 ~6 p. a, L: g$ G8 G5 z% P6
7
/ L5 H) h, l: Z& m& e8
9
2 r* N  I" ]3 o" m! b10
4 c; q1 U3 P* d; ^% t11
12
13
14
0 H/ K/ J, V  e' i6 h5 M' S; G15
$ D5 {, e0 N6 b3 S! H/ B! ^16
17
用算法再带入这个例子，进行加深理解
4 @% D# r# k3 r" x  T

带哨兵：


补充：对链表L进行插入排序
, v$ X" O7 X: L. @  X
void InsertSort(LinkList &L){
' y+ n3 P$ f3 k/ I& ~) Q0 g    LNode *p=L->next, *pre;
    LNode *r=p->next;
    p->next=NULL;
    p=r;
    while(p!=NULL){
        r=p->next;
* c( i# ~$ T  o        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
        p->next=pre->next;
0 r- P* k1 d7 r& ?5 G7 x. J        pre->next=p;
        p=r;
    }
0 w- w9 U6 t. s# V1 L- Q. E$ n* n}
  N1 b! V/ u7 _" ]4 ]7 ]- Q1
2
9 @  c3 O. R% z+ t# ~8 X) U. b: `3
9 {" J8 b5 C$ P; O: `: \4
/ Z8 A% a# L7 M9 Z5 B# }+ a6 s6 e) k5
! [; U0 H; J' ?  g1 A4 S) p( H6
! N! @4 J+ e6 d* B5 X4 G7
8
! T! @- U3 s4 t( I  q9
, g3 m7 {4 C& b) @10
* p6 }, x( l+ `$ O3 e  G+ m# D11
12
6 H) y- G: T( b; [  B9 t13
# _' r9 r2 O- M3 J+ \14
# ^8 {- Z  ^, N$ @7 o* V4 o15
8 ]. N7 d- E' ~, }5 ~; l2 g  Z! u时间、空间复杂度
4 x& X4 }0 F' T- V0 G. x
* ~9 N" W% ^" i9 ~: H
最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
4 g5 `5 G# x/ z3 K% C- I最好时间复杂度—— O(n)
% _* f0 ?# ]3 ^
最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
, X- r% Z: f$ f…
/ v3 }. L$ ?2 ^第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)
* S+ ~$ g9 w9 @: R2 v
2 H$ W) t' O& c8 a) D' t5 X+ y2 G1 U


5 @* ]& ?) J5 e% A5 R6 {
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
- [  k' O. S- ]. H6 V& ]' R: L过程：
# m6 v( u. n5 W$ A) `* k
5 ^9 z! S4 z$ C* m8 j" V

//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
( c! ]. x. {# ]{
    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
; H: \" Q$ o' D% `0 t  s    {
        A[0]=A; //存到A[0]
! M. m* n) u& i  U; K% g, f6 g. C4 t8 |1 _. G        //-----------------折半查找【代码一样】---------------------------
- J& T: Q! ^9 W        low=1; high=i-1;
, W% q$ Z# a0 |* i  m9 J& h" w# g        while(low<=high){            
            mid=(low+high)/2;
            if(A[mid]>A[0])
                high=mid-1;
' ^& U; K" e7 t5 a, ?3 }            else
7 t/ b  w3 @8 c% p  k$ ]                low=mid+1;
( i, z( a7 \3 ~        }
         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];

        A[high+1]=A[0];//插入
    }
7 `! r0 N" z' M9 [8 N% _  T. m9 M}

3 |% Q, B: }5 w- W& z' L! B7 s1
2
3
) i9 F! b2 \6 s4
5
; n# q6 @& Q5 @$ f( }6
7
0 J. N' U6 s* b2 F+ y8
# v$ ^9 R0 A. Y4 k8 e9
10
. c8 m& `/ V) L. R& ~5 k11
3 F9 S# m. ~8 H% O3 F12
8 g4 q4 u6 e! _/ o' k13
14
; {1 ?6 F7 E4 X8 w3 o9 d% ^15
16
" t: Y' f+ C$ {  @7 g% @17
18
: q* F, B0 ?6 D3 i2 U( v( h" f19
. B* Q2 j1 h( T20
21
- t/ U" a/ O1 g# F8 W22
23
时间、空间复杂度
空间复杂度：O(1)
4 d6 p3 w/ L/ E( s( f0 J
; @: P& r- `4 K9 A1 _【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
+ A& z& q' L7 J" V
  ?' ]9 V4 b; l4 v9 p/ J
1 q6 U" @) u( C9 G  M/ N1 l# G. [8 E+ M（不稳定）1.3 希尔排序【多次直接插入排序】
5 p$ |  B9 _, ]) P$ w2 X是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
- _; \* i% b7 {; B
算法思想
* i2 k. C0 U* y$ I
* p1 @2 v& O; T" R( T' R+ |希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
& I* |& b. Q/ R% a( [+ B$ G! ~. H" _随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：
1 |, P5 t( V( ^3 q) |

. K! \" k# F( _
) m7 ~% x! F2 g- L4 E# }代码实现：
! z. L, f7 X% o. f
//从小到大
" P. Q+ p% u& N3 fvoid shellSort(int* arr, int n)
: u7 u& U' k4 c. @) e8 x{
        int gap, i, j, temp;
* [! _& [7 h0 D$ V* @        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
9 g5 Y) j0 P3 D' D# Z* D+ ^3 P3 b        {
            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
/ A" h! _5 o2 g' z- ^, x                if (arr < arr[i - gap])
                {
& l8 q' f; Q; g& f$ k' u1 v: Q                    temp = arr;
# T$ w8 y3 F4 w% r4 ]
2 Z  f7 p' m+ R& z                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
  ]% L8 D7 @; b* @! n                        arr[j + gap] = arr[j];
7 t0 c- ^3 ]+ W" t+ r; W
9 c, B; p1 l0 b: S3 X- }1 G8 W                    arr[j + gap] = temp;//插入进去
                }
  L+ _% `" I8 c4 q% U! P            }
. W! a. P, I4 e            //************************************************************************************
        }
) n; G7 R! v3 Q/ @# ~. w}
9 i5 Z: e4 v6 Z
9 V% h# g* {) x) O0 d) V+ |1
2
  O* E. n6 d' f* m0 _0 }" ?1 ^. T  m8 o3
4
5
6
* Z. R* o$ D& o. G+ V* _7
# V/ a+ d  C. O" a2 o8
5 m# Z$ U7 s" @. C. {$ ]2 v9
" x1 A% T2 _5 E' ]10
1 k: z( ~7 @4 a8 H; k1 e+ O) l( q11
! o/ K3 e+ o5 b8 ^0 @/ }# @12
: A: b' y% ^1 F/ b% `13
14
15
9 a1 M; [) f/ ^# I16
17
18
19
- T$ P! o6 M. a( Q/ X20
21
22
2 C" ]$ I2 K+ D0 H( Q8 y- ~23
24
时间、空间复杂度
空间复杂度：O(1)

时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
# R# X) I4 {' T1 h
3 P% Q# p, Q8 t. Y/ Z: h: t稳定性：不稳定！
3 p/ ]# }$ [. x. H


适⽤性：仅适⽤于顺序表，不适⽤于链表

. S" o, B$ v4 J0 P

2. 交换排序
2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
; m! u: T. I4 H+ K' k从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
: D4 \, A: E! O
  u! d# b6 t+ ?2 k/ n7 u! L每一轮比较会让一个最大数字沉底或者一个最小数字上浮

, k) P  a6 u2 R! j这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
; e) o8 F- ?7 B
, H1 r8 L! A0 X/ `% ]! f实现代码：
) e9 y6 V8 Q4 z+ t4 B: _
//从小到大：
# l. W: G% ^# P+ ]/ ^% L5 U  wvoid 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)//从头到尾比较一轮
+ ~' |! B& h" F# r0 q  Q7 v4 `: P                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
9 Y# I7 u" g2 p                {
                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
7 A* w' {% q7 w$ i) A                        {
                                //交换两个元素位置
: H) |- K1 C/ m  V! k4 X* }                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
9 T5 R' A3 q- n8 _* j                        }
                }
        }
# }! ]9 @8 s9 N2 G! X5 g& d4 h}

1
- B6 N' O: J/ u5 Z' x. k  ?/ q$ q2
' V9 i6 J& L9 K3
1 W$ n) i/ Y9 @4
! H5 G! q5 t' ^8 K! q5
6
7
9 ]  N7 p3 W, b) h0 U8
1 \# r8 D+ E; a5 s4 q9
10
5 o. A4 `4 h; e8 k( Y, s3 J( Y11
12
13
14
7 v# h  [  }7 S* \3 G% |15
16
17
18
19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

( z" p$ F7 ^& d/ A1 A- H. N5 {# ?//从小到大：
void bubble_sort(int arr[], int len)
6 x4 \1 r# l; x! d+ k{
7 F/ \$ `8 U+ s: f5 ~; Q        int temp;
- q5 `6 M* T4 |! b- R, N0 }        bool flag;
1 W1 d; Q/ `, G! L        for (int i = 0; i < len - 1; ++i)
        {
            //表示本趟冒泡是否发生交换的标志
                flag=false;
# i) o$ \) x& @/ E, h6 K- [               
& [1 |0 A5 I7 `/ r1 Z# \# q0 V                for (int j = 0; j < len - 1 - i; ++j)
                {
# U* E9 [: }+ P9 h8 t" e                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
/ Q# ~+ b# {. b                                //有发生交换
                                flag=true;
7 g: V1 C4 j6 O                        }
/ \1 h/ n8 \: F" \                }//for
               
$ Q6 b0 N' \; [' O                //本趟遍历后没有发生交换，说明表已经有序
( o/ ]# X5 l) M0 A1 `                if(flag==false)return;【1】
        }//for
1 F0 R; z- a' }2 w& X}

5 A% @  _$ [* u) a1
2
3
3 t, c! a% j2 ~- A- ]  v  }4
  f/ U) [2 R! Q: @" R. N) ?5
6
7
8
- [0 ~6 e2 ?$ f2 `5 i9
& Y# z/ a  Z: F10
11
12
13
14
5 `! v* y( S& H& W5 C3 y2 S15
16
17
18
3 U3 M( @: q7 b0 C- W19
6 ?/ o7 w7 M2 i$ T9 H20
21
% A2 ?5 R* x3 m22
23
24
25
26
时间、空间复杂度

: {, y2 c5 p# I& Y9 ]* T/ F6 ?( G适用性：冒泡排序可以用于顺序表、链表

/ B1 c+ F) E7 ]1 C4 d$ _/ B

& @" v. K  `+ M
4 L- W( ]+ B0 `5 |5 G" D9 z2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
+ l# J* o5 l! g3 Z; W算法思想：
' ?' q6 u* Q- }' A! j在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
+ \8 x' I4 j8 ^0 L. p; L! n* n+ ^% Z通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
  ?! s, i  E3 a
然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
" y! }! a/ g3 L
划分的过程：
7 V" w$ w1 [; q2 H! \+ T# O( O
7 r" h) g3 V8 t! l- K' \/ h初始状态：取首元素为pivot，定义low，high指针

首元素为49
high指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置

. R1 k0 B5 P3 ?



// 用第一个元素将数组A[]划分为两个部分
3 R! e% `7 S# ~' F+ {  Zint Partition(int A[], int low, int high){
        //取首元素为pivot
    int pivot = A[low];
  C% {# G; j, b+ `
: m; N) T) b- m( q: B: x    while(low<high)
    {
- f; ?* Q) _5 [& x2 H* Y, C' ^! @            //先是high开始向左移动
0 ?6 Z7 T; j) r9 ~2 r. a" Q        while(low<high && A[high]>=pivot)
9 }) ?5 B& A" o+ D% L# {0 @% q            --high;
3 ^7 X7 a# |8 d+ R        A[low] = A[high];

, L2 E9 k/ ]% t; p3 F5 a        //随后low向右移动
        while(low<high && A[low]<=pivot)
+ d5 W3 E% |/ }- B9 g* }            ++low;
        A[high] = A[low];
* ?" p6 p8 q( J3 F( e' l; }    }
# \' W5 u, {! B5 N! u+ x
; C- D$ X! v) m( B! g8 `$ n    //low=high的位置，即pivot放在的位置
" V- M5 k  P0 l( W6 p5 a, h    A[low] = pivot;

    return low;
& Q6 T2 g  H7 u9 \8 W}

9 F$ c3 T  r$ h% h! n9 x/ o7 v# k6 ]// 对A[]数组的low到high进行快速排序
void QuickSort(int A[], int low, int high){
    if(low<high){
; J6 Y; }+ n. n        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
1 G6 ^/ B5 C% e$ H        QuickSort(A, pivotpos + 1, high);
/ K/ F$ C: S- h3 m  d- R( j: @$ q    }
}
' D2 P; [) J- T( h7 o/ @' z: C
1
2
) t5 W3 U( j! T8 I7 `3
' \3 K- q" U# W4
  Q. ~& Y9 E: c5
6
7
8
) V2 ~7 \6 d) i  V9
10
11
12
13
4 c8 k' l- @2 u4 b14
15
16
4 v8 f" k- g4 b! I7 z17
7 g! ?! i# Y1 P% @* M5 b' D6 |; t18
19
20
21
22
23
9 G5 h: t, |5 k5 ^24
# Q/ j" I3 W8 L- u7 ^25
26
27
28
" ~) r4 v6 E, {2 \29
9 f: o" \) K+ S  L30
$ @5 ~, a/ q* I8 S31
* y3 n5 D6 r; C8 D32
5 h+ l! \5 _. b" P& J& }2 ]( B2 Y时间、空间复杂度
8 O/ b! X) V/ h6 t0 N' }2 V3 I
/ D+ }( X8 C: `+ _6 k) T. i# p
把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

5 G5 g+ o) V; Q7 pn个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

7 t$ ~# D. g/ y: J; `时间复杂度=O(n*递归层数)
' l* ^% D* v& X最好时间复杂度=O(n * log2n)
8 D" b, E* W$ p; A最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

+ Y' s# \$ Z" U空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
- i1 X5 \" ^, r- X; ~7 X9 H最坏空间复杂度=O(n)

& P4 V2 ?% N: B0 Z0 K最坏的情况
% v! N; _! w* S: @

7 s/ x- D! j+ J% ~. V
⽐较好的情况
4 R5 f5 z! ^3 P+ @6 O
, |3 z- [3 s) Q( P& [' o+ E

不稳定的原因：



' y) Z2 X0 y. Z7 Y, U
& F8 z" l" M1 T
. y) u7 V+ j8 g# }- Z/ S! T3.选择排序
- K; K% `5 Y6 P$ T. W& |选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
& [/ C/ Y' c5 k9 p* G+ s0 F
3.1 （不稳定）简单选择排序
6 r) c9 b+ B0 v1 L算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置



" d" V0 P! p% f; ^- w  S// 交换a和b的值
. Q  P! i& L4 U3 B2 U+ ]void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

// 对A[]数组共n个元素进行选择排序
" v8 G, H1 g& y: y2 pvoid SelectSort(int A[], int n)
7 L4 e" i7 {. s1 N( N& l' {  H{
        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
    {                 
        int min = i;
; f; G1 r/ ?* j; i9 R) b( P        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
  @0 R- `* a' G; ~$ W4 g! R            if(A[j]<A[min])
0 a# I& h. c' g                min = j;
! ]8 i9 d* E* K. B2 r6 O        }
# u2 v1 ~5 l# n8 r/ I; z* J1 p        if(min!=i)                     
            swap(A, A[min]);
1 q) M! P& F$ z: r" u& }5 l+ w9 e  D    }
4 p* V* r# R* Q/ ]" |2 ~}
5 E0 R- J9 P8 M
1
4 H0 j3 g0 Z+ M5 \2
+ N: e$ p0 ?3 o. E, }/ p2 m3
4
5
( R/ u$ I* g3 @8 t* m# N6
, d/ t' q" a. h( g# r7
6 D) u" ^' f; h( d- S8
7 o+ P5 o; Q+ c9
10
3 E! |, }) R: I6 ]) @( \11
12
13
14
15
16
17
18
8 X6 _0 E8 Z" o2 P+ u2 C19
20
21
22
  Q  I0 U# @$ e6 B! t补充：对链表进行简单选择排序

void selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
    while(h!=NULL){
$ H  C- Q% m8 i; h2 O' y; ~! K        p=s=h; q=r=NULL;
6 m3 I; [/ I. P/ d7 B1 Z% d        while(p!=NULL){
            if(p->data>s->data){
                s=p; r=q;
& U; L+ q7 `  e            }
            q=p; p=p->next;
' J: H3 O0 s2 |4 _  o/ q        }
        if(s==h)
            h=h->next;
1 ^7 B! ^3 e+ u# J& v        else
9 L! h7 v! e* [            r->next=s->next;
& K6 I7 D+ P2 R8 l        s->next=L; L=s;
    }
}
+ ]6 k+ _$ ?5 d& N8 y/ \6 O
1
2
3
5 T9 d+ a" ^: l6 w4
5
6
: T9 \% A$ b. N1 ~* T7
8 b/ G7 _, [5 c9 t# g* J8
9
1 W2 t" P2 J) G1 V% S1 l, x10
11
6 d$ F% f  l( s, s0 `- v' O12
13
14
( v+ A! z% z5 {- ?15
16
8 I! V; e* k* f1 i3 i17
18
$ z8 A7 L: U% X4 M8 N时间、空间复杂度

/ R& T2 w9 ~5 y/ _8 J! K6 [" W
/ z  m3 A' v" U3 T

适用性：适用于顺序存储和链式存储的线性表。

) m& O& Q. P- X& T

8 w1 [% F% X" i+ l% c3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
) h" k/ M3 t7 d6 r  e* x' `1 x6 x每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
: M' ^2 d5 e/ A& C- Z1 Y  J

7 w( |2 G# M( D" q" q4 S
2 b3 }) B2 ^( P6 s; W  p9 E4 l即：
' ~/ r' E! B" y5 T2 f若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
$ p$ g5 z5 `8 X若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）

! o: u4 j! y' _4 X- n! m- k5 \7 i5 T② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
. S8 G. d  z3 u3 ~7 l  m
在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

4 [! F! G* |, F1 b' I. U6 u检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

过程例子：
6 Q# X5 s0 ]5 V2 j5 N. t+ S

4 r& Z0 ^7 y- _( H
建⽴⼤根堆（代码）：
' B: S- ]) \5 y; g' b% O  b
  h1 X2 u. J% f7 F- D" D

// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
( a! M( C7 R: g2 B& M- l- H}
4 S: k3 V+ C/ W2 }8 Y8 O
// 将以k为根的子树调整为大根堆
- Z8 {: O9 L: bvoid HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
! K' C1 _  R# {. s7 y+ Z5 [    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
! N$ V" g6 u) i" G            i++;
        if(A[0] >= A)
            break;
        else{
8 ~; H0 g, w0 r% O            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0]
}

0 }! ]+ D) ^8 e9 b1
3 d  y/ ~6 S$ h2
# x9 S, W$ g+ |' r+ _4 V' D3
4
5
6
7
8
9
10
11
12
- I  L9 R4 N/ y0 [2 I13
14
9 c' I/ ]1 R, a& s15
16
* m; b, D9 V& Y17
18
19
; k2 W% U/ o  I20
# T; u3 ]; z- j4 `" e; @. n; ~% f21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

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

过程：

// 交换a和b的值
% g' a9 h! Y4 K2 D7 B% @; fvoid swap(int &a, int &b){
7 M8 ~, |0 g; Y! J. a3 ?! _    int temp = a;
' @0 d. B6 B$ ?+ ]6 ?    a = b;
- j) d% T5 f% _5 P6 Y# D5 L3 D    b = temp;
9 \, Q5 n) b  D8 P}

// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
+ a2 w; P! h3 o        //初始建立大根堆
    BuildMaxHeap(A, len);                

7 r; M3 i5 k' p    //n-1趟的交换和建堆过程
$ E# B: A" W+ g7 x9 z" k    for(int i=len; i>1; i--)
    {             
        swap(A, A[1]);
) e" R  ]* v: G: z+ s- ^        HeadAdjust(A,1,i-1);
    }
}

1
/ T0 d4 S$ t5 M1 C  G* i- h2
3
0 x' X* Z( U, [( ~1 G4
8 W1 n* n+ M/ s9 n5
( Z8 v6 v% `( ^3 X& t$ x3 J  s% R3 Z6
7
( W2 p7 X* [9 s$ }7 a8
1 E9 W! m* c. F0 U2 W9
- J6 ~7 @) I/ D' C. h, Z- Z10
2 j6 u6 W- B6 I$ K8 ~# f% V, s11
8 X9 {6 E2 d1 L$ [4 b- h! Q4 w12
13
14
( v# m2 _. J- a) f* Q" e, u* h15
1 n# f- k# Z9 s* Y16
) @8 P% R  P! y( K6 E: |9 V) y17
18
19
时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
  Z0 V" v2 ^3 [故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

空间复杂度 = O(1)

结论：堆排序是不稳定的

. l  U2 R! k1 b- `  O! F4 X
④ 补充：在堆中插⼊新元素
7 T1 S, j4 L2 l5 _5 ~对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
- q4 g/ w& c2 w, v0 [新元素就这样⼀路“上升”，直到⽆法继续上升为⽌

/ {5 Q, E0 b& h% [, j- N
- t1 k# \8 u$ Z$ p3 ]9 A! b
" m- j6 S+ a% s& i, W⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
: p4 Z4 ]4 ?. P, c6 e& ?- |% o: b
4 R; q7 A3 G, l1 j% ]: N
& d4 {" p; r# Y$ ?4 \7 b9 A$ v
  M+ V2 F, B6 u1 p8 D  r
; v! p3 ]* S/ ~# q$ |3 O* I
4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个

① 明白什么是“2路”归并？——就是“⼆合⼀”
2 m4 b; C5 n7 u1 _7 l2 Y
" x. T& U9 l- ~" W' @& |多路归并：
7 B5 {: N0 k3 k! ~$ l4 b" e

) D" q5 r, k5 r! v  ^- F2 ^② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
- {1 k. B1 K% u8 Y
③递归进行分治思想【MergeSort(int A[], int low, int high)】
/ p% `+ S/ m( w7 O3 U
8 x! t  n& M# C; z: J
④ 总实现代码
// 辅助数组B
' M& a3 e- [8 G4 A# a7 T8 h1 Zint *B=(int *)malloc(n*sizeof(int));
; c9 g0 f  |/ B! o# H
// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
) ?" W8 E& L2 J& _void Merge(int A[], int low, int mid, int high){
. x- Y2 r5 s' X3 P8 r, y7 J; e    int i,j,k;
7 u. Q+ \' R5 Y( X& I# T    for(k=low; k<=high; k++)
* i% l7 H5 }" B+ L  \+ @        B[k]=A[k];
    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
, l) C0 o3 `( E- P7 W        if(B<=B[j])
            A[k]=B[i++];
        else
            A[k]=B[j++];
    }
    while(i<=mid)
: I. K- u! {# Z" O7 l1 k4 l9 T        A[k++]=B[i++];
; j+ a0 n/ z4 v% ~; L) k    while(j<=high)
$ m6 V% z- }8 ~6 B4 f        A[k++]=B[j++];
}
( D$ N7 _0 a0 R8 s. s* ~
2 S2 T0 ~0 J# o+ l( {' X$ U3 ?
// 递归操作（使用了分治法思想）
void MergeSort(int A[], int low, int high){
    if(low<high){
  i8 P: O4 G$ x' O6 K6 d$ w        int mid = (low+high)/2;
: a% W0 D$ a: J% `2 U$ s        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
8 E( I! W4 D9 c  h3 \) V+ E9 |    }
}

" N7 m' w9 a. u7 M1
# t- S& y0 g( @' [& D2
3
/ ?' _, q8 i/ K/ R0 A7 n$ u" t. L! }9 P4
5
6
4 q) C! F+ Q  a4 |$ ?7
2 q( w8 F0 Y5 S$ ^- @' J! T, R9 h8
9
" i- H+ i- A) B$ r& H5 J) W+ E! l10
% h( {7 e! ^2 ]  z+ Q) L5 L8 q11
12
" c, f% a+ w7 y( j$ `7 M7 I13
0 }  ^0 Z( C3 }! ]14
+ o* h3 ]1 Q$ w/ b15
16
17
/ X5 a2 @. W0 d18
19
7 e1 ~0 T# s4 }, l20
21
, P: {! \6 M8 V2 c22
, U: W1 E) W/ t  l* y$ d23
( M. j$ i+ q3 ?. i$ H6 j" s24
25
3 g+ r3 L; `! U) c5 a: m26
27
28
29
30
时间、空间复杂度


& l4 t) [9 L: E7 [

5. 基数排序
直接看课本的过程图来理解P352

3 @1 N$ g8 E$ z2 J2 ]/ u  `再看这个例子：
$ n& l6 t, O- z
$ N3 E5 Y  z, ?& g9 B
算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
& S/ L7 N  z8 [% P. S分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
0 a% r1 p6 C, ^收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
/ E, c" j0 @7 ?, }" ?基数排序擅长处理的问题：
* X2 S. i9 e  D* V7 j①数据元素的关键字可以方便地拆分为d组，且d较小。
2 M9 E% b1 h8 |0 P' z! ?②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。
算法效率分析：
. i6 }# f9 M2 w: c- w$ Z' e% j时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
4 m9 }' k5 W+ w9 \, {稳定性：稳定。
  l" e( A( |/ r) E
& g6 Y/ r, f! U1 k: c
/ T2 O( y( ?; O. g+ q内部排序算法总结

5 ~3 X; E* w* z/ N' q9 M/ H————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
, s# M) Q8 c& k5 Q; b原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969

" T+ [' ]3 j! H2 s9 z$ o2 B