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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
8 u# }# ]4 g: O! O1 V# y3 t文章目录
排序
* c+ ^/ C% s' c9 A" H4 ]1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
0 a  V! o$ B3 ~时间、空间复杂度
2. 交换排序
# k' |' c* U' V; {8 W6 K2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
- X9 T: W  n+ q+ M5 s( v3 H! Q时间、空间复杂度
3.选择排序
6 U* |' C* ~" e; R) U# }- L3.1 （不稳定）简单选择排序
时间、空间复杂度
$ E* d3 D0 q5 X+ X. {; w8 p3.2 （不稳定）堆排序
% D* R( u/ k+ k% U① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
2 v' n$ v+ Z- L- D& |② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
6 C6 D/ z3 N2 X* Q- N8 v③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
④ 补充：在堆中插⼊新元素
, L) p: [; `1 G! z9 [! W8 m⑤ 补充：在堆中删除元素
- V& p9 {5 t4 N0 ^' k2 Q+ ~8 i7 q4. （稳定）归并排序
5 l  t& L6 r3 `6 [, t3 I( U① 明白什么是“2路”归并？——就是“⼆合⼀”
' E( f' i, i. v8 f- p② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
4 Z# D: u8 O8 O4 G$ p4 {③递归进行分治思想【MergeSort(int A[], int low, int high)】
! n. k- i6 p" y/ A9 G; U+ N④ 总实现代码
时间、空间复杂度
5. 基数排序
; G6 t$ K; `# u+ u4 S" V5 P内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

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

算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
- I4 u4 @) T5 a8 o6 g6 w1 o7 a稳定的排序算法不一定比不稳定的排序算法要好。
2 D6 Y- `' ~6 n9 M
/ v5 A2 Z0 A  [8 z3 ?
; d. t8 A4 H/ V7 \排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

% A& l7 _4 J* G! p* T% p

$ p# u4 |# x  i% _1. 插⼊排序
9 [) Y$ ?- k- v' l1 d% C9 O; [( i（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
- d& [9 y' f/ B* _. I1 D. q8 d, ?
算法解释：（从小到大）

' @# q0 E- j$ X! S" ?+ w& v; O. y
算法三个步骤：

先保留要插入的数字
往后移
0 \" Z; Q% O# t) _. V; u2 X5 V插入元素
$ `' [/ W! y) z1 L# W5 H- ?
// 对A[]数组中共n个元素进行插入排序
6 T8 u9 }* W% M7 F! E4 J4 Gvoid InsertSort(int A[],int n){
: Z, c" U& G3 s0 @0 U9 @    int i,j,temp;
' F9 p4 P* ]" |; w3 a9 A    for(i=1; i<n; i++)
    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
) G: j  r6 ~" i& i" ?        if(A<A[i-1])
/ I5 x" [  ]- D2 Y8 y* L7 o        {           
- a; E2 q2 ^2 s            temp=A;  //保留要插入的数字

* j! e  M6 b" j: L6 ]            for(j=i-1; j>=0 && A[j]>temp; --j)
- I9 Q6 \0 Y4 C                A[j+1]=A[j];    //所有大于temp的元素都向后挪
( ?& V. {: o: @; _; j% l
% q  S. P' o2 O6 N2 v4 w            A[j+1]=temp;//插入元素
5 ^) g; u! d* S# X" c5 A2 C        }
    }
# s! S. P+ U- r) \$ t}
8 ~( b+ d0 B* M* p4 x  C/ c, S
  t4 r8 K( j+ Q! ], `1
2
3
4
5
- W6 r4 _  e  ~6
7
: W/ {9 T; n0 J4 S+ t8
8 R8 p+ G! m0 `1 X# v9
% A. v9 `1 Y* S/ T) q' e6 E& h+ E10
: E: U. b4 g0 G) k/ _2 l9 H: t11
* w) n7 g, L, C! u9 F12
13
14
15
# v. u2 D" m+ h" H1 C: A6 Q16
  g& b, F7 o8 [17
* K' f$ J2 O% f, q0 q4 s用算法再带入这个例子，进行加深理解
1 A8 e( e9 x/ G, V9 F! M9 o  I; b
7 L; E0 Z! o- q' G! ~' R* R; p9 x
带哨兵：
, l, F( C6 y9 w

3 g: H. V/ Q# M! K补充：对链表L进行插入排序

void InsertSort(LinkList &L){
    LNode *p=L->next, *pre;
- Y9 `) `# f" P. n3 Q' {    LNode *r=p->next;
    p->next=NULL;
    p=r;
# r; q( E9 m. ]# N' L: Z+ v    while(p!=NULL){
        r=p->next;
: e: E. g$ r; j$ Q; ~$ ~$ T' k        pre=L;
4 _. \$ c* B1 f& i5 o' T$ C        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
; b3 |; K2 ?2 y7 u2 A        p->next=pre->next;
6 v# ]) W+ p- d% i6 l8 H( g        pre->next=p;
        p=r;
4 U2 ?4 C  b/ f. s( F7 i    }
}
' @' Z1 ?' A; x& c2 |7 J4 A. c: T1
$ W( U6 ^; B# Z/ O' U2
3
4
5
8 i+ U( T1 n6 S/ S  F6
7
9 F6 L+ u  x% @( H0 B- R8 C' |8
9
10
11
+ r0 h1 y2 c7 i* t1 N& r) E: y12
13
) d2 L# p4 g, P14
15
% E+ G! q4 a: m时间、空间复杂度
; q# |" V% e; r0 X
$ x' o+ I) t' x8 E- j, K. v' T
# W2 R+ ]  b& z最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
/ a9 r# H# r1 G9 B: c1 k$ h' l8 Q最好时间复杂度—— O(n)

- J7 S* T- ~  B; F6 X% D; q. O& T最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
/ \3 J4 u; l: A7 O& B/ H3 N9 s5 a. k第1趟：对⽐关键字2次，移动元素3次
  m* V) V# X$ Z8 C2 ~第2趟：对⽐关键字3次，移动元素4次
…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)
: O% f) T; X# u( m. U

. o$ m8 k( ~4 O# u0 C
6 p4 q* L) Y* u4 V. q

（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：


' {, x- l$ S, G
& s& r* Z% J1 o/ h& G" f//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
% R) p! ^7 i. H/ @7 s3 C) z# ^2 d{
    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
    {
        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
3 c* U+ E9 ^! {        while(low<=high){            
( l8 O4 X( S7 {& N6 G% L6 {  A            mid=(low+high)/2;
            if(A[mid]>A[0])
7 j0 t9 f) q5 F0 L5 w5 t* w                high=mid-1;
            else
5 p$ p: p# u& _0 C7 G! |                low=mid+1;
        }
         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];
8 D- B. `6 ]( L. \4 P. _7 P' b
5 r# J) b# V6 O5 z& R- i        A[high+1]=A[0];//插入
    }
}
3 L) I  p6 W7 y) t; r
7 {' a% M  \$ p" w1
8 Y4 _" j6 w7 Z: a9 Z0 L) J2
# d6 f$ W5 e% @) ^* l% V1 R. s  f3
4
8 n% ?* [6 ?, D5
' }- ~( D$ }% h+ x1 n6
7
- H) ?1 t& g  K: N* X8
1 V7 W. J7 B) A3 [! F5 x9
10
* r% L  |; ^. `( j- H- x: `6 B11
. R3 I2 \% j3 O2 p' m0 b12
13
14
! }" w8 s3 n0 {# N4 R% ?/ A/ Z15
! O% g1 |( c- c7 ?& a; _( e16
17
; H3 D3 D4 `6 ^( `1 o& p/ p18
19
20
21
22
& Z* ^: l& [1 a. |7 H7 l( f23
时间、空间复杂度
5 U5 r" U  @6 |0 k4 u# t3 A/ Q6 e空间复杂度：O(1)
5 d% Q1 g) ~" e3 r+ `, i7 G4 N
【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)

. C" f$ U8 W2 t
9 ?* E" j4 r; |（不稳定）1.3 希尔排序【多次直接插入排序】
& d& n% t$ w. h2 |7 e; P是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

算法思想
; m8 G  l2 U7 l& M# g; R9 n/ n
2 @' o( O2 c. ?; U9 |/ j/ y希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
) V) L. C8 R2 f) t  \图解：
5 ], V" N) m- M1 }& ^5 Y
& R3 b# ]8 ~0 {: \

代码实现：
4 x0 i- H) h0 m3 @' T& ?0 F3 W
//从小到大
" b7 l: q. q/ a' F2 ^void shellSort(int* arr, int n)
{
        int gap, i, j, temp;
6 N) c0 J+ E# e( k" s  C9 q        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
/ {: u7 T/ I- k& r0 D: b            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
                if (arr < arr[i - gap])
                {
                    temp = arr;
4 [% W, X8 r% ^& t! I. l
                    //后移
  |- |9 F5 w0 U, `9 K                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];
9 H3 m# p+ \8 p( u2 v: u. W* n4 e
+ z# ?4 o3 E7 v' J1 n8 N                    arr[j + gap] = temp;//插入进去
5 ?8 O0 Y2 K7 w  P% Q                }
' O/ g) J/ o, ?1 z6 Y/ L            }
            //************************************************************************************
        }
}

! `) s, H: ~- w) c; Z1
2
* Y& E7 W7 Y4 Z+ m, G4 e$ _$ p3
4
' f. ?4 A, J% [2 C% x5
" }1 [. @: x  L& m% E. X' L6
  }+ D! K6 U) W7
8
7 x/ f$ E+ X7 s% A! E; P5 F9
4 x0 E+ y8 a5 g" M10
11
12
13
14
, T# {. C" T, B15
16
4 T: ]6 d$ r5 ?. b; @6 K1 ]17
18
' `  @! G/ K$ S; s19
4 C6 n8 t, I) |: y4 e, ~20
21
: f" s9 e# P% j8 k( j; U& r( n  D22
- q9 Y/ \, J+ q9 w$ q23
) @* ?' g8 p+ q24
时间、空间复杂度
- V7 m8 {. P7 O空间复杂度：O(1)

6 V1 A' A( F: e) h# H- E; M时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)

8 {2 u5 q( @2 e. z& R/ n稳定性：不稳定！
/ B! |& @7 m3 T% |5 P# ~2 F, _

9 u! }/ e. W4 s3 r7 X1 {2 ^
适⽤性：仅适⽤于顺序表，不适⽤于链表
6 P1 u: m, J: ]4 c3 S


2. 交换排序
2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
3 N+ ~! V" z4 j, P从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
' G, z9 a8 ^) |# v% q8 n4 y8 s
每一轮比较会让一个最大数字沉底或者一个最小数字上浮

( Q/ x/ ^% K  c  C6 Z! ^这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
6 }" U, S& g% q' w1 n, k9 ?4 A
实现代码：
3 A9 I, A5 K8 G* M/ G. M* ^  P
# C0 r' A- J3 S' a6 M% Z//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
; S2 W4 o: x6 z2 u{
8 k& `' ?: L, ?        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)//相对于上面的一个优化
                {
                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
                        {
                                //交换两个元素位置
6 U1 \/ v& i+ {& n: _3 \2 T                                temp = arr[j];
, v7 N" c: [9 o$ H                                arr[j] = arr[j + 1];
7 M' x0 c5 _% X, Q                                arr[j + 1] = temp;
( ~' A$ O7 f7 I+ b, Z                        }
                }
        }
}
3 k# N2 V3 V1 a8 e! T& B
1
+ H) y: e7 F/ B  v: z( b6 R7 _( S2
" ~) @" Y$ x6 n4 q& X; f( ]3
4
/ i/ a1 P  [7 X5
6
6 y4 R* C; i, v& x7
: ]6 h2 {; v& G, O! {8
9
10
2 @, w4 e, Z& a, @% W* Y11
( d+ p" Q* g  b1 s! @! b1 |12
13
14
15
16
# q2 S9 A+ S; e5 Z1 U- ~17
: Z6 E  e0 l7 M# I. `& S18
19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

# i  M/ r8 V3 K# w2 h//从小到大：
! t& f: l) l: ^) A6 K4 `9 [void bubble_sort(int arr[], int len)
+ X: S$ v1 w. m0 C$ s$ o{
0 q( l, g0 C8 v& s& N        int temp;
        bool flag;
# ~5 H9 c0 p4 u3 w6 D( s% {0 M/ u        for (int i = 0; i < len - 1; ++i)
" u) R/ g# t' H. Q9 s+ y3 o        {
  L2 q2 ]' q3 p) S# d            //表示本趟冒泡是否发生交换的标志
                flag=false;
               
                for (int j = 0; j < len - 1 - i; ++j)
4 i. D- R3 ?3 ?. u: j* f                {
0 r5 J3 a6 l7 e) q/ ~, V                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
                                temp = arr[j];
5 y4 [9 {* V  |- T  w                                arr[j] = arr[j + 1];
) r  i& [) L$ _. @! ?                                arr[j + 1] = temp;
+ k8 {9 h; z2 p3 h1 L  n( ]  ?                                //有发生交换
0 g7 G& x. S, [                                flag=true;
$ |0 a; z/ \4 w, ~# G2 z                        }
4 K* g* c+ f# u6 F- {                }//for
               
                //本趟遍历后没有发生交换，说明表已经有序
. y5 H% ~, ^0 ?( X. I0 p                if(flag==false)return;【1】
        }//for
}

4 @5 Y& L# t0 |0 B7 _9 G1
0 h' I# C2 [# F2
3
4
5
7 ^# l5 K' m3 T- B+ h6
7
3 i% g9 t& ]) G8
# G- `2 ]% y5 [1 `9 q+ R9
0 _1 q/ v7 f7 P4 m  M# K10
; Y' U+ }7 Z1 {5 }5 D11
! [$ B* |! E& G, c- ?9 c% L/ L12
13
* `8 N1 m0 Z" g; R$ ^  e14
& R0 r* a* K; s5 Z/ N" e9 {" {15
" C" b- a% U3 a  v  k7 P4 F% b; n16
$ I; H4 f/ K4 h17
18
19
% e4 B0 e" n; @+ T# Z! b8 Q& Q20
21
1 L- r8 P% w- x+ A/ K22
23
" i' M6 V" ~+ T, q; v24
! _& Z2 M# k" S* k% R- f. i25
$ ~( ]: c4 M& v7 K' D$ G26
3 b, N9 [% @2 C+ I- J2 W4 O时间、空间复杂度
( J* F' }, S) n6 A' r" L+ k
4 c* P7 M' B5 t8 y7 }7 k' U适用性：冒泡排序可以用于顺序表、链表
3 n- b# h, F8 @( z' y( B1 }7 Z
8 U: v" L$ ~8 K  J4 T


  ~. R! R) h/ l) ~7 b' s) J2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
- c& r6 h4 k/ [在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
3 Y( X: D  r' c* l7 Q: [通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
# O3 e4 u) x" s使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
6 |0 u4 l* W/ Y( x' c再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

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

4 c. h8 D+ [. u2 s' i: U划分的过程：

初始状态：取首元素为pivot，定义low，high指针
* T, q# M! l* |! C* Y% f1 _
首元素为49
high指针指向的数据小于49，就放在low指向的位置
- I, N! f$ s; S9 n8 w) `low指针指向的数据大于49，就放在high指向的位置

9 j' t; U( R* X# a4 k
' T3 m8 ~4 F; p2 m; Z
, X* @. F5 {6 x- B4 y4 r
  R/ p5 w! L8 y/ W) J! f: s* l
+ U; E3 |, A# d# p7 K// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
# r2 t. Y: O) w        //取首元素为pivot
5 k- @4 L0 j! g0 {    int pivot = A[low];

    while(low<high)
    {
            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
5 A/ m; h5 x2 I' S/ ^2 C! ^            --high;
        A[low] = A[high];

        //随后low向右移动
/ b1 s0 s/ m$ Y; z; B+ a2 U9 w. Z" ^        while(low<high && A[low]<=pivot)
: e% `& [# P" }4 U            ++low;
        A[high] = A[low];
% C$ v' Q) ]' G, t/ |    }

    //low=high的位置，即pivot放在的位置
6 n; K) O+ y7 R' q; a2 Y    A[low] = pivot;

    return low;
}

+ w1 F6 x5 U( L7 Z. D// 对A[]数组的low到high进行快速排序
void QuickSort(int A[], int low, int high){
    if(low<high){
$ T3 r' y5 p  O( k        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
% ~3 \- J3 F- d/ B3 e        QuickSort(A, pivotpos + 1, high);
) C% z* s2 [. n. C: q    }
' b& |2 d* O( L9 e' n/ ~+ ?7 h}
& m$ @9 }  N  g: C7 o2 z1 D4 b
1
& x/ K% I6 M  v, M: O' Q! @; F* Y2
# [2 e0 h& G' K3
4
9 Q) \4 T$ [; e% h5 {2 O# u8 V5
6
; U6 E0 @: m( S6 a% T7
8
9
10
11
+ h# ~/ o6 V" G, M$ ~12
' P9 l" O6 A) u' l7 U+ A9 J5 g13
14
15
16
17
18
19
20
0 Q2 {; @2 s2 L% ~2 i& {( ]21
9 m, P8 B1 ]. E# t  g; d22
23
24
1 Z! M) B0 V- B# U* _25
26
( O" r- q: }$ c0 X) B& [( F. q27
$ x! ~2 I# `0 B  {; k$ R28
29
: ], N0 Z& g  e; E30
. A' m( x5 E5 ]. A5 C- V7 T31
  T% \+ I" e. Q  Y32
时间、空间复杂度
$ i( @( l% a% K7 P! f

* I2 L) y5 v; N( A. c2 G8 D把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

& [% k' N% q1 N* [n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

时间复杂度=O(n*递归层数)
1 D  }2 x& Q+ P  `( ~6 r最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
+ Q% i( s# D6 o8 A0 `% o平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法
6 k8 \. n" D6 O2 m+ \$ {" P
$ [3 x' [( [: @9 I3 t. o+ u5 j: [空间复杂度=O(递归层数)
( Z& t$ R  e6 s最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)

$ i$ Q0 m/ B$ v9 Z. N6 q" Y& m最坏的情况

3 Q% R4 U: T6 w. m$ a2 F+ L

⽐较好的情况
: ?8 u; k+ r& R9 v8 B* W% @
0 }" d9 V: O! E* _4 |; Z
! b' ?$ T* z+ S
, z2 X6 c3 i5 U1 \" A不稳定的原因：



# ]$ {. P7 R6 c: J  H3 X

& l+ c$ h$ r- x* h3.选择排序
( R/ C3 \$ @/ o+ s3 f选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
0 J1 h" ^! w# z! N, x9 [6 J
8 c" z& L9 B! C: q* v; B' @3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
( A( R! h0 X# }+ I/ _
" `& c7 q) `+ v! |
  c% n' X. r. ?3 h1 X
) j8 t# Z* b0 x: x% d; U8 i% W$ o// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
; W# L+ c: V' J: K    a = b;
$ s6 P1 G4 k9 s% j    b = temp;
}
' z. [5 c2 t1 J2 D
5 y; V/ [2 ^* o; ~: d7 T/ f9 F// 对A[]数组共n个元素进行选择排序
/ c: `5 Z) O" L7 T& tvoid SelectSort(int A[], int n)
{
        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
    {                 
        int min = i;
3 M5 h9 E4 E5 m        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
                min = j;
        }
5 j& a' u8 U4 K1 @) F0 B- C1 W        if(min!=i)                     
- n+ F) c1 I  ^" Z, V7 g* B' M            swap(A, A[min]);
    }
}
) u4 N+ Y0 |1 }9 h6 M, z% v- L
' S% ^- E- P% Z& |" H- k1
3 ^6 q8 i5 M) l0 ^, P2
3
1 i- p, d( H" w, Y3 P/ o8 S* B4
- O/ h; L4 G7 {2 X# u2 v! b5 t5
6
7
+ ~" v  y- B3 \1 I+ F5 z4 o8
9 ^& w% c) p5 w  ]0 X* p0 R9
. Z4 e- u6 U( `10
4 M. Y, E8 A+ ^, v- @8 v" }5 D11
12
# S: o2 E$ G7 b9 W; S1 P. ^4 R13
14
7 N: f; D% y1 s! e. F8 A! Y' _15
4 c6 s" c1 B" m* ~( X  P6 V2 ]# k16
: Z* T9 y' m; s) p; @$ B! Y& j5 \% C17
; L: y/ u5 ^$ Q18
1 e3 @' l% A! T) Q19
20
. o, t1 E( _! t21
% q1 i1 Q/ V4 ]7 ^1 @; {0 D- b: S( E* v22
6 V" j1 Z) P8 Y6 i补充：对链表进行简单选择排序
* A( G* I- G. O3 d! t
void selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
    while(h!=NULL){
        p=s=h; q=r=NULL;
* I  ^: M  E4 Y        while(p!=NULL){
; G% M  U4 a4 X  L4 K- i0 \            if(p->data>s->data){
                s=p; r=q;
            }
            q=p; p=p->next;
        }
' [3 n8 [/ Y5 R* R        if(s==h)
# V$ u4 L' ~5 t* M' c# ^            h=h->next;
' F$ f! M1 u# t7 T% T% Y        else
            r->next=s->next;
. d5 `  q" O: T3 G, ^8 Q8 v        s->next=L; L=s;
. _! g0 q+ ?8 y& b1 z& R    }
}
" c  @# j; U& M# }
3 ]4 c( n. L$ R! j1 g. B1
5 W  r# [- O: p8 D2
2 d/ x( A; L! V: T1 z4 Y3
4
5
- i0 n. T) D8 [! T5 m# G) Z6
- Z( _/ x" u- |8 V/ X! L9 P  A7
4 B* M& B2 v: I/ b* k8
9
/ Z4 |" {9 P3 l& j% J10
1 K8 ~/ s2 l; T& {/ c11
12
13
14
8 ^6 z; M& O  h) q7 T+ O* S15
- |+ p2 B3 M/ |3 c2 M16
+ H6 z; Y8 K( j: H/ O: b* g7 W17
18
0 _9 E. s& B$ Y( U4 g) i时间、空间复杂度



, `/ S7 m- c6 ]- P. i
适用性：适用于顺序存储和链式存储的线性表。
1 ?6 e( G+ i& r* ?/ A& q3 s

7 ?, G% x) ]3 R- z- e# w! }
3.2 （不稳定）堆排序
& ^3 B: f, h! Z' N① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
  q9 f$ D4 b1 ]堆是具有以下性质的完全二叉树：
0 ?* [. A" d4 X5 e每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

7 b$ M  d3 D+ Y" @! g5 j
) B  o0 K2 F1 ~$ T* T. x
2 ]& A6 A: M. o0 ^8 m, S即：
若满⾜：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）—— ⼩根堆（⼩顶堆）
9 W& }( ~# f) h; a, y
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
思路：
* @* G# c5 s' ~# K$ P0 O把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
# J4 R4 O7 B  x. O7 i
2 `" O2 i, l" w& c# X4 ~/ {* a检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换
8 p% r) [; t1 ?* e4 K- e) ]
7 X/ R' b/ ]0 r+ i5 S; D5 k过程例子：


( m" Q( `- V9 _; A! E; M: }
建⽴⼤根堆（代码）：

0 U4 A0 l" n) n8 E: U$ H9 T& G% p
, l0 K% X# b2 m0 H/ T
// 对初始序列建立大根堆
, m9 F! J) _; W7 H3 m7 Ovoid BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
( X! O9 D+ V6 p6 u}
. n, C' h4 t2 z& g7 R
// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
2 ?5 F; P  O1 h' U; w+ Z9 b9 t    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
            i++;
* M4 J! I" S) J& B: }( s2 f; J        if(A[0] >= A)
            break;
        else{
/ V, ?% }% y* A) |            A[k] = A;                        //将A调整至双亲结点上
  e; p; P& p0 T; e$ a" N6 F            k=i;                                        //修改k值，以便继续向下筛选
        }
) @- v$ s1 p' v$ A! h    }
    A[k] = A[0]
}

7 J- O( s5 U! o' J1
2
3
4
% E# B! p& |1 V0 z) F2 Q, ^1 v5
6
, B' x. u6 j7 F5 n% b* i7
" l7 R2 U# O: c/ D/ _% z- Q" M8
9
4 @! {; H- D& Q6 s" D8 E, h, H8 w10
11
" N4 [9 G2 E6 l3 A( U, X% z% ^12
13
6 K: R3 x5 W/ k& k0 V( |14
15
" s$ X5 |: X9 \; j16
17
; B. F) P3 ?4 L18
19
20
  z5 u' j7 K- n# ~. A0 h4 H- ^21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

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

过程：

: N8 M* ~( O4 O9 X/ B+ n// 交换a和b的值
7 u9 \& T& I* c8 Q3 M6 Q; Avoid swap(int &a, int &b){
    int temp = a;
    a = b;
! I: p2 G! E: |    b = temp;
0 n3 ~' l; \3 N7 V, G}
; H3 d) h9 a8 X& y( x" C2 O
// 对长为len的数组A[]进行堆排序
0 j" _( ~. `6 \void HeapSort(int A[], int len){
" R7 [0 B, V' b7 m8 U        //初始建立大根堆
    BuildMaxHeap(A, len);                

' a: w* z% B  n! K% @0 h    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
    {             
        swap(A, A[1]);
        HeadAdjust(A,1,i-1);
    }
# p% a+ H6 z% P}
% R, U4 I) {2 V" }+ k, [
1
1 i' C  h: L" V, L2
3
- Z. K- a, q, |- v4
5
" M) `2 V" ~, X4 ]! R, E6
/ X" m7 Z' f2 N  H2 U! X7
9 Q. f9 V  f1 }2 P. G3 e$ i8
) P/ t, S$ [. T% D- }9
10
* [% A% j3 u# W2 i3 h2 E, ^11
12
: h, [+ t9 p: `% Q' C) ]! q13
14
15
5 \. W9 P% q& _! F8 m16
  q2 d; e8 }( G" K" ^: C- j17
4 q2 j" [, C0 @5 J+ O8 e18
' L% x9 g, x& h3 B19
) J: _7 {" r8 y. W) q& v* W4 H时间、空间复杂度
6 ]. i: a  A" g5 @+ |5 j9 S建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

* P8 g' r4 W( ~& @# |( I' D+ G, X5 x7 M空间复杂度 = O(1)
. j/ ~  W( J! I8 W2 l
结论：堆排序是不稳定的
7 E" m0 }/ I! U6 ]: X
5 o6 v! \9 U; j; o/ ]& D. ]
④ 补充：在堆中插⼊新元素
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
' o8 I9 l" y- G& }* D% w  p新元素就这样⼀路“上升”，直到⽆法继续上升为⽌



6 A9 t/ B' M1 s( D⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌


2 s3 x0 l% ~, L3 R9 @
/ F9 d7 R' u) \8 O; M! |5 @. M3 b

5 p& T" [+ _! i  G/ h7 Z4. （稳定）归并排序
+ ~+ D% d! d. x" m; l归并：把两个或多个已经有序的序列合并成⼀个

① 明白什么是“2路”归并？——就是“⼆合⼀”
5 J; K  {, H. }
多路归并：
) R9 e' d. D" w' H6 K$ u

② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

+ G: C5 i) l7 K7 u2 p7 GB[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
: ~( _' ]3 `# A! ~+ ]/ k
③递归进行分治思想【MergeSort(int A[], int low, int high)】


6 }$ c  _, M9 T) u. {! ~8 f④ 总实现代码
// 辅助数组B
' l2 A$ ~  w1 y1 Nint *B=(int *)malloc(n*sizeof(int));

// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
  h; b/ p1 p: T# }- ]    int i,j,k;
    for(k=low; k<=high; k++)
        B[k]=A[k];
    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B<=B[j])
            A[k]=B[i++];
        else
, H( d8 p5 f/ a9 C, n( h! o            A[k]=B[j++];
    }
    while(i<=mid)
% A1 \/ ^  u! g$ v8 I        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
}
& _, R/ _! D" @
% y+ l) l- A' E5 V: ~2 Q
$ n" i0 A7 H8 H) _; p- ~/ j// 递归操作（使用了分治法思想）
- s! R5 M5 |- S" k0 Ovoid MergeSort(int A[], int low, int high){
    if(low<high){
        int mid = (low+high)/2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
; F' `. ], x, R% W" U3 E8 E2 ^" M        Merge(A,low,mid,high);     //归并
( H! o* e4 v, Z+ a' |" |    }
}
, y! s3 o# p4 Z" Y4 G6 q4 [8 L' P3 h
1
2
# w# t" K9 a4 p/ E; L3
4
5
2 w4 ?& r9 O1 {; x  i. a4 l6
7
( S" \) |+ K7 `4 ~3 u; E5 u3 Y8
( n$ P2 n" Z8 Z5 M% ?* m, P9
" F8 K3 @  [! y% v10
11
( m% \) G4 [3 Z  }$ J2 ~12
13
14
15
16
17
" @: o; z- {6 q5 r$ M+ x, L2 X9 q18
5 h- @1 j" O' U( R, G0 M" f19
20
- {& G& D6 J6 @8 |5 H21
7 `) Z7 w2 L5 \! k  C2 e! I6 F* A22
6 B) h8 j% x# [% f( v4 q  Q23
" A0 S0 o2 U4 O* K  c" ~0 k24
& D1 o5 N2 v, T' b. o25
6 H2 V' B" R  I26
; }$ ^' Q: W# t/ x# U: t% ]! l27
( ^! j5 \$ D0 m) a28
" d- X$ [5 R6 ?) J8 p& b& ^29
" X8 Y2 m) j* R& B9 z30
时间、空间复杂度


0 T: Q& t- i# c/ Z2 P3 {
; m4 Y9 L6 O6 I% d
5. 基数排序
- H# o* p; O2 C5 O直接看课本的过程图来理解P352

再看这个例子：

& ^% C9 @& N; `$ M. d
算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
) x# B; q& T* s3 Z, F: l收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
+ B4 j8 O" M2 R. P1 `+ \5 m1 L基数排序擅长处理的问题：
, H8 ?6 L( }# \; k. d5 d; I①数据元素的关键字可以方便地拆分为d组，且d较小。
& h) z/ L5 W& H9 O" t! L②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。
算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
. T' C/ \+ Q, u; o# `稳定性：稳定。


内部排序算法总结
  P* d% u+ \7 k9 F+ Q
$ T2 c) s( G$ G! Z————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
0 D! S8 Z9 |  j) t$ I$ q  L原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969