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

杨利霞

2 E' c+ X; O5 h【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
排序
) W- D% @, v; C' i6 Y1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
时间、空间复杂度
6 T4 @& D% j7 c! C- n* u（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
" F9 ~/ e- M$ P) I7 t7 M# b（不稳定）1.3 希尔排序【多次直接插入排序】
: `4 f" `+ I7 g) \- [) Q时间、空间复杂度
+ m! I+ @" `4 W6 V2. 交换排序
2.1 (稳定）冒泡排序
" E0 ^; P0 N) s, h% O1 S时间、空间复杂度
% n# Q* f( |1 c6 J( ^2 f4 g2 {% W2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
3.2 （不稳定）堆排序
& B" v- w, e( ?) U( |; R. I9 h① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
0 S2 k" R" O/ j: r② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
8 x1 ^  m' @; W③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
& U: x! X, q5 l, y时间、空间复杂度
④ 补充：在堆中插⼊新元素
% R& z% n; Q; ]+ s  g, h8 `3 G⑤ 补充：在堆中删除元素
" f6 a- j8 @8 T! T" b0 f$ ]4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
" N: U- e  Q& n5 G7 b④ 总实现代码
时间、空间复杂度
5. 基数排序
内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
. l" z* z8 B' A  g
排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
% w8 F7 X/ N- H5 N+ x+ d' u  x
算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
& V2 m: z  j3 Q- I$ P稳定的排序算法不一定比不稳定的排序算法要好。


. K; G5 }; k$ O/ _5 Q" e* l& Y4 ~4 S排序算法的分类：
2 y* H+ E+ m0 c" P; K$ A5 R+ e内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
8 m; b* ^) V8 y5 X5 B% ^外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

6 j/ D7 I! E8 x6 Q* D各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html


9 H! H! Z$ J, y3 n% \2 J
1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
; ]/ d6 s4 ?: c
算法解释：（从小到大）
$ t# l2 z! T4 O

, F. ^/ c( Q6 a+ j) l; s) Y. M7 X算法三个步骤：
! W5 t3 Z) L7 o, x0 R; B6 c" z. T8 Q
3 [3 g2 D3 s, n! c/ \先保留要插入的数字
往后移
插入元素
+ T) b, ]- S2 g: Y, \0 _4 x( K
// 对A[]数组中共n个元素进行插入排序
. b9 Z1 r! r# q5 svoid InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1; i<n; i++)
    {
* ^! f; h0 E' {+ f8 h2 l2 ]  Z" B            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
        if(A<A[i-1])
2 F$ g$ A$ C5 m' W( ^5 s7 W/ r        {           
% J; o! V( b' R0 H            temp=A;  //保留要插入的数字
/ G" k- l  M3 [6 h& M4 v% a
. t. M$ E. M% Y5 l; }            for(j=i-1; j>=0 && A[j]>temp; --j)
) f+ m; b3 y" `7 a                A[j+1]=A[j];    //所有大于temp的元素都向后挪

; U7 p, @/ \. i7 X$ s5 z8 T: A' z            A[j+1]=temp;//插入元素
8 X5 E/ i  R" g+ ~: q* N" v        }
' n0 `/ j5 I' V3 W% \7 T    }
}

7 I9 }4 _5 V+ s! ^4 t1
6 `, c5 r3 a! a9 r) z: _$ ^2
2 E  a+ @# J+ x; u' |3
2 K: Z/ ^; @# q/ o8 h4
5
6
7
  i6 t! {# Y" q) t8
9
10
5 Y1 S, T7 v/ u1 m11
  k. E: Q2 ]* ~4 G12
13
14
1 S6 W% P2 o8 [15
" T  A  d' W! h1 T6 O1 Z6 q& v" j16
17
用算法再带入这个例子，进行加深理解
3 p( ?3 W1 U! t# n: L8 I
: Y1 a2 T; P7 r8 y
带哨兵：

2 Y& j" e0 a! l5 U- N- q
补充：对链表L进行插入排序

. A+ ]. b/ u5 f7 {3 g, D- q# yvoid InsertSort(LinkList &L){
2 K4 {. ?) R* \! U    LNode *p=L->next, *pre;
    LNode *r=p->next;
$ m( Z) q+ _, h! L6 [# N: Q    p->next=NULL;
* |/ G( |8 W' ]5 i    p=r;
    while(p!=NULL){
        r=p->next;
# I) J1 e3 Y) I+ \% F5 a: f        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
        p->next=pre->next;
        pre->next=p;
9 v, t4 Q6 W8 s7 M        p=r;
    }
}
1
$ P! G4 l9 t2 ]2
3
4
5
6
7
" {$ c0 [! h) {8 m/ s8
3 y4 @2 N( |0 G- @- u9
1 Z, _+ r# m# t# P$ T8 M. K10
( t; o1 \* x4 T9 B" V+ t11
12
13
- ^, i# g+ z0 ?- x14
2 a6 H/ K/ m% d15
时间、空间复杂度

' p# X5 `( p. r
最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
* g* l! _2 m% B# }' \" j最好时间复杂度—— O(n)
/ J1 `& H8 l' j% \  Y: Y( [
0 q' x; k. b2 L% N5 u# x最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
+ M: N* a& P5 T0 I1 c! }. q1 z% O第1趟：对⽐关键字2次，移动元素3次
& B  J% g0 D7 M1 s第2趟：对⽐关键字3次，移动元素4次
9 K# `7 `5 G+ f1 y) S2 B$ M…
1 }6 d- y" W; C& P  s3 {第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
$ B! O6 H# f) K+ k最坏时间复杂度——O(n2)

4 C: h9 Z* p+ N+ Y' ~- |& Q


; c# A7 Y% u6 y$ }4 X% P9 T: Z
5 l& ]9 j* S, i* a* Y（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
! Y. q: Z# J  @3 a) w/ [* T! I1 }  K过程：



//对A[]数组中共n个元素进行折半插入排序
: `0 h& c% c2 v2 S7 ]+ Tvoid InsertSort(int A[], int n)
{
    int i,j,low,high,mid;
4 r4 P9 d: p; u% v    for(i=2; i<=n; i++)
5 ]/ n4 ?& j0 R: T    {
# b; k2 u8 y/ M9 m. r. O4 ~        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
+ |* {. q6 p: E2 m" L        low=1; high=i-1;
        while(low<=high){            
+ J# y7 U6 @! b, x            mid=(low+high)/2;
, ~! `" }  g3 A/ ?; s2 K            if(A[mid]>A[0])
                high=mid-1;
            else
                low=mid+1;
" j& i0 g' |) Z, _/ D7 ~; g        }
         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];

        A[high+1]=A[0];//插入
    }
: p% D0 T- ]/ z$ S* O8 ]6 l}

! R2 y  P& A  f% I1
2
3
4
5
' R' o3 y' y+ |% o! |6
2 l# A/ w$ y/ z+ W( G8 ~7 v7
) n- {; n+ T& Y8
9
10
11
12
13
/ y1 H$ \+ x3 C0 G  j! r% ^- v14
7 \4 H6 z6 d  S- C. l$ [+ S15
16
17
18
0 q. q, ~3 K$ A' W19
20
' s4 _* t9 y7 m# D21
1 F+ N$ K4 I+ P22
23
8 |9 O6 r- ]7 |. P1 q时间、空间复杂度
空间复杂度：O(1)
1 A8 J- M! }8 Z, l
【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)

+ |, V+ ]6 Z/ Y2 F
6 d! s/ U6 g$ L1 f" G5 I+ A（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
; Q- {  B( p" _# ]% C, b
- v# U; Y, H  F$ U算法思想

+ a/ e) O% h2 S. T希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
" g# j, f4 W3 u6 V随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：


! C) K' z8 s( p& h) v
" s& i4 v* a! W& H2 B  A& W7 b7 C# i! e代码实现：

. q$ k0 T8 x- B, n( s' \. j) Y//从小到大
void shellSort(int* arr, int n)
{
        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
1 R# u/ S; N, t: T0 {8 }- E        {
. v0 {, i- y( }) r* ?) w8 t            //**********************************直接插入排序（只是步长改变）**************************************************
; f  n0 Q$ D0 {) u; S            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
  k! i+ |$ W( J            {
7 |7 G5 X$ g9 N; f                if (arr < arr[i - gap])
" D" b9 G$ n+ M- o                {
$ U1 s# J3 t) V; I                    temp = arr;

$ D! e1 `- ~! U6 p! m) N                    //后移
' Z  K! r3 W) M                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
8 M& L. G% C# j7 _1 L                        arr[j + gap] = arr[j];

! C; ~0 q0 ]9 ]4 i4 \! A) {                    arr[j + gap] = temp;//插入进去
                }
            }
/ B% Q1 x/ M% B+ N4 W3 T$ \. H            //************************************************************************************
        }
}
' _+ }5 I! L$ X/ e1 W
1
2
! a/ }/ s. @* p$ C6 a3
' @: R; e. m/ }5 q& X" H' N4
* j# _7 }2 N% b  L; b9 t5
6
3 s$ t# c- ]  Q  C% J7
8
) X; H( ^  D; H9
" W$ X$ F7 M. }: X3 s! `; Z10
- Y+ F, ?' f. M; n' K) n- v11
- R8 S. Q1 ]2 Q* [( Z12
. Z$ n) e7 }9 N9 s, Z13
) F; Q% T) s' ]+ Y+ F8 @; n. y14
15
$ e3 i( @: u) ]16
! j# Z$ b8 J+ v" q, S5 }17
9 m- c! R, H/ @' y3 }0 N/ l7 ]. o18
2 J/ o0 o  G) W2 r. ^19
20
21
0 b& H, ], u3 y22
23
+ \; g. G) J" C5 z8 }' e24
, {0 b7 X( O5 e7 m1 }7 W时间、空间复杂度
4 \% A; [, E' _$ n6 e空间复杂度：O(1)

时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)

* H: S7 f  ?, j$ S# r' v2 j稳定性：不稳定！
  L/ ~+ `6 x5 t

! [0 v4 @* ~. R
适⽤性：仅适⽤于顺序表，不适⽤于链表


3 ^; L+ @8 U. V' L! R
2. 交换排序
2.1 (稳定）冒泡排序
' O- V; H9 {( E/ w+ [1 R( A英文:bubble sort     (bubble 动和名词 起泡，冒泡)
' s+ s6 @* L# K+ B. C从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
- s& \) R6 }6 i  R8 \% W+ U5 Z
每一轮比较会让一个最大数字沉底或者一个最小数字上浮
" `% h& Z! z: ~, W" U* \
7 b3 `% q) A3 j  t1 i/ L: K这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

实现代码：

; D( p* b! c) \/ \0 b//从小到大：
1 a" J0 }7 v  ?/ I2 _void bubble_sort(int arr[], int len)//冒泡排序int*arr
{
) J& F5 H1 A: Z$ M& \3 W# m6 q! F* X        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
        {
                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
2 ]) Y. v2 d* h/ J7 b7 A9 e1 m" S! L4 V                {
                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
                        {
                                //交换两个元素位置
; U9 H( C1 a( W& `% w                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
                }
        }
}

' j. a: z5 r' w, g, v: }1
' s# I! U' @% P; h, ~& e2
6 j6 J+ q8 `- G" v3
4
6 K2 R, x% r3 o% V4 J! S) H- c4 C5
6
7
8
9
10
' L# \1 S; l$ x1 `7 k11
" j: Z6 ]) j3 Q& y! U8 Z* I1 E12
0 u7 W1 W) z& m. `+ q, w8 Q13
14
15
+ q, H: T! C9 }) B$ r: n16
17
18
19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
6 |" Z+ W8 L, c0 w9 i3 j  P$ G
//从小到大：
0 A1 m/ q' `  n# Zvoid bubble_sort(int arr[], int len)
{
" b1 p- N6 A" ^# r% R. \3 e; t        int temp;
5 \( t. U( T  W( D/ c        bool flag;
        for (int i = 0; i < len - 1; ++i)
1 T( ^% n  V8 V& M  f5 [+ M8 I        {
            //表示本趟冒泡是否发生交换的标志
# J7 ~1 C* J2 D4 x, C+ Z                flag=false;
               
                for (int j = 0; j < len - 1 - i; ++j)
  \  n3 y! g+ n5 ?* Q: W                {
                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
% ?3 H' [* c6 v5 A                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                                //有发生交换
                                flag=true;
                        }
6 q2 |% j" t7 \$ U  R! n7 d                }//for
               
                //本趟遍历后没有发生交换，说明表已经有序
                if(flag==false)return;【1】
        }//for
}

1
2
. N  ^% g  ?( i" g" c, c# u% ?" i* x3
" ?, f' C' E& Z- C! w& W) L4
5
6
. y- I. l) g" K- j6 p7
8
7 u4 g% y7 k$ S9
10
' A% [. o) s' q8 C11
  J6 u% H, H* I7 l9 T- k12
3 }" l2 F, E1 I. P13
1 y" U' o2 v6 D, K14
% h7 _+ o" u  u' ~15
  b1 Q" C( @; N16
5 B4 B9 n6 Y( A9 B% M2 z2 B) g0 b17
18
- F$ T6 V' Z3 w! m. M& D6 ]19
+ T% c5 ~2 o% i20
1 O! E: D" p7 T21
22
23
24
25
% V. {2 Y0 T; \4 D3 G4 e) C26
时间、空间复杂度
% ?4 F6 T! e" J
% ^2 u" x6 t5 w) Y2 o适用性：冒泡排序可以用于顺序表、链表


3 f/ h6 u2 K7 s' g- d8 {

( F7 o' O! u# W% c  ?/ v1 ~9 j" E2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
1 R& `% e( }" i8 W( _算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
$ P+ v9 e6 R2 }8 C再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

1 Y0 I& n; M; `4 Z. n$ A9 u然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
$ U1 ^9 [* W& ~
5 S/ |* A6 J( J划分的过程：

% }, Q6 l" b  G7 U+ U4 v; B初始状态：取首元素为pivot，定义low，high指针

首元素为49
8 _, M2 y. e% R) L9 Ghigh指针指向的数据小于49，就放在low指向的位置
, b) g+ ~2 w; W5 o! T0 qlow指针指向的数据大于49，就放在high指向的位置
) B6 B9 g% x# h9 k
* S& \1 W* W# Z

' x1 F( R9 S' N7 r6 C, u) ]

// 用第一个元素将数组A[]划分为两个部分
3 F# q' ?: L3 Q! u6 Mint Partition(int A[], int low, int high){
# e. l9 K, {4 @: ]3 p& ~5 h1 I' C        //取首元素为pivot
    int pivot = A[low];

: j/ Z. t2 P* V; S+ _  ^, W    while(low<high)
' H) q9 R/ Z( d% C: _    {
5 ]6 ~( U. _# u( r$ E  C            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
            --high;
0 b) W$ I# |. }1 [        A[low] = A[high];
+ Y, j! \/ ?2 c) @# n% }/ Y
2 [; t5 K9 S+ S5 T. g        //随后low向右移动
        while(low<high && A[low]<=pivot)
, t  t! J( M, `. J" A- H& @            ++low;
; m/ p& z  `2 R3 p9 G: D+ N        A[high] = A[low];
% c& v3 [& v/ T; Q! {    }
0 d. i) f4 C# d8 o3 D4 v2 H& x7 D
3 I+ _# Z# ?  A/ ^. z    //low=high的位置，即pivot放在的位置
    A[low] = pivot;

    return low;
}
) Q: u9 g3 Z, Y- T+ K" P6 u
2 p% y5 T" R* m1 L. i; p// 对A[]数组的low到high进行快速排序
9 W/ m8 f6 z4 t/ l, h7 q: Gvoid QuickSort(int A[], int low, int high){
% U- i4 a4 f7 W5 x4 m3 L% c    if(low<high){
        int pivotpos = Partition(A, low, high);  //划分
3 n' O4 A: H( ?        QuickSort(A, low, pivotpos - 1);
3 m  @4 R! m1 E$ y% M) @        QuickSort(A, pivotpos + 1, high);
    }
7 ^9 P: z- t+ J% H}
+ }: U$ ^4 [. H+ `: \
1
2
- R- f& f8 b" M4 q. o/ I3
4
* I$ r$ ^+ I- |% v9 n, x$ \1 T5
% l* {* i% b2 N" J% ]9 G$ ~6
7
! f" q) {/ t. ~$ t4 G' |) k0 M" c8
9
10
& x- E5 W' i+ Z8 _11
2 r/ e! }; K/ U  {* l. r12
13
* l. [. R2 B# v" a14
- K0 P/ [5 L+ P# E' r15
16
17
18
19
20
- s7 u1 {( i% {. C21
( q+ ]( l9 \8 Q$ T$ b5 G22
23
& C- r% x; x" i24
25
1 J( `) J/ S) c. \3 Y26
4 X: |& n8 {$ U8 T8 ]  L% O27
& v, e% y3 g1 N8 K28
) f/ ]6 n, W$ k& H29
30
31
32
6 e; H1 R. E8 ~2 r0 F& w时间、空间复杂度


把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

! R6 s* G/ B5 n) ~; q* z' m时间复杂度=O(n*递归层数)
% ?. }* C2 u4 `& r) V! q- b" B# `8 R最好时间复杂度=O(n * log2n)
& n8 |( H' [7 m4 _* b最坏时间复杂度=O(n2)
- I& D2 Z* P" U; `; ~6 o# f! a! C平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

6 g9 f9 C6 Y. V9 H空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)
7 t; L8 `( R1 @- e# g. w+ H
. H4 U" M* E2 g2 k' F9 ~" A最坏的情况
' G% s. ?$ v+ i! ^7 m6 b

$ V3 m& H. F5 ^
$ o# m& g5 J  S⽐较好的情况
, O8 I1 B! r8 Z: |5 Y
4 Q2 c, e7 Q! A; b$ Y6 }# M  e2 w
2 R- {7 I. m& u9 A8 ~3 W
不稳定的原因：
$ _6 J1 x% `/ {! L2 H/ v
5 S& O- b. y2 W* q



6 ]* B5 b- f6 A5 a6 }3.选择排序
  K+ N7 T& i7 l% F1 w/ n选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
9 s0 m/ }# F) h" T, K4 J. h
3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
: \2 i7 e1 U, F# Z% \4 ]7 Z. Q) d
" J! K; H4 z; G

// 交换a和b的值
void swap(int &a, int &b){
5 N# x* u0 |& M" V+ N' K, o3 X    int temp = a;
4 p0 {  h/ V. J! O+ @9 t  ^    a = b;
    b = temp;
}

// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
{
        //一共进行n-1趟，i指向待排序序列中第一个元素
; A7 s0 t% o4 H  g7 x5 g  z% L7 a    for(int i=0; i<n-1; i++)
: b0 y. t+ m1 N( _* v& R    {                 
7 W  x( F" \: T4 ^5 |/ z7 ]' n/ Q        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
0 S5 e+ d; G& z            if(A[j]<A[min])
                min = j;
0 H4 X/ b- X. ~# o3 I7 X3 r        }
        if(min!=i)                     
/ i; b7 _: y8 ^1 i' M" {" E            swap(A, A[min]);
    }
% ?  g/ S$ B' N/ Y5 j7 F% A}
: ]% K, _; p4 h% \
1
2
3
4
* `; M2 _1 l. p) _  h: c5
& b& e/ V7 S+ [. `* E5 n6
: C- q/ B( [: q: r8 b7
1 O7 R- ], I* ^9 `3 N4 c6 |8
9
( l/ F  y* e; ?& S: m4 Y10
/ _& g4 @5 Y8 {9 _  d6 B11
12
$ C' X+ j, z' n! |/ e& H13
8 w9 f7 v9 ]; v4 d3 w6 ^14
7 V& W8 x2 |8 ~0 n# ], l+ `15
16
17
18
19
20
) y, C3 r# L' b2 U0 D% I4 K21
22
# X5 T8 j& h- z9 N+ n补充：对链表进行简单选择排序

void selectSort(LinkList &L){
) M! Q9 Q5 a' C    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
( |. ~! Y( Y! W/ F3 ^/ t4 p    while(h!=NULL){
        p=s=h; q=r=NULL;
        while(p!=NULL){
  w4 z# t4 Q  B6 d            if(p->data>s->data){
. F0 u& b7 ?  b9 f$ ?                s=p; r=q;
; b" g. L7 y+ ]/ }            }
7 t0 K2 y& D' g1 |            q=p; p=p->next;
- b/ g1 T5 M# p% ^        }
3 T6 V9 h. J, ^& k* p- x- t: i  S9 t        if(s==h)
            h=h->next;
        else
' ?1 |7 M6 k8 H" D) q* L            r->next=s->next;
7 B! R" [- J( g; X        s->next=L; L=s;
    }
: z' t; O& s* c- w}

' k7 v, t: F8 }; {# o+ ?! F1
0 g4 E9 Z$ Q5 i% T8 a2
3
8 `0 P4 i! n5 Z) ?4
" |, W1 g' \$ d0 x1 v5
6
' r* X2 J3 i: k  |* ^$ i' S+ J7
8
1 A" k2 \$ R+ l3 C& l; l9
9 e- A( d6 ]5 t/ P6 P" g10
11
1 r* w9 ~0 A8 U& f12
13
14
15
& i; `6 \& k3 {; p# q7 a* s4 U16
17
18
7 A: J  X% c3 }时间、空间复杂度
' }# g5 r" A8 @

$ t' ]) i: L& _3 Y  g
' T! m& R( d$ e
适用性：适用于顺序存储和链式存储的线性表。
2 D3 ?  y8 L( t
, o4 [4 o- q  u2 s: i$ o" g

8 i; U% \& w) ~5 Y$ t3.2 （不稳定）堆排序
: v# A8 X- T. o+ `. P3 k① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
/ Y5 ?5 z. c% q6 r% l堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
( ^7 y/ p$ j: Q* L+ ?' y2 X

# n6 t* x7 U) W. U1 o  I# T
6 l5 [' X' Q2 ^9 \即：
. k9 g* M) o4 i若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
% s" Z0 B( T4 @  l1 U' X若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）
+ s9 {/ ]) U& d' _7 Y2 W
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
; a  R. p! E! ]; u- W思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
# D( u# e6 s  |" z. m
在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
( }6 k/ e- w% y' }' ]# p
检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换
! e. H: c  h2 y
% O  ?. \2 u) W# _9 W过程例子：
- B, x4 M1 G  s9 [4 u% f2 i
1 w% Y: Y6 P5 t& s# }

4 A5 T# j) T7 t" P) c, D& a建⽴⼤根堆（代码）：
  [5 }$ z1 ^, f: J2 P
' ?6 y/ A% y/ w9 A' j0 @7 Q- A
& ?. ~, r9 O! ?" U
% w% Q7 B  v% l% q+ B: m0 k// 对初始序列建立大根堆
6 c8 i. @" w" P8 V# W! X" h8 Ivoid BuildMaxHeap(int A[], int len){
2 V/ W/ \0 s+ G7 o" a    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
' d# L5 R( j! g" L        HeadAdjust(A, i, len);
2 V! ]! q$ X1 O$ f% C# p; Z0 q}

6 t$ |6 p  y- ^2 |, s  ^& L// 将以k为根的子树调整为大根堆
1 F- c/ {$ U5 S8 E5 G  M  Svoid HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
. W" }1 p% I9 S4 o    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
            i++;
7 e% }; s' A$ u4 P$ A7 S' H        if(A[0] >= A)
            break;
$ ?) x( ?* w4 y0 r' }7 d        else{
            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
        }
    }
7 M& H% \7 x# |8 m    A[k] = A[0]
  m/ q0 N6 c7 m! u}

. A6 h* n) B& g. o1
2
# T" L/ @* m4 d8 d" G  M  E3
( ~! K- G" \$ N: T4
5
6
7
. W0 Y: q9 A2 ?$ I3 k2 {8
9
10
* G6 f) c4 e" S1 ^8 a8 ?: J; C11
12
13
14
% J8 |4 X* ~7 n1 Q* U7 e2 i15
' r8 C3 B& ]" g/ x16
17
7 q. ~. r( P' I7 \! w5 I18
" x( J" e- i7 p4 @$ [7 H% P  A% S19
; \* Y9 T( e- k# g: x$ T. ~" B20
21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
3 e4 W0 Z5 I6 _) ~$ C9 i选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
9 [, B0 \1 j: T
9 S* U+ k! B" `+ c0 n0 N! ~3 _0 b' K堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

" Z9 A& {4 x% G+ U过程：

// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
5 W$ E6 ~+ U6 X8 k9 v) R" c}

( m4 U. |4 r0 |$ J// 对长为len的数组A[]进行堆排序
9 X1 ?* k/ r8 Lvoid HeapSort(int A[], int len){
        //初始建立大根堆
    BuildMaxHeap(A, len);                
) L0 K$ l5 \  H
    //n-1趟的交换和建堆过程
; X& s" R- q* D* F8 M" V    for(int i=len; i>1; i--)
2 S. u. n8 j$ G7 E: t  ~# c3 o    {             
0 C; ~; @8 \+ o4 M! H        swap(A, A[1]);
' s% t$ Q; V  Z* \* e3 L0 X' \0 X        HeadAdjust(A,1,i-1);
    }
6 @$ \' D  c7 D6 A. N2 k/ a}
* `/ P' r6 B8 Z' c* D# H
* M! l% r2 ]- W3 W1
/ w+ K( D1 @6 n0 k; e( X6 F2
  K0 |' [1 z9 B# x* u# a4 c3
% s; w; z' p# L# ?  H. i4
5
  [+ P) O# _4 G( j/ x6
5 _8 U5 u- X: q2 K0 L! ^2 E* W4 i7
2 _: v0 K/ i4 A* I% |4 k9 p! F' U" a8
$ E* ]. b+ D9 @3 c9
10
11
+ ^. ?9 f( O7 A% Z4 T- O12
13
9 F0 P, U- O$ [  H: m: s14
- J1 |) E% e: I( U15
16
/ o2 f: A$ c, N6 K" g* S% _. ~17
; c" ?0 d; S8 x6 ]0 ]- o/ v9 O18
& G. Q6 `0 A' J5 n# E2 Z19
: `1 n% J5 a! k6 H$ s时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

7 H: C4 t' p& X空间复杂度 = O(1)

结论：堆排序是不稳定的
0 P" z- @1 d  r

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


( Z9 J/ k8 }. _% @
) H( ]3 j% P3 ~. B; [⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
* j5 L, i% e+ y2 \. K9 r4 E4 Y
0 B. G1 n- t6 y) D* }9 w* z

3 S' g& I! a- |* h

4. （稳定）归并排序
) S0 r" x9 l0 g/ G& }归并：把两个或多个已经有序的序列合并成⼀个

① 明白什么是“2路”归并？——就是“⼆合⼀”
! L+ P5 h1 _$ P  {5 e: t  y! j
" J. y  G: Q/ z5 n3 S多路归并：
. w  q  P, u% }7 S

② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

/ |, O( n, R6 SB[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
& P9 S; v+ K9 W) {8 I: q  e2 |
. O/ V7 V" j  c  \# q. d& V  O) ]③递归进行分治思想【MergeSort(int A[], int low, int high)】

! O9 z8 m; g8 m& e: Q
3 i8 }+ n: H9 M" [' o④ 总实现代码
// 辅助数组B
- r6 G- X, C7 l0 N6 B) b8 d% rint *B=(int *)malloc(n*sizeof(int));
4 p! l$ L" u' b) R9 Y
! E5 ^7 N5 K9 U) b* u. m* G// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
# Y9 p; z" J( h- C' B; qvoid Merge(int A[], int low, int mid, int high){
: C8 q- u% K* p4 V% ^4 P5 z    int i,j,k;
    for(k=low; k<=high; k++)
1 \( \/ P4 T6 Y& T0 P  ~0 h        B[k]=A[k];
$ f6 Q6 q! @( C! L7 J' t2 j    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
( K' W( e& v, Y. O5 A  ~        if(B<=B[j])
            A[k]=B[i++];
        else
            A[k]=B[j++];
    }
    while(i<=mid)
- X  `- ^! |4 A. I        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
}

3 Y' X, j9 x2 B: k" S+ D" S7 W  G/ Q
8 Q' i' ?" r0 s/ S) e! ~' s// 递归操作（使用了分治法思想）
3 O! K; _  X( M6 o  K0 yvoid MergeSort(int A[], int low, int high){
    if(low<high){
& W, E" W1 j2 W# P% W# \3 ^        int mid = (low+high)/2;
        MergeSort(A, low, mid);
. L0 K$ Q% V- g! b1 i        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
    }
8 Z  U6 A$ w( `0 D$ v4 Z}

1
5 }# `1 l: D' a. E2
7 N9 ?, w! h2 M! `& M4 U8 ]2 V+ r3
4
/ p' U$ P7 K8 O3 Q4 A5
5 a4 I$ F" |9 w/ D! f- A6
% X3 U/ Y9 B9 \) [; Y% W7
3 x5 `* X9 ^$ G: H1 J8 ?8
( ^4 h" ~  d( n5 [6 n9
10
; G# `6 j, C# @3 u. ~1 u11
8 s5 o3 x' P, ~- K12
13
14
) `; b" y# L9 E* r5 C) o) s15
16
  l. F% L, b6 y& ?2 i6 t* G17
18
19
20
21
22
23
24
25
& `* }* h1 k$ x26
: K) o& E& A/ _) K, i$ r! x0 a2 z27
4 s% r& l+ x0 ]28
29
# x! h: l0 d/ b) E30
时间、空间复杂度


3 _  T* \* a3 u) E$ C
! M& \9 `3 M5 i$ D+ o
( a; D; F+ G( U5. 基数排序
* r0 `" S; L9 N. s! L直接看课本的过程图来理解P352

9 V! M9 y& b, r1 \7 j) r0 G7 a再看这个例子：
  `( ]6 N. f/ r" m8 J2 x- [- N: m0 s
  |1 L3 p: F% J, A
6 p6 G9 v) Y9 p% L% |/ d算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
9 R0 o2 r8 e: ]  V; B①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
! a: a6 a' z+ Q/ T# ?8 F③ 数据元素个数n较大。
算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
, j; {, H6 g- K稳定性：稳定。


内部排序算法总结
1 h% t" A4 r& V; i  }. q
, L$ c) D  C/ z& q7 M————————————————
9 K+ C' E: j) r+ s2 D# [  A, G1 P版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969
3 M- Z+ e* G% k) A