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

杨利霞

* G9 [" C# |! q0 |3 C4 l2 S【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
* o$ X0 q$ P" E2 a0 c) v3 t4 x: s1 O" V排序
8 G5 M" X( i( P+ b1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
2 @+ n0 h/ N! A8 K) U0 |/ e时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
0 o/ _% b- m; h0 o6 j; n（不稳定）1.3 希尔排序【多次直接插入排序】
时间、空间复杂度
6 e: T) ^) K* _0 n) i2. 交换排序
9 I5 s. p) N7 K7 Z6 D* Y4 _2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
7 V3 I% y3 v) P3 Y7 X( h( _$ a3.2 （不稳定）堆排序
" p( F/ x' L, M! U, ?; m' |① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
2 c/ y  T# w$ O0 N/ ]③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
④ 补充：在堆中插⼊新元素
3 x$ ~5 F1 t2 X+ n& a; K# O! s⑤ 补充：在堆中删除元素
! M$ C8 B5 O4 u) [4. （稳定）归并排序
, ~9 f( x& j( z! I/ g; S① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
* i3 Y$ e1 H9 L& _9 o8 ~- d③递归进行分治思想【MergeSort(int A[], int low, int high)】
6 O7 `6 W3 w" e' L④ 总实现代码
时间、空间复杂度
- n% i! C3 W& @8 v* H7 I% q5. 基数排序
8 I# \9 h2 y7 X$ w. W4 g内部排序算法总结
排序
  ^! D" Y& t3 U# g排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
$ ]2 h) B0 t/ M) [  y) J
排序算法的评价指标：时间复杂度、空间复杂度、稳定性。

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

- Q* x" y" k1 S, q" v
排序算法的分类：
( K8 q% t8 @- @8 P. Q9 U内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
2 }' \4 ?& e8 X7 W! B; F/ n' G0 O外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
- N$ K+ x( ~; o6 V* o( A8 V5 `
* ~  W, }; Y% ]! |' J* u2 A( v6 h
7 R! K1 r- l$ G. Y# Y- |5 F5 h
* T. J( q4 D( @) R1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
, N. C3 `7 a5 F2 O# Z基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
+ J* J% v! U2 e- Q& W+ c3 K8 N3 r
  l( x' J4 K3 K  A! F算法解释：（从小到大）
3 y9 J8 p1 B+ O7 `

3 l% E. O$ k! b: H  H' H算法三个步骤：
& u2 @1 Q$ S4 {: W& g4 t2 R  w
* o# J9 I, J+ ]: z/ N! s, Z$ A先保留要插入的数字
往后移
8 b1 g5 A9 V0 ]; A& X& X; \- J插入元素

4 |$ H/ N# J7 x+ b& c// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
3 y, S/ k, y2 K' d    int i,j,temp;
    for(i=1; i<n; i++)
- o0 J/ ]( |4 N- V1 H    {
& V: w$ }5 K( T2 n6 u+ R, d) Q            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
        if(A<A[i-1])
; ?0 D2 y0 `" G% r& w        {           
            temp=A;  //保留要插入的数字
* o& E. d4 Q; l" M' q' S. e" x
            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪

  s% y' L& `% M' P: w            A[j+1]=temp;//插入元素
        }
    }
}

! s% j/ e4 a& F0 _0 n1
4 O& p) s" B/ @/ `2
3
4
  Y# L' I& L1 b, G5
# Q! t6 j. {% [2 v# N7 V4 ?7 |6
0 ?, n! u( U8 h7
8
9
10
% ?0 {6 l% |0 P) u+ [: G11
12
13
  l: N1 \3 x3 W! m! Y! C! z1 D8 Z14
+ t4 C! ~1 c/ R, R  ~( F15
- A- A+ d$ K1 Y2 r* @8 a% G16
17
用算法再带入这个例子，进行加深理解


带哨兵：

  m( K# h7 k! |1 O) k( n: Z
# d6 l/ @- |- x+ N7 O/ X补充：对链表L进行插入排序

void InsertSort(LinkList &L){
) l$ i1 D! J( E    LNode *p=L->next, *pre;
+ G% C" \+ a# ?& l    LNode *r=p->next;
    p->next=NULL;
8 U9 w* @; I+ C. ]. O) X8 {5 D- A    p=r;
    while(p!=NULL){
        r=p->next;
& @" {! w; O% r& r7 e        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
        p->next=pre->next;
# s- r- r$ j, {+ r; h: [6 M  m4 N3 W5 I        pre->next=p;
  A' e, n( _! l3 X- C% X* A        p=r;
. y% T) {! c/ T+ T7 K    }
$ a) \- v  a4 P1 _, A1 L}
1
" N# w# B% ^1 I) A: c6 k2
3
  u; J  ~9 S) D% g( {3 h! b+ a4
1 v) h9 h+ a' f2 s+ V; f6 a: A6 U5
6
7
. h- K( }2 h& A" |8
9
10
11
12
13
14
15
! k/ P9 k9 g, B时间、空间复杂度


# D& {% P# Q9 c3 h+ Y9 s" h; j; }最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
5 g, B0 W/ z* g, P; Z+ ^" R最好时间复杂度—— O(n)
. q/ {7 i4 a9 C. e; a
# n& e3 H; n7 {最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
& i# E9 }' U" b* g第2趟：对⽐关键字3次，移动元素4次
0 h5 e+ c) V* I5 K9 P& G; W…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)


( n/ @3 d7 d3 N9 S4 Z
$ h- w% c# }8 \! p. N( ]7 l
5 _. z: f0 L. j. X, A
$ r8 p6 o: o4 U9 y6 q; T6 U$ ^- H（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：
* d6 m+ t6 |7 u7 X
- f. J3 w% c1 t# `. k$ ]! C; I( {

//对A[]数组中共n个元素进行折半插入排序
2 k+ i+ u) [! g6 R) Mvoid InsertSort(int A[], int n)
{
    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
' l( x+ J' C# S: F: R: P! R    {
5 N7 F5 E0 `# l- O        A[0]=A; //存到A[0]
; C9 T; ]: a% V' H        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
        while(low<=high){            
) y5 X- K9 F5 f( l' Y8 _1 d            mid=(low+high)/2;
            if(A[mid]>A[0])
                high=mid-1;
            else
                low=mid+1;
        }
2 ^9 {( ?; `% g! b! H# v) O         //--------------------------------------------
$ P  d( G4 \; v# C& T% u        for(j=i-1; j>high+1; --j)//右移
0 y: N- }0 G8 J, j2 H  i4 b            A[j+1]=A[j];
- H1 \* c7 @( {8 j. o
        A[high+1]=A[0];//插入
9 V. \% G6 p# V6 [& @6 y- L    }
! p  @* S3 @1 R# S}
" J- U: E' k; t3 H% |/ b1 w  ^
1
2
3
4
5
6
/ G3 M1 G% R' C7 z  e# h7
0 s2 p" a5 J# j2 b8 b* Z8
: t9 h* S: d$ I3 f" i9
10
1 K* ?% K+ S0 _. m11
3 `- e5 N5 H" i3 O% F: `12
& F- }. H$ L% s: l13
14
15
16
  f, U* l  n! K) C17
18
19
20
0 [# W4 e: Z0 m0 X0 k21
22
( _  p  y! h  \) V# t! i: z23
时间、空间复杂度
8 _  ^0 q$ Z* e  Z' K+ n9 q9 q空间复杂度：O(1)

【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
9 j( o/ d3 h: G1 m/ }% R0 h
) ^! i; j. ?$ e
（不稳定）1.3 希尔排序【多次直接插入排序】
% N- m, T/ G: p% Q- \是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

0 @- L! t# N8 C. o2 V6 n算法思想

' d+ _9 p$ X1 ^5 C) `; s希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：



代码实现：
2 ]% t% N$ s- _3 _8 [! P
//从小到大
1 K! ~8 Y3 _0 X: G, a$ k3 t, [void shellSort(int* arr, int n)
% H" }/ n3 P- O) o; L# H{
        int gap, i, j, temp;
+ b8 t% r; T4 R5 z        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
3 p0 i9 f) R& g9 P/ q4 X$ l        {
            //**********************************直接插入排序（只是步长改变）**************************************************
; F6 }; d. F  a) Q3 G0 y            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
                if (arr < arr[i - gap])
  u' j8 A1 R% c+ {# `+ N$ Z! \                {
; U# K! O( L+ E                    temp = arr;
7 @( }8 Z  n% u& i6 J8 ~
                    //后移
+ A3 g8 ]9 p7 [6 v& u6 ?                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
3 W' C" F" x7 ?& }5 ^                        arr[j + gap] = arr[j];

4 y4 j+ I. `6 G  J3 d  {                    arr[j + gap] = temp;//插入进去
( I& g5 w6 l) [0 b7 j5 i5 L( s                }
' K2 Z. V% r6 {            }
            //************************************************************************************
        }
  X4 K0 k. e/ Z1 k% O}

1
2
1 A$ u6 @$ L: O3
4
5
6
" k4 }! {& S0 j5 ^( I* Q6 T: v7
- e4 R7 H- L/ _* S8
( e9 M* c: i% k+ N3 L4 I( L9
2 |! @; e, Q2 W) ~: o/ U10
6 c+ e! a$ B2 Y- x8 x" [% ^8 W11
# S$ a1 c6 P; I' W12
' ^  I5 s* g3 C* H13
14
15
16
17
- m4 K& H9 i% {18
. P2 ?! `3 Z4 Z19
) a% J  [. W, z; Q) q4 H20
3 Y, S$ i+ i9 O, L' y21
22
23
24
& Q3 j0 W  S4 _1 z; a, I* i时间、空间复杂度
空间复杂度：O(1)
) G. V7 @! q( h$ [; ?* I) @
7 S: d" d" h, @% t+ [, v时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
: J% K# q! ]6 p6 a  Z& [
稳定性：不稳定！
2 v0 {1 e' r- R& ^  J$ {# x0 D
: y+ p1 S* e9 f% ?1 R$ e! W) V

5 ^9 b3 k4 T& |) D3 S适⽤性：仅适⽤于顺序表，不适⽤于链表



2. 交换排序
2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
! n1 |9 l2 w3 g7 O从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
' |7 \* ^- Q! U) T% x8 A7 y& g
  _( U. K6 y& {& q3 ^每一轮比较会让一个最大数字沉底或者一个最小数字上浮

. }  x# m( e- u4 }0 u. z# k这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
% B3 l& W6 e$ R1 N- g# k
( {/ ]5 {3 Z, d& c, o实现代码：

3 x5 X0 p5 R; g; Z- h0 V//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
9 S7 x1 a% C1 {& a0 z' V( T{
! }7 M- g0 x* Y) u, P# L2 s1 a        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
        {
$ _+ ]+ a& F# O* Y3 G; G& P# w                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
5 _6 ?/ v. u  Z5 ]2 g                {
0 k& _5 v( A( M0 P                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
$ t/ _* D! d5 @' ^$ f3 I+ a" }                        {
                                //交换两个元素位置
                                temp = arr[j];
                                arr[j] = arr[j + 1];
: i, I. x4 r! G                                arr[j + 1] = temp;
, ?6 M0 x$ o3 f( O: D  v3 n                        }
6 _, }' [; b) @' m9 \                }
- p; I# B& [+ X; K/ L* \3 b        }
}
. N& V" C! }7 d' f7 H! O+ d2 K
1
/ s, U# t( O5 V6 E3 O2
3
" Z* u% p' N$ X4
% C6 E  h  j4 e3 n; b( d5
( j: N! X' j+ y# n% E6
7
8
9
3 \! H- d5 i% [* ^1 G- r  {10
11
12
13
14
15
4 i1 p7 u) a- U( Z3 E16
17
18
19
4 O' ~5 z" R/ K  v5 j  v- u优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
1 r, c/ n' N, n6 p1 J1 x, S- A
) e5 d' Y% ]: f" l. b9 `1 f//从小到大：
void bubble_sort(int arr[], int len)
{
; e' T; [3 s/ \/ j        int temp;
        bool flag;
        for (int i = 0; i < len - 1; ++i)
) L3 Q, d; U) F* Y9 f1 K        {
. s8 F' _! o. P" S: D* x. D            //表示本趟冒泡是否发生交换的标志
) v& u+ R& E9 _: }1 Z3 p                flag=false;
% T9 w! c) |. \5 s               
                for (int j = 0; j < len - 1 - i; ++j)
* ?- T- H5 @: a+ c! g. D8 M                {
* l% z. c! h% L: X                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
# F- N3 l) ], P& R, i7 I' g: q' g# i                                temp = arr[j];
                                arr[j] = arr[j + 1];
3 G, H% E3 _& W( u                                arr[j + 1] = temp;
                                //有发生交换
" \5 \' M) y: ~0 m                                flag=true;
0 ~. G9 `7 Z, a2 k$ w- H/ T                        }
                }//for
               
2 R5 z' }: l+ y3 L9 x6 `( Y2 h                //本趟遍历后没有发生交换，说明表已经有序
5 p9 N: s3 h( ?0 O) \                if(flag==false)return;【1】
        }//for
}
$ {% _0 {7 S$ k/ L2 g
9 D: ~1 w+ m, }  E# b/ M+ k1
2
3
/ }4 K' }7 s* T4
5
6
7
! `0 t# S! A  S8 o  n- k8
9
10
( o- U" v7 e& b' F! b( ?9 I; H11
12
8 L9 W+ i/ d4 c% Y8 {13
14
15
& R/ D- \2 O2 H4 Q, c* F16
5 _7 a6 B( ]( t) `' u# Q17
+ o4 d  ~  J9 M: K18
19
9 t, y- Y, Z  |: J! T20
21
22
23
24
25
" W% E, }! g; ?# S( |+ a5 g8 W26
  o0 {) u# K% `/ S时间、空间复杂度
& R# N$ }6 T! S
2 M6 u/ g/ t& y. O8 F4 j适用性：冒泡排序可以用于顺序表、链表
2 U2 S  Z6 k. J& J' N



" R- J: s, I: }. x6 @2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
& Y: t, E, [  N/ ^在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
9 c- D# r6 {8 B9 d( U, x) o通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
# ]6 z% w) u9 a) V% K6 I$ S' E8 i) F再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

' H( E* N3 B; X. V+ y4 i, Y然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

划分的过程：
+ m5 F, a  x; v+ S
3 W6 h; Z7 r, l. `4 H( B, w初始状态：取首元素为pivot，定义low，high指针

首元素为49
high指针指向的数据小于49，就放在low指向的位置
- t4 B4 O2 `! G: s1 h  i3 ~low指针指向的数据大于49，就放在high指向的位置
; @- m  c9 u+ {/ F  A
) _- t6 E. [9 Z; G" |
) O6 u7 e' u* P( c) {

4 y. e2 d' g! `
// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
        //取首元素为pivot
! @1 Z7 W; o, k6 e: v    int pivot = A[low];

$ Q. `2 w, X: F) ?( D9 L4 O    while(low<high)
    {
            //先是high开始向左移动
* ^4 L1 g" d) S% X        while(low<high && A[high]>=pivot)
- [! x3 I0 [! r( J! B! n& i% F6 Y            --high;
        A[low] = A[high];

        //随后low向右移动
4 ?9 o* S$ c8 u1 \% u7 t        while(low<high && A[low]<=pivot)
  N, u) m6 N! d            ++low;
        A[high] = A[low];
. B% [! N: l1 U# _9 H. V    }
/ @' h1 b: D/ v" z9 u4 D; Z
1 _) y, X; U/ R& t) R8 M    //low=high的位置，即pivot放在的位置
    A[low] = pivot;
' e8 \/ p" C6 a3 g
    return low;
}

9 l3 z# B1 o8 `4 G4 f// 对A[]数组的low到high进行快速排序
5 G" \9 |9 ?5 ^; y, c/ ?8 q$ evoid QuickSort(int A[], int low, int high){
    if(low<high){
5 V" _  g: B8 k' `8 l3 D        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
    }
}

7 b" K, I$ c$ C) Y" `" X6 E1
2
8 H7 n2 x! P1 }! g+ L, X$ O3
' I. B5 S9 e9 f4 T, f4
8 ], |/ N9 F6 w7 u$ o# D5
6
4 W& L+ i, }9 ^$ D; \2 G, y# |7
8
9
10
% c: |6 J) n0 Z1 R' }11
12
13
- z( E( J4 _/ @  L0 [7 Y' H14
15
' J" u/ u9 c' f16
17
) [. a! k1 b4 o# I+ `18
19
20
21
# s8 }5 D* e5 N2 n4 d# c22
- W0 Y4 ^8 H6 h7 X9 b  N1 j23
4 ]  `/ l( c8 Y/ F0 `( h24
25
26
3 T$ O$ W$ T# i) L, i/ T) B6 U27
" y8 Z! C& _0 e7 x( A' d% E+ _. w28
29
5 ^& J5 n8 S# K  U& F30
31
32
时间、空间复杂度

, o+ @" L1 [& d, q/ R9 H3 [
把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

/ R. Y; _. r& M: V1 O4 n8 U, e* on个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

时间复杂度=O(n*递归层数)
0 C! z) j1 g8 `" P. ~最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法
' k, Y: `  N; t# Z0 n6 E
空间复杂度=O(递归层数)
8 N8 e% x$ ^5 _9 q6 E& v/ M最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)

( U! a$ `6 F' a最坏的情况

5 @, @% w8 h- {3 \6 o

⽐较好的情况
  B% ]3 m! e# T
; ]5 G; V; P) x4 O& V0 w

5 \% a0 G  W3 E5 e' V! z不稳定的原因：


" p$ W6 b6 e. `
8 X/ ~' d8 S% |; _# E

3.选择排序
. j3 x$ Y; f# n( d- P/ l选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

: U: @5 H5 y. h! Z3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置

1 S* J5 F5 A' F! _
6 n; G# d# u/ ~4 R$ }
// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}
6 F$ I3 a) [$ f  i8 O
& J9 W: x( V- @0 Z5 L1 Z// 对A[]数组共n个元素进行选择排序
7 Z/ n5 F. S  ^: q1 ?- {void SelectSort(int A[], int n)
{
) J' H% p: v3 z  n        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
    {                 
        int min = i;
# D# u8 S3 _* r$ @$ L        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
9 w9 o+ S$ `6 ?            if(A[j]<A[min])
                min = j;
        }
+ O  X% r: c5 B        if(min!=i)                     
! A: |$ j' k9 {/ D4 r) k            swap(A, A[min]);
    }
$ _* d5 u7 d6 m( C}

6 L) Z. u' c9 ^9 V. e1
3 ?" z% E: i9 J7 H  e1 I: j2
3 s8 t7 R5 @# t/ E; ~; a3
, d6 S# w' h$ x2 V  {: j" u4
5
6
( N( |7 |- I& F2 D/ S7
8
9
10
11
1 j$ l2 x& d6 x7 @2 Q2 M" q12
+ _' N2 m: D% V7 v6 }2 f& K13
  s! V5 u+ `( f3 J  Y7 G14
0 t6 _9 M4 j1 W. J( `- R4 ?15
+ \% e6 x) J, E' w16
. G2 X' U% ~- L4 ]! f7 ?' R17
18
" b! j5 b. {# A19
) m. q$ D) v6 H1 ]) Z% _20
21
3 J- R& I: A7 K; d" s4 `& g, R22
& U; ^" P3 z$ \+ T补充：对链表进行简单选择排序

void selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
, d( k; I- B4 J. V; ~$ v    while(h!=NULL){
  `2 N7 C: t7 |# V        p=s=h; q=r=NULL;
        while(p!=NULL){
3 k3 W8 r* h2 ]8 {3 f8 I            if(p->data>s->data){
                s=p; r=q;
            }
- G8 L: o" g6 P+ X0 s' F! p$ c            q=p; p=p->next;
        }
        if(s==h)
            h=h->next;
* m7 }  N: i) [' Z3 j        else
            r->next=s->next;
5 A9 }# i% ^0 t( M) Q        s->next=L; L=s;
# T+ b4 n1 a$ ^% e7 z9 T    }
7 B8 b: d. J# ]}

, j! [4 I$ J; {: g: B7 s# r+ M# g1
; I0 C. V2 Q- _0 w2 e2
3
4
5
  V" a0 H2 F; T5 s8 z6
5 r) W+ k: l6 W1 R8 @4 R7
8
  o% {3 v3 J5 d/ \1 w- j: X- ]9
7 l* m7 E! l! l7 W$ d1 n6 U. Q10
11
1 i% n( ^' O; k* a  y7 t  o12
13
2 e- O8 s0 O7 S' M. p7 s& p( o$ H- p14
& }$ a. d2 ^6 z+ B" C15
16
17
$ A: S4 ^4 m) o( J7 N) {. y18
时间、空间复杂度
/ N% V! v1 N2 L# `# R7 R3 @


' m  N4 J% k. t( @$ m6 {4 f( j
1 O9 D/ ?$ M& K2 C& l适用性：适用于顺序存储和链式存储的线性表。


1 {$ Z2 P; {( X, T
3.2 （不稳定）堆排序
) C0 u3 J! k& |) o① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
" x2 w  k% Z# I) E7 w: {或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。



即：
若满⾜：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）—— ⼩根堆（⼩顶堆）
/ H7 X6 E- L8 P7 k0 `  \
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
/ E' ^; z6 s* t# l# Z思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
" f2 P1 O) T4 f* \
在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

1 g" `+ E! E" a; m检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

* ^9 d4 k% @3 M. F& o3 S$ k过程例子：
" Y; d1 v: y% B7 S- T


建⽴⼤根堆（代码）：



7 {2 h  c' N2 ]// 对初始序列建立大根堆
- ^# v0 r! S3 m. r+ R0 u! Xvoid BuildMaxHeap(int A[], int len){
3 ]& _  w; N+ @: O2 N  B    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
& S5 S5 M# b- G5 ?, ]/ R+ y        HeadAdjust(A, i, len);
/ t$ K& ]9 {8 {  N}
) }* C+ ~. W; s- y2 D9 ]7 M; T; l
// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
            i++;
        if(A[0] >= A)
            break;
        else{
$ ~* j# S, i$ R            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
        }
+ {" R7 d, q$ K* ~" s    }
) L" }7 R0 [, i/ A* @% v    A[k] = A[0]
}

1
2
7 W4 ]3 n+ x0 ^1 j3 v+ J: Y1 j3
4
5
6
2 M' j- o9 F0 _! F+ g+ k2 t$ k( p7
  E$ N) B8 D9 o2 O8
( @7 ~  ]( m2 h3 J7 e5 W7 e& D9
10
2 R+ U, S- s, w/ X7 j11
3 b: M9 A" b* ^! H  \) x2 e12
13
14
# A! p( G2 L# b& A) I; R15
16
17
, M1 d3 e/ x7 w# J6 s+ M1 L18
6 D/ A( ~& G, E: S- g( s2 x8 R7 M; W: L  w19
20
2 G. s8 m' Z- k# N/ ^21
( \' }7 f* L+ B+ x" Z% i$ Q# w③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
, Z$ U4 `4 i6 g2 |选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
& G1 Z. z. c% f
, |! D& L3 u- I9 e) R过程：
: u9 _8 ?, D: N* l' U3 Y
// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
: ?+ N6 }( y8 u, U3 ?+ S    a = b;
" g& ~& d9 B9 ^3 t' Z- O$ H/ x    b = temp;
) p8 O4 }2 e5 z0 x: q# y( K  c}
5 \& A% P. U/ q9 S9 ?' ~6 F7 C$ d
// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
        //初始建立大根堆
3 e, y% @9 _7 Z    BuildMaxHeap(A, len);                

    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
4 h2 s( n, J* R$ {    {             
/ m% n. K* f, M        swap(A, A[1]);
/ Y3 `1 a: B$ p        HeadAdjust(A,1,i-1);
    }
}

+ ?: v3 ~4 }1 `0 a: N; n1
2
3
3 J/ I5 b' B+ }/ b4 g8 L8 }4
5
6
7
3 _# k: E" z) q6 H( e* p  V% @& H8
9
10
/ d! ?- y# C9 a$ ], C11
12
: K4 J8 g5 \7 [3 `13
14
. G7 P; f. h. F, `- f% j15
16
17
4 k2 l- M- ^/ \; v' N- S18
! \& s; Y- n. ^* g. ^19
9 G4 h* L8 W# Q  c时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
+ F$ [3 p$ N6 {故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
, n, t" m- B& g* Y
空间复杂度 = O(1)

9 @& q' P5 T+ K1 R  z2 P9 _7 B. v% b结论：堆排序是不稳定的


④ 补充：在堆中插⼊新元素
. }4 \$ R$ y- w7 }5 B+ w: K( Q对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌
  a4 f. U- G' e$ x4 l

+ o" S( j" C* \% h' _& t
  k6 S7 q& R4 \4 }⑤ 补充：在堆中删除元素
. @$ P$ F" X  Z被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
% h: ~- t7 P' J4 X! q
8 K& V* h) B/ F! ^0 k



4. （稳定）归并排序
, T1 S  a+ q% y8 C8 G归并：把两个或多个已经有序的序列合并成⼀个

3 c% b, U& b, F! u① 明白什么是“2路”归并？——就是“⼆合⼀”
$ |$ }1 R' _" X* t: c8 o9 l" f
多路归并：


8 L  r: m, `; o% J% e, Y" h6 o7 Q② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

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

7 Q3 c& K; ^/ _2 X; {- b③递归进行分治思想【MergeSort(int A[], int low, int high)】
0 I( l  P0 ~9 ?" S% W" r' _
" m# E. m* `+ j  A# p6 \' c* S
( ~! `! p* o# i' W- A④ 总实现代码
3 C4 a$ U1 [5 C# Z1 v& P// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));

// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
    int i,j,k;
3 s8 {) V( v) J; j  v    for(k=low; k<=high; k++)
& ?: W2 O( D& U" V6 x4 h6 D        B[k]=A[k];
, p% z3 p, q: W$ Z7 C+ K% x    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
; i7 Y3 c6 c* b( G! F1 _" `        if(B<=B[j])
            A[k]=B[i++];
' H  q# {% m% p  B$ h" Z! h5 _& \0 D! |        else
            A[k]=B[j++];
& H; A$ `9 }& J9 z3 u, S    }
! @& ^3 w6 K9 |8 H    while(i<=mid)
/ q' ]/ y6 M) A0 Q; h% j        A[k++]=B[i++];
# w8 G5 C9 c& f8 Z% [" D    while(j<=high)
        A[k++]=B[j++];
}


// 递归操作（使用了分治法思想）
! P/ Y5 e  z9 V3 N; ^9 Svoid MergeSort(int A[], int low, int high){
    if(low<high){
        int mid = (low+high)/2;
        MergeSort(A, low, mid);
: ]( T- x0 o  {, s3 Q        MergeSort(A, mid+1, high);
' u2 a) B' J  c. e; S        Merge(A,low,mid,high);     //归并
    }
}

% t0 L4 S8 p# V: g1
! F0 o1 h6 d# G2
! R% ?: c* L% O) l3
( W4 H. u7 N( s4 }! {4
5
* p; P: {7 S( i+ V) ]2 U6 d6
- _$ u# W. M9 j5 D# n1 y- r, E1 J7
1 s' M2 ~$ C& Z4 e, C/ b) |9 H8
9
. f2 c: W& P" E; a10
- F8 ]' @7 I; Q9 c8 B11
, f- f' l- V! ~; j# `% j" I12
13
14
15
: P8 W7 l. E5 c$ U7 q7 v# N$ Q16
17
" k) d- Q/ b' {6 Z, N, j/ k18
19
  f6 F9 h6 Y3 z" Q0 ]  O7 L, ^+ O20
6 S( j. {  r/ R) G& A" k) f) h21
" s3 b/ H5 p6 K+ T0 m+ G2 A22
2 x  s+ H  U  c1 t23
24
2 k$ J6 J# E* W" G/ U- G# _25
26
2 O" K/ c% k* B5 x$ N" y- }27
28
29
, t! D4 m  M8 Q30
, v7 A9 k7 H' R  Y% {* }" ]时间、空间复杂度




5. 基数排序
8 B6 k/ M* j, h+ L. }直接看课本的过程图来理解P352
3 |% x; {; S7 X% O/ N
& ]+ k) M& C) P再看这个例子：


, K$ F" E( Z4 x& Q  M9 S" n算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
8 q9 |& s) G' e. K收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
* O8 E* z) t5 p& ^①数据元素的关键字可以方便地拆分为d组，且d较小。
$ J+ Q& I6 q. p# y9 H( A②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。
算法效率分析：
9 T$ p  _; }4 D8 [2 ^6 q时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
" A& V( k6 h. W8 ~" }  u稳定性：稳定。
7 T' y2 K1 `6 I; J% T
8 P  R/ Y$ v  x) X6 m2 G+ g
) {$ u- C  W6 F内部排序算法总结
* k3 t9 E& ^- M6 }$ `6 p
————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969