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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
3 ~1 Q" I' P, h" {& r- ?文章目录
排序
5 G, I; w( h% ~3 f9 x0 _+ o1. 插⼊排序
4 c% |7 S$ m! k# Z5 t% d# s（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
) T6 ^" e- m0 |. g3 w& y  c9 `5 \时间、空间复杂度
/ ]8 n9 }6 U1 {. r) V! d（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
4 K: P1 X6 @( a. G; t时间、空间复杂度
: A" z. V/ h5 f2. 交换排序
2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
9 ]: J0 K3 a: |: j+ W! f3 b时间、空间复杂度
3.选择排序
3.1 （不稳定）简单选择排序
3 L. u7 x3 Q( c  C  G1 B时间、空间复杂度
3.2 （不稳定）堆排序
; x: R" ~- i+ n8 t1 a! M! }6 B& X① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
6 s: g! k# r  l② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
; S4 X! f8 B" m+ U③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
4. （稳定）归并排序
4 [7 ?7 B4 g, L! t① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
7 u. N5 _% V4 L/ D' j* O0 S" N③递归进行分治思想【MergeSort(int A[], int low, int high)】
. e- E3 B2 d/ Y1 n) t④ 总实现代码
时间、空间复杂度
5. 基数排序
# [: s$ ~. M7 \5 A内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

- e9 Q( S, h; ?& X: u. `# I排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
3 l" ]; G( p- ^+ ^* C3 b
0 V4 y; ?) W7 g4 F  [* a1 n算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。
- z! d/ J8 e5 C$ |1 u
. r; O9 ]5 p/ L  x! n0 ~! S* B6 M
排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
& e8 c+ c8 l. z外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

) W. r* f4 r5 Y; D( `! \/ K4 A( Y各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html



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

9 D! Y0 m3 z4 k/ F) n算法解释：（从小到大）
3 [2 q+ f) b# H6 J0 S
4 z/ w9 l8 p: O! J7 J6 V# V2 }( b+ L  F
算法三个步骤：

! }' u  C4 l: m8 u! K先保留要插入的数字
& y7 r4 q8 G  S! F: A' z1 x; Z; q往后移
8 {$ g# S( A; q) K7 z; V插入元素
! ~' P  v4 w  N9 I- R
// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
) O& K9 J4 m: i0 z/ Q% d; F: A    for(i=1; i<n; i++)
    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
        if(A<A[i-1])
        {           
- a( N5 K8 @0 Q5 q            temp=A;  //保留要插入的数字

            for(j=i-1; j>=0 && A[j]>temp; --j)
, L/ Y& Y$ ~( Y# D# v                A[j+1]=A[j];    //所有大于temp的元素都向后挪
! `7 k. H2 r, m5 L
- N! M& [6 B4 c, F            A[j+1]=temp;//插入元素
$ t" w% L& A* t0 a, B        }
& D0 }" s( I# Z/ v+ ?' ]  Y    }
}
6 j: r& m  U* f+ s
1
2
8 U( E8 ~* w  S$ j- z; |3
' F8 r; n. y+ L$ \3 _- u# [! D, K4
1 J7 r7 X# \- y! g/ b- w5
6
7
) _* e6 O; j; c- |* k: Z8
) v" Z$ Q/ [& J# F+ Q+ x8 h9
4 T0 J1 [( f6 U10
11
12
13
4 }' [% ]' ?) B$ Z" H! Q14
15
1 Q* \# s- e! n8 K) l16
4 U  r- S% n5 {4 w0 l: _# S17
' _6 Z" a) }: e4 P/ D7 B" ~用算法再带入这个例子，进行加深理解
1 h, [8 U4 L2 K

带哨兵：
; L8 Q8 e  V0 o/ n! @: w
7 e. @6 m7 M/ I* o
6 z4 P  ]/ ~9 i1 v6 c补充：对链表L进行插入排序
6 H/ r& x, Z) @+ v. D- F
* X4 j9 {. y6 I4 a- K2 R/ H5 Rvoid InsertSort(LinkList &L){
; ]! L7 f; `; ^/ d    LNode *p=L->next, *pre;
8 d: n: p' N- K$ F' M  v    LNode *r=p->next;
* a/ I+ Z2 k: |" n, U) Q    p->next=NULL;
. ~* |6 r" r3 t$ ]  N* ^2 X0 m    p=r;
    while(p!=NULL){
        r=p->next;
        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
" s5 U; @4 Y. j. d$ I9 ~, ]  Q3 f        p->next=pre->next;
: i7 v  a( Y; j" f+ \) o        pre->next=p;
        p=r;
( d! X9 e4 }2 v3 f    }
' \$ o5 I; z7 d9 E/ J}
1
; K  q: I8 w" _1 u9 L0 Q2
5 Z* ^4 ^$ t8 v3
4
9 C6 N' t5 r$ W! K9 l5
) R% W7 ?& Y& C1 C. u6
, c" \- ~* i# c+ f7 p) \1 |7
, C3 l* z4 b+ k% r8
9
10
11
/ j  |  E! X) m* w( a7 V% R12
) Y; @+ u4 I+ c13
14
15
时间、空间复杂度
( V. Z6 ?. y$ J+ M' t8 m5 |
* k" i" E! E0 y8 |2 j, g
7 E/ p) x+ x9 \9 v' H最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
9 o. J6 g6 d2 u5 b0 V最好时间复杂度—— O(n)

  t+ ]1 v! K5 e最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
+ |. O9 i% G# w4 `: M$ T0 l第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
* h5 H2 z: V* S. P8 q, N) Y9 U1 v…
: L$ n/ M( X1 j. D第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)
6 f& \) k2 k5 W& W# |. K
' |- t# P: c( w  ]6 `) e1 k
8 c4 g4 V7 D9 L4 {3 s5 d


（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：
6 U* }! V9 o- ~$ O" U5 j* `

2 I9 E7 `$ Y) @4 i: Q
//对A[]数组中共n个元素进行折半插入排序
& g6 }/ d/ b! l2 i1 k# i3 evoid InsertSort(int A[], int n)
{
    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
& P8 G  L6 P* T/ _# l, X# x    {
        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
        while(low<=high){            
9 Y1 J. v2 g3 _6 E: h            mid=(low+high)/2;
            if(A[mid]>A[0])
: d! o) y  ~& |7 ]* P/ F( M& s- c: @                high=mid-1;
+ L" b/ N" E$ w2 [. x            else
  {1 D5 @, ^' ~6 L3 T) ^% ?# h                low=mid+1;
' j; k: Q, r7 _; L        }
8 i6 u5 G7 ?& h/ t         //--------------------------------------------
" t! m( Z1 Y* u3 F2 ]( {& B        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];

        A[high+1]=A[0];//插入
    }
0 O0 s) t9 V- M4 t" ^! b" K( v  q}
2 f( B; Y* d4 ]6 l/ R4 H/ r; I
1
2
3
  ?) w/ G9 C7 T2 g% b% x4
5
% B: B# j2 u# ~# |( H" L0 D6
  @% P; Y# \$ l: R: C; F7
: J6 A" s: w- F4 d6 j8
, j5 m$ I3 |7 L  u" m6 @9
10
11
: G% {; ]2 s# ^4 }* W8 a12
13
5 N! |) V2 Z8 @/ S14
15
$ l9 e1 r* k9 l" G16
0 h: ?1 r. K, E) I0 d7 N& `17
( ?7 h* q6 V' T! K18
+ X" V' r" r& g) c19
8 e: j. n" y, _/ }2 s20
5 H  u4 M( ]! q' g7 Q21
$ y. t4 P* j" ]5 a22
23
时间、空间复杂度
( `# M! X' S  p/ P空间复杂度：O(1)
- `5 [; d; X: J( W& m! i
【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)

; t3 e* B- `+ \9 k7 Z" I+ f$ Q
（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
' `. t* F& E% b5 H
& ^4 T/ i' z" X# I算法思想
2 B+ r# _0 Z  S( b, P- d
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：
2 G5 M% C/ _2 |9 m0 K% h0 D
2 U- S" \1 ~' e9 }# l+ q
+ }( {. d; L# _! q. l
; p- j' w4 y: E/ p% t$ `1 T2 ^代码实现：

) H5 s* l- Y! [2 ?//从小到大
void shellSort(int* arr, int n)
{
8 A" M* ], \1 f5 R. }- M/ Z        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
        {
            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
# W6 _! `4 k/ \            {
                if (arr < arr[i - gap])
                {
4 C! m' a* T& s( P3 V                    temp = arr;

                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
) V6 l9 P- x: i( E: W                        arr[j + gap] = arr[j];
; C" \# s/ n1 z# U
( j. x0 y, u1 G; Z/ p# o. z                    arr[j + gap] = temp;//插入进去
2 V8 n7 v1 c! s$ U/ X( r! V                }
            }
            //************************************************************************************
9 m/ z; m5 w2 u/ w7 r        }
8 ^3 \# k! T- G0 n}
* Z( d! n2 q8 m) m" b: _& T( [/ b& [
1
1 k5 q9 h! {# g2
3
4
5
6
7
8
& Y0 S. Z6 T! i2 `9
10
( \3 M6 b- H0 h" L11
12
13
4 B. W' @3 f4 f3 t) T14
15
16
17
4 i# w- a- d9 E. O18
2 n2 z5 e* Z* e. `% O19
- C8 |( B( v! ?20
21
22
( o) O% H0 {. {) J4 n# s5 Y: G& \23
  h+ K% e; b- G$ \& @2 t; _2 G/ u* v7 V24
时间、空间复杂度
# n! ]$ B& x9 q( d, z5 @空间复杂度：O(1)
' t* S1 k, Y! o; [; G
& L4 n8 y6 M; J, a时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
- i+ o+ {( p% T: l
1 S3 c% Y1 t9 ^+ Q6 H6 H* y稳定性：不稳定！

7 P4 }# {/ k- P1 f% W. F/ `

适⽤性：仅适⽤于顺序表，不适⽤于链表


& g3 s5 F9 Z9 t' j. r" _4 {. Q
7 ~5 ]5 Y  H' L/ l2 G# F2. 交换排序
2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
5 s( k7 ?& `/ K1 A7 t# P从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

8 }( t) Y) H( }' a4 w- d. `每一轮比较会让一个最大数字沉底或者一个最小数字上浮
# C' V1 U+ Q, f+ |
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
$ `" |+ f5 K8 Y# J5 U+ K% ]5 s
实现代码：

//从小到大：
6 V9 `# N/ d, ?  _void bubble_sort(int arr[], int len)//冒泡排序int*arr
{
' ^1 l$ i: x$ v* M" l# K! J% J$ S        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
: F  \: I# w5 o        {
% w8 S' E& H. r6 j* H                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
# f; V* ]& s  u6 G+ w                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
- k2 M, d0 [5 r' i# o: h$ T                {
) t2 X; I' [% X                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
/ A. q5 `5 j# H) x) X# x                        {
' \, s, x$ J  Q* h; }                                //交换两个元素位置
- y, k- D1 d& Y9 J2 ]$ D                                temp = arr[j];
* ?8 v0 ?9 R$ E9 \                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
& ?" I" b3 `2 ?( l- ^. M% f                        }
. H. S8 g4 a' h, e& f' K( [% q, y                }
6 {6 A% d3 ^" T8 s& H& Y& v        }
' @: R2 @4 S$ x9 P8 \}
! H$ J8 |9 b6 G! }; W$ J4 M
1
( U- Q5 C3 L& R4 y6 D7 @9 K2
3
4
5
7 f1 f& S* b1 P4 x) Q3 |" R6
7
8
4 G* Y9 H* e- D9 }3 o/ w$ }8 a7 I' E9
10
% t% N( }( J2 c" S5 g: D2 [11
12
13
14
8 ^2 `8 r3 H' k15
+ M/ ~7 R2 j( j9 f/ _/ d16
17
, d8 e. a4 Q3 Q6 s% Z18
19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

- N, `/ q: r  E//从小到大：
void bubble_sort(int arr[], int len)
{
# p% ?5 @3 ]8 C. G! c9 e        int temp;
        bool flag;
        for (int i = 0; i < len - 1; ++i)
        {
            //表示本趟冒泡是否发生交换的标志
+ ]7 a5 U# [' J6 r                flag=false;
               
                for (int j = 0; j < len - 1 - i; ++j)
3 N) k9 Z' O% w$ K1 l1 o  h: I4 W                {
                        if (arr[j] > arr[j + 1])//稳定的原因
2 u. w# m) o4 U: t" i, T" J. c$ _* r                        {
                                temp = arr[j];
                                arr[j] = arr[j + 1];
2 c' ^/ G3 k. N, }# S6 b                                arr[j + 1] = temp;
                                //有发生交换
7 Y( q9 y9 p8 x0 A                                flag=true;
  h) F; S' ?9 i1 X# h                        }
                }//for
- z. a8 E! k3 o( z% o7 B5 k               
                //本趟遍历后没有发生交换，说明表已经有序
- j6 G7 J( }1 q+ G                if(flag==false)return;【1】
        }//for
}

1
$ L% \' l. F- B* J2
3
8 S2 c/ O# D2 M/ a4
5
* t2 G4 L" S1 J+ l4 X# X6
) _5 f4 q5 W9 [% G( S; x  c7
8
7 [/ e* P7 g- {8 R9
10
11
12
' g* Z, ^* ~1 ~. q, o2 O5 E; W13
14
/ ^) u# M6 D+ Y- S( c  H15
/ `- P' J0 s6 E5 C' B0 t' h* b: q16
0 K2 I0 L( x/ h17
18
19
20
' |6 s5 z9 ^2 H7 I21
22
23
24
) o" z$ Y' ?9 y+ Q, f25
26
时间、空间复杂度
* f: }( F2 Y; g( k! ?! c+ b4 G
适用性：冒泡排序可以用于顺序表、链表
8 O4 h4 K& A' z  E5 q; t
. P# W( U% i+ f5 T

3 X  E' }/ u4 @" S: Z# |. P
- N' v4 \1 L+ P, p2 A0 M  U/ T2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
$ _, I. N4 j1 G! Q- [7 q& K5 X再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
  a6 S5 B3 V# _# C' q! S
/ \! U( y: Z/ E3 a/ U" l划分的过程：
: O; W/ ]- w  Y' U# e
初始状态：取首元素为pivot，定义low，high指针
) p3 P- _0 F+ k; P* s
首元素为49
high指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置

# d; K1 [! u6 p

8 Z, y; |) `9 X3 G
& |' g/ N5 ^9 y
// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
* l. T' w, e2 g6 v! K4 Q. F6 f        //取首元素为pivot
4 g% s' x6 {& d1 m; A  O! A% A    int pivot = A[low];
2 X$ }5 S7 l+ Z6 B3 |/ G, W
, \* z1 d- @2 @$ x) V1 I7 V/ e7 k9 s    while(low<high)
    {
            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
            --high;
        A[low] = A[high];

" z3 J& F9 L3 b        //随后low向右移动
        while(low<high && A[low]<=pivot)
            ++low;
        A[high] = A[low];
    }
( T+ b! Y9 a0 W5 [6 {& `* m) W
    //low=high的位置，即pivot放在的位置
/ f3 x  X6 w$ Z8 x    A[low] = pivot;
% |/ m  P( w- }/ J, [# X4 I" S3 C
( i; l2 e: \) W* X    return low;
}

8 Q% _* [! ~+ o4 Q, O% W* g4 x// 对A[]数组的low到high进行快速排序
' B$ s" I% L: ?6 gvoid QuickSort(int A[], int low, int high){
    if(low<high){
        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
    }
}
$ Q& w* h, D% l/ H
1
2 N! W/ r2 n2 q- K8 |2
3
+ W1 ]+ F  [& J9 [' k6 v4
5
, V8 S' L  g5 N- W6
" }# B5 b( k# D9 W3 @' r7
8
9
10
11
8 K! Y, q/ V4 W, Z8 _: j12
$ Y; h6 \4 |: O! j9 q8 n13
4 C( K6 a; t' W- u7 Y14
/ ~" M1 p, i( P( N* g9 Y15
16
17
/ x1 s. t# c3 [$ V- f$ \/ c* i: y18
# x  O' `/ u6 g" q: y19
% R* q, L3 l# \20
21
22
/ |5 H( v2 w( J! H- u8 ]! `23
24
25
26
( m& B# r4 F: G. [27
- |3 b- X" g' M9 m3 L8 w28
6 ~5 Z' B- W2 s1 M# a0 G29
30
5 T  G5 H. M+ w* [31
32
- i1 `( I5 P# y时间、空间复杂度
5 F! v, M8 L* K' g; w

! v) Q$ F4 f' W7 B6 _把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数
1 |6 T: u( Y/ x6 l4 ^
n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
, ^; K: l9 O. @3 Z3 k平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法
% l% R) W& E4 c. E+ O3 _
0 c* q" y* `% b  i( l) j# u. j' f空间复杂度=O(递归层数)
# s: R# f+ D# F+ a最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)
$ q2 J$ B. l2 e
4 Z+ o/ l- G. s7 v( d) J最坏的情况
  y- u4 p1 ^. D/ B% ]: P8 G1 t0 p


⽐较好的情况


- ?- o5 x5 l, t( |- y8 Y7 a
不稳定的原因：

, ^& A) g1 B% p1 U+ K. p  \
$ f& L" K$ u% x


3.选择排序
) ~# T; M0 m* V; g. t- t0 g选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

( w7 K% \3 [6 V  ^! j3.1 （不稳定）简单选择排序
  B8 w+ V, I7 r! w: ]算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
( ]% I2 h1 \' q, W3 a9 E. m* t9 \
1 u. Y5 Q/ t8 K  M7 b4 x

* N9 }% v% r. j) M, Z& c// 交换a和b的值
. R+ o$ O3 _2 U% ^' o/ ]void swap(int &a, int &b){
; J- T) t# i: \: f4 ~) ?    int temp = a;
    a = b;
1 T. m: a+ `/ T1 l/ z0 m+ O1 p/ K    b = temp;
% b2 n) k; t# T1 [}

// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
{
8 z) K: y; |% _% m8 D# }        //一共进行n-1趟，i指向待排序序列中第一个元素
3 R+ k) O7 K' Z) p  {- A1 h6 c0 ^    for(int i=0; i<n-1; i++)
0 t3 I! p% U% k* R    {                 
! x8 x7 ?& o- Q' M$ V  G$ d) a        int min = i;
" u1 N6 k. L" y# z9 s4 U. H; k        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
                min = j;
" {' A0 n- s  W+ i) w' |' q        }
, S/ i# X2 z. _        if(min!=i)                     
            swap(A, A[min]);
4 \9 ]( Z1 Z5 K- E& k: \, o    }
' ^) p; S  O6 I% K( L}
% q1 m7 X" l9 {
1
2
3
4
5
6
7
8 Y& s) p& L: {5 n% f9 w8
2 h% j& v# N9 @7 v2 x6 J% j9
10
11
$ a# e+ L: Q0 U- o$ q7 W; c/ @1 P; n12
13
# k# X' F% T& O  o9 b14
15
16
7 z/ A. C. W5 P$ y9 O" g4 q3 U17
18
4 D9 {6 E4 v& B1 j$ e19
4 J8 g7 q' {7 j) Y( b& W. ~20
6 N  w( n1 l% z: Y21
/ c3 F- N6 r$ a5 j3 P22
: B" }9 \5 q" N: J4 r3 Q7 D补充：对链表进行简单选择排序
6 O  N% E) V  p& N- \
4 L3 S/ J0 f0 z7 F1 B# o5 Qvoid selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
8 p9 m; T, [8 S" E    while(h!=NULL){
8 i: `+ E6 T1 M        p=s=h; q=r=NULL;
        while(p!=NULL){
            if(p->data>s->data){
                s=p; r=q;
            }
# }$ d0 x  f. p; w& y            q=p; p=p->next;
# n! n8 B' Y4 |, b7 A8 A! ~        }
        if(s==h)
1 B" g* j& A# ?) b9 q            h=h->next;
- \0 o, m: X4 s        else
8 \* t0 Z& ^( ~0 h9 m- V& ~            r->next=s->next;
# [& i# u: O! K* i4 W        s->next=L; L=s;
    }
}
, Z. |# S" W, F6 }6 h$ I
: f6 z' I  n! Q1
/ {! R% Q) r8 ?2
3
, {8 d6 z( v: y7 k/ }4
' `1 `1 j9 `7 H+ |0 ^9 c! `, e0 `5
) L$ s# X# _2 a6
- c1 Q# a: t. c4 O  Y7
8
9
10
: I4 v7 h5 Y: X11
12
/ q; X  H' C& J1 H$ e. g13
14
15
+ \* c# [4 @+ D5 r3 s# X5 |9 `16
- p5 T; z" {, I7 }" F17
18
时间、空间复杂度
2 V2 q; D/ Q. m' [

1 N' o/ r( q3 y$ p, s$ D" F9 g

8 ?, U9 G* c" o1 c* s# \; q2 N& I7 z适用性：适用于顺序存储和链式存储的线性表。

$ N: c0 t: O7 Q. v3 g4 n2 j
0 T! z! y, X. a* w' k/ G0 I/ c
3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
0 [2 q# G. @  B. X堆是具有以下性质的完全二叉树：
! N* Y# s5 U; V- b& R, @) B  v每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
6 o) v+ \# Y) o( X或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
/ a9 i. F# ^1 H: Z7 b  H" R

; F! w0 \/ b$ E! G: }% v3 u
即：
5 v- O% |* e7 Z& ?8 W. f& ]. i& Z若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
7 s' ^2 g7 D9 p  n" C, z8 B若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）

② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
: W9 F6 K, v# ?1 q" g思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

& S, x) L3 G* ?" d7 _% E在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
! Z* Z8 {/ Q; A, a
# s2 R) I) Q8 C( B$ A检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换
0 X+ ^4 \& `" Y& Y0 I
过程例子：
% b5 ^4 \7 ^! Z" e6 R

2 s& h: \2 p$ R# a6 `0 _3 v) A  W
建⽴⼤根堆（代码）：
1 `: t& e4 Q9 c4 {0 Q3 _


( c$ r( p8 J* }// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
5 B" m9 d  m" K0 s) Y2 D    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
' ?4 F' l( a! I! h# e% k        HeadAdjust(A, i, len);
}

// 将以k为根的子树调整为大根堆
$ ~, X* {( y8 K4 L3 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])       
            i++;
        if(A[0] >= A)
* V, B' r2 Y5 z9 g& p$ J            break;
5 u) \* r/ ?, e) E/ x        else{
            A[k] = A;                        //将A调整至双亲结点上
5 h2 D; C1 R. U% q8 t/ c& ]3 ?            k=i;                                        //修改k值，以便继续向下筛选
        }
5 W- W! O. T: {    }
    A[k] = A[0]
}

1
2
3
4
" j+ V! m! q# E0 |$ a5
2 O6 @( G3 h  a+ {' T6
7
8
9
10
7 I) K* Y6 s' N# t6 E. u& D11
9 B+ P, s) J' D2 d$ _, G3 D0 A9 f9 g12
13
+ I2 ~8 o5 p7 `6 D* {3 R14
15
3 f- P1 m2 Y6 o+ V# {7 \16
17
18
19
20
21
* F4 I; @& h# y, Z$ b③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
: n) A( n* o8 H9 J# b& T7 B
" Q2 A) K$ M! u3 C% u堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

# ~1 \4 p/ a6 _6 }过程：
6 q$ _9 M2 c# m8 _+ O, t3 O
) h$ U* ]9 s& M0 I// 交换a和b的值
5 I! K. P- h: S5 O5 r+ Cvoid swap(int &a, int &b){
    int temp = a;
' F: N2 k* j5 U# U, Y% e! n    a = b;
: s0 a0 w) K; n    b = temp;
, b. N/ T4 H" |$ n% M) u& i}
1 j5 h0 D1 B4 C8 g6 b& r
// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
/ w% ~7 j6 x; y$ W+ q' U8 _, t# S        //初始建立大根堆
    BuildMaxHeap(A, len);                
0 m5 _& Z7 ~- W* U! t8 p0 U
+ [/ Q4 j6 ]1 m    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
    {             
) N# C1 x7 G2 B1 E) a        swap(A, A[1]);
* K1 }% |& ~+ v        HeadAdjust(A,1,i-1);
    }
}
, N0 |1 p) D0 ?# y" \+ {
1
2
$ u7 ], b' _- J& ~; f3 ~3
4
5
1 W6 b0 M5 N! ?# c5 C2 ?5 F6
8 D( [) |( s0 }$ y7
8 M- c5 D8 t$ D6 z! l! j' @* V8
2 w: u" S5 f; u* O; X: h. s1 i3 s1 y9
1 e, Q, c  V. w1 I- M( y10
11
12
13
3 q3 I# I4 z* g% U. w' F  [; l14
15
- x+ Y! U! r. A" O+ o! p( `. A16
17
, Y# A# G  L5 v4 e. X3 C; H18
) J6 X" ~, M3 o) H9 \6 E, c19
- K! c: e2 o( u: i. W: d时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
) G" O) @8 w' G0 F! P5 |故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
: d3 s6 C7 m. y* d7 J4 O4 k/ j% ^7 e
空间复杂度 = O(1)
7 O. L) U0 O5 I5 `9 w+ A3 R. z
% M/ f: w: l* G1 l+ D6 a6 E结论：堆排序是不稳定的
( e/ w$ {( g2 F, s

( r* |: l5 ]; B④ 补充：在堆中插⼊新元素
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
; }* P) F2 _+ m新元素就这样⼀路“上升”，直到⽆法继续上升为⽌

% n2 }  t3 o% {% y% P0 h

& F; D/ i# E& W, z⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
1 [" h- W8 i2 C. l" O& j7 b  }
2 e, y: o  S/ H9 y. g, x8 ~- Q1 r


: L# L8 u' u/ ~2 f! z
8 u6 b% w( J8 `6 h3 G( R7 e8 R4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个
  m3 e! \% K, a. O
; Z5 A: S5 [. s① 明白什么是“2路”归并？——就是“⼆合⼀”

# M1 b- ?5 R3 l5 N9 Q多路归并：


' U% O5 S* J2 d* I/ W  W" r② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
( k' ~0 J5 Z7 K( G" u. c9 z
9 R) l- m+ Z- S4 F: R  P! m9 lB[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

③递归进行分治思想【MergeSort(int A[], int low, int high)】


④ 总实现代码
* }6 @  L0 R% `// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
, @$ q6 ]& w2 p# u
6 h: S! \6 u; S, }$ E# S9 q// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
    int i,j,k;
* F0 p2 r  Y  r0 L. o4 l; g9 Z  \    for(k=low; k<=high; k++)
  k1 H, B" p* X& |; D! F+ D        B[k]=A[k];
    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B<=B[j])
! z; o" b9 O, d7 W- C5 ?            A[k]=B[i++];
        else
            A[k]=B[j++];
    }
# m6 M( a5 C  t( Y) J$ s    while(i<=mid)
* ^4 r8 S2 z- `1 U( \  o& n- P) G        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
: j: v) E9 g$ i0 ~9 N5 T, u6 ?2 h}

  |/ ?: z( Q. c
// 递归操作（使用了分治法思想）
, s3 X( d' o0 `+ {: `void MergeSort(int A[], int low, int high){
    if(low<high){
' X  m/ V) `3 v' ?3 Z        int mid = (low+high)/2;
! U' B. N# J! Y* V        MergeSort(A, low, mid);
; a- I) J9 `6 K; X3 O  ~! K        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
) y8 x% d5 }* Y  d1 P+ B& K    }
}

0 m% R, _: G! X- Y' K7 Y1
5 t1 @9 u# I! m7 o2
3
) [* z2 b; Q+ v& f6 r/ q* Q4
5
6
7
8
, n5 M; i; n6 m; f2 V9
# ^- t. N& \: h10
/ j4 q5 A# L3 ?! P- f11
12
( m7 d# m" I, G  ^# K13
14
" {: W' h4 S' f3 O+ A$ e15
# H4 w& B4 w; }$ Z# t0 ^16
17
' \& B! H, k) Y6 }  v  S18
19
% u3 _9 A2 H; K1 G20
21
22
23
$ C. ^. S9 s$ w$ [. s( }7 C24
' E  b# l5 x7 A0 a6 ?25
26
27
4 ~5 {3 p5 }0 r28
29
30
% r; I3 C6 L% Z2 e$ F时间、空间复杂度




' d. a$ t( \9 S. x  O5. 基数排序
直接看课本的过程图来理解P352
, X5 Z; x4 r% [
8 a1 }3 V* _4 Z+ f; C再看这个例子：
7 D8 z4 \' A# Y, R- g0 J

) a# D: s3 B$ m  y, b算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
+ j& ?' D- U. |- C. `$ g  f收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
4 t/ N' q/ S# m0 [/ X3 v: Z基数排序擅长处理的问题：
①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。
1 q' ?9 S! q/ f& g# G+ I$ f8 o算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
稳定性：稳定。
8 N! ?, ~* ~! f0 Q3 D

内部排序算法总结

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


" a) b, U" T6 E. e. y2 X: p3 q# P