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

杨利霞

3 n  H  Y1 V9 t* t3 L  x【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
) T  e! d. t+ V排序
1. 插⼊排序
9 R9 K, K. E  V' D6 ]# i5 h2 N; m（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
2 d* y! s; v, {2 j+ o/ E时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
* j0 _0 D; f' ^2 ?, I2 g9 m( O: H时间、空间复杂度
- T4 h2 @; w' F7 A1 v（不稳定）1.3 希尔排序【多次直接插入排序】
& d: a) f9 [2 K7 s: `9 E" M时间、空间复杂度
0 r2 a: |3 u: g1 s! F2 t, q2. 交换排序
" B- k0 j: P) ]2.1 (稳定）冒泡排序
! ?3 }; h. l+ ^0 u/ `时间、空间复杂度
3 A. B' F! V8 p2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
$ W6 M6 G  m# e& r" N时间、空间复杂度
④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
4. （稳定）归并排序
! ]0 p" }/ ]3 l4 _9 O  M' S① 明白什么是“2路”归并？——就是“⼆合⼀”
1 j/ i; z* y* O( ?② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
5 A- l# x4 X& h) X+ M. E* I) ~④ 总实现代码
时间、空间复杂度
5. 基数排序
% P7 ?) i$ i. B内部排序算法总结
排序
! z6 A4 X" X7 o, ^排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

& o: t7 I5 R9 [# R) ~/ D0 g排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
3 S7 x" T( `2 R. _' W. b* @0 y6 |8 k
算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
3 Q9 |7 u* J: J1 m; Z5 Y, C1 H稳定的排序算法不一定比不稳定的排序算法要好。
* V2 ]: }  t. K" e5 I+ Y0 j* k

/ N) t$ O6 N/ K9 i排序算法的分类：
7 i) F6 |7 N& f# z) h6 {8 l/ L内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
& U* e$ z/ E* ^" z外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

  w- f2 i- |  T  ]各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
# ~2 D2 N& R9 }% P' z


1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
. q( Q# S) {0 r% ~* p/ G基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
4 h3 D( y: x5 H2 Q' N% S/ i- O
算法解释：（从小到大）


算法三个步骤：
7 c) c& G4 C& J$ y
先保留要插入的数字
& O6 k6 j7 z2 `往后移
2 ^0 ?% c: ^6 t, h# R  \: \/ k插入元素

// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
3 U+ G; z! A4 \- E7 A7 I" h    int i,j,temp;
    for(i=1; i<n; i++)
% e# A* P& V, N! H1 D$ D7 B& O    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
# K" g7 H; _% e8 x8 ?9 |5 T        if(A<A[i-1])
- C" f8 {+ h% r* C* e" A        {           
            temp=A;  //保留要插入的数字

4 u& n" A! s; ]            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪
7 V4 c- V7 R( h  d- p
$ E4 _" F4 a% Q$ \# l/ L            A[j+1]=temp;//插入元素
9 |) ?8 }: v$ x* R. d* t0 Z        }
    }
8 T. V! Z4 A" d  G}
# d/ [( o1 Z1 l. P* o: C
, W9 a0 v. j8 F( y  J' Y: U  c1
2
( M$ W8 O: R3 d7 v( V$ n8 n" h. ?3
" E  [' F8 L: A8 {- l5 v4
5
6
7
8
9
10
. U, ?0 W* b1 A- r" o/ x11
12
13
14
15
16
17
  w# Y1 p0 N' l, d  f用算法再带入这个例子，进行加深理解
% Z+ k' k8 c- G4 H# ?7 J7 ?
5 N' `! W( ~. i' q: i$ i, {
带哨兵：
2 n3 I- D$ R! l8 N  Z$ l4 A+ H
, a6 j* i/ n! \0 l; l: F$ {
补充：对链表L进行插入排序

void InsertSort(LinkList &L){
    LNode *p=L->next, *pre;
    LNode *r=p->next;
    p->next=NULL;
    p=r;
& j  G3 Z9 c* z5 l: M2 K; b; R1 F+ r    while(p!=NULL){
        r=p->next;
        pre=L;
, y- {9 h. x: {* H        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
        p->next=pre->next;
        pre->next=p;
        p=r;
% V6 U1 x4 e2 @0 Z2 _    }
3 h& [7 Y: Q1 T9 {1 j}
% B' r8 Z% C1 z& G2 l. n/ ~) q( p1
6 @) X, ~2 z- o. b9 V1 G7 d2
7 s& W8 ^; }# f) X4 v  ^6 f: v3
, E* Z6 I0 [) C5 z  V, l4
5
6
. p+ ~2 y5 T! E5 k7
8
% l" Y. @5 M* Z- Z0 h0 ]* h/ B3 P9
8 Q' [6 J* y+ J5 u- t. h10
' c1 t0 W- k. T! ]0 {11
12
13
2 J4 k8 o- J# i14
2 [, U, @0 l) B, F, s5 p15
- P* P( d5 g5 u时间、空间复杂度
. J: m" z7 n( |/ V: I" G

9 C- z0 v) _$ V2 o" y最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
! o" R/ n8 D7 K3 F! B最好时间复杂度—— O(n)
2 A2 y; Y* S$ _' H
最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
…
/ x4 Q/ Q7 O/ ?3 h第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)
0 ?) w3 o; K( ?# o8 o: }* x/ n& d3 O
0 ^" e. e( q/ b) [1 F: w
: f9 }" j( ^+ c0 j4 a3 K5 D


; V8 i2 i& L5 g7 w' e* @' D（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：
! p2 h. ]$ s% o

; N4 M. j% ?# A! U$ h1 w
, _7 m; X0 b+ P; A% j( M2 V, G//对A[]数组中共n个元素进行折半插入排序
9 S3 h& U- D" p8 y( [4 wvoid InsertSort(int A[], int n)
{
    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
    {
        A[0]=A; //存到A[0]
5 [, d4 t0 \8 v; k& |: h& F" m4 K        //-----------------折半查找【代码一样】---------------------------
4 t% W8 K" u2 o4 e" y6 l& s        low=1; high=i-1;
# Z- S" s6 H2 m  [( U/ k        while(low<=high){            
            mid=(low+high)/2;
# \  t7 c& O$ u9 y            if(A[mid]>A[0])
' V* Q/ Z+ x7 `; O6 u- P                high=mid-1;
            else
3 \/ e4 r8 G1 ]# G                low=mid+1;
        }
0 w. d! p+ q1 |2 e$ `; u* Y3 O         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
, O+ W8 @& V; N) a$ N            A[j+1]=A[j];

$ H7 M8 V7 b% a5 R5 }        A[high+1]=A[0];//插入
( ~+ z: W+ C# F1 z( V9 e9 k    }
# z9 s# h: s, O, @% h}
- L# ?3 v0 r& V# f+ v2 w" P
1
! O$ v# U: a# w8 ?4 Q: r( T2
" e2 P4 R! G# C$ I% `3
4
( F& b& n( n! D' w3 d5
7 q; W) F% I9 }6 B+ F' I6
: r) ?# X4 j! L$ [! J7
8
9
  J5 P2 G# P* f& D10
11
12
13
14
15
! I* ~6 Z4 {# ?16
5 i- a4 r. O* R, z4 P- ?' m17
18
19
20
21
2 E. s+ ^/ |2 H22
23
时间、空间复杂度
空间复杂度：O(1)

4 {- x" c, ], a% F* T/ A1 x9 r【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)

. b% j  [* N6 L% ^
9 P. u5 J- @# w, t: z. ^5 X) K（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

算法思想
2 s6 V4 v3 L6 `" l; G% `: c
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
( p2 |$ {/ {/ u/ [8 a$ z随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：

3 e7 x" h& j7 Y- P

代码实现：

5 n$ G: [8 t0 O& d# E: b//从小到大
void shellSort(int* arr, int n)
1 A3 o9 L3 C! p& {' x# I% R6 I  F  X{
. b8 K% k# s9 M, W3 P2 C, O        int gap, i, j, temp;
; F: \9 x5 l3 ?  L9 K/ r. p8 U        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
  f6 E4 V; `6 W+ {2 J( }& y            {
                if (arr < arr[i - gap])
                {
, D  S" D; X4 Z- c% T                    temp = arr;
! F: P% R" `5 o! P7 C' r3 i( _
                    //后移
* `& @+ b8 y5 F! _                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
0 p5 L: y! W0 H                        arr[j + gap] = arr[j];
3 Q4 m$ M# B/ t% Q
3 k7 z" x- n6 E/ {/ F                    arr[j + gap] = temp;//插入进去
                }
8 \+ S' ~' E! v$ ]4 g; F% m: s9 ]) `            }
  f1 h- a; r8 D            //************************************************************************************
+ Z( {8 }* u+ F* F, ]* M6 V        }
& b  |* J. g0 \# h+ O2 [$ K}
0 d! ^3 J1 r! B5 x# i+ H/ ~4 Q0 f
1
2
* N: p. n9 G4 ?* W) E3
, Q9 U: h* K4 i' {4
' w' t+ F0 c! G* K9 w) p5
! j! f: W+ y0 w6
7
$ m+ m0 l; V! {8
9
10
- S9 l" U$ O' V) s# {( a11
12
7 {5 ^6 N- F3 x' t2 y+ y13
: m! y. h, }. V0 F14
15
  `; P$ c1 M$ }. Y; J16
2 R* ?( ?2 U3 I0 U% {: j17
18
19
9 n5 W* X0 |% M% C20
21
22
9 a  `: e. I: V. n3 J! q23
' ^. C7 b& J+ f4 X: I, H24
+ Z* u2 O. L. |9 J0 K) n时间、空间复杂度
9 g: u. E( M2 ^! D  X空间复杂度：O(1)

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

8 q2 S! z$ c- i稳定性：不稳定！
: D3 {& W1 {* Y. x3 o( ^. {% t
- ^5 d9 k' n9 Y, d" P

适⽤性：仅适⽤于顺序表，不适⽤于链表
0 b6 m- X* u& B: h. K; r" `


3 a8 Q! P2 k* x% I$ W2. 交换排序
9 H& @8 h" r2 u; [5 O  R- _" h2.1 (稳定）冒泡排序
3 m) ?5 v$ }+ ^" C英文:bubble sort     (bubble 动和名词 起泡，冒泡)
+ O( H5 m2 j- |4 C从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

: P7 [$ r. p  }" D每一轮比较会让一个最大数字沉底或者一个最小数字上浮

& K$ x$ u* ?4 }& I; ]这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

实现代码：
  T  n" d7 f6 R  @
  l6 q- s% k3 Y//从小到大：
' Y& B: Q* ]4 X6 n  S6 Ovoid bubble_sort(int arr[], int len)//冒泡排序int*arr
0 A. p0 i/ l* m7 I{
        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
/ l3 R. Y$ D" o! w        {
                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
' l9 {7 n# Q. G8 W, r                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
7 Z5 ?0 ^3 b1 c# l2 g$ I3 ]                {
4 a/ o5 I' u2 |/ r' h4 o                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
9 Q- M0 \* }2 J3 E% {6 K0 R7 \                        {
/ w/ i9 K. [  t8 T# |9 l                                //交换两个元素位置
- }$ }" s3 @$ }$ ?/ F( ?1 e+ N! Q                                temp = arr[j];
                                arr[j] = arr[j + 1];
% ]/ P# x5 w) J* M6 L2 L                                arr[j + 1] = temp;
                        }
5 F: W) I  c; g/ i, x2 P0 o: S                }
' m/ ?. T. u3 _! l9 c3 R) l- f        }
" L4 @' P; T/ O* }% Z* a}
& U( P( \8 t2 J) s% H9 `
+ Q* [4 ~. y1 h0 \( b/ X  C7 ~% i1
2
9 f' B8 }7 |6 w, ~' U& B8 C3
) v& U% Y0 T3 v% I6 d$ i2 X4
5
; J2 H  ?6 h8 d. v6
7
8
0 O' ~& d  v, H  i3 l$ E6 u/ G9
, d0 {& k$ {+ r, v  B* `10
* k3 p1 e8 p* G1 f11
0 ?; I5 [6 P9 M5 G; L+ P% |12
13
5 p' C3 q+ q1 {' R7 J) |14
$ G0 ~! a2 {8 {2 M  R15
2 r$ V. D* O" D5 [. u- \: u4 U16
3 o+ S& Z/ m9 T; L6 w17
9 m- U% Y. A8 O0 I8 u18
$ N- f! H) ^" Z; f9 ]0 v3 @4 U19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
" V/ x" Y4 S0 Q* o  d* y8 |7 T: i; ^
//从小到大：
void bubble_sort(int arr[], int len)
{
        int temp;
+ [" s$ V' {0 W! @! U7 B/ M        bool flag;
. \  h1 G. Z( _0 `        for (int i = 0; i < len - 1; ++i)
        {
0 g0 W0 w* y; d" L, K            //表示本趟冒泡是否发生交换的标志
                flag=false;
2 v& d& `5 F4 h( f               
                for (int j = 0; j < len - 1 - i; ++j)
                {
                        if (arr[j] > arr[j + 1])//稳定的原因
  G" `4 X+ `% d/ C1 V                        {
                                temp = arr[j];
                                arr[j] = arr[j + 1];
2 u8 P; f% ~9 M. B* u                                arr[j + 1] = temp;
% d% q* ~: T& j6 o                                //有发生交换
                                flag=true;
                        }
                }//for
               
                //本趟遍历后没有发生交换，说明表已经有序
                if(flag==false)return;【1】
        }//for
" {0 x2 f2 g4 e  ~) K4 j: k}

1
1 \+ R' v1 `2 B! C( `2
  ~% \% l* [2 c  T  }6 B1 y3
4
& W9 h# n& @& H; N  I" Y7 `' _5
1 k" e! z# x* ]" g; u+ u4 }6
# w+ R) d7 Q( s9 p' M. h7
8
9
  V9 P- z. R; m4 u4 X10
11
  D' l, Q3 \! p' W7 }- B12
13
14
15
2 i/ V- n6 x: z16
17
18
19
20
' K) Y2 M7 f) q2 i; m21
& ?; C* L. F+ E7 Y4 r" v; I22
23
% f& a9 s- U/ `7 K7 V24
* s/ F6 [4 [, V6 w1 y25
1 S, y+ ?3 b1 @" z26
时间、空间复杂度

适用性：冒泡排序可以用于顺序表、链表
. |5 m. V/ {2 H' c0 n/ x2 ~  K5 r
) C9 L0 f7 r3 Y7 L, ?4 l% V; X5 {

6 w; u) `, e3 @5 M0 |% C! X  }
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
. I- a: A+ f& \, t- d) t在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
( I" R6 O6 j  K* J  @使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
* l; R) E( e+ ^1 o0 U
& l2 \. F# n  a3 r7 ]& B' v/ d2 j然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
; R2 `; [' }: {
划分的过程：

初始状态：取首元素为pivot，定义low，high指针
; y  |1 q" w( C' Q- {
首元素为49
high指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置

' r% L$ {. p, f7 X3 _4 B5 U
* W# h1 f) B2 \% i5 q/ H" x0 D
2 z6 X+ ~/ j, o/ x. K! S

// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
/ ?" b- ^! R  y3 Q; I* g" ]+ g        //取首元素为pivot
    int pivot = A[low];

    while(low<high)
3 d( I* U' v; r    {
% L& ~) k/ n! C            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
            --high;
/ W. y1 D- l4 L. M, `7 v& K4 E* g        A[low] = A[high];
: t% l4 n2 h3 @4 ~- ]
        //随后low向右移动
9 r/ q+ W/ V% j! i        while(low<high && A[low]<=pivot)
7 a/ ?' L& e2 P! [- P            ++low;
        A[high] = A[low];
    }

    //low=high的位置，即pivot放在的位置
* U" d* G7 V8 g6 E    A[low] = pivot;
; H+ r  z5 {6 M
* X  L% y. }6 {4 _+ t/ a    return low;
}

// 对A[]数组的low到high进行快速排序
- A: I) T  X1 W, w/ b% [+ m5 [void QuickSort(int A[], int low, int high){
    if(low<high){
        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
( C! x+ `0 a* l2 F1 V  ^, X        QuickSort(A, pivotpos + 1, high);
    }
}

: T2 B# H* |7 S* K, u) o1
2
3
4
5
* c! A# V" t' p' |2 A0 H, u* Y6
+ q" P: J7 {0 q/ j7 p! g; K3 r7
8
2 U  N8 U" }8 q+ |! ]6 ^# t0 h6 S( [9
10
11
12
# x' \1 ]# G; o) |% w) o13
  o- p* q- v6 n14
: z. X; k5 s4 l% C& A+ I/ F4 i15
% @" q( ~7 X% G/ t& U16
17
18
6 u3 S1 n( }& `2 R0 |19
, A3 ?" N) v" V- k: R20
21
6 ]! ~, l7 ~% ~/ Z$ m8 q  o7 i22
23
& U8 X- `: t; t5 i/ ~24
7 @7 S6 [! Q# y# A4 q! J8 a& ]: J25
26
! {* O0 f7 ?3 C0 H7 c. s' q) t27
28
29
30
% O" b% ]* O0 O31
32
时间、空间复杂度


( S; o. O6 ?7 S# P+ ?/ w  r* `把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
  m; {+ ^( I% u( p
n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n
& a5 i- b( g% j, P
( A! A4 ]" Q2 e$ I. L时间复杂度=O(n*递归层数)
% k1 Z" }3 K8 P3 v6 ^' C5 k最好时间复杂度=O(n * log2n)
; k8 Q% c) b& z0 |最坏时间复杂度=O(n2)
5 Z' B/ [7 L. m, p6 B4 T平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法
8 N. ]5 u6 P# \# t% L' i
空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
- c5 s1 F% @" r" l' o2 c最坏空间复杂度=O(n)

0 _* ~5 G& ]7 U8 }0 y最坏的情况

/ F, Y: @' ]8 b# b

⽐较好的情况



& J# Y7 E9 m1 A2 }0 j& t6 k不稳定的原因：



6 H; @& s; o0 L2 E
2 w+ G6 p/ E) w* a% y
# V2 ~" |; R7 ]# d3.选择排序
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

9 F  c1 c, w: U: e/ `8 O* P4 y3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置



// 交换a和b的值
void swap(int &a, int &b){
2 O: S; n; @2 @' u, z    int temp = a;
    a = b;
    b = temp;
, n5 P" O+ C3 P3 s7 i4 x, ~}

// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
# _& W, W2 i, R- F$ T! {9 e{
        //一共进行n-1趟，i指向待排序序列中第一个元素
8 K- @. N& `, w% t" m# o/ x    for(int i=0; i<n-1; i++)
    {                 
        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
3 G7 |4 ?! t  z) P# J$ w            if(A[j]<A[min])
" ~3 I  ]9 H( a% M3 U2 B, {                min = j;
        }
/ e0 Y3 [% R$ _( C6 U7 h! b6 s        if(min!=i)                     
* \9 L/ d$ V4 i) k! ?' a& o            swap(A, A[min]);
    }
}

* e3 D! l. Y- V" e6 F6 @1
- g* T+ `. C5 m& S2
3
7 C7 O- R+ v5 v+ @7 x- U4 n4
9 L! Y" i4 G2 {# m4 ~5
) n. h. N, E( N2 r9 b4 \6
7
! I/ G3 ]; c8 c0 X. y8
, ?0 m0 R4 D. G0 m/ W9
10
11
9 W. ~4 x# R$ m3 K12
13
% H2 ?! ]& }' |$ N% R8 ~14
6 Z3 H' e9 K4 w3 B15
+ Z$ t, H0 j. S: X16
) m) |0 z0 |4 _8 G. `2 i6 _- j17
18
19
20
21
: l* k* W% I. c1 `22
& Y  r2 `  R% p$ Y" @+ G0 u+ ]3 R补充：对链表进行简单选择排序

void selectSort(LinkList &L){
5 H4 I' q" c; H    LNode *h=L,*p,*q,*r,*s;
" f: F9 J+ m0 \: J0 |    L=NULL;
6 a* t" i( J- D. @. {    while(h!=NULL){
7 K0 L5 a8 O2 v# m1 I        p=s=h; q=r=NULL;
# U& o' E; h* Q$ E4 M        while(p!=NULL){
            if(p->data>s->data){
                s=p; r=q;
            }
7 U. \" o( }9 `9 h            q=p; p=p->next;
+ ~) _! A* Y8 f        }
1 ]( q7 r; o- J' ]1 {        if(s==h)
% V( ?& R- t4 g/ m- a            h=h->next;
        else
            r->next=s->next;
        s->next=L; L=s;
    }
}
% X& z" ?% K/ R  y$ y: a( v, [' |
$ W5 l2 i9 G% X8 i1
; m$ q$ h& R, ?# E8 ?- Q2
3
4
5
3 F  C$ ]" T6 ^6
9 K. ]$ J" B9 j$ L* }7
, h5 Q& [- ]) ]* W) f+ I8
9
9 l$ e6 N: c( `7 D10
11
  T" w& G8 g/ ]. h' S; |( [8 a12
13
# Q, C3 I: X6 h2 Q7 M) d* M* k14
" g# b& N8 ^7 d9 E/ M0 H15
16
17
) x% x2 v* k6 P/ W9 x, \% v6 U18
时间、空间复杂度

/ U+ Y8 H" x* d) x) A5 r. X& a
1 q* n7 ~( m" ]1 l9 e1 F/ y! b2 e" Q
4 D2 u% v2 @* h( [9 o( O, F
适用性：适用于顺序存储和链式存储的线性表。
- J' l- P! i0 |9 ?- J
2 L7 M1 T" r* K% v! S4 Q1 C

3.2 （不稳定）堆排序
2 t' W' j% c% {! t' c: L① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
! C1 D9 ]: g& z! s0 a堆是具有以下性质的完全二叉树：
, K/ `$ f5 A- W) ~8 G5 s每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
. `/ P- g  E* W# N% Z8 n# G8 d
) X- }( w8 `( l7 I0 \3 J. @3 a0 O$ G- o0 f
' ?+ o; B8 o) ]0 H. M
即：
若满⾜：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）—— ⼩根堆（⼩顶堆）

② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
* k8 D9 M+ T# |3 h思路：
- {2 x+ Y! j/ V1 n6 ~6 P把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
7 t& h2 p" L2 b$ R
$ S$ m  X' W# A0 U  x7 I( E% c" y5 Y在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
7 K% A/ a9 _0 M! ^8 k* ^+ A
检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换
+ O# E; t' S3 I$ z/ O9 @- v- {
过程例子：
# w2 f9 c! W7 q+ A( [9 l" S

* V  X% n& t' B
' V9 Z6 G$ C. W2 c建⽴⼤根堆（代码）：
  v' b* L6 m; X& N# T6 `) X) @
6 v6 [/ b. {. B; G2 h6 f3 C

// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
3 X: j8 C3 C& Z3 i0 t    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
0 O5 ]3 m& k8 E' f}
! k; p, @1 E' H
4 Q2 v: o( ~8 K// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
9 w; S8 J' ~; p& K    A[0] = A[k];
    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
/ E. \2 U( g: C. `) B        if(i<len && A<A[i+1])       
            i++;
        if(A[0] >= A)
) R4 h- O' {6 R5 S            break;
        else{
2 c! e0 M9 N1 _            A[k] = A;                        //将A调整至双亲结点上
# B% I0 R& K9 q2 }/ a5 t            k=i;                                        //修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0]
}
! H7 ^% v9 n( x6 O0 M0 V
1
2
" d% e+ K- @# x' ~% ]/ ?3
1 i1 l2 L9 d8 s; A8 X4
5
, C9 J8 |5 @! Y  m6
1 U/ {9 s  Y+ y: F4 _0 b2 n& E7
3 R  y7 m; Q, @; d( d8
9
10
11
12
13
14
9 h5 L( F+ m0 L. R  X( N15
16
% x+ Q8 f% H- A) y- m' ~& P17
9 M0 y3 `( p4 |) p, x18
( t2 S, i6 ^! Z, D  K% }5 @: K6 N19
20
% X1 ^: y; m& S% c$ h! w7 D! o21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
! e7 \" J9 \* d3 w选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
$ O0 A" ]; b- x, e4 n2 r
堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
. i; I) {- J+ `8 Y2 L
过程：
0 o3 r# }' S3 V8 `  V/ l1 y1 I3 o* c+ m
8 ?8 o7 l9 j- A% H0 V- [, l// 交换a和b的值
void swap(int &a, int &b){
* u) x  w* w/ k6 ?; v    int temp = a;
    a = b;
    b = temp;
) ^  R! Z$ l5 ]5 I2 P/ u$ M; d8 v}

0 Q7 s9 b0 U4 b; T// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
        //初始建立大根堆
% a1 Z( M6 P5 P7 g    BuildMaxHeap(A, len);                

    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
7 ~/ t- h+ j: P- a2 j- c9 w    {             
1 A' P7 V3 `: B8 `1 W! {4 K6 e        swap(A, A[1]);
! L  n0 S' I. b, C( X& N. Q        HeadAdjust(A,1,i-1);
    }
- b9 t  ^6 z# T8 y0 d}
% Y- t, U' J0 C
1
9 H% N/ y' i- K: \: K2
3
2 j$ H6 U- X. F" e4
5
6 w3 x; R( _7 Y8 L! M6
7
- o- w4 Y& S7 n1 r$ P8 |/ g8 z, |8
6 F( P8 T3 |4 F: d9
10
11
12
, ?0 Y' b- ^. {2 R13
14
15
, G0 A; E, G3 t7 K7 x( q' C% l4 [16
/ c. i$ ]& A. w* k& w17
18
2 x! J: e1 p0 ^3 n: t' z19
时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
' N0 V4 M7 v. k) F, `  x$ i' c
/ l' ^0 z5 M; [* Y空间复杂度 = O(1)
! Z, M3 V7 L" e6 L# A) r6 ^/ r
% |. f9 J# l$ F4 c结论：堆排序是不稳定的

( j' z0 y, L8 v" @
3 a3 n/ ?- N* m& G5 Q: m& B④ 补充：在堆中插⼊新元素
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌
8 s( o" s$ m0 i' t  F
* |2 H7 }, |/ Y
. J8 _9 u! e+ _1 t" H( s8 c( k2 C
⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌




6 c( U% w( i7 t
4. （稳定）归并排序
) a3 o  Z2 w! N* d归并：把两个或多个已经有序的序列合并成⼀个
) _0 B$ ?, L. d: n( v9 K  R# o
& h' z1 ?/ y8 y' \& T$ c① 明白什么是“2路”归并？——就是“⼆合⼀”
: k# W) \2 E2 A
多路归并：
! K0 T5 r0 j% S8 b  W0 Y# u0 H! y/ @
, x$ v) m5 _6 |! H
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
5 ^0 y* f2 p$ Z( ^
0 u+ ]4 ?6 Q2 S# rB[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

5 p" t. o1 }# l$ K6 }) L0 x6 d③递归进行分治思想【MergeSort(int A[], int low, int high)】

: ?0 p! |9 N6 z
$ W# o$ G8 r6 i% E& X④ 总实现代码
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
0 j/ k* t6 \- m5 a2 d: }
// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
1 N4 b* V4 e) Wvoid Merge(int A[], int low, int mid, int high){
    int i,j,k;
- c; m- K; k! V6 s+ K    for(k=low; k<=high; k++)
* @  N; R9 k' l        B[k]=A[k];
    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
' F2 p7 G7 x. Y5 S# M        if(B<=B[j])
( j6 ~; I8 I  W$ o' l            A[k]=B[i++];
, x4 A( q9 H8 o. p/ d- {) X2 l        else
            A[k]=B[j++];
    }
    while(i<=mid)
/ M: s& J6 }4 g4 u; C        A[k++]=B[i++];
    while(j<=high)
/ ?, `5 P. g8 X* G" v7 X, p        A[k++]=B[j++];
% u: l4 I4 F+ `}

' r- V( @6 ^% G# ^
6 B/ C4 k& y8 m1 B// 递归操作（使用了分治法思想）
0 p- ~6 C# p2 h, P. d/ A- U* Cvoid MergeSort(int A[], int low, int high){
    if(low<high){
        int mid = (low+high)/2;
' G! N) A8 H% y6 R        MergeSort(A, low, mid);
. B. b: |4 w$ e! a        MergeSort(A, mid+1, high);
8 c6 J1 e( T' U4 S/ Z" }$ \2 `6 L        Merge(A,low,mid,high);     //归并
, a3 v8 l4 d- W4 v$ o    }
4 n- c+ m7 y+ j# `}
& J8 x* @+ l. C( g
1
2
! b7 ~, i2 }' N8 e- K# S3
4
5
8 _8 @0 G% [, r6 X. q% o6
7
8 x7 O+ r5 {- C! r- @- f$ J8
; Q$ J+ T0 o# p% e& D' |# W9
1 R3 D# u$ Z& O10
2 y% ]/ X& ]0 Y11
12
+ I* l7 i0 A2 X% O13
14
- X9 e4 w3 O+ o15
) U4 y" ^4 U  k16
4 d5 _% d( b0 h( y3 ?5 n! h+ z17
18
19
20
21
3 n. z' Y  I& n& l: l22
: F0 i5 n* {2 f: c23
# `% Q" J: n& a* N24
25
26
27
28
. k% b; b- o3 H6 f. u7 H4 M29
" s$ `9 o7 C3 }1 w7 c$ P30
9 O4 w4 \1 s# U; x: _0 j时间、空间复杂度

7 i# y4 a- r5 K. M/ s

5 k' U6 N/ T1 T  f
0 `6 z" I/ |- O- I) ?5. 基数排序
直接看课本的过程图来理解P352
  I. W! E6 a  A7 J& w! [7 E
再看这个例子：
5 i0 h4 b) q: y- r1 V

算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
+ v1 q+ d: q/ R  v6 K) O$ b1 u分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
; L$ ~* ~. }6 G3 r/ t  }5 z基数排序擅长处理的问题：
①数据元素的关键字可以方便地拆分为d组，且d较小。
" r' r3 a1 u' g, w6 j) i' V②每组关键字的取值范围不大，即r较小。
$ ?8 H- r6 @  g& p③ 数据元素个数n较大。
+ |; j2 s! L- l" j算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
稳定性：稳定。
# s3 d8 [7 ]2 u" u" w/ d3 p7 B
$ P7 u3 N  n& e7 I. R( Z$ I
* F1 K- d/ q7 t% W7 P6 }内部排序算法总结

————————————————
  s4 F- E; O) T0 B& w( _版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# {& y7 Z2 l# s原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969
* m& c# V5 d, u3 z