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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
2 F" j' X* x" w" k3 Q7 V排序
1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
时间、空间复杂度
- S9 L  E# [; r: F2 }  G2 @- B（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
3 k  A! F4 O3 w8 T+ O# \! v（不稳定）1.3 希尔排序【多次直接插入排序】
$ W! z; F, u7 }; ~- t0 M) ?时间、空间复杂度
, K! U4 B3 b9 j2. 交换排序
2.1 (稳定）冒泡排序
- U( L5 L, l  `0 v& k, r7 N0 q时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
) d% G% ~4 ~  r8 c时间、空间复杂度
④ 补充：在堆中插⼊新元素
" N! O! W. H6 v3 ~% s/ `⑤ 补充：在堆中删除元素
7 U5 h9 |- E: j4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
' f! b* P/ f2 B) _! ]1 R③递归进行分治思想【MergeSort(int A[], int low, int high)】
" A+ v( {' B) i: ?$ A  B/ @' b& Q④ 总实现代码
' g2 T+ M0 E* G" O时间、空间复杂度
5. 基数排序
3 r7 y1 `3 S4 e内部排序算法总结
1 y" F; i& `: }+ g- B& v( N排序
; g( u  i) e0 a$ s% K: E- c排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

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

算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。


1 H* I" ]! F% z9 n排序算法的分类：
% m; ^  ?  [& [1 w/ A" D内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
% x* |0 ]- G  W) N' B& I外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
' e& I. l( C- `0 L4 a& f
! z; ?. ~4 \* S7 E+ a各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html


( @# R7 v# |3 q9 D5 ^; z
5 V+ C: s5 ?3 g  W1. 插⼊排序
8 }' }  w1 u- J% O* F4 V（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

/ z$ _0 I$ J) E+ }算法解释：（从小到大）
+ s; M! @5 L% B, U  |* w

' ?6 d8 }" r& }0 N1 f0 Z0 e/ I6 D算法三个步骤：

% Y$ ?" n/ h* |先保留要插入的数字
# x1 k1 l$ h2 T$ D' W9 `4 h, _" A往后移
插入元素

// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
* l) ?) L) b% ~9 ]  l    for(i=1; i<n; i++)
1 t; X1 ~5 b! U/ u# r/ j    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
# r) P5 ]% T9 E" }# ^7 `        if(A<A[i-1])
        {           
/ {) a1 s* k- \: q            temp=A;  //保留要插入的数字
( o8 b0 `, X' }+ W! V6 Z
$ x5 J$ u, J2 T+ O$ K3 n% ~            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪

            A[j+1]=temp;//插入元素
        }
1 Z/ Y* |, N3 @8 g$ I* S1 f5 c    }
}
$ N& X; R; G, B( ~9 N( j# B
! A7 t; B6 k. w" W+ H* Q2 m1
2
3
7 L1 o8 f% O7 m% M4
* b3 s; @4 Q: P5 G5 n+ _5
6
2 M* Q" q1 Q, ]2 _7
. s8 X! l+ D# m1 _4 {5 j+ h/ h8
1 ^- w0 M! |0 l9
10
$ S/ B/ K6 f% R3 F: B, n, J. |, D6 A11
12
" K. w. \, z  W& g3 c- ?5 a13
14
15
! S, d( b7 {, p% V5 C4 v+ _6 [16
17
2 A( K! y( O0 E: T$ n$ b用算法再带入这个例子，进行加深理解
4 C% p0 h" D$ q

" Y! N  y# I( z带哨兵：

4 u, d# B4 H  a7 R6 ]
* I7 ?# t: `% d/ i4 O补充：对链表L进行插入排序
1 |) h# {# X. V( E9 ?
void InsertSort(LinkList &L){
1 g- d- Z9 ]# v# I% W8 ~, M, k/ F    LNode *p=L->next, *pre;
! ]  U+ [4 R! p) [    LNode *r=p->next;
    p->next=NULL;
    p=r;
) T% r7 p' Y! @2 f6 o    while(p!=NULL){
2 z0 ?! V8 j" F& B. L9 Q        r=p->next;
. b; d) [- K; C# b) a        pre=L;
4 h. Q3 F! O+ B* c        while(pre->next!=NULL && pre->next->data<p->data)
8 Q8 Z  E4 U; x" S& c" }            pre=pre->next;
% h+ G: \6 z. X& W4 Z. w. J3 B9 [+ W        p->next=pre->next;
( \2 H$ U% q5 T- F        pre->next=p;
! X0 `4 v8 f; j. z6 g        p=r;
" l; k1 N, c5 \) U4 ~# |4 ^    }
}
  S) O* Y  r/ w1
2
) q. {- {, ?" Z  B. R6 `3
4
7 j2 ?5 z  h4 ~0 @/ P  H, S5
6
7
  v# m+ T5 X% _( }9 [8
3 `% v3 t0 A6 r9
+ w" A  y& O4 i$ _8 |9 N. M8 A10
11
12
0 L+ D8 z5 N, K/ E' z5 r, M7 Q13
14
4 u4 Q$ e. d& Q15
7 F  ~* p8 J) ^0 y7 ]时间、空间复杂度
* F3 z: H! Y" F( E  `

5 V2 H) W* Y! R最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
# _3 J6 F2 N& u$ Y- ~) w最好时间复杂度—— O(n)

+ K9 `4 C7 j0 q最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
8 T% f4 Y9 ?% B& h1 \/ `1 d3 _…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)

  r& i9 ]9 b$ S& S. l, M
4 N9 S. o% x5 w, v- W9 K1 M* O
2 S) A, k" l4 }; q

（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：
; y8 u" n! D) w# |, y' m


7 c' o# ^, w0 c/ T//对A[]数组中共n个元素进行折半插入排序
3 C6 D# F0 i0 u' k4 t1 N2 svoid InsertSort(int A[], int n)
3 k. k; f' T5 S6 E# I{
/ c3 {! f- t% l) O    int i,j,low,high,mid;
* t) ^& `; o" f) V" Q    for(i=2; i<=n; i++)
    {
        A[0]=A; //存到A[0]
) O. m% H7 |6 q0 Y2 b7 p        //-----------------折半查找【代码一样】---------------------------
$ Y2 V& I# c  d2 c7 }3 f        low=1; high=i-1;
        while(low<=high){            
            mid=(low+high)/2;
, G3 m; G7 L# c            if(A[mid]>A[0])
                high=mid-1;
            else
                low=mid+1;
: @, c& Y- t5 m- _% k) u, l% Z        }
+ w4 i: ?6 X0 `" ]/ ^$ G5 X         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];

  J; L9 a& E" q0 \! m: z        A[high+1]=A[0];//插入
8 s0 G; t) m0 H/ T    }
/ M4 C0 d5 }8 u) V+ T0 ?, |}
) w: w* G4 Q, i
/ z$ h( K8 ]1 ?6 k" U1
0 m, h) A: _( S+ I" {2
0 s$ c5 V! h. W9 e5 J3
4
. G6 k5 L4 D6 J4 m  T/ w  T5
6 m; b1 [# @5 O8 O( Z5 D6
7
8
9
8 ~( f- X2 Z* v1 Q. Y. j* H10
11
- p9 @# I# R. ]8 [) \0 f12
4 C+ E4 F) {; ?# F3 M5 E13
0 Q- o$ O  `+ S2 a8 m14
0 h# R7 R( B  a' ]) F15
0 H0 Z# z5 K: T% n16
% C+ E4 |' z% b* m17
18
19
$ D' [' ?' E3 @2 a20
21
22
23
( {3 n/ P* N$ q# j0 g9 X时间、空间复杂度
空间复杂度：O(1)

3 K2 c: w, j3 r" s$ j$ c【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
0 n5 K0 l' x0 q  L

（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

算法思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
) X# q6 x. h8 a( g7 A随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
9 F( n! N( g1 ]$ j1 W+ s图解：

8 U# x4 {  ~; N- `& j# i

5 F2 c- H- W2 K2 }9 G代码实现：

//从小到大
void shellSort(int* arr, int n)
{
& H% |: p6 P1 ^9 ^- l! x        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
1 ~0 J2 `6 Y0 K: m9 K# ?9 Q# n        for (gap = n / 2; gap >= 1; gap = gap / 2)
; {. J, r' A$ l4 N- D* A9 E6 M        {
, m% Y7 ~2 ?! x$ k0 `6 P9 y( {            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
                if (arr < arr[i - gap])
( @0 v" w) ^3 J. w                {
, J4 j7 l1 m0 j                    temp = arr;

                    //后移
! r! {* n  b% Z2 L9 h. T+ b* n5 B- ~                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];

: Q' \$ p/ U8 D2 Q                    arr[j + gap] = temp;//插入进去
                }
            }
            //************************************************************************************
7 {1 e+ L& h: Y4 w* H3 E* g7 |        }
# i' N" R" p) O$ n* K, B+ J}

1
0 y6 L9 e, P0 i+ N# \! L2
# N" A' v8 T7 @2 \) v  ^3
% {, C$ G6 k' s& k: v4
5
" `5 K/ @' N* F; t6 I4 K5 V) N+ k6
: I% ~- {6 e! b+ ]) g* S7
8
9 H! b( K1 h# _$ ]# d9
10
11
12
) o! t$ [3 T' W13
5 d* N! B! [+ e  E$ |' F14
& W& ^2 |$ q9 O  z5 @15
) p7 ?3 W' o3 K) N* C! z% X# w16
3 w4 h8 g2 x6 U5 u$ j0 d( A  Q% t17
18
0 O) q2 X( X: Z6 m" |8 q19
20
21
22
23
24
时间、空间复杂度
$ @: N0 y% ^3 O" y7 e空间复杂度：O(1)
; s+ M3 i9 w0 H9 W( U( b: t
时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)

稳定性：不稳定！
) I  X0 f0 m3 }# \- E5 b

  ?$ v! C# m2 d( ?* R/ Y  d
  E4 N% p2 ^: x适⽤性：仅适⽤于顺序表，不适⽤于链表
+ h7 W2 L$ i/ j1 }- C

! U/ D6 j- `8 O6 f$ L
2. 交换排序
2.1 (稳定）冒泡排序
5 S  I! r: I- r  J  e8 w英文:bubble sort     (bubble 动和名词 起泡，冒泡)
从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

每一轮比较会让一个最大数字沉底或者一个最小数字上浮
6 [: X5 [  `1 E% v
: p! i5 o5 k2 O6 M; v6 W. A这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

0 X( j: b2 ~7 m* |. l实现代码：
$ i& {4 {' \6 u  }: k% w( B! z
) r, S  i1 n0 S" R' e+ A* p6 _//从小到大：
8 q8 [/ u2 U3 Z* Avoid bubble_sort(int arr[], int len)//冒泡排序int*arr
{
& W$ t2 ]* ~1 e9 B, D9 K        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
        {
, k6 ]$ h9 {2 @* E6 M                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
0 C3 e) p! `# r2 j6 `7 j                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
                {
0 l! }  P6 U9 p% i, R                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
) _( H6 f5 T, o0 T2 ^. s                        {
/ C4 n8 ?# P( o" q; p1 w                                //交换两个元素位置
                                temp = arr[j];
3 l, a. {/ R3 D" ?                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
* L6 e6 K7 j4 d; l                        }
& {5 r3 S4 B1 W# T                }
        }
- c6 y9 P) R7 d; C5 e9 F}
' y+ X7 i( V+ j  I! s
1
! M! n$ u1 N$ L  e" G: K* S/ k& ~2
3
4
5
: W) g& \9 J+ g: |; }0 P1 n" f6
, t+ L, E, @7 F; m( u7
7 Z' K7 g* @7 F& l% B, |8
4 {$ [; Y0 w4 ~: I" t$ i5 m9
& y2 w/ X. b% }4 C8 I# K! G8 D" D& B$ n10
11
12
13
14
15
16
8 \8 @' P; Q9 h- U1 c$ ?17
% g* u! l# {* f18
9 X% P  T5 x; u; v9 ~) G19
! F( @# k0 P+ [* b/ O; i$ q优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
! C: U( s4 \0 t3 A6 d5 H$ l' ]( G5 [
//从小到大：
0 D$ L9 Q: Y- p3 D& R( H8 X) Vvoid bubble_sort(int arr[], int len)
{
        int temp;
% |  F3 S7 s* C        bool flag;
        for (int i = 0; i < len - 1; ++i)
        {
            //表示本趟冒泡是否发生交换的标志
                flag=false;
+ m. Z$ h7 ]5 k2 k2 E& S; P               
( w9 C5 l% f& F1 R1 @5 z                for (int j = 0; j < len - 1 - i; ++j)
, _2 S* p4 t# y4 Y                {
8 l" X3 U# M6 M' \4 m) [) S; J                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
& l' F5 C( u8 B6 A9 {                                temp = arr[j];
4 m; t/ I) C& k- W4 h& Q                                arr[j] = arr[j + 1];
$ k1 N+ m5 e8 t; A) w                                arr[j + 1] = temp;
                                //有发生交换
+ v) C9 d2 ^" x: M                                flag=true;
                        }
                }//for
               
# y: a/ d+ ]+ g                //本趟遍历后没有发生交换，说明表已经有序
: f9 Z: K% X8 X1 L6 d! g                if(flag==false)return;【1】
        }//for
}

1
2
! @5 g8 a( C( v- L3 D3
' `/ |1 B: {# r3 l# k+ ~9 K% I4
" w  t# ~, l9 N0 N1 Z! ]8 q. \5
6
6 u6 p4 p- Q& c0 F9 J7 O4 j- B: L- b7
6 M5 g6 T+ f; v6 O9 K0 F& N8
9
% v$ y5 M+ B8 Y6 F, _10
11
12
! T/ N. j! O2 N13
, f3 n5 C1 D3 z  G, C& k6 x) W2 G14
15
7 D0 d6 [3 s8 H) i2 J' s) V4 z- G2 A16
2 d+ p. y$ E1 G* \& ]' [+ l5 }" i17
5 x6 B' a& k( ?7 }5 m18
6 e1 O* ~" q8 X7 l0 [: D19
( l8 G. z9 y' ?. J20
21
8 D) T6 L! n  |2 i- _, G" b22
23
" j2 q  C7 F& p% N$ q% V2 p24
25
26
时间、空间复杂度
$ Z, E8 t0 e4 x: ?8 O/ u6 H! {
5 B( b; j5 F* d3 Q( M4 q* u适用性：冒泡排序可以用于顺序表、链表


% n0 J/ j0 q8 l0 ?3 z" Y
8 M, X, _) N, Z8 U+ f4 X, l
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
8 L, m* |4 u3 c6 s2 u+ }在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
/ ^5 ^, Z0 Z7 P% z/ {/ Z: n3 _3 K, l再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

! v+ G: o/ F6 \然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

划分的过程：

初始状态：取首元素为pivot，定义low，high指针
# d7 |5 A5 l4 h
: h$ y, y7 U& o0 a. Y+ ^首元素为49
high指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置
9 a; l8 \/ l% X1 y- D7 H1 X1 F: w


* ~% f/ t2 V8 J# q; Z& }: i

// 用第一个元素将数组A[]划分为两个部分
9 A0 ~, `$ s( {int Partition(int A[], int low, int high){
        //取首元素为pivot
    int pivot = A[low];
. |- b2 e# L  @: ]) Z' B
* g. E2 g/ w6 }- u- u5 s$ W# k    while(low<high)
    {
            //先是high开始向左移动
5 S8 _6 ]8 M+ V        while(low<high && A[high]>=pivot)
            --high;
        A[low] = A[high];

        //随后low向右移动
        while(low<high && A[low]<=pivot)
            ++low;
        A[high] = A[low];
    }
/ J6 [3 B! ~: y4 i. y; d- `% @
    //low=high的位置，即pivot放在的位置
3 R' c+ l9 o% y+ r- Z    A[low] = pivot;

0 W' {% N. u& O1 c3 j+ Q    return low;
}
4 Q5 J0 P- v1 z- d& p6 I; L3 N5 c1 @1 R
// 对A[]数组的low到high进行快速排序
! w7 P" f% f1 D3 V& Y. Yvoid QuickSort(int A[], int low, int high){
    if(low<high){
        int pivotpos = Partition(A, low, high);  //划分
9 W' y2 E' L# \5 T: F1 o        QuickSort(A, low, pivotpos - 1);
# a) Z' J# m/ X- m  M        QuickSort(A, pivotpos + 1, high);
    }
0 R8 b! u0 @4 N7 `0 q1 {}

1
3 B" S5 m5 ~+ D+ I2
7 T4 ?& P( c7 J2 z* [: T3
4
- Q$ T( P9 J) {7 t' s5
; H3 z$ z. N" |$ c, ^6
7
6 w' Y6 q7 g2 l, R8
1 v& ?( k# {. @% [) W9
3 }  I" L' o2 @+ }2 ]10
( e2 F) B" |) d- n, R5 }11
12
13
5 q! A& }& M9 z, R4 T/ |1 G14
5 `& r# A5 q  N* {4 X6 ]15
16
4 L& n" ^7 F8 F17
18
3 s- I: ?+ Z( u6 x/ T8 d+ c8 F19
20
21
22
+ u! e  }/ t" x6 {23
2 e/ b! g! c) s; V5 ]24
25
/ b5 e6 t8 F" L! b4 f. O& j26
3 n. j# r  d4 ^# M: V% r$ V8 L27
28
: U8 T* f# S6 _  h5 E: ?! l0 i29
! n- e3 a6 W* @2 H1 W5 r& v% `30
31
" j6 @, i5 F( `( h32
时间、空间复杂度
" l3 g5 k! W( Y; B" g/ F
+ Z$ ], X9 U6 R+ \
' f: d* y5 x$ e& M1 a4 K把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
% n' z3 k, y: o; o1 e
n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n
) ?3 B8 _! U; x' _0 U" h. {) Q0 D
时间复杂度=O(n*递归层数)
/ _8 B4 M/ [: A2 G/ M% l  T1 ^最好时间复杂度=O(n * log2n)
7 `7 _4 F7 E& _6 J% J+ C. X* i. Y0 U最坏时间复杂度=O(n2)
" g. M6 o- Y0 N" Y平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
% h7 H& q3 S' M3 |( C* _最坏空间复杂度=O(n)
0 M8 ^, _8 Q& O9 j1 j
, n0 K8 p  U8 v) U, X; J+ v& N最坏的情况



⽐较好的情况
, f* U$ q3 V6 Q( z1 ^3 y6 g
( Z4 E/ M  e/ g6 p
% q6 Q# ^/ E, W
不稳定的原因：
7 G+ ~3 [$ W1 M" O% N: a  d
( z* t8 v6 A5 x



4 x7 _, @% m* Y3.选择排序
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

- Z5 l6 h. c7 ]/ l3.1 （不稳定）简单选择排序
9 O! b% M5 P5 y1 A9 D) V* _算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
  p5 s. D# D' L3 W. f0 a


# l1 u) j6 X3 f$ w// 交换a和b的值
9 M) D/ n0 ]. z# ]5 i9 d# Avoid swap(int &a, int &b){
, }, |! P3 m; Z- w* H, B    int temp = a;
    a = b;
    b = temp;
( m5 O& W( R0 V}

9 s- ^: F( e6 K0 ~: }2 T* ]// 对A[]数组共n个元素进行选择排序
" c; Y: [7 G" p3 {4 A) U* Svoid SelectSort(int A[], int n)
{
        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
% K3 z- O9 D% F! w2 L) B/ x- y. m    {                 
  d! @) p, b6 J        int min = i;
8 V/ A5 m8 C) W% `& n        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
- `2 X1 N2 f% ~# c                min = j;
4 V  S& `5 t2 S0 E- n        }
) n( b1 ?# f' b1 p        if(min!=i)                     
4 H# X% z' b  A1 _; j/ p4 s% }# y            swap(A, A[min]);
1 E1 o4 N" _" m! a# q- o4 h) F0 R    }
}

1
2
# A- `- u0 `- T3
4
5
6
7
7 [# R% A8 _& R6 H: t8
$ \$ A  w9 Z1 K' ^5 c4 f9
+ G& Y0 s  q% v2 e' k10
11
. A4 h5 F- @& @12
& F0 E9 ^) q' a- Y3 A13
14
$ w5 q# h$ x$ d8 K" g15
9 x! a9 z5 L4 S6 G16
+ s, G; [2 Y9 L17
18
2 h- }. X" I/ z19
20
21
( C: Z$ ?& A8 \" z( @9 q7 \22
) B$ B4 t% w5 Q3 B" g补充：对链表进行简单选择排序

- S( M& J6 D. X( H$ \; Zvoid selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
5 S0 Y! J+ a1 E    L=NULL;
6 z2 a6 D4 J. q3 F$ M  _5 _    while(h!=NULL){
4 R9 i, f$ J; d3 O0 A        p=s=h; q=r=NULL;
3 v: Q* u4 C5 s        while(p!=NULL){
            if(p->data>s->data){
                s=p; r=q;
            }
            q=p; p=p->next;
        }
+ R3 v% Y3 C, S" _        if(s==h)
$ |# n! l% j- p. M" O" @% X            h=h->next;
        else
" R0 k, }9 q0 S, Y            r->next=s->next;
, w! o. c9 ?% K$ ~& `$ X4 l        s->next=L; L=s;
- m% d7 {) x7 r1 `+ r  G- b7 H    }
}
& P1 q# r  {! b3 f1 ~( j
1
2
3 G3 B/ b: X( N( c# V% M* Y+ x3
4
5
: Q; R1 O0 D" ^8 F' s6
, h5 F& b: H4 q3 K7
$ Q3 ]. u# P# {1 w5 Z9 W) d8
9
9 P+ d& \$ L! H; x( @10
/ K& c( r8 I* B; Y( B11
) W2 N3 K, f$ A  V8 P9 ^12
13
" S' p( Q6 {+ k14
  k, c. a/ K3 s* n15
8 w, h* T. s# v. M8 I$ c, H16
17
18
" c' I( M' e5 F5 c' H8 _8 X2 h时间、空间复杂度

( a. i0 T5 |& f( R3 A; p


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


' n4 i" I7 Y/ S# e; x3 F* `
3.2 （不稳定）堆排序
9 |1 H# a5 m# b" @; G) r2 j' q① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
. M% [7 \2 p, x; g2 n& v堆是具有以下性质的完全二叉树：
+ T9 e  T: l) ~* H' `每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
% m) B, N! q. ^  O$ {* _& b3 R9 F& [
" W5 ^# ^1 q+ {/ c6 g; ]
+ E# d0 B! R. V) k
9 {. S$ ^8 Q) J即：
4 K1 Q; I' ~( u' `$ H0 I  a若满⾜：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）—— ⼩根堆（⼩顶堆）

- W# {1 N  A) o9 s" ?② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
3 `1 ^8 U1 Z+ {* c% D2 y
在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
/ z2 r0 W2 L& I* ?- H7 _
5 A2 k* _" P7 j' M) e检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换
+ k2 ?: `  Q- p& ?
# G+ [# a: {! O% D9 n& B过程例子：
/ S" f3 K1 o  x& U/ F  \8 Y9 m

# V& N5 t# i9 \3 D) q& v2 L) D# \
建⽴⼤根堆（代码）：
7 n) p, H' x% S) c# s$ i

, s+ S6 C( z# M* C# p3 r" x$ z) c
! |$ ^$ j, z' E6 y2 w! p// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
( `& m. @6 D1 Z2 M  w" r: a        HeadAdjust(A, i, len);
& J$ `2 _* L" ?& L) _+ {, A}

// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
/ @# K. ^, C& m7 u    A[0] = A[k];
5 c# p% u7 z) a. F    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
4 c5 M; V7 ~- J( C7 g0 b3 p# g5 t        if(i<len && A<A[i+1])       
            i++;
        if(A[0] >= A)
            break;
        else{
            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
        }
( X: P# ]7 D2 v8 j    }
1 ?' ^3 \4 |) v0 s$ X8 U    A[k] = A[0]
/ @2 A8 I9 R9 }1 x) F9 m}

1
2 D- V: s# ^. n( w  n  _2
8 C* Y+ R, H9 _! n3
4
$ @5 P/ F  r2 m5
+ b: ~" H; l1 {! A# F2 R0 s6
7
8
9 ~! Z. t9 z# }; _' c9
10
11
12
13
14
1 h. W6 p$ w0 \& {8 a15
- \( i' w( q  w6 }4 g16
0 n% f9 P* N2 ~, d8 ]9 ]. _8 |6 J17
18
19
5 ^& f/ F+ X( c7 \3 o; v7 r20
21
4 q& \# a' C) y3 E: ?! r③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

) D, u5 f& ?+ M( k; G( u过程：

0 M5 e$ A5 Q0 ^- @  H// 交换a和b的值
void swap(int &a, int &b){
! ?: I  ^8 {- |3 w* H1 r# G    int temp = a;
0 r) _7 E; N8 E$ d) M    a = b;
3 B/ w, Z* c$ Q$ n" j" D    b = temp;
( h* I. K# T, j8 R/ S* P! p/ e}
/ l/ {; f' z! t; C+ W3 {
# |- x2 i' E9 S3 t" q// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
- B) x# y+ z- E8 K/ c2 B) n6 a0 c5 c        //初始建立大根堆
    BuildMaxHeap(A, len);                

$ i2 J# Z6 o- J. U: r    //n-1趟的交换和建堆过程
5 F2 T6 \! M; w1 _9 I    for(int i=len; i>1; i--)
    {             
/ r& C* g) O9 U: ]* f1 n& R        swap(A, A[1]);
/ E9 q; ~* [( R& Z- X2 v. D        HeadAdjust(A,1,i-1);
8 P2 F! F# X; M6 ~, W    }
}
( ]* |) o5 `" U
1
6 Q+ r+ j% V$ ?0 o: R2
& Z& q# V6 R" _3 B3
# J0 w' [  M5 u2 @  L. O4
5
6
7
* o2 ~  p, `6 ~0 X5 H8
0 D9 d9 L, ~# [, ?" H9
10
2 U" r/ |+ e& ~" q  ^7 X11
! ~' B" C0 T/ t" _% N12
! H; V* A% I. ?, |2 P13
14
1 p( d9 U. ~; i$ A0 K5 K15
16
17
18
19
时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
' v0 z( B8 N& }% V$ }故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
' q, m( s' d( G( h. X
空间复杂度 = O(1)

结论：堆排序是不稳定的


④ 补充：在堆中插⼊新元素
* Q: G9 k0 X8 i对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌
% ]$ R: Z% w/ d: ]3 U" m. h1 b% `, A

- x. D6 ?, v& V3 `: c' x7 B3 i
" B! J  [; E7 G0 O' O, @+ c6 X⑤ 补充：在堆中删除元素
0 q4 n$ @% N: T- R被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌





6 f0 k; ^- H$ K& ~, f4. （稳定）归并排序
& I) u! I+ J# v9 Z% Z) r归并：把两个或多个已经有序的序列合并成⼀个

: A, I" @' y" j4 c6 T- J① 明白什么是“2路”归并？——就是“⼆合⼀”
2 c7 M4 F2 b6 j3 m+ x& e
0 d+ v; ~- k2 A9 |8 R* Z多路归并：
) G) D& f$ z# b, }
2 \" X( j3 e, m, b: F3 _
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
8 ?4 k( F  }0 B- l" v' N
3 a' p: F7 A, d③递归进行分治思想【MergeSort(int A[], int low, int high)】
7 [$ R$ `" T1 s9 q. U8 g' V4 x

④ 总实现代码
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));

/ ^4 P. Z' u9 a7 {// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
2 E' H# s8 @- n! Gvoid Merge(int A[], int low, int mid, int high){
& e6 J" X. J' L/ a    int i,j,k;
2 X1 h, |3 ^' G  B    for(k=low; k<=high; k++)
) y, l4 a2 c2 u0 `, e        B[k]=A[k];
( |* o& j' t3 r) \# N  b1 W% m    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B<=B[j])
            A[k]=B[i++];
+ {5 E5 O* U% x5 ?' ?: s        else
" v* Q, ?3 E0 n5 p. M- O* ?) G            A[k]=B[j++];
2 K8 `& \& U* Q- C% F    }
5 N! A5 H+ B; U+ N4 C3 b    while(i<=mid)
* p1 n! l1 _4 B% v) x        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
" Z# `- c  Y1 E9 o: y* C}
7 F. D2 Y, M8 \/ t1 O
& l2 ~* e5 Z9 T# t+ \  j) w
" ?  l+ m9 H# O// 递归操作（使用了分治法思想）
void MergeSort(int A[], int low, int high){
! N" q5 S8 ^6 L9 Z; f, c    if(low<high){
6 }( n5 e* c( b$ C  x3 B        int mid = (low+high)/2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
    }
- L( d& f7 f6 U}

: L5 V. {2 M( n$ v* S" O* Y$ Q( @1
6 a$ l* G9 O+ w& X) O8 O2
& l; n* h. u+ {$ Y! P' s3
) b) m, `4 m/ E% X0 G+ R2 q4
' i8 \. i* y$ M* e5
6 r: @6 l$ J" F& Y: o6 @6
% c0 v, {. P) [8 h% ?2 c! t1 g7
8
9
5 M  {, x. `0 W" ~: a) G0 {10
  c3 O# E% K( ~/ m$ P; |& g7 n11
12
0 }. E6 c6 q* E5 C$ S13
4 Z* n7 O" j- Q  Y* j, e0 Y14
15
16
17
18
19
5 `0 V9 G' y) T$ X20
21
22
23
24
25
) J0 p% c& l! Q26
. ^9 R. K" S5 z! G( H: j9 ^27
( E& x8 E, q$ x( S: o28
! W% ?% y( D9 \29
% D5 m; o3 e( H& m6 f! [  I30
% v, z6 V# U) o0 _3 K5 ~3 S7 @8 d时间、空间复杂度

  j- B8 F. l" U- |0 a9 [) g
" ?# i4 Q) r8 U% u6 @, b
  ~1 L0 I7 T; g- X1 P  Y
" }5 P; x5 ^# f  c% H5. 基数排序
0 v$ L* {$ ?, L& l直接看课本的过程图来理解P352
: v3 J, m! y' _8 N
/ L  b2 Z5 q5 `再看这个例子：
% p5 b3 R, V8 M" X$ ]

算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
& L  J% L+ o1 `+ v% I6 m: Y1 q收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
5 @% L8 Y' R+ t基数排序擅长处理的问题：
+ W6 |' W( \1 s4 A①数据元素的关键字可以方便地拆分为d组，且d较小。
1 Y, G/ \& p: W) d8 M②每组关键字的取值范围不大，即r较小。
* h' E5 U% }+ j③ 数据元素个数n较大。
算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
稳定性：稳定。
  v9 y9 r6 [8 ]6 S  v5 m) _

. K! t  k, m. U! V% h5 v0 i6 D/ f内部排序算法总结

' @2 b7 G; F& B4 [. F6 K( x————————————————
) @1 T: W# j: I1 Q3 d- V' w版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969
/ N$ ^$ b3 C  D" h9 W
2 h4 P0 d1 U9 W7 y) q8 _7 e2 H