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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
, a$ V) C3 E2 _6 m$ k/ ?文章目录
+ a" [- S( x* y4 X/ A! U排序
1. 插⼊排序
3 p* ~0 k; c7 J2 V" y" H（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
: ~: x. k: z! i3 V$ c* e0 n# ]# j时间、空间复杂度
0 j" L* |: ^' R( J; Z! N（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
. ?/ Z$ y. M$ A, `（不稳定）1.3 希尔排序【多次直接插入排序】
9 P: B1 q" P. ~+ Y时间、空间复杂度
- M* `1 [8 o3 q& y$ C$ v+ T2. 交换排序
2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
. Z* c7 ^# M0 F$ T- I8 Y! c3 r( g时间、空间复杂度
3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
! T* z3 V* y* d8 h4 \; ?; c5 R$ b3.2 （不稳定）堆排序
/ L5 l; a3 H. q6 [① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
! x& M4 |0 j. L+ |% H② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
" k& R) _! p& ~1 i( ~时间、空间复杂度
6 M0 v7 T9 Z5 j9 [- O' f4 p④ 补充：在堆中插⼊新元素
% t: O! [! c' j⑤ 补充：在堆中删除元素
, t9 q& N0 h9 G0 q( U% U4. （稳定）归并排序
% C  ]+ H9 w0 Q" S6 |5 r  d0 s: u2 i① 明白什么是“2路”归并？——就是“⼆合⼀”
  Z9 d& J0 D$ N! u; {② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
$ S. R1 m2 y0 k4 e③递归进行分治思想【MergeSort(int A[], int low, int high)】
7 O6 O" H  X- R6 c. \④ 总实现代码
时间、空间复杂度
5. 基数排序
内部排序算法总结
5 q' }' l6 a9 |& a& N- ~) ~排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

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

# `% A8 q8 K% S. p. w& N* C0 {算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
# \0 q( Q* q5 Y# ]: R稳定的排序算法不一定比不稳定的排序算法要好。


排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
3 |8 L4 }* {0 C- U0 m0 i9 I外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
6 Y7 r& \. J: j" z
( i- Y+ Q/ \' J% u' b* n5 d( Y各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
. s. q( M. \+ `6 ~+ h
: k8 x3 g2 F3 d5 g. Q$ F) i
: z+ H# z* w- \: k1 M. s+ F# {
1. 插⼊排序
& ]) m# L# Q& h9 E+ V' ~4 ]（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

算法解释：（从小到大）

8 n" W9 }1 z% F) U* \, Z
算法三个步骤：
2 a' v7 g# G; x5 i
8 t1 r" T: u) k) K7 N" `先保留要插入的数字
& h0 [, U  r+ I往后移
. L# ^: n/ A. w1 |* `/ S插入元素
" [+ R( o( D0 p3 x: q9 N4 P: T
  B9 _  X: J' p* f3 Q, q6 E// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1; i<n; i++)
* ?" P& Y. D" ~% f    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
        if(A<A[i-1])
0 j( N- I( E6 @9 u: r) ?; ^        {           
) h/ {4 J4 I7 c) H7 d            temp=A;  //保留要插入的数字
* u, |+ D. N  m
1 Q- Q+ K1 d1 q* _9 m! j            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪

) ^+ J/ q+ @( i' `/ n( k8 `! a            A[j+1]=temp;//插入元素
8 g! d; D& |5 s8 _; U        }
" v) `; ^6 ^. t5 w* J    }
}

1
2
3
+ O( e- j/ X& Q% J# u! e4
5
* Z- o4 u) G0 [. C# Y8 A/ x2 e6
7
! L$ ~4 y" |0 Q$ C6 z, ^) `/ ^- ?8
9
5 F3 ^1 b0 i$ \; z, Z5 ~10
11
12
13
. x# p. h( B# @9 o14
15
' \/ @, t5 u" S$ J9 d16
" b1 U3 r% v% r* w) h6 T: r17
; E' _1 ~4 }( @用算法再带入这个例子，进行加深理解
+ b5 c9 W6 L+ d
. d, P- c; q* o8 w# j# F
带哨兵：

% O* M1 K2 l8 @. \  A+ ]
补充：对链表L进行插入排序

" {4 N* r  k: N  y$ h' xvoid InsertSort(LinkList &L){
    LNode *p=L->next, *pre;
5 F! g( P0 Z$ m5 ~2 c    LNode *r=p->next;
    p->next=NULL;
    p=r;
/ N  j/ l& q& m9 c. e/ j( A. L: f    while(p!=NULL){
        r=p->next;
- w$ Y/ K) o- c/ x5 ~9 e; N- Z3 q        pre=L;
& T# n9 V. ^& ~) x        while(pre->next!=NULL && pre->next->data<p->data)
! p8 {+ F7 _4 q1 [; T            pre=pre->next;
        p->next=pre->next;
) `/ ~' g* G* m! t        pre->next=p;
, z/ |2 C. o1 }) A, u/ ?        p=r;
! @5 m6 \, I# O% f1 {& O    }
$ X8 m' L+ Z% F! [' }7 P- c}
1
2
5 `" f' x) a4 `# a) V3
4
5
# Q1 V6 p' h/ r1 |6
. D8 P: W. n& i' ^, ]( m. P7
8
9
0 y! N  z  I' Z10
# }. y1 R# m7 N' J11
/ Z. s3 l+ V7 t6 o+ E12
6 y. Y9 K: r* ]2 H, b; ^4 n5 ^# n13
( T4 L5 }. S$ B% Q( ~! a' x4 ]14
15
时间、空间复杂度

" C% [$ U' V9 N; X
3 X- W- j& ~7 Z: Z最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
/ G6 Q; p* \/ E0 R. t9 n$ s( @( |7 Q最好时间复杂度—— O(n)

9 ^" z2 w+ v2 y+ I, i2 m最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
; }! }; @6 X# [  L& `# [& B2 W第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
# P1 ?7 g4 K$ b8 v…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)
# [7 z: k& V1 t. j: N/ I; _- t

) [) j* c/ f5 t3 z8 N

0 r* Z% |  x) `" a7 [7 ^
" g" @2 Q- K) p$ q（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：



6 Y  m. d& q# s% K2 Z) Y, g//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
; _+ Z* Z# M% I5 B6 u7 i1 I9 c" j{
& Q# l& c( g. B) d6 E0 B    int i,j,low,high,mid;
, {. N$ L4 ?; t6 z- Q    for(i=2; i<=n; i++)
. {, b3 y1 B! x  F    {
/ _' J8 _' E5 M/ A$ c, ~# p/ M& M        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
        while(low<=high){            
% ?# Y- N' p# w/ ]: d0 K; a5 L3 j" Q5 c            mid=(low+high)/2;
            if(A[mid]>A[0])
                high=mid-1;
            else
                low=mid+1;
" y2 @+ A5 d! j6 z/ h; F        }
         //--------------------------------------------
1 Z4 t3 J! \) t% w( b* J' X; ]; V        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];
9 D% G8 p. }6 f5 k' o) r. f) L
5 `/ t4 \- p8 ?: \! p9 E5 J        A[high+1]=A[0];//插入
    }
9 B; o6 ?3 g" b/ P}

1
) P6 `+ W! n% _5 }: ~! e5 W2
3
: c% b) \! f. G5 K6 T4
. X6 `4 Z  ?- ?7 [0 f5
6
3 u' j3 p  V5 r7 Q6 f) V1 m, S' a  x7
8
2 K/ s0 |/ \, v9
10
( T7 H) x$ ~3 i# J9 `* ^11
4 b6 b' l; P! r4 k2 x" j+ N12
13
14
) N3 ~7 I* o8 P1 \15
' c" U6 b& Y, K! c$ o16
17
1 e# b( y/ p/ A6 c8 l8 z18
19
20
! o2 h; I: L5 T! l1 f5 }4 H21
22
23
9 k! s; I/ O: T% C3 R9 V8 @2 u时间、空间复杂度
' t7 W2 [, G: D3 ?空间复杂度：O(1)
) c" D. i/ N; m& z: q1 x3 R7 H
+ }- ?; J% s) b$ w/ M) j9 c【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)


8 v; @3 v. V# Z9 D, }" s9 H' K（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

3 a' h" y5 E+ U7 ^  S  D8 e算法思想
) ]" l) D; |, K% o5 s/ O% W
) B9 y9 o; \- }1 }希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：

: o# D" v, F4 n5 b+ E

8 `# d, D! u& k; \代码实现：
& B1 O: x4 m; [1 w+ {
//从小到大
* p% W7 }7 M- |6 x0 ]void shellSort(int* arr, int n)
{
        int gap, i, j, temp;
! A+ q5 g# @' _! e/ J, c3 |        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
% T+ r; ^! c' |  ?& C! X" a/ M; ~        {
+ P( v9 V4 q; u* H& }  `7 u' V            //**********************************直接插入排序（只是步长改变）**************************************************
& e  p$ R  z2 {8 S, H5 ^            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
6 R) Q$ \7 W9 p5 B% f2 {                if (arr < arr[i - gap])
2 X+ {: d0 s- e) t8 {                {
4 _  O8 |  H0 f5 y7 _) P) C( _& s                    temp = arr;
; K* @! D$ Z5 w
                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
" j& H- q) L9 e5 w7 j9 I6 H/ O0 h! N                        arr[j + gap] = arr[j];
% k9 i2 B! ~( _( S3 N
& f; H5 G8 ~# v% h. S9 x) |                    arr[j + gap] = temp;//插入进去
2 G$ J0 W# M" p/ J* Z                }
            }
7 T$ o, k! S9 }' ~            //************************************************************************************
* n3 f6 S# N* L. e+ o& o* E- E$ {        }
: U' q, S1 W0 a$ Z}
8 m, t4 b& T4 \- z
/ g6 i3 Q, T( L; ~# f1
6 |8 ]; w. v; Z+ u0 D; `8 q( V2
3
4
5
! x. }7 q2 ~6 t. |9 `. r6
9 D) M* `2 o8 @, [3 b& r' I* v& K  g7
8
" ]2 \6 ]( _& f% a9
5 u2 y) u, v5 x2 R10
: d' T4 a8 {4 z3 _11
12
* G0 o6 ~$ j8 x+ R& D; o13
( ~/ c+ T: S  s5 d. j2 t14
15
% H- ^7 L! K6 U& A3 G3 S; V' ~, D16
17
3 |2 d" Q! E# {7 y' c! ^# O18
8 p% `& ^- T( `% r1 \19
20
21
22
23
24
3 z. H  W( ~* z0 K时间、空间复杂度
空间复杂度：O(1)
  _  q8 I* x7 T1 o5 ^
时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
1 p( b  R4 v3 o: o
* V+ I: q8 f5 R: D) O稳定性：不稳定！
- @7 j, J0 \4 U, l* x8 x# w
3 K+ G; w$ x2 V/ r2 _
) ~8 r' }& m! {/ h8 V6 d
适⽤性：仅适⽤于顺序表，不适⽤于链表



2. 交换排序
2.1 (稳定）冒泡排序
1 o1 f( W$ A$ H英文:bubble sort     (bubble 动和名词 起泡，冒泡)
7 V0 P9 W4 E4 I* x从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

每一轮比较会让一个最大数字沉底或者一个最小数字上浮
. _9 b! Y) ^) F- b
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

实现代码：
! y  v! J6 B' t
//从小到大：
) s1 {8 D+ [% Yvoid bubble_sort(int arr[], int len)//冒泡排序int*arr
1 n, P9 C2 g+ A{
+ q% S6 z1 N3 t; V3 g5 e- A        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
        {
                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
3 n( h3 w5 Q% ~$ n$ l& J                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
                {
                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
                        {
3 C- H9 }& r7 g- \0 o1 U  |* z6 `                                //交换两个元素位置
                                temp = arr[j];
                                arr[j] = arr[j + 1];
( [- H: e6 w* M) W/ D                                arr[j + 1] = temp;
                        }
                }
        }
}

1
. h% j" q/ x% M5 w. D$ p( T7 x2
3
4
9 h* y- r2 p+ t+ J; ~5
% c  \* Q$ a  U# E4 o6
& Q1 F, z3 `' w7
1 h* E  F" K* R/ `$ V8
9
/ S: q* n+ n6 D10
11
12
13
" t% t, ?. S# r5 {, S  u% E# x14
15
16
$ y' L4 U& D% j. u" L8 H- v8 m* V. n17
18
19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

  R% P+ f1 I4 h  W& n" I) a' r. P//从小到大：
* V8 z. w. H6 T9 uvoid bubble_sort(int arr[], int len)
{
        int temp;
7 s9 X' z- m: T- ?+ c9 j& K5 j3 W        bool flag;
        for (int i = 0; i < len - 1; ++i)
        {
$ U/ x- ~# Z4 p            //表示本趟冒泡是否发生交换的标志
                flag=false;
+ t" r: [! j! ~) A               
                for (int j = 0; j < len - 1 - i; ++j)
                {
                        if (arr[j] > arr[j + 1])//稳定的原因
0 L+ J% B2 e# U2 N                        {
3 {9 X! ?8 y; p0 Q8 P                                temp = arr[j];
                                arr[j] = arr[j + 1];
/ |3 y6 T- \2 A                                arr[j + 1] = temp;
% ~9 D+ m) M% |( i* l                                //有发生交换
$ B* e6 Z# z( i, K% v- j% [                                flag=true;
                        }
                }//for
" d+ W8 B0 n. \% m+ J               
                //本趟遍历后没有发生交换，说明表已经有序
. ?5 }6 N: ~  ]                if(flag==false)return;【1】
5 b" m/ J9 e0 g) X6 @        }//for
. U7 D2 Q' @! p6 S- G& d% Q( m}

/ ]. o* G2 ^) X" E  }$ X1
, u4 d. S, D6 G" c: [2
% Y+ \+ o) X! {0 R# {3
4
5
  |7 T9 t( w5 ~. z6
7
8
0 J4 G! X% A, `6 G9
10
11
- z" r: z5 D1 _$ p: v12
13
' k) T+ X- K" H5 h9 z14
/ M) l8 s2 R2 h2 `1 c0 y15
& ?8 Z7 \0 m% K6 }5 I/ \7 \16
9 n, A; `/ [& k2 e8 f; _. J17
18
19
+ f& H0 `3 \0 P20
21
22
23
5 R& a6 |$ d& F1 ]' u' L- K24
25
0 M% U+ D2 e& Z* Y; j  h5 f26
2 A5 j7 g  V( y2 u# D) L时间、空间复杂度
' p' M: G8 g4 l
适用性：冒泡排序可以用于顺序表、链表



2 L, q% J) H7 x  h8 E7 ]* [- z0 q
# G( V- P# x% G+ A2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
" U: j* H$ `: f2 l* D: A0 K. V使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
8 a3 T  {+ ?- J' U: g! ~3 X
然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

* H: s7 r3 c5 g划分的过程：

1 H" N) u4 B+ Z: L( `( [初始状态：取首元素为pivot，定义low，high指针

首元素为49
high指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置
$ p7 h& {: L- \& t8 m

$ M5 w; J. p0 e* ~1 r% v
' Q2 q0 ~3 y9 z+ x9 A

' }0 r4 F  U1 {1 U- {' r' a5 V- C// 用第一个元素将数组A[]划分为两个部分
( M9 y* h+ J/ D) q) [" G: Dint Partition(int A[], int low, int high){
        //取首元素为pivot
: x  ^2 u4 P# d' z8 S* h+ f    int pivot = A[low];

/ }/ g6 L# y& z5 T# O    while(low<high)
    {
- c+ W; m+ j0 C$ E) h/ g4 B            //先是high开始向左移动
8 m- q9 \+ @, V4 U( f; A: u        while(low<high && A[high]>=pivot)
            --high;
) W4 @# V. b4 [4 U) q, Y1 p        A[low] = A[high];
' p! E* F, x9 Y. _
        //随后low向右移动
        while(low<high && A[low]<=pivot)
8 z& A! Q$ r# _: N/ M. A! U            ++low;
7 J; ?1 L: G% t+ I        A[high] = A[low];
% }( [& @7 S8 G# m0 x    }

: `' U# ]% j# J7 H% M+ W    //low=high的位置，即pivot放在的位置
    A[low] = pivot;
/ S$ @1 w& L  m2 ?2 d! K4 }6 p
    return low;
. P2 b# _2 G  |! y5 m! A4 g}

7 u. z9 {/ d# j3 h- T- t; l3 @+ ~// 对A[]数组的low到high进行快速排序
void QuickSort(int A[], int low, int high){
    if(low<high){
0 ^; z: B2 G3 G        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
    }
}

# d6 W. x) c- |+ G) ~) @1
2
0 ^7 R! H4 [# j0 j- b2 w/ v+ L6 g3
4
5 @" L3 L$ i9 ]$ e. e7 p5 Z- ?5
7 X1 u- L% U; K; ~. @8 Z$ J% j6
7
  U6 a; D: Q+ z8
. {8 {: H( ]- W1 q0 p9
10
11
12
( F* B3 \# o+ V/ n4 s( m+ L+ }& K13
% G( m* ]& f1 [+ o# G7 m9 J14
9 n# x5 J+ r6 N15
! T+ d# F3 f. V7 G1 M2 f16
2 w. H# C+ [/ @" D: d17
! Q7 i, l# O; U$ k4 S18
  X/ w' O$ j/ z19
20
21
22
) j4 x# q& F8 }; q; y! w/ L23
0 L% z. ?- B' x. }8 _& @2 b24
25
5 X1 N! t' o$ o26
27
" ?2 d6 i9 |0 L* _' x28
" E1 z$ T1 j* Q3 Q29
0 O7 ?1 p, w4 o3 i5 a6 E30
31
* I' `; }* {7 T9 I' u2 @+ `1 i32
时间、空间复杂度

9 [2 t4 r; s/ K& `
7 F) y1 n; M1 J把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
# x* a/ `+ V- _
n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n
2 c1 B1 T$ F  i
- U4 g8 T, `. F: @6 w5 L. `3 U时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
9 Y% \$ _9 e: Y0 p$ |( L平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

空间复杂度=O(递归层数)
! C5 a# i' J" R最好空间复杂度=O(log2n)
* g" N( @7 g) U% a% d+ a) \+ y最坏空间复杂度=O(n)

7 u7 U' C3 B7 H) g最坏的情况
: y& X7 M. b5 z: g- B6 P; r
2 M( _! i, B$ ~5 V8 c' ~

⽐较好的情况

; r- v5 ]% c! L; F$ r
" j1 m8 \0 m) z4 Q1 a: H$ Q1 @
不稳定的原因：



( \  j. \' a/ u. ]7 l+ ?' K
. L3 i! L  ~2 v# f: X- |
3.选择排序
, Z& H8 S: i$ \! n选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

4 F) t& v7 i. U& a' \3.1 （不稳定）简单选择排序
* f8 G& c- |6 @* Y1 P算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置


( Y4 M/ F* `! {1 t  v" U% i
// 交换a和b的值
* p" Y% K$ k/ G. w" _3 b, @void swap(int &a, int &b){
. i, {7 m) B8 ~& X! ?7 z    int temp = a;
    a = b;
6 s8 ~) p6 v6 F    b = temp;
% s, I) L1 m$ u5 f1 I& K}

6 [  l  E& y( T// 对A[]数组共n个元素进行选择排序
  T6 f! {6 A0 c! H' hvoid SelectSort(int A[], int n)
3 D& o8 z8 e" e1 b$ K% K1 t{
! l* ^  Z1 G; I8 ^. u& O        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
) i9 ^7 M& R. [* z! {    {                 
        int min = i;
) P6 Z. V# M7 ?& Q7 c' Z) o' A        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
' d' k: ], O' ^: C( T9 c6 U            if(A[j]<A[min])
# ]' {, D1 T2 N: d$ N: i5 }                min = j;
        }
  U( h$ E2 t7 `+ J0 c* k        if(min!=i)                     
            swap(A, A[min]);
    }
}
2 t+ ?+ G) N* H( D
1
! x* u& @" G$ N, Z% d# h9 c2
3
; `1 K) j/ M$ x( y4
5
9 `0 W5 G0 x5 _, b6
# H7 g" f% j0 ^' }( y- v7
8
4 o% ~" L6 f; t3 @2 m/ k9
10
11
; `) u3 {, B0 a( c& n, W$ R! V12
13
& E8 d) b" F, W/ N: v14
15
16
5 z3 Q7 G: A' q* ]17
1 `' o+ Y( S2 ~18
19
20
21
22
补充：对链表进行简单选择排序
2 A$ D. }( f3 u4 s, K
void selectSort(LinkList &L){
. R' V4 U* }* v; [: w$ W, I    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
7 k+ c- n+ I) Q/ H% u% S0 I! b    while(h!=NULL){
        p=s=h; q=r=NULL;
        while(p!=NULL){
            if(p->data>s->data){
                s=p; r=q;
8 ^0 o& p1 f$ C# n            }
            q=p; p=p->next;
# @5 x( E6 j7 T5 ]5 n8 F        }
        if(s==h)
- y5 t3 D3 r' [+ p6 t            h=h->next;
; g* U) q+ y6 ^' O0 n        else
- B4 c( k( h0 r# E! x! C3 v            r->next=s->next;
        s->next=L; L=s;
% b+ q& M* s1 Z( s    }
: S: S0 h; p8 e}
% |/ ?' ^: z( V
1
% @% b. W2 l. U, s% {2
& e* Z" b9 H8 S! }3
4
5
; t% h: q( _0 l0 K3 x  g6
7
& ?% @9 Z; E4 v& p  d8
: m4 `$ q% ^( G1 L4 H9
10
, B# I1 T( T. c11
2 O& f4 B. A& [' [! u12
9 {) S0 H7 t; A2 ~13
4 ?6 h( j" F3 a4 Z7 \1 J14
8 R9 |9 V& u4 d' S15
) J2 W0 V; ^# K# d16
# C! @' Q, [1 V# L17
. t/ h: Q5 k5 O  M+ @18
& Y1 F: K( p* a  r" x时间、空间复杂度
7 |7 p" k% l7 ^9 E8 o
1 s7 }0 x% }, i/ z' L3 c6 h

. X; Z! @! F; R" ?/ [
适用性：适用于顺序存储和链式存储的线性表。



3.2 （不稳定）堆排序
9 s! a8 w( n& i- c7 o① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
4 }; ^. y2 i3 u. l: u每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
* F  M- G& j# n( q/ O' ]5 }


即：
若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
/ ^. A+ ^6 |9 G0 |( q2 N. r若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）

5 L& s0 e7 l7 s5 e② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

: D6 `7 [& Y7 ?2 ]# N5 P在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换
/ o  |8 |1 ~4 p% C8 y- Z
过程例子：


7 s0 T! o; E, E( `6 M
, B- j# F* }% }1 Z9 Z建⽴⼤根堆（代码）：



1 w$ t0 n: E2 y8 m+ P3 f7 s  i// 对初始序列建立大根堆
" u& Z9 h5 c! ~: t3 H3 r0 u& i% Yvoid BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
: f/ P% w! v1 r; B* E        HeadAdjust(A, i, len);
7 m( C- [4 t8 C- x, j) @: s}
6 k9 G, `4 }( d- i/ u6 }8 Q
// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
* E2 Y. E! ~  z* f& ~4 e: F    A[0] = A[k];
    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
1 ?1 a3 T' w$ S            i++;
& w& s: C! f4 v, [6 E  v        if(A[0] >= A)
            break;
        else{
$ U% C* N- ~3 D; P            A[k] = A;                        //将A调整至双亲结点上
! D3 T5 y* q/ R1 ]/ e7 D            k=i;                                        //修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0]
% {+ x( C& d- H1 A; y6 k}
4 u3 }0 S, n! o8 B" X, ]8 U( ?% u
1
" C7 _5 l- ^1 B2
, w. X+ L0 |0 b( z4 {3
4
5
; c+ N. H- b" @9 U/ ^1 N  |9 `/ I; y6
7
4 X# J/ w* G/ _. g8
9
10
11
8 X8 J3 t2 U/ n. [( D4 [0 }12
13
14
15
16
17
* n" ^0 Y/ E0 V3 O8 `8 W# _18
19
20
, }* Y* ~) c; \" i21
" ]% D+ m5 u: c5 ^- Y③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
/ g9 p# o" J& F* N
9 D* q6 O) S) ?7 Z! y/ |6 f/ `堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

过程：
( J. f6 o/ ^3 p8 M$ L" F
) z- m* ?, B% j8 p3 Q" {// 交换a和b的值
" z: R& V; U* u% ]! [' o8 Tvoid swap(int &a, int &b){
    int temp = a;
/ l$ |. r& r1 t; x    a = b;
6 o7 `' D* E2 i0 c0 c) F! |' I    b = temp;
}

// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
        //初始建立大根堆
    BuildMaxHeap(A, len);                
9 x+ C' m  U3 {6 \. s
    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
. _( b  u* Q4 N9 T# \6 h& p    {             
  O# g! g% N( m3 a' {        swap(A, A[1]);
; G: U5 e, Q/ {        HeadAdjust(A,1,i-1);
    }
! K+ o+ D1 y+ E}
! f4 K: W! m; b. t4 Z8 V' T# u
, _, T: w! t2 [3 q! h. y1
1 ]9 L5 u6 w8 b2
3
4 e& K5 J' d% J& a+ y4
5
) r2 c9 D. l" T2 X6
7
8
. u" w% m& ?" _9 r1 `6 k4 c9
+ f7 ~6 q) f+ p. M# `% z7 s9 z9 ~10
1 P3 J) j- O: Q& c) s. h, F11
9 }2 F2 ~* G7 ]; x12
13
% r4 N4 _4 H* F4 E, j# @14
15
16
8 ~7 ~6 d! Z4 R% Z2 x7 x9 v17
# [/ ~9 U" m- u& C& R# R18
; f' U& _+ j0 T4 A19
时间、空间复杂度
* }) b* [) @' S$ d; P0 m% G建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
; [% n: n7 P! {1 y故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

  i7 U: h/ [$ \% m* p2 A' I4 P空间复杂度 = O(1)
+ F/ |+ K5 Z. T, i1 ^: K1 M
结论：堆排序是不稳定的

2 F7 \! }  z4 z4 o- r2 e- e: m: t
④ 补充：在堆中插⼊新元素
& M4 G  }+ J7 Z对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌
4 ]" Y! K' }# Y# e# @


⑤ 补充：在堆中删除元素
' u- s2 n, v4 O' Y# a+ z+ k0 L% A被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌

$ E) f! m( W$ |


) C4 i2 b" o: s: @2 T+ y
- d) D. M0 `: w; p! v4 M# w/ Z4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个
! M2 v' G! ~3 u1 U  f& I
$ j& d7 X" L# G: s& R2 a① 明白什么是“2路”归并？——就是“⼆合⼀”

) @  L6 S# @: r3 [/ C" v8 Z多路归并：
; q) o' g, Z. e8 C/ o! [
' N! p: N5 M0 W- k1 O5 f+ n$ s
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
  N% C3 k# b4 e& k4 h; L4 I
9 b% z  g5 J, e8 f3 d" K2 @B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
3 \6 A7 O* M$ ~
③递归进行分治思想【MergeSort(int A[], int low, int high)】

/ z' T$ ^3 s8 d: N5 A
④ 总实现代码
0 H& u. Y' I7 h# l4 j' i% G: I8 s$ ~// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
  d+ }6 |  U  n/ C" D  k  n- Y+ Y! W" @
// 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++)
- W; d- ]) @+ z! _) c* O        B[k]=A[k];
. q  a+ K% N7 V& S) r  U( J    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
: [0 |# B& z9 S( B6 [4 S+ ]        if(B<=B[j])
* ?6 t% X) {; s# h8 g            A[k]=B[i++];
4 ~. b: q- d$ k' o' U& b        else
# ^; h8 u3 _9 }' N, N) D            A[k]=B[j++];
7 ^: w8 ~7 B. [9 _: ?    }
- A" L  k; o# ]1 o    while(i<=mid)
& K1 X( e5 }5 i& B        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
}


# x7 {; W- E4 F7 n// 递归操作（使用了分治法思想）
void MergeSort(int A[], int low, int high){
    if(low<high){
3 \0 ^7 c- R. d. e! g' \  F9 q) e        int mid = (low+high)/2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
    }
4 o3 ^* K6 _# w6 _( Y}

. s$ ~9 k# j# m: ~1
. X2 z* {1 Y/ M% c7 ^8 n2
3
4
5
7 c* v2 C# R/ E; m, Q' c3 z" g6
7
5 f" s* c* A6 k# |8
  c$ J6 |. F, p1 [# e: g. H: s: S9
: c5 g! D, B, ~! N: n0 {6 O10
11
12
13
8 V( n$ D% f- |14
15
. z2 h" a: |4 V/ W9 t16
17
1 s# O. o! {) s9 S0 l/ M$ C2 u: t18
19
20
21
22
23
# S8 R6 Z, p! w0 r. N$ m7 q24
4 u8 h) r" C, [4 t1 V" V) [! b7 R" w25
3 p( m/ x$ q1 m7 f26
27
1 F7 `2 K& g/ X28
$ G5 c# M8 P1 C29
30
6 f/ c! Q/ F8 I, \2 R时间、空间复杂度




/ ^* s9 j7 v" i8 v5. 基数排序
直接看课本的过程图来理解P352
! b) f. L" Y: c# r6 e; q
再看这个例子：
0 q5 M& A, P2 Z

算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
$ w* T9 m  h7 V! e; b) r4 \% E分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
2 i2 S4 W4 I+ J) G5 W3 B2 _3 W( A) R基数排序擅长处理的问题：
①数据元素的关键字可以方便地拆分为d组，且d较小。
4 |( b3 v* P/ d/ \②每组关键字的取值范围不大，即r较小。
# F% p; I0 K1 m, A! g- S: j$ p③ 数据元素个数n较大。
算法效率分析：
3 V  N- T: g7 W& N时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
1 E8 i, b3 `0 [9 a1 h空间复杂度： O( r ) ，其中r为辅助队列数量。
+ f8 H8 {$ K. t5 g稳定性：稳定。


内部排序算法总结
$ P3 i: X; O3 Q
7 W. G0 ^6 S  T5 Q3 J————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* s6 ~; _7 R& T3 k5 y6 j原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969

* t, e* }9 E; H4 \& f
1 A# H* d& B7 `8 j( B* ^# L0 U