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

杨利霞

  K) z8 f( v, |6 m3 T' u/ D+ w【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
6 L6 t( x% L6 ~. _1 z! h0 t文章目录
排序
7 \2 g- B( `3 i# z/ C% g+ @1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
' I' A% E& \+ t1 q9 r5 o. S时间、空间复杂度
' c! w4 L* w) J3 d2 f  K- B（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
时间、空间复杂度
2. 交换排序
2.1 (稳定）冒泡排序
9 y; E  \: O9 g$ m# k8 k0 F) H+ E时间、空间复杂度
5 ]( @; B& I% ~4 Y2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
8 X* ?/ X! I0 u$ ]2 I  @* m0 Q7 D时间、空间复杂度
3.选择排序
4 ]9 Z1 b# U, W! M- x) \1 u3 w3.1 （不稳定）简单选择排序
时间、空间复杂度
3.2 （不稳定）堆排序
( o" d1 l( Z0 l! u" O① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
: e  N5 V2 Q5 n* H时间、空间复杂度
8 f: D" L8 b$ E2 H④ 补充：在堆中插⼊新元素
. H3 Y! t2 B; t4 ^& H% E1 U% z) ~⑤ 补充：在堆中删除元素
4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
( j4 J9 n9 f( b0 _  E( l/ f时间、空间复杂度
5. 基数排序
内部排序算法总结
& ~) A% I: i- B$ t$ o: e排序
- n/ |: _( v$ F" @) h. A排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

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

算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
2 g) ?; t1 t8 j稳定的排序算法不一定比不稳定的排序算法要好。
" _3 h+ B( R" ^; }0 R3 }3 o
$ W- D: \, A4 x) ]; n
排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
2 w# i$ n4 _- t8 b
! ~8 p8 Z' V/ Y: L5 P. A$ L

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

算法解释：（从小到大）


: i! {( l+ x9 c5 r算法三个步骤：
& X- H4 b- f. ]7 o4 _/ A
% v8 ]$ Y$ T/ L8 E先保留要插入的数字
往后移
插入元素

. y( H, G7 J, x8 R, J; t4 d4 I// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
$ d: n9 a# P* M6 y    int i,j,temp;
    for(i=1; i<n; i++)
( e1 W& o% U2 }6 Y! M    {
# v: r# ^8 ~5 d' Y+ z( }            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
0 a* g3 ^/ ]3 c: U6 C+ w        if(A<A[i-1])
        {           
3 s, g" q" \: Q% e9 f            temp=A;  //保留要插入的数字
6 H$ F9 B; z/ Z$ T' p* a
$ e4 z, B, ~& O% k& ?            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪
( Y) }5 K+ Q" B- S1 y5 T7 ?
            A[j+1]=temp;//插入元素
# o% w/ ]2 O, e        }
    }
}

1
2
3
6 m: {/ ]) i& p4
5
6
# N# M8 h3 [1 Q; O4 b, S7
2 l0 N+ ^) R& m/ K" q8
9
# v5 k& I6 I9 X* G5 v2 W10
11
( {) H  E( Z$ V) w12
13
( e# B4 L" B) ~- l) S5 |9 F! G; @14
15
/ \$ ~. j: g& C16
' ?2 X, M# u" q5 a7 e7 b17
用算法再带入这个例子，进行加深理解
* I6 H) R6 Q4 {; P
$ |5 `' q- |: t( M% n8 [
带哨兵：
- w/ K+ w# {3 ]5 s6 p" t: ^

补充：对链表L进行插入排序

( i# J2 D4 u% mvoid InsertSort(LinkList &L){
    LNode *p=L->next, *pre;
2 T& r4 b/ H: K* B    LNode *r=p->next;
    p->next=NULL;
6 ]7 ^7 H. `3 N# z$ l8 w+ x    p=r;
    while(p!=NULL){
: E* c9 |9 z' E. d' p1 }        r=p->next;
" q! w- c4 u- q, N. Z9 R$ j        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
$ p* z" x0 f7 N' U! c% `( h            pre=pre->next;
        p->next=pre->next;
        pre->next=p;
        p=r;
    }
! ?0 i$ b6 Y; |" a; s/ w  M/ W}
1
2
3
* O8 M9 ^  U) }+ e* s$ E4
) X7 c5 P8 _1 Y+ x/ L# A4 g5
6
3 S/ `9 r' o7 F- Q- J* M+ o7
! u) v( y" f. t- v8
! E! w- ^7 Z% d: c) y8 H2 L9
10
11
0 F9 w! [, r6 r' U' Z12
13
14
15
- A8 C/ I8 b- d时间、空间复杂度
/ ~8 T9 a) V3 e

最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
% Q" B$ w6 V0 S) ~9 x9 r; j最好时间复杂度—— O(n)

7 V+ j5 d1 E; I+ q6 P9 f& b最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
5 ^" G" M# t- M1 g3 ?- l第2趟：对⽐关键字3次，移动元素4次
7 _+ M$ B7 _: p1 }…
. Y$ d3 i$ ~, w; P+ }) c( j第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)
: ^1 g5 E: N1 X
0 ^" @6 U" D9 g( H4 B, C* O
7 z9 i0 X7 j; o


（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：
3 K) [/ S' A5 l4 A

" I5 J- L7 c2 y
//对A[]数组中共n个元素进行折半插入排序
1 @6 L/ \  m$ o8 R: N& yvoid InsertSort(int A[], int n)
{
    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
$ C3 d+ d/ W3 H2 d    {
; ?6 _( }  g* v8 a3 u# z        A[0]=A; //存到A[0]
) W( v2 o" X! W1 \        //-----------------折半查找【代码一样】---------------------------
2 g, m" X  M% i- Q6 C        low=1; high=i-1;
        while(low<=high){            
: g' d0 Q  W3 R            mid=(low+high)/2;
" a3 I7 l; }  w8 q, L            if(A[mid]>A[0])
                high=mid-1;
            else
                low=mid+1;
        }
         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
7 M; b/ L& Z/ a( n            A[j+1]=A[j];

/ E' e) j; ~8 b7 o        A[high+1]=A[0];//插入
    }
: R5 ^$ V& ?8 g0 @$ j}

1
3 J7 g# q+ e9 K; N6 {2
$ H1 b5 l7 H2 _4 o  p5 c3
, c& n4 u  Z1 F6 f5 T- x7 b4
5
6
7
8
9
8 G* p( W: b+ k. C10
11
12
13
' T" k2 u7 D+ G0 R1 A2 L" g14
: A! l9 o8 t1 u: }3 Y15
& d' \, x0 k5 D( Y( O% `2 m$ G16
17
18
19
20
& y( k" ^  V% w* c+ [' L0 ~21
22
, e8 o- z) \- G* r7 J# S0 r23
' C# z% p. n, Y9 I# X, n9 g时间、空间复杂度
# V! I4 `2 x. Y) b+ S空间复杂度：O(1)
9 N! T8 U5 X1 w1 L
1 v, A0 t" u1 H% k+ D5 ^【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)


（不稳定）1.3 希尔排序【多次直接插入排序】
; V- i2 ]; m6 u是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
  y8 i' t% A3 N% M" L& }- E
算法思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
0 x% u& K/ H- N/ G" Y9 t图解：


7 t/ c; G' u8 V# f* X, `* _
代码实现：

9 F2 \+ u8 ~8 I( z( V( I0 O+ c//从小到大
void shellSort(int* arr, int n)
{
6 G# o9 s! A  ^* |; n# m        int gap, i, j, temp;
  ^* |" y) Z5 M+ e        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
# v* J' }# g$ U  H, y: w            //**********************************直接插入排序（只是步长改变）**************************************************
. \8 }% i# c# d) x+ d3 J            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
                if (arr < arr[i - gap])
+ l. |1 n' w3 J& a4 N                {
; N- J% \; V. c  S" \  C9 S                    temp = arr;

                    //后移
* n: Y! n. J" z% }* l* Y                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];

                    arr[j + gap] = temp;//插入进去
7 o! k! p: c6 ~! e! a) x                }
            }
% ]" m4 B1 V, y' f7 x            //************************************************************************************
        }
6 e% r. s; o" J}

1
2
5 d( g0 d: p5 c9 P3
1 {$ d# K! n$ r0 W+ \5 v4
$ Z" k' P1 {# w8 o( i' u* L5
# k1 G* U* T' u6
0 [5 l6 L6 Q$ n' Y4 z7
8
6 Q& M) c" r8 o( l* z: E0 c9
10
& A0 }7 Y% C, I% V11
12
, J/ P) m" p  R: G1 ^13
14
& [8 X, @/ S. N) i15
) O/ E; x/ I3 @* @. H% V16
17
18
19
20
2 f! @: n- Z0 s; Q6 S0 u21
8 Q$ H( R, I& @: f0 Q22
% l# {! H, _' p# M/ M! Z23
7 g, T0 k1 b& S4 g  n2 x6 F/ Z24
时间、空间复杂度
空间复杂度：O(1)

时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
3 y5 P7 b) b$ `0 X. R
稳定性：不稳定！

% ~; j* I( f/ O5 r) c9 x* p7 s, t
+ K, q7 m, l1 Q" I0 R( @9 d+ z
适⽤性：仅适⽤于顺序表，不适⽤于链表


$ Y& v$ s% _9 V
2. 交换排序
2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
7 \5 \& U! `8 G5 p3 x2 g+ w
# T" Y+ A9 Q  y每一轮比较会让一个最大数字沉底或者一个最小数字上浮

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

$ o+ |# k. G1 }& W# r0 p9 `3 J  ^实现代码：
; p1 Q  d6 F, Q! I1 k  u4 Q
6 J. X0 {+ G+ d# ]4 N+ G% Q, I) n//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
5 z. s8 b$ d7 i7 [6 z3 _{
: m% B$ [; o3 ~; ]! {8 d, X, H" Y        int temp;
0 v8 U: y; _* Z( Y        for (int i = 0; i < len - 1; ++i)//循环比较次数
5 |$ Y0 R8 }7 Y% l; O+ b        {
# x/ W- G: F1 U# N; T& c7 [. `6 I                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
$ ~5 ]- k; l, O. u" I) M0 `                {
6 {* Q! }/ L9 D6 q% S% [! e. N                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
, s$ ]! j- ]* F/ q! i                        {
# U. m1 N( X0 C: i0 E& e+ ^4 I                                //交换两个元素位置
; L+ U6 J' a, h& P                                temp = arr[j];
; n  Q9 x$ z7 W  T& j3 \                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
# |& O! J4 S" |1 U0 }7 [                }
        }
- f( p9 L6 ~( V& _# G}
1 ]! n9 W) V. b$ e: [8 {7 m9 u& E
4 v$ u$ R( M# w1
2
3
4
; c# r# S: I! A% i: Q2 V3 @& U. Z5
6
( Z) t  s  y) R, S4 x; b- a1 H7
8
+ U" @0 y! I" P2 h! _9
( i1 |) c, w1 P. L1 S! z! t$ Q& o" S10
11
12
- W9 A3 {  b2 A5 C- X13
14
1 k7 n% k. |! n/ V9 I15
16
17
18
' o4 R0 L' H8 [, i7 a& d19
! C2 c' a* A5 N; M! N  Y8 V1 m. }4 C优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
! y' J% V# Y3 w- n  o% ]- y& ^7 }
//从小到大：
; \' n6 K- M5 f3 E+ jvoid bubble_sort(int arr[], int len)
{
        int temp;
( \9 G7 c5 ~% i8 _4 K5 ^3 [        bool flag;
, N! F1 K, {5 z- H' I        for (int i = 0; i < len - 1; ++i)
        {
            //表示本趟冒泡是否发生交换的标志
                flag=false;
               
                for (int j = 0; j < len - 1 - i; ++j)
' c) M6 _  _. ~1 j                {
                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
                                temp = arr[j];
9 _& T2 R- y* x                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                                //有发生交换
# x# |$ s* u- H# b/ G  i( M                                flag=true;
                        }
: M; V) b; j# `; ]7 k0 u                }//for
               
                //本趟遍历后没有发生交换，说明表已经有序
3 A% k0 X" j  [. i  e7 `' a4 M+ L9 @- m                if(flag==false)return;【1】
        }//for
+ k. N+ }, a7 X7 T5 H}

( b9 i9 \1 z2 [  m+ t8 a1
2
) w% ~- t$ L  Y" v# g( s3
% ]/ @6 \6 R+ r# q1 u8 y4
5
4 k# A' ]/ @, b0 O8 x/ S' r6
" r' |5 o) J8 c# z+ h7
3 o" A  ^, s) u6 M8 P, D: G8
9
10
) `$ C4 g/ }4 a1 [8 i9 k11
12
13
14
15
16
5 |0 r9 w  j: D- \17
# N* g$ R* G2 E18
# C) p' t! L9 t/ C9 V- Z+ `# o19
) {9 s! u& ?$ |, t$ l4 M20
21
22
23
, d8 ^% Z  l7 F) [/ s3 k24
25
& q- h9 C" E. l9 }6 I26
时间、空间复杂度

+ J6 P5 R/ ?) g/ {, {  |适用性：冒泡排序可以用于顺序表、链表

2 C, r: H0 q& ]- _6 ~
/ i, Z3 f: |: w" k2 h0 s+ k* T
" I, X, b+ W6 [" w$ ^
+ H0 b9 p8 T% y( \2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
  c5 y: L& ^9 P! j( i在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
+ Z0 u7 o  R. A6 s0 f/ Z使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
# h" c8 T) L# x1 ^% y
/ u$ B7 s- T, i然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
1 y/ S5 K% u" O
划分的过程：

" U" H! u/ h, _& A  u/ O8 Q初始状态：取首元素为pivot，定义low，high指针
1 @) c- B& e' `7 _# V2 [
( A8 H" s' ^" K' Z( d0 V0 B首元素为49
& `8 S1 [) d3 i" V7 O# |high指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置
' ^4 {  k6 w7 M! }! r

9 ?! k! ?* o+ Z

+ H( [. V/ L% Z' F5 V, w
// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
6 V6 E& y/ t3 `6 R+ [( _        //取首元素为pivot
    int pivot = A[low];
2 L* w  {8 A3 h3 J
; g6 v5 u8 c9 q    while(low<high)
7 }# y9 Y7 P0 i. G6 h. ?: h    {
8 M4 D, ]- N) M/ y5 z, z            //先是high开始向左移动
1 ^0 p6 I2 s3 @$ w1 f) F        while(low<high && A[high]>=pivot)
: F2 I+ [. E: m' Z" Q            --high;
: q, {  N& T# `# T        A[low] = A[high];

        //随后low向右移动
        while(low<high && A[low]<=pivot)
            ++low;
        A[high] = A[low];
& F; U& ^" v5 F1 I; U( a    }
& i  ~7 D- V+ d
    //low=high的位置，即pivot放在的位置
+ x) V; u, ^% q- N0 L* w$ c% g    A[low] = pivot;
% H9 C3 h% X- X7 R8 ~
    return low;
}

// 对A[]数组的low到high进行快速排序
void QuickSort(int A[], int low, int high){
    if(low<high){
        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
) \- @4 l! O/ a3 }2 V' P8 H2 ^- Q    }
; X3 {" w8 P4 _& R% S}

% s2 u3 Z) N& n& M& K1 I1
2
1 t2 F) B) U8 G& x- D/ W3
4
- ]2 n3 W7 G0 y! @$ z2 K% G5
6
  C3 f$ |6 B0 [6 X& _, y7
! L* p. O1 U" \2 e8
( u2 d! Q2 g* Y7 O9
10
11
5 Z# T  B; K( P  q4 D0 z. z5 Z12
13
1 m/ s( D" n. n& G" M14
# z) @' q& r+ {6 a15
, s: x- k2 m* F* h9 b1 z16
17
18
  Y# ~0 G$ v7 q9 l19
20
21
22
23
24
6 [3 l) {4 j# `6 ?5 o. j+ m/ w25
9 m" V- W) ]5 F' l0 y" z26
$ `+ r  W, y( D) j8 ?0 W2 r27
28
29
7 q; N- K. h/ E8 |- O30
31
) @% ~4 w" }; ]/ t+ {32
  L. c  l7 ?' p9 o- r* t( G时间、空间复杂度


" I0 U- }! X& n0 t& y, {把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
" f1 b" x, x+ p& {8 h
n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n
8 ~8 f& E3 \4 B: |4 s
时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)

/ |7 P& t# p6 Z) p最坏的情况


: a, y# n3 Z4 N9 R
' N3 G0 j3 R7 d9 |⽐较好的情况

7 h$ V7 G3 t* v" R+ T

! n/ _5 w2 O% H5 C! i, ]不稳定的原因：


5 ^6 M4 _1 D$ s9 ^


* r9 }5 u4 b: P; r9 O$ M! Y# X3.选择排序
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
' X: r  n8 ~  D+ E9 \
, n' C$ z2 p1 h# J& T3.1 （不稳定）简单选择排序
: X  Q/ M9 P6 o算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
+ q/ a1 w3 A- X" a, m* D$ I" |

* V1 J( b' {3 l- e4 w
! K6 F/ f9 Q8 }& m( z// 交换a和b的值
/ M# n  B' P$ F* J# T2 b: z' |6 |void swap(int &a, int &b){
) a: h2 U4 g( s: r, G  F    int temp = a;
: P  c7 [- o/ |1 \    a = b;
- k9 ?8 Z6 g& e7 @) }& X( b9 O* ], t    b = temp;
}
* m/ I- e) z8 H: }. N0 ?
: q3 O) {7 `5 \7 [1 [) u// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
% ]; t- T% r4 c; N! ]{
+ |# ]1 t4 v! A  z+ h4 ?4 E0 r        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
7 U8 Q0 ]0 b$ n    {                 
        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
' k- w( {6 {) w1 S* D            if(A[j]<A[min])
, k; q4 K6 e8 |6 K# K                min = j;
        }
( H2 }+ E% e" o. E; e7 D2 G7 o8 T' |        if(min!=i)                     
            swap(A, A[min]);
    }
% a2 D7 R* c; V; D" [; z8 h}

2 t1 {' R8 L/ h/ p, \5 M! T) v1
2
3
1 X& g* w8 N/ U7 H" B4
$ S: [' {! O1 ?- O2 V, M5
6
7
8
9
10
11
12
: c9 ]+ L9 q* s2 C; A13
14
* D0 ?% ?: R% V* j15
% d: ^9 _" l0 V! U16
6 V# T& T. l: p' i4 F7 l0 M& P' T# _17
: Y5 q. c; }/ N  w* l' Z1 o! w18
& i/ n! l2 _8 u! z$ J19
20
21
22
补充：对链表进行简单选择排序

) M$ \3 G" c# I0 v+ Gvoid selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
    while(h!=NULL){
        p=s=h; q=r=NULL;
3 X- y: K! i5 d/ N- S        while(p!=NULL){
+ [+ _1 w) k; W' @* {; J1 Q4 p; t1 M: h            if(p->data>s->data){
9 u) z$ S0 Z* W5 H' b  l, B; F                s=p; r=q;
            }
( O9 a7 F" F. `" v$ S            q=p; p=p->next;
4 t# C1 v, E4 j2 y. P  O        }
        if(s==h)
- p6 g6 i9 v; ?7 {( X; Y2 s9 Z            h=h->next;
        else
            r->next=s->next;
3 [* M+ M8 W7 n1 p        s->next=L; L=s;
1 u1 r/ T; p/ |; W    }
6 ]' r) \( F6 \2 a# Y1 D}
2 M& q9 {6 L4 t
1
$ x7 r0 I7 O0 P& e2
3
( U. U2 u$ S$ u# S9 l) m  A* [0 k4
9 \+ N8 r1 Y3 n2 t* ]3 n% g5
6
7
! ~: M8 U, r" Q; w8
9
10
5 S' |* R1 F# f" O2 g3 q3 ^9 p/ [$ O/ @11
$ H2 Y5 L+ z0 W12
13
14
15
( g- }/ f* _- L2 q3 p% k& K' v, @16
17
18
0 ]8 W7 r6 t% F8 I4 y1 n" [9 _. s时间、空间复杂度
) M$ W* t; b3 [  W5 S1 n
% P1 \' Q' N' ~  P; u
# ~8 v. ^; F$ g0 d1 ?( _

: F2 H9 ?5 n% Q% G5 H适用性：适用于顺序存储和链式存储的线性表。
% G: d' T8 Z6 j  i/ k


9 l* e2 ]( w5 {- u0 D! _3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
* N- O+ V9 g% l& t$ o& j每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
4 I5 O, b/ o( r/ [, |
* K- n1 x& b& h# O! P" E  t

/ r, g: }( ]# T$ T8 y/ l即：
9 `" |) w' I4 o6 u: s% R若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
7 J9 }$ P1 v% q+ r& A' p; P* u6 J若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）

. E5 U- G% r: ~! r: `% A) ]② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
思路：
+ g/ c& D# {, m8 ?3 Z; s把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

, e  j: n) t$ ]% }$ ]$ y& }在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
* _: l5 p1 i! @2 y5 W/ U
检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换
& Y7 f; a+ T- A/ P) h1 n
0 }/ Y# q) V/ f! R7 ]1 W, U" C7 c# ]过程例子：
7 i. I& L0 `  q! j& c2 b


建⽴⼤根堆（代码）：


: b- x9 X. \- f" r8 I( `9 k8 }+ ?
// 对初始序列建立大根堆
/ q- s2 V# t3 O+ a) ^+ _void BuildMaxHeap(int A[], int len){
6 j( @# E& h* M3 Y  J    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
1 @- k% ]* J. m' O. ?        HeadAdjust(A, i, len);
}

$ Z5 n; R. E% |5 U9 k2 X. i// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
, N2 F# n) G. {# f& |/ c    A[0] = A[k];
    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
            i++;
- n" i' F- J8 T/ A4 V: a3 g6 P1 X        if(A[0] >= A)
$ k+ w1 D  y  I! `3 e  V            break;
        else{
5 c1 C4 p4 _% z; A' x/ S            A[k] = A;                        //将A调整至双亲结点上
4 ], P# }6 t. s  v  C            k=i;                                        //修改k值，以便继续向下筛选
* X' d$ P) l: H' s# m5 _        }
    }
    A[k] = A[0]
}
8 a& g. t- T, b4 d  o4 A
1
7 H& f$ `8 `/ S* F# h9 b( }) G6 o: a2
( v6 A" j3 W* y  H# o8 ?3
7 I' L' y1 _: }9 b4
3 G& v' T% [- v" ?1 e+ K. ]5
6
9 W3 t/ z4 \( X5 b0 q& [2 |7
: f/ e1 r# w/ W- c, q8
9
10
2 W# [! f* M1 Y8 k! s$ p3 I11
12
13
14
1 R) I4 B3 ^' w8 F15
16
( _; l4 m3 m, L17
18
19
20
! \: ?- M) \; m, i21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
, t3 q! A; C7 s选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

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

' w& H/ ?) Y) O  f# t# |, G# ?过程：
, g* F/ E6 s' N
// 交换a和b的值
5 t# f) P/ r6 B- n/ _" Cvoid swap(int &a, int &b){
    int temp = a;
    a = b;
" f* a* ~/ G3 q& d    b = temp;
4 K( ^% ?6 O  h. n$ F}

// 对长为len的数组A[]进行堆排序
: A% w: H4 S( Y0 d" N3 ivoid HeapSort(int A[], int len){
0 }) u0 d3 ^5 B0 n# ?        //初始建立大根堆
) S) b$ T& `) R9 D$ D    BuildMaxHeap(A, len);                
6 ?' ~% g- o. a
    //n-1趟的交换和建堆过程
( B5 j' u$ Z- @& L5 F    for(int i=len; i>1; i--)
    {             
        swap(A, A[1]);
        HeadAdjust(A,1,i-1);
# q; f9 x  w& e: N8 ^    }
}
6 h5 K; b! V- ?# U  {/ K
4 e1 o- `% n$ B, X* S9 C3 Z1
2
* v& c3 @; b/ a1 v3
4
4 J/ R+ n3 U6 |! {" P- Q2 i) i5
% H% \8 l4 T8 M6 ?6
7
8
) A$ `$ i1 ~6 I9
) b3 P3 Q6 \/ O4 f10
11
12
13
14
15
; I% c. l- O. ]' M0 o16
; `8 o  A) T3 a0 Y17
8 j9 n/ s( w' }6 k9 P18
: Z0 u& ~6 ]" h) u3 S19
时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
, m, Q2 k" ~) |- z$ _故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

6 I9 s; c/ o+ b6 y! @# H- \空间复杂度 = O(1)
' U! _1 b( o( M# S: v- a4 ]
结论：堆排序是不稳定的

4 f4 k' x, G! L( w+ Q$ q" t9 l
④ 补充：在堆中插⼊新元素
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌

3 T2 W6 a% @4 x/ O2 Y' m

⑤ 补充：在堆中删除元素
2 x0 J& q- t  v) P被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌


0 |; `' D6 M; ]
/ z5 c4 a+ x, ?7 ?2 v$ J/ o' s0 c$ W

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

7 ~0 X/ H8 M5 {% R( A2 R① 明白什么是“2路”归并？——就是“⼆合⼀”
- x$ V' I- u& Z$ j+ i4 I+ N
" ?7 M% `# c1 [8 l7 X- U4 Y% ^多路归并：
+ D9 x7 K# j  K  u

0 R1 ]! I  g: I" z② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
$ k6 m7 b9 Y# s
( C* W4 M: D6 ]! ], C, G! ~B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

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


  u' ~6 d* M( q0 w: N& h④ 总实现代码
// 辅助数组B
8 Q$ [; @* @0 Cint *B=(int *)malloc(n*sizeof(int));
' }: h# y; M* C  o+ M4 Q: j
  G( ?8 d3 D% i// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
; s7 a7 O0 m4 ^6 m4 q+ A) Vvoid Merge(int A[], int low, int mid, int high){
    int i,j,k;
    for(k=low; k<=high; k++)
        B[k]=A[k];
1 d- v4 G7 q, E* y# r' ^    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B<=B[j])
" i- x2 B: c& s7 P' c! ~+ U            A[k]=B[i++];
+ b& G( e  V* n2 ~' S) T0 X        else
            A[k]=B[j++];
( |, J  M& W3 _: P3 M    }
# m0 n3 \) l  h) e& v% K    while(i<=mid)
  G' r7 A4 n  z& t" \4 D$ R        A[k++]=B[i++];
7 h5 z! \( X$ C    while(j<=high)
1 K& U) N$ |4 Z% X0 z        A[k++]=B[j++];
}
3 ^, e2 u* [3 X) `# ?0 Y% n% s, x/ n. h
/ r, o; C$ }! L- O( r7 L
// 递归操作（使用了分治法思想）
+ h5 ^0 k3 D6 ?- i( `$ {void MergeSort(int A[], int low, int high){
    if(low<high){
8 |! o* Q  [( O1 O  K* L8 r        int mid = (low+high)/2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
' F* ?; Z  x* s# ~# Q7 i        Merge(A,low,mid,high);     //归并
    }
}

1
2
. h% k: P( i: n3
. r# ?6 Z$ J6 ^1 n5 C4 q' }4
' \% k4 h7 M$ y' {) E5
$ X4 s. C  Z3 |6 F6
7
$ q* T$ Q: o' q. }$ z8
2 X  j% Z2 G2 F; d5 _9
10
/ b* o: G9 ]" G5 y  \& Q11
12
3 B& w! V: `( G! @# T. u, n8 F8 h13
, F7 \- z2 p) X. K" U14
15
16
17
18
0 d5 K) G2 ?4 e19
, E; z& Q. O6 f; t# ]. O% P% B5 N/ h20
21
22
- J( C/ V3 H, y' r) T: {4 [23
' R' R; Z  ~1 ]: V: O" u24
! l0 k9 ?2 l+ ?4 t25
0 w* i; v4 c3 K: }# I8 g5 H26
  b$ o: a8 w6 _) o+ n. ^' i; B  @6 p27
6 u2 @+ @5 n! h( k& ?7 e: }7 f28
29
30
0 N+ ^# e/ ^  [) a+ u, G5 Y" l时间、空间复杂度

  ]" `7 o8 s; B% d/ E5 Q0 t


5. 基数排序
直接看课本的过程图来理解P352
& x  O3 _% E! V' E4 `5 Y" |
( l- N5 g7 [( I8 T; o' |8 `9 A+ J再看这个例子：


, }, b3 o4 u! }- Q% `' f算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
4 r! H! c8 i- g分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
  D% T3 M4 C/ u$ N+ A收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
! o" T( Z+ u5 a$ p基数排序擅长处理的问题：
+ g$ z* I3 X1 L①数据元素的关键字可以方便地拆分为d组，且d较小。
" ^5 S: |1 s& k$ q②每组关键字的取值范围不大，即r较小。
# @. S- u0 I: O) h③ 数据元素个数n较大。
5 w5 }% d! l$ p5 P: G/ K算法效率分析：
7 |- q5 c/ x  i" U8 J9 t时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
2 \! s/ p4 d" a稳定性：稳定。


内部排序算法总结
3 I0 {- |( X; D" H) b7 v1 C. A: O
————————————————
5 |# o- @% Z( t) O6 K版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
/ W4 E( O9 t6 o( J$ B原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969
" T  f0 J! _1 U. v7 u
" f, R/ I; t- V# k! O