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

杨利霞

3 S7 _7 Y% s2 M: P【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
排序
1. 插⼊排序
& |. A+ H4 w( |. f! i（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
9 J) @- u& @6 i! F2 r1 f: {（不稳定）1.3 希尔排序【多次直接插入排序】
时间、空间复杂度
0 r+ F6 B0 N/ i9 O0 Q2. 交换排序
% v% q+ k0 b) o2 _0 r6 z  `+ K2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
) E) F- R: H- W1 r! M时间、空间复杂度
" j) O$ `% f. J, v4 E: T+ R% h+ r; _8 J3.选择排序
3.1 （不稳定）简单选择排序
- s6 k, _- @0 q0 S时间、空间复杂度
3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
4 A5 {3 v9 p) b4. （稳定）归并排序
7 ]: x; L8 C" E0 H# Y+ k5 y① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
" S8 D1 ]% ~  p③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
时间、空间复杂度
- ?0 T+ ?- }! C' o5. 基数排序
内部排序算法总结
排序
6 K3 R* W2 T! j  e; Y& K排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
6 g1 y2 l* M: L) T. _+ y
排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
) p3 q: u7 z% P" _2 ?4 j; z
算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
! b3 }4 O! U3 e! \稳定的排序算法不一定比不稳定的排序算法要好。


排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
/ A, S2 N$ [( ]) @6 R5 H6 z
各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
" N, F. u: ^; @8 x6 ^2 z2 m" Z0 m


5 Y* N4 W% f. b$ X+ k9 _1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
( b  N' ]3 {$ `! @基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

. V5 w, |9 j5 D! ^( V! V8 `: V" Q算法解释：（从小到大）
/ o  X' j& u4 c8 J! I6 |4 H
, c7 v4 c- V% A. ]+ c( I" ]' k
. S$ ~9 V- D5 M8 k算法三个步骤：

先保留要插入的数字
往后移
插入元素

: |( L. x- e. u: o$ Z6 e# I6 `5 c// 对A[]数组中共n个元素进行插入排序
- ]$ O9 x! }5 b. @( }void InsertSort(int A[],int n){
    int i,j,temp;
6 r7 c, R5 V& p    for(i=1; i<n; i++)
$ m4 b% u% Z4 o4 K3 d( A: B# t    {
) q1 q- u4 Q* E2 N            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
        if(A<A[i-1])
        {           
            temp=A;  //保留要插入的数字
" y3 f$ W! q  A$ Z- e; E
' A$ @8 p( ^. I& [1 c            for(j=i-1; j>=0 && A[j]>temp; --j)
( G! k8 W$ f& j* X, ?. |                A[j+1]=A[j];    //所有大于temp的元素都向后挪

            A[j+1]=temp;//插入元素
        }
    }
}
0 D8 f) O3 Q/ [+ ^
1
2
3
4
5
1 L% Z+ F% h3 J. _6
7
8
9
) Q0 u1 q; d- G2 ]# o' a10
0 p% `5 I3 j- n8 h/ s, y: h11
12
  b$ G+ J7 z$ q$ e13
: V3 G" w8 a( m8 q' a14
15
! g# x+ B: `( T8 z, ^4 {16
17
0 i# P$ j3 F; D. f用算法再带入这个例子，进行加深理解

# z6 m& _* V* J) _: J
1 l7 a& D2 K$ d. o& J9 w带哨兵：
- k: L( Y" A& J- m( ]

; r7 }8 ?4 z; h% q, M- V补充：对链表L进行插入排序

5 c, w$ z& y# l4 z1 {+ ^+ Pvoid InsertSort(LinkList &L){
* E. O, Z- t1 K1 Y% w    LNode *p=L->next, *pre;
    LNode *r=p->next;
    p->next=NULL;
    p=r;
    while(p!=NULL){
0 _4 P+ I9 b8 A# l        r=p->next;
' s$ l/ N) S& M' }        pre=L;
( a) x! A# Z6 O3 D% d        while(pre->next!=NULL && pre->next->data<p->data)
! R# ?1 S# Q% u$ y            pre=pre->next;
        p->next=pre->next;
- i4 U6 ]+ t2 T! U2 N        pre->next=p;
4 a) I. |7 N+ Q7 S        p=r;
    }
6 r: \0 ?! y6 |9 i& {' O' U9 W}
3 i" M' d# k4 A: X  Q; e1
2
3
9 l8 e3 z: Y/ z* v0 ^4
5
6
0 p8 Q/ H# u# l5 n( T; |7
8
9
10
. s8 m2 o+ ?9 }( K  I11
% o: f6 {1 _0 Y12
13
. B' V1 S/ k) s14
15
时间、空间复杂度


最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
最好时间复杂度—— O(n)

) Q" p5 j% \; R# Q9 ]* t0 c最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
7 [% z/ C% w0 W# |第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
3 {$ B1 }+ s8 ]. L: C& Z…
0 p( N5 r- s- _! J# h8 K1 \& W5 W第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
& U; ~8 O  C/ `! p; D最坏时间复杂度——O(n2)
5 @* u% r, l3 l* f
9 E2 }# T; d4 Q
/ G. w# i3 ~/ F/ v4 s  B

. n+ y/ G  W4 e& H/ v
. C: e5 }2 N' K5 R5 o( I) N9 A! j（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
8 e' p1 K/ ~; w2 n' o# _6 x. Y过程：

/ q! D/ T# J  a$ ]. x- e

//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
{
    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
3 ~7 T8 p0 g8 K5 X; e    {
        A[0]=A; //存到A[0]
) E2 P4 A; l+ W8 t- f1 Z$ w        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
7 t6 U6 N# H5 r& y5 K5 Y) ^. W        while(low<=high){            
. o! P# }, J# F$ m' X  _1 w* i            mid=(low+high)/2;
            if(A[mid]>A[0])
( g* k5 S& I. C$ Y( p                high=mid-1;
( d$ X; w4 M; `, s0 }- h# V3 H            else
* N9 e1 @  p; O( T7 v+ A# e$ T- ~                low=mid+1;
        }
( T, K/ I- o' t& B& Z5 H3 C, q         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];
. X# V& P# s& B+ B2 I
        A[high+1]=A[0];//插入
    }
& u5 `5 \. e% y}
9 j% X8 ^4 _/ g; ^. ]. E
1
! G& q1 g, {6 b9 R4 \2
0 N1 s! e0 ~: ^3
4
5
. ?  O" Q  L$ w6
7
8
9
10
8 U4 X6 m% H& D4 @! o9 J11
0 x1 d$ D. i7 P1 Y3 k$ b9 ?12
3 E9 @' P: s. w$ U% K13
14
% Y0 r: T0 Y+ n  R15
- u% F6 Q6 K. D" i5 \* ~16
17
% i# ^1 `3 P, c) O, W  ~7 @0 Q18
3 d$ C4 y9 R  o6 @19
" m! e; C. y: O9 v& L20
21
5 ?. E8 D5 `3 L7 S( d/ m# @; X0 c22
8 g4 _8 G0 V" j4 A* Y- N+ F23
时间、空间复杂度
+ ^1 M0 I0 o5 @$ D5 h' Q% P* V空间复杂度：O(1)

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


9 K) H& L" [* k+ i( n（不稳定）1.3 希尔排序【多次直接插入排序】
; Q1 G% Z. D8 W/ [( [1 N" M& _- [是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

6 M6 I8 z2 C: N1 L3 p  A1 [" D算法思想
' f9 y- ]; `* I8 d& j
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
3 l! i$ R* U, v7 I( q. V随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
+ o0 ^& B# @7 h% H4 ^& t: H+ m0 v图解：


2 [8 U. h0 j; V% g  b* W
, ~# {: j, T3 L0 F( W( ^* B代码实现：
) Y2 K) {9 `3 T& P' W& k3 Y
- E9 n: {: }6 U$ r: a0 e//从小到大
void shellSort(int* arr, int n)
{
        int gap, i, j, temp;
( W# }% r1 U( C        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
9 t' u  G+ B8 e        {
* ?/ E8 y7 H' I, \$ R  T: V, p            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
* b0 m) o; K; _$ G4 z) m            {
* H- Q) X+ _# I                if (arr < arr[i - gap])
                {
" }( b4 D! L3 S' w6 d                    temp = arr;

                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];
; k8 X( u  M' P# N
/ S. q/ J8 p. v6 Q                    arr[j + gap] = temp;//插入进去
# D- w; z# [. y                }
2 j3 g4 ?& \8 H4 r            }
( Q  o) h  P- I            //************************************************************************************
        }
% q7 ^+ _+ C# w3 F2 G9 G7 {}
* k* Y$ a$ o1 C  c5 Y2 J
: U: S/ s2 Z2 n3 W1
2
, S1 d3 {5 w) v4 A+ ]& Q3
7 X0 b% F3 |1 j4
: B/ ]5 L- X8 e5
$ G' s6 [+ g: ~) [5 u6 w* q1 H- Z7 s6
7
, Y! r. Q5 h, u8
9
/ i) o0 D: k2 f10
; ?( M7 r" e+ ]: b; K7 ?11
12
13
5 V4 K7 \* E1 Q$ d9 q14
15
16
$ Y8 A8 e. z8 W& M, k% h17
18
# v( W+ M/ \. Z* @. ]% C# r/ Q19
20
8 [  z) B3 j  P8 q5 X21
: P) S+ K8 P) d1 ?. L, V1 j22
23
24
0 O2 b# W9 m7 t$ p# k时间、空间复杂度
空间复杂度：O(1)

) E! X5 K1 }, ^+ |+ }" `+ X时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)

/ Z' x, G* C, m! Y* _! l6 F* ]稳定性：不稳定！
; O8 c7 Z' r: T8 }5 _, R: Y
- U' R: q7 @' u# y' V  g

适⽤性：仅适⽤于顺序表，不适⽤于链表
6 V; ~, o3 L7 H) g+ Q  T

3 ]; T$ b' u$ Z
! ^! A. k4 ?6 z! b* g, W2. 交换排序
6 d7 }+ q: k; Y7 J2 q; c" w/ G& ~2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
: \8 w1 N: t8 _  b从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
; K9 }; ]6 C3 y" d" l; K* F( Z
2 i! h: @- p9 ^! ?: L1 Z4 C每一轮比较会让一个最大数字沉底或者一个最小数字上浮

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
/ x* F. S% n0 Z6 {- k, e
实现代码：
5 e" K- b# y: k2 X
//从小到大：
% Q: A0 M# F: X) @void bubble_sort(int arr[], int len)//冒泡排序int*arr
9 j' P% c- }8 S! l, g# @{
- k* |, C  [2 N8 R% d  B1 ?3 ]( Q        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
        {
                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
; U2 G4 e2 x& s' C; l3 _0 R                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
                {
                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
6 a& y, Y" _; o+ i% Q                        {
                                //交换两个元素位置
# V* z: W: t" a5 i                                temp = arr[j];
1 S. P8 q& {, Y2 `; a                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
0 E) S9 c) ^2 q                        }
                }
        }
% L# o2 h" C4 O' y: w6 e' A}

! m! B7 o' S, S1
2
3
4
5
) Z. d9 X8 m; v6
7
8
9
6 o- ~7 c# [* v2 v  C10
11
2 c! ~# S) T$ `1 N2 |# s/ x; [12
13
% b& }) _& t- m1 K' z1 A# R14
15
16
4 Q( {! n7 r5 f- M, P# E17
18
" N. m3 K5 A* V2 u& q6 k9 e19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

* B: q! ^" L4 `5 ^) f- G9 S- \0 A//从小到大：
void bubble_sort(int arr[], int len)
" C" P  |6 }* V, W4 z6 {# Q{
% _8 `+ [  ^% ~" w8 b3 X; j        int temp;
        bool flag;
        for (int i = 0; i < len - 1; ++i)
        {
9 k  N. A" w2 i& L            //表示本趟冒泡是否发生交换的标志
% C4 Q5 _" p# R2 h6 j                flag=false;
& a# G$ F2 M0 _. m& D+ a               
                for (int j = 0; j < len - 1 - i; ++j)
                {
                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
                                temp = arr[j];
2 s+ W" d- ^% S4 N3 Q                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
9 T1 W) F% Z2 h( B: z6 b; Y2 y                                //有发生交换
                                flag=true;
; O- j! k  ~! f8 ^: F& ?; U                        }
                }//for
0 {$ M' i1 y+ Z8 W               
* J# q/ m1 o3 D                //本趟遍历后没有发生交换，说明表已经有序
+ @/ k9 y7 m  ]/ w' Q                if(flag==false)return;【1】
        }//for
9 W7 Z* x2 _% w/ D& {  d9 F! o5 m}

1
2
3
4
5
0 i9 L8 [4 t' B. \  Y) T6
9 I1 ]% s* C0 q3 O# f7
8
9
4 m' P* e/ J& c8 B% ]0 @4 i5 Q10
11
12
13
14
15
16
17
18
19
20
21
22
23
" y3 ?; C& U1 u% ^24
9 z3 C6 f" m; a/ `25
  Y1 b! Q; r5 K$ n26
* Q) K) ~! V  F9 v时间、空间复杂度

适用性：冒泡排序可以用于顺序表、链表
9 m% `; B; s7 V, o1 B% b8 q

- h" m. L% S7 {" M
2 U1 E! z" q, P0 |8 J4 q: ~
6 E8 o( s: ~4 W+ X) n" m6 N& p4 H  }2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
- C& c  |5 u! v4 a3 ~在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
8 T- t* a& I* b; o2 Q; Q通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
# v" u' U7 L6 O/ s! x4 o* C# K7 L
7 b; }# z" T  C然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
) k8 y# X3 j! b5 N# j2 A6 D3 O
8 ^- N/ ^9 C) j: ?% t# U划分的过程：

初始状态：取首元素为pivot，定义low，high指针

首元素为49
6 c' k7 M+ N" L* u2 I  N' Ihigh指针指向的数据小于49，就放在low指向的位置
* @2 J) p4 W6 X0 `0 O2 jlow指针指向的数据大于49，就放在high指向的位置
8 Z5 @2 ?- Y2 L
1 n6 l! s- N4 Z
: v$ H& ]/ n' [; g. _" Y

) q3 c& m! y( ?, w6 r) t$ I
" N& ]) u" O; z# F/ H// 用第一个元素将数组A[]划分为两个部分
. M7 ?# Q" K0 T5 [& G# B' zint Partition(int A[], int low, int high){
        //取首元素为pivot
    int pivot = A[low];
/ g: [% _2 B4 k; w4 b( l
! o6 X+ Q6 ?- f; T6 k. Z    while(low<high)
' H, l' ]- l1 y: Q' r2 X- S& |    {
            //先是high开始向左移动
# u. [6 |$ w" O        while(low<high && A[high]>=pivot)
8 _+ e! F) X0 E3 N* {6 u! c) n4 I            --high;
$ g% }3 a6 `# W+ }! b        A[low] = A[high];
9 g3 Y% o8 {3 u. \# g6 m3 d
' ]$ z$ S! V! F  k4 q* J9 p        //随后low向右移动
/ M; ?, s7 Q5 B  A& k        while(low<high && A[low]<=pivot)
            ++low;
        A[high] = A[low];
    }

) Z/ t1 |& T5 N' ]+ ~; b2 t( H    //low=high的位置，即pivot放在的位置
    A[low] = pivot;
) s' n) W& u  s. ^0 x& ^- {$ U$ d: |
, M1 |( m9 X9 L9 I0 a1 E5 `    return low;
* G- D+ H; m2 u$ ~" \& z}

// 对A[]数组的low到high进行快速排序
, o/ h: ?/ A* {void QuickSort(int A[], int low, int high){
    if(low<high){
5 n: z( P# J! B        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
/ l; }7 K2 W5 M! T        QuickSort(A, pivotpos + 1, high);
0 J" A9 C) |1 x    }
- r0 P3 J0 F( q/ A* i6 K: L  n}
* r  W; z3 q& q3 u1 Q- d% G/ h
1
2 u9 u$ ?8 v6 `& W" X; h/ s2
3
; |  `) ]$ l6 _4
5
6
9 W8 w  q% c# }7 N$ O5 w% I7
6 i* N! k% R9 w+ o* K2 M( {! ^8
9
10
11
9 c0 I8 X+ t* i% p12
13
14
15
' K# B; {$ W' v- Y- P! Y& }5 O16
# J5 V8 X  v" O, V7 ?17
! j- T/ H# I% ^  P3 ~% r5 G18
19
20
: @) M0 f  ^  `+ M5 I2 s4 q( T; f+ j* Y21
22
% x; p' p8 f6 O6 o0 \23
24
5 i' g8 E0 R" b) y0 l9 z' m8 ?25
26
# e0 X, T6 E5 r2 |3 R) ~27
28
0 N5 h8 q/ ^5 ~* |29
30
( u1 W7 I. G$ X8 Z6 m31
! U* q9 ]7 u2 ]& L32
4 Y. Z7 H. _# z, G9 j# X时间、空间复杂度
+ C, R7 }& ~- h" Q* v

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

8 n7 C; I6 G* \) i' V& @  V5 x- |n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法
; C& `5 ?1 C! H  ]- a! P
! [! P4 P5 m' U  D/ L空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)
: D. |4 P- `, e% o& N9 @" L: k
最坏的情况

9 l( w, |6 e. A/ o0 J* b. ^

⽐较好的情况
% V7 Y2 R" j: T$ ?4 O2 G) f
4 H0 F9 A+ i; `7 q! h  L! Y

8 M0 h( j. c7 Z8 ^5 j不稳定的原因：
/ e* z. T$ W/ h5 P5 o+ f0 ]1 m

& J2 _( _; v8 k

, }# K0 H" |% m
" w/ G1 v2 J: S/ w/ ~" X2 B" g+ \3.选择排序
2 t0 Q% ?. Z9 ]* p- a: _选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
! z9 h# G1 s$ g& k
3.1 （不稳定）简单选择排序
5 H8 C$ H4 j# @/ O# [9 N% e0 t, D算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置


4 E: T4 J  K' Q4 G  `) o
// 交换a和b的值
8 |; A. V3 o% L3 [; Xvoid swap(int &a, int &b){
" [7 r9 L: x  e$ I+ A$ k    int temp = a;
4 x- z) m1 V, T! E    a = b;
    b = temp;
7 C  b0 D6 i; N1 J/ t7 y7 |}

) `8 A; d: H" i" m// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
) \( B! \, _6 r, u" @1 u; [  _{
        //一共进行n-1趟，i指向待排序序列中第一个元素
4 @% v' {+ r' W$ a1 _    for(int i=0; i<n-1; i++)
    {                 
+ s+ q& h! |/ d  i7 f4 V4 [        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
  J5 j. z$ a$ [. J9 F' w" r& N            if(A[j]<A[min])
: H& \1 C9 X6 B2 [: i# K& K                min = j;
        }
3 g' R( Z  M: z' \( E        if(min!=i)                     
% d. x$ x( r+ ]8 }+ _3 O9 B) v            swap(A, A[min]);
& C& U) X, |* q& n; t; B  z! t    }
; W, l! s; i% L+ F* W4 J1 o3 C}

5 }+ S- y4 W3 A: k. o0 s1
5 F. |$ I' [, {& x5 Y6 M" B2
/ e5 @& W& s- g7 }3
! X8 k5 h3 {- }4
5
6 T( ?$ j, ?* B5 `$ I6
  q" E( R2 M' u9 m7
8
9
0 k* P) o0 V) H. H" ^3 r, l5 N10
11
* {0 v$ L8 y; N/ C. ?12
- Q( R# y( Q& X3 B& t# B& o( @13
14
15
* `8 C4 w% h; b& X16
17
18
' L2 g1 d1 t# n6 Z2 A19
20
21
/ p$ }; l" d$ N3 k; G% p22
补充：对链表进行简单选择排序

0 u) R' A, O, y3 ~: Kvoid selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
, m& D& S( g3 Y' ]  c/ n0 j$ C, [$ E    L=NULL;
" f8 y8 E; S& n    while(h!=NULL){
  w5 M; o) L; B# u4 p( `1 T        p=s=h; q=r=NULL;
        while(p!=NULL){
            if(p->data>s->data){
                s=p; r=q;
# n+ C$ t: |. l! I            }
+ b7 }5 c4 D( S# d% v            q=p; p=p->next;
: j5 K, C! m9 ^+ V6 }, M: ]' [3 T        }
        if(s==h)
            h=h->next;
# |* }8 T* d  `8 d3 {) k        else
            r->next=s->next;
        s->next=L; L=s;
    }
  A7 B( U3 u6 y% Z1 `}

1
* k7 H7 m8 ^# e0 r, S2
9 q' M' @" {: h( ?( `7 J9 ]3
4
5
: H5 `7 Q. Y' O. i7 @0 s6
( O' ?) ?. H, w7
8
- o0 t$ }+ l5 X* x. J& U9
10
! Z, ?, o  f) ~1 k11
12
13
14
15
: {* I. @9 [/ \3 r+ g5 F( x16
% E$ f% ?( t: Z17
9 l# p% t5 W% U( g+ h( s: D0 o/ O18
时间、空间复杂度


$ R5 ?) ]7 L! z  N1 D" \0 a) Z
: A: h6 N* _4 @; x. @9 O9 K8 F
: {2 ~" X6 e& t% X) ~' L( X适用性：适用于顺序存储和链式存储的线性表。

' A% {/ L3 J/ x

3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
1 `3 `5 ^4 `/ H3 Z每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。



即：
若满⾜：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）—— ⼩根堆（⼩顶堆）
8 V! X! I6 F' `/ w  L
) f$ H5 x* A  Z* R② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
  O2 y/ x7 X0 L8 }' b思路：
! a# e8 T) a: n3 c; [4 G把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
8 d# i5 s/ |( ^9 P
. b, X6 Y2 t! [% ~0 I3 w在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换
: k: h6 _, ^( J
过程例子：
( m, Y9 Q/ f* D- ~" r0 t0 z7 ^# ]

% U. d$ ~  ~5 I
6 a( W2 c- h8 _建⽴⼤根堆（代码）：



( L* J/ A1 m/ E1 d// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
7 c0 f) g) i9 g    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
# k' _" D0 N6 u3 W}
. h6 g) Q: D. v. B
// 将以k为根的子树调整为大根堆
# L& e) d6 S7 J  cvoid HeadAdjust(int A[], int k, int len){
1 J& U5 x- B/ [" V$ [# w- U. r' |    A[0] = A[k];
4 ]8 t- ?1 B% i5 E1 b    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
            i++;
5 z4 i/ U8 N5 d& Y: U! j        if(A[0] >= A)
            break;
        else{
: q2 |3 N2 V! s4 x# M; t            A[k] = A;                        //将A调整至双亲结点上
, _$ i" B& s7 H$ E" ~5 w; {& Z            k=i;                                        //修改k值，以便继续向下筛选
        }
    }
5 E0 Z+ R$ A, K    A[k] = A[0]
}

1
2
: u9 }: p5 s+ _! E3 V+ ]3
( D) c3 j9 k6 a  k5 s0 t7 |: G4
5
6
7
8
/ O0 A2 w; r* _/ g9
10
11
! C# T5 c+ e% i/ m' m. F12
13
% `0 H  T0 ?! |1 r: s+ {; i$ M14
+ a% U: m. }0 N8 _7 ?& r7 H. w15
16
17
18
19
20
21
5 o7 z( \, \: H6 Z' C③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
" w# J3 X0 {( Z9 l' N
堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

过程：
% m9 U; E* F3 j# o+ r
1 R( c  |7 F% _! s2 m) {// 交换a和b的值
* m7 }$ d* V( f: {4 O! \: }  Vvoid swap(int &a, int &b){
    int temp = a;
: Y. `2 m8 ^" t6 U0 w7 D0 A    a = b;
    b = temp;
% f4 I% l  P% G}
% }$ F9 @5 y/ |; `# c5 Z) R' m/ p9 d- f$ v
- R1 n  _/ B" F- ^6 Q. r) K- J# U// 对长为len的数组A[]进行堆排序
) h7 S2 I/ X4 \* p" jvoid HeapSort(int A[], int len){
( ]/ K9 v. X, C2 t$ t. d5 c* B! Z        //初始建立大根堆
    BuildMaxHeap(A, len);                
  z5 L5 E. c* D
( C! {0 g9 j( m7 p) u$ `    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
    {             
        swap(A, A[1]);
        HeadAdjust(A,1,i-1);
    }
}

1
2
3
4
5
6
8 d( G1 w' F) \# U1 T: |; m7
8
. Y6 ]: P; \: y) e; W9
4 ?( I! O( `+ M& ?- j! Z; T7 b10
3 k" V9 V" @+ H: `11
12
( t. `' Z% f% a13
14
15
# f- ?5 \( p! P0 b2 X/ @16
17
18
4 ?& I, z, ]0 P+ x19
, O/ M6 a1 p+ U时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

空间复杂度 = O(1)
5 W1 @! s/ M+ l& D) E" f6 Y
结论：堆排序是不稳定的
# f* N) B1 A% u5 y

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


7 t) ^: b1 q* j: f3 }- C1 D* T
⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
2 {5 N) v6 S# u' ?
  V9 a' W4 x: P


3 {' u! A! \9 ]
0 u! Z1 h0 a& Z  }9 U4. （稳定）归并排序
3 `+ g7 F; d8 x' \1 l- q* T" j归并：把两个或多个已经有序的序列合并成⼀个
& Z* l" B2 O! t8 T9 b% Y
① 明白什么是“2路”归并？——就是“⼆合⼀”
, C; d- N- A( H' p
多路归并：
) r" ^1 p( |+ {' |

# F  V9 Y( {2 w② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
. _1 E) n) A& `# _# W- t
B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
" B4 a" d0 F4 R4 R4 e9 p! t7 N
+ M( |5 C. |7 I& d' G2 A- z* _; Q③递归进行分治思想【MergeSort(int A[], int low, int high)】
% x" G) E) X/ g& \. E
  p; }2 j8 A1 V$ f5 Q. K
④ 总实现代码
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
' g/ _2 S9 n3 _* x, u( c: G5 K
// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
4 q0 S$ i9 L  }  I- U( `: z    int i,j,k;
4 F! o3 F9 b7 p8 ^/ K    for(k=low; k<=high; k++)
; y/ s) @: G+ j% K2 b" I        B[k]=A[k];
( j6 K! V. |  |( G6 h    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
% A. e' Y) R  R0 X  v; C. j6 w% v        if(B<=B[j])
/ @' ^0 G" u% N# I) t9 s1 a            A[k]=B[i++];
        else
% |8 D9 |/ b! b7 [2 D9 s            A[k]=B[j++];
    }
    while(i<=mid)
. `0 _3 o( O* a4 @: d. M        A[k++]=B[i++];
$ Z" }& C$ K0 Q" h6 W    while(j<=high)
        A[k++]=B[j++];
}
$ P' S. G3 H0 g0 n+ Y2 W. y( s9 T

// 递归操作（使用了分治法思想）
. ~  ]5 P% O7 \2 c- |, w; ]void MergeSort(int A[], int low, int high){
    if(low<high){
/ x3 S, R+ d; G1 L& u% f  i/ I3 A- V        int mid = (low+high)/2;
        MergeSort(A, low, mid);
9 l6 c6 C% r0 s9 P0 g$ S/ T        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
  L+ x: N8 ~/ B/ J4 W( E% \" }) O    }
}

- z$ @& _4 k  c6 D& u1
3 g& e+ U0 g7 V7 N3 e6 h! q2
3
4
5
6
- h- n& u* D3 S. ?7
8
9
, t- t$ `- z5 v5 }- ?10
4 d# Y1 M# K5 j1 |: M7 y- T! _11
! i/ i( \7 L$ w* X: L12
/ j  S0 \- q* z$ _% v! n. k$ A" U13
6 F0 n% }( O) S/ }3 |14
15
5 I1 f. b% V* g0 K9 s$ J16
17
18
19
0 h2 X" y8 K! K. Z6 T# D& o20
21
22
23
- B* `* R- _  ?$ e% ]$ n# x24
25
$ u& C; Z) m6 g' j5 s26
27
6 o" [7 k; o! ?- H* ~  G+ O% U28
29
30
* ^3 X# v* l" f4 S3 k/ ]时间、空间复杂度

2 b; T+ W. v" ~5 v

" O+ u% O0 J, z' D
5. 基数排序
; ]  v1 d; |) }0 ~直接看课本的过程图来理解P352
1 a+ o* X" J3 d  F
再看这个例子：
7 p. M6 G" s! ]0 N# J7 R' {
$ v# a7 ^5 K* J. D* s6 u; X
; p3 P' Y& k" c; E( M算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
1 P, {8 O( S, K* j* T: p' n/ w基数排序擅长处理的问题：
3 D4 V+ r% R6 y+ f①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。
( D( h% t8 X* }1 V, d4 F" d) R* B6 y算法效率分析：
2 L& |! K* F) M, U" T时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
8 w" p) E3 G; Z% ?- x  |- H7 |/ h( }稳定性：稳定。
5 e! F7 ^8 K  ?0 {8 F% L# J
' v' ]2 U4 S* _
内部排序算法总结

————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969
2 J4 M, l1 A% U7 I( l
8 |/ Y9 [+ d& g/ C1 T+ W
  W; T  x. p4 L! s. q0 P4 a