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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
( G, n" h5 V. [: }+ s7 F文章目录
: n. `6 a. ^0 a. y. b: ]排序
1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
0 B% N. V( ~7 h3 U% Q* w时间、空间复杂度
3 v8 i& E# b: ]) ^# j# s& R) Z（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
8 @: Q* T9 G! v$ F# A% f1 f% l/ N（不稳定）1.3 希尔排序【多次直接插入排序】
时间、空间复杂度
' L* b2 c3 O1 k+ P2. 交换排序
2.1 (稳定）冒泡排序
/ X$ ]- ~9 Y( T% l& g2 {! T时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
. X  Y# l& t2 ~+ x7 K- C2 m3.选择排序
, C& ^& Q% U4 O- ~# q3.1 （不稳定）简单选择排序
( ~6 n% P- A. `' e1 Z" P* Z$ O时间、空间复杂度
- x: {+ i8 Q: ]8 m1 H3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
3 c% B3 r# F& d- }1 g7 P时间、空间复杂度
④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
" n+ T& {, V% O+ m0 d7 S② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
3 l) s' T* o7 _. \/ H5 H  q. e③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
: E1 \, E$ y' K/ _时间、空间复杂度
8 F4 _% m! g6 x5. 基数排序
内部排序算法总结
8 i1 C$ {& F8 l1 T' H% k排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
& J0 B- J- F7 f! I( T1 A# Q! V
排序算法的评价指标：时间复杂度、空间复杂度、稳定性。

算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
3 H+ y( O! F8 D, c; D稳定的排序算法不一定比不稳定的排序算法要好。
9 _# ^; n( X7 W& f8 v, w: G

排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

9 s, x( i: K$ c6 D3 J3 \. d6 G各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
2 O( `. `! m2 E3 S% O: j
$ F+ B$ o& `/ ]$ A& t4 U7 w

1. 插⼊排序
- N2 M" O) o7 ~（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
( m. `  h! v7 V9 g! J+ Z1 C
算法解释：（从小到大）


5 ]$ v# R: O4 @" ]* R7 K, F$ B7 U8 g. T算法三个步骤：
$ `9 W7 E3 b. q
2 P  x1 b0 J* h% |7 u" w) ^先保留要插入的数字
/ p0 \' C( n# Z往后移
插入元素
; o1 ^* K9 s4 u1 Y+ l  _
2 E* z7 T) l6 ]" m# @. t: r, X// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
; v4 K+ T. v& t& k" A# L    for(i=1; i<n; i++)
0 x' k8 w3 H+ A! y7 N# x# C0 T- `1 V    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
) g3 R4 {0 X  i) }* Z6 u1 P        if(A<A[i-1])
        {           
* x0 G( E/ u2 X% Q            temp=A;  //保留要插入的数字
4 W6 q" V; a$ ?  ]& U/ s* \
            for(j=i-1; j>=0 && A[j]>temp; --j)
5 ?+ C7 h' A+ ~. [9 u                A[j+1]=A[j];    //所有大于temp的元素都向后挪
* _7 v4 m2 `6 M+ k9 u
1 O& W8 Y3 Y+ M. {  @) @8 W0 G            A[j+1]=temp;//插入元素
( P; y  {" }0 P3 R$ Y        }
    }
# b- _6 Z* Q3 S}

/ v& E8 r. P. Y& }8 B8 e1
7 t, B3 {: A& }8 s# f5 ]; Q2
3
4
5
6
7
8
9
10
11
12
13
; ?4 e8 F, u: @' a$ ]' m14
/ y9 e& z' w) Y' j, ?$ {; |, w15
16
% [- F. v" I0 ?5 o17
用算法再带入这个例子，进行加深理解
2 V2 ^: W+ U2 V* K- v

2 u; K0 k  e# m' w" I0 ~带哨兵：
( I, T$ j) ^: \1 w, c% z

( k4 ^  K2 P# N# b' X& h2 o" k补充：对链表L进行插入排序

2 @& F6 s; ?0 C1 v& o6 `void InsertSort(LinkList &L){
    LNode *p=L->next, *pre;
& G- L: F% S( z( r7 p' a7 z! y" R    LNode *r=p->next;
2 O2 f. i; h8 W, t. x1 f: p8 v    p->next=NULL;
( C* W8 a- X2 u0 P$ B5 L  R    p=r;
    while(p!=NULL){
        r=p->next;
4 B( A1 w( j5 w+ C' [; T' l        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
& h: J  T/ s: m            pre=pre->next;
        p->next=pre->next;
9 C* Y9 r7 @# s4 G        pre->next=p;
        p=r;
    }
}
+ u+ f" e9 f% }3 \+ F1
2
, e3 |& f* o3 F: N; Y; f* T3
' r; B, b/ W+ Q9 Q( O# \4
5
6
7
5 B. e, D# {$ Z& o4 j! `$ O8
9
( Y- O5 ^; W/ Z! |0 y( Q- d10
' K1 D0 p" `4 R. A+ ?( ~11
12
, l% T6 Z+ a1 V13
14
8 G" G& s/ {6 W( B15
时间、空间复杂度

& H3 H9 z+ f+ _  P  B
( `, K+ C) ?. ^& D3 j5 R  u最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
6 a" g: s& D+ }* G) w最好时间复杂度—— O(n)

最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
0 V0 U& K8 M2 j& P4 Q第2趟：对⽐关键字3次，移动元素4次
0 |4 U$ s' _$ Z" h…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
# J& M$ j. s7 m. Q% f& ?: E5 C8 ~最坏时间复杂度——O(n2)
. }: m; u, V" M& `


0 |4 e! q+ O1 w4 T6 ]6 g& n5 N3 w/ H

（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：

2 S; D( r* P- I9 ]
1 U) z+ O/ _2 v, U6 k9 [3 \
: m, ]: a# b; z, T* P//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
{
' @+ l  ]% `# a# R" h0 Y% A5 j# A    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
. T" L2 F# u  q6 g5 ^    {
% n' L. B7 V# \- m9 Q1 r        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
+ t+ V( X- e4 S! k        low=1; high=i-1;
$ K. F( \* d! e5 ?- H! [" V        while(low<=high){            
" [- t# X0 T' f            mid=(low+high)/2;
' V0 N9 e# F/ H; V            if(A[mid]>A[0])
                high=mid-1;
1 T8 m6 p# `# S1 h% V& @( F            else
                low=mid+1;
        }
         //--------------------------------------------
2 Y$ c: G7 M1 C5 Q        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];
) M2 P$ T9 J5 n! {3 @- u8 [1 x; n
        A[high+1]=A[0];//插入
6 G# i. ~3 Q9 f% a% c    }
8 |( Q2 S& h3 f3 v$ t+ `" u}

% `) v+ E# D& ^7 v1
2
3
4
* ~0 T8 {8 ~4 c5
6
! A- Q% G8 ^  Q" L7 g! X7
: r" z( _1 r+ x& Y8
9
- J( ?/ R) _/ x3 W10
11
! ]2 M1 Q7 ?) ]6 u& [. `7 ?12
13
14
" M. O5 B, q$ E, l, N15
9 \; S& I* P9 r3 g" ^3 D2 H16
* X+ |( z5 f& e# R# V# W17
18
19
# E. a/ M* {; [1 h0 |7 T2 d, _( P20
* o- ?# s4 Z$ A! W21
( T7 J' y0 u: @2 N22
+ m1 ?- C: i# ]  U23
( T8 n+ j% x0 b# G9 O时间、空间复杂度
空间复杂度：O(1)

( Y, P9 j, b3 I8 J$ L  P3 m1 `$ B【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
0 p* N% ?1 g3 a( G1 E- y
& _2 X6 O# q/ v* w3 v  b
( o$ a! f$ j# n$ j4 `% {（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

0 T1 j! j7 @& d2 L& B$ e  x, ^; o* f算法思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
$ p/ R, L' E$ k# J图解：


% ^; l, \( {9 B  v) C( ?
代码实现：
( u# B/ X1 w0 C6 s/ ]
//从小到大
void shellSort(int* arr, int n)
  ^; k- u* ~7 U+ U* M2 B, r{
        int gap, i, j, temp;
' m, }  z5 C3 g/ z. U  Q2 R" C        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
" H7 K. F" a% Y1 U8 W! [8 A0 }9 H        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
2 m) P1 H7 L8 X2 C4 a  }( d                if (arr < arr[i - gap])
# \9 g& M7 T0 H4 d& J& f% M                {
. s" m) M- f8 A  N- N! i3 C                    temp = arr;
/ V# t1 J2 X. n: c* a
7 O1 ?  B! |% R) F+ L% o                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];
4 m3 z* l3 l& D, t0 G
4 Q( u" e/ h# [) l9 r, |/ m8 b                    arr[j + gap] = temp;//插入进去
                }
            }
9 e/ j: a3 L6 f9 m: `3 ~2 M            //************************************************************************************
        }
7 a9 A! b% A& O6 C* w}
" H1 W% B2 K* O) \1 o/ @
  [. c6 _7 e8 V. u, A$ f1
1 [) s% c/ g. X- r4 P5 R$ p2
3
4
5
+ n! G# V5 _5 G2 X: d5 [" b9 `# h6
6 k. ~- r* ?6 F# S5 d7
8
- D* C% ~0 P7 ^6 `9
10
2 B0 S: W9 \# v$ E7 c% \7 J11
12
13
14
15
/ e: u# Y$ _3 o  X/ `! c16
17
2 l! G/ I) V5 l8 A/ R' c18
19
0 R* b( C: ^! z' U4 a8 }: x  B  t20
21
22
23
24
时间、空间复杂度
空间复杂度：O(1)

时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
5 ~, P( `: H" \" v/ Y
稳定性：不稳定！
8 P7 A, j% K3 f0 m: M  e, E

) l9 K8 ~+ l+ o1 r2 w- T
适⽤性：仅适⽤于顺序表，不适⽤于链表

0 ^* o% p" h# Q1 ]. Q3 D/ z/ r
' z% Q# p, t% X( z: e2 h
, n( P4 t0 K! {$ P; }$ G1 m2. 交换排序
- {  x) @, m0 G$ O' E9 x2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
: D. u3 [0 u4 T( a
6 U2 x: ]* P1 V- @! }: s1 l每一轮比较会让一个最大数字沉底或者一个最小数字上浮
2 m+ z& K2 I# O0 \3 C  `
7 D( P3 |, j2 L' `0 b这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

7 b8 \/ o% v/ D* ?" u1 D实现代码：

//从小到大：
, ^- Z. X1 g9 U. A  Nvoid bubble_sort(int arr[], int len)//冒泡排序int*arr
{
        int temp;
3 C% F4 T- Z7 H9 M        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)//相对于上面的一个优化
                {
& P0 B9 @; S* Z                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
1 W( N% l6 _: g  D8 i' g                        {
) _7 C& t. M5 v; A                                //交换两个元素位置
                                temp = arr[j];
) f) d$ N) b- [# F# E% d, V& Y9 s                                arr[j] = arr[j + 1];
) [. C5 D9 M6 X. e. U/ H- \$ x                                arr[j + 1] = temp;
% ^5 L& S# a+ L6 K) n2 E! n/ [7 `                        }
                }
        }
& i; I  f& Z& B8 z}
# y5 ~; i8 g6 r; F' A6 j4 j, @
1
2
' P) o! b' {9 N3
4
8 B% p# p6 w1 J$ f+ v9 g5
6
7
& s9 J& K* r3 r9 [% S8
9
8 z% ]" X+ Q" J10
3 D+ W2 t3 Y! V6 L2 {6 X, d% {11
& S2 g  T1 ~& P1 L3 g& C4 _4 V12
13
( ?; Y$ h. T& p: C14
* _( ?8 ^0 P! z& T& X! B( }15
1 o" w* B4 e/ Z1 p16
$ ~' A3 B! \1 D7 T0 r& T17
' f9 G* b' k/ J* D7 y18
( y" ?0 M6 B- V, D6 D& w19
9 B' s" E9 k7 q& ^: l8 E; k6 y7 `6 }' J优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

//从小到大：
. X" J, m) k$ m# ~9 }9 ^+ rvoid bubble_sort(int arr[], int len)
{
% u! ?& \% o' b" O7 Y, R; H1 D' Q& k        int temp;
# @; u& S0 k- |) V        bool flag;
        for (int i = 0; i < len - 1; ++i)
* |1 T! Y% T8 ~3 J. a6 i6 ?        {
            //表示本趟冒泡是否发生交换的标志
                flag=false;
               
# I* B% I: ]- k% O& x                for (int j = 0; j < len - 1 - i; ++j)
                {
                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
                                temp = arr[j];
# H# U5 V  w4 ~6 E                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
; E: B8 N, B% r: p) C- J                                //有发生交换
; v! C" c9 c* z. i& G                                flag=true;
+ R8 c! q* s3 o4 r* g. U: L                        }
                }//for
. @. |' E/ t: k: j$ V( [% ^( Q               
3 v* p1 C/ J5 X0 N, w2 h) |                //本趟遍历后没有发生交换，说明表已经有序
                if(flag==false)return;【1】
5 Z  a) V& w- Y3 J/ \9 D9 k- t        }//for
}
4 Q# S* c" ?4 R8 o
, }' \( L2 x% Z9 i: M3 P. f1
4 L$ q1 b; v* g; a3 s6 V/ \2
3
4
5
- u5 u. g) _, g3 w& \- _6
. s# D5 A+ J5 j/ H" |" n2 j2 z2 ?& l7
8
4 c: ?6 @* A+ U9
% x/ {# T: @& n! A2 w9 t4 I1 h10
11
9 p5 ]6 @8 S% D, R; G8 D4 U12
13
14
15
16
5 i) R6 Y# w. u* d+ t17
$ k+ b! [; c1 s  X- [  ^18
19
. r1 N2 g  P* A% ^20
9 n/ I* o2 d1 w* W3 T21
22
23
24
25
6 E/ P& m, k# k5 s# n26
/ J7 A7 D3 z  b: ]$ `; V9 P7 m% b时间、空间复杂度
6 k! y/ H# S% K7 @2 \+ W6 C
: Z, |( Y3 ^1 S2 c5 w: H2 @5 J& c适用性：冒泡排序可以用于顺序表、链表

" Z, O  Z5 v/ ?$ p4 S# B4 `


  s4 ]; R' C7 k* w2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
$ e  Z" {( H# p: U! |0 E在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
' W* \  P/ T7 J- Y' ?1 w) }通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
% d" f# V$ _: V. i; a使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
; [4 n& y! T* X& ]9 h# C/ W
' h" y0 e9 y( ^0 [* ?- B/ P& D然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

划分的过程：
/ y; v' T. v3 _2 B
1 w% g) o0 B/ N1 U% g初始状态：取首元素为pivot，定义low，high指针
3 l1 r4 K2 u- l, ?1 o
首元素为49
high指针指向的数据小于49，就放在low指向的位置
$ e; A8 _: m5 N' s' z) Slow指针指向的数据大于49，就放在high指向的位置

6 ?( w8 d+ h8 r
' L& m5 u. `7 i' O6 h0 _4 ?


( D+ d* S4 h% R2 C$ p/ c0 r* A// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
5 @1 ^0 L; B/ c' w        //取首元素为pivot
    int pivot = A[low];

    while(low<high)
    {
2 u" N2 I& t& q$ v, k            //先是high开始向左移动
+ E9 i& b- z0 |9 y, z8 r$ K& [        while(low<high && A[high]>=pivot)
            --high;
        A[low] = A[high];
: Y  X; G  e, M' }
6 O. P6 w- u/ m% I4 V        //随后low向右移动
; v5 M# w1 o) X6 D' H        while(low<high && A[low]<=pivot)
! v/ x$ {  S! v  {* K            ++low;
% Q) z2 Q# O9 Q: y        A[high] = A[low];
    }
$ h# e- J0 w% {. ?: q: f
5 O% L5 w* Y  w0 V+ A3 t    //low=high的位置，即pivot放在的位置
1 x5 ~* |. k1 h0 Z. g    A[low] = pivot;
# |: b: L8 m6 j* z
    return low;
9 f$ N, Z) y+ S+ C}
+ X" p' m: w! M5 W/ G
// 对A[]数组的low到high进行快速排序
  f6 E9 r0 v4 x3 [& r' Ovoid QuickSort(int A[], int low, int high){
" e0 J; T0 F8 L# E. `5 t% {1 L    if(low<high){
        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
    }
% u; b4 r" v" T. a6 H}
0 p" u& G' q7 \& M
2 X2 t) {7 y9 R0 O3 r# Y5 U! I1
2
3
4
6 E; D$ v+ h# x( r5
6
  e( h* u' ?% d% b: m* Q7
! _5 g7 H' M1 J0 [6 j9 }8
9
% d& t2 i8 S3 s10
11
12
; z( J0 g3 T/ ?9 Q, l0 f; ^13
14
+ }  O. y5 k9 u" a9 x15
16
17
% o4 V( t5 z; X& T& m' o18
19
20
21
0 u& g: U/ `. j" d22
+ p$ T9 t4 m* ^4 h23
24
25
2 E6 B# T; E+ u6 h7 N+ D8 L7 {26
27
28
29
30
31
32
4 o% b, a6 n: x时间、空间复杂度

( ?, ?. e" e' \& E, S' q
8 n8 D& h  c1 Y6 a9 Z  k* Q把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
; b7 |  l' o5 S
  t* {- Y) x# |% g/ gn个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

6 S4 B  a! w' P( r9 ?' e- ]. D时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
4 ~& Y" h$ _8 v6 ~2 ?; G- `3 m最坏时间复杂度=O(n2)
3 R" Y9 r+ C7 O! W平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

/ R" f9 `$ }% R! ^空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
5 X$ z6 }4 i6 N# X* V最坏空间复杂度=O(n)
0 p% g! E$ e! ^, n. t" C
最坏的情况
6 d8 C* Y/ R9 _+ m


8 s7 H5 k6 k8 w; o( C4 d⽐较好的情况
# c- ]+ A4 m; F/ P# r2 C
% J( h: q8 C* ^6 m7 `) {2 \: i
: z- ~) a" E- O, Q$ ^4 S& K' [# g* @" F
不稳定的原因：
/ ^. E" p1 k+ R) [1 G; }  \
( |$ Q* e7 r+ l6 Z% I5 |
  d, ^# S2 g5 g4 g) e7 K; J
3 z+ O# `* A9 f4 n5 C. a+ {
( q5 R/ B$ {& ^
& ]. Q) K& U: q# }2 N8 ]3 }3.选择排序
) z! K5 L& d. z选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

: @* A) l2 L! y3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置



// 交换a和b的值
0 e, z+ O, w" D7 C* u1 xvoid swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

// 对A[]数组共n个元素进行选择排序
' V  R; ~( |* [5 l- k$ @void SelectSort(int A[], int n)
{
        //一共进行n-1趟，i指向待排序序列中第一个元素
% l+ C  m1 {. l8 w2 \' Z& F    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;
        }
* Y9 A+ M: w, W  q        if(min!=i)                     
' R. i* B, P  l8 }$ s; A/ V, d            swap(A, A[min]);
    }
( F  H( e$ {$ d, j& u* s}

1
2
" S: A8 n% L( p; ^7 ~& v0 n4 J) b3
0 x0 V4 W7 x2 b$ t2 [) @4
) I: w3 b* o- D9 M, g0 h! M0 B5
( `5 Z" ]  L* d% N$ d6
; [  S" I7 w* [( h8 ]6 L% F* ]4 I5 u7
8
; O4 b, c, I7 b. m9 P. V1 X- @% {# t9
# u$ s5 ?) e/ q2 O0 w+ C10
11
12
13
14
15
16
17
18
19
( \+ l2 N9 a; m) y# ^. Y20
, ~6 N2 y# g0 J% G21
22
补充：对链表进行简单选择排序
. }/ ?! Q  U4 v5 E5 F- \
void selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
    while(h!=NULL){
        p=s=h; q=r=NULL;
        while(p!=NULL){
4 F0 z, f# F: J            if(p->data>s->data){
                s=p; r=q;
            }
            q=p; p=p->next;
( I5 \3 r/ m8 Q% e5 n6 z        }
: W1 z* W$ w( |" T( k% B: e1 \        if(s==h)
            h=h->next;
        else
            r->next=s->next;
        s->next=L; L=s;
  O; u! t! T% K& n5 d* @    }
}
% H- A$ d! L$ l# G
1
2
3
# k/ \) z& ^. U4
5
% `5 s  s  z' E6 }6
7
0 u" c' j: t; {4 N% n+ i# F8
9
- K7 a# W( ^& E2 q6 L- P10
" b1 t* w3 I1 x( D% b# M* r: m11
6 `2 Z& I! A5 b, J4 p$ Y% [12
13
; f5 ^! \3 O. s14
15
16
9 ~# }0 q, F. e% l1 {17
18
+ O* f, }# Q; V7 }7 g" R' Z  o4 k3 v时间、空间复杂度

5 h8 [$ k8 M" e5 _
  }7 f2 @; I- O' }( c
) V3 X. E, y- ^4 j; l  Y9 H
适用性：适用于顺序存储和链式存储的线性表。



' j. v9 i$ C( ]3.2 （不稳定）堆排序
, a, d: P8 K3 D1 [① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
3 ^5 ]0 c" }+ l8 t  K) [, L# e每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
- e. `% m$ ]6 T( E2 H) D, P
! [% J1 A. F1 b5 ~& f

即：
若满⾜：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）—— ⼩根堆（⼩顶堆）

; k! t0 d8 O2 w6 X* y% t! K② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
3 Q' Y5 i& @0 t( ]思路：
2 x" d& b" X+ W4 i把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
" d% E! C! f6 F0 W6 f: I( |2 x2 K8 T6 h
在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
/ _% p' f4 \- u# b0 c; V# q: ^
7 J1 M) g6 z, a检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

9 U7 e8 h' ]) o6 N过程例子：

. U/ M0 s" X/ }  Q1 Z* g

建⽴⼤根堆（代码）：



8 h6 z6 t8 S. z3 u8 V. Z& Z// 对初始序列建立大根堆
, N$ x6 W* n$ s4 U4 l5 v5 jvoid BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
}

// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
- F  Q' r, _$ f' y/ w    A[0] = A[k];
7 |( |$ \: ]7 t7 ~5 D& c    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
/ G9 v- }/ N5 |& N        if(i<len && A<A[i+1])       
2 I1 H6 h. Q9 T- _7 c3 {            i++;
        if(A[0] >= A)
            break;
) e/ }( I! ]6 {+ T1 o0 p        else{
0 f3 n  b9 d& c6 t            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
2 I, m/ b! T3 V        }
1 \3 k% `, c  L( Z; o6 t    }
$ E* b- I8 ~% r. Y6 h    A[k] = A[0]
}
3 K1 O+ x% s  ~: R
6 u$ E5 I4 S8 T1
; {, Y* F* n" G% x3 C2
3
4
3 x1 b* `; ~, A( Z5
6
7
8
" a* W- i: Z0 H- \! p! x/ v9
10
% S( R: ], H8 W. V* v5 E( y11
  a/ _: Z' I3 B6 i12
13
' S3 E4 r/ P6 G# C3 R6 p14
: o% w% n7 |0 j4 {15
! V0 t6 n' H) j9 F5 N( {16
4 T; {8 B; ^6 q17
18
19
' x8 F4 j: a: H3 B. S1 O1 m20
21
2 b7 H) W+ y7 [, c# z' L8 ?) L③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
3 A4 t! S. a2 ^3 l/ ]! _3 J选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
3 a& w- K% Y8 K. g+ j1 L
4 G& l8 f: `, ^# F1 m+ ?) u4 X7 I堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
9 J! W  R! J% Y- d% |
过程：
( S/ t3 y6 }3 K8 D- n
// 交换a和b的值
# ^& [) Z: ~3 x* u9 z" E) U9 bvoid swap(int &a, int &b){
! f" X6 r' V( X; b$ ]8 t    int temp = a;
( G( ~  Y1 m1 E, Y6 i    a = b;
    b = temp;
! Q* r) M0 t$ i}

( X, v$ b, J3 a// 对长为len的数组A[]进行堆排序
6 B$ `7 \: T. Jvoid HeapSort(int A[], int len){
        //初始建立大根堆
    BuildMaxHeap(A, len);                
! s- h3 z2 u! Y6 j
' d* G; i; {( q4 r7 B    //n-1趟的交换和建堆过程
8 y8 o0 r* m, |9 b    for(int i=len; i>1; i--)
9 _1 }+ w2 g0 i) i    {             
. C$ t& J# {2 ~) b        swap(A, A[1]);
% e/ `7 ?2 i# ]  q; G        HeadAdjust(A,1,i-1);
9 n( e( A& z7 N3 j    }
+ P1 ?4 R" a7 I4 [- J7 W; W}

7 P* s& X$ G1 }% f3 l; Q9 ?1
$ f- q- `' y7 J' K5 c2 Z2
3
  t6 I& K; Q1 o4 J4
5
6
7
8
9
- N% R. z5 c( v. f! a) Y6 j10
$ M. i+ L* T% t11
12
13
14
- U# M: |: F/ m9 E" t15
16
3 x1 `1 t( u" P* ~, ?17
18
19
时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
% X9 H! {, n$ x6 D1 O
3 c- l& u" A6 v* O$ P6 n; v3 U空间复杂度 = O(1)

结论：堆排序是不稳定的
, Z% b) {8 O- I; ~8 q
% y3 P' z  v) ^. C% l. @1 N( i
" u5 o! K1 u/ L8 P④ 补充：在堆中插⼊新元素
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌
! P' e: W8 I3 Q7 t, X5 D$ e


⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
, q# j- ]+ v# V' e0 x! y8 _
& p( a& f8 C1 b1 V


, F0 w; B! [: n3 @+ X
4. （稳定）归并排序
& a  ^* h+ b$ P3 s归并：把两个或多个已经有序的序列合并成⼀个

① 明白什么是“2路”归并？——就是“⼆合⼀”
, t$ e: W1 i- d  b5 T
- u6 p, ^7 f% I/ e; Z2 D+ E& Z多路归并：

3 \, R" n+ G  H9 d  J
6 W. s0 I( }/ l2 M& i② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
: S( x! H( `8 z$ T3 o: P/ H
③递归进行分治思想【MergeSort(int A[], int low, int high)】
3 \, ]% ~5 z9 i# G

9 @2 {0 j. \! G! y: o8 p: I④ 总实现代码
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));

// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
7 d, y, Z' ?* }" J: y9 Kvoid Merge(int A[], int low, int mid, int high){
' Y$ d1 d) N: f( A' W; r5 v8 Y    int i,j,k;
    for(k=low; k<=high; k++)
2 A0 S& C1 n# F        B[k]=A[k];
8 H4 E% L( l/ Q    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
- r. z& {/ i% p9 q0 N2 O; i% z        if(B<=B[j])
3 r8 ]  e* J& C- R            A[k]=B[i++];
6 @* W) G' S1 @% I1 L8 `( j        else
/ K, O6 t5 t! V- _            A[k]=B[j++];
    }
    while(i<=mid)
5 x& P3 @0 e, T2 `        A[k++]=B[i++];
" J1 s. P) a0 m; b$ t    while(j<=high)
) [! u8 b- H4 @9 z- L4 \( s        A[k++]=B[j++];
. @% f+ h  `( @}
$ c* ?% X- ~9 Z6 h( b. _
- J9 V2 ^$ V1 I! }
// 递归操作（使用了分治法思想）
void MergeSort(int A[], int low, int high){
# h! P& T6 j$ \/ V    if(low<high){
        int mid = (low+high)/2;
& X" G4 i  }6 O+ d& e& U( ?        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
    }
( }* w) b* U1 j$ W+ r) c# O) S1 s4 O}
$ G6 i8 Q0 C  K9 F1 l, Y$ \: r! d
1
2
- F2 w& d0 o, X1 D3
4
5
$ F  P, d. }/ W" K6
! P: A1 B; U% e+ ~. h, R: k' S7
& U$ @- \0 U: K5 n' r4 i# c+ f8
5 w1 ?& G, m! p' h! N: m9
2 r4 a  g0 J. {# s+ o3 O4 I  a10
- L( n) e3 P' x11
$ n2 ~$ e# h6 r$ }12
13
% h/ u2 {; a5 o* E  Y2 K14
15
, H+ \- Y+ @' y& @! b" X; Z& r16
17
! r/ W8 S, \% U+ \3 A18
19
20
21
22
23
24
25
5 ]3 K# o, Y8 e2 M3 \  ?1 ]" ~% ^26
6 I0 y* p4 o# E/ h8 S4 B* V27
28
29
30
时间、空间复杂度
  I% ^* y5 V; c; t) I; U
6 h% o# ]; p% ^. e9 S" a1 X


5. 基数排序
# M& b  I; f. q/ e直接看课本的过程图来理解P352
7 S6 q9 r7 v8 w/ h* Z  e
' }3 j* k4 M/ z2 j再看这个例子：
, V- l: ]8 ?: L2 i9 \+ S

算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
4 k8 b' g" f) E: o/ W" ?% C( X/ F收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
. C6 w4 w, ~, p①数据元素的关键字可以方便地拆分为d组，且d较小。
9 W: ^( @3 ~, a- ^: V2 ]+ g; ]  P# c②每组关键字的取值范围不大，即r较小。
# ?9 k! c' ^+ L# B* M9 b③ 数据元素个数n较大。
3 }8 H1 P/ ^2 G1 v算法效率分析：
- {  J1 w+ W' J0 o1 q. x4 n$ _时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
稳定性：稳定。


$ F. P; F, d# ^9 G6 y, W内部排序算法总结

& z4 y8 s, ?% l7 x7 \% i————————————————
2 q, N5 _7 f2 [8 \+ S4 A版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969


, e6 Y. h; P- P7 A; }+ y" f- d