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

杨利霞

# R0 q2 l7 V0 e, ?* A" y4 |【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
7 e: r- r* T5 e/ t( B& B文章目录
排序
1. 插⼊排序
5 H9 {5 Q$ B6 H% j（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
  p8 J/ T; J. S: B时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
0 S  d; f& J7 _: F: }: Q( S时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
, G3 M+ a) w* e. v* a( }7 d7 b时间、空间复杂度
' X$ z9 H5 s7 b: I2. 交换排序
5 d+ q9 I7 f3 R  S, X, [- K! m2.1 (稳定）冒泡排序
时间、空间复杂度
+ ?0 j7 l! T9 r! Q2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
" _" j3 N& m# `& ^* |( Q3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
+ H0 e" m& }4 }, b3 e5 a3.2 （不稳定）堆排序
* D2 z+ Y. d, e1 g) ~/ e6 l' l5 O① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
* r! K+ B% ~% @0 `; \1 A③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
$ E0 l# {" Z8 A! l4. （稳定）归并排序
  s; b4 S. A" `. b) Q5 b) z① 明白什么是“2路”归并？——就是“⼆合⼀”
( @/ ~" J" W# F0 w# G' B② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
+ J% @. u/ k! A- ~; _③递归进行分治思想【MergeSort(int A[], int low, int high)】
" Q# R% I: ?- U( z④ 总实现代码
" t2 B! H  l# `; J0 S8 m时间、空间复杂度
7 g4 f+ K+ ?- o- a4 E+ \9 Y5. 基数排序
7 @2 u( X, [+ o9 @$ Y内部排序算法总结
, c2 C# B+ V" }$ s排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
# r7 X' y/ u( D
排序算法的评价指标：时间复杂度、空间复杂度、稳定性。

算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
& |2 }+ R7 \* t/ o8 W. C稳定的排序算法不一定比不稳定的排序算法要好。
( o' m7 n  `+ T% A
1 W6 d/ r1 H2 |3 V2 R
排序算法的分类：
$ i! W  ~9 f! s- ~% s- V5 B% Y内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
$ S1 o2 H9 S8 A5 I- j
" f  o0 r7 x3 e/ E/ A; y. I各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html


9 f2 v5 e4 S0 L0 A
; e, e! K( R4 h+ {/ P9 \1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
8 Y& f4 n2 x+ b4 d+ g, v3 ?基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

算法解释：（从小到大）

- }" h' D2 S# F# u" _
算法三个步骤：

3 P' ?+ Q1 \8 t& i# T先保留要插入的数字
2 ~1 ]+ w2 v% j' \7 B- h* |往后移
; B8 V4 x8 x. L9 y插入元素
) d) L* R; g; o- t$ N, f9 M" A2 _
// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1; i<n; i++)
! w! L2 D8 w1 A& N    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
' K  Y4 H3 c: M* F        if(A<A[i-1])
        {           
            temp=A;  //保留要插入的数字
6 u; f; \7 S! a$ _' z
& k( F# J" R, ]/ X  l. M, h% h            for(j=i-1; j>=0 && A[j]>temp; --j)
0 [% q: S" O5 P- ?$ q                A[j+1]=A[j];    //所有大于temp的元素都向后挪

0 B) c+ s0 _' c9 c3 V0 o6 Y& b            A[j+1]=temp;//插入元素
        }
    }
& [( ]- \2 o3 e$ O6 f" `9 T+ x}
3 r9 N+ x  @7 p, D  W: |( H
1
2
  Z6 c- M0 r7 {# |% Z3
: @* u8 e0 [7 ^* M4
5
6
7
; F" }) d( \0 {8
9
5 @# O: ^( @! W1 Q( d10
11
12
, m5 X: i6 N2 T5 J3 \5 Q6 g  I9 N13
14
15
* N/ \+ P8 d( M4 T2 l* }16
17
用算法再带入这个例子，进行加深理解


- p) f+ s$ m% Q% N8 r8 \带哨兵：

# W) r; H7 R, m1 e, C
补充：对链表L进行插入排序
$ s8 e( L1 K4 G; l9 D$ y+ k5 X
void InsertSort(LinkList &L){
- c/ w; Z$ J# {& J1 K9 J8 n9 X    LNode *p=L->next, *pre;
    LNode *r=p->next;
- h; U/ o4 w5 @/ h    p->next=NULL;
    p=r;
4 c, d7 ~( G) @# n, H, ^    while(p!=NULL){
" Q5 ^2 t" d4 J5 d2 C1 l        r=p->next;
        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
$ I# L! b1 `- ?: Y            pre=pre->next;
$ Z6 e7 {. ^) c. l- M. d! i        p->next=pre->next;
        pre->next=p;
        p=r;
    }
& i) |+ Y3 ~6 A/ x3 U}
5 r# a& h" i  h: p1
, [/ F! N  ^1 E& C" V: W2
1 e7 B9 q- W- Z4 `3
4
* P9 l3 z5 i0 b- ^4 r; x5
6
0 n: @$ N( F" }& a1 @7
8
$ ]8 z  t) [, a: O9
10
11
12
13
6 u' t( A: G; j6 R14
15
时间、空间复杂度


最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
! I7 v. o! f! V& G9 C5 x最好时间复杂度—— O(n)

3 W' j6 F- ~/ ~; \+ V& _最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
& \1 A7 Y1 I. a, u3 Z; Y第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
…
" a( I9 t+ a8 N# f5 n+ I' O第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
8 B5 N9 K0 |8 }' h- m9 y, _7 r最坏时间复杂度——O(n2)




+ v* b3 h; l; f8 T( z+ Y
$ q3 |: X! l( {1 v7 D5 ^（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：

; [& O! n4 _, R' ?3 u" c# ?
8 ?7 {, I& ?1 R0 W4 f; w4 L7 C% }
//对A[]数组中共n个元素进行折半插入排序
. W% h: O+ f* jvoid InsertSort(int A[], int n)
7 N7 D  r% c& }/ c" O6 ^{
    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
    {
        A[0]=A; //存到A[0]
- [) }! K) a8 M& r        //-----------------折半查找【代码一样】---------------------------
6 i, r4 Q% {' u        low=1; high=i-1;
) v6 Q- w! y, A        while(low<=high){            
            mid=(low+high)/2;
2 I6 t6 x" F3 }' }5 ^            if(A[mid]>A[0])
                high=mid-1;
            else
                low=mid+1;
        }
         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];
) O+ C& y$ ~* ^! p0 U; z; o
        A[high+1]=A[0];//插入
    }
}
) J" v0 a' O; V" z0 }
1
/ x3 z. ]2 Z) F& v8 q2
3 Q7 o: D- N0 H0 F4 Z) }: D! b/ I* r3
4
5
6
7
6 y" K/ E% b; w8
9
10
11
12
" ~* Q+ o  r/ b- S: S  V13
14
; X3 i- _$ {  X8 M& d) m5 M* A15
16
/ |+ H! j# v; j  {$ `+ l# }17
18
) H% e# W8 `4 x& Q7 _19
+ X' l5 v" y. q& V* r! w# g20
! Q! ?7 u% {8 e21
3 I8 K6 M. m, X. c3 C+ y2 [9 f22
! v& h6 T$ q/ ^: Y23
时间、空间复杂度
空间复杂度：O(1)
* c( o" w' a$ k% O& K) a# k; q
5 z5 b# h: i; C& w【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
% y& c7 [' F% j) f/ }' V
9 {! P9 L3 w- X1 h+ a
（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
0 T0 u. X. z" `+ L2 S( q9 Q
0 z. N4 r+ s* C& O算法思想
+ f; o+ G8 n- K$ Y$ X
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
5 Z% j+ r' Q; J# H. P: C& u, f随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
; ]8 S8 F$ Q; b& o5 M图解：



. B: S: Z9 y/ Y% E& w- t代码实现：
# z  k! F( y* K5 C' `4 e
//从小到大
void shellSort(int* arr, int n)
{
1 {" F: \8 O6 D. {/ U        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
# i  b' l8 s; P) a$ L( A, c            {
7 L: j/ h( j* t5 s. H                if (arr < arr[i - gap])
                {
( `1 G- G) ?8 S$ h& x8 b0 C, }                    temp = arr;
$ c: J6 r$ @0 y  K0 V+ I. v
                    //后移
: o0 B2 }, S3 ~+ N                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
2 P' N* J* z+ _7 S8 z                        arr[j + gap] = arr[j];

                    arr[j + gap] = temp;//插入进去
; t! O' g$ ^5 I$ L% ^' K* p3 S3 Z                }
6 U6 x( Y% L# [$ ^; Y, r7 L            }
            //************************************************************************************
4 M- V% y" `1 A        }
}
: y3 D, U  ?1 K6 o
, _0 N( Q9 u4 X5 n; T  @1
2
5 E4 ^0 x; A' C0 x2 H* c3
/ D  {4 l3 }* j4 S4
: H3 s- Y, w3 ^" o2 W/ O1 ~5
6
7
8
" P  j/ u4 }, w* }& K9 j! v9
* C# i9 x! r2 N+ D5 b10
5 Y0 O4 z# s: H* j  r: ?11
12
# V' e8 d* W+ l# r' o9 s! [13
, J) ]4 X$ |( L! O14
1 Q9 F* u- j6 T% p5 E15
16
17
0 ?0 R! _8 ^5 t% ?4 ^3 {3 E" ?18
+ J. s3 c0 z- e0 L4 `19
20
1 {; r  M+ @6 j  P) m21
22
/ L! g! |' a  A4 L" D- b23
24
时间、空间复杂度
! \2 x' r& U7 F2 t" k空间复杂度：O(1)

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

稳定性：不稳定！

+ G9 n: o# d# z$ t  Z4 z

- o3 H  d, c8 P/ O9 G适⽤性：仅适⽤于顺序表，不适⽤于链表
0 s: _7 k" V) T- x; M% r


* ~0 v0 T: ^9 l6 n# m2. 交换排序
2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

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

实现代码：

//从小到大：
! `$ o% n6 G* F) _, w3 J5 U; nvoid bubble_sort(int arr[], int len)//冒泡排序int*arr
{
        int temp;
0 V& e* B% z1 {7 E' B+ E. n4 }        for (int i = 0; i < len - 1; ++i)//循环比较次数
        {
                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
, w) n' \+ [5 B% F8 q                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
, ^; X6 n, [& E" a. P: L3 l' c                {
                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
                        {
: B/ o% w* c% |& {) H                                //交换两个元素位置
9 c& l: {' x* K6 L$ s                                temp = arr[j];
& |- J: M, X! e                                arr[j] = arr[j + 1];
2 E3 G2 T# ?, M* t) N6 l                                arr[j + 1] = temp;
                        }
                }
        }
3 T. }( w/ w+ r2 B# F# T& n}

* X  e! w. ^$ E$ D1
2
3
- |" A, a) M' a' \8 Q/ f4
5
+ A% L& K" C/ f: B' Q6
7
- w2 J: [+ U9 o' f0 d# u$ ~8
: f  o! T! i7 M3 j; u+ ^2 Z9
/ a6 P' {# |* F  `% }10
11
12
13
. T+ y$ \. x" I1 O2 @4 }14
15
16
17
; D+ R" A- ^2 G5 v  x* \4 ^18
19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
) u3 N* g# T* f. [
//从小到大：
% L0 }( T: u  v' ]; {" q' Evoid bubble_sort(int arr[], int len)
{
7 c0 j8 s; v1 P5 x! _6 h5 P" H        int temp;
        bool flag;
        for (int i = 0; i < len - 1; ++i)
        {
1 Y& ?. r/ r1 |7 Z/ T3 x! k            //表示本趟冒泡是否发生交换的标志
5 E. W) M" b5 j( J                flag=false;
' g  j' K6 h: D; B% D               
                for (int j = 0; j < len - 1 - i; ++j)
                {
" r+ c) l* A7 Z4 k/ q, S4 E5 I                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
                                temp = arr[j];
( A, o% Z* F6 F1 |  R$ B                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                                //有发生交换
# n0 k6 L' m5 C" W/ C4 y                                flag=true;
; [: }- N3 Z6 ]3 m5 r& a3 @                        }
                }//for
               
                //本趟遍历后没有发生交换，说明表已经有序
                if(flag==false)return;【1】
        }//for
1 J: y. n/ R# R! m* o) V}

8 C" z/ |! ^& ~( ^1
5 e& u# A3 k8 ^8 u2
8 j5 W9 Y) u4 L4 Y3
( P' x9 F! x" N4
6 U9 A3 ~2 D! S& T" o3 H" A5
6
2 R1 J$ j9 t  c- x7
8
9
10
9 ~* I9 T& T/ g1 W9 Q6 f# @2 S1 [11
12
13
2 |: `3 E: `  a' f14
+ y6 n9 I6 z! o! c15
16
: @# K1 _- X0 n! b! e17
18
19
' N9 M6 q& o1 P4 c4 T* c# A0 t20
: C# p, y' U7 q6 d5 M7 W2 `" {21
; }( w2 {. I% L& C: _( r22
1 ~/ m) Z+ x& h2 f: z& F: S9 w3 e5 f23
24
5 w  ]5 f& X: p2 R/ v! s. c25
1 N* m: c" Z2 v8 w4 k: k. \5 o26
3 A" Z; F& i2 K) ~' Q/ m: n! G时间、空间复杂度

适用性：冒泡排序可以用于顺序表、链表
- R+ _1 ]5 w1 E8 R7 Y8 `) [! Q% k

& p8 j& ~- d! r5 E
0 n; ^3 A' l8 i" [' b+ L
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
% I3 k+ B5 N. D+ W# T2 L算法思想：
0 r3 R$ v$ o5 q2 B- u( d在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
) H2 X: ^2 O; K$ ]3 R0 ?通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
9 A) ?- n7 O3 v8 N0 Z, R4 a使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
6 D0 j5 [- U2 c4 r再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

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

划分的过程：

% O7 n# Z5 P: t* d% f9 m初始状态：取首元素为pivot，定义low，high指针
5 c( ^6 I; o5 I1 Q% ~3 {
8 O' E" p* q% {1 W. E; m5 b首元素为49
! ]$ T/ j/ v* Q' Hhigh指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置
" {0 y- a! }# O& u/ v

  J0 m, a! u# y3 b" L0 R2 T
4 q0 k: T1 J7 e5 R7 C" f1 R8 }
6 L* S3 b# c% R- w7 r/ ^, `, n# Q
// 用第一个元素将数组A[]划分为两个部分
0 Z' c% n3 ]( Q7 @int Partition(int A[], int low, int high){
! g+ s- G' A, ^: l        //取首元素为pivot
5 w4 K4 O! g5 l6 `    int pivot = A[low];

    while(low<high)
& |5 n. u* ~, v1 N" m    {
            //先是high开始向左移动
( v; j: \& u9 o0 m0 T  {! O6 b        while(low<high && A[high]>=pivot)
            --high;
        A[low] = A[high];

        //随后low向右移动
+ |! j8 G2 y9 ~  ^$ S+ j        while(low<high && A[low]<=pivot)
            ++low;
5 `2 y/ O" q2 M3 n9 R; c        A[high] = A[low];
    }
" e- }* \/ L# P0 z2 H' m
    //low=high的位置，即pivot放在的位置
' `7 f$ m" U% n3 g: e. i7 e" `1 Z    A[low] = pivot;
! X# \7 ?* d4 ~$ G/ b& E
3 e  J1 I5 G, w% E4 T    return low;
# |1 D  W+ |. \( i1 n+ m* `, x}

// 对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);
" n( r) E6 _  L' M    }
/ `: f! u! j( a0 A}
0 f8 J' o6 t$ x
1
# c& V; b* y3 F* u' ]4 j- W2
3
; D, _7 E' R3 G9 T- `4
0 ^, n9 h" |- p2 _$ L3 w' U5
6
( q0 |* T. X- Y. h, b7
4 c9 P: ?9 R- P: S8
9
10
" S8 j8 D# v5 ~# S11
; g6 q9 ^6 e' y" N  r0 F12
13
; v6 A3 m+ G! F; g) t. o# b) D14
( ?" r/ x" u( Y15
16
17
2 i: N' r6 Y/ E, J% Z; O+ H& H18
. t' C8 [) L2 Z2 f$ R19
3 z! I; \/ k7 @1 H% L20
21
, b2 p2 r6 ]9 V; I4 ]+ ]" T22
3 d1 I4 m) z5 C- Y23
24
3 o, ^& ?/ f* A/ N: m8 }25
/ q5 c' C7 u2 L' I. y26
$ {* l* `9 y: ?' c  p27
7 ]% u- N# j, z) J3 |' a9 x28
29
30
9 b3 r5 Y. V3 I& t31
9 o+ T& t2 `. _: s# C* `32
& c6 H8 ~$ R  t& Y) G( i$ H时间、空间复杂度

  a' A4 n1 V' R! |
把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

( s4 W4 O. u4 r8 Y$ O3 h$ kn个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

时间复杂度=O(n*递归层数)
* V' V; D# G" k最好时间复杂度=O(n * log2n)
% Y2 x8 g: ^/ J3 {; p2 M6 e最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

6 ?" ?3 b3 c4 u2 h空间复杂度=O(递归层数)
& M/ E2 M0 p- e, `4 Q* i最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)

最坏的情况

5 n5 d! [) i; L- d

⽐较好的情况
, Q/ @9 G2 A  G

3 J6 K8 K8 l: V9 }5 y
不稳定的原因：
3 f; l  f) |; `) @7 q$ y/ G( }

, r( T  B1 x* \5 t7 m2 g5 T  D


3.选择排序
: n+ r4 m$ P' M9 z选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

% z6 _  d* A) |) `8 }1 I1 y3.1 （不稳定）简单选择排序
, u+ d& O8 h: Z9 L$ u( x' }算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
, d7 ^" a0 S( b* k% b
( a. [7 t( J% F
. i3 u; f8 U: B
+ `) D) F) s2 ?// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

; t) T, P0 m$ N5 ?5 I$ ^// 对A[]数组共n个元素进行选择排序
$ g( n3 E, }# e' M3 xvoid SelectSort(int A[], int n)
5 O. f" ^) U+ h8 }* h{
6 |* [: |6 Q) |0 Y        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
5 W: V# d2 j5 S5 z$ L: i5 S7 a    {                 
1 b( g& K: {* K: s5 I        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
# O' L! ^# s8 I) w            if(A[j]<A[min])
                min = j;
        }
' v( m) f  p; P0 J. b# I; n        if(min!=i)                     
            swap(A, A[min]);
  b& j8 Z/ M+ `; G9 E" s    }
}
& ]; U' ?5 R6 A( d6 [9 J5 Q1 d0 \
1
$ \% V# R4 t/ {2
3
) T/ b8 x& ]' [! x: I( K% ?4
: p0 |' j$ |, G1 Q5
' U6 l" a$ B1 F- c6
1 e; h2 t; `$ e- |# q6 O/ l7
* w+ d, E" z$ e6 J3 Q# z" {8
6 T! n& J8 }4 _0 i  y9
10
11
12
: S( J- Y' J& ]' r13
14
15
16
17
18
19
+ F$ X' a- g# K/ s3 S7 d, C1 T* w20
: O" A3 u3 `2 Z  T/ a, S2 P21
22
补充：对链表进行简单选择排序
5 X  d8 s8 a& w" T, t. m( a
1 n) R! C5 b- Mvoid selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
    while(h!=NULL){
" z  B  s& u  Y/ c  b; {# U        p=s=h; q=r=NULL;
        while(p!=NULL){
9 j- H3 G2 [7 M# t9 G. ~% m            if(p->data>s->data){
                s=p; r=q;
            }
3 _8 R/ I* n  p9 Q            q=p; p=p->next;
        }
        if(s==h)
& e5 X" C7 S: c            h=h->next;
        else
            r->next=s->next;
        s->next=L; L=s;
. ?+ M; L/ B8 `    }
4 O! A! M9 Q# c}

1
2
: J# x% d' F! K3
4
3 W+ R) P  q; Z7 l% a; X5
6
3 L$ [1 Z& d% ^. P7
8
9
10
! Q0 z$ R+ U3 C6 m# f: `11
% e+ [: |6 v( f! L( _- I9 [12
$ Q) \9 s# s  b13
1 }5 N- k2 Z- ?  Y% G7 q  L14
; M4 W, d7 @$ @6 u" E: o15
& t7 ~( N  `1 e: E+ w. c- S) O16
17
18
& {+ n( S4 E9 T; U" X  g$ E7 _! I时间、空间复杂度
4 Z" A% L2 Q: `" G+ ?
. v, Q9 i+ S" r
0 f- T; M# n4 |  \  P* o
4 ?: l; c( j7 J' u
6 {/ x# W+ L  o6 w" K/ @& }2 T适用性：适用于顺序存储和链式存储的线性表。
2 I) i" D$ U+ T7 z; o% S: w; z

) l5 D4 ?8 N, _% P0 D+ ^/ R+ P
4 v8 b" H( D1 K( s3.2 （不稳定）堆排序
+ c9 u0 Y: T% z! p- w① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
- c: M1 L9 ]3 F8 C/ s堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
6 z1 k5 n* }1 r0 C% _& r" k) i或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

. R! a/ v! b5 f' _
, V8 k% j# {; I+ k
即：
若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
! Q+ ~$ K* q% M若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）

② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
2 s. c7 C. V/ u5 [- v思路：
6 V4 ~$ i4 ^# u/ w3 a把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

% K; h/ C4 w) @* S在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
! F, I# o/ u& b, u% S
检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换
' G$ }# o0 p1 I; s3 ]' t$ N
过程例子：

3 r9 ~1 J. G$ m2 u) j4 E

建⽴⼤根堆（代码）：



// 对初始序列建立大根堆
7 O6 z7 v3 ?- X5 G3 q, Y5 nvoid BuildMaxHeap(int A[], int len){
6 y, a; T' e: L- U* o+ p    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
. V5 U5 m4 ?+ T$ v$ p. n7 e        HeadAdjust(A, i, len);
}
" B( @( h2 Y+ f2 I
) s: T+ Y& Y1 W+ l0 Y// 将以k为根的子树调整为大根堆
, d0 \- I! @  rvoid HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
4 L- }% H$ P3 L/ U. p# H    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
2 M( P1 `7 T- k( s# v5 N) a        if(i<len && A<A[i+1])       
            i++;
/ X( |! A( L1 [$ V4 T" t        if(A[0] >= A)
+ J. ^+ x' b$ J5 e: ^5 \, d            break;
6 \8 R& A8 j' [        else{
6 V$ {7 u8 d# ~$ l            A[k] = A;                        //将A调整至双亲结点上
) Y6 z+ A3 z7 q  K8 i( y+ c            k=i;                                        //修改k值，以便继续向下筛选
4 i. V+ ~6 e  d2 ?5 a        }
( ?  ~0 e4 U& i! S- n& e    }
    A[k] = A[0]
! E  d2 a7 p0 o- j4 @4 K}

+ M! M+ |$ E) {# O; L1
4 n3 t  }% C+ h) E) B1 R2
; r! a1 ^8 Z! E) b8 [9 ]3
; u# `0 z! F) k3 u4
& Z! t+ J  ^' S: H& h3 r+ f' g1 _5
6
7
  ^* w' q* z: [1 H. Z8
( H& I* Y2 j0 q9 O; H6 c2 n9
10
/ c4 z0 n7 W" u0 R( ]11
1 Z. W- E( |6 [) W/ S4 n12
13
14
15
: v  T* q$ w. D& @' [; W16
' b$ J# s: U* P6 Z8 i4 J7 z17
18
% }* ^0 X3 {7 c2 @19
% ~  Z+ e$ c  F! Z20
; p. E; f: ~+ g2 s0 S21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
6 t- q0 A- {# Q* w7 J- G" x; Q3 Z
堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
! A6 e, G# n+ {
7 K4 `4 A5 s4 |# I  ^; u过程：

6 }& k" Q% ^5 W1 r' H; k. S" d! h// 交换a和b的值
7 m# i# J3 j# a8 ]3 b5 ovoid swap(int &a, int &b){
    int temp = a;
    a = b;
2 i9 V  g7 T& ?4 n# s5 ^9 m# ^5 h  c    b = temp;
3 A7 F) R% z' W, @7 H6 X5 W/ }}
4 @8 y) R7 q: I/ i: j9 [1 k7 l! c
# x& m+ L$ M! L// 对长为len的数组A[]进行堆排序
- _+ g( J3 a* S6 R1 ?( Gvoid HeapSort(int A[], int len){
        //初始建立大根堆
+ A2 p  B: [: W    BuildMaxHeap(A, len);                

    //n-1趟的交换和建堆过程
; _; Z4 O3 @* z$ i# m1 M# O    for(int i=len; i>1; i--)
! h* s$ z9 E- |& y5 O8 O) m    {             
5 d8 y, M- P0 H- d. y        swap(A, A[1]);
& k8 g7 Y/ L% K) r5 u9 U        HeadAdjust(A,1,i-1);
4 b# T' A) D; {, S  N* h4 y, E# z    }
, w. I7 |4 W  N4 t' K5 a6 F}
. C( x5 ^. O' ]% U" I* [
6 [& m0 T4 T& y3 w/ [1 j+ B; D% Z1
2
3
! @& m% f2 l+ i4
5
6
( L+ X* V. ]& j! m6 S5 c1 F6 S6 ~7
8
9
/ S  J2 l3 [" s, X/ }8 u1 x# g10
11
12
3 m& |2 x- R2 X- L: p' J6 d! H3 n13
14
15
- O. f; R# V. j8 X16
17
3 E! K& a/ k* f18
19
时间、空间复杂度
; E# W/ F! ?' H- T  i# f建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

3 s6 A- C6 X2 w. k; @) D: i空间复杂度 = O(1)

结论：堆排序是不稳定的


8 O5 f1 b$ @# @9 }④ 补充：在堆中插⼊新元素
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌
! g" u' c8 d; J- c$ r


) b7 Z4 G# E% [, [⑤ 补充：在堆中删除元素
% ^2 u! B' n% I! M% ~7 K被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌

3 i8 {+ H7 K8 G" K: N& L
: H' a2 Q+ T  C  \
4 Y& Y( r+ X4 @
5 a% ~8 a" ~; b. f, @  c
- F4 P- O1 E* S2 m" F9 W$ P4. （稳定）归并排序
, u" J& M1 x7 T/ L/ V- x" O归并：把两个或多个已经有序的序列合并成⼀个

① 明白什么是“2路”归并？——就是“⼆合⼀”
7 b% H+ f8 l; ?* c  v, F
3 Z2 o# r  ^9 n9 W4 P多路归并：

7 R. S& ~9 c) l$ L
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

( L; ^, Q3 |9 Z; w1 r- v2 x③递归进行分治思想【MergeSort(int A[], int low, int high)】
4 v6 j& ]. o' {

④ 总实现代码
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
0 z: y, h4 u* s: o  z8 K
// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
    int i,j,k;
; k0 A: n- I! y; t4 M    for(k=low; k<=high; k++)
* R8 [9 Z* X5 _; j# q) |+ y0 o        B[k]=A[k];
    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B<=B[j])
4 e# L; u. ?. ?3 D& {8 v            A[k]=B[i++];
) G8 |) G3 \& _3 J1 U3 G        else
+ |, r% R' p7 Q            A[k]=B[j++];
    }
    while(i<=mid)
        A[k++]=B[i++];
8 i# T3 ^4 T9 I    while(j<=high)
+ J( h$ c1 ~3 A        A[k++]=B[j++];
}
$ n) A, h) x8 y8 X( w

& Y) q0 a9 c2 r' j// 递归操作（使用了分治法思想）
void MergeSort(int A[], int low, int high){
& D( c5 F/ a4 L5 U    if(low<high){
        int mid = (low+high)/2;
        MergeSort(A, low, mid);
# d% R. P/ M( D        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
    }
3 b4 i, r5 ^- D}

1
4 Y4 \0 n+ G" @# f5 P2
3
4
; @: n. S2 ^4 |9 a' B5
" x) y( r& o7 E6 c  T6
7
" P, G: E9 M1 o% \8
9
1 R8 C! {2 P4 c1 l+ ]% r9 [10
2 D' d7 G( j  L6 e  d1 W6 p11
( {8 H) S. `$ v6 z6 z; z12
13
# o( Q$ \& h8 T6 w$ X  m; e14
15
  z0 R! [! b& C4 u: W' O3 o16
% j2 V; v7 t" u# u6 a/ @, ]17
18
19
" x0 N/ _8 q0 |/ T4 }20
8 l! v. _; I7 {  J) T8 \21
7 {( P3 R7 T' O% W7 d6 e22
0 H6 f4 _  a3 i7 M: z# s3 B23
24
25
  P. p3 ]& W# ?. N, M26
27
: ?8 d4 Q* v% r; k+ s28
6 C/ |; p  k, g/ q; h; P, u, n$ L7 P29
30
1 w! ^2 ~" p8 ]- I时间、空间复杂度

6 \. K8 O8 n7 q6 L5 J
; E. K; X2 F0 o( E1 \0 R0 ~5 |
7 v# x$ t1 V# ^. \
5. 基数排序
- Y! v4 ]& N; k+ L1 [9 _; D) w$ A直接看课本的过程图来理解P352

再看这个例子：


6 _7 h2 E/ y$ C3 A& w5 i6 ~算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
# p  C; ^  i4 d& Q基数排序擅长处理的问题：
6 Q; i; n( p9 W- s+ u①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
# P2 v4 q! H( H: a+ l) M. Q  S③ 数据元素个数n较大。
+ j7 v7 c0 c4 R; D算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
, G/ e0 E) E- x  u8 A' _( |稳定性：稳定。
3 n6 q0 c5 Z# P" Y4 z$ v& f
; }- ]; j; S8 L8 X# }2 b1 Z1 x
$ y5 q; F7 M% o# B2 G0 I2 o内部排序算法总结

9 M$ }: H! n/ |- f% }  _————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969