查看: 3321|回复: 0

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

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2022-9-4 17:18 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
排序
1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
时间、空间复杂度
2. 交换排序
2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
时间、空间复杂度
5. 基数排序
内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

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

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

排序算法的分类：
内部排序：排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

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

1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素插入到已经排好序的有序数据中从而得到一个新的、个数加一的有序数据

算法解释：（从小到大）

算法三个步骤：

先保留要插入的数字
往后移
插入元素

// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
int i,j,temp;
for(i=1; i<n; i++)
{
//如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
0 O# Q* D6 x- V! h; c$ J& d       if(A<A[i-1])
$ M7 |9 g8 Q( d: X5 `1 z% i       { " B- P* C' Y2 X8 t' U
         temp=A;  //保留要插入的数字
, U% m! U; p( z0 S- E7 G# y8 f9 y' ]& B$ D4 M* |8 H/ @
         for(j=i-1; j>=0 && A[j]>temp; --j)
  D( G5 ^" r  t. b8 s; n  Z             A[j+1]=A[j]; //所有大于temp的元素都向后挪6 @, [7 X* h# ]
" F! k" A/ v3 N5 f4 E; V
         A[j+1]=temp;//插入元素
7 j; \! Q, }1 G. S! r3 N3 N6 A3 _       }' @, q9 h8 E- R5 S1 h. [
}' }; ]! R2 G; \
}- ]9 h9 J* J# G
% I9 E2 w" t  U$ `
1
5 k' k6 D  z1 x" }0 B" |2) V+ U3 a* J9 A! f+ i& W6 [
3) J' k" ~' ^" c: [) @
4
& n& P* y7 c9 m5
; s' B# O- e; h4 y1 T5 D6
6 y9 O( F0 z3 s9 _- {7
2 k3 D6 N4 A5 v2 D9 n3 b. J5 F8
# G& F9 @2 v+ p+ Y9% W$ Q( F' ^5 {( |1 M! }
10' E: \8 r5 H& D
11
' [1 J. w: \; y! E12' |0 b" s( T" `* ?
13
  h. g( V1 D0 Q, ^14
4 R2 i6 g! F1 x+ D15
/ ^4 k( E$ J% Q+ g, o- j167 N" M/ t% d/ W1 N+ P! Z
17
) L0 g; H6 \0 ?8 U2 J1 n用算法再带入这个例子，进行加深理解
" e& j. ?: Q8 ^, R4 R
9 h: d- f2 q) R! G+ s! W9 _# Z- a6 L; X( A( z8 B
带哨兵：; [' E- W  P7 J
2 v( j+ [2 A- H( X" r. g* ]
. @( z  a, `& B- q" `
补充：对链表L进行插入排序
8 n  C; ~3 M% G5 g8 [+ U& Z
, Z! L6 K: ~7 h+ U. p+ svoid InsertSort(LinkList &L){2 g& @" K/ E: j. A# Q9 Q) m
LNode *p=L->next, *pre;
+ p. u# N$ |7 l; Y: I' w- h LNode *r=p->next;1 y, F* ^) C: i2 s1 u: o
p->next=NULL;: N" l/ @+ f/ g8 J2 f3 u
p=r;+ I: T( |" m0 P9 R7 i
while(p!=NULL){
( V  J) ]( t# N8 L$ ]& }( H3 W       r=p->next;
" o; h6 M2 U! h! ~  p. x8 C       pre=L;. S5 ]+ ~+ X1 w/ B, N9 K( Y; L+ t
      while(pre->next!=NULL && pre->next->data<p->data)
) ]1 \5 S$ P1 w, a; Z          pre=pre->next;1 I1 w- D* Q6 M" k  e  ?8 |6 X
      p->next=pre->next;* T" y( ~+ n* n
      pre->next=p;/ A) x' k, N% n/ |
      p=r;
}. M) r8 S! t# W! [" N
}
! N8 o9 ~8 V7 i) W: Z18 M" O, |! g9 n+ n# I1 H
2; N* R" E  W+ a! Y" l
3
% O4 ^' A! B. \# t4# [: |) f/ l9 }" S/ K8 g) j- B) p
5! b- p" s3 g- k3 m
6! {$ N  \& ?! |& T' s, @
7
9 N, o& Z- l0 U+ i) X$ A0 d8 v8
3 Z7 d: [( N- \4 R% ~9
/ I2 ^8 q# A6 ^10
, d& a. E, M% H) f% v1 p11
5 X0 s8 H' Z, x+ j& g5 F, Y124 P: K0 [  q, {8 v
13
' d  D. C4 T9 c9 z14
4 @6 m3 {% i; u: e" O15
) n& K8 H8 o; R) `- [" b时间、空间复杂度
0 j9 M3 c9 o# t9 \8 o. s$ C% `$ |3 v' }* {# ~/ ^' d: T& [6 S. X, S
3 K  @, N$ r! m" S0 ^8 Z! x
最好情况：共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
3 }% M' N! N; D% \最好时间复杂度—— O(n)
( x/ U4 r5 o" K% w- g& B0 J* L7 x; D7 {. P( H/ K
最坏情况：【感觉第1趟：对⽐关键字2次，移动元素1次？】
0 B: {: m9 h+ h7 P* w第1趟：对⽐关键字2次，移动元素3次
4 r8 R9 P* R+ L; h4 c+ n3 w第2趟：对⽐关键字3次，移动元素4次& k; o2 ^1 M  b4 g! U6 D
…. ^0 Z. r1 B/ y  c, d
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次9 E( X( W+ D1 u) m; V: L
最坏时间复杂度——O(n2)5 P+ M* {5 N) c5 P
9 e. r. J6 F) A1 S1 d
& a9 N/ L  u& m, b$ t
5 N7 Z" z: `4 \1 B2 `

/ v" K+ J2 R6 L
: S+ c) v- ]" z3 w+ u& m（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】3 Z7 G  ^  D; @
过程：
! b" \2 s# i( l  f/ R% z! o
) m3 `) R7 T% J/ o" v, g
( \% W4 C' `, g3 |+ I
% a& U: y4 d% ^. N//对A[]数组中共n个元素进行折半插入排序
4 B/ H2 J# ~5 p6 u+ `void InsertSort(int A[], int n)  x5 B4 }# i$ l" X& l8 f# j, T9 l
{ - i) N: D" `* n  q
int i,j,low,high,mid;
% ]0 }% ^- V; }% Q1 U: b7 Y for(i=2; i<=n; i++)
- u4 L+ ?& t, C7 x' f {
/ c" v+ V2 K2 `$ b9 r9 e  Z       A[0]=A; //存到A[0]
8 B( a2 ?4 {- _! c       //-----------------折半查找【代码一样】---------------------------' R7 O* K2 C  j: Q/ d0 Z
      low=1; high=i-1;
, r. [# Q, D) U+ @: N9 s2 v. k       while(low<=high){          : Z" N6 K; B: y$ b# A& w5 K: S3 T
         mid=(low+high)/2;
6 o  t' p, `! R8 D# o/ t8 h          if(A[mid]>A[0])
' @1 p0 {* I/ X9 @' M3 A1 }             high=mid-1;4 q0 d2 p" \1 X7 `+ K) k
         else
5 u% F  ?" H# P" z: L9 U             low=mid+1;
/ X  M) R' N2 e& T9 @       }
4 W7 K* ?; f+ m5 X       //--------------------------------------------( M) r0 N% c+ ~; ]! _; i% ]
      for(j=i-1; j>high+1; --j)//右移
- O: K2 o0 @: `0 F          A[j+1]=A[j];$ ?, h4 P6 Y$ d, m( N

9 X# u( {/ Q/ B4 ~5 i  s/ y       A[high+1]=A[0];//插入
' Q9 ^7 d! g) H  A/ \ }2 p5 E( S- t+ p* a1 Z: G
}
5 ?. }" z8 ^  V- a
  H: D8 m) m* `: l% _% N: `1; t. C0 w6 }* M, |' }# ]1 h; Q: j
2- z" y6 N" Y7 R2 Q6 Z8 y
3  D5 {( b4 \% u3 r: z1 N7 p
4
' y0 S2 R* Z* e* _% ^53 h. i: \# e1 ]" [+ R
6; ^$ b. }# [; O+ h$ P1 R
7; I" K9 f1 W# ~3 l
8
  x/ z; s0 q/ c/ m3 x0 k6 |! ~9
- Z& ~1 H' F2 P) {10
- \8 J$ S. X8 F' Z( e11
/ z/ \+ U7 d9 G5 T12
* e( l- J. v! i2 N2 z, Y+ ^% t13; R5 h, ]2 }6 ^5 c6 E  X) r1 B% n
14
. _) a1 C" T2 d  U6 x) }$ t158 y: z4 l1 r9 [/ Y  F8 R' D  ?+ I
164 D& m  d  d0 r$ d7 \% m
17
' q4 R8 r. c6 S# F4 a# ?18# V4 Y, q* Z; Y1 E. T* ^
19
$ Z6 _) K) T/ G/ J1 ^20
4 n1 f6 v' v% [7 F. j3 g21( I, j3 f( F# b
22  n- _# T: ]4 @+ O: `8 d
23
% T2 ]0 v9 W5 X% n7 }4 F时间、空间复杂度
$ ~1 ~" o! B  m' k& n% [空间复杂度：O(1)
6 q; }) ?' W: q7 U6 B+ Z" |3 M1 [0 O1 r) l& k; Z) w
【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
, w! X$ v+ y( X4 w; c
, Y* d; I' X# }( P3 f
" j8 {% C8 K: {  }, w（不稳定）1.3 希尔排序【多次直接插入排序】* M, X0 V1 h6 q4 U
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
2 |2 K7 ~! C  e" Z) I2 W8 Y8 R/ O% G/ d( y, Y
算法思想
! Y  Q; i5 D2 t" ^2 z. e
+ q' n7 c. S* J9 l0 n6 I希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；+ M$ `' [2 F6 {" [9 Q# z/ W: j
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
% D. Q# ?9 t. Z. w5 T0 Q! ]图解：
; _# S1 u7 T8 l
6 i# J& o$ M# q# c( e, i7 x" m! C' ?, j5 R/ L
3 S) ?- p" U9 k& Q; t
代码实现：
  ^2 r% o) ?7 q- k6 ]4 Y1 ]0 j" X8 J- o$ b
//从小到大
' g  `7 u' b6 v% h7 [% y- w  zvoid shellSort(int* arr, int n)# X2 I& L, J2 a! d
{
3 M6 v# h* [1 S: n$ o8 G- I+ p6 W' a       int gap, i, j, temp;4 \1 L) J: `- l% ]
      //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
2 q8 e) ?+ }) R4 \4 }       for (gap = n / 2; gap >= 1; gap = gap / 2) . j4 K# t4 r6 f6 P3 o0 j6 N% F
      {) \& c1 Y' Q2 l2 A6 a2 V% D) `
         //**********************************直接插入排序（只是步长改变）**************************************************
9 k' X$ ?3 D* I4 p. |          for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个7 ^" R* i3 Q3 g- e
         {  n: g3 j+ }4 `. f0 d" v: m
            if (arr < arr[i - gap]), C6 N* _3 o+ b& }% x
            {3 }5 C8 Z4 B- X9 q; X/ S$ }6 B6 z
                  temp = arr;, _; \$ y) H9 P- X% _

( z2 Z6 ~1 Y" Q! l, V* m                   //后移: T3 ]8 T# O: C$ v1 m
                  for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
: s3 g" G0 Q3 D- T! U1 t3 j6 h                      arr[j + gap] = arr[j];& ~0 J" Q: x3 O+ _# c

3 Y7 y( d; t( H7 R: O                   arr[j + gap] = temp;//插入进去
  D. a3 @( Q& y; ^             }# e# l9 S3 e4 C" E! @; l' Y/ p
         }' r: r* T" n5 C+ I# |' F
         //************************************************************************************1 ^* d5 p- ~% L) `* y, F$ {3 ~* T
      }* w  ^7 n# @9 l$ B7 R6 L! V
}
6 h% @1 A- A1 j/ ?0 X4 v6 c- S( i) g* S1 B5 r% ~$ j
1
4 W/ w/ Q6 \% ~  E2
" Q3 g( Z, i' n. _3 O. ^# x38 n# p2 M* `0 V8 ^
40 m: |! X- H) @& Q
5
7 @8 @$ W! q  O* H4 n# C, b6
# Q$ x0 F; f; A4 Y* r1 _' G7
( g: g& J% p) g" M8
' \. v4 g8 y& s* S& x. {99 j, l" [" u. m  i) m
10
$ E  c0 A9 X% b. H7 U9 G2 \11( p7 Y- k  J! \% a! V3 f, \' \5 Y
12
& e  d3 U0 x- e) W* d8 K& o13
& n" e7 z9 `5 W" Z14% _2 U. ]4 R3 E3 U4 R' E
15: S9 A6 o/ I* n
160 f9 `5 T" c% ]
17; ^* D( {1 t6 C, B
18
- ~7 l" c- ?7 c- o+ u' g, t8 p+ t19
- W9 p1 C8 y) I* a9 w205 ~& c: C% C6 r* b$ f- |
21* y1 q* j6 S' D7 J1 [
229 P! {" ^3 \; K: S8 y9 u
232 {- e3 Y) M% q3 y+ z
24
6 H# I' W3 [. F. ]' H时间、空间复杂度. `' S6 W1 p" [( C! ~/ I
空间复杂度：O(1)4 {3 D. h1 z) ^$ k( W4 |- A

( p$ G4 }4 O1 ^时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)& N8 _9 |+ v' j# C! |8 \& g5 p# o; ]

& k% P6 H8 w7 O6 n* u$ `稳定性：不稳定！( C! t" j# K$ A2 a
4 _/ Q* Q0 g# x

; G/ U' I# X" Q9 j0 j
, ~9 I( X7 c2 K% K; }- E适⽤性：仅适⽤于顺序表，不适⽤于链表
; B2 R7 I% P+ A6 w
: X  Q) j, q7 E- |8 ]: Q' x0 g' @" B5 H2 I
# |  ]4 ]# a; n$ W6 j; j$ x1 H
2. 交换排序" J. V4 z% v) s1 m5 T
2.1 (稳定）冒泡排序: \4 o) H! A6 t. [9 S, N# n5 t
英文:bubble sort    (bubble 动和名词起泡，冒泡)
% G% f% P- s3 F6 L/ s4 U+ p2 T% }从头到尾相邻的两个元素进行比较大小顺序不满足就交换两个元素位置# C, ]2 x& d! [% l7 A5 [( j
8 V* }8 k# {$ L& R7 i$ \
每一轮比较会让一个最大数字沉底或者一个最小数字上浮5 r2 B, U" V+ M$ I5 L8 x

3 X( n' }7 h) o( w* L9 V# [$ P- p这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。5 R+ Q2 \) @3 R4 o

! S) I9 o! d8 n2 I; N5 k% Y实现代码：4 c/ z* g* h, E6 x( N0 t1 L$ J
8 Y6 q7 v9 Z) O! X8 |* C
//从小到大：
# \5 J9 s( \; k7 Z+ z: fvoid bubble_sort(int arr[], int len)//冒泡排序int*arr
6 ?, \/ Z2 w- p7 Z- `  ?{
. C, Q& j! I8 l5 Q/ \' ~( J int temp;! U+ o. v' a' A- H4 P
for (int i = 0; i < len - 1; ++i)//循环比较次数
7 {; h+ q. p% R8 S {% g! s; J! O/ y9 ]. e
//for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮1 u1 V8 L& b: n
for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化 ! j1 b3 z- E: v7 w2 r$ m! {
{% i9 ?3 v* @$ Y1 Y, e3 [- [* c
if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
. ]7 B* f5 L# E' I$ O! Z {4 [- A# f7 G& @& `' H5 z% G8 e+ D( H, C
//交换两个元素位置
; P' O6 u6 [' z& p temp = arr[j];
' A( Z& y4 W7 E  f7 v6 ~ arr[j] = arr[j + 1];% \0 `: B; _: o* Y
arr[j + 1] = temp;
' F; g: L3 _3 ^0 \8 P# K- ] }7 o6 P, n: ^3 T, S9 y. `# V9 c
}% k5 g' W3 f/ O5 N2 A) y
}
; [7 w7 g! J/ q8 E7 s) M}
# R3 f5 S2 E& v, P7 J0 _+ Q  {; c$ M& V% b/ ^$ N/ n  L
14 P: H4 \1 [/ G! t; H0 v5 Q7 G$ r
2
2 F+ o( ^4 u% t; N' m9 B5 R3
" e  s: [& Y- Y8 k2 I4% m8 o5 I: O- m0 P9 n1 H
5
$ M# V5 V4 _- T% ^4 \- `5 T- C, W6
5 E+ Q1 f0 ]4 v4 `8 R' e7
$ t; n5 `5 \. u3 a8$ a2 S8 e$ x' g5 ?% _3 J
9- A/ |2 ^8 g/ y* ^
10
. W; a  s$ A* m8 {2 S# h11" P5 r% N# P) g8 N% h. a1 `8 D
12
" N' Q( q/ r! q9 \$ ]2 V5 h13
# I4 W, ^  }( ^0 W14
- l8 x, S/ o4 v/ e0 Z- Q+ T15
; s( m( N; m0 T  l16
+ G% N- b/ l" g& T( I4 f+ G17/ ~* o: r6 S+ p3 Z) p2 i
185 y" g3 @$ r9 G2 S) P( U
19
( v6 m, n$ P  Q2 V6 b! l% T优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
) t# g0 l% S. {' s, N: V( x4 T5 o- t4 O5 M: D3 u
//从小到大：, T4 n+ l: g, E
void bubble_sort(int arr[], int len)# y, @! _; {! I" v
{/ u& {# Y6 j/ D, ~8 L" E
int temp;
& O; O2 Z9 b! ]( u+ q; ]+ s bool flag;8 N" ^- [2 _6 R/ h
for (int i = 0; i < len - 1; ++i)  ^3 X6 \( D$ r# ~6 r
{
9 z0 ~( R0 f3 c6 r       //表示本趟冒泡是否发生交换的标志5 z, N- d# U9 e
flag=false;! E$ w: s+ x* X, j
  M# Q6 |1 _; y# k0 h6 Q
for (int j = 0; j < len - 1 - i; ++j)3 t. O1 K" I# j7 D/ T
{, g$ T8 f9 X. T' _7 D7 B, p1 i
if (arr[j] > arr[j + 1])//稳定的原因' o( f5 _4 B. {+ k1 u
{
, W4 d- E% c/ X$ _! [$ U' c) K temp = arr[j];* ^' D+ Z  [/ Z8 n' z! _8 l. ^
arr[j] = arr[j + 1];
' L2 h0 u9 _# p arr[j + 1] = temp;
& X9 R) u, V% o* W //有发生交换- m0 a3 ^* x6 r  U8 r
flag=true;
0 ?. r, Y1 C) \+ h }
7 x9 Y& t$ ?5 Y- U }//for
  G' m. R: F! t8 I7 d) r ) N8 x/ C3 N) E) H
//本趟遍历后没有发生交换，说明表已经有序
! Z( L" w9 ]9 [( W) ^  u% s# a if(flag==false)return;【1】
" e' j( t( Q8 |& P2 ]$ Y }//for+ n: p5 P6 @2 T2 O
}' M1 y# I; }, F  N' g5 X
) U: i5 a: ^6 Z; Q
1
; Y9 F# r: l# d& ]" G, [2
: T7 m: I& x4 M5 |! Y! c# R3
! |* P9 _; N3 C! s4: i1 g/ L- T2 O  k% O
5) k* o' ?! Q; ?% m
6
* H: }  O3 \  v; t76 B8 Z7 Y* G% d8 B
8
# }4 `( |! `1 O9
1 G9 ?! u% d! I10
2 A: e' E5 M& }8 [# Z11
( J5 C) `6 a1 q! z12
8 P0 {' w8 _& Q5 a+ M13
2 R3 H: ^1 r9 Z* t  d14
15! r6 }" V5 ?' f' n1 a! `! W4 A& _- ]
16
$ Q2 }+ U4 `* z9 G: C+ C17
$ T/ H3 I$ n6 K( S( `+ z3 l18, }! J1 `0 T6 o( ~$ J5 Q# ]
194 P* Q6 ^5 b" s
20
) X7 X. o# X0 h+ H3 M218 c3 T  P  a; s+ ^! \: k- o9 T
22
/ y: ]3 Z$ o+ V23
# @" y& p- E( ]& L24* h- y2 @* d; F/ q1 r/ F2 a
25+ N/ x9 M+ h/ A1 ]2 Y
26
9 ^( x; S( d: e1 P# [  I时间、空间复杂度5 D: y, ^, Q) ^# y7 ^3 x

( e$ k9 z$ ^% q  Z. f! t* m& k. a适用性：冒泡排序可以用于顺序表、链表/ i( t5 ^+ l9 C" Y& k+ T" q3 u

* j! x% F0 H' p# U/ P; D' T
9 z2 {% U1 L) A3 s  g4 A9 j) L$ t9 T2 v
" p% T+ {& j+ J& f5 ^% g/ J
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】# f' X1 U$ y# L" x( m! J
算法思想：: g% ^- G& w& ^" B- f! @
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
; X% k: F0 M/ v8 t! n- a通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，9 {' Q( L! B- E* r6 ]' a
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
  U  C4 V" j9 i' _5 R2 _再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
- b; c# A: P$ k3 a! b
; c$ E6 K) @' o& e然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。- G# Z* {1 w; O& s9 W2 E

* L# n5 Q  p  W  R: ?3 P+ K7 m划分的过程：2 Z7 c9 a' m( D& r) j
' K0 K% m! ^2 f3 W) O
初始状态：取首元素为pivot，定义low，high指针1 w' P3 D$ B9 X% r8 N. K6 v

$ r4 B6 {% U4 n6 V9 R首元素为49& h5 f9 L2 z% A, P2 E6 s# i3 l! a
high指针指向的数据小于49，就放在low指向的位置2 l  I1 v% u! e1 }
low指针指向的数据大于49，就放在high指向的位置& [5 D% `! P0 O) j$ O
) X' _$ L1 _4 a
4 x6 N( q% Z- P9 s3 F3 l. B
4 v- ^, |: z! r8 X" _

# K! u9 v8 P3 U! r
# E. ^  J# C8 X, I. Z// 用第一个元素将数组A[]划分为两个部分! T: i5 A% t' b( {( g. ?; y( b6 t
int Partition(int A[], int low, int high){/ Z& Y! {0 W3 F: q8 Q2 L
//取首元素为pivot& W3 C, I8 m/ G
int pivot = A[low];2 n; ~  B9 Q7 k# U$ v
( G+ D1 I- E) ~: k" w
while(low<high)
: |, u- I: f! P& Z7 P+ t/ f1 u {4 X5 l; H- [% o7 I" _. B) l
//先是high开始向左移动
  l7 U& _7 H' \) Q       while(low<high && A[high]>=pivot): S; A( D' H& D& t8 p3 I# I9 k" A
         --high;
0 N- Q* X7 b6 Z) {; E6 a       A[low] = A[high];
  s/ z- p+ U1 [8 C6 X7 \3 }, z( L& E8 Z, X; L- s5 e. s. O1 h
      //随后low向右移动
# K5 x8 r' t" u2 n! @5 O       while(low<high && A[low]<=pivot) ' R1 P* \8 l) @6 p! g+ b( W
         ++low;9 m0 U. B3 ]: J! I, B
      A[high] = A[low];' S% R: s# e! ]2 E( O
}5 V0 Y3 f* Z( I& _
% i. ^1 \0 W8 k% [
//low=high的位置，即pivot放在的位置
: L' h! \4 l$ s' C A[low] = pivot;) `* w! W/ f% @9 ^. w, R+ v3 [
4 s4 \" U; G  P2 v" N
return low;
3 F5 N9 L$ ~  q( I}
  c9 d% [3 T2 @& m1 G
6 q7 n. ^$ j3 l3 Y* y4 M( q# q7 n// 对A[]数组的low到high进行快速排序& Y; ?7 }- i, v  f' ~& A, \
void QuickSort(int A[], int low, int high){
9 H' l! B; S0 o/ ?- c: T" T if(low<high){
3 w) T% ?" {$ U. C: w# B7 T* p& A       int pivotpos = Partition(A, low, high);  //划分0 E+ M% d$ y+ p6 d5 X
      QuickSort(A, low, pivotpos - 1);
, C  [! B! `' j, O& A0 F0 C7 L; C5 f       QuickSort(A, pivotpos + 1, high);2 `, Y& u1 o' _) o+ F$ k# K0 I
}8 @% Z( D, w8 Z9 L5 O5 g
}
; w( V3 g$ B8 ]) j* {; M) k1 n4 h# c
1; I+ K; H% Y! Z8 S
2: N* F& g+ @  ]1 d8 X6 C
36 v2 Q" H+ @. `( q& g
4
4 t; L' M' v. E7 E% F+ }5$ o: e: r3 Q3 h' ^( s4 E
6! G" b* A  a" R' W/ y
7
) W' V$ J: Z& L9 w* w4 V* }88 B& `8 Z4 Q8 j- \! l2 w
9/ z; }8 N# N1 g4 H6 j
10" i, P- R7 @7 W! L" z
11
+ T' Y; y& j' y3 w* \5 A12
/ }6 r" _* A, c& @3 c13
# q. L1 [% N9 l9 r, v( x14
/ v6 v2 K& Y" u* t15. w+ Q# @0 ?6 v& `  K& X2 K( y
16: t+ s5 f9 q; `" ?5 x: w0 ]6 N, q; P
17) P3 i* K% J# x! a5 p
18
* R7 u6 |9 p$ F' r6 ^. \$ c, u, L19, f% ~  D# ~5 g! t! V
20
+ A! x- D3 f; u8 t+ j21" ^% _1 \0 G0 J. B, I
223 b- D( ^" n+ a& Z8 ~
23( K& a9 a) V# ]; v) k7 k( ?  o
24* x$ Z+ ?( `" E
253 T1 r/ F1 v) E# V) d$ b
26& [. `' W0 I1 ^, d' ?- {3 S
27; l/ J/ j/ @+ ^- L
28
+ n: v9 s6 X& m% a8 K4 k! P5 ^29
9 {. m3 z$ r8 ~0 {6 J305 {! |) z( U+ U# N2 ]. e
31
. p6 o: A6 a. U' J( T32
3 I9 B3 `- K( L. C9 m& m时间、空间复杂度
: }  X/ J& X( {3 }1 V2 o
4 Q* D2 }& q) v0 a7 q, [
% Y( r1 o& Z$ U7 O& [/ l) [5 M把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数* x8 o( X& b& [4 c
1 m8 M7 M7 G. H9 W: i
n个结点的⼆叉树：最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n
* ]3 Y: {% a% d* f
" J" O1 `6 D3 A+ ~1 o4 J& s% q1 g时间复杂度=O(n*递归层数)6 V! K: s6 i$ n- ^  {/ A- w5 x* q
最好时间复杂度=O(n * log2n)+ L& H6 p6 F% S/ g5 l8 h) s$ q) T+ ~7 T
最坏时间复杂度=O(n2). [& b1 D$ P+ v
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法  i; H' j) _& c& Q5 E7 t
& F9 I3 d1 _$ f4 Q+ O* y
空间复杂度=O(递归层数)
; R2 w! x$ K! p' r最好空间复杂度=O(log2n)/ }* H! l0 o  O3 I
最坏空间复杂度=O(n)
  T  |2 L/ e/ X5 p' j
/ y: O6 b/ c0 j( O$ K4 {最坏的情况2 a: _# g. j* ~4 ]( p/ m9 U2 i

5 B5 j% \- f! O( l% K% Y$ @* h( X) [( M; y2 {# b, A
6 F/ X5 q; U2 g- Z$ [* M0 q; Q
⽐较好的情况
# N5 c$ B% S2 C3 T" v/ y( d" {6 _, A! H; `; l7 S
& |  E, g- R3 n) m1 r: x9 H

8 `# p% [! a5 ]. Z不稳定的原因：
8 s/ ^1 ^$ L0 p$ I! h, @8 w, \0 ^3 X" O; k, J3 z$ H
5 D( ^2 z' T1 u1 S! k: m- i1 ?4 b5 v
2 J( E7 S. Y+ r6 U& {! m9 V
1 K- m# |# E4 |1 D0 x+ \
: _3 ]  z. @2 a9 }
3.选择排序
; \) Y. V% _( n" N+ H% ?. [选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列1 {( d" }2 t' X6 L7 g: C  D8 e

: Z- H6 H; N& I5 o. A8 u. e/ [  c3.1 （不稳定）简单选择排序
: _  c! c( Q- u$ i算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置( T9 {9 {/ C0 O3 s! S1 q. Y/ q& _% U& z

. G" S' X' D/ b/ j9 y) Q6 ]
$ C# @- q! |9 N
! ]7 W0 E( `' ~" Y// 交换a和b的值1 ~* v3 Y4 M/ M+ `" g; `* k
void swap(int &a, int &b){
% V- V5 e' P5 w  l/ }3 ]2 g) Q int temp = a;) _2 L' P0 h4 R, q
a = b;
/ s2 H. a. R& M9 A8 z b = temp;
- k4 g) s+ F; V; U2 ]  q}
+ ~3 S% r, ~1 q" n% i$ F! G! ^3 s" T2 o; G
// 对A[]数组共n个元素进行选择排序. q  b6 W9 `. p8 B
void SelectSort(int A[], int n)
! Q& Q! ?- n; h9 f{
* N, _! ~4 Q9 y  z% M2 O' @ //一共进行n-1趟，i指向待排序序列中第一个元素6 ~9 C( M' N7 R# Z- B# n
for(int i=0; i<n-1; i++)
. [- b2 p- @4 C# q {
4 u: |8 @8 w/ t) I( S1 ?       int min = i;
" L/ l7 g) u0 @, Q; Y9 b' ]! s8 J$ Y       for(int j=i+1; j<n; j++){ //在A[i...n-1]中选择最小的元素
! W+ ~4 O' I* g          if(A[j]<A[min])3 x" u  |& o1 o9 j
            min = j;; @" e4 F. E- P7 a
      }0 o8 H+ J+ S9 d2 B3 e7 A
      if(min!=i)
; U- F1 R$ N) G# H. ^$ M          swap(A, A[min]);
, ^9 F- i: Q- _& o% t' b* G; q }
" h7 n, {3 t5 Z. K: @; f. h}
, z; y( a& G6 L* w( Y; z/ U7 p5 v- _" s
16 ]) F1 z% z6 s
2) O" G0 ?7 E: r' f5 C5 k
3
' }4 H" `4 {- _& N5 |1 U4
7 ~. k* v' Q  i6 b& k5- s7 g9 [' j+ k' @& Z- X
6
8 P7 U  S1 W2 ^! }2 t/ o7
1 P) w$ ?. |4 h. n6 b$ R  a- G8' C! i! g! O+ [  F5 ~  }  W* \
98 k! f( Z( y: O1 ]3 c6 X
10
' M" R  E9 _# O' X8 ^: C+ X& W/ o3 {114 Y( _0 Q$ c) j* U: m; _
12. |9 `3 [& e; i) d  c  a) t* V4 @
139 q8 y' v! l! ]  a9 p0 M+ V# S2 P* l
14
6 E& `: F; H; X& {' Y15% e5 v( f. e4 ^) V- S' T: k
16) K0 u6 q6 W. J! L
17- w# K, D+ L' A! T- T
18" R8 w( s5 n( |0 w2 N& |5 K
19% V  N9 I; H$ G! E
208 Q8 \6 o/ q5 y
21+ P( h+ b1 q& a, I& u
22
  e1 Y$ @6 Z: h( `( E补充：对链表进行简单选择排序5 N8 n9 O/ L' M2 h

$ O4 M3 K- L6 V, ~2 c2 r1 L% `' pvoid selectSort(LinkList &L){
6 z+ p: ]. n- j LNode *h=L,*p,*q,*r,*s;
+ |3 o0 c. Z0 O; h7 {/ D L=NULL;" k9 \9 v5 ^" @9 j
while(h!=NULL){! f; ]- w( M# [7 J
      p=s=h; q=r=NULL;
4 W# U; ~2 ]( `0 ]" y0 i       while(p!=NULL){. ~3 g1 a% n; Y2 V% i
         if(p->data>s->data){
8 E( u, u& m' ^* |. G+ Q0 G             s=p; r=q;
. X5 B, `  Q# u2 U1 U          }
6 F5 m' S+ Q' n( n          q=p; p=p->next;9 n4 @7 g/ m) g0 c$ \# r
      }6 ?+ |' Y3 F. m" N
      if(s==h)- h4 _# A$ W- F% G2 Y
         h=h->next;
8 P( ^& N* o/ C       else, y2 ~5 b  I  O3 N  \& V
         r->next=s->next;7 x$ d8 s. J. a0 [$ J3 E6 ?  w
      s->next=L; L=s;
. U7 L9 }5 V7 e' b/ y& B }
, ?2 M" c- G# f. a) r}( Y9 s! t$ b1 C3 w% ^; ~
+ t& Q5 Z* g5 H6 z
1
9 ]# G: @$ H) B% G1 a0 k4 ?* p, J2
3 y4 \7 a% X: t( J* v$ C: S3
3 b4 ^" I- X( b4 \6 I$ C4
; w0 ~8 a" h8 Y- j5& _, a3 q; c* l. {: {- p' x
6
! C' E+ A, v, `" W6 X" k1 [" S7
2 B6 Y4 U2 T3 u0 {$ T7 Z' \, ]8
/ s7 I' C2 m$ \5 ^: A$ Q9" O1 s, `6 H/ P
107 P: C! q8 A% h8 s
118 V0 W& X3 ~, [. f) J8 M- t
124 S8 V! I( ~  n2 Q! T
13
3 C2 y0 I# C" P, v) S6 L' r0 c/ z14" y2 j$ M2 T( G* G1 {6 T9 z8 T3 v
15* x) Q! N6 k! ?* s$ l
16
( _! [& ~2 l) d6 S6 N1 p17
/ g$ N0 @6 |% U7 A7 J18
% [. A& X- L; y时间、空间复杂度* c$ ?  O' e: T' C2 D" S: r
% N2 S5 T+ }1 \: E! [3 {4 T* K, J

$ C/ x8 Y( D# E/ Q2 v
* J" |9 Q( h; J  n3 f- M
8 @$ {: r. _* a. X" R5 d适用性：适用于顺序存储和链式存储的线性表。5 i6 n7 i9 N7 ?5 E5 m5 Q

* U, ~( V. b4 |, q" a$ d$ f; x# F& [5 a8 {3 X
! O/ G! l0 |, [) P& K
3.2 （不稳定）堆排序6 I1 `. `: b, ^$ y
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？8 P2 x& \$ [9 r! i4 T, }0 |
堆是具有以下性质的完全二叉树：: S/ b, j0 V# |
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；7 w/ e, V% L; Y7 e, i/ R. N& w
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
' m  p+ f# B1 `6 X
5 K! y1 T: a# y/ ~1 x% K. O/ b4 w. ]; n, k
9 t1 g) X* o# k
即：+ G7 g- p) E- h! v$ z( n7 m' K
若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
$ `5 @) v9 Y7 N  f% {( A若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）0 l( B, E7 _4 b+ [

6 C5 ~2 @* l9 B; B9 q  m② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
! u+ T. S8 Y+ n! n! i思路：
* `2 v8 F# v$ H: S把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整6 Q1 m) k. L5 q; o9 J

" a" p( z- J) [2 X$ U! e# m在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点" h; H' }7 i- ~" |. Q

5 n9 A& B0 \* \* a# s4 l; E检查内容：是否满⾜根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换  m. n" W! M; `, T9 K6 q% k
  Y/ d( t2 F, [3 c
过程例子：
; K! D# X8 C/ z+ u5 s5 q9 u
: H6 R6 A, x2 d; q% [1 D) |$ r; C: m" C. Y3 u
. G- N& |, n4 k4 b* M  Q% z
建⽴⼤根堆（代码）：' ^0 C0 j% j; ~$ ^, P8 b

" L8 L, u; e3 [( F& ]3 ?
' N' L& a( @6 E3 X/ B  h6 R% j1 Q% J$ ~' a( m
// 对初始序列建立大根堆, A) [# m( Z, V# q7 m, q$ _, X
void BuildMaxHeap(int A[], int len){7 S4 ]+ w2 }# h: g
for(int i=len/2; i>0; i--) //从后往前调整所有非终端结点
& j' }! o; q9 J- S# q% A+ B3 B4 e& p       HeadAdjust(A, i, len);/ V: ?8 L( s8 K$ t/ A1 x# a- w
}
( Z& t! {# h8 Q2 \& G7 c
( W: C" }0 ?7 k' H// 将以k为根的子树调整为大根堆
' }& Y9 ^, Q3 hvoid HeadAdjust(int A[], int k, int len){
  i4 J; I( [8 K; D8 A A[0] = A[k];
. Z& D. M4 R) |% d3 H7 G( \. p for(int i=2*k; i<=len; i*=2){ //沿k较大的子结点向下调整* t, K3 {( y' [0 L! D3 l
      if(i<len && A<A[i+1])
% D" |2 i$ |, P7 ?0 k+ p          i++;) R+ ^: G! z$ }
      if(A[0] >= A)
2 l& e; p5 `+ ?          break;, O, C9 J  P! U/ m0 Q
      else{0 ]& W2 Y( F# X
         A[k] = A; //将A调整至双亲结点上4 A$ `8 m! `+ M+ g& j8 u7 I
         k=i; //修改k值，以便继续向下筛选
  ?! A6 F6 k# A# O. G) n2 U       }! v( n: F6 W5 c: t0 E( `
}6 @& v$ v2 U" {8 u
A[k] = A[0]
9 O0 \/ L# I5 M4 O6 D  o$ w2 M}
  V  @! ~. y/ ?2 O3 I# D3 _  f& q& G0 {7 b6 ?+ R4 h
1
# _: n+ @- l4 F/ v9 }: n7 u8 I2% N4 h% T- O, e, a& T9 w" t
3" H& r% `* j, D6 a8 k  _1 G- I8 L
4" @% W$ {$ Y! B' j, h' e
5
0 J0 p$ ?4 f+ q" k  b; U! Q6" B4 {8 W+ T$ S3 K
76 ?+ M# V+ n# q7 [& J" Q& Q7 }8 p
8
0 D4 K6 C( J/ Y9 J9
5 O" Q* s+ ~0 C$ I: ^0 Q109 [2 ?. _! N# o+ s( X
11
( ?* H' Z  T7 V3 d5 v4 d" l12+ H+ B% P# B" `! S
13
$ }, q: j+ E$ B% ]14: B4 D* M" T! ^# d* q. \' `+ ~
15
9 A3 E4 L$ s. f$ q% O- M; x16' a% ^! a' d3 P9 Q  _: M: z
17
2 m; B) |; r' ^18. ~0 J% o3 U, u# P* E3 W
190 h  o5 G/ L- \  y
20
! J* u. l* e) O3 _+ G+ }) z7 x21; C& ^$ X. B! a( J2 t& L5 `
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)" W+ G, W& T( ~
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
* E# Z9 s5 ~7 l& C- C7 t0 U8 s1 [( U0 Q2 ]; t- G2 ~% G
堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
  H5 _3 K/ E' w: d8 b8 W2 [" ]6 ?: `* _2 s  e* ~- }4 L
过程：2 V" u2 f4 N2 O7 q. J
1 e2 t2 B) d0 P; l0 v+ O
// 交换a和b的值
* a4 e' Q: b- B6 ^/ o! [$ k9 pvoid swap(int &a, int &b){
. z! s" M/ N% o int temp = a;
6 }- Z; A" y$ ^4 l a = b;
& h2 w" e& X- P& c1 n0 H b = temp;
/ U1 T, R" W, E# j* ]}
3 J! c+ v" p% B  @* e3 Q
% n: ^& ^5 T/ }$ V, z, N1 T  x// 对长为len的数组A[]进行堆排序
" r6 {3 m* O. w; G0 X/ X3 O1 @void HeapSort(int A[], int len){
$ ]; U# X* n5 j& F  X% | //初始建立大根堆) E( }4 B5 }) ^7 x4 t7 b3 I
BuildMaxHeap(A, len);          6 j; d  B  a& l- m' b) _

! z$ d: F- `% {$ v& p" {& E //n-1趟的交换和建堆过程
; a2 z1 Y! w8 f5 a# T for(int i=len; i>1; i--)
" Y# l$ W& i" H" E% A$ `6 _' W( j {
1 o; }. _. \/ s: U* x0 j7 j& O' B0 o       swap(A, A[1]);
! j/ x7 u- Y/ e; i' P       HeadAdjust(A,1,i-1);
; a5 P* F6 I; ]4 `; J }
- ]4 `% q7 |% q4 K}
/ V( s8 ~9 f3 L% D; h
' ?5 t! z+ M/ c: L8 `' H1
2 p. U* Y1 [4 X( N1 U27 a1 _$ X6 U& a" U
3
* Y7 M2 W" ?  L3 ?& N  O4& {, C- U6 U! t. ^# z
5# l# A  U0 Z/ m9 v! b7 _( \* G
6
. y# F& O- `9 X4 _0 v7! l- a# e' G- L
8$ n* \( U! y% X3 m6 J2 R6 s& x
95 b, d$ K8 M3 I9 G2 a" k" C  N% y; `
102 B/ v  l* F; C. r4 }+ E, J. ~
11+ Q/ }0 `$ V' l. S  L
12' P5 T0 x1 }* z- H
13# W9 i5 K& Q/ ?5 `
14
' m3 F2 X! o3 y9 i3 i15
. H1 R7 x2 P6 A( d% h! h16
) q$ y5 n5 b1 o6 [) I. ^5 R17+ N' ~( m2 G! l2 h" s8 b( A0 w
18
2 N* }/ R5 |6 S% ~19
$ X- g1 X7 A5 `2 u& F1 K时间、空间复杂度: M8 ]* K3 m- B( G$ B
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
! b* S- k, n' ^% L. ], p故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)' Z: o* g. {* ]/ q0 \- |
: s! G" v/ `" E0 k3 s2 I+ u; p) y: w
空间复杂度 = O(1)# T' k' v  q& ~1 M% A( n2 L0 I
% e8 o1 T5 I  p+ x
结论：堆排序是不稳定的/ t* Z  x; _  C0 i; A5 E) S0 t
$ d$ D, a0 L2 B4 K/ Z2 `2 o
; s4 s0 }7 l6 H) u6 N
④ 补充：在堆中插⼊新元素1 e2 C; n/ x; M0 r# e3 d' t: r
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
# W) `2 Z: ?* {9 p0 t. O新元素就这样⼀路“上升”，直到⽆法继续上升为⽌/ x% |; x2 ^: e3 E* V
3 B+ d% L5 O0 G7 H* _4 t: C
  t% T+ V! b% x5 ?

! Z0 V5 C0 p# T4 q* b( i6 u⑤ 补充：在堆中删除元素& l  {7 i0 |% k1 Y- L! B
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
: p0 [- R* q" Y& r5 a" R4 B2 w2 K! q# f& h/ I
$ z) X" g0 H' ]" g  f! R: b

% c. D$ U: W/ O( |3 b
" ?5 j/ E  \; |
- `& d( X7 R  a( B, s4. （稳定）归并排序7 {0 e# q% ]: l8 M8 D9 x# _
归并：把两个或多个已经有序的序列合并成⼀个5 \. S' ]/ |7 k0 p

) ?4 [0 T/ S* u. \) s① 明白什么是“2路”归并？——就是“⼆合⼀”% i2 W8 P5 p$ |5 i# I/ ^9 M6 O

& t3 R7 \4 \. }8 `2 L0 h( R, `多路归并：! l% F- l; z% m/ v5 r! `

0 U7 w, j# N3 ]! f; q) k( o4 h2 S2 s% t$ M/ f' v
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】4 r- ^( `* l$ b) F& o

/ A& j) P& t4 ]- G& c& L( l, ]1 yB[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定$ z* Y6 B0 j1 k" u; ^0 f
3 E, r/ }; a7 w8 x0 h
③递归进行分治思想【MergeSort(int A[], int low, int high)】- A- Q0 H+ A' q6 a4 r; L

% L- M3 \8 \8 l6 _) X$ ^: \8 |& ?+ u) I
④ 总实现代码( U% g5 n. N! A% \: A0 w: y9 R
// 辅助数组B) ]* `4 P3 T% z0 Q1 ~% G/ u
int *B=(int *)malloc(n*sizeof(int));  w+ O: F1 R0 T& a. \

6 |5 J' v" l0 j; r9 A// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并# q- a2 o! k* Z4 _, l4 r
void Merge(int A[], int low, int mid, int high){7 Y# V! @! _7 g2 r  r# Q
int i,j,k;
2 d& R/ m7 T5 A: X1 s( Y1 Q1 Q. B for(k=low; k<=high; k++)
- }; o) o4 t: R: t7 P       B[k]=A[k];
- d7 m1 K- Q  \ for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
0 }6 L% j1 _  G7 o* G! ^. o* Z6 n0 B       if(B<=B[j])
+ J# x( {" @) D' R1 K8 {5 w          A[k]=B[i++];
  D: C4 T2 I  S' U- k* e       else. e5 y+ U$ O' m: o4 K: G' t
         A[k]=B[j++];
6 r$ J0 s' E5 a# w# o/ @$ A }  v# l. ]$ ]$ L
while(i<=mid)
8 u) y- I( s: Z* F3 e4 u4 b$ l1 W, H       A[k++]=B[i++];( t% Z& j8 D- A. n+ ^! c" [
while(j<=high)
" s8 F* S8 L1 {9 ^       A[k++]=B[j++];3 t$ I/ r" X$ E
}
+ k* [  a' Y, g) {6 b  s+ n2 B( P' d- M. T# U  c# k' [
" A: [( [  k5 A3 X( }
// 递归操作（使用了分治法思想）1 _# j/ _5 e* ?
void MergeSort(int A[], int low, int high){3 w- R1 U! b1 J8 ?( W+ H) o
if(low<high){
$ {! Q3 _2 F/ a& o5 [       int mid = (low+high)/2;+ A2 i$ x! s1 \6 Y+ o
      MergeSort(A, low, mid);
- O7 B' G! y+ c6 Y9 h       MergeSort(A, mid+1, high);( `# V0 l! ], |* U) ]! L
      Merge(A,low,mid,high);    //归并( a% A9 D! E# v5 \: w4 ?
}
6 `2 D- m! [9 D, d}# g' d0 J* _6 Y

# G, K9 n/ ^0 Y6 h# m+ ~+ Q1 T1
5 X, J) M7 N+ C6 r2, N5 @6 o7 R- c
3- z# a3 t- m. z/ S* |
4
. b2 T# s, n. i5/ L2 w- e. \  S% |+ A2 O( i
6
% ~4 c& ~8 O. C: {5 ]7" n% `0 v: p! ~. y6 i! G  G3 M
8
5 c9 t" v; {7 s9$ ~" R+ p( m! E4 l6 _% X
10
" ^0 k* s# X7 |$ f' E9 x11+ P3 m, i$ @+ F5 B
129 K: W8 e& W. B8 Y* z8 l; f% z  r1 T6 b% T
13! q9 s6 `; i; N0 [0 r+ y9 l
14
$ M) }8 `. Z  |- d; c15
  q0 p6 s" w! ^  G& A( d, c16
: X; ^) _5 n8 N/ D8 s" z0 f+ J9 Z17" \# C5 l9 t. D6 |4 ]/ z& |2 @
18, i$ O, I% d* K! O" R" E+ \  `
19
4 r, L; p/ v  p0 H, Z20! q; L! N" Q3 M7 R( J: d$ ?
21
+ u" k. b$ z/ c22
! b) O1 m' a) R, r9 P# I4 O8 ]23" s1 t  f- E1 F1 \* Q: F% r1 z
24
5 v! p/ P2 C3 W; E# O25' u* m  p9 ?/ C- g- ]) c6 ?
26
, W" k$ q% b( I8 W279 _4 s, W) a# ~
289 \, t6 }/ H" B8 Y
29
$ ?8 Z9 z0 B8 R" U) k30
' W8 ~$ }, A9 m  M6 _; D时间、空间复杂度
0 U3 }+ V6 \9 V2 ~$ b/ @
% R+ o+ g% i6 ^! z- S
& E& d( T) q$ C- z! _& J' r, t
! F3 r; I' C5 o" ]% a8 k" R& D/ x7 @( I) f4 Z  \# A
5. 基数排序
: s6 T- f4 @0 a. p  t直接看课本的过程图来理解P3524 o) v+ r$ m0 P. T5 q( M

% r: f8 r- A0 c0 G. ?5 ]- Z再看这个例子：
8 Z0 d( K. @, a& p9 i( N* k
9 J6 P: K% f% H4 K4 ^. J* Q7 N& k$ z  t) \
算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。& V0 U. x5 E, f8 P
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
2 Z3 t  T5 S- r( J收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
6 ?+ I5 B& E* h9 j$ e- j基数排序擅长处理的问题：
, z0 j- u8 T  B7 K①数据元素的关键字可以方便地拆分为d组，且d较小。& }! M( C7 a( |; x
②每组关键字的取值范围不大，即r较小。
% a+ N( |# \1 n* r! p③ 数据元素个数n较大。, U% t! j" Y5 b$ h% v- H
算法效率分析：
  q" z1 R0 c% I7 h时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
, l4 V5 L  g- y* h2 c, Y+ `- h空间复杂度： O( r ) ，其中r为辅助队列数量。
/ |( d( T. U3 V* ~2 q4 U稳定性：稳定。

. ~- \8 K$ _+ e' J4 E6 `4 e3 `) F! u0 C1 l6 U
内部排序算法总结$ G2 f' `- I" x1 f9 m1 P

3 r5 i, r4 T, e( X* r————————————————
2 C; g- C7 L8 e: n6 u版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# s' w- I- f+ Z4 n* V原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969
  k; W$ {/ c" Y$ o, f. R
; O# e. ~9 i, q- j* ~2 J" p
  d. F+ C* A) [4 ~