数学建模社区-数学中国

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

---

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

! r3 j8 Z; D4 Y- T; O, B  K【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
+ T4 u" V' F% v; g& D文章目录
' A* v4 {# d% S3 T$ `5 E6 t排序
1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
4 W/ F; L, n) E* b* K时间、空间复杂度
7 R) A5 R9 j+ V  |  D/ O" [（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
# U/ G  R0 X: S6 `2 ^  _! @时间、空间复杂度
* j0 l% p# L) Y7 s, U8 n（不稳定）1.3 希尔排序【多次直接插入排序】
时间、空间复杂度
' s, w7 g" C* E2. 交换排序
2.1 (稳定）冒泡排序
: b2 A( F5 e! g- `8 z5 C, h( q时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
* P8 p, a( d3 g0 ]时间、空间复杂度
3.选择排序
+ T+ T; B5 o! h. f3.1 （不稳定）简单选择排序
$ z  \0 Y  L9 ]  d  P时间、空间复杂度
3.2 （不稳定）堆排序
/ R) X4 Z; p) l5 l  X1 I5 A. P6 w① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
% `: ?4 G3 h1 s( K  i+ v3 L时间、空间复杂度
④ 补充：在堆中插⼊新元素
* l' r: ?, B4 `⑤ 补充：在堆中删除元素
4. （稳定）归并排序
8 p$ k9 W0 q! [/ \① 明白什么是“2路”归并？——就是“⼆合⼀”
  ^3 P- ^& w, h② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
: _" t: g! l) j" d% o* d③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
时间、空间复杂度
5. 基数排序
/ e2 E1 w5 V0 j; y2 ^2 ^& ]" M内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
" R2 u! N8 h" Q: O
排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
: ~+ e8 i* j7 `# u, ^- J; r( h
. ?6 l* O6 q/ n4 _3 n4 Z+ {算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。


& T+ o- r  U( n  V# x' o2 Y! R排序算法的分类：
  r3 K8 D$ J$ S) O+ D% _内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
* N) [! {8 T2 l& K外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

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

# L( \% h8 G  o2 M) [/ r
3 z9 T3 ?0 f! {7 B
+ v$ P0 E3 E  E$ I1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
; D7 h' J" r0 x: n7 z( E3 o& p4 R
算法解释：（从小到大）

+ F8 H# |1 ]% U2 N' @+ ~" X- [
算法三个步骤：

先保留要插入的数字
往后移
5 z! ^6 ^2 x. D4 p- A2 O插入元素
" d: w' M6 N& |5 [( y, n5 S
// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
1 r( W) K8 M5 l9 @8 \' Z    for(i=1; i<n; i++)
    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
+ D5 G; L' w. g        if(A<A[i-1])
        {           
            temp=A;  //保留要插入的数字
8 Y1 T+ k: a0 S1 J( t
% N- V# V7 B% o: i+ s: u            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪
# b* ^# g: v% F3 z% \: J
6 `& ?3 m5 D( |0 C1 D. W            A[j+1]=temp;//插入元素
        }
7 ], N( _) s$ \; [3 K* g    }
% G6 q: [+ o4 U}

1
2
% w( r5 S4 x+ I# I( l0 I3
4
8 }' z& x- D" I0 z0 l* Y5
6
# P' n# n* }" B1 x! |" D( }* {7
8
6 n5 S, p. H) u* |" D7 z; [9
10
11
5 r* ^2 B. u+ V: @: u12
13
" E2 Y0 p$ P; y) C% I* ]14
15
. E2 T! H( K. G  Y  t! s+ d& w16
17
用算法再带入这个例子，进行加深理解
0 F+ e* m7 [( \3 m& F% ?; X

5 y2 K5 v  B" f% f2 ~2 U带哨兵：
2 V5 o! f. I/ n1 N
) V% p3 H/ J, P/ w
5 E4 L" {2 T6 {4 P8 }补充：对链表L进行插入排序

void InsertSort(LinkList &L){
    LNode *p=L->next, *pre;
    LNode *r=p->next;
* Q7 k) n! F0 Q: @& x    p->next=NULL;
, K5 k% ]) Z/ ~9 s& k+ j4 ?4 |    p=r;
    while(p!=NULL){
        r=p->next;
1 I8 x& s+ k: o! ]7 k9 v) p/ }& q        pre=L;
% A3 w7 E/ U7 ?" E% H* x% t        while(pre->next!=NULL && pre->next->data<p->data)
, u9 O) `, l0 T9 V) g            pre=pre->next;
        p->next=pre->next;
" y1 M2 ?! k' S# f' s0 S        pre->next=p;
- {4 M2 S1 W" B3 U/ ^5 y, t        p=r;
3 f' c* l$ D$ V1 w1 S/ B) _    }
4 K8 z2 X- J% Q5 m2 l: O- o9 V/ j}
3 t6 J. B% Z1 Q1
. y( k9 x; o8 X! P6 Y% K! U# W2
3
4
5
  @/ {: G' c* ^6
6 _# {" d" l& x$ W7
9 `' L" J; c1 U- C$ ^1 a8
9
3 j: N0 F/ U) o2 X2 n10
5 Q2 w/ W, z# q2 M11
& u6 s' ~: B5 n12
$ u, |, n1 d" O7 d13
; k, W7 q$ u- T6 M14
15
2 P/ Z9 R5 h8 {" m时间、空间复杂度


# j$ F; \6 f: v1 t最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
最好时间复杂度—— O(n)
4 s4 Z4 H" `' I" c  @
4 k( |+ S, i: h. n9 |最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
) B" I; M% F, o4 w3 K8 M第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
! e5 E6 A. F( Z5 N7 f; M…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)

, W# r+ a# d3 `



7 m# j# b7 w- N( b1 A, J: R（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：

- h3 H- f3 o, q2 E& T7 y& s
* [7 r' r4 s  }% X! J- G
* _" Q% X+ \) D, _. C2 `" D. K//对A[]数组中共n个元素进行折半插入排序
! P& q! _/ J' G) B, c: Zvoid InsertSort(int A[], int n)
: O  I2 c# f" D! j5 s! B. K{
    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
    {
; F+ a- V/ F7 c, h5 n        A[0]=A; //存到A[0]
$ Y9 p* J( x9 O8 l+ ^$ g3 _4 x        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
) D1 j& s% N  D- {+ a        while(low<=high){            
" |( n) s- M, m+ ^7 e  x5 r            mid=(low+high)/2;
" ]: o' c1 A6 \8 |            if(A[mid]>A[0])
                high=mid-1;
4 \" v$ N4 f' n6 N            else
                low=mid+1;
6 O! S+ n4 X5 C' m. a        }
6 J' U8 O8 l2 V" P5 D         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
/ ?2 [2 J% T! M; |( K# Z* _2 C            A[j+1]=A[j];

0 z) }9 C3 B8 }( M& I/ Y        A[high+1]=A[0];//插入
  |2 [4 r; u1 {! j, ]    }
}
/ S( P5 u; p1 K- Q9 _, l
1
% t0 ^8 h+ u$ e3 e+ H0 A2
* }+ m4 |) B6 z# T3
4
5
1 j" u1 B! _2 ~! J  V: e/ L7 n6
7
9 Z: v0 b6 |, r& a( ]1 l$ f+ E8 c8
9
10
11
12
2 C( V1 y  r- y  W' V% f: J: i13
% c) A( z% m4 J( |3 I: V: _14
* W  h8 ^+ `2 R, g4 W% c: f15
16
17
4 G3 P* H/ d" B& z, E18
7 c8 h3 m. d% s! j" C1 r19
20
1 A2 G1 ?( v, @21
$ b7 s4 ~3 z4 D) H- d. }22
" |9 a" i) n8 `6 W+ _6 x, R# k: h23
时间、空间复杂度
空间复杂度：O(1)

【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)

; e' k0 y0 [& T/ I
（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

算法思想
' [7 L, F- m/ M( P! R/ c
' t2 e9 M2 T) C+ U/ ]% t希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：
" j& t0 K* q5 x

3 c- l) a4 a* c5 j6 ?0 m5 n; k
代码实现：

; {3 b! W! O* H5 }0 v//从小到大
void shellSort(int* arr, int n)
6 ^2 v  J0 R+ v+ v5 y{
. s9 W0 M/ y9 X        int gap, i, j, temp;
9 `9 H- e. r2 h" L& }$ |' ]        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
/ \2 ]3 i5 S2 b4 x            //**********************************直接插入排序（只是步长改变）**************************************************
# j6 t+ Y) I7 W9 ~8 Y6 |% @            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
                if (arr < arr[i - gap])
; @/ J" R5 U% `) ]' @" Y/ Y8 r+ Z                {
                    temp = arr;
, U- [! M- m; R+ x$ V3 U
                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
- _0 `* O2 c8 c  j- g8 S/ @                        arr[j + gap] = arr[j];

                    arr[j + gap] = temp;//插入进去
                }
" `+ f1 L3 s) W0 {7 t/ [            }
            //************************************************************************************
8 V6 ?/ U3 e& o$ z( C& B4 q        }
6 e7 F( k7 h2 J) z9 m8 D}
. `4 x/ C3 o9 N) M( b
0 u# x" U! ^' }  L, H% V. S1
2
3 I; j; ~3 E4 F: g, R3
4
5
3 I! y1 p3 R5 }* g& U4 O2 R; F4 F6
7 R% q4 s! F. m7 ?3 l" b7
8
. p3 N$ A3 f2 c; I9
10
7 F' f$ h6 @* y# J11
12
- \# a0 }$ _9 f3 D' ]% Y& s13
14
  Z) {" Z) `2 |% t# N1 F# ]; Q15
16
3 N5 C' ^6 C! c$ A) G, r6 }17
2 Y+ }/ h* E0 q" j, o. ~18
19
20
21
! v# W" e0 t$ }$ o8 G: V22
23
24
时间、空间复杂度
空间复杂度：O(1)

- K4 x0 _9 Z4 S0 L  t* r; R时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
8 y) A9 O% @4 L/ E- ^
稳定性：不稳定！
% M. Y; F2 {$ j/ W

) _7 H6 c- F- Z9 b% z/ e
适⽤性：仅适⽤于顺序表，不适⽤于链表

; j. w% u4 ]+ e7 P- ]

2. 交换排序
  L2 @  J/ B- ?% g! B, R0 I8 C$ z2.1 (稳定）冒泡排序
1 D; }" H7 K1 V% b7 ~4 x& g英文:bubble sort     (bubble 动和名词 起泡，冒泡)
* P* z* N: V) ]! T" O, I% [: A从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
  t. S- }" w" m, }4 _2 O* E9 ]4 I
0 x( @5 p. r/ q3 {, L/ m每一轮比较会让一个最大数字沉底或者一个最小数字上浮

% q; t: a2 Z; {( H6 Z9 y这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
# D& }  ?# m$ \) H; X( S) P2 F! b4 v4 g
5 E  u9 Y; j# ?9 I  f7 |4 O实现代码：

//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
- O- T; E7 m6 C, ?2 h{
        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
        {
, @- {1 D2 Q) \: L6 s$ O, L9 O                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
8 t# \% ~# m! I) m+ b1 u# m+ k7 t* a                {
# V' L: P: o6 G! h3 H! S( o% H                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
) {7 n6 j) U6 \( n0 l2 _% y                        {
# k6 t7 z9 Z$ ^# k. m                                //交换两个元素位置
& _% V! p, o/ u7 U5 m                                temp = arr[j];
                                arr[j] = arr[j + 1];
6 K/ J! h! H9 s" o& h                                arr[j + 1] = temp;
                        }
! V, X5 f. x4 R) N. l+ e/ e                }
7 j. @; s, o4 t: l, c/ Y6 o3 c% v        }
0 j! A0 A3 o4 Z9 W, p& c0 _}
: z+ o7 q+ k" N5 R4 z& F4 v$ ]
1
' l' A4 L5 b, Y2
3
4
7 X; p3 D/ d7 Y5 b+ v# v5
' U7 U* `2 H2 p# n4 ?6
7
8
9
10
11
/ o" y% [+ W9 z1 [- A& O1 s12
13
( ]% a8 _$ h) @0 W) s14
15
+ ?- e) |8 d: w$ m! w16
17
18
9 g' J) Y9 A% j: {19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

" k% U# V* c6 m; d7 U* z1 B& V# K/ H, W//从小到大：
/ P& [- R* M* ?) [void bubble_sort(int arr[], int len)
{
. ~* a" ~2 x. p  q- ]3 e6 U4 R        int temp;
        bool flag;
1 m. e. L2 u. ~4 `4 q8 ]' ]  D        for (int i = 0; i < len - 1; ++i)
        {
            //表示本趟冒泡是否发生交换的标志
                flag=false;
               
) Y- t4 u) u" C( C* w9 G( U6 `6 Y- ^$ ]                for (int j = 0; j < len - 1 - i; ++j)
                {
9 D- r# R5 Z  X                        if (arr[j] > arr[j + 1])//稳定的原因
, J& ^% O9 l& d& T6 z0 f' k                        {
* v. ^% I4 Q- i2 v9 X                                temp = arr[j];
' d$ ]4 m8 k% r                                arr[j] = arr[j + 1];
; E& F# i/ v2 _' V                                arr[j + 1] = temp;
                                //有发生交换
+ l3 a; X& ~6 k3 v4 i                                flag=true;
3 ]9 M# @; x0 j+ S0 P* w1 W9 n                        }
                }//for
               
                //本趟遍历后没有发生交换，说明表已经有序
4 l2 {/ C0 r4 I3 t                if(flag==false)return;【1】
        }//for
}
) m1 ]5 ?) _. D$ S, K/ E
1
# K7 x  v( j$ [# l" ]. ^* c0 Z2
; a' `7 r7 ^5 k! g9 T4 `5 x3
" v/ k+ M/ x# ]8 V) l4
5
6
7
8 F* a! g" I7 e# G: b8
% E; V  {) R4 [& J9
10
) l- X% t1 f  [. j/ u  T1 L11
) c; \' s- _; d+ O+ T7 a1 z12
13
- L! l4 Z# y$ V; y  Q14
7 h. ~: C* T& }6 m, ~5 ^5 V$ s' W15
16
! {4 B1 I7 l5 L. ^& Y3 g6 ^0 Q17
; T# `# R. g" I" O; Z18
" S# c$ x2 Y; [  _- U" i19
7 P8 _( m3 M0 }5 X! S20
21
3 @( B& u% U/ ^2 R8 i22
23
24
2 W5 l8 Q' n- f& b) }25
26
- n4 K5 f4 h8 P& ]时间、空间复杂度

3 N* z$ ^+ S, {6 [适用性：冒泡排序可以用于顺序表、链表
+ `( m+ [5 n& j3 j

! g; p$ g: {% h  z$ V5 F; P

2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
) ~0 I# I" d7 B3 k! b2 I5 m+ M+ ~算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
6 Q; ]8 k# Q4 c1 n8 D' j通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

# C3 T/ R8 x0 f/ C然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
, @7 ~* |8 c+ H) ^
划分的过程：
/ S: C5 s. C) g6 I
初始状态：取首元素为pivot，定义low，high指针
1 f! C& v# D( j( w+ d& d( y
. ]+ _1 u2 C8 U首元素为49
4 i; w3 u6 \& F- m; u7 N+ thigh指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置
- u4 H3 V; m% h' r  x' V




4 S9 t# {% q! x$ p// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
        //取首元素为pivot
) |% ]2 K! T' K' k( d" Q2 {8 u: p2 {    int pivot = A[low];

" x1 {* ?# M* S    while(low<high)
    {
            //先是high开始向左移动
. S3 |& G* a, X; v: w! {3 O/ f; T: R0 K        while(low<high && A[high]>=pivot)
            --high;
5 Y7 [. l# r$ l0 [' m        A[low] = A[high];
5 u% D: l' N/ b* J. p
6 Y6 Q3 X# Y. x% w5 o6 ^0 _        //随后low向右移动
        while(low<high && A[low]<=pivot)
            ++low;
  c" E8 J. L/ ?# \2 X        A[high] = A[low];
8 y2 B: {' e6 T, D$ ]    }
4 T. y# f+ B1 \( M- m) |
3 M( q8 x- p& P    //low=high的位置，即pivot放在的位置
! [' l+ K9 j) h* H! f    A[low] = pivot;
/ j2 o' L- [: t1 |' K8 N$ \' j
    return low;
}

6 D( K8 ?* l  H# r* S// 对A[]数组的low到high进行快速排序
# D1 Z' Q* u* m8 s  W' x  jvoid QuickSort(int A[], int low, int high){
    if(low<high){
        int pivotpos = Partition(A, low, high);  //划分
1 O! F: |* s( m+ P- w        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
3 ?% J$ ~3 ?& i  D4 D' S% W5 s    }
% w9 n9 U( B4 k9 K5 S/ S/ e}
0 U5 C+ d5 u* Q
  ^* z- M0 X% {! ~  l1
2
3
6 s3 C( b$ m3 s& _+ O4
5
+ {7 P$ @0 g' E6 e8 y' O, B! ], o6
4 c2 J- p! o+ X+ G7
6 f, P3 n/ R, B" n" K8
! ^/ `$ ]$ j- J4 w( A9
7 o% q. ^8 j2 p: L  e- n10
  B' v. s% c1 q- z% @/ P$ k) Y11
# c4 s3 L3 [, X: G9 L8 c% t12
13
14
+ }" A: @6 N' f: W# H15
16
' e& H$ U: O2 Y. u17
18
19
+ Y( @; i9 K% ?/ m0 f) V3 L4 |20
. W! `+ ~, k' T  `4 Y/ Y21
" o$ ?3 S5 v/ s& _$ q6 d22
: A7 D0 S6 }; x  X23
& q* p, F6 A, ~' s& i* Q24
25
26
27
  D8 B6 L4 T! a) ?% w28
* O2 `% [7 q/ X9 t: n29
30
31
- J$ M# V* j% R8 O32
) T$ f( S* D; s: n( E时间、空间复杂度
% T6 \: E7 k$ o

把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
' Z. Y5 q3 }# p& ^! I
n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n
: \0 j/ N, E9 ?0 ~: L
时间复杂度=O(n*递归层数)
7 x  A2 {( b, Q最好时间复杂度=O(n * log2n)
/ B: e: d4 H6 k2 F最坏时间复杂度=O(n2)
# E4 {  p7 [( J& k$ E平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

2 `1 ~3 E  @+ b# [1 i. a2 p空间复杂度=O(递归层数)
* x9 `* i6 Y# ^" g. y. j+ J3 O, z最好空间复杂度=O(log2n)
- W1 \8 H  U% N- s$ ]最坏空间复杂度=O(n)
+ i. \' y  Z, }' S0 h9 f
8 M6 K$ F- \$ H3 A* P. e& ]' I最坏的情况
9 s4 p, T( e$ c4 e$ h& e


0 S$ B2 B, G  F6 f8 k. p/ q: l⽐较好的情况
( Y3 Z0 H) q  D+ `* P& Z
0 r0 M3 V9 t% `+ `, ?+ H1 m& g2 u7 c0 `

6 M+ u. E' _8 y- E不稳定的原因：

5 E$ S; N) @! t- b; U

" d7 {2 r" L* \0 m

3.选择排序
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

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



// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
, m. h5 H" Q, ~7 x' V    b = temp;
}

// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
6 h& z1 W% b1 {{
+ s( X6 m0 K" r( l7 V/ N        //一共进行n-1趟，i指向待排序序列中第一个元素
) [8 J* ^% P/ i' g- B6 r+ a1 I9 E    for(int i=0; i<n-1; i++)
- x) Q9 Z" ~) i. I2 J. G6 a! p    {                 
        int min = i;
# C& `& w/ r. n8 m) {        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
2 N0 G6 q' i& B( P/ R7 @& u            if(A[j]<A[min])
                min = j;
        }
8 m7 q7 b! |. B7 V9 @0 j# V7 u        if(min!=i)                     
            swap(A, A[min]);
! G& @  J+ k: f; Q2 T$ [    }
}
. U9 T+ `+ F. a: {
1
) L  q3 q4 i4 d& Z1 I# p2
3
; f9 N7 |/ X8 V7 v8 Q9 T9 C* g4
$ F1 X  y, g+ V; w, u5
9 W! B7 }+ g) Z! n  b3 d' L6
. q( p' _" C. J  _7
8
$ Z3 r  A2 \. \. l( @' s% y9
/ J" a: ^9 w6 a9 o: b0 n- @10
  P/ Y- m$ s7 b$ @8 j11
12
; N# z8 a4 S6 r% |; T8 w2 q6 d13
* E, u3 O6 [) [. j" B# q14
15
2 S+ H( m3 _4 r% S$ q9 e3 ]16
17
18
6 h' d! ?4 u+ y  Q19
, Z% T" D1 e5 _( l% n4 G20
1 I5 r3 t0 F. M5 g$ L21
22
6 A& Y! W9 c) E补充：对链表进行简单选择排序
) V2 Z* q+ _  x6 ]
void selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
/ w* Z; r* ]' L    while(h!=NULL){
        p=s=h; q=r=NULL;
$ }, I) L$ A4 e6 G+ _        while(p!=NULL){
            if(p->data>s->data){
7 B2 h0 c& q* N# V                s=p; r=q;
            }
            q=p; p=p->next;
+ s+ Y: l1 [  j$ [7 I        }
9 m% n. U& g( x2 @( s# d6 O        if(s==h)
            h=h->next;
$ j. N* [0 D# A& }        else
! k( Q" M% h* n. M0 M            r->next=s->next;
2 N3 E- Y& o6 }& \7 `        s->next=L; L=s;
    }
}

- x: J" P; _/ o0 ?- a, g8 ]) {1
9 U$ a5 x6 {0 }. K" t4 t" B2
3
4
& _! m9 q9 H/ W- C5
' G3 h' d; S+ e0 r6
7 e9 ^4 r; t; `6 F1 g7
8
. P; t/ o( Y) g8 |9
10
7 P  r+ C, [3 w" R+ `6 ^3 Q11
12
. h; v- m& V1 H  P% ^( M+ y13
5 W3 b/ h% F7 j- I) e8 f( b: Y14
15
  q1 ]8 C9 [  _& D5 }3 R( i16
17
- s9 t' Y' y- q18
时间、空间复杂度

5 C1 Z+ E4 X  {

! i! i+ V3 H( I2 C2 F9 Y
适用性：适用于顺序存储和链式存储的线性表。
( b, f7 z( C/ M3 j
3 K4 ^! M7 }* |3 r- v: p- g! C

3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
- M) g" P; f6 P: c8 }
3 n# w  z* e/ _# e9 O7 F
8 b3 E& h% x' `0 i
即：
若满⾜：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）—— ⼩根堆（⼩顶堆）
& [0 z8 J8 u" Z: k! B* K8 K( J
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
  l* B/ g0 [4 z; ]- a$ G( z" j思路：
# r) W/ X- V' P5 M) r把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
, P+ C' q; r6 Z7 ?
# l  D2 G6 m. w# c  k' P在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换
. u  R3 h  d3 Z: s
过程例子：
/ ^; [; e' s0 {& |' {* o* u* b" X

/ X3 H- w! Z. K# Y7 f
1 e7 \8 [* e3 c& w, i- h建⽴⼤根堆（代码）：
; l& T7 v1 b9 ~/ x
4 {, B& b# a8 d2 b1 ^" q
% C, j" e8 x- d' V; u1 ]3 d$ V
: k$ j8 k4 @+ _5 H+ T# L  k7 u$ w" ~// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
8 }! _& r: B% G- d  {: `' X& }  V9 w* H}
6 K2 O5 ~$ J# G2 [  }- F
+ G# A1 L, v* F9 a// 将以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++;
# Q3 T4 a; x) F  S; D" _        if(A[0] >= A)
$ R, @2 p; {2 m: R% |            break;
: L1 Z. F0 a* d% U0 E* @        else{
            A[k] = A;                        //将A调整至双亲结点上
7 M. a6 h! J& S. W) u: }0 o            k=i;                                        //修改k值，以便继续向下筛选
        }
# b+ N! N2 r* s# W( z( H' y    }
    A[k] = A[0]
% B: [4 i: T/ D. N}
2 t" T6 A3 ~$ Q  {1 a( `
. ?& X+ V6 T4 B" S, ^+ |0 i/ }% R1
1 q& K: g6 x8 I% k$ I+ u7 w2
* X( f; y% d8 r2 F4 [0 J3 H8 j8 D3
4
6 \4 C! W" H; c, ?; V5
% k3 W9 H) ?; A2 s% {5 T. ~6
8 S- G$ p7 G* T7 D7
8 J& N- u* `- x5 l* r8
0 w8 C) P4 h6 ~9 z% ^3 ]9 d  @9
" z; M& l: b0 X7 t# @* E10
8 z; A% o+ Y- F% r! l, V! \- G/ l11
12
13
9 U8 C5 N, y. M8 ?14
15
16
17
2 o$ v  v& B8 H1 O$ K: e# E18
: i+ N5 ]9 s; {5 N) E19
/ N/ y7 }' t% d! p( C20
# n, c+ ]) Q7 w& \) F' N" m6 L21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
: R7 |0 O% ^# k5 L, j8 Z2 s选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

: z: W; f; ~6 l" h+ V. [, _堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

过程：
1 X9 X4 {5 m: q) W. d  d
// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
* v, V  y" I4 j& j  q    a = b;
9 ~! z( O# E) X5 @2 b  l. f& T9 G* f    b = temp;
}

9 y% ~& W+ ~3 }/ W4 s// 对长为len的数组A[]进行堆排序
0 e1 H2 b' u5 c! s# Evoid HeapSort(int A[], int len){
        //初始建立大根堆
0 o* X( i) b' _! t: X2 B    BuildMaxHeap(A, len);                
; l" C2 P. b7 u7 @
    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
2 V- y3 k! b  E2 i2 k# k    {             
4 v) N, m: Q" e7 ^6 l# T/ q        swap(A, A[1]);
        HeadAdjust(A,1,i-1);
    }
; _* c" n3 \& `9 R2 n5 b+ K: @) q}
4 _; p+ W5 N" b: ~+ Z# G
6 {7 }; R1 J: Q* n8 ~" E/ C2 ?1
2
3
; W: Y6 _4 v9 j9 M4
5
# z; B$ V( H! F) c2 h* M  {6
, d/ V! \. Z2 [7
6 f5 A: C5 w! ]1 Q8
9
10
* ?8 D! S, I) a0 ~$ c2 g11
12
13
8 k/ j, K& ]- E6 g6 k14
3 `5 V' S5 F, Z, d, ]+ M1 W15
. ]. Z, \# Z* E/ D( O9 g& \16
: f; F3 M3 ^7 s" V1 c" A( `17
' k/ c9 M- h3 U- L# U18
* G+ t. l* z4 c5 Y  k; u19
1 L0 P% ^5 Z# i5 S时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
& h& o7 F3 O0 ~. o
空间复杂度 = O(1)
7 C9 A/ _* W5 _$ Z* T# s; d) P9 Q
+ z! T' F3 T& B结论：堆排序是不稳定的
+ T2 D  Y3 ]  X- v* N- D7 A; \
+ K; n/ M% H3 H  B# [( Y
7 n/ A4 X; H. \4 n: `* X④ 补充：在堆中插⼊新元素
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
0 ^9 |1 H# b* H1 a新元素就这样⼀路“上升”，直到⽆法继续上升为⽌

5 x7 l0 n+ C  t; f

$ l9 }4 \2 a% @- V) \' X9 u( S0 F⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
: N, w0 h5 X: ^0 X, m

! l( R, z7 d) M2 y
. c! j. ~$ I# G1 u2 v: F* l" M

+ T: G* h; X+ V3 ^4 Q( [7 x" P4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个

) I8 W+ C: m% ]- M! C① 明白什么是“2路”归并？——就是“⼆合⼀”

多路归并：
3 m% {5 Y$ B3 \/ U( m  p4 ~

② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
) S9 n2 E, }! `: m1 ~2 H
B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
5 c1 @, [: V6 D8 {+ j; b
3 i( O1 s9 o3 |③递归进行分治思想【MergeSort(int A[], int low, int high)】


④ 总实现代码
// 辅助数组B
3 K- @7 g. B6 G* L5 Nint *B=(int *)malloc(n*sizeof(int));
) P8 @. c$ c" e) A+ z/ L) Z
# a" F' F  Q- z6 o1 C// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
    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++){
& K$ {7 ~5 X, Y+ L& t3 n+ B        if(B<=B[j])
            A[k]=B[i++];
        else
            A[k]=B[j++];
    }
    while(i<=mid)
4 w( K1 n3 K- I        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
" a0 z, o8 r2 b% t}

! T. N6 l* U- t$ z0 S! ^
& r6 n4 S* P+ e& M: Q0 A// 递归操作（使用了分治法思想）
/ X, L7 u2 x' ^4 L+ b! dvoid MergeSort(int A[], int low, int high){
; u; b* f7 z; M& |. S$ a    if(low<high){
" d) G/ K2 i( r" ~; T$ l1 [/ a, M$ Q        int mid = (low+high)/2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
, m* O, ?3 U1 m$ Y3 ?        Merge(A,low,mid,high);     //归并
    }
}

1
2
& V' g3 S7 }" A2 f3
4
( L3 z0 d& j7 x5
6
7
1 N% x% w; Z1 O" Y8
9
10
11
5 l8 A* w' f% c2 k0 k12
2 R' p" i% Q4 S# ?8 g! ]8 Y" z13
5 q2 t4 V$ Q- q1 @3 W14
7 X/ @7 ~" v" \+ k3 h15
# r9 H3 u  m- t8 [, u  N# K16
3 r$ t+ `# \1 A% t* u- F17
18
19
2 I5 \! p+ w' G4 ?9 n) H20
# b& d- x( v* o; r- g9 S21
" ^( G# e( C9 d$ Z22
23
4 I9 h6 ^3 z" n24
& Q' n7 w, J9 _& u3 J, x' g7 U, h25
26
27
1 {1 T7 X# o* ]' S+ ?28
29
5 L0 g* W! w& P$ k30
) M2 H: @1 m+ }8 X# F" X时间、空间复杂度
2 X8 W7 o. c) J- F
; F. d7 o# i3 ?. [
+ B6 E! z7 ~' a. R# B3 g+ @7 F0 B2 w
( x, W1 @/ d! \! T% R9 j
, q$ M7 x7 S, B- n' X/ B& g5. 基数排序
直接看课本的过程图来理解P352

6 {- I. F( R" p( Y; ~再看这个例子：
: R- o2 G7 N' t
1 m% }- Q3 I# Z
, W7 L: w6 t( u! n" _, p3 p算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
# |" P1 n% N6 M3 ~  D4 P基数排序擅长处理的问题：
①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。
算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
  U- J  W  H  g2 a. \' o空间复杂度： O( r ) ，其中r为辅助队列数量。
稳定性：稳定。
- E( i1 p0 G$ f* h7 V4 `0 W. c
3 H* g% t& g; {/ f
' [4 I- [8 [( q8 L# Q) O1 G内部排序算法总结

————————————————
" \3 B: Z1 j% n+ y! ?+ s2 ?& Y0 S版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 b5 n. c5 k3 n8 j* a) a6 `# o6 {原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969

---

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

Powered by Discuz! X2.5