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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
! x" x& _7 Q0 z; S+ C4 f文章目录
排序
6 u! J# ^6 o; O6 x% ]# L6 C1. 插⼊排序
) w& \7 k3 A0 M! V2 V/ `（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
9 g+ z. [( X5 q+ {' O（不稳定）1.3 希尔排序【多次直接插入排序】
- L; @7 m! \' T$ X" Q* Q时间、空间复杂度
2. 交换排序
! `8 T4 u( A# v6 N* z% x2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
3 f; J, K+ q7 z3 R1 r3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
3.2 （不稳定）堆排序
3 V- u5 a1 e) s$ U! v' w9 c( l① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
0 n, U  z: ]" ~0 R8 j② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
" s. G1 g/ s3 ~( w③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
4. （稳定）归并排序
. `( d, |& y! {0 J* u) Q  E① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
/ u3 o" o: Y* t' \) k% C3 @" l1 U# f③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
( d( P" ?& C: L. Y8 `; f: g时间、空间复杂度
/ Q# q+ Q, `+ J5. 基数排序
: e9 ^2 C3 m) \内部排序算法总结
% l5 h8 O  X; n5 e5 P排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

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

算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
/ j  @9 y  o( ?: b; z稳定的排序算法不一定比不稳定的排序算法要好。


) J) n$ R. n9 N) _/ g8 \  W排序算法的分类：
, z$ R2 D# |5 t7 M4 l0 c内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

: ^) g2 K+ ^* ~7 ~4 t各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
4 p* O: z4 T7 A3 N9 i' n) p+ V1 A


) z0 p* q( g, d. u1. 插⼊排序
2 q0 Y4 ]. x  y1 b$ F$ X! H  n（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
0 i2 [+ |( N4 O: ]" Z8 \! ^% p# X基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
6 ~# X0 U6 [  J
, z7 ]# M& X9 k5 w% I算法解释：（从小到大）

- b% ~; _0 w2 c2 p  Y1 _3 j" W
6 @5 e1 _( S# [% a, m! M算法三个步骤：
7 Y1 r/ p8 W6 n
2 I  v- c7 `4 W* L先保留要插入的数字
往后移
& `% s, {: f: d3 \+ g插入元素

/ ^; c5 C+ e' y0 D# t3 n// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1; i<n; i++)
    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
1 w2 C' u% v. R7 O1 {8 A; ^1 I  @        if(A<A[i-1])
) }' U0 l; [+ H4 u1 ?        {           
            temp=A;  //保留要插入的数字
; o  G0 }+ f5 T7 o9 G% {2 n
5 q3 N8 J) i2 R9 S7 H# B: i+ [            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪
- J8 f7 @& t" U" |5 A3 O- `% M
6 Z" |! K( m* I* E0 ]            A[j+1]=temp;//插入元素
        }
9 x, X% c3 U. J6 e$ w    }
}

1
2
3
9 _$ R; }  G# x1 G* ?/ f4
5
6
7
8
9
10
3 Q9 u, p6 M- x+ h% [" M11
12
5 m# ]. t$ m7 a8 K$ {13
14
15
16
17
用算法再带入这个例子，进行加深理解

) N* l* ?9 I* c7 V& Z% A
带哨兵：
$ d8 h% q  n  s9 w( W. R" i

补充：对链表L进行插入排序
5 M7 Y7 d1 x$ b- D$ [
void InsertSort(LinkList &L){
2 K( D* h6 H* l    LNode *p=L->next, *pre;
    LNode *r=p->next;
    p->next=NULL;
    p=r;
1 _4 H6 ^; y# m+ p: C, k8 j$ c9 ~! ?    while(p!=NULL){
        r=p->next;
        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
8 h( y+ W4 l0 G- I7 z            pre=pre->next;
* \& ~9 V) j1 a3 ~& Y: U& F3 `: v        p->next=pre->next;
        pre->next=p;
" M( `) E" h: g! j4 c        p=r;
    }
}
1
# A& J/ I! x2 h0 {3 I7 U" M( n( e6 a% A2
3
4
5 k% U. E5 b- d/ U5
6
2 Q8 ]) T# P! ~- ^8 H% g3 O5 Z7
( g& e6 b% L: V6 c8
" q2 ^5 b# f: f7 ]4 M5 o9
1 ~& w) S2 U/ f  A10
# ~: k3 D: l' |$ y11
12
13
/ A0 V$ z5 k) [3 {, v% s; n14
15
时间、空间复杂度

! z" t! ~3 ^6 g/ H* u
. c& b- g1 U9 A  ~' ~最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
5 L% f* b9 `( y0 o! d最好时间复杂度—— O(n)

! b; q: Y6 v4 l' X1 y最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
& ?- p% q" o6 k8 x…
6 ~  Q( G' H7 Y$ V8 S9 _第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)





  J8 Y4 _- a6 w- B6 i2 ]（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：

" z3 d) h  q! ^) B+ a# X/ o
% p, u, A- g7 `+ N4 f
//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
, A6 ]% Y+ \$ S{
    int i,j,low,high,mid;
! d! w/ R) I2 F) G# G+ l    for(i=2; i<=n; i++)
    {
9 m# C4 Y8 X7 ^1 q$ X+ e        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
8 g- ?- W  R7 G7 u+ }        low=1; high=i-1;
        while(low<=high){            
            mid=(low+high)/2;
            if(A[mid]>A[0])
                high=mid-1;
' \& Y2 S- ]1 _: U2 [; ?  x1 H: Q            else
                low=mid+1;
. l, x) Z# Z* N' W% j/ p        }
: G# d1 ^1 V" R% @! @         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];
3 S# C: u& Z6 }( }3 {  D, W) R
3 u2 ~' Z6 n- c  j. m+ Z5 M6 }. t7 `        A[high+1]=A[0];//插入
    }
}
; B+ J) n' m0 U# X& P/ a9 a; t
1
2
3
4
5
6
7
2 A# Q& f+ D: b) [8
: ?( {" c# w4 V/ V' O9
; b3 g( M0 P! P% K! K; J6 U10
# s+ T" J0 n) |& d; R( ?) I5 }11
12
13
14
( O! _8 P# d6 G0 D1 X15
16
17
5 d: U3 u* N/ X18
* M" @2 A1 c+ p19
% ^$ z) a, n; j- z, S20
' z: `( P. u: g: p9 {( ^! [21
22
23
* F, v( k9 G2 a6 P) x时间、空间复杂度
# L2 W2 D0 U# m空间复杂度：O(1)

# f8 _/ {  E# Q: T  H7 v9 d【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
  i( r; j6 [3 w8 ~; D5 ?$ d
/ G, z9 c0 `* x. W2 W4 p! x4 d) h
（不稳定）1.3 希尔排序【多次直接插入排序】
) {8 G5 T. u! d+ w# U. f) i" i$ |是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

算法思想

6 @- X) q  l1 P; v. Y0 L3 p! K# R希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
& Q3 K; N; Z9 y6 c0 E4 x/ [  L' {, ]随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
% W, H2 P- l8 ?9 {# m图解：

2 {2 {$ g# Z/ F: p. l

% j5 h, n7 a- h4 B1 q' I6 s代码实现：
2 Z' N9 a' _/ J, D, k- U' s
* f' N2 Q" G( w$ _) P; a: N' u8 h+ J" [//从小到大
- N6 j6 Q. Y& E3 z% Z+ Yvoid shellSort(int* arr, int n)
: B+ S, t/ }7 w1 R) U* S{
* w. N( R$ G* G: ^. I        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
2 H) j8 B1 i/ D- |6 n% u        {
7 i1 n$ R: {$ r: k, n            //**********************************直接插入排序（只是步长改变）**************************************************
5 j6 V4 g+ M- l            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
1 y) ?( ~# N' R$ Y            {
% f! ^: o  S, V9 V                if (arr < arr[i - gap])
                {
3 w' C; Z* k, a' Q& K( v% r                    temp = arr;
( j' S$ F1 O: f2 Y' D1 [) ^
9 j. Y9 @5 f$ I! z- ?* R                    //后移
9 M4 Q  s, M" ?' m7 S  ]                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];
) ?; K! `  g# A1 w$ I
0 Q& {+ h! }0 T% z/ |$ f9 C                    arr[j + gap] = temp;//插入进去
                }
! y: Z4 l2 w1 k8 ]8 s1 a( A3 B6 d. a6 [            }
            //************************************************************************************
6 I/ [% }: n6 V* o8 d        }
}
6 s: b7 S! ~& U3 w4 P, E- E
1
2
& k/ Z( H1 b3 r; D3
4 p! I1 L9 A8 g& b/ [7 I4
# [8 E3 X$ G- D& |. k5
6
7
8
9
) F' \9 c# |) [- V( {  ~, l10
11
12
13
. i, w, h( c6 |& S14
15
: h: I* u2 V# N0 k4 y4 }: B3 I% t16
17
* w9 M1 M; N% Z3 E18
/ H) s9 v! U8 t; r4 P; P3 x, b19
20
9 m  L2 s2 S" O9 z21
22
23
- A2 p: b7 G" Q/ C5 @; ?, i24
+ x( X6 a2 E8 U" S2 R6 S时间、空间复杂度
& D: S  {" U' i, P" A空间复杂度：O(1)

时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
' i( ?. @. a/ N+ q
稳定性：不稳定！
2 \9 i! I& n( @) T, W% n, }& k
  i1 i- v+ l* x; T
5 U3 S( P6 B/ J6 v
适⽤性：仅适⽤于顺序表，不适⽤于链表
. H, _0 p) [, G9 y+ o# X0 ?

3 K7 b& n( D7 k7 N0 l+ [
2. 交换排序
7 h+ R) I$ V3 a3 V* R2.1 (稳定）冒泡排序
2 ]1 I; ~0 c9 v5 W# O3 R' i英文:bubble sort     (bubble 动和名词 起泡，冒泡)
# D2 K- J. c3 B从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
0 |  B! l; a* W" f
每一轮比较会让一个最大数字沉底或者一个最小数字上浮
& {8 G6 g3 B: a7 h( a. a
) t" t0 X7 w" |0 Q* R; \( P这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
; e8 a: {4 i: S3 ^" l5 v1 S
+ Z  Z& V. Y) L* l% M1 t实现代码：
: a" n- V) M: Q9 z- m
//从小到大：
8 Y* H0 B$ |+ w9 ?& [! Mvoid bubble_sort(int arr[], int len)//冒泡排序int*arr
{
        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
7 l) a3 U/ h8 t& T; N$ v0 A; c        {
% i# k* H. g  J1 @- s                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
                {
                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
                        {
                                //交换两个元素位置
) [) L: V2 K3 M# }: Y: G                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
8 v; v. T2 s% ?3 g9 x+ X$ i4 G" g% O                        }
                }
& Q  b' c% s, U0 ]; `        }
}
) j0 V" [8 l: ]9 J4 b
1
, F9 r' x' O4 B( G2
3
4
5
6
1 b5 K6 ^$ m4 b1 Y/ A) \$ {7
) K+ I4 E+ L3 o4 X9 c. t8
9
10
11
3 {- w8 M, v1 x. R) p12
13
( h$ J( S2 V" s14
. @  \1 ?% e$ P# k15
16
7 p! ^$ _2 ?% _8 H$ x17
18
+ c9 p7 j' j" i. Z& a19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

//从小到大：
# f& v& R. A! Z! ]0 Nvoid bubble_sort(int arr[], int len)
. Q' c. t! T( B# {1 Y8 u. n  E* h{
        int temp;
        bool flag;
  g. \$ s9 b; m* g7 F7 ], p; j8 A        for (int i = 0; i < len - 1; ++i)
; R4 s4 U& g( J% o2 S/ \- ?; a        {
            //表示本趟冒泡是否发生交换的标志
                flag=false;
               
                for (int j = 0; j < len - 1 - i; ++j)
. Y( m! g+ ^, O1 C                {
                        if (arr[j] > arr[j + 1])//稳定的原因
* }% W' B! J6 L                        {
% P: Q" v* X1 n5 @6 Z1 d                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
, t+ @0 I# X! s( q6 P; t                                //有发生交换
                                flag=true;
                        }
                }//for
; [( C1 v# Y+ T* x               
                //本趟遍历后没有发生交换，说明表已经有序
                if(flag==false)return;【1】
6 Y2 N& p2 V2 V        }//for
. b& K6 _( g. r* ?2 `4 W}

, L9 w& R( b$ R1
) ?& x2 f6 N, T3 g2
/ J2 S$ Y  E0 |# x" |3
4
5
6
7
8
: B- {- r* W  |9
10
* V. x+ V. G* Y2 r1 w; s: T& L11
* k+ t$ ^+ {) K' [. [3 V5 v. R2 @6 y' @12
- N, j% l7 a) S1 Z/ F- f0 i13
1 p+ C' U0 x$ w4 d, \7 x) B14
15
16
17
1 T& h0 q( k3 ^8 t18
19
20
21
22
23
24
25
26
9 ~$ p( R3 P8 Z6 G5 U3 u时间、空间复杂度
. Z$ F  b2 @6 {# Q; v' V& Q/ W& z
适用性：冒泡排序可以用于顺序表、链表
1 k1 Y; M  }% n- J" a+ d- h! N. c

6 l: _+ T- G- C2 k5 ~

& u9 y+ M' ^7 f8 J8 R* U2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
* k2 S2 g& u' C算法思想：
. Y7 {8 c( d# H" @3 S在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
  b- z, g& S7 E( ~6 ]通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
# T3 V( i& f( x' |* F. `; q6 z使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
5 T- l0 I: ~2 Y$ W# \- B
划分的过程：
& Q% v! ]6 m/ q4 d0 e% s) m# G$ n! Z
初始状态：取首元素为pivot，定义low，high指针
& Y" Q2 s9 u! C1 V$ [3 O8 I
首元素为49
high指针指向的数据小于49，就放在low指向的位置
% Z% v' D# U# a% Z$ L! ulow指针指向的数据大于49，就放在high指向的位置
0 X$ j8 }0 Y5 X$ c
" L# y3 r$ w* S- `$ U
" Q6 Z% I8 G* o- _! d+ Y% k


7 R; z- |" [' f9 h6 C0 W+ \// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
% [3 j7 j8 Z4 w$ O9 v, s        //取首元素为pivot
, Z! p7 v" t! O9 x3 `: z, Q" N; }    int pivot = A[low];

    while(low<high)
) [% ~0 k% X# D# }! k4 q. P    {
1 e1 m$ ]' |" y) k            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
            --high;
8 G% B! g* A; |0 q        A[low] = A[high];
3 l' w: S  R7 u2 e' p6 }0 L
        //随后low向右移动
  A5 w$ l1 C2 r$ D        while(low<high && A[low]<=pivot)
            ++low;
        A[high] = A[low];
9 F! l  F. _- n& q. h' g4 u    }
1 I% Y0 U: B& o1 p% }
    //low=high的位置，即pivot放在的位置
    A[low] = pivot;
0 M7 f, E5 b  _8 `' r# r
    return low;
5 T7 a' S4 e  I0 H: v}
4 T; u+ r9 Q. j) f+ F
// 对A[]数组的low到high进行快速排序
void QuickSort(int A[], int low, int high){
    if(low<high){
+ h- I" O$ s: k( M& W        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
9 H& o. K5 n2 Y0 D( \1 L# Q% D/ V* u        QuickSort(A, pivotpos + 1, high);
    }
0 E$ O# O/ @; \% F/ m6 v/ P- I}
/ I5 C. x0 k6 _' Q8 f
4 \7 K0 g7 H7 g! v$ }3 b% i# T8 y1
) u( _- t. }5 d4 g8 c8 ~5 S2
0 f" w2 u4 o9 s. `* H5 i$ n5 s3 @3
( M1 `5 w. g2 p. V& W- w  b1 z% `4
5
6
; U' [( U) m/ d5 a1 ~- C, I& x" ?7
8
3 [) `# _7 v0 e6 w4 p9
# R/ `" ?/ y6 N& ]" C  I4 H10
/ r' ]6 U3 R$ j* J; U! j7 t" ?: ~; k5 x11
12
13
14
" y# R  V' P, Y  {2 n, J! ^/ X15
16
17
( G9 W: h2 ~1 M+ o6 T9 A5 t18
' ~/ Y" Y/ {; M6 r% I( m19
( v  e, p+ _7 K* U* j# p20
" i. g) }& Q* v# h! J21
22
23
24
25
26
27
% N7 C2 i3 |6 U% o6 y3 K' G28
29
7 w6 Y1 _$ ?7 h; s30
31
, Z' |% L% x8 a9 _) x32
5 _. d5 d* L$ Q8 Q时间、空间复杂度

3 |: A3 ^* b( G5 B* D
把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

) G3 ~- P/ K9 [n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n
- x! k6 x; O8 t: u
! H4 L: j, P+ X1 ]( Z3 M# k时间复杂度=O(n*递归层数)
/ U* y) u  A0 ?- G7 v最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

空间复杂度=O(递归层数)
  H& M8 ?5 f: G6 ?$ x- o最好空间复杂度=O(log2n)
. j7 V& _9 E* z- g, l最坏空间复杂度=O(n)
/ L  w& R+ S9 r9 i7 J
最坏的情况
, [* P9 I% a5 `


  P$ T% E" X. ]8 }; @- K  Q  ^⽐较好的情况

; m$ c0 ~+ i8 ]! o. [' _' m$ w
1 q3 u; M/ [2 S) p$ p; _
  @  o0 Q6 k& _) @8 L不稳定的原因：

* P) F1 G0 {$ Q! }* J

9 l6 c6 f0 |9 j4 m' r: j

3.选择排序
  b1 d6 f/ x& o0 l/ U选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

6 M6 L; H. @/ ~9 V' u3.1 （不稳定）简单选择排序
3 w; T1 n6 S0 o- P3 I" I算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置


/ L; R" c+ c6 k2 O, k8 c  g
. X& _: |8 u1 ]+ p( i5 ]' ^// 交换a和b的值
5 h1 K! T4 T) S$ T5 v  Tvoid swap(int &a, int &b){
- X! X( H1 l/ D/ }7 s; k    int temp = a;
    a = b;
3 Q, R9 }' l) O  g, ^    b = temp;
}

// 对A[]数组共n个元素进行选择排序
! g' c7 p  z# \: ivoid SelectSort(int A[], int n)
2 r& W( L- [6 U. ~0 R1 T# c3 v{
  j  A; |) r3 j+ M) k, s        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
    {                 
        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
                min = j;
- O/ V  F, l8 [9 M! V) S" {4 q        }
# ^$ ]4 G2 f& G1 T+ H/ r  _6 x        if(min!=i)                     
            swap(A, A[min]);
    }
6 J% w. U* f. N/ n# _& \}

9 V. l1 k3 Z5 \" R1
1 |6 k. C* o5 e( o/ V: d2
3
4
5
) v# p3 M  [0 g4 R6
7
8
9
, x$ P* U0 q6 E1 H8 ]' I+ [& X; Y! Q10
, z! x6 ~9 ], L' Q11
12
, p7 l: G" i& e  C13
14
15
16
17
18
4 y, x+ a6 E% d$ s9 t% E& B+ t( ]19
20
21
22
补充：对链表进行简单选择排序

6 ?5 S. m! R( D. b2 l- K# avoid selectSort(LinkList &L){
/ X' G, ~: W6 U, F# N1 Q    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
    while(h!=NULL){
8 c! E2 Y7 \  p        p=s=h; q=r=NULL;
        while(p!=NULL){
- [& V. S# D6 h& K            if(p->data>s->data){
/ J: a7 g0 K; X. Y                s=p; r=q;
! n- z6 u9 n  M$ T: d+ v            }
8 s! h8 q- _+ p9 X+ |            q=p; p=p->next;
        }
        if(s==h)
            h=h->next;
0 t, i& k' Y) G        else
: }- n( N) p' a' J. g8 \, Z            r->next=s->next;
        s->next=L; L=s;
    }
9 M& @2 C5 J2 w}
# q5 s; K' O; W  V, b; d
/ A+ t; c+ v8 j; U, l  U1
2
0 k& q6 B& h7 S! y* R8 z2 d& ^( w3
4
5
6
" a8 I5 g% _  u7
4 }/ N: t1 j& {8
9
0 G( k+ \  \" r& ]0 v1 k: A2 S7 J2 y4 R% \10
11
, z1 P+ ], t$ A1 \- n, C/ L12
13
14
6 E8 B3 S; q8 l7 p6 w15
1 U& z1 F% u7 }/ h; Z5 {: o5 P: P16
2 g# G: I- X1 ?( v* e& L17
( S2 Y# E3 Q8 J$ |2 \18
- t" S  K+ D' l! @' f( W& k& u( {时间、空间复杂度
. r) X# {* i% L7 T) s% {

; ^& @- O; p& e" L! w' w7 l
2 x) C1 [: z$ |# I* G4 T# G0 d; @1 Z
适用性：适用于顺序存储和链式存储的线性表。
; h) t- X- U: n& l$ B- x9 a7 V6 M


5 x& ?( M$ I) x3.2 （不稳定）堆排序
. g- G& g  d" x' c& @① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
6 Q5 x4 H7 z6 D, z/ ?每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
7 d0 f" L- H# Y$ h- W
% ~8 u7 y. L  F. k7 r' c% k

0 ~4 U  t4 c. ^* J5 M( r即：
$ \! i6 g. F$ J+ \0 \若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
% m5 v+ O9 N* D8 f+ J若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）

② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
( k; y# w2 z  E5 c5 M思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
; o/ @! L8 W; E  e- s+ v4 ~
在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
' d; d7 a+ R0 v" Y) O+ p
检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

5 N3 \& ~5 _, O& L9 l过程例子：

/ ]6 g5 \* T2 E' t3 p2 e

建⽴⼤根堆（代码）：
. h- o/ D& r2 C& ?9 r

" G- J4 t. y( j# C, R
// 对初始序列建立大根堆
) o5 U4 `" {" d5 E" Y6 s4 rvoid BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
: w& W7 L9 e$ l8 ~& A, |        HeadAdjust(A, i, len);
}
  u9 g) j) @# \4 A% E! f
// 将以k为根的子树调整为大根堆
5 e) l2 ?0 Z0 d% O" w# Hvoid HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
            i++;
8 j( {. ]# m0 |, O( L3 O1 q: z        if(A[0] >= A)
            break;
        else{
            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
' z; d8 ~5 m9 M! E" c        }
    }
    A[k] = A[0]
}

( R& f! X2 U9 r) O7 ]6 \1
+ c. e; _: D& a& R2
3
4
4 I9 Z4 i* ]  s2 E3 z! y1 I. v5
; |9 |; f2 W; M5 G. _0 b6
7
8
* L2 z; {" s' m  @: I+ j, {9
10
11
7 @% L, S: s! f12
* f% p/ m9 S  e, G13
14
1 a$ g7 L* ^2 p) i# e15
: f6 d7 m, H! U' j16
5 |' [& Y/ W/ B/ z  J* g) y1 w17
18
9 A! h* d; R- J19
3 _8 q: D  ~  f  J20
: D6 Y1 W5 \9 P21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
9 [/ O  A9 g, G+ J  |1 I$ l选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
0 e$ U. `0 k* \
过程：

; i8 W) u8 K, p& _+ v// 交换a和b的值
6 l* G' o5 X( H* ^$ `* cvoid swap(int &a, int &b){
% M8 z2 s7 l' B- H    int temp = a;
2 K( D& @, c& N& b1 J    a = b;
8 \# I' D5 J5 y/ d( j3 ?    b = temp;
+ C9 T; Z4 I- c; S6 ]}

( C" c! f/ n0 ?+ D2 u7 L// 对长为len的数组A[]进行堆排序
  ^0 m" o& G: g1 q' w, u1 Wvoid HeapSort(int A[], int len){
        //初始建立大根堆
    BuildMaxHeap(A, len);                

7 q* d1 h. N7 n0 |    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
5 s9 }4 D, l4 @+ e+ V    {             
2 Q* ?" s- A0 ^) I1 J' t$ J- j        swap(A, A[1]);
        HeadAdjust(A,1,i-1);
    }
}

1
2
2 E) u) M1 V% `: x/ @1 U3
+ Q2 w* u3 H' k4
) o' K! I6 m" X6 N& S5
6
) V$ j# n  ~. C( d; z  _7
5 d8 y4 `* O8 ?" s9 m, {8
) {( d# w; ^/ D6 K* F9 Q9
* I1 T, K& k6 _4 R; E( @1 z  F10
8 @: E* l8 R' j, z# j+ k11
12
8 R, B1 D' H  p4 v8 w13
: h. i3 G. N6 Z. i* i, f14
  E( }) q; s1 B15
  }' O8 B6 k( P$ l& `+ U0 D3 D/ u16
17
18
19
时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

空间复杂度 = O(1)

结论：堆排序是不稳定的


④ 补充：在堆中插⼊新元素
4 `5 p$ c+ O; l* I; h2 J对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌

  f" W; j; A4 d! e

" d8 T( m# H" f- X! R⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
( v  k4 {6 v: E7 Y2 ]

9 t' u: z9 T. q3 A7 c! `
. i5 p" E( R' l1 G* E' W1 N! G& U

4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个
$ e: D9 A# `7 y& [  z
* X2 k! Z  [0 h, v, L$ ~① 明白什么是“2路”归并？——就是“⼆合⼀”
/ h) I- k+ c/ x& r! v
多路归并：
+ E  }* ]$ ]3 E) M: V
- [5 [  x5 E3 S4 }: \7 Q) b% u) O
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
2 F9 d* M/ `' }0 a6 n
B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
" Y0 n; T2 X; d/ n" N2 F6 k
9 s. f6 ?9 |) ]! ?" o9 Q" m③递归进行分治思想【MergeSort(int A[], int low, int high)】

; P6 Q4 @$ O& Y% ?  D
" f' m& d1 P2 K0 X④ 总实现代码
/ `" n; f/ P& N  U4 A- y// 辅助数组B
" Q$ V. ]+ Y; E2 ^" m1 c0 |3 Tint *B=(int *)malloc(n*sizeof(int));

2 Z1 X5 R, f, a9 y5 Z// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
9 p! h# w; ?4 E% J3 U    int i,j,k;
    for(k=low; k<=high; k++)
5 C6 t! O0 W6 V5 F( A# k        B[k]=A[k];
& G7 \! P3 u3 Y1 T8 J    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
" ?% d- e7 n0 Z) @! Q        if(B<=B[j])
* x5 A* ~; a1 J3 f            A[k]=B[i++];
        else
0 _& w! w7 J9 w5 U: X$ q* V3 [            A[k]=B[j++];
    }
    while(i<=mid)
        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
}
  U/ @1 _3 J6 L, i5 Y! {
5 V8 E% `) |0 C6 ~. N
. m! }) Z( ?) R$ f// 递归操作（使用了分治法思想）
0 C# b( R/ r2 a+ Bvoid MergeSort(int A[], int low, int high){
* s7 n" G+ o6 E    if(low<high){
/ ]* j% _& s* j1 R$ b$ @        int mid = (low+high)/2;
        MergeSort(A, low, mid);
  w% T  Z" L  L        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
3 w) v5 `6 J5 i2 O0 q6 ~    }
}
1 M* B& s) F4 B& w3 P+ p( a
1
3 i2 k  K& o) ?0 Q0 N8 _2
3
4 e3 M, V9 a' \% B( e4
; R+ \) P" f& _& u4 f5
6
7
# r# X; I! `; F8
2 c, L, \4 {% N5 i) R9
' C& s* a* C; i5 K5 R) i10
( R8 ]' e  I- I4 {11
& z0 J$ R. o6 P+ K12
13
, X' Q/ Y' E! [. O8 `6 [14
15
16
17
18
19
' H: E' w# c8 P1 j. r" N# O0 n20
9 Q+ u: g9 }9 Z% `/ t21
* b. C/ S% |! v+ A2 n4 I22
23
24
25
  M! ~8 l) S; s; z26
27
28
29
30
- B( `# v2 I, t时间、空间复杂度




  w. Q) R$ s0 @$ o5. 基数排序
5 B: B4 E, p  W$ P直接看课本的过程图来理解P352

" i! n* ^0 c5 G0 c9 w% x" _) w再看这个例子：
' [. t' z: b& p' K3 q, N6 |1 z5 H9 i

算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
- L+ L& y6 X% q) o. ?+ F; `分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
" d6 T) _2 x! R2 \( G- g收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
, t9 @9 q5 Z/ H4 S+ S! c①数据元素的关键字可以方便地拆分为d组，且d较小。
! B  g' i6 u: ~1 N4 P3 C②每组关键字的取值范围不大，即r较小。
5 C- o7 p. l- D, w1 j" p- k  Y③ 数据元素个数n较大。
算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
4 B( W! W" r' @( q# ^  N: }: H空间复杂度： O( r ) ，其中r为辅助队列数量。
3 w+ r; N0 X, T8 x- i- V2 m稳定性：稳定。
, R0 V" P5 f6 N9 y" z

9 E, G2 ^4 }6 A! k7 V: w7 A$ A( z内部排序算法总结
; |% I+ |2 @+ h: F
————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 w. a/ f' j; r- F- T6 _原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969