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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
1 d" _" r7 R2 ~: V排序
1. 插⼊排序
/ \9 e  [1 S  ^$ u1 e（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
1 h" {7 u  w5 r! u时间、空间复杂度
) v# W/ j2 q4 W3 R# L/ Q0 w8 {（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
6 }8 Q5 E$ A9 e3 Y- i. r3 J时间、空间复杂度
6 f* [, }7 ?( t- \$ E3 r* |- W（不稳定）1.3 希尔排序【多次直接插入排序】
% G+ J! l. S8 s3 F$ v% x时间、空间复杂度
2. 交换排序
2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
  v6 D4 T1 x+ {% s; x( Y9 z时间、空间复杂度
% c0 R+ G; H9 `3.选择排序
: [4 g/ d- ?3 d1 Z* y7 @3.1 （不稳定）简单选择排序
9 u8 y/ r( q% k# P+ c时间、空间复杂度
; o8 e5 R# n5 q3 X! B/ A3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
' v$ w) Q2 Y; |; U  b6 o② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
; z1 `, Z! L3 T③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
6 x2 r$ ], y4 B, ~4 R! |② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
: ~, X& `; ]% C9 K9 X- f④ 总实现代码
时间、空间复杂度
" }# ^, M. F: e: \3 A( h; I8 c5. 基数排序
内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
, H; J. f" }: P8 r7 t% R! n
排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
1 i! ^' P; R' {7 y
8 U) ^% ^1 \) _" t2 p- r* E, ]+ O" c算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
2 X6 O" Q# p  W! R5 x; _稳定的排序算法不一定比不稳定的排序算法要好。
0 c8 R+ g; Y9 f! k
3 }4 R  f6 C" V' J) F/ j
排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
% a& e/ d. |1 f: ?! L* F$ V7 y
* }& k! M0 b7 x8 X7 b( R' w各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
+ N6 h& d& O$ Z4 n4 p! g( r) H
+ w; Y! ^& [3 E7 y5 ^

& o; o7 l9 I% ~" \, {7 h1. 插⼊排序
$ u, K3 w0 I2 v（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
- l8 O! R! u. B" E) k+ a3 N基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

算法解释：（从小到大）
! {* x, R; v( z) r: \1 m. N" a# _
* n/ I9 c9 \+ y+ A
算法三个步骤：

( K! v; N9 ^3 B9 o先保留要插入的数字
往后移
5 @+ l3 z9 Q5 F8 S插入元素
. l6 ?8 P7 s, f& D9 i8 M7 s8 g% S$ z# f
: N3 S( p! B* R// 对A[]数组中共n个元素进行插入排序
& I8 t4 |+ @$ N* d# k1 T; m& {void InsertSort(int A[],int n){
    int i,j,temp;
; Z7 H+ o0 @" Y, {, P- C: S    for(i=1; i<n; i++)
    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
        if(A<A[i-1])
. H7 S/ F9 |# Y        {           
            temp=A;  //保留要插入的数字
+ B2 A! `! @- `0 q& J+ `4 U( C5 e
4 @8 J0 W' g+ ^1 P            for(j=i-1; j>=0 && A[j]>temp; --j)
2 f5 A5 }; r1 g1 U: Z6 E                A[j+1]=A[j];    //所有大于temp的元素都向后挪

) b2 m2 e  U8 f  L# w            A[j+1]=temp;//插入元素
( }/ w+ Z6 b- b: V1 s) h        }
    }
}
# D; R4 s1 _: a- ]; P) V3 O5 a
2 y5 {0 T6 e% x( e. P7 ^9 Z1
2
3
4
9 @: g5 f9 L/ c  o/ ?& A2 w2 ?5
6
0 @" n: R6 Q3 O: A! I7
- [3 A% Q$ p/ R% V7 c8 w8
9
5 u6 V5 b# E8 H1 I" T8 c: l10
11
; d3 @$ D4 Q6 H; V7 W12
4 }2 O& n3 [, _# P1 R8 j4 I13
% v* G7 {1 S& F+ Y2 D14
15
# x. X2 x! t) `5 ~16
4 [, F& M' o( X* s% }& q17
* a% r! J9 N  v3 F5 Z, I" P用算法再带入这个例子，进行加深理解

% l' A3 }' \9 s' `" n1 q
带哨兵：
# A6 O0 Y4 P. M, k
1 X- h+ w2 K( E% D2 A
% I3 D" T" O. ]$ Y补充：对链表L进行插入排序
- M* T: q/ `* q8 K
* V* K( ?0 M7 U+ |$ D& E* v4 zvoid InsertSort(LinkList &L){
' Y  w8 K$ ]. J9 x    LNode *p=L->next, *pre;
1 Z" O" y  j. l0 D+ h. t    LNode *r=p->next;
    p->next=NULL;
8 l1 v# `2 ?8 I  r9 ?    p=r;
2 Y) v; N1 e8 _5 w8 ?    while(p!=NULL){
3 V- C/ N" F' l* G/ a9 N        r=p->next;
        pre=L;
+ z' X, O$ t; |5 F1 a' o) b        while(pre->next!=NULL && pre->next->data<p->data)
" j: I5 X: j' a# s( ?/ T1 }            pre=pre->next;
0 g2 e; y( F0 ?5 B        p->next=pre->next;
        pre->next=p;
- g: S: G& @  H& y8 D% L  r        p=r;
2 G* H' ?, v* V3 l0 _    }
}
* n  K) `7 w$ C! p+ V0 m" F1
6 y, p# s  Z7 T5 Y' _0 Y+ p2
; ^1 ?3 D4 I7 z; Z# o& v; b5 k3
/ X4 o$ B) F$ N' p! ?4
5
6
; ?+ p- B8 `$ p0 ^7
8
9
10
11
12
13
14
15
时间、空间复杂度


最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
: @( E% C! Z: G, a% E3 h' ^5 o最好时间复杂度—— O(n)

6 i4 ~! F0 K2 s6 I; e最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
- f2 |. q$ ]6 l% N第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
/ N0 `1 Q) T0 t& O8 E( V& X2 n最坏时间复杂度——O(n2)

/ @# u9 M( b" ^: ^! C- d
8 o. G& r; E, `6 Z7 O
6 x% f1 P, @$ |" f
5 T$ b# r6 _8 D. ~( [3 e
$ p6 i% `! _# p, [( G1 t' ?1 Y  t（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：
  _! u5 |8 ~* l/ K8 C3 R) t: D

! q/ I# c1 ~# d" B% {8 {
//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
{
    int i,j,low,high,mid;
. G2 \, g& K9 x, v% d- N: z    for(i=2; i<=n; i++)
* L4 w, R% k5 X9 \3 g    {
$ p1 c, z3 h+ P9 I; w' P& n        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
$ H+ L3 F. f2 }        while(low<=high){            
            mid=(low+high)/2;
) t# D' G3 H/ Q7 {' A* j) J% o            if(A[mid]>A[0])
6 v9 Y  I- G& n" O( y                high=mid-1;
" M& ]& A5 D& g4 v            else
                low=mid+1;
1 M! n/ H" s- N) |        }
$ P  ?- p  ~; r         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];

' m6 n" P1 i( X  C4 T1 L        A[high+1]=A[0];//插入
! G3 r$ f8 c  v8 K+ T  _0 ^    }
}

1
1 ]7 U9 x8 G$ y' Q; y2
3
4
  t- t0 T5 J( w  N5
7 i4 K! A1 A2 i) S, z6
+ G( G- V8 e  m& }% E8 l: t4 s7
4 B' E5 _# @" w8
; s6 o" X! f) n( L9
10
11
7 N4 B7 }; A* {% Z& X# |2 L12
13
14
! t8 s9 m, ]' V8 [# M15
16
: ]* X1 \* Z4 _) o: J" W17
& W9 H9 z" i0 D+ M" B$ x18
/ f; e0 T, Q( [2 x% C9 _19
3 F/ K" a' {+ ?20
: }2 g* F, T7 W# J, e7 K) K$ N- x# M21
& i' z' W- n& g1 H: \22
23
- A. X! I: B5 H0 B& J时间、空间复杂度
# X7 }9 _# ]+ _' `. D2 c- n空间复杂度：O(1)
& ^. k  M$ m' L
3 J- z) k2 F, }. p+ l4 G【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)

& J, n& A* P# P% Q# Y
（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
& j6 Q  ?+ @5 k% u/ Y5 _* y/ e
1 A7 b/ S) b4 I* U算法思想
! d6 N( j; \& L( i$ O: _7 @% {
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：


: [" Y" [  ~( C5 v  J
代码实现：
5 s0 y: a- J8 {8 n, e7 f' b
//从小到大
5 |8 o2 G% |& V8 qvoid shellSort(int* arr, int n)
$ S2 t5 y  Z3 ^4 a0 {8 N{
& H5 R* R. T$ {        int gap, i, j, temp;
( ]  v- k! ]8 K        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
& [3 x  i: R4 H& G( K4 _& l7 X& h        {
# M  K! S+ b; y3 q            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
1 W/ e5 o6 o( r% ]) q( O  E% @            {
                if (arr < arr[i - gap])
                {
                    temp = arr;

" g2 |# j5 `. z: P# j' b                    //后移
& k2 L2 x& x9 z& z                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];
* [; `+ ?: o, C; w
                    arr[j + gap] = temp;//插入进去
                }
/ A- y0 u& Q* M+ I& r1 w& |            }
            //************************************************************************************
        }
}
, q2 g# v) i& F
  W( t$ w; ?- _" e. Y; H4 B' S1
2
3
4
4 v! M0 d8 H4 s/ ]3 K: m5
1 G6 F* H4 S7 O9 o& Q6
7
; l* t, \, M3 ?& O8
4 x, m$ d; L. ]7 e' w& v3 T9
# ~* E0 K0 ]2 b2 X10
7 e6 I7 v: Y7 T2 B9 ~/ _& G11
8 X6 y# M' U/ w' {( W) ^12
+ f! o& x- d& }7 n4 m9 f, W13
4 v: }- R( |1 c* y' x; n" Q14
15
16
17
6 q2 H! n$ X7 M1 P3 S18
19
( O2 i$ j6 d; K1 ]20
) s  i$ i  r! y21
. B! d! U9 Z% K22
23
24
时间、空间复杂度
空间复杂度：O(1)

- e6 Q/ K: J  B( s" n' n9 z5 }时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)

稳定性：不稳定！



适⽤性：仅适⽤于顺序表，不适⽤于链表
9 n! Q, o4 f" _


, w# u$ i' m+ @2. 交换排序
) @) D8 {9 C* [( C3 ?* v: P, I2.1 (稳定）冒泡排序
% K1 n6 t* {' g! M: x英文:bubble sort     (bubble 动和名词 起泡，冒泡)
5 U4 y' A+ {) e0 c& I: Q从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
& o# a$ z% Y* I$ H9 M7 V% _
  N2 U  T2 c8 O% L* V/ o每一轮比较会让一个最大数字沉底或者一个最小数字上浮
9 Y+ ~! d4 Y3 L: f! d
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
: m$ Z( ^9 `7 d0 m) q6 E
! Y" K# ^$ E. j1 t实现代码：
( g1 C2 E( O6 x6 x1 `
3 J2 E" X; W; M( Y* u5 c//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
{
2 ^' Q8 u0 W! w8 r5 B- ]        int temp;
        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)//相对于上面的一个优化
. i( ?; h& j' o$ O' F                {
$ k' z  I1 L. {4 w8 z1 Z                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
: \/ D* ~7 K, E' G) w; U                        {
: v* g$ `; A0 D                                //交换两个元素位置
3 ]1 `% ]3 Q6 j                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
" |5 k- Q, k7 j$ Y2 D! B                        }
( p4 N+ n6 D4 f/ L' p* L                }
& [& C' H, e3 a' m1 k0 t        }
2 y+ V% ]' _( j9 f}
: c% b, K/ o' S% J  e
1
9 T2 e& T" `& ]! \. D; L' h( L7 C, K, r2
3
! r5 g( ?0 i+ i. ~9 D5 n! ]4
/ Y; O5 c1 y6 z6 X  S5
6
, w+ E# v4 l/ x7 `5 ~7
8
9
10
  b5 V9 P( ]/ j. W( G3 Q' {11
12
13
: i* ?3 k, c  p8 {14
15
16
, O% z/ |# v2 d9 {17
18
19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

//从小到大：
2 U- Y$ p8 I$ n3 Y% {$ y2 pvoid bubble_sort(int arr[], int len)
{
% T, v' o! D+ E5 o3 a, H1 F        int temp;
        bool flag;
4 q: I; w* ?; d8 G* ]; k, \7 e        for (int i = 0; i < len - 1; ++i)
        {
) y7 W1 z2 J" I2 \( U1 {            //表示本趟冒泡是否发生交换的标志
                flag=false;
               
& O- \% J* `, A6 j. t2 I- Q                for (int j = 0; j < len - 1 - i; ++j)
                {
1 Y/ f0 ]; V0 C# d( k8 I                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
; R( Y: w! h0 p" \                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                                //有发生交换
                                flag=true;
                        }
- G" V3 s* ]: H+ v4 ~  V2 i                }//for
! N. e, J; e, T& C- c5 s( Q               
                //本趟遍历后没有发生交换，说明表已经有序
6 c) U% D0 S8 V/ N; r                if(flag==false)return;【1】
1 l( l: o0 C( J        }//for
( h+ U4 i" W( V+ e% i. v8 b# A}

1
2
+ X5 f/ p) `( o( m% V, B4 W1 l7 R3
1 q7 U7 K3 W( f: i! j7 _% b4
/ f5 e7 i+ B) C. E- P" ?/ X, ^5
7 Z  N, i+ Q/ S: T9 F  A% n, {6
. O( b1 h: T# I9 S  W3 X7
  h* Q2 F% Q! z( m, P  N8 f8
9
9 i  j; D5 }4 o( X$ P# |' u10
% m* g; O* h+ e! o- }5 ?9 P11
7 B' ]% s8 w& ~3 H) X7 j8 I  o  T12
( l8 C" c  I% F; V13
( h0 n' H$ O( r  ^7 o3 y# T14
) L) O3 M* H9 P; `, X5 w15
/ y8 ?4 p; g6 I* ]# M$ R, {16
! r% l2 Y" b8 X! t7 N+ r1 j17
18
19
" z* L  u% }% |& k3 U8 i7 B4 g20
21
( @+ n& E: N8 H& s22
23
) G. k2 y8 Z0 S3 i- m24
25
26
时间、空间复杂度

适用性：冒泡排序可以用于顺序表、链表
- T8 M  a5 A$ L. `

) l( [: O1 J& a! U! ^" \9 J

2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
/ J5 G& e2 e0 b. v9 Q. Y0 F算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
2 v" K( r) e6 H$ s6 T通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
! W$ a/ \7 `6 ?使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

$ S6 ?, G; e* t8 M# m然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

划分的过程：
0 T& ?9 X- w2 G
* y- o& `: D5 C" @" M  m初始状态：取首元素为pivot，定义low，high指针
# y' s- U7 U6 T- O# E8 f& W, w
: A/ ]  P) C& h首元素为49
# g8 w. j1 F- j1 p, i% t0 Shigh指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置
! T# i+ z, o( l7 P% y, ]
# D" g% P5 W( k5 s+ O" q

$ [! `& B' u, T' P6 e% e; y3 A
$ r2 a0 X; G3 X
3 \' a- \' ]/ l% X// 用第一个元素将数组A[]划分为两个部分
7 B) i& W; i* l! Wint Partition(int A[], int low, int high){
        //取首元素为pivot
    int pivot = A[low];

    while(low<high)
# O/ ^* R# R7 B% J5 `; A( T, y6 Y    {
, l% T/ A* S5 Z# _            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
            --high;
) G" Y2 }. \: {( ]$ n1 X6 W' I' L        A[low] = A[high];

) |7 X4 a& U" r" C  |  j9 r8 B, X, X. e        //随后low向右移动
        while(low<high && A[low]<=pivot)
5 w+ [8 g; s9 v3 d& ?# L& {' \            ++low;
+ X1 |% G! M- d/ }0 S        A[high] = A[low];
# y- r- L  W5 S$ t7 [8 h8 X+ v    }

    //low=high的位置，即pivot放在的位置
    A[low] = pivot;
  `5 B4 B% o* j2 e8 B5 ?8 ~
    return low;
}

/ ?! r9 _" L+ i/ D9 Y: `6 {0 B* |6 z// 对A[]数组的low到high进行快速排序
void QuickSort(int A[], int low, int high){
2 G7 b& n" h# f$ G    if(low<high){
* n1 g% d1 i9 B% G        int pivotpos = Partition(A, low, high);  //划分
* J( w+ ]* ^  [1 K) Z+ }% H        QuickSort(A, low, pivotpos - 1);
3 {" n# o6 m: U9 W- V        QuickSort(A, pivotpos + 1, high);
! N7 j  K7 V- y; {! U' w; H    }
3 p$ h6 {) U5 A2 b}

5 N% U# V  U! ~2 K; |1
: N0 Q% _1 \7 @2
1 |8 K: A* ?% C) H- F3
4
5
6
! }& `/ w( v- k# L! j8 \7
8
6 n0 P4 e( I" i& P  A9
10
11
1 {/ S$ R9 _9 {# S: a! F1 T12
6 c+ O$ a; L* {' d2 I& h: g13
1 k. I. h* j5 G! R" K14
- o/ g2 H# ?& l5 M4 j15
# O1 b$ V8 P8 ?4 V/ }16
% y2 V/ X9 N1 Z9 L% m$ U17
+ R2 T( y' P; }6 G18
19
20
21
22
23
3 A( i3 X( V, Q5 D; s& @24
* Z) y, e( c$ F& d( m/ ]# f4 E$ \25
* Q0 N% s4 z2 I  ^" A3 ~, ~3 D( u26
. B5 Z' `" u- q27
  J4 G: B, P7 I6 B28
29
: k) j9 f8 f9 g30
31
. H: @8 s6 L5 G) p32
6 t" T2 g" a* `5 x时间、空间复杂度
+ A; E$ l! W8 }# T, Y/ B

3 e& Z. q4 Q* M& e把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

# f  M+ l( K. P. G/ {6 [n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

4 E1 p. r2 q& u/ V时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
, \7 K4 g4 g( X* ]9 Y7 _7 N最坏时间复杂度=O(n2)
, _2 R" S0 |  S: J- S: t! N6 q平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)

最坏的情况


( y7 \( D6 N  x: X
⽐较好的情况
6 J2 X( W" |% v2 J( {


! {+ p/ I- s. f7 w, w不稳定的原因：

6 |) K0 r+ Q* M. P8 ^& `6 m4 q' E
8 w# C( D! m+ _" r
7 _) T: D( v1 O. o  e0 c0 M! Z8 \

8 [% Y) m; R: z3.选择排序
' f& l( k5 D% ]! u2 ]) W选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

- }  \/ e) W" [5 I9 s! g3.1 （不稳定）简单选择排序
4 |! `& j. l8 t, O' P  l/ E算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
( [- h. y' U# F0 K% p1 x
% z2 p  t3 I! M
8 Q, {; p) U9 k# ?! A$ }
' Z: B3 K; l6 r7 C, f) J# C" l// 交换a和b的值
void swap(int &a, int &b){
' ?" l, V4 y( e4 Z    int temp = a;
2 H$ {* d/ a4 V8 d6 n    a = b;
, v+ P1 O  B- T' Q7 I% E    b = temp;
}

0 S1 m7 ?* r: H" M* Z# L* u- Y$ L// 对A[]数组共n个元素进行选择排序
' Q8 S* C1 `* y! Q$ Pvoid SelectSort(int A[], int n)
: n3 _" r' p9 A) n{
        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
- a! ]: ^6 T( `+ }, d4 N    {                 
        int min = i;
% X6 i" N. G9 ?+ L+ s        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
+ m& d) v* [* O6 }0 E! Y1 @- O6 [5 Q            if(A[j]<A[min])
& g% g$ G' K2 j  g/ f- {% l6 i                min = j;
' J! R$ y1 U$ z8 i' D4 ~( {4 i        }
        if(min!=i)                     
            swap(A, A[min]);
  J9 i  H8 }( N6 s" g4 h" ?' [    }
}

5 D) [6 X. S% T6 a# J. [1
; R4 h8 L* a% m9 w  F8 i2
* E. z7 W' z& U" g# |+ R3
6 {" {" P* w4 e5 x  w8 [9 [) y& Y4
4 y# u7 w6 ~9 N  s) R& }5
6
7
8
9
10
11
1 E. y8 O. X* P$ T12
% `& R& |& q& U" \0 s$ c13
3 C4 [% M, P+ \. S- C6 S% O14
+ _0 ~8 l& l+ t8 M) L: y15
+ Q/ {- f" N( s" }! \16
5 X9 J  ]5 n( R9 l% b3 J17
18
19
( |' p9 L* R: r5 v20
0 T' v0 l; R, \- R0 s$ d9 N21
5 F9 e4 E  F/ u) n  N/ |0 X* C22
补充：对链表进行简单选择排序
9 x/ ~6 J+ T5 r6 |8 e. |
! Z& e& \/ h2 s% E& q. \void selectSort(LinkList &L){
& h: ^" S/ R# D$ t7 c' |* E7 W    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
    while(h!=NULL){
$ k! Z6 u9 j& r# g! {# Y" h        p=s=h; q=r=NULL;
0 Z, E, `6 r  o0 I: y  B  H        while(p!=NULL){
            if(p->data>s->data){
                s=p; r=q;
            }
* z* f: O5 j* L8 |2 x            q=p; p=p->next;
        }
        if(s==h)
/ m* y% g' [# F3 s            h=h->next;
        else
9 r  V  i  V5 U% Y% E- X0 g6 K2 }! s            r->next=s->next;
+ \3 |3 q* M# k0 {6 w: o        s->next=L; L=s;
. P3 q& f9 ^; R    }
1 z8 p9 Z7 u, G8 T, `4 B}
6 G$ y$ z- b/ U- t& t2 |  |+ T' G
1
2
" N% J/ g: e" ~# s3
7 Q, |( Y! A. L4
8 a' l+ |* J8 e5
6 m- x/ E5 D* r* `- u; o3 G6
7
8
9
10
9 C4 r- v* N  j9 g11
12
13
14
9 d7 H% i& I  `$ {: ]' L+ B15
16
17
9 k! x3 e+ q" a/ G9 i2 q* h18
9 h3 `. O5 m# s0 {/ M$ O  d* L时间、空间复杂度
; Z% x1 v, A. W. ^* m, A
- q# c6 z+ U, `) B
6 b5 D3 I5 ~( p" f" ]/ C" w

" t( j# Z( g  C8 ~( `6 l( g, A适用性：适用于顺序存储和链式存储的线性表。
  n) R2 o- F! c- j" o

+ N* L/ M8 x* ^: W& J3 c/ F3 l
' v0 Y, G( J/ i3.2 （不稳定）堆排序
% R+ ^* R& J& ]2 A$ E) T' T0 m① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
4 c7 J& v0 d% P) i每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
# B( |: J3 e; g/ B6 ^* B% D3 P1 ]或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

; m+ ~5 s. P" ^9 {3 v
& A( Q8 t9 h" d. ^. S
即：
5 V4 r- {8 V& @% {, `; w若满⾜：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）—— ⼩根堆（⼩顶堆）

6 v; \! D: \0 C2 b② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
  N9 u, p* B( \- y% Z* c思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

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

% Z( W; V  W+ F: R" X6 y" U检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

3 H& ]8 Y- d7 y5 ~) ?5 @过程例子：


" p, k+ t) h  x
建⽴⼤根堆（代码）：


0 [, R2 Q; `! e; h; n
' ?; V) t: A" r7 A+ u/ r// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
% C# j& R1 b; ~( L        HeadAdjust(A, i, len);
+ {! |% L) i  _7 a}

2 N# V1 Z# F  [* B. P// 将以k为根的子树调整为大根堆
+ g; j; x! h6 l# e4 E# Nvoid HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
/ d" Y8 c$ Z  b; @7 Z    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
            i++;
        if(A[0] >= A)
: V9 Q9 e" ~: k$ u: j            break;
! ?) E- h( V0 ^8 C  l9 T        else{
/ j* f4 L  u  \; a$ r            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
- E. X4 |: q7 N! m        }
    }
    A[k] = A[0]
; L6 q+ Y+ {* X( s/ _}

$ U9 d" N! a- C) e! S) s1
5 y7 [  q5 T$ u5 `2
3
4
5
5 R2 k" i" |/ X/ n1 w' h* F6
' J: ~+ Z4 f  v$ |$ |* |; D7
- M% w2 x. U% @2 q" f: \! K0 ]% ~8
0 e1 H* k: r+ S& J9
10
) _$ ]) C3 X# D: ~; _5 w11
12
13
+ X  l; H% s3 ~2 ?3 l: p$ Q14
4 u3 B) a6 X6 `+ j0 }% ]15
16
17
1 s! Y' _3 f. c' Z5 `9 u18
19
2 u* t' ]: P. z20
21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
0 [/ Z- b9 W# p6 n) g
堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

" p  J5 x9 ^- P过程：
, X5 s2 _1 P9 w1 ~( r9 c6 Y5 I& ]( R
// 交换a和b的值
# q2 N: c4 O" p3 H& z0 X: b7 Fvoid swap(int &a, int &b){
    int temp = a;
    a = b;
. L# Y# ^% }) {2 s9 S0 B    b = temp;
}
3 m3 r8 x4 i  ~! q: a% H
' W# y! _5 e* W; u  K4 u4 ^4 A// 对长为len的数组A[]进行堆排序
; X& h+ _9 W0 Wvoid HeapSort(int A[], int len){
7 H3 s9 p  P- f        //初始建立大根堆
+ Q* x1 P' [/ ]6 [    BuildMaxHeap(A, len);                

1 z* q6 X1 h$ Y4 O% o6 Y: \8 x( J    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
9 b" `3 U+ C" K; }4 t! t    {             
        swap(A, A[1]);
3 s9 t7 S7 y! {/ H        HeadAdjust(A,1,i-1);
    }
0 U2 B& y0 W. H  a}
) y$ M! d7 ~+ G+ n1 O
# ^5 z6 N% w9 x1 d/ E& D1
2
3 j& {9 ^8 `* s' ^8 H3
& L( I( d" N4 e# t" e; M0 a0 f8 U4
! d/ z( A5 M: X5
6
( z# S) X8 y; D$ V7 K+ `7
8
4 U9 j& m+ i. o/ C9
6 e* n% Y& |1 \/ U# }, A) N* J10
11
5 {/ z6 I0 a4 C' l' n7 ^! z$ r12
" S8 g. U1 a+ [' i! D- F2 L13
5 q, h% v5 ^$ O9 ~8 l14
: L/ y+ d/ f4 @! Y/ L$ w15
16
17
18
19
% Z3 B2 p. p# ^+ J时间、空间复杂度
. f/ k" c7 X* e3 Y建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
% C% I4 G, t7 _* w4 [. Z
9 d* h0 j) `' E! v$ D% u空间复杂度 = O(1)

结论：堆排序是不稳定的
2 ~- B9 J3 T/ P- }2 R4 i

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

! i* _4 ?4 U/ o: k) `' ]5 }" a6 V
$ u& W( @$ e7 k) B, ~
, Z1 s9 J0 u5 O7 {4 ]: h⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌


" b, ]/ W2 L) A' ]

5 s$ D! r' b6 }' L6 b
4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个

& q" X- n) T$ x! o+ q7 w  b" I1 w① 明白什么是“2路”归并？——就是“⼆合⼀”
6 N+ x: x7 C+ p4 q* o. F
多路归并：

; a1 o) P9 g. S8 ]# U: `
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
4 K. H/ u3 d. u  z; [/ p
' g. x& S; H2 ^8 ?) F1 J5 }B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

③递归进行分治思想【MergeSort(int A[], int low, int high)】

$ `% `' A0 d+ @
2 G) s  L) B' c9 G+ {& j* @④ 总实现代码
) Y" D( L3 S+ ~/ r' h- X// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
% H0 T4 k6 y2 Y8 g% n
8 k, {. }# G; C6 a9 R" g+ i// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
2 T/ b) W3 Z) U) n    int i,j,k;
    for(k=low; k<=high; k++)
        B[k]=A[k];
/ `8 e! `6 A. S    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
/ N! A7 \  Y* u6 S0 J/ |        if(B<=B[j])
4 B0 \8 B  S& x6 X            A[k]=B[i++];
        else
3 s7 s- z2 u$ `            A[k]=B[j++];
    }
& \" a7 d; a# J6 \2 H- L/ t5 ^    while(i<=mid)
        A[k++]=B[i++];
- Q7 x! A* ^' d3 k    while(j<=high)
7 [. F% _8 n' ~- K        A[k++]=B[j++];
}


// 递归操作（使用了分治法思想）
6 k+ V/ l( o9 X% _" bvoid MergeSort(int A[], int low, int high){
    if(low<high){
7 B: t0 {5 m3 {1 z6 y+ X        int mid = (low+high)/2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
    }
$ i" @5 r, V/ m4 y; u0 w: @0 t, U* X}
. N3 t- M1 ?) r) v" p  t
1
, [! X) U6 _* ?+ w2
3
& Q* L$ G+ x- g. R4
: P7 s( `5 i5 h3 z% f# R* ]5
6 w. h6 M; g$ q* }6
7
! _' q" h1 E2 X2 m7 o/ X- X8
9
, Y3 K4 j" Z1 p+ g% c0 Y10
: N* X0 F3 j6 C0 m$ _11
12
13
14
15
16
+ w" ?/ h/ w; n5 \& Y17
18
19
20
21
5 A2 ~  |8 ]: D' G( k22
23
24
# C5 O5 k4 m: {25
26
27
28
29
9 C. O( |* v* X6 r% j; O30
时间、空间复杂度


. l) s$ H4 u* y1 A  L# W

5. 基数排序
& E$ s7 L( G6 h5 d$ K- M. H直接看课本的过程图来理解P352

再看这个例子：


算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
0 O2 x8 J9 C; `. h. n" K6 t6 }分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
% n. H( i8 {# {+ }收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
% f( U3 E( a, Q; K0 F①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。
算法效率分析：
; J: q+ N# e0 ]( z时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
+ c% z7 k8 _. z; W& |% a8 P/ B3 I空间复杂度： O( r ) ，其中r为辅助队列数量。
6 G- S! P! j- t1 G稳定性：稳定。

! e% f* S: I& a6 K1 ?2 I8 w
: U% Y4 X; |  ?0 Z内部排序算法总结
9 X% T1 J, {+ {" J( G5 ]
————————————————
$ a" _; N2 H2 A# ~: ~1 B版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969
/ q; M8 x, l7 g1 E  e0 A6 W. p