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

杨利霞

7 ~+ W5 \. |9 h( h【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
排序
1. 插⼊排序
% ~0 X3 H) d5 i（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
7 R8 [! U5 g% s2 T时间、空间复杂度
0 O0 f3 k) B9 w( ~  Y（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
; X" i' n% A0 N（不稳定）1.3 希尔排序【多次直接插入排序】
7 g* S8 S  {& N+ h, O时间、空间复杂度
2. 交换排序
2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
& m: d; {0 ^3 K" [0 Z6 L( F4 j' s时间、空间复杂度
5 K) U2 }  v9 `  z/ a3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
& E6 N' e2 E' D1 ]. ?# B  ?3.2 （不稳定）堆排序
  @7 |- I  z7 L4 f) X  w; }① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
④ 补充：在堆中插⼊新元素
7 s& ?- p. N5 h& n4 [$ W( w6 ], H⑤ 补充：在堆中删除元素
4. （稳定）归并排序
* {$ R6 h& r! Q% [7 Y. i6 |, ?" R① 明白什么是“2路”归并？——就是“⼆合⼀”
$ Y2 F, a3 `. ~7 w0 y$ `: p② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
. q$ V3 O- D$ f7 [! A④ 总实现代码
0 Q( e. D$ |5 [0 K) p时间、空间复杂度
5. 基数排序
内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

9 b0 c9 |7 _* I排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
% r1 v, j7 }0 X" R
9 w  S6 Y) s* u" j0 X. Z# Z( x算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
' H! a+ ]' J: l* H! x8 a3 r稳定的排序算法不一定比不稳定的排序算法要好。
1 l& N4 R' t9 l: k6 x2 ]" D

8 v- a$ Z6 P, D0 K) Z排序算法的分类：
8 G6 a  E8 D/ k. Z+ m/ `' g内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
) K5 l/ J' `  q9 Y! ?外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

' g) p4 ~) j( A. U3 ^

1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
# X$ U- P8 Q: x$ A4 v基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

算法解释：（从小到大）

, p/ I4 n; D# c) W9 m6 ?
+ q$ f# }; P- `5 _6 ]2 s1 H) M算法三个步骤：
$ b) ]) x. a" H. O: s
. m: {' y4 a& J( V7 x& L1 [先保留要插入的数字
/ c! e/ I9 Z* I) N往后移
插入元素
. l. _# Q) Z- m1 [! t% Z/ V/ z
// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
7 s1 X! y+ e1 V6 w5 j. ?: b    for(i=1; i<n; i++)
" V7 W. X9 t: H    {
  S" N4 _1 E6 m! n/ B. A$ ~: A            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
. ^/ C' k. X- }) F8 R5 ]        if(A<A[i-1])
4 o3 O) l8 N8 C0 ?; O% C0 T5 H        {           
            temp=A;  //保留要插入的数字
: s' F6 m, P) Q, d9 `2 H; v
( T% ]: a0 F5 U# J2 c" ]; C            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪

            A[j+1]=temp;//插入元素
        }
( \( T. h0 ?3 c, d    }
" {& g7 g% ]0 B. T9 ^}

1
2
3
2 i/ l! N* i3 L4
; t8 n3 j0 v/ n5 u" V3 Q5
6
7
4 o! o+ o3 v* G; i' Y0 Y6 \8
9
10
6 M4 M- a6 x' z7 L11
12
# u& y' T* c$ `# p9 g13
. c5 r* w. [. Y1 V+ Z! ]3 r" Z14
4 e' B8 b" d& j3 G6 n+ U! M$ o" w15
+ e9 X1 Z2 Z1 V& _5 X* i5 Y16
* O" g" a2 i5 Y17
7 Y  h3 }# M; Q) S' c( U  g用算法再带入这个例子，进行加深理解
) I" |1 G0 A# m; F* q/ B0 F

带哨兵：

) S) Q2 h: Q6 h  ?3 @' D
补充：对链表L进行插入排序

/ V9 j" Y/ z" O/ s: \% cvoid InsertSort(LinkList &L){
3 \. G1 o& }2 J. p) c  O    LNode *p=L->next, *pre;
    LNode *r=p->next;
    p->next=NULL;
8 p6 c! C1 O+ X- S2 n+ ~    p=r;
7 [* A" V& T- R% J9 s) w    while(p!=NULL){
( C( V& f% [' a& K5 ^" S; S+ }        r=p->next;
" i( z) R8 m" `  O* D' P  m( n        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
        p->next=pre->next;
        pre->next=p;
        p=r;
% _9 D- M* \3 c5 n/ l9 M    }
}
1
2
& P% _  }2 z3 T* W+ p3
0 t1 \4 C" F/ l6 R( f4
5
6
7
, c& |& F, e& e8
8 r, `! R  t. s9
/ c2 _' P2 r; x# X( [! u* {10
7 J7 R3 m( q4 _" R6 l& {* V9 g11
12
0 |" C  j( w( e8 Q13
$ j& O. ]$ y0 e! J2 n; k$ ^4 I14
! V5 \. u" X. T- v9 _5 @0 T15
6 S# E3 E$ \% ^- k& I时间、空间复杂度


最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
2 T' d' Z  @9 h最好时间复杂度—— O(n)
/ h6 j8 O2 s. G" V( A
8 }  i4 E5 q+ ~) C) V" l; }0 m最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
' }/ I) S' Z8 D…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
) U* d2 w( s# i1 J9 [' P4 G最坏时间复杂度——O(n2)
; J/ m% f& T3 Z4 ~2 }- U
( o; v; J# [! M7 |, |2 B8 V& q, F



（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：
2 g; R8 j& u/ Q3 H) F


1 O$ N, e# o3 j5 z. j//对A[]数组中共n个元素进行折半插入排序
' _2 _) B6 v0 O5 `void InsertSort(int A[], int n)
  h; ]7 T- w$ g3 r3 i; Z0 M{
    int i,j,low,high,mid;
6 B( z5 M! e- k    for(i=2; i<=n; i++)
    {
        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
        while(low<=high){            
% _6 v/ a( |1 g3 V; ^* c( u( Z( N            mid=(low+high)/2;
( U/ c6 \( s9 G2 O8 |            if(A[mid]>A[0])
                high=mid-1;
            else
                low=mid+1;
        }
         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
- a+ I/ c. p3 m2 R8 r. J4 h# F            A[j+1]=A[j];
& w2 H. c6 O# [. X% o" e& f6 M
3 |/ x' Z& L% a7 b  X, @$ U$ L4 a# O        A[high+1]=A[0];//插入
& |, z2 m: m$ h    }
5 O6 a$ w' E6 d$ o! Y5 \}
( n, V7 k3 p) x+ n
1
. ?+ e. m8 s; P; B, U2
2 W& C! V2 C9 c% D" q3
1 ^* E9 \5 F: |. r  \6 o( c2 u/ n4
5
6
7
# V/ \$ B4 }1 ~# e9 ]7 o8
' b1 b1 t' ~: g  ~' K4 X5 Z9
10
# {- a0 _7 u  Q11
12
% u; r, b0 @2 D# z13
- p; K) z& L* I* S' s14
15
- R5 J% U1 H2 e+ |: U16
" ^) N: b6 E+ Z. N. I/ I6 L17
  ?6 ]; K3 U  v* H: ]/ H1 G, ~18
19
20
* f) A- q2 A' S% p2 N" z21
- @1 d% u8 C! k0 Q1 w6 z; A22
23
7 ]. H6 G" F: f9 `% j8 m: i' a时间、空间复杂度
空间复杂度：O(1)
* Y" I) o" \% H5 z( a& l
: }! J1 |5 r% U3 ]【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
1 p; R8 n# O: C' U, ?& s) ?$ a: i
3 t/ P# |& _8 y8 b( U8 G" R
1 @7 G4 Q. }- L6 \& \7 g（不稳定）1.3 希尔排序【多次直接插入排序】
: E( d# q$ f! K是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
  K) N, p  C5 T
算法思想
2 ^) Z% G0 W+ P6 \& E; k$ @1 V
5 c( U) ^& c5 u$ r" X- g. {希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
2 f& y* x- C) o3 E6 M) t6 S! v图解：
* J+ u- P& t2 E8 H* z' d
& S8 R6 Z3 O: b5 n1 ~: e
) v7 ^  I+ O- f* V  T; }" c
代码实现：
5 h* T+ C3 h8 w& D; S! T
//从小到大
" N# x' y& K4 o7 G  P* Tvoid shellSort(int* arr, int n)
  S$ `+ ^, i5 ?6 H. ]' h{
        int gap, i, j, temp;
/ _1 |* x0 M) F9 G: j# D1 b        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
" s3 ?. b2 `- s* g3 k' a& r& I            //**********************************直接插入排序（只是步长改变）**************************************************
7 ]# `5 }: B+ {4 P7 R& E( w            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
                if (arr < arr[i - gap])
                {
                    temp = arr;
7 p4 U7 o1 g6 e5 [5 Q4 f
' U8 x" m9 t2 t/ G4 T, p% X                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];

                    arr[j + gap] = temp;//插入进去
3 H4 ~' ^! X' F7 g9 F                }
8 [6 T& B" y# `+ u            }
            //************************************************************************************
        }
}

1 J/ g" z" ]' x! L1 ^1
: ?7 e. y# H* s* ?. e% t  ?# ~& Y2
. b. ?) ?$ E. y! e0 h; b$ h! f3
4
5
# e* e5 V+ }& `6
7
8
9
" k* R# e; p6 E2 C$ g5 M10
" r9 ]* w& H( @/ @11
: k' y/ k9 X& @2 W/ H) Y- _' Y1 ^12
13
14
1 `$ F1 [! p% r% K* O15
0 P; w3 C, X1 ^16
: q9 C6 {7 O& ~* Z7 W17
: C% c# F$ u, i6 T& p- P' ^& v18
19
20
8 s  e) l$ z1 ]21
22
; ]; {* r8 b: A- v! x5 V23
24
5 @1 F2 M1 S+ f& w6 g! t时间、空间复杂度
  A9 }8 o# c7 E- `1 t7 }空间复杂度：O(1)

时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
- Q' z/ l, g4 S' s
2 q9 f; i( U# s稳定性：不稳定！


: W# m! e9 W+ d! ^7 z7 h% J  Z: i
& v/ ~: ?/ _" r- y0 T适⽤性：仅适⽤于顺序表，不适⽤于链表
+ X4 @1 q& ?. m  |
- i8 y* y) N$ _: M4 v8 ?( N5 E

2. 交换排序
: n% J6 x7 g6 Y, Q" a$ s4 U2.1 (稳定）冒泡排序
: }/ W/ J! m, J4 M英文:bubble sort     (bubble 动和名词 起泡，冒泡)
从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
; B; c1 O' V# M8 R
每一轮比较会让一个最大数字沉底或者一个最小数字上浮
# `  M$ A7 s- U8 R$ `
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

3 b# W0 V% K) d- w实现代码：

//从小到大：
1 M8 P0 X- K( ^& o$ r& n0 t4 Qvoid bubble_sort(int arr[], int len)//冒泡排序int*arr
* }4 ]+ o! Q: {1 t; u) Q{
4 }$ j! T8 ]# i: f- U7 q0 r        int temp;
" Z( Y! g5 {1 M4 \( Q4 ^2 X1 ^        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)//相对于上面的一个优化
                {
1 j% w4 a: n; C2 O$ v                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
6 V: h+ h% I) e% {+ G# f                        {
                                //交换两个元素位置
                                temp = arr[j];
                                arr[j] = arr[j + 1];
! g% V. t" a. ^. F                                arr[j + 1] = temp;
/ i. ?( o0 M/ h" r                        }
                }
3 W) a  q6 r2 k        }
/ J% R6 X& o1 w7 h) |& V}

6 m2 o5 L2 B3 ]3 m% h. J1
) h% p! `  P9 Z6 r& @( ?2 T2
3
4
5
8 k/ Z+ j3 k8 }8 [6
: C: z) W, K4 g7 g7
: d; j" L: ^* [6 F4 c, L8
1 I; M8 u; |) A; G  H4 j7 Q' K2 J9
10
11
8 A6 x# O* W  w) M1 N; G3 I12
13
14
15
16
17
18
9 l* H. e# h$ ~9 p3 E( h19
5 c, t" M  `: T优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
. L9 f+ z( P. }. D% {. l, |
//从小到大：
void bubble_sort(int arr[], int len)
{
8 F" i5 ^3 h4 z( {/ [7 V! g" X        int temp;
2 F  r8 G) H% E+ H) K        bool flag;
        for (int i = 0; i < len - 1; ++i)
        {
) U# r$ q, |* Q            //表示本趟冒泡是否发生交换的标志
                flag=false;
               
                for (int j = 0; j < len - 1 - i; ++j)
                {
                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
* x$ r7 z7 O. ^9 o7 l                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                                //有发生交换
                                flag=true;
+ l3 J1 {7 G+ f, v: }+ L; J0 R) M5 K                        }
                }//for
8 \1 O! s  ~2 ~; T               
" K' n( s- P3 F) E' p+ J                //本趟遍历后没有发生交换，说明表已经有序
$ w. r# [, V9 t1 @% s; ~7 z                if(flag==false)return;【1】
        }//for
( c9 ?+ w: J# j}
3 h3 e& [$ c& I( Q2 N- x  E* |0 W
1
2
3
4
5
3 j# ]2 Z5 q9 ?& ?7 x6
4 \$ w3 o2 @" J$ [/ O. k  x+ S9 F7
8
9
10
11
12
7 P0 R2 ?6 Z4 q' n' \# [& l13
14
15
16
/ X0 ?, `0 R9 n! K17
18
% N4 o* I* D9 c( f19
2 N3 T& a1 J# H2 Y6 x20
21
22
23
24
25
26
时间、空间复杂度
6 \* ~+ n3 A3 x: L- S
8 N: m+ [* R& {适用性：冒泡排序可以用于顺序表、链表
' Y( @# b' ]1 G7 E3 U6 O& N
7 c$ Q- |) A% z7 J% Y6 b+ x

3 r/ T5 i# F; d8 f6 L, A+ H: L
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
: w" @0 z0 l6 u  e& r算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
  k5 K; I1 d: {9 x使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

: s% z; p" t# _( h然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

划分的过程：

初始状态：取首元素为pivot，定义low，high指针
* f) W9 S" @& h/ A$ Y
首元素为49
high指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置



, U  p; D/ R8 r' O0 a

7 b$ J" u, K* y& {// 用第一个元素将数组A[]划分为两个部分
; w* r% F! x0 A( N4 G; ^0 }int Partition(int A[], int low, int high){
        //取首元素为pivot
' q* [& n& c( L) u$ }  H- s- |  q    int pivot = A[low];

    while(low<high)
& z8 M+ q- W# `& ^1 j; w3 g# y    {
            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
            --high;
* F. Q! |( b" g3 d- ^; v        A[low] = A[high];
- S! R4 ]( S  T# k/ |9 p
        //随后low向右移动
* h5 J6 l2 ^) b4 r( X3 I1 H        while(low<high && A[low]<=pivot)
            ++low;
        A[high] = A[low];
7 Z7 r6 ^' U5 l$ k+ t5 C* A3 D    }

1 c3 V  E+ J9 P5 L2 ~7 ~! z! @$ H    //low=high的位置，即pivot放在的位置
    A[low] = pivot;
8 s4 ^" r8 d4 S- D+ p, _; H9 b
    return low;
5 B& Z4 F, J. B$ X( Y8 I}

/ u4 P; X  Z! T% N// 对A[]数组的low到high进行快速排序
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);
# p2 G% D0 q: y; L7 M; C    }
! y) r& z% D& W2 C. r+ N, W}

) s0 C% ]8 m7 B1
) |: u+ `! @6 D1 F6 ]% I2
3
4
5
6
7
# Y0 k/ q) z% Y8 \8 c4 F1 L! m/ S% Z8
/ y+ L# X  K( \1 D: p9
10
) m' s5 S6 y  p4 N& k2 m11
0 a! d2 K6 O4 I6 P12
13
14
. s& D' J4 u, |5 {- m0 A15
16
17
* Z" p4 k! |3 [. d5 |, n/ v18
( y( r/ T  p! H, Z) o- L$ k& T19
20
' }( P1 z: A; L( l# P% c, \21
22
23
24
25
8 q7 e' |8 y/ r. }5 v: N7 v- _26
27
28
29
- i$ m: v; X! G30
  m& k, [2 t" O& n0 T31
32
$ N  x' z0 i5 s3 t: D时间、空间复杂度


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

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

' G  T4 D* K: G( U) x& H时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
, i/ m" X$ q$ X2 y+ W) L: \/ ?, b2 o最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

空间复杂度=O(递归层数)
4 ]" i5 E" u/ {3 X% T& F6 w最好空间复杂度=O(log2n)
7 t+ E/ y. S' r: o) U最坏空间复杂度=O(n)
& v! d) y7 ]3 t8 E. C% i
最坏的情况
! w5 a4 d$ b- i! O6 g
" N( S4 b* F, a; @: |+ Q/ u
, J0 S& V6 n9 k8 b1 W$ G8 u
; \4 I+ M7 d" s⽐较好的情况



$ `0 h4 j  j0 i$ V# c9 i2 J6 V不稳定的原因：

; n1 y: ?8 _7 k# i( O


4 K" L4 G" i! E- B1 y
3.选择排序
6 j; ~) S$ @; [  V: [选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

3 G0 Z, S( @: U8 ~3 Y3.1 （不稳定）简单选择排序
+ X& i: j, x1 M算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
! _9 z" {/ Z* q3 k' Z. U9 Q! ~


2 i  T+ Y- i8 Z  {// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
& L  o; z- ]/ c* r2 F% F    b = temp;
}

// 对A[]数组共n个元素进行选择排序
3 G+ R, J; o2 X6 `5 P/ r/ x5 Pvoid SelectSort(int A[], int n)
4 A' l3 {5 `3 d{
% P/ H! K& l! [5 C* @        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
9 ]/ U3 o: D# B6 w3 g+ N" n* Z    {                 
+ k3 F* _- A/ J0 O8 f% Z7 r3 e        int min = i;
% a) e4 `- `0 A# X9 C+ H        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
- j$ R7 q: r8 r/ m$ V6 L" r            if(A[j]<A[min])
                min = j;
        }
$ w  G) h- ~: z* [0 E# w        if(min!=i)                     
: \; p/ F& h, Z0 \            swap(A, A[min]);
    }
  [( ~6 P2 R- g, J7 @. [}
, a5 O% W! \9 X, b, {& }0 {
1
/ D/ P3 D3 e5 K- o' |2 s; w" p3 w2
3
4
  Y& w% A8 ]9 n' B* M; ~' S. k! U, p5
2 q1 q) D( D+ E7 `5 ~6
7
6 e' L( l* X4 A. |$ U, z. X+ I8
( ~  F/ r. F1 k- A" W6 Q) {9
5 C" q/ I* o+ {3 j( B- b7 j10
8 z8 @$ F3 s6 w2 W: S11
12
13
! z7 @0 H5 y8 q! g& x; r14
15
/ Y7 N0 l* _1 F0 K" a# b0 y16
17
18
2 Y3 I, M! X3 B0 S  E. Z" q6 ^19
20
9 @- k- P* Q% f8 a9 }5 Z. Z21
4 e' Y  `- o6 Z3 Y  I+ Q22
3 K4 V& d8 _& H2 e5 A; ]6 k, ~8 S# s补充：对链表进行简单选择排序
  H  k2 v9 F$ N0 L' \$ a8 h; V
void selectSort(LinkList &L){
& E* M0 N# E! U: ?/ w/ r$ i    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
/ ^1 f/ Q4 N6 \; u& m& Y    while(h!=NULL){
        p=s=h; q=r=NULL;
# p% J3 i' j! K  g        while(p!=NULL){
            if(p->data>s->data){
                s=p; r=q;
            }
            q=p; p=p->next;
9 z+ h1 O8 n. Y( K( \, ^0 E! ^        }
/ @; Q6 l+ }! F" g8 ^. N. h. i/ J        if(s==h)
            h=h->next;
& b: |' S3 ]3 {4 c  v        else
            r->next=s->next;
: f$ f, O1 {; n" d$ V. v3 i$ m, c        s->next=L; L=s;
    }
}
  ^0 @1 f7 m6 M8 b
+ R  Y2 D( ~9 t  l- [$ C1
2
3
4
1 i3 _( J5 X( x% z: W5
6
( |: ?5 d; Q! ]7 b* @1 C- k7
( _4 t1 K3 P3 N' w& H8
" E) W  S0 o4 B8 B# q" I9
- J2 ^; l4 P7 ~7 k% ]. a7 z10
11
12
, C3 P* f" J" y13
  I. J; X: X; _, ~! p8 O14
15
16
17
18
时间、空间复杂度




适用性：适用于顺序存储和链式存储的线性表。

& ]$ @8 q, P/ |9 h" j
' k5 {: X1 j, f
3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
. j" ^3 n& V6 c每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

, D. S) |/ a( J6 _. x( v

* n0 h% G  T  V1 R/ i; U4 A1 h4 A即：
7 q' l( u; R- N# T/ i  C3 G& n; ^若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
" t. |! s9 [7 z. N% g, l% U" O若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）

' j' w0 J% E2 ?7 G, d② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
0 Z/ M! N9 ~5 H% v1 n3 Q1 w: }思路：
9 X1 U. S3 S' `8 ~* V把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

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

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

- b) ]5 X% ~/ m9 O! y过程例子：



建⽴⼤根堆（代码）：



// 对初始序列建立大根堆
  F/ G' d1 C( M/ [void BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
}

// 将以k为根的子树调整为大根堆
& K' A0 ?9 S. D- l  D! k& m, dvoid HeadAdjust(int A[], int k, int len){
/ w) }, ?3 Q9 O$ }; K    A[0] = A[k];
- u  m8 g* H  q0 o3 t; N( a+ k  _! P    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
  M- l5 N8 Y  @" O4 z5 }        if(i<len && A<A[i+1])       
            i++;
2 b# _! s4 u- I6 u        if(A[0] >= A)
' f' v+ T* D- A' q: x- j" Z            break;
$ e( h$ G0 A# |# ]& Y5 R        else{
            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
0 m! U/ H- Z5 X4 i        }
1 d, Q: _6 T1 B8 K    }
    A[k] = A[0]
+ @2 _. E3 g, f9 O" w+ e6 }' i}

- j  F" B4 _& S  Z% v( o1
2
% Z1 f; K. k" w" T! `3
# j$ F& m1 ]7 T# X' E- x/ n9 B! K4
5
- b" `' x& m* O8 r- ]$ J* F' k3 Y6
3 B/ O" w6 U0 o) z; [7 }2 H/ v! c7
8
9 f4 y% b: n  _5 Q9
! j7 u  t0 m) B& c6 _. |10
( ?* }) L% ]1 r- Z11
' a, v# |; c0 |1 \) I1 `+ ^/ ~# _+ A12
13
2 U8 p+ c$ J# @' ?; `14
' M! [) L' A- W; C6 z0 c( E15
16
17
18
- K& Y& K+ a6 I% j& y! C5 E19
20
1 o: Y  d( l9 d) Q21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
  r5 G/ u7 w+ K8 t0 |; B
堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

过程：
# O/ H4 f& ~2 Y- d
// 交换a和b的值
! a- J/ n7 k' }* D0 ~& Wvoid swap(int &a, int &b){
( k6 G- ]  A) c( W    int temp = a;
' k1 |( x6 }. n6 @; t    a = b;
    b = temp;
}
. q& G% S) R: Y
7 d, o7 r& ~. P# ?! _// 对长为len的数组A[]进行堆排序
) k% p! j  V: ]& F: H* K  |/ mvoid HeapSort(int A[], int len){
+ R% x7 `6 @) s& Y        //初始建立大根堆
  ?% {, f- P& v1 {, g    BuildMaxHeap(A, len);                
+ n  Z8 {9 H8 x) E
    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
    {             
  Q; s- L# P7 t0 h0 Q8 B        swap(A, A[1]);
        HeadAdjust(A,1,i-1);
    }
! o* Y0 n( ^0 V}
" ~# I1 `0 s- o, B6 J
1
4 C: K; j5 `  y2 K% q2
3
. g- ], w+ c8 E# i5 p; b8 Q4
5
6
7
8
9
8 J7 T+ S, ^% h) j  n+ `3 E! z10
% B5 u$ `  W) M8 f11
12
# Y, k: X. B2 ~4 v13
14
15
( Q! ]( M- F. z5 @# O: p: |16
! Y/ _1 y: ^8 a- C17
0 F8 ^( `! k. Z. U' y: F4 N18
! ]0 c' f2 u* |0 ^/ N9 r19
时间、空间复杂度
8 @& j8 |  ?7 r( E8 b$ Z2 I+ a, r建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

空间复杂度 = O(1)

结论：堆排序是不稳定的

5 z% R1 ]* A4 r7 u
④ 补充：在堆中插⼊新元素
' s4 p5 p. K0 E5 ?' F对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
) }! x0 S9 z( s$ A* e新元素就这样⼀路“上升”，直到⽆法继续上升为⽌



3 \2 ~4 w' y' E; W( ~1 G- b( J⑤ 补充：在堆中删除元素
5 b2 H  D, s8 C# z( v( ~; r被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌



, l' E3 h+ J6 {& m' I" V, Y6 k

4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个

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

多路归并：


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

B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
5 e9 r/ ]- a3 n/ l: h4 z
③递归进行分治思想【MergeSort(int A[], int low, int high)】
* g" R3 s' @2 J+ D( z" p

- T9 C. D+ n* f- z2 c④ 总实现代码
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
- f  l) W+ a& R( V2 N6 y" C2 f2 l" ?
( Z4 y$ J6 c5 O, A3 Y( L// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
1 q: i0 ?8 V* ]* \, Xvoid Merge(int A[], int low, int mid, int high){
    int i,j,k;
% m  L2 v# o0 @- J  Q    for(k=low; k<=high; k++)
        B[k]=A[k];
    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B<=B[j])
! w7 a, I- ]# l: Y3 g9 N1 e2 d            A[k]=B[i++];
        else
            A[k]=B[j++];
5 s4 ~- d9 M/ W7 l    }
, z$ C9 g! |  C, E    while(i<=mid)
        A[k++]=B[i++];
7 b( S) |% Z+ k6 [7 ^& h5 a    while(j<=high)
& N! c8 _% B) f        A[k++]=B[j++];
}
  d( t- K  p6 u8 g/ D$ [

// 递归操作（使用了分治法思想）
* C: a2 ]4 Z3 q5 B; ?( avoid MergeSort(int A[], int low, int high){
    if(low<high){
        int mid = (low+high)/2;
* W0 v' r* O) q7 \/ n- X; E3 Y        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
    }
1 Q8 V5 G0 q8 ]( g! F}
/ a5 z' v1 d9 H  {! S. ^) k
1
8 ?2 I( g6 L: Z2
+ s/ D- C+ h* S9 V1 b3
" Y: c& \+ t3 s: @4
5
' @  u! a3 ^$ |) `6
7
8
! {  U, x7 s; j1 @2 D  `9
! y( d! s6 g# U0 E10
+ I5 h2 B8 J* v9 E$ U11
12
$ A( a3 C2 d, ^) P2 C13
14
15
16
" L- I/ }# Y' b) ^17
18
19
20
' _& u/ l% }4 N3 g2 C21
; \0 x% g1 C1 H" R* d% f22
5 K) p1 ~, G2 B% h, C, b( ~23
24
25
, b' A' w/ b8 R7 P26
4 V1 f* i$ O1 R! U9 {4 g9 P, ~; c27
( c9 L* `: Q. V; w/ I28
29
30
时间、空间复杂度

- [- [3 \1 g1 z* @: u


5. 基数排序
直接看课本的过程图来理解P352

再看这个例子：

! U% _, m% y9 ~- Y
0 y3 I5 k- D0 @! Q+ D- K5 p算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
$ _5 m6 }4 D! \7 a基数排序擅长处理的问题：
# I- h; {9 Z4 h) B* m. ~  q" I+ @①数据元素的关键字可以方便地拆分为d组，且d较小。
# N( _4 D. t7 U% H' N5 |. s②每组关键字的取值范围不大，即r较小。
8 C4 O8 a9 Z6 N7 T8 Y/ M5 u7 ]3 H③ 数据元素个数n较大。
算法效率分析：
8 @: Z- p# }& J$ u时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
稳定性：稳定。
; L3 _1 F- K! b4 q: w, }% U

# l* V4 x! U+ n+ X# K内部排序算法总结

1 Q  G: [$ d6 W' l6 ^) W————————————————
/ b) S$ _6 j) a版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
' ]3 `- E9 U' u4 ?* z原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969
  ?, Z: z6 X- ~' ~

. U: p' d8 P- Z% ?- ]) [