数学建模社区-数学中国

标题: 【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选... [打印本页]

---

作者: 杨利霞    时间: 2022-9-4 17:18
标题: 【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选...

! U$ s, F1 [8 z# ?【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
排序
1. 插⼊排序
: J9 f4 [" Z: I+ O! d（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
: y2 v9 P" v3 c+ o5 L) F+ Q时间、空间复杂度
2. 交换排序
2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
6 N9 T0 I) G# h9 y5 {3 Y6 u3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
8 \) x: s4 L$ f# A③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
④ 补充：在堆中插⼊新元素
  |2 K+ R/ u% J# I⑤ 补充：在堆中删除元素
4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
6 t3 b& {4 F9 }( {② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
! |6 S+ W$ ~6 e, B! k③递归进行分治思想【MergeSort(int A[], int low, int high)】
7 @2 z: v3 v5 f4 x④ 总实现代码
时间、空间复杂度
5. 基数排序
7 a2 u( ~/ J5 l( A; O0 S内部排序算法总结
1 _( J( U* W7 X( o. [, B排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
3 f4 _- |0 ~3 {) o$ L# j7 h
+ I+ f! d+ L0 K6 y2 O! P4 p排序算法的评价指标：时间复杂度、空间复杂度、稳定性。

3 l0 _& b; X" a+ |8 N& J* |  K算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。
+ c/ C+ {" F: ?

排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
+ o# G8 t; s- l7 K0 G9 O4 K外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
2 M, K; P) H0 m' f! O3 P. z
! u. g) ~, j& D$ ^: j5 ?各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
. \' P; E, b5 {+ N0 C: ]  N% [* b
7 P+ P- _7 a* g/ d/ i

" n, ?- f* ^; w* h" {, ~  N1. 插⼊排序
. |# U( [0 _5 k$ m: f（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
2 e% [; u, X9 h7 Y) J) ^基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
9 A8 o% G/ o3 o  `0 @2 e3 B1 [
算法解释：（从小到大）

( H, I. S0 s5 U! v9 O
算法三个步骤：

先保留要插入的数字
7 H. [0 F- _3 k1 a2 W往后移
( I3 e9 N9 O. D- q. v* s: i3 g插入元素
4 ^+ d1 a" B7 a  O3 c% d
( f4 U7 }2 q& Z// 对A[]数组中共n个元素进行插入排序
  }; v3 Y# m, h  ovoid InsertSort(int A[],int n){
  Z7 _" c" f7 [6 d3 W    int i,j,temp;
! q+ {; J* m! W    for(i=1; i<n; i++)
6 `; V" B4 G( d8 D8 Q0 Y* h    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
4 r2 W: c; @$ y$ ]        if(A<A[i-1])
        {           
6 w  I2 _  b$ g! S            temp=A;  //保留要插入的数字

            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪

9 _; {# v5 C" q1 |            A[j+1]=temp;//插入元素
        }
    }
}
6 h) M& t  n& f. U& ^% N$ I+ W
! Y% O) U* t3 C. L1
2
3
4
5
6
7
8
5 B. j/ z/ {3 @7 x8 s7 |$ Y0 Q# X9
: Q+ D7 i- a$ T- T: i+ ~% c10
3 ], Z5 _, V/ m% r* ^11
12
13
14
: j3 E3 p6 A( w15
16
17
5 I$ ~/ d! |" f! q- E1 f* }用算法再带入这个例子，进行加深理解
5 W. n" X9 f! p; d6 Y* z% Y/ Q

带哨兵：
* I! r0 g0 W9 g# w4 e8 m. ?
7 f9 m4 D1 U5 P* Y' k
1 v. |4 ~3 C0 Y5 T4 [$ s0 d补充：对链表L进行插入排序
& h. }5 K  {0 r* v* F
! I7 m0 X8 B* Q$ V% }0 P2 \void InsertSort(LinkList &L){
3 d8 g# W! Y0 L3 Z    LNode *p=L->next, *pre;
    LNode *r=p->next;
    p->next=NULL;
) c. y4 g+ Q: F$ q, k0 U6 b4 Y    p=r;
    while(p!=NULL){
        r=p->next;
        pre=L;
4 r+ u/ Q  t6 b& [) i        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
: S0 e1 N" k. C        p->next=pre->next;
" |6 ?2 Q6 r  I+ B# c* u/ }  `        pre->next=p;
& c- i  ?) L" `6 I* r4 w        p=r;
    }
5 ?0 Z! @0 |. ^9 L9 C  |}
1
2
& M& i/ R8 [/ A1 i, |6 u9 i2 m3
% I1 k. `+ X2 `! c8 C4
5
6
- R, Y5 S* F" x/ h7 C# w7
, u/ o3 ~( t0 ?5 q  T% z. X7 o+ f' I8
9
& j4 U! x& O" p; ~3 z. K5 ?6 v0 ~10
, S  C3 I$ T0 a! F/ P; v/ X& _' t11
) `% B+ O" d/ t: C" A0 G1 P12
13
14
* ]4 j: }  z: W# n  o4 K15
3 \' S$ ~; V% b. Z时间、空间复杂度

. _: j# \- y0 p3 Z" Z  T% ?2 o
/ P. J5 \% G3 O  P7 L/ F$ ?9 D. ^最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
最好时间复杂度—— O(n)
; s8 ^" E  h. }; C2 I- F; b
最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)





# m' n3 y6 K. ~+ J（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：



2 A+ F  T9 B$ [4 A//对A[]数组中共n个元素进行折半插入排序
8 B3 g+ S' ~: svoid InsertSort(int A[], int n)
( B2 G# ]3 u5 i! \$ `8 \4 z{
. f5 z8 H3 q" Y: O1 s# [    int i,j,low,high,mid;
. I, q" G( Z$ g& z    for(i=2; i<=n; i++)
! l' K0 h3 S1 X4 q6 {4 D8 E    {
" D* i* q* U$ ~0 v* Z1 ~7 i/ f        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
        while(low<=high){            
* F; y8 ?( U" K/ O% V- Z1 I; o: H            mid=(low+high)/2;
            if(A[mid]>A[0])
# Y3 N( V" l; l$ e- X                high=mid-1;
            else
# d# I) k4 ?8 I" j! n                low=mid+1;
        }
         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];
( j- q; j, ]6 B/ V1 E
5 P7 x9 T% C8 H: T1 }. H6 G. `1 L        A[high+1]=A[0];//插入
    }
! c9 d3 X) B+ a}
5 P* `4 G' a( J
1
2
3
4
5
6
( _3 ?& d8 Q  j# h/ N7
  {; `8 D. h+ n3 K+ \4 l2 F$ r" [0 a8
  t, ?. t* p* N+ R" X9
10
11
12
2 `! _+ M$ x2 r$ n- P9 i2 U  ^13
14
15
16
17
18
  U. f6 I# s. ?* P) Z19
: d1 A7 f1 s% y7 m% {/ n20
21
( P6 D; m; j( R3 p22
1 p3 X4 M& d+ m% ^0 p23
时间、空间复杂度
空间复杂度：O(1)

【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
2 }: m, {2 E+ o
4 m8 }( r- f$ H! l5 z" D' X6 M
( a8 x) Q$ m7 S3 J$ ~; I4 A! n（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
4 g, E" n1 R' {4 a* K$ {
算法思想
, a) o9 ~& n% r* _- [: n
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
' K! |& {0 q9 U) E  c2 R图解：
7 s& f; I- U: g/ ^


代码实现：

//从小到大
void shellSort(int* arr, int n)
2 M- b' {5 Q  ~3 o{
* u, f; h* Y( \3 G" a# Z        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
; i* y% s1 d6 H- ~            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
9 {4 k: ~4 e8 V                if (arr < arr[i - gap])
: p* t( P, S+ F5 m' p" v                {
( t& r+ W* M. G( E0 \: O/ y                    temp = arr;
( Z" ]0 t5 ^) e& r7 K
- U4 H4 s( O9 w1 c, x                    //后移
- g! E: L& |1 x7 m                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
3 Y. M' v" W8 @3 i+ h; {                        arr[j + gap] = arr[j];

                    arr[j + gap] = temp;//插入进去
                }
8 d* j/ y/ E6 K; z" b            }
0 a6 s8 Z+ c( H% m% `; j            //************************************************************************************
4 V) o. q9 \$ k2 S) {        }
}

1
2
& d4 |5 W1 Z- Q" x# X- T7 |6 K3
4
4 G8 ~9 \  e9 w9 y- |5
* R) p" B. [9 \1 ~" M* L6 ~6
8 L+ W8 X+ X7 P7
8
3 J3 ?/ M/ T* G) r: S' n# \. ^9
+ \% O7 U6 }" h# W10
11
12
8 d  |9 |8 w, ~6 J, ^* I13
% m+ Z: F9 `/ h$ E+ k14
/ B& O; Z9 y8 [15
* Z) V2 n+ G9 S16
0 L! E$ z% f/ |, ?5 K: P17
- U7 r$ ~9 ^2 z4 N+ x; ^- _18
) q- Y! U4 m- H5 p. p" C19
9 k6 A. g7 f2 E& I2 V20
21
5 F) V% U/ B& m% F5 o22
; g# K8 b% ^" w8 b) w23
24
时间、空间复杂度
# J, {! C. ]- H# u7 {空间复杂度：O(1)
' o, G; `5 e. M
时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
/ `. T8 [! y9 G% y- Y" {
稳定性：不稳定！
6 e: |% P5 b: z; ?. v! D; G' p
- T& c) Z8 E) K7 G. E0 z

* X4 S* d( o7 T! j/ d$ u' F& j适⽤性：仅适⽤于顺序表，不适⽤于链表
8 x0 e: X% [# `3 k, U


& Q+ ~" F6 H' e- m. p) v2. 交换排序
6 E6 ^/ W( u8 i# |+ ^2.1 (稳定）冒泡排序
+ R: Z( k, H4 ~" Y# k英文:bubble sort     (bubble 动和名词 起泡，冒泡)
4 k% I" w5 Q0 d7 M+ r- r从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

9 |8 T* }% u- C! R$ E8 I每一轮比较会让一个最大数字沉底或者一个最小数字上浮

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
  e5 q6 a+ Z8 r  h0 c# O
' t' Y7 k4 u8 T: m4 _" v' [  `  l: U实现代码：
! v" m5 u6 a, [* {- D
: ^! z) u. |$ k- X) C0 m//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
, R1 q9 m8 t! r9 v  N- ~8 a3 i  L{
  }) }5 r: J$ }' |5 F7 @+ Y        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
2 f; Z) Y. D6 P2 g& r; k        {
, g% `/ ]6 I2 T& N, H                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
! Q( H0 Q* F4 K9 }                {
                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
/ [! A# n4 k' Z1 P/ k+ o                        {
                                //交换两个元素位置
                                temp = arr[j];
6 f+ o4 h$ `+ _; c, s) |& D                                arr[j] = arr[j + 1];
3 o4 P% }: B8 ]! ?2 p$ r                                arr[j + 1] = temp;
. `6 X. e0 j) T3 i& Z( I                        }
                }
        }
}
7 a2 Z  W/ V# c2 e& t
' S' T2 d% M1 Y2 ~1 X3 S1
# Y6 T4 q6 v+ s4 B2
3
& i$ q7 R2 @+ x# \: C0 `2 Q4 ~4
" t! P, h2 {$ b+ ]- f5 ^5
6
( ?2 @! K7 N7 E" G  j/ P. x3 n7
8
8 X; e2 H+ \: H. q& D2 ^9
& }7 ^7 z; A, |/ U10
1 S  f  T; B1 f7 Z11
0 s! Z" P0 @% j- Q! F6 T12
0 F; m: ~5 ~, F1 K13
3 v4 J/ H0 ~: g( y6 t# `( y14
15
16
17
18
19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
$ w% j& Y3 B4 I5 f
- ?# `- d* Q  z& |/ O! h+ T# K: h3 j//从小到大：
$ o3 k, P0 H' t. {void bubble_sort(int arr[], int len)
' {- @; @5 I. l4 Y{
" g4 n$ u8 A3 e  T. N6 f% Y# B        int temp;
1 N, G/ g( m. W; X, ?7 Y        bool flag;
        for (int i = 0; i < len - 1; ++i)
- G6 n0 S' [! G9 G. n8 H        {
            //表示本趟冒泡是否发生交换的标志
3 M/ X6 _1 B1 b0 \                flag=false;
. d$ F7 c. L$ T0 n               
                for (int j = 0; j < len - 1 - i; ++j)
                {
  [5 n9 y1 f3 X& [9 p" k- u                        if (arr[j] > arr[j + 1])//稳定的原因
0 @$ C- w( Y% J6 x6 @                        {
                                temp = arr[j];
2 R  q5 x; u. m$ _9 \                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                                //有发生交换
                                flag=true;
                        }
. t. z1 i: F8 D% y( y                }//for
               
                //本趟遍历后没有发生交换，说明表已经有序
( h! e% N/ }9 y                if(flag==false)return;【1】
4 |+ I' N3 |) M3 Q$ `        }//for
8 l6 ~& B9 x/ {* H+ h}

/ ?3 v; d9 g5 B: ]9 f- B1
# _/ i0 v0 d7 }# ~+ c5 l& T2
3 f, f7 |/ H  r: m# X3
, c- ]' t: \4 P/ O9 J4
/ g7 v, z4 N+ e) B# n( P5
6
! L7 j, P9 R/ g( D6 I5 l2 z7
8
! _6 Y- i$ g- a6 R9
5 E8 ~6 |% z1 }& U, h; Y10
11
12
13
14
) N; w* E1 K1 o" P: f* o% r. ?9 a4 x3 T15
+ m( I3 a  [* {4 U4 ^16
3 ^1 S8 I* b, H2 X17
18
. Q# u1 m: c8 I( ?" V! a, h9 [3 ^( t19
7 K1 Y" C9 z, ^% o3 b, l8 U20
- k' i0 e( C# \21
" S- z0 \9 Q4 ^22
23
24
6 h4 C/ B! A- I* _, e25
26
时间、空间复杂度

适用性：冒泡排序可以用于顺序表、链表
. m, o9 R' C- m" y# H' q; G
- _2 Z0 Y& x' b* W3 _' ]
2 b3 n' e5 T. a7 O
& h" P; j3 v8 Z) D, ^& _
. b4 @- R2 B+ H! j7 X2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
. o0 U) X. g" E, p- [( [在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
0 h3 d# w6 X: }: X4 ^# j9 R使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
* }) e9 a& Z- s) ]再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
! s0 R5 V9 V* P
0 l. y4 A  I5 H5 u0 o  ^9 q) J  D然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
; b3 {7 b( ^; C# K
划分的过程：
, V# P7 K1 y2 f
初始状态：取首元素为pivot，定义low，high指针

首元素为49
high指针指向的数据小于49，就放在low指向的位置
1 I# D1 d. A, z7 \2 v8 f- S2 klow指针指向的数据大于49，就放在high指向的位置





// 用第一个元素将数组A[]划分为两个部分
. X/ [8 E' k( _9 `$ _7 Rint Partition(int A[], int low, int high){
        //取首元素为pivot
    int pivot = A[low];
+ K: M8 V5 s2 W
' J- w. @  ~! U, x8 G2 q0 d( C    while(low<high)
    {
            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
            --high;
        A[low] = A[high];

        //随后low向右移动
' H! ], b! T; _  @9 ~" h1 j/ M" R: z        while(low<high && A[low]<=pivot)
, N/ v% i9 Y  D) J2 H            ++low;
        A[high] = A[low];
( O$ b1 W5 E$ B7 R( H    }
' A( r  V, @8 N0 G9 N9 q! ^
    //low=high的位置，即pivot放在的位置
4 _( E. a8 p( L4 R0 }    A[low] = pivot;
/ B" L( N" p3 e$ o8 s# |: s7 D
    return low;
}
3 K  v- e3 q5 q  l& x/ p, z3 g. ?
$ L+ l* m8 M3 A- w- ?* ]// 对A[]数组的low到high进行快速排序
8 R/ P% s/ p1 s+ ^3 Gvoid QuickSort(int A[], int low, int high){
+ s/ G1 \2 ]7 |    if(low<high){
        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
4 b9 s/ `8 O# ~6 h5 z! y2 D( ?! |9 J& X        QuickSort(A, pivotpos + 1, high);
    }
7 n, R# h4 \: V# W: r% z}
: v7 S! K* C4 R& J- v" e4 `. y
$ E* g3 C7 c% X: s8 p8 `! v3 f+ f! `( t1
2
; h; x# k& B3 U* `; u& r3 _0 H* u0 X2 C3
! j+ n* ~* \5 [" R- A8 L& p; j4
5
7 O* _% H& \, w6
: b* j  \8 N1 p8 e0 a) c5 ]7
; S* r. d5 H. H+ m% b8
9
* N2 D7 q8 Z- t( s1 y9 I; O* g10
11
12
13
; V; M* {% g4 d: e14
15
16
17
18
19
# a/ z, l6 A& G( o0 e$ l20
21
22
0 T. \1 s% \' C+ U- L! s23
8 h5 U# z7 G$ o  k; D, d( Q24
7 D- z7 p  ]; N% F0 g: N. F$ p25
0 v; M3 \8 T! w0 Q+ z& U" t26
27
28
29
3 h  H/ ^& z( W: M30
7 }( ?) o1 V" i* L' C% T31
32
时间、空间复杂度

9 ]' X4 n3 T( ~- \$ M: H% s
把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
# H2 u% W' ^3 d# ~) Y& E8 v3 Y, \
7 t5 ^8 R# B9 ?5 q: L3 Q5 c! fn个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

# q6 \' n% R* }5 ~& b# B+ w( \时间复杂度=O(n*递归层数)
1 x* e5 C* e6 b! J7 j. @最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
* M6 P3 }2 I3 H& Q平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法
7 k4 J' }# o& L8 ^6 y
空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)
7 J; l- R  G. _' }( J0 J, ]
% t+ I% U& n1 ?( a% Y! P# {+ R最坏的情况
' |0 a' V2 o7 S7 y# @- i


# j. B( z& `/ y' e2 T$ L6 E8 V⽐较好的情况


7 V1 s% B6 W1 ~$ H9 d3 x
不稳定的原因：
1 b. J+ I) i9 |$ q. R0 r


' P6 e; t1 U2 I

& o& N7 B3 L0 Z1 B$ c- |  u3.选择排序
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置



/ j3 A* l" z8 ^, P; z% v! I// 交换a和b的值
  B9 X# N0 ]- _void swap(int &a, int &b){
+ X' ~  n$ J% e    int temp = a;
    a = b;
2 Y# K4 ~* ]/ {! G    b = temp;
& C7 N$ P2 J* ~2 c3 Z}

// 对A[]数组共n个元素进行选择排序
4 x5 K2 J) Q# S6 T; m1 g# Svoid SelectSort(int A[], int n)
{
/ G3 ^8 S; |! L; o0 y+ [3 J! F        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
    {                 
        int min = i;
" \- f! P4 R4 ?% X+ R+ A        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
! {3 ?+ Y4 b% H, z                min = j;
        }
        if(min!=i)                     
9 @% R# e$ W8 V9 ^! `            swap(A, A[min]);
    }
# @" t0 m5 z+ i6 u/ w}
1 L+ r. W0 a- I2 \0 b  \7 d
1
& ]! U0 \% B8 ?: \" F2
3
$ U  b+ _1 v) y8 Q- ~4
5
6
7
. s% f/ G7 z6 z$ o7 r8
9
10
11
12
13
( `, _- {/ n/ }0 B14
15
0 |$ [" o3 B2 x& n0 X$ C16
# \6 N0 k, u8 C9 Y3 W- G. Y17
( c$ h. i) W& W& \2 ^18
2 F: L& b# `' r9 }- a9 `3 n19
; x/ I" N  s7 z# N! P, ^20
21
# j; R* p( s4 A! P4 b! m22
补充：对链表进行简单选择排序

void selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
$ s% j( |( W+ ^/ U  o: L' {( Z    L=NULL;
: x" U9 P2 u7 M% w  S, P1 X    while(h!=NULL){
6 J3 o( J% N& Y- ~" G$ K        p=s=h; q=r=NULL;
- o; E9 Z" v- N: ~        while(p!=NULL){
            if(p->data>s->data){
1 B4 O, g/ r0 u) K* b                s=p; r=q;
4 m# H  N; r6 R& M. k            }
% l1 M7 ]0 @9 N            q=p; p=p->next;
        }
1 \. O) g6 Y: G3 O        if(s==h)
            h=h->next;
        else
            r->next=s->next;
& Q  @/ \1 Y1 m. L" Q- [+ U" }        s->next=L; L=s;
9 Q; ^" C( K, |' s    }
$ z5 O5 J3 v" d  ^7 P4 n0 ]4 G}

1
2
3
4
5
6
7
% @# p; E6 O9 n, n* I. ]8
* Q2 F( J% T- A  R7 n0 n( T9
10
# x4 u2 H: H1 ~& x11
- `9 c3 |: d3 ]1 w0 i12
( f% F% l" }, q* K- e% [4 E13
+ z7 B3 W8 k% f# d14
15
' i& p  e9 d/ T5 u( g2 V) Q16
7 c7 T& U0 q+ o. J17
18
! s, d! Q6 x0 N& D: w时间、空间复杂度

/ w) L* j3 j  _; l( z2 J

) t0 K' C+ ]. t4 k* m. d
适用性：适用于顺序存储和链式存储的线性表。
, s! h+ P& A0 ~# p

) Y, n4 W: Y- e1 `5 \
7 Y8 v. @& q' a7 Y3.2 （不稳定）堆排序
3 [- y5 X5 l& B7 C) z① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
2 N* Y: u# T0 i1 B" a6 H或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
/ G9 }: V+ O+ X% f& Q

! s5 D; P  |" g0 x
即：
1 r" {/ F% ]# w# B% w若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
* [+ k7 z7 Z, |; [若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）
3 z0 ~! T9 a) j, D
- g$ ~! \% w$ @: X# X% D+ U4 Z, Z# T② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
, h: x- A7 n$ F4 A+ Q8 c思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
4 D) O; h! }) i/ @3 ?( N
检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

过程例子：

" {1 j0 N0 {* W' O+ |6 J& x: t

建⽴⼤根堆（代码）：

1 Y. m& Z8 P0 ^( K9 H

0 ~/ B9 T1 T: b// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
* Z7 Q1 `  a3 f# Z# _; T    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
) a) n* w7 u1 N' q* ?        HeadAdjust(A, i, len);
}

// 将以k为根的子树调整为大根堆
# r/ K( Q' H4 M! i+ l/ ivoid 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])       
: g% f: X- W7 T- B3 ^' z            i++;
        if(A[0] >= A)
. f6 j) ~. z- Y# `4 g            break;
        else{
            A[k] = A;                        //将A调整至双亲结点上
( s1 S  w' A! c6 r            k=i;                                        //修改k值，以便继续向下筛选
. ]- B/ ?& A8 F- b0 _2 T+ W4 e        }
    }
    A[k] = A[0]
}

# H+ ?- b0 X# R: D" g- _. k# ]4 N1
  ?( j% {) y, H. U+ V: h5 R0 \2
: a, C, k( k3 q2 w3
4
; e# v& S/ c7 w9 F: {( V5
6
7
8
9
; Q! y8 A0 [7 k. V% I10
11
+ d0 ]9 `1 v8 j$ j12
13
14
15
4 b1 w, n( C0 v& ~# S16
8 ?2 z9 C! G% K: e+ B7 K17
18
0 b. X& X' V; d4 i# l) }) b19
" \' b3 Z8 P6 u" ~' u8 r4 T4 N9 d20
21
9 R6 t% y" X/ ?0 A③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

. _% v% h  |6 q7 [5 S" o( A% B堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

6 b1 `: K8 T. r- p过程：
  r1 @* T7 l3 n# G1 l; a5 _' E5 `3 @
// 交换a和b的值
void swap(int &a, int &b){
! h. p8 s! k1 g' i    int temp = a;
    a = b;
    b = temp;
}
8 R3 g: v; M; \. L/ m
  R- b2 b/ X  C// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
        //初始建立大根堆
# w' f7 V  E% h" s. l: k- a2 s    BuildMaxHeap(A, len);                

    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
    {             
& z1 X+ s2 K& @0 ?6 R; y  v, M6 j        swap(A, A[1]);
8 P/ u* d, m. m+ ~0 E+ e        HeadAdjust(A,1,i-1);
0 L! J) M& c9 \- \    }
}

1
) b* i0 S9 W8 L0 T8 R$ }2
3
4
5
6
7
8
5 C3 W" e- o& Q0 E5 x9
10
11
0 W% a7 }2 H6 T$ W; _# i12
( k# m/ t3 A$ ~) o13
14
15
# n2 W* H1 F% P# ^' {, d16
17
  ?2 E/ C) R+ I" A# L' I) w18
19
时间、空间复杂度
$ u. C  Y/ j8 ^' u# h5 l& \建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
1 q- b6 ]/ c( g$ `' R3 l' n故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
/ W- [. w9 X( K; ^9 m& A
空间复杂度 = O(1)

结论：堆排序是不稳定的
; @" C" {( l0 u& s, E- z
2 K0 S- [. a1 m7 {' F" I
④ 补充：在堆中插⼊新元素
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
# h. K: a# k1 N0 w0 ^- P7 B新元素就这样⼀路“上升”，直到⽆法继续上升为⽌
+ M, L( {7 U- _4 d* b! E* }


⑤ 补充：在堆中删除元素
2 k" a6 m* q: N! N/ u被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌

$ R. V9 b7 s0 t: P- ]
2 A# i" q' z% x" m' h# P  O


4. （稳定）归并排序
" ]) J2 `' \. b. ^! g* K6 @6 l归并：把两个或多个已经有序的序列合并成⼀个
( M+ s4 b. f9 b' g. ]& Y
① 明白什么是“2路”归并？——就是“⼆合⼀”

多路归并：
5 ^5 h! t$ G! g
, P0 m& U0 J0 A; K# \, S5 W
- s, I, v, I0 Q7 \② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

. n) I- b1 \# R' O# U+ ]$ X* S/ PB[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
' c2 }2 C8 T2 Y5 X
③递归进行分治思想【MergeSort(int A[], int low, int high)】
+ U' g1 o( v# @( a. t

# r  H4 ?# Q0 c( G2 ]④ 总实现代码
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
7 c2 G  k: c4 y/ J: D
// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
7 \" D9 R( f# y6 H0 W- e9 nvoid Merge(int A[], int low, int mid, int high){
0 t3 a: F2 D6 @( _. ]    int i,j,k;
8 U) C3 `  P, W    for(k=low; k<=high; k++)
        B[k]=A[k];
+ Y" a; K5 g/ O    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B<=B[j])
& T, ]7 q- d0 G1 t9 d+ B% G8 H            A[k]=B[i++];
5 B! Y, R# F$ @% H' F; Z' B3 q# d        else
+ J% P! W+ r! a$ r            A[k]=B[j++];
    }
    while(i<=mid)
1 p5 i# \; C7 Z9 g) l        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
. p* Q$ i9 p) i$ ^( a}
0 J: M6 ?7 Y4 _, L' v# k: M0 K, X

2 M9 Q% y. z5 `) l/ r. U: h- S// 递归操作（使用了分治法思想）
void MergeSort(int A[], int low, int high){
    if(low<high){
6 _- M. K5 W: Y& C4 S) S        int mid = (low+high)/2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
8 S# \, m0 q- j. n        Merge(A,low,mid,high);     //归并
    }
}
0 v1 m# U/ J( K1 [) r; y1 B
5 }+ w7 A9 B* ^" p1
/ ?7 q3 b- s2 i4 r' l1 @( O7 `! F+ Y: T2
- x3 L: A# }1 F$ V# {3
4
. ~6 }0 z9 D5 t- r5 B8 Y5
2 ?! j9 O9 M/ C" K6 e' K9 N6
7
8
! ~# u; M( F  C* D9 f0 O2 ~9
* ?4 O- p% j% z  |5 k10
11
12
13
14
15
16
17
18
5 T3 W. `. J. q; ?9 T# \0 G" @19
- y5 \% V2 m7 ?% y/ E. T20
, C: N- S) S5 O2 J2 B: m21
22
23
24
25
9 u9 c! Z  Q8 E4 g# m9 |4 N+ c, m26
/ a5 R( z7 m+ C% Z3 e! @$ l2 T27
28
29
30
时间、空间复杂度


+ R9 m0 V: l0 {. D5 t7 H

5. 基数排序
直接看课本的过程图来理解P352

$ D0 T! \4 G+ u; n4 K再看这个例子：


算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
( F% _3 A9 B9 F  y2 p分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
①数据元素的关键字可以方便地拆分为d组，且d较小。
9 }+ }1 m' G! l# T②每组关键字的取值范围不大，即r较小。
1 P; M6 A( `5 O! R8 S* F) `) M6 _③ 数据元素个数n较大。
; d% x) [; P* Y算法效率分析：
& S! g7 @/ c5 V5 d# z; y时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
" ^% t' Y9 c0 A0 c7 S$ p4 [稳定性：稳定。
7 {, l' P+ T& m0 f

* {9 R3 h' T0 w3 s1 \. y! T+ X内部排序算法总结

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

! N2 r/ b0 H2 ^0 [  R% {
+ g' n6 m/ @+ [0 L5 y

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5