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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
: L, ~+ `( W0 r$ \文章目录
排序
1. 插⼊排序
2 k! I. L3 G8 M6 U4 `  f$ i9 x+ f（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
3 f. b$ Z5 @) O时间、空间复杂度
4 l6 H, ^) T* e4 h# ^2 b: [（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
时间、空间复杂度
& c( f  M8 O- k6 h4 J# V. b2. 交换排序
2.1 (稳定）冒泡排序
( G$ G1 }! B: t- h6 A$ s时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
3.选择排序
" u, J9 v$ Q* |! h; t7 e3.1 （不稳定）简单选择排序
3 r0 r, v1 b7 K' N0 G- e6 C% S时间、空间复杂度
3.2 （不稳定）堆排序
) X/ @# F+ g7 A2 V0 `: V" p① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
④ 补充：在堆中插⼊新元素
4 C! p  W" |1 s* Z9 K0 S# d" D⑤ 补充：在堆中删除元素
; X- m9 C1 C1 ^1 ~3 B4. （稳定）归并排序
! M, D# N/ ~! ^% l$ z① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
时间、空间复杂度
& O! q, V8 L2 v1 H" a8 Z5. 基数排序
' [& F; L+ C' U" E! L内部排序算法总结
: A& O' X( J. _) J排序
* _' }" g+ @3 d1 u/ `0 k排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

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

, M# T4 d  l2 N6 A2 t$ T算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。


0 g0 Y' {" }" V0 {5 J& e排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
& e# W7 m/ i0 _  f5 W
  f8 @' q+ r# d4 |! j( F各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
' l6 k1 A5 b) |3 @
. }1 a# j# V2 I2 p, P0 ]. }2 L
4 T8 t) y2 Z* V
" L% R6 A% A) B( i9 G1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

算法解释：（从小到大）


1 q8 I4 @- Z, [' U$ ~4 j$ C3 X算法三个步骤：

  n3 m7 t" A* n- L/ \, U先保留要插入的数字
- w- q0 g' r' i! i往后移
插入元素

// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1; i<n; i++)
! E  Z! x1 B2 r4 y    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
4 \% }5 S" B' s- Z        if(A<A[i-1])
  C4 N5 O4 ]/ z4 Q6 ?        {           
            temp=A;  //保留要插入的数字

            for(j=i-1; j>=0 && A[j]>temp; --j)
  x: f! B; G9 V  g                A[j+1]=A[j];    //所有大于temp的元素都向后挪
; f# a3 v: Q% x: Y! {6 t! n& l1 A
            A[j+1]=temp;//插入元素
        }
% b7 x/ Y+ S3 E# T9 n1 F& O( ~    }
- h6 `' }( K7 O2 q* U  A! M) d  I}
' o9 C4 F! g+ {
. r7 p, `3 G& a8 p1
2
3 ]# R8 A, m, \) ~# u3
3 n# @9 Y9 U3 z: r9 s) X: D8 N4
9 e1 D0 ~; ?! S7 m+ Y% O- [5
/ h0 o- e( \/ I% v3 `+ {1 c& }, X6
7
* b# Y' p6 a/ b! v3 r. I8
( O2 c# ]& i; C9
10
* @4 O5 q1 e# i0 J2 Q11
% a. ?9 D. ?# i12
1 A' q& I1 C3 ~- e% j13
0 ^% A! a* f+ j0 {14
- G& E5 f+ N  _- {5 W6 u- q15
! U" z! m; Y5 u3 T$ a16
4 V$ k' Z; l; g17
用算法再带入这个例子，进行加深理解


带哨兵：

7 I! y- }, s& r" z+ X) x
" Z5 P( h& s& V2 n( [" x/ @补充：对链表L进行插入排序
9 q% [7 i: R; P: Y0 _* n. f
void InsertSort(LinkList &L){
    LNode *p=L->next, *pre;
' n3 E' s6 }- ~: A4 o- v    LNode *r=p->next;
    p->next=NULL;
    p=r;
    while(p!=NULL){
' ^$ h! V- T6 a) u' Q        r=p->next;
3 }  a) u1 ^( `' w4 z9 ^; L        pre=L;
) e# E/ L: H! [; f, G; H/ u8 h        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
; @' {1 `$ ]8 P! b* }+ K2 A        p->next=pre->next;
$ h6 c' ]! X% c7 l0 ^        pre->next=p;
        p=r;
' _7 e/ O& M9 Q& _0 {( ^9 r" s" P    }
}
1
2
* e, y1 O1 u, I3
4
; h  j* W; g. S! V& }. B5
6
7
) {; g2 D: N# H) o1 \4 L2 p9 E; _8
% d% X, T! w+ G7 V' J* t$ |+ |- e1 H1 `9
+ ]# p7 T1 {1 q9 g, V10
11
- b, O  S) H3 E& H12
$ F+ v: R$ Q/ Q& U13
: l+ O% K' S/ X. [4 R, k14
. S* H" B( O/ x5 a' x, Y6 V) k: `15
* R6 M/ X* m% F- @# s时间、空间复杂度
, b6 I+ k2 |  S1 c) Y" C( b+ v% p1 \

5 o4 y4 ^* ^6 a! G. j; v4 c. }) X最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
最好时间复杂度—— O(n)

  ?+ k2 [$ k' q3 e最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
; S  ?: r# l) T9 F4 c; x. e第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)
; z% ]  ?. o1 r; T
  F1 Q" v& p( w% p- E. R

6 a1 n/ M( h! |' X4 H* O" ]! ^
( q4 R. m" n5 [+ T  m
7 ~4 G; \1 w, s（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
( p# r$ `* X* `" }( X' t过程：

: J9 T6 d$ }/ u0 b

//对A[]数组中共n个元素进行折半插入排序
% p; i6 ?4 {0 X# Y7 Z( dvoid InsertSort(int A[], int n)
{
    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
    {
        A[0]=A; //存到A[0]
' D" t3 D8 a- }! y* y        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
        while(low<=high){            
            mid=(low+high)/2;
            if(A[mid]>A[0])
                high=mid-1;
  E" J/ `$ @$ q; g            else
- R% ~4 d/ b1 {/ Y                low=mid+1;
        }
& y9 U/ }' v! }9 e# w         //--------------------------------------------
) k" u4 Y5 H$ m; b9 A2 S  L        for(j=i-1; j>high+1; --j)//右移
6 \: |- A8 b$ z; b9 @* R0 c; |* w7 ?            A[j+1]=A[j];

        A[high+1]=A[0];//插入
    }
* D$ J7 ~5 \) G0 N: o0 ^}

1 l5 Q0 ]5 F# N1
2
3
2 @2 s0 p2 W+ T2 p: P, A; v4
# ?  q+ Q$ v. b. d+ x, V5
6
' N1 B1 o) p6 F/ N$ H- s7
8
9
10
. E9 @4 x9 k  P  c$ F11
12
) a" r3 y" e5 N- R9 o) y13
0 i2 ?# M& t: f8 p2 {0 W14
15
  c" F) P8 j, }8 l7 H. a3 K4 P! `16
! o& U/ X- y' ^7 l/ Z8 _17
18
0 K, a4 E& k; _, w1 F% P  L" D19
20
  }  i( I5 N) i  [' B21
3 j5 x+ z2 f+ j6 w22
( C5 D$ l2 F2 N% Q8 g23
时间、空间复杂度
空间复杂度：O(1)

【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)

& X& [) P" I5 x+ v7 f6 p9 T
（不稳定）1.3 希尔排序【多次直接插入排序】
+ L- A: q+ S& m1 [7 P是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

! z+ |3 {3 \) N( j* T  H算法思想
8 x" I: c7 A- W, P; Z
8 o) Z2 T2 g1 D6 }/ x希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：

9 e. U# @, l; k( r2 r+ X: ?

, m6 W; o4 G/ k4 r" R- E4 P3 P% r. [代码实现：

* q& j/ T0 u& K! m8 D9 n//从小到大
void shellSort(int* arr, int n)
{
        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
8 `  S" b6 W& U. [        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
; l' ^! `! X# I1 C, J            //**********************************直接插入排序（只是步长改变）**************************************************
( V6 m& x. v3 I" a7 u& S: Q            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
" M( |) }1 @) ?/ U( }' `' }            {
                if (arr < arr[i - gap])
6 V# A0 Y+ ]0 k. ]; g' g1 |! {1 z                {
                    temp = arr;
8 o* F7 k5 [% l4 V2 W
                    //后移
, z; Q; a* e8 [! C  F1 ^                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];
+ {. \% u- C, |, H" r! V
6 H$ d& b5 m; e" x                    arr[j + gap] = temp;//插入进去
                }
            }
            //************************************************************************************
        }
/ H) E2 a4 c4 h}

; {, K  g3 ~( |0 L! m1
2
3
4
5
6
5 H5 T, B, |: K* A/ T7
* }+ b- B6 Y# n- O( `  r8
9
10
7 @: s5 h7 c( Z/ n1 B11
. S+ u. K" e: a3 c3 v12
13
4 r0 E. Y( g+ c14
15
. r' g7 k/ l; a5 I0 @: j0 z" \' ~16
( ~3 M3 ?+ V& _* V17
18
% O/ P2 Q: @6 v( g: D1 M19
20
21
: w  [# J7 X2 {% X0 H22
23
% I- H6 P* J4 b3 V: G& T5 }24
+ c" z1 D& N! r4 T% v; [/ ~8 ?时间、空间复杂度
空间复杂度：O(1)
/ B. {/ S  O) H  m3 J, ^9 C, g. d
; Z" E( z% }3 b8 A; `  X5 N/ Y# M9 F2 x时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
. |9 G1 \8 j2 y% z$ ~* a1 Z
0 f7 y- r/ N7 }" y稳定性：不稳定！
- L# N# X8 V! Y0 l/ A

! N) }# n# W- L. g6 A2 U
适⽤性：仅适⽤于顺序表，不适⽤于链表

5 Q5 ~3 M6 ~, e/ i) j- D1 r5 {

; T( O/ V% E5 @2 x2. 交换排序
2.1 (稳定）冒泡排序
2 r4 s5 f5 s, [1 y& R4 s* C英文:bubble sort     (bubble 动和名词 起泡，冒泡)
8 t! w! ]# O- o, M从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

( e3 a# G6 @# ^, Q" Z" ^6 ]每一轮比较会让一个最大数字沉底或者一个最小数字上浮
& M) j+ a. P5 m# n
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

( Y+ I8 W) D9 y2 l! b实现代码：
+ L- d: M+ R+ J1 x0 _; E
  q1 n6 l. i! {' _, @//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
{
& J, D9 z4 D8 T        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
        {
3 r/ w1 g( Q9 R. a3 b  b" f                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
                {
" P" J& i5 F0 t) g2 y                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
- N3 \  q5 c2 _. x7 d- w9 a                        {
                                //交换两个元素位置
% q* F) R7 d* l  @) I: G0 h                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
" P! ?! {# r1 o                }
        }
}

1
2
% N& s% W$ K& ^- ^5 Z, J3
4
5
6
7
8
3 {+ q5 i6 U: ?9
10
. ?9 |/ J8 j+ ^0 \! q4 n" M11
12
13
; H! e0 s9 I" b$ G8 ~2 m# z. ^14
15
" \1 o& ]1 @& U4 p* D16
- [# B$ a+ P, [, K6 O9 K3 y7 N17
' m% x2 f  b: D8 f& n18
19
2 O5 g/ ~4 V" q2 o- V) r优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

//从小到大：
void bubble_sort(int arr[], int len)
& i5 C; O, R( q! c{
        int temp;
- b6 Y. [2 S: E4 `1 W$ E        bool flag;
        for (int i = 0; i < len - 1; ++i)
        {
            //表示本趟冒泡是否发生交换的标志
0 w5 X1 y* x5 l; w                flag=false;
               
                for (int j = 0; j < len - 1 - i; ++j)
) j$ ?/ {* Y+ C/ y' E( l. R: `                {
; [! w9 H7 k7 J1 Z3 k8 Z  k                        if (arr[j] > arr[j + 1])//稳定的原因
7 \1 d5 s; T* J( z" U$ ~5 g                        {
                                temp = arr[j];
7 u% ]$ h6 O6 W: M) B8 F7 F                                arr[j] = arr[j + 1];
% n2 D" O3 V1 k& i% u* V3 K. ^                                arr[j + 1] = temp;
                                //有发生交换
                                flag=true;
2 l9 H  w1 b9 ~. l( C) k7 o                        }
5 Q9 P6 b/ b" \( g, ^1 k; p; T                }//for
  y( o; e9 R! l7 V* r+ w% E               
                //本趟遍历后没有发生交换，说明表已经有序
! u7 X( e, k5 l                if(flag==false)return;【1】
% G! m/ j5 q1 M* M3 i3 c5 U        }//for
}

1
2
3
4
5
6
- Q2 s3 T# h' s! T; y7
8
9
% m3 K, e; v4 i1 O10
- Y  Y0 J- w6 H3 E6 ^# S& z11
# d3 n5 h; I& b5 ^: N12
13
+ v  Q; m& N' ?% h14
$ t. D" M4 r& s  \" e- u0 k& c15
0 z1 ~& h6 s9 O. t5 K/ t: T16
* w7 u- {* o% H+ j% B17
18
1 j. N' ]* t4 a$ P8 p  ?19
# _. @. T3 [1 S) _20
( S8 T3 r9 F! |/ L21
22
; ]- B7 @4 U( `4 ~8 ]1 E* Z9 W! |23
7 N2 q- r" u, {  Y% n, N3 \24
4 C  y$ J- l. F' a" W25
26
时间、空间复杂度
4 f1 _2 H' m/ N3 M) J; M$ e
% j3 l# i7 ~+ _. n7 ^' o' o适用性：冒泡排序可以用于顺序表、链表


( |( N/ C9 s* ~, Q

2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
5 ^. m& g. s, c, d在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
# n8 w! E! h1 I& o* r, w再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
5 \  W8 f1 n( j" \- o
) e& G( f7 O1 C! n& x3 ~' ^8 {然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
! H7 A& C' F2 c" V' Z
划分的过程：

/ ~0 g5 S6 L, l2 g初始状态：取首元素为pivot，定义low，high指针

; P; g  ?$ V* u. M5 Z3 h$ ?4 _首元素为49
# [1 m/ ?+ @2 Z& d- h" b+ Ahigh指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置
8 d7 N9 \' r" i; J/ b$ Y& N
5 F/ m2 Q; p# x1 l' k2 \" G



" D5 F# `. Y" y// 用第一个元素将数组A[]划分为两个部分
) R& k' ~# D% l- i. _* V. }int Partition(int A[], int low, int high){
        //取首元素为pivot
# \, \1 I* X7 u1 b" H    int pivot = A[low];

    while(low<high)
    {
( G# O9 N% d/ l6 Z            //先是high开始向左移动
4 V; g& @1 k3 D& P7 b7 F        while(low<high && A[high]>=pivot)
$ w6 b: G4 S5 L, h3 P            --high;
        A[low] = A[high];
" a( m9 a0 U( C
        //随后low向右移动
" a% j, f8 @  i4 A- n/ P: x        while(low<high && A[low]<=pivot)
            ++low;
        A[high] = A[low];
    }
) ~0 `+ C2 y% T; Y3 b9 g
! R1 h0 o6 c2 L1 z1 ?, V    //low=high的位置，即pivot放在的位置
    A[low] = pivot;
' C* g. P# v$ S
7 w% k9 M5 x: P: s; O    return low;
}
" E1 o) S% R1 F& `
2 @. n# ~$ F5 J$ p// 对A[]数组的low到high进行快速排序
% {" x* t) Y0 z: E( {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);
    }
}
, d# ~; ~8 i0 R
6 E" L+ o3 `7 U' l& m& r1
2
3
4
5
6
8 @8 x( E5 \1 v. I+ K. l7
: e  |; X4 N% ^; u8
9
$ A7 c: }' ~7 w) D- B0 H6 M10
3 N% v" H1 I3 N7 t3 M  j! ~1 s( {11
+ u* y8 S' b$ G. G12
8 ?: K# Z  a9 K% T13
+ n2 M! R5 F' z" U2 J4 N) u5 S; M/ J14
15
16
17
18
% s2 O: t/ Y" o9 i% M8 X19
( q: {7 f, _, X6 X$ j20
21
22
4 \1 O6 R. J+ Y( a$ l; z23
# V3 ]6 N0 E* L9 q. U/ y24
4 A8 w7 y8 ?/ P1 ^1 B, `/ x+ Y25
! N/ V$ Y& c: Z7 Z26
27
28
1 F- P( P2 O, r* N& G: p- j29
; h$ {; ^- h% ]4 `8 p30
31
32
: p, Q+ R7 I& q% ?# `2 b6 h时间、空间复杂度
# d9 i+ Z$ }* e" q
# n3 w$ }& O- b) m. f! k
把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
/ K5 l# y" R0 n3 @2 Q0 A* Q3 [7 T/ x" F
/ X% {7 ~0 _" H, w; l+ on个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n
# r) o$ n* x- x* N# _" Z7 D; I. r
6 N# W5 {9 d# m. @. U+ p7 {+ z: k7 v5 F时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
' Y1 |5 Q- F  C, a平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法
' z0 R% Y% G: I7 i
空间复杂度=O(递归层数)
; j$ h  r0 O  C! X! _0 l; N( e/ m最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)

4 k# x+ w4 r+ d. Y' T最坏的情况
5 u4 ^4 V) |! `$ V6 Z, t) j# p7 P

: h9 B4 }* S: p# Z
⽐较好的情况
% z7 w) g4 K0 W1 d
1 o! H: k) G; d
' A, q! G# W  G; V* d0 w! D
不稳定的原因：
) {  \8 T8 C' ?; Q9 _

  u7 Z/ w/ W7 k, H& R

. O1 n2 Z" y* ^
0 v' k) N6 w4 n9 b3.选择排序
7 U0 X+ j' b" A+ u" h+ Y选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
' W1 `2 r2 S" U! P2 }( A3 t
3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
/ }" s* O9 h, g9 y! _


3 p0 ]/ A! E- U  N, M4 O// 交换a和b的值
( |- e7 |4 Z9 ]void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
1 [' A+ K; O% s+ n}

% ^. S( @% x2 @/ N* e. {0 t% H  H// 对A[]数组共n个元素进行选择排序
$ C4 B, ~/ ^- u, h$ {4 [  [void SelectSort(int A[], int n)
{
        //一共进行n-1趟，i指向待排序序列中第一个元素
( K7 v8 V# B% {' W! i" _* ]' Z    for(int i=0; i<n-1; i++)
( J# S3 a9 L4 c4 b    {                 
0 r1 }, M( }! g! ]        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
! {8 b4 G" c, Y            if(A[j]<A[min])
7 I9 K8 P8 R3 M% ^9 r% Q3 X                min = j;
        }
9 f" ~) `: _! G        if(min!=i)                     
* W; P  w+ O- A, |            swap(A, A[min]);
    }
}
- K: |7 ^! g4 f: `
' _- w' d( F* V( a. }1
, I. ]- d7 _; D+ X" [2
+ y9 a. H2 J' O: x3 ~9 ?/ i3
4
! g. s0 P3 b: Q; z7 Z) d( T5
' _# Y* s* V. A$ u5 `' A. Y  X6
7
! s8 k- ~1 Q$ }2 k1 v8
8 G$ h1 C; f' {9 j2 c9
2 s( h0 C# R+ z10
! |: \  C& s+ g6 m5 f+ u5 J) f. [/ p11
1 M5 A$ w* Q0 R: w7 K) K12
& }2 Y% M! A8 `9 _13
14
2 T5 \& U- d# p. _# Z  b15
; S3 F) @1 r* H) z+ _16
17
18
- \# B8 o; k1 J  u' g- M( b19
, [) R& i* I! m8 o20
. @' E+ `3 h; l21
3 S  Q4 c0 z% m. z4 g) V, q22
补充：对链表进行简单选择排序
( M* h5 Y" I8 @8 K& `4 E% \
  @% B5 Z/ n5 O& i+ Mvoid selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
) D4 L- K# P1 T  K9 g' Q& _) }' ?    while(h!=NULL){
. k6 ]8 m  R, h" W! n9 y        p=s=h; q=r=NULL;
        while(p!=NULL){
2 s7 M! c7 h+ F5 U9 }6 X            if(p->data>s->data){
( B9 C# Q. m  `2 ~7 W8 |                s=p; r=q;
            }
            q=p; p=p->next;
6 t: T' o, r; a( H, T$ D        }
$ g2 e* i+ |. h2 {5 c/ P( W3 M        if(s==h)
8 }$ c& q, N' y" c9 x/ j# ^# W0 I            h=h->next;
        else
            r->next=s->next;
3 J+ Z7 Q: F0 H8 @        s->next=L; L=s;
& C0 x$ O; g7 M    }
}

0 X0 f6 V1 q3 ]% b1
2
. Z9 y; y# f& i0 b7 j6 W+ e3
; [) e8 b$ O* U' u4
5
6
7
5 J$ n! z, n! ]! L+ F- m6 A8 T8
9
+ m3 M# Y: l/ p* I! ]10
11
12
13
14
15
/ U) X' M. Q8 }/ Q: I16
17
18
7 T; m9 S, R, `- h5 v. Q时间、空间复杂度
% R  E  Y1 f6 x6 r6 e0 L5 g1 m& A


' T. i) [8 \, L; t4 B! o
/ _0 f4 D  T3 H& T适用性：适用于顺序存储和链式存储的线性表。
8 h* x$ @# y, r& x  t0 k- [8 F" s
6 h; a+ }# Y3 @0 @4 b. d. c5 r/ o
6 v  X2 A" `( P8 ^- U1 j
3.2 （不稳定）堆排序
! R7 x7 _' R* Q① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
- l# R( s8 Y/ Q. \, z每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
. F8 |  x, V  p
, a+ S. C  g6 t9 j

即：
若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
# C9 x: c3 l: g6 ^& L8 {7 k% i若满⾜：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)
思路：
2 q% i# {3 A# J4 q* [把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
9 X& a9 k, n; m- [3 S
/ q8 m& |5 p5 _% W) b在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
+ s3 t8 v* t9 _8 t: k6 F) b
; L; b6 ]8 @( E3 Z检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

6 F* q% H5 p. c; b8 y6 v过程例子：


% S2 ^* l, y- M: n9 {# o
  U6 p4 _/ \/ N. \建⽴⼤根堆（代码）：
# }4 Q( W5 i  M

+ F- d7 m- L' e6 k* I8 R/ r
, }* ^+ l6 K; q. w// 对初始序列建立大根堆
: m0 G1 b6 o- E  y2 p( Yvoid 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){
    A[0] = A[k];
    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
% Q8 e$ d6 Q5 T0 v        if(i<len && A<A[i+1])       
1 z  F$ z6 [4 s6 P" {6 K            i++;
        if(A[0] >= A)
% D. I! a6 B2 P9 h7 y5 ]% p7 a            break;
# x# l0 l6 ^( e0 L* E; |        else{
- U& {  C1 W! \' n. t" O            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
        }
9 s* N; f: V$ g8 Q  R3 f3 A* W    }
1 a; r0 k! J  e5 n/ c5 K% m    A[k] = A[0]
}
+ H  T6 p1 [. \  j- D. D& o7 S
' p7 o4 u. D( X0 P5 _# e1
, V. h- i% ]( a7 i( ~5 V: `2
3
( M" T1 n5 L1 H9 L6 t( ~4
' B" @  q! t- t& P; c6 H5
4 s$ u  J; G4 F; J5 L6
& W. O9 F# {; s, U4 ]7
- M5 x* D- R+ q' V8
9
' `. t  P6 \- E* I10
11
+ ^3 Q' z+ C2 G3 r2 P12
13
# O- x4 e  P: i6 p" {$ M7 t- M- R14
15
. c4 d" w) [5 b( U. W# |16
: _# w3 V" }7 l' j& c17
% g' u3 m9 r/ T5 e0 V18
19
0 z' w+ f/ z# ]0 n+ i) ?; ]20
1 q( ?# w' z9 n! ^! u, P21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
' x/ a: g) ~& J- J选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

' C. @7 T- n6 e( b堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
* g( t0 E/ {: m, A5 D# O; T4 o
过程：
- @0 o. w) w7 u) D$ \  h. u% f' J
1 c8 k; E; @6 g( N* x0 t) ~4 R9 P4 _// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
/ t  Z. V) l& P+ \8 \    b = temp;
}
; u$ r3 q" J9 H2 ^% {2 X
$ y% [; s6 |! _5 a& h// 对长为len的数组A[]进行堆排序
$ P' {; T( q# s( }' c. Avoid HeapSort(int A[], int len){
        //初始建立大根堆
9 ]( P) z, ~% g$ l2 d  _    BuildMaxHeap(A, len);                
  X3 E: p: J3 @* e2 D' U. I
    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
7 j2 T( p% e7 c. G# z    {             
        swap(A, A[1]);
  k% g; o  P  q$ l) ~        HeadAdjust(A,1,i-1);
    }
& B! H( _; i+ K  l% R8 K}

! H( K# ^7 _- _% B( t1
2
. v5 {, @% c4 L+ ?3
4
5
6
% k) l9 Y4 ]  ^1 W7
8
! W2 J1 Q! y0 M' s) I9
10
11
12
0 t. T; T! M' t3 ^" Y) w& A13
  j1 }6 N& V: e$ D# M9 Q14
15
. o" E$ Y& A8 u16
# x2 d9 P; ?' t, \17
( v+ w8 M+ ~' d4 I18
19
; D1 a, N( a* }3 X+ y9 A* I4 X3 @时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
! k0 I# J! O! T: e* G故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

! j: z9 q) {7 A: R% Y空间复杂度 = O(1)

结论：堆排序是不稳定的
4 }# Q. V" e4 x" ?3 i3 g; N

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

/ b+ l3 ]. Z' s% v/ V
4 l0 d  C' x4 g; a# O4 s
& C& Q& X1 }! {/ G' p6 i⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌



% |* D4 D) a8 W- W; _/ P1 }7 g
  U+ `, W% Q# f7 G# U
4. （稳定）归并排序
' r9 e* s" ?' D& O+ M9 A+ M+ G归并：把两个或多个已经有序的序列合并成⼀个

① 明白什么是“2路”归并？——就是“⼆合⼀”
! R& L% I; a0 K" J
多路归并：
4 W# b1 b9 p" O4 m. J
3 D  {. L2 u; x6 @
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

0 E; v! X4 }) q/ h# lB[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
" v9 h2 Q- y; S, K! V: h
3 t) B9 }; P% H( O' w③递归进行分治思想【MergeSort(int A[], int low, int high)】
# \/ N1 A+ t. s8 y9 t

④ 总实现代码
+ N$ M% A! e; P, u// 辅助数组B
8 r8 ^4 o2 f' u0 w, Hint *B=(int *)malloc(n*sizeof(int));

; Q0 ^; f9 h/ L( G6 ]// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
    int i,j,k;
    for(k=low; k<=high; k++)
4 B( {. z  x; N" S9 u4 X0 e        B[k]=A[k];
0 M5 {6 X( Q. Z6 ^8 W& `- m* y    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B<=B[j])
            A[k]=B[i++];
        else
            A[k]=B[j++];
    }
    while(i<=mid)
        A[k++]=B[i++];
3 x/ X8 e2 ]$ p9 K6 ^    while(j<=high)
/ L7 y- I+ k* B6 G; z# P& Q. e        A[k++]=B[j++];
}


// 递归操作（使用了分治法思想）
" ]1 T! i4 C6 Z% d! rvoid MergeSort(int A[], int low, int high){
9 S/ z( f. m4 j4 F; B  R7 T    if(low<high){
        int mid = (low+high)/2;
  m: [0 j6 C$ h5 D! y5 Q% A( n3 S        MergeSort(A, low, mid);
: c/ G/ f0 \3 c5 i/ X        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
/ W: J$ z# S( ^; G+ n; i    }
" m. W8 D7 i0 F: g7 ~- B+ }1 B}

/ f+ D, A: W( G' V# u2 x; G1
2
9 `1 a# @7 p4 S/ r& X) C3
1 J( v0 W) d8 K( ?4 a7 M! U4
5
- @3 R) J1 f9 A6
6 v( }, u: g1 X; h7
* m' l$ T" O4 J# u0 Y8
7 g  U( a) _7 b9
! u8 a" Z6 V) z. f% h. C* R10
11
12
13
14
5 S* y; Q9 E0 l3 O( |15
* e" K' P: d5 u7 ^, J# y16
17
$ s9 N! ~! `$ P6 `8 d  ?( o+ o6 i8 T18
19
, S2 M" m& m" @. M/ C" ~% X20
7 v. w7 v& Z* Q- k6 p8 N# T21
22
23
5 ]. F5 t7 H% S' Y% b: I24
25
26
27
( @3 H2 q8 n: E& Z28
29
" F8 g/ B6 j* w7 m30
时间、空间复杂度




* x) D! K: M$ I- n6 V2 Z/ U6 s! ?5. 基数排序
) i* M" B. t' E3 F. a9 d直接看课本的过程图来理解P352

0 i1 Z1 Y3 z! j# D再看这个例子：
! o$ n2 U9 A0 Y' ]! v) H9 B  a

算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
& J1 W6 N3 x# V/ Q1 A6 N分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
( N' C, i1 L; ^# R. i0 I收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
1 [( I+ K4 ?6 a& T; k+ [) a基数排序擅长处理的问题：
" t1 E+ [) a2 o% y①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。
算法效率分析：
8 y  L( N( A9 ]时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
: c$ I( l( q3 C9 j稳定性：稳定。


+ U) i* [4 R5 Z+ s2 r8 B1 E内部排序算法总结
6 P9 f9 K3 a! k- S; a, E
) T+ y1 X  c# T) D7 h3 l8 ~————————————————
5 i9 G; {  l4 x# ^; Y* Q2 C* c版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 V2 a" p3 P/ X8 q+ w: o5 \( l4 a原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969
8 r8 `! p  |' h" T' u
" N1 ^. L6 j$ q6 l8 p9 z
; n; {' {' s5 [