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

杨利霞

1 t- N6 X+ |0 U3 ]- U【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
! l* |# v( f7 D. p" a排序
* {+ z, X7 U2 B* h8 _1 E( W5 L' ]1. 插⼊排序
9 H( G$ f+ A% G  @（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
! [- e5 o3 s* m& P/ h! P时间、空间复杂度
! K+ x0 P! r8 ]( Q（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
时间、空间复杂度
3 o( K+ G( x# V  [9 L7 r2. 交换排序
( Y: ~8 m: s. u2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
3.选择排序
3.1 （不稳定）简单选择排序
1 Z! s5 q" R* W' ]- {6 C0 I时间、空间复杂度
3.2 （不稳定）堆排序
' w, D% V: @$ V① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
1 ?; M. a# k, x③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
# H% S  n3 [0 v) T" f, S1 V④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
, Y* Z, }( s. q& t② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
$ N; A/ C) O2 T  u4 S7 s& Y③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
) c+ B! V) [& O$ s' i时间、空间复杂度
5. 基数排序
内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

4 B8 R3 n3 |5 j6 q- x4 b排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
5 h6 j9 Z+ s! m2 k' Z* D+ {# s% u4 \
4 c2 e2 Z6 J7 q" r算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
1 n& O. y: I* W; y5 u稳定的排序算法不一定比不稳定的排序算法要好。
4 J# P! P# v8 M# r3 u2 b
+ N  h8 g% b8 b% ^) ]+ C" C- f1 e
排序算法的分类：
+ `8 Y1 L* d$ P7 X内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
( p0 A$ A+ b" E2 X外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
) J4 H& Z3 D( U6 E% G5 T


1. 插⼊排序
- _  H& E, F3 ]1 N! i4 u  h' \1 |（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

算法解释：（从小到大）


算法三个步骤：

先保留要插入的数字
4 b0 z& ?8 N+ @- V+ x( l+ b5 y往后移
插入元素

// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1; i<n; i++)
    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
' ^* A. ~1 Q* t& Z8 `. V/ Z; w  }        if(A<A[i-1])
        {           
            temp=A;  //保留要插入的数字

            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪
" A# x6 O* x  }' j7 T$ G
0 T2 z! g* g2 ?9 A2 n! R            A[j+1]=temp;//插入元素
        }
. p* Q, t- i/ }1 X: V6 q$ Y4 R5 w* J' X    }
& l/ @% w3 y6 Y* M. |; E}
, B. I: [5 a' {. n
! q! A8 a; d% Q9 |9 s1 B7 U1
2
3
4
5
  z2 B" _! D( E! W. K; C6
7
! B* O: p+ J. ]; p( |" M3 R8
9
10
11
12
: U' p: |- C+ A/ D0 G) a5 J13
& h9 a  v+ X& _3 J) ?- Z( S14
15
16
. x, p$ y! K! d) a17
/ e( m* n7 X* p9 h7 n  z9 \6 l用算法再带入这个例子，进行加深理解
4 h/ j# }+ M  c. r

8 c1 f$ o- X( I+ U5 m' r- g带哨兵：
6 o; [* v) O  O. l% O. z. G8 f6 `

' t# g+ R! v0 g$ j# h补充：对链表L进行插入排序

8 I8 w0 a: z  A1 {2 cvoid InsertSort(LinkList &L){
& _6 r7 {+ ~! r6 z" K- N    LNode *p=L->next, *pre;
    LNode *r=p->next;
! O7 a1 F$ k- q    p->next=NULL;
# a% e8 }/ p/ f- X; i+ r5 h7 l    p=r;
    while(p!=NULL){
        r=p->next;
        pre=L;
+ n) U. {# @" Z9 N) z        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
        p->next=pre->next;
        pre->next=p;
        p=r;
    }
}
$ k: b+ j2 g' {9 E/ {1
/ j+ L9 a" q6 I1 s0 R- t& M5 W6 Q5 x- v2
3
! m8 u0 g  q8 M. y% _4
5
2 `. p: Q( N' {; f6 B. M6
7
: f( Q! |  {5 L9 y4 j8
) y- f' v8 M$ @8 c8 l9
10
' u2 Q4 g) f) u6 Y( j& M0 X  w" p11
12
, H3 y+ K4 u: Y* G13
14
15
时间、空间复杂度


最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
4 k" b9 a7 B3 s0 X) H9 H最好时间复杂度—— O(n)

3 V2 q( f6 r( I2 s% D最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
1 h. C; ^& s" e0 F第2趟：对⽐关键字3次，移动元素4次
…
8 c) j+ q' U/ u第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)

5 F) z" k) L+ w! \7 K( l& Z$ T4 v
" }% p9 h2 g; n4 C( E! o9 k, |8 N

* N1 D" N0 Q" z" S) z: S# f# ~  h
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
) L, ~) ~; d' \, R过程：



//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
{
    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
$ x/ @) h$ }4 k    {
$ E/ y" x( z& k* Q" a% Z6 D7 K        A[0]=A; //存到A[0]
: H! F$ _" Z  e) j+ [# ~/ Y: F* l        //-----------------折半查找【代码一样】---------------------------
* h2 r* a! c! j        low=1; high=i-1;
; b5 ~- B' s& F        while(low<=high){            
, m' y2 z; _( V' a  X            mid=(low+high)/2;
- ]& t# w& [' {2 ^5 d            if(A[mid]>A[0])
                high=mid-1;
            else
  ~6 |8 _! T3 V% F5 f                low=mid+1;
        }
$ E( K1 l* [+ z5 G* P         //--------------------------------------------
5 `3 u& d- i9 s- N- Q- [& |        for(j=i-1; j>high+1; --j)//右移
; J4 A+ \3 U) ]" G  ~9 ^: U% X            A[j+1]=A[j];
- F0 e* s4 O/ F3 {
        A[high+1]=A[0];//插入
, |/ E3 o+ e9 g# Q; Q5 s8 X9 L    }
8 t# F/ `1 U/ f" }" [5 Z+ a) ]}

. ^# i, r/ ?0 C" p4 r) H0 w1
* [! H$ m. T' f- _2
3
2 K( O8 k3 E' J! W4
1 |6 X) T" X7 U' \  P$ I5
5 t3 h5 e5 _: q; {) H' K6
7
8
: K. i! w) c- V4 v/ {. M9
; |. d( A" O$ A6 y& _) L: G  G10
: o( R% h/ c# ]; C3 N5 E0 A* A  y11
/ U! d$ X) L0 A$ i12
13
4 j% e$ ?0 ^2 \/ V& B; S% q+ c# |14
  \. Z( Z  Y% N/ [! K8 c4 R5 R15
16
17
18
4 E! W0 T  H+ a: {5 W19
3 M# E  j9 P6 K. I3 S' k20
! p+ A4 r3 G6 d) l5 P# F/ y21
22
23
时间、空间复杂度
空间复杂度：O(1)

, _) ]4 z! K( j% n  x3 e- o2 @【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
1 k" k# `! }5 o5 e
7 A7 h) C7 u/ u
（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
' C1 b  H6 D$ n- L, V. P+ ?: I
, k1 r" I2 F5 ]' Z/ ]算法思想
1 R  a. _# n' T4 \' c/ E, E
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
& w# D* m) F/ a2 ]$ H0 Q6 V$ }图解：


. ~4 g$ x/ f- b1 h. }' X+ k
* K  n2 N3 i1 @9 \  d  t( _( `7 J( C) s代码实现：

/ C1 J) A6 l2 R( W$ a3 l1 e2 R//从小到大
' g, s  b8 [3 a* T- k0 q0 }void shellSort(int* arr, int n)
6 ~; k- U* q" Z  l) x{
        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
, g8 b- ]0 C: N" e3 t& }+ K0 Y        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
- X; `% I; Y* X, `2 B8 z            //**********************************直接插入排序（只是步长改变）**************************************************
2 Y! P) D1 X* |% ]; t& U" w            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
                if (arr < arr[i - gap])
0 G. R2 g# i9 n" \# B; P# {# `                {
5 _3 l( r4 d. p/ H                    temp = arr;
% v" a6 V9 L7 t- o7 E' A
                    //后移
% Q  B2 O! Z/ J                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];
% n: N: {# g/ J) _
                    arr[j + gap] = temp;//插入进去
( z! ?8 x2 T( w! h  \8 E+ L                }
7 Y7 o# c8 v. ~; g            }
. o; G1 s; U. D+ r            //************************************************************************************
        }
9 X* R+ b6 X0 ]}

1
2 U5 `; M( r. S. n6 |, l: K2
1 J0 @* V: x; _3
3 z! S( }1 \- o6 w. r4
5
. D% k' U: w' T9 F6
5 F6 _  K% m" F5 G3 K7
8
2 |: B8 z7 {' Z6 |# C* x; s/ Z+ A& w9
& I; x; }" M# z7 Z10
11
12
13
14
- n* I( Y* v& p9 m15
16
( ?  k6 g" u' Z3 `) u0 m17
2 K* V, _: f; i) q3 a7 p! l( M18
19
; i1 q  l' Q# L$ i  l20
21
22
% ?) m0 k7 y; r% @23
9 U  I. o3 B( j" L" j$ M24
$ F7 p3 `9 T) H5 B时间、空间复杂度
空间复杂度：O(1)

时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
/ @9 r' i3 C2 O
' D$ |6 x1 n% |, G/ t稳定性：不稳定！
/ u+ n4 a7 _+ r) G2 Q
% A; @' L9 u7 K% x7 R& U' T
# _5 d) g) J# j- I6 r, J! W
适⽤性：仅适⽤于顺序表，不适⽤于链表
) i. u/ `: j! _/ V8 T
. j9 a# c$ Q, S5 D+ _3 y
* Y9 D  r* [' R+ ^/ t/ I- x5 C
2. 交换排序
# n0 Q" r2 q: \- R  G% P5 k6 k2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
$ \1 h4 c, |" M* O- I3 m" ^: u8 X从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
  E; z4 h, z8 U) M; v+ k
每一轮比较会让一个最大数字沉底或者一个最小数字上浮
6 b' y( B' g! \* q
3 l" o2 W) ]- e7 `& b; [这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
, w: g% ^) k( K; F+ M
. q4 s7 K* v; q/ T' y4 R实现代码：

( j4 d. l0 o  N  W4 E  O//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
{
        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
& x4 F; N4 r- ~8 w        {
8 ^3 ?: o+ Y6 j; M                //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
  t" |' X" W% p* J" ~3 m1 W, A                        {
* E. }: ?4 p. q+ q/ e. M+ A                                //交换两个元素位置
                                temp = arr[j];
  @6 {' W) J. O4 g9 _% v0 q                                arr[j] = arr[j + 1];
4 d) o9 W1 q, P+ T                                arr[j + 1] = temp;
6 i2 {4 u5 _) f# L: b) y+ K                        }
( f& N9 o- K% {: Q; `2 g/ F                }
% {7 q9 ^. v: m  i1 r) ~8 t4 F        }
}

1
5 D  d: h# b4 P1 d% [" q& j2
: ?7 G. }) X: q, A2 L1 }, L- }/ [3
3 z, R6 A( c% A- P: U( {4
5
6
7
8
9
10
11
1 r1 j/ A0 l3 q3 y: D12
# y; f7 Y; d6 t% W1 |/ `  y13
( a) t, g: `5 `! d( _" O0 P14
, e4 ^, H1 d6 \5 K. g8 k6 @8 ~15
5 ^: G( R& ]5 V9 |+ g) H, v, p! {16
17
18
19
2 H: p8 d1 y2 v  y优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
( u- `9 K, [. P
3 y2 Q0 [9 B, ]8 I  m: L//从小到大：
7 g6 J& p$ q$ P  ?2 X) w0 fvoid bubble_sort(int arr[], int len)
  ~/ Z/ z, F. k+ e! C{
        int temp;
        bool flag;
        for (int i = 0; i < len - 1; ++i)
/ L; y# Y- {1 K+ V1 G8 G% F        {
, l9 x% D( b$ d1 `4 d            //表示本趟冒泡是否发生交换的标志
+ j' S1 y% K2 B6 ]0 b                flag=false;
3 D0 V  B8 G, S  V, \+ Y  [) c               
                for (int j = 0; j < len - 1 - i; ++j)
                {
                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
4 I7 z/ g8 A: H* h# t/ m                                temp = arr[j];
- e1 P! B' {- ?                                arr[j] = arr[j + 1];
! O5 d$ x3 Z. C6 G' ^6 S                                arr[j + 1] = temp;
                                //有发生交换
1 e+ e: c! r  G! ]                                flag=true;
+ m# K* r" n$ s2 ~! V) T4 o/ y1 [, ~                        }
                }//for
4 K; N# m' G( s! W               
                //本趟遍历后没有发生交换，说明表已经有序
                if(flag==false)return;【1】
        }//for
}
4 i2 B9 |+ k/ O) b5 X( u, l
3 d6 U/ }) |* @. G+ d7 y: v" u1
2
3
! X# H. X' ]0 h. w5 R$ [5 e4 n4
7 S% C: R5 c+ K4 A' o/ d5
6
7
# K" W8 f+ |8 j# ]1 I+ r: j8
9
0 ~+ j0 i* o, F10
* |" t1 C$ u, G) G11
3 B0 b$ A' U" s9 ~12
13
14
15
/ j0 I$ ?3 ?5 j* ^- d4 @% K6 H16
17
; h; B0 r3 g5 N18
  g6 P; O& v6 H19
: p( u  t- F, C/ ^. ^# G. I* e20
* h& ?9 P: w. b, x! C21
7 ?( b6 n+ [  r22
23
1 T$ c9 r" G- n4 f& D! k, D8 i24
/ ~; x, M. ]8 W25
$ m. c% }9 W6 e26
: z) W% @3 l, z% \% s: V时间、空间复杂度
1 G/ k+ [8 c# ~# M, a
适用性：冒泡排序可以用于顺序表、链表
; l* c" q1 \- P# P7 O



6 q: p) Z, j6 U3 Q9 w* H0 G2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
, s: O3 e1 J  n+ L5 G通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
- {2 O! ?5 Q& @- |使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
: _' i% a8 T/ {) z' ^' t再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
: h4 B7 S3 U+ C; H7 m* t
& l1 O7 d7 V; e然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
9 s4 F; j' Q- X/ m) r
8 B) W, _, S6 X- P! d" ?划分的过程：
+ d/ T5 ?( w: Q5 N" ?+ g1 w
初始状态：取首元素为pivot，定义low，high指针
" b" [9 B8 p' `" d
首元素为49
* X: h  D. f- H+ g+ S+ mhigh指针指向的数据小于49，就放在low指向的位置
7 Q0 ?: e6 ]! j; d8 N% A5 k1 ~0 @low指针指向的数据大于49，就放在high指向的位置

% c7 G+ V2 p! a+ h/ j
* |0 \; ]4 s3 k& q/ i' c; d1 |! O# b
) J* }0 @0 @2 E% O% J; g

// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
        //取首元素为pivot
7 A, P. k; P! E& r" Z8 i    int pivot = A[low];

    while(low<high)
+ R' H- j# d! I    {
            //先是high开始向左移动
4 Y- x, \1 _1 e" i  W        while(low<high && A[high]>=pivot)
2 U, J2 |: a0 J: P* {) i* a6 `            --high;
* W! }; Y; u( }& }, ]" ]        A[low] = A[high];

        //随后low向右移动
5 U; m2 y, D: Y: c) l, C6 i+ ^        while(low<high && A[low]<=pivot)
" X, ]! q$ R$ d8 `# M0 ^* A            ++low;
( q' ^& M$ I6 a* Y8 k5 c. O        A[high] = A[low];
    }

    //low=high的位置，即pivot放在的位置
/ M, i! v; @, P% Z    A[low] = pivot;
/ q" e" H) l. Q9 d& b9 K
    return low;
}

( @. D, I4 e8 S( I8 g// 对A[]数组的low到high进行快速排序
* h+ B3 c& L; k: [/ |3 Yvoid QuickSort(int A[], int low, int high){
  n% X. F1 A- m9 m; H. t    if(low<high){
! e  `5 K1 C3 d9 V8 {6 l        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
. ^8 D& T" _! `" z! h7 j4 P( {        QuickSort(A, pivotpos + 1, high);
    }
6 _! N  F" Y* W) k! I" ^- s- u}
: M2 d: I: Q2 R
1
. n9 R! s. X& W6 C5 e2
3
4
; a. f. w! ^7 s9 B) l/ J: |3 ]5
6
7
8
4 y7 W; H4 W7 k, v3 G- K8 e3 e9
10
11
/ W% x, a; m, Q( @5 @$ z9 W12
13
# h& X2 \7 [) U1 s) `; o' B( x  w14
15
2 z" d3 f$ @5 m9 Y! l16
17
% a: E  }; x3 Q5 ~& s8 B18
19
20
0 b" X+ s2 P! p5 ]. C& G: O21
22
1 H; [' `: O1 V+ e23
24
, n# t. \7 y* l7 l- y! r, A5 [: j25
/ f$ o8 @7 l8 G. ^26
27
28
9 Z; I2 B4 ?, g29
. ~' Q/ E$ w5 q' x- `30
31
32
; j! I; b7 K: l: d4 q时间、空间复杂度
* `9 N# [, E! c1 |: v' p
) `! X; d3 z. f" \% z% _+ S
, G1 ?8 ?7 |0 F8 S; M1 O0 J* E把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

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

% ^( X: E; t# a* z时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

6 a) I5 u( ~# E) Z% ~/ {& A- e空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
: C  y: Z/ t; S0 {, H$ g, O最坏空间复杂度=O(n)

- k" ]& q, {* W8 A( r' q2 A2 u/ C最坏的情况
+ k0 K, T9 @7 G$ [: M# ~. t, m+ ?

8 f6 w0 ^$ ^& z8 S0 Y
% E. S* x, X8 t8 G; r7 M, _  f; k⽐较好的情况
- ]6 }8 Z4 ]+ `; t3 U& y) T

+ E7 u2 ~: a# s
: G: e# q! s/ x5 Q% s3 _3 K不稳定的原因：


/ U% H+ X; A0 D; o) M


3.选择排序
! ]0 m4 c8 H- Y8 y6 q( C' U- g: k选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
" Z1 R( f# f. l, j6 |. u! X# r
5 F& M& W9 n: N' L; [: H, T! [3.1 （不稳定）简单选择排序
+ m$ u' x# \. I5 N+ v9 z8 P& i算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置


& l) d5 J3 M$ N% u7 n, ]" j
// 交换a和b的值
void swap(int &a, int &b){
, ^0 ~) Q) O/ }1 d. ?4 j4 p1 I    int temp = a;
    a = b;
! }. S; J$ S; i0 O' W5 E    b = temp;
}

// 对A[]数组共n个元素进行选择排序
& Y5 g% D  p7 F# q" xvoid SelectSort(int A[], int n)
{
        //一共进行n-1趟，i指向待排序序列中第一个元素
& }$ v2 V: w- f    for(int i=0; i<n-1; i++)
: E8 F) D7 b. m9 \    {                 
/ ?# v$ }8 y/ o2 `! _        int min = i;
. a) d- `% k) k        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
3 V# \9 X* N& @                min = j;
0 [9 R, I8 K' D& `+ Y+ j        }
! J. j# Z7 Q0 Y" |. \" b        if(min!=i)                     
. s! i( m* O& h6 V4 p  O' n            swap(A, A[min]);
    }
}
: P# }' l5 \7 I' M
1
: E; r% l0 L- \9 x% A9 I7 [2
8 g0 ?9 H: {& H2 o) U. J" W" {3
( k% V# g9 w# j$ p7 b4
8 W2 |% X  X! \7 D, B! b6 q. @5
6
7 Z) K0 ?! h) b) W7
+ e% g5 T& @' E- p8
) T& s2 f# A# v! ^. F: v& U' t1 z9
10
11
12
13
14
15
! I# {6 k& x- d16
17
9 i* A+ c/ @  S9 M6 P9 `  O. f18
. M+ ^) G# O7 L  l* f7 ]0 o19
20
21
22
补充：对链表进行简单选择排序
& G( M6 P+ k. m/ S% R6 s4 `
void selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
3 c6 V& j+ q  k; r$ G* N* d+ ^    L=NULL;
$ v2 w% ~+ S' N; o3 N3 _    while(h!=NULL){
$ l4 Z" O8 o/ S# k7 n. n9 H$ b, ^        p=s=h; q=r=NULL;
: \4 c5 `! p# p        while(p!=NULL){
9 @" e; k" W- E. t; n; M2 _            if(p->data>s->data){
                s=p; r=q;
, e2 I2 R' p6 q) v# U. @; \; L  s            }
            q=p; p=p->next;
        }
8 F. \& x' @/ w1 o        if(s==h)
- Q. s: ]+ J& R: ?4 u8 w) X            h=h->next;
        else
! Z5 q* l+ Q' j4 J; ^2 g( A, h            r->next=s->next;
5 {0 H: I' N; ^4 t4 q" d1 g4 o        s->next=L; L=s;
    }
+ q$ r0 o' p8 N. D4 s% o3 u}
4 N( A/ S1 h, D3 B
1
6 c2 @; O$ `# Y! z8 F2
& R/ n- p% e8 j0 }" e3
4
( h% W* M: n) W! |" Q' u5
5 o  g+ w. D& |$ Z' s9 p6
  V/ E7 k9 k$ C$ D" E7
7 ?, r2 |( a+ E, F5 E$ D8 z9 `8
) G! ]% q4 s( C# ?; Y0 ]  M3 N9
$ K; s* X" M7 \' ^& z10
3 B$ n, ~) B  c& l3 T) A2 i11
12
6 [& ^; F" \4 Q! E) |13
14
15
2 I) P% X# ^) F8 ]16
17
18
时间、空间复杂度
) Y; s# G& e" o- i8 h+ g5 m6 b



& ?* P: h3 e  E7 n9 W8 q. S5 n适用性：适用于顺序存储和链式存储的线性表。



- @9 y2 S5 E( O1 ~" }3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
8 Z1 W0 a* n# A! b堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。


( C) D# R- J, D6 u
即：
, F% U/ m" p. z1 ~, F6 B% m0 ^若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）
& Z1 y. S' [4 l" |; Y
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
5 s' W) O: L3 H, S思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

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

过程例子：

1 I0 ]8 A. _" r# z  }: ?

建⽴⼤根堆（代码）：



// 对初始序列建立大根堆
0 I/ ?( K* D- B$ b& Yvoid BuildMaxHeap(int A[], int len){
& f* F  E+ }5 G5 U- K/ j    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
' E/ N6 X3 Y/ Z( i- U        HeadAdjust(A, i, len);
}

// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
5 K+ S' b4 O8 T* @* M% T; y& p! M    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
' H9 z$ i/ |" d+ c; R+ c. M( k5 x            i++;
( `* c  k4 V/ M# _. [% r* w2 r2 f7 ^& H        if(A[0] >= A)
8 ?3 a7 j. z! [5 Y/ b  y            break;
        else{
* ^/ i  R* S/ @            A[k] = A;                        //将A调整至双亲结点上
/ ^/ U  ?. O( N3 m            k=i;                                        //修改k值，以便继续向下筛选
        }
# ^* ]/ m! y% m$ y/ z8 ?    }
" t4 l9 H6 o. O/ ~8 Q    A[k] = A[0]
& E6 A0 ]. O  |2 ~3 |+ z% V/ T}
) ?# h5 u0 i2 x8 K: [0 W1 r
# e6 c5 P1 C- a# ~1
9 q. @' K8 O" L0 c! [; `: {2
0 i6 h' c6 x0 E' V& K1 P; G! [3
4
5
+ E. X- [  N4 U5 ]! }/ I5 l6
7
$ C. h; v7 M$ _! ]3 \. s8
9
1 i. J5 c" e7 O) M10
. ?3 y: ^( Y, F8 @6 }1 F. v) a# W11
12
: I8 R: ?$ h% s: L13
2 \* P, ?4 Z6 X  u% h14
5 j% g4 a- ]5 {7 U# o6 _9 o15
16
& @; U/ x1 E& C' k# y17
18
19
8 `' P6 y, |4 P1 [* |" K5 v! b0 G20
21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
. Y3 c* z% o6 a% K5 J* L' w4 _; t选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
! o, L+ Y8 O# ^2 {& I
  [( h  f8 s; R5 b堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
; U9 v- S7 a0 u
过程：

" d9 h! w) r, P& Q2 ?$ p: h2 \// 交换a和b的值
  `# r- a8 g2 I( vvoid swap(int &a, int &b){
: x5 I6 `8 Q$ }) p$ G& u# ~    int temp = a;
    a = b;
    b = temp;
- d3 ]8 z( H, k8 O}
- Z  p* R% V& j3 N: H- i4 m
// 对长为len的数组A[]进行堆排序
% [, x* l; j; J1 R; |void HeapSort(int A[], int len){
        //初始建立大根堆
    BuildMaxHeap(A, len);                
; C+ v$ U" o/ o. C" {; }
, k  u+ c, I" v2 r2 O& X8 Y    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
" R- H5 E1 l; k3 t* }# C8 L    {             
        swap(A, A[1]);
% ~5 M9 S: g9 B2 d0 u4 r        HeadAdjust(A,1,i-1);
3 c* C& @2 L' m" R& H7 _7 B" b6 t    }
" S5 t1 c; ~6 g}

: H& |3 [$ p. M5 Y6 ?8 X( p1 {4 ?- o6 L1
3 Z, |8 k: n9 ]1 T5 l* Y2 Q2
. a  {4 `# E; B2 O; G/ E3
+ z2 t1 F1 H1 p; |; @; R4
5
6
7
: y4 e: B& y! ^( O& Y4 V0 E7 L4 Y" v3 u8
9
0 D7 [% H: S3 f& l+ `) @10
+ m* i  O: e: F4 p6 H! u' k11
12
% W' u8 Y$ j8 w" c/ {* X13
' ~6 E. i7 P$ s" r( Q14
3 L* C# ?0 y6 w15
16
' ~0 i0 J8 ]1 I) n3 x" ^+ P5 v/ U17
& N( i$ C" g+ v/ E0 q7 p18
1 E" _7 G! w7 [! c19
时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
  X4 v7 l- u5 S, h! }0 W/ K
空间复杂度 = O(1)

结论：堆排序是不稳定的
7 X2 c  S( _" g: E, j( l: J! m$ @4 l2 D

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

) e# U& t, h1 F' w& ]1 i: _, r
. F" M9 r6 A/ b/ R+ x( e
⑤ 补充：在堆中删除元素
: s, U7 j) r3 w( H被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
, {& D8 q9 D* V& y8 `
2 V5 A# X6 N( `6 X6 q3 _, A



4. （稳定）归并排序
$ h" A' p5 n8 b; W! C6 W' X( Z) \归并：把两个或多个已经有序的序列合并成⼀个

① 明白什么是“2路”归并？——就是“⼆合⼀”

多路归并：

6 |6 V- K5 Y: A2 ]! ?
+ D' \) Z4 I% ]0 |" d. J4 B② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

# \* K5 n; [4 w$ FB[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
- w8 h/ R& |* x+ o- i% H
) x, v* t" N6 L+ W③递归进行分治思想【MergeSort(int A[], int low, int high)】
) r( d; n& B; z/ o# U' M
9 T  M9 u; y! E; i
! E' I6 F$ r0 n5 L  I( V$ `0 k' O0 M④ 总实现代码
// 辅助数组B
' R* T4 x( Y9 r" K7 z! u( i: O9 Fint *B=(int *)malloc(n*sizeof(int));

7 U9 n9 S* p- \6 f9 Z( M6 g// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
& O! P1 U; l3 _- p" P3 D6 l    int i,j,k;
    for(k=low; k<=high; k++)
4 E7 H  \" @+ V) l( A4 A: x. S        B[k]=A[k];
    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
( W7 U' t. F2 \1 D  f        if(B<=B[j])
, |/ y+ g) V1 r) ~+ f; n: a            A[k]=B[i++];
1 s9 v  H. e; T* o3 m* N2 `! L: _1 k        else
) T$ H! U* _2 ^. W0 x$ b' B+ E            A[k]=B[j++];
" L: U+ f5 ~5 e$ Y0 Q; u    }
% I7 w. G/ _, q5 i3 L6 u" S2 t    while(i<=mid)
* f2 ]+ a' m' Q$ w# o        A[k++]=B[i++];
    while(j<=high)
7 F6 r" `2 c$ N' p9 B' T* @4 o9 C. p        A[k++]=B[j++];
; }, l0 ?% ?  c4 V, Q8 x( S}
+ ]. `: C1 x% }6 T

, b  p! Y3 B, n5 r2 i" \0 A" i% a// 递归操作（使用了分治法思想）
6 _- }- n0 }! w0 k4 H2 R& Mvoid MergeSort(int A[], int low, int high){
    if(low<high){
        int mid = (low+high)/2;
; M; U1 `5 d* ^# u4 |# A, f1 C+ o9 C% {5 y        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
' x" e: Q/ j4 N6 t7 L        Merge(A,low,mid,high);     //归并
    }
) ^2 ~5 M7 B4 o9 {}
  D! S4 ^: t+ E- Z6 P
- U! z1 U6 _8 o8 j' z. j: v1
9 W) |+ X& ?3 g3 ?6 a/ h2 W, u2
3
4
5
6
# Q! k' ~: T: n! h5 Z( K. O7 j7
8
9
: z' F3 {" l# g/ M2 Q! z10
11
12
0 W( {/ g/ f* A+ p" W  q& o& p13
14
9 q  k1 Z2 ^8 Z2 r- r: ~+ n15
, X* n5 i' ], j: `16
17
, l$ q4 g; F) r+ r* i18
! ~1 X0 z- H5 B4 `19
20
21
22
- ?# l6 t7 U6 H23
24
' m( C, A7 m( S+ o$ I25
; G" A& L- b/ }2 a$ X5 u26
27
" G" A5 ^* n- m28
) `$ e: ]$ V8 [: x% f( {3 T1 r; I29
30
3 G& }/ S/ G9 a) O/ P时间、空间复杂度


  ~* g& P) c3 p% q& b
* k5 D: R3 K% w" c! A
5. 基数排序
" x/ t. V9 S# ~! n0 K, D' _3 W/ y直接看课本的过程图来理解P352
4 \0 O$ L. x+ U4 S. S
再看这个例子：


* i  c" a4 ~4 o5 [) q算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
" o7 U, y- d% m- ?+ N3 r分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
( |& }7 h& m/ U) n  d9 O; e①数据元素的关键字可以方便地拆分为d组，且d较小。
* G0 h  n; I( H4 L. M) n" m②每组关键字的取值范围不大，即r较小。
- n6 \4 V1 @( ~  s, e) D③ 数据元素个数n较大。
2 F2 ]. Y) R( g8 y' s, D2 H* j算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
- }+ O! }& u8 J# m: Z+ H空间复杂度： O( r ) ，其中r为辅助队列数量。
稳定性：稳定。
% v& J5 |  F. v" |

内部排序算法总结
' l  A- n6 v% U: |
- G3 S5 ^1 r# a8 _! K3 Z————————————————
% y( [( d, c8 `; e% R版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
0 n$ J6 ^% r1 S1 B) D% Y7 v原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969


% h5 x& O$ x# b3 w4 \' g9 ~