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

杨利霞

9 q# i4 L& y2 i【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
+ e- n# v& ~+ u# b- z  y排序
- x; S  ?" E9 L: N" V+ e* V1. 插⼊排序
5 G9 k; \6 Q; s2 X' ]  }( G（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
2 `( o* ?" z9 g' g- c8 N# V时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
5 _1 o1 V* \& W（不稳定）1.3 希尔排序【多次直接插入排序】
时间、空间复杂度
2. 交换排序
3 L6 ^5 M, I% G* T2.1 (稳定）冒泡排序
时间、空间复杂度
/ L0 |; I; w" m3 x- x2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
/ o/ K( m7 i* m& h) {3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
9 ?: e+ q/ g0 n, T- Q3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
* D1 }- {% v* X② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
) X3 u  G$ S. v③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
& f! b- ~0 H2 ?0 J; Q④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
+ K! F5 L% J5 h4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
: V: M! b) k# q② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
! x/ V/ `7 i! |* u2 J! ^+ ~④ 总实现代码
) E; \# x" A/ h时间、空间复杂度
. J; M* g) f' m* D3 ^8 n' q5 {5. 基数排序
+ n- h/ s( Y3 y% e4 G内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

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

; D3 ~# `" [+ E  E5 H3 |7 [3 M算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
1 x$ G2 s0 y5 O% C1 i, F稳定的排序算法不一定比不稳定的排序算法要好。
  i5 x+ ]2 O9 [, b

) Z4 ~* H6 |  t1 F. ^) d5 o  H& [& {排序算法的分类：
- B1 H1 t; |2 f6 g内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

5 z+ y/ x8 W4 d1 k+ @2 Q: t7 X各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

' V( d4 E, W# @$ \: N4 j7 f6 m
( K) C; I0 L) }* z3 b( d/ R
1. 插⼊排序
/ r( F/ E: {* ?（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

/ h) f8 t( q" I, K9 q" F算法解释：（从小到大）


4 T( V6 d+ M, {  p算法三个步骤：

9 A! t( Q, z" J" ~3 O9 Q3 [- D先保留要插入的数字
往后移
插入元素
$ m- _* R$ U# K+ k/ l2 x" t
3 z' F; C  I! L// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
" H) D) I& j0 D' ]. \0 U% [) s8 @    int i,j,temp;
    for(i=1; i<n; i++)
' @$ K+ e  I8 {  l4 T    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
        if(A<A[i-1])
        {           
& x! ]) ^3 a7 v1 \            temp=A;  //保留要插入的数字
, e) }& p( h, |: i  i, E
            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪
8 {) L! `0 ~* ?6 e9 ?% R
# ^/ F& r8 m% }* L            A[j+1]=temp;//插入元素
6 W0 B" ~+ Q# I- ~- U        }
% I# \) L: U2 Z( d  ]! x    }
}
* `6 {- V* a* J; N% z: K( A
1
2
  x8 y6 `4 O% L7 @  e8 \- u3
2 @) ~7 x2 u) a. Z# n' g4
5
6
7
8
9
10
11
12
13
/ R* b& n/ M6 `- e% P. l9 V* L14
9 S) L! x" e" r  n) t1 p& y2 m5 d15
9 ~. Y# B$ Y* v* d' e+ ^  Z' d) E16
% y& L: j, g( a0 o5 |% _17
% G, u) P' L( c6 s' M6 w3 K3 }用算法再带入这个例子，进行加深理解

7 X* {6 R2 j# Q, H' w' \
带哨兵：
3 f* x* k4 x8 R8 {# j5 u' H
- ?! E+ K3 X7 T0 r: @3 u
- J2 ?7 g: j6 ?* L+ x补充：对链表L进行插入排序

void InsertSort(LinkList &L){
    LNode *p=L->next, *pre;
" U! p/ G! b7 X' a  n    LNode *r=p->next;
    p->next=NULL;
    p=r;
; A$ \1 G1 S; d& d: u6 N- m2 s: j    while(p!=NULL){
/ _7 g; `. Z# r, O2 }6 `5 M        r=p->next;
: l+ R8 ]3 S: D' Q        pre=L;
6 n( d0 k( \' h# ]7 k        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
        p->next=pre->next;
0 `9 k$ }3 y; i; T/ v* k        pre->next=p;
        p=r;
    }
}
# A$ F+ g3 E" t( g/ T1
% ]& e! o8 D) r# q2 r2
3
4
+ W0 x, H0 }! w# m& H5 U% v6 Q5
6
; t  g7 h/ N5 E8 V: U- u; j7
8
9
10
11
2 b; {" P% |; }# H5 j: O12
13
14
6 N5 t) P9 R( l" N15
* r5 N  T5 r# d8 \0 Q时间、空间复杂度
9 j& c$ a1 j# D- D+ ]. s$ I
5 G. I9 y4 b, h0 s
最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
最好时间复杂度—— O(n)

最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
) t, E( [4 V, S3 ~1 i& H第2趟：对⽐关键字3次，移动元素4次
5 C; Y4 [" _: y  O" \6 {& ~…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)

: Z* v" l. D: S/ b5 V2 Y


8 Z, Q7 ]: o. s3 [8 o$ U
$ j: X/ N  G! A4 Y5 x（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
# |- ^  ]0 L: U# r7 A3 j% R. L过程：
* Z2 C$ d$ m, b% z  d* d) ]1 F

' j  ?  ?3 a- K; k% L
//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
3 K$ G4 u& n& h" F{
' Y+ a5 [; E1 P, S    int i,j,low,high,mid;
: Z; T9 U6 ?  E/ M    for(i=2; i<=n; i++)
    {
; I5 ^$ k6 J9 n$ k& B9 s3 [        A[0]=A; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
; a3 A. d4 j+ y0 f6 u% U        low=1; high=i-1;
        while(low<=high){            
, t- |7 O; t0 Y, i' ]5 x% B            mid=(low+high)/2;
            if(A[mid]>A[0])
                high=mid-1;
            else
                low=mid+1;
        }
         //--------------------------------------------
        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];

$ a& D1 ~9 A) B+ u: X) n6 L# x        A[high+1]=A[0];//插入
' {+ y# H' D, |0 Q$ a3 i  R, H0 Y8 ]    }
}

1
% D6 H' ~, t) U% q3 M2
3
4
5
6
8 a: @) G3 W& ?) p. X7
8
9
10
11
12
  j4 S" [' R  _+ y13
14
15
16
17
& n5 C8 I) P" D" s; r, e# j0 H18
19
# E( B; ?  d) L  f6 w2 d20
' O" K' |! J+ e0 A6 [21
22
6 _, M" \  q3 k2 |23
时间、空间复杂度
9 B  e8 q" ^1 j# P空间复杂度：O(1)
2 ^) T- W, [( _/ a
6 \7 y  D: `: U3 ^2 n. P- [- C【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)


$ y( J' r0 }, \3 }( j（不稳定）1.3 希尔排序【多次直接插入排序】
1 {6 i+ T" [8 w) K9 \! d4 O是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

! Z; Q1 \1 n8 E; R" [& }算法思想

3 V# I. F( ~4 M  c希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
1 p) Q3 k. N" u9 e随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：
" ~8 D" |1 r' y. [" F


代码实现：

//从小到大
+ o+ h! b- g) Uvoid shellSort(int* arr, int n)
& _. Y/ G( w1 P{
        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
" N' P2 _" t- h% S        {
2 F: y- ]0 T( v8 K! X0 F/ R            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
3 }( t% u: B0 p' S5 u7 [/ u) Q                if (arr < arr[i - gap])
                {
% F9 X7 Y* V& B7 v3 J                    temp = arr;

                    //后移
$ y$ ?+ M: |% {" b# n; ~) g                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
/ N6 s* k% S8 x4 x  }6 D/ u1 A4 Y                        arr[j + gap] = arr[j];
" e" }, B5 i( C
                    arr[j + gap] = temp;//插入进去
                }
            }
  b. j$ v( e+ I1 j) w- r& \            //************************************************************************************
        }
}
: p/ P8 Z8 a) t1 x
: d" Y# n; A- s/ v1
5 |4 w; c! V% m0 h. v7 v+ \& @2
+ d* ~+ b$ U, f6 i3
% _0 X9 G# m! R# {4
5 z( X+ H- I* ~6 c1 K# l0 K5
5 P8 c* q" m0 c  s6
7
& i/ @' J$ F$ p8 k! Z  M8
. ?& ]( G4 l: V: n9
  X" j4 B% ^# E, |, N1 C10
11
  T' `' P8 ]# b0 o1 _0 S+ ~12
13
& f- ~0 E% M( g14
15
16
17
8 T% A$ q3 ~+ ^3 P- \* ^; c18
19
20
21
: H# A, R: q2 {* X& j1 t0 E& U+ u22
5 p9 l+ t, t  M% [7 s23
24
1 y2 l" S1 L8 L- _1 W3 \时间、空间复杂度
空间复杂度：O(1)
5 @" |! L; k& [! w! T; M7 r
% h  v/ \3 z* P! ~时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
/ d+ \+ m) B9 U7 p. w4 d
稳定性：不稳定！
* A+ x: D8 n$ ~+ j) d" {


7 `3 r) L  U" D( m# m# E( w适⽤性：仅适⽤于顺序表，不适⽤于链表
8 s4 c# O/ s! k1 v2 `: j
. Z" r- Q1 [5 C
8 l3 i% H+ b  b; T8 {
4 n) C) g# a1 f- w- `2. 交换排序
% |, L: M' x' a4 k2.1 (稳定）冒泡排序
$ Z! K4 \; V% Z" X; q, ]$ V6 E英文:bubble sort     (bubble 动和名词 起泡，冒泡)
' t9 ^0 X# a) V从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
& W% |/ q4 L& ~4 F/ G8 p
每一轮比较会让一个最大数字沉底或者一个最小数字上浮

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
- ]0 \, W% o2 }1 a, r, ]+ F
0 H/ r2 \6 b0 P7 L& j实现代码：

* r& y  Y  |" T8 L//从小到大：
( A1 F$ A* X  p) Ivoid bubble_sort(int arr[], int len)//冒泡排序int*arr
{
        int temp;
  o: @' _  \- V+ q/ \) q5 j        for (int i = 0; i < len - 1; ++i)//循环比较次数
9 c6 B2 |! d, @1 S        {
8 M7 @/ @+ D4 I/ {/ O& A                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
. ?& f: ?6 {- Q8 \2 ?" |                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
                {
                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
% B* e! F- w' V                        {
  }2 ^' W% w9 U) A- Z                                //交换两个元素位置
                                temp = arr[j];
6 t3 T  n- e! U" n$ ]" y' i                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
                }
8 ]( E7 D6 K- V* {5 z        }
+ C9 ^/ U5 n* a1 e}
1 Z) l' a4 c  o  Q8 `0 \2 f
1
6 p  V) _; P( `) ?" k2
- r3 n5 F7 U) K3
4
5
1 _, ^" P$ b6 x& r" C$ s6
7
8
9
10
11
( J6 z- |1 ^5 |12
' x; x" l1 b1 ~, o$ m* m13
. }$ t1 G; f- t6 D% @! A3 [14
15
9 }3 x$ D% m8 |% `4 Q& q16
17
18
19
9 Y& g6 v9 A/ f' U优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
, d7 u% p9 v+ U( V
//从小到大：
void bubble_sort(int arr[], int len)
  u: ]- u* k+ d2 W* G{
        int temp;
        bool flag;
7 B8 }( \  `; Z  h        for (int i = 0; i < len - 1; ++i)
2 n1 p4 E) ~6 U0 A; u* C0 _" A        {
/ v( ^4 o; o, P. a6 w$ r            //表示本趟冒泡是否发生交换的标志
+ V& g3 I+ p; d8 c                flag=false;
               
                for (int j = 0; j < len - 1 - i; ++j)
9 W! N; C. n7 F- s                {
! y8 l- v1 m* z3 n2 M8 U( o; n& m4 q                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
                                temp = arr[j];
                                arr[j] = arr[j + 1];
$ e4 N( n+ b7 v& |9 \6 Y                                arr[j + 1] = temp;
                                //有发生交换
# R7 Q4 H( \% `5 t/ H6 u                                flag=true;
                        }
8 }% e% }0 C8 s" @8 o! w8 l                }//for
               
                //本趟遍历后没有发生交换，说明表已经有序
                if(flag==false)return;【1】
7 K4 b: k/ Q* w) B) h        }//for
1 r0 U  |, o  t2 K( @  L1 R6 n}

4 {4 D. h5 b% N; M( M( ]( o1 x1
2
& X0 r, d4 R1 k$ Z# Z) S/ U2 b9 V/ O4 G3
4
, B% v5 c' G: L( Z) f  j' ?5
6
7
8
8 E6 l9 {. c% R0 h  b9
10
9 S7 w! G' e9 W* [( [: E1 x11
' w% }' k, y1 I5 A1 |12
: b! @' c$ ^7 k! }2 \% w4 ^3 Q13
14
: ?- i- \5 |0 p2 i" I15
  U# j1 L, ?) K- [1 e) h16
  s2 J$ b1 O. S. A( \- T17
18
19
9 x, j( g! `' k! K20
21
* k, ^2 q+ Y& f: Z22
23
24
( Z. I8 b2 H* u) v25
, N0 g, H2 Y3 T' w' E+ a1 ]7 \1 A26
时间、空间复杂度

, R( n, n/ A" F3 y6 v适用性：冒泡排序可以用于顺序表、链表
3 d- Q- E% |! q% Q) n4 Z
9 ~& v& A* l5 I; ^) \; f


7 A' v4 i6 m; Y: f  j7 k9 E* ]2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
9 i! k3 M, p  g$ I. q4 T" k  y. }算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
7 l. e- `5 v7 V9 D7 _- }使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

1 X+ f0 ^4 a% C然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
( m6 I* y6 d) w/ X7 k( j
' e0 d& n" _5 V4 h3 T. }$ Z划分的过程：
( a  k2 F; h. N" f/ l
5 M! h. `  b& H; r( r6 q; `初始状态：取首元素为pivot，定义low，high指针

首元素为49
high指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置
0 j! e- w" D2 v9 e2 C0 n
- q8 _9 c5 a( R1 B% W* |
7 p) ?1 {/ B1 b5 b8 D0 ~7 O' {' r
; ]' U# P$ Y) e2 c! v+ c
& `3 b. R! ~4 \# E' b' A
// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
$ t% f. Z+ _1 K2 ]6 ^0 d4 \9 e' P        //取首元素为pivot
    int pivot = A[low];

! P. k. v& X  V& @! n# v% {    while(low<high)
    {
            //先是high开始向左移动
9 o/ X% `6 z  K; R% ^  F        while(low<high && A[high]>=pivot)
6 n4 E" S8 Q1 {0 e3 H) f            --high;
        A[low] = A[high];
: d5 X  V& z  S- z) H3 a
        //随后low向右移动
$ Q5 y5 }5 s% I+ n; V( T# C0 F5 t        while(low<high && A[low]<=pivot)
6 F3 C) e2 o; m* x            ++low;
        A[high] = A[low];
    }

    //low=high的位置，即pivot放在的位置
, h3 p' M( E  m- s  I    A[low] = pivot;
9 x% U: |6 e; Y, l" }
# V6 @& J$ A" L& l# W- k2 j# \3 N# @' v    return low;
( _, o. ]! I& e- @  v+ c8 W% K}
& t3 n& w2 i- L; a( U- ]: m/ N6 @
/ y# K6 x5 Y; e2 ?// 对A[]数组的low到high进行快速排序
, J0 `0 w1 Y  l% ^. Ovoid QuickSort(int A[], int low, int high){
    if(low<high){
7 c8 v$ G/ Z& g- ^8 y        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
3 D4 e6 M# `  b: s" U    }
}

1
" b. l6 Y9 T* x/ A2 `# k5 {" `0 Y9 k2
( c  T6 O6 r' T) B" F- g3
4
  @  b( R8 K0 S5
! n3 N& [4 h( ^+ D7 o1 z0 H6
" z# V# r, g. c5 d7
4 ~7 I" F) k" l8
6 _) y% {2 u, `5 z2 d9
10
: |$ Y' }, D) R11
12
13
/ p5 T* t5 |; [8 f, v14
15
16
17
18
$ y3 J; J+ q9 o1 C" }19
20
21
9 T1 j6 Z, w8 x$ R0 o22
/ q7 d- ]; c0 w7 z1 X6 F! ~23
7 V' E, R0 i5 s# I24
25
. H" [- z) s- S" \: z; Q* v26
27
; A3 Z; P9 F  ]) A28
29
- x; F. c3 C9 V: M  Z30
" c2 }2 h6 F5 S5 r7 g" A31
* A& c3 y& z$ e" ~( l32
时间、空间复杂度
/ a4 [1 v/ e5 n5 ?) l/ M
. f4 I1 V2 O( B. M+ D/ i: _, F" Y
把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

! w3 L. u: A) O' Z+ X3 h$ r0 \; i! En个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n
, D# W3 \+ T/ U0 r. D$ u
时间复杂度=O(n*递归层数)
% n8 B0 }$ b7 c5 x, F- \3 R; K最好时间复杂度=O(n * log2n)
2 H1 S$ \, P  M+ c7 c, W. [+ R最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

$ Q& V! q$ y7 P- R# Q+ c* T/ V$ {+ j空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)
# \$ w- ]- s: N/ e  ~5 s2 n+ D
最坏的情况


/ A  X, e2 z+ [
⽐较好的情况

' v4 o: c2 _" n
3 k! Q1 r6 \- ^8 ]* f: x
; b- q7 n( S1 U& t不稳定的原因：

  Z0 [* U, N* F9 x
/ u% u& n7 _- Z# h0 ^3 K1 A; ~
& x# }" \: a6 k3 L$ d
# z' ]' u. c7 ~- j+ z# C! n2 E7 q
8 s( I6 ?" w4 a/ g3 O7 l3.选择排序
/ [7 }4 i( _& j7 O选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
9 J. d# s3 F& s
: A) \6 e; D' k( y  P3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
# }! s" u, j: N# s2 s$ r( n

# Z0 ]& y4 v/ T8 X7 q
9 [( v8 |" u( a9 a* o: X// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
) ?( P0 s" P9 P6 A    a = b;
    b = temp;
5 `- M! K7 y; o  m}

// 对A[]数组共n个元素进行选择排序
0 R/ t6 B* M7 O$ bvoid SelectSort(int A[], int n)
2 Y6 w/ Y/ n  {& j: }- @{
        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
" |0 X( D. [/ n! X8 f    {                 
) e; K1 R4 J8 S1 z' ^$ }5 i6 c        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
: G5 M: Y5 k/ f0 d7 u$ v            if(A[j]<A[min])
                min = j;
        }
& Q: e7 ^; y" b6 u/ l7 k        if(min!=i)                     
1 t) Y0 B# l4 m4 K            swap(A, A[min]);
( h2 d3 `* X& R$ ^    }
}

9 O3 J6 C0 f+ G- T" p9 C5 M) k1
5 c& z: B) V% i4 f2
3
4
; y0 f: U  S, q. v1 s: U9 l5
6
7
8
9
10
+ S$ ?0 D3 A2 q! \7 o, X* \- A11
12
5 L% C' g, N# J. N+ z13
14
% d4 z7 c- p8 W; p7 |& r  B# M1 |15
16
17
. Z3 k3 r! ^! s! J. G% K% K6 `18
& N! t  W: h7 ]- y8 ?' D" w4 }19
0 g* v0 l7 x8 H+ b! Z+ K20
, S: [4 [7 `' w0 r/ |3 l. T21
4 P6 O& E& }+ \% H- y$ c22
补充：对链表进行简单选择排序

void selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
. {0 F9 Q+ R5 K% {  y: B: r8 i4 J    while(h!=NULL){
        p=s=h; q=r=NULL;
        while(p!=NULL){
            if(p->data>s->data){
6 X8 q# X! h" r8 s- {4 Y- o                s=p; r=q;
            }
* p" `$ v6 P" h  x- Y; ?            q=p; p=p->next;
        }
        if(s==h)
  r7 x0 Z  h4 v! @            h=h->next;
        else
" p0 A! ^& o  U+ X# ?. e1 @            r->next=s->next;
        s->next=L; L=s;
    }
}
4 w- C5 C7 z! P0 J( ]  e/ M
2 Z  ~4 d; I7 m7 S/ g3 b) K1
3 _* a. r; N/ C3 @4 i2
3
# i. Y  B) G: O: m. r7 o/ A! A4
5
3 F0 k; o# c2 j$ ^- r" l6
& |  w8 m2 N' N; c9 u3 Y7
0 ~2 @3 H/ \. n  C9 v: t8
  o; U8 M' M! Z9
$ M% g$ f5 A% h2 G5 h5 _3 f9 z! a10
8 s- d9 M* P( h. F6 g! V) n11
12
13
14
* j. s" M# o5 W4 \7 I# I1 x15
# P9 b7 a4 [& B$ {2 i16
, _6 s2 z8 Q8 D1 _$ M17
" s" {, B9 D& l0 c  }" {$ e18
) G$ J) E1 O- D1 _- a( U: T: s, J时间、空间复杂度

& P& P; P* b% I- O! x" m& I

1 W( i5 V7 x3 y5 m% n2 B1 o
, p; r4 m8 O8 w适用性：适用于顺序存储和链式存储的线性表。

% x, \4 m# i, t. R  M$ g" U) v4 z3 }
$ w  B9 n1 T) P' E
, m6 ?9 @2 a6 O) b+ ?  X3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
3 @; q* }  l( u, ~: e' p! L7 R$ u堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
& j7 K* r/ r% Q/ J# h4 B4 [或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。


  m% [, ]1 R3 s$ i3 F+ i+ e. ~
即：
  Z& K: q: p/ z4 F9 D: X* ?& H若满⾜：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）—— ⼩根堆（⼩顶堆）
8 @2 R  {0 o  v
8 w' T: g+ a( X! l# I3 P) Y② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整
  X4 J6 Z/ |0 u/ k* U
# M: k$ T& U3 C2 h$ I7 t6 \在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
: }/ d9 G" I) R2 O, i/ c( G
/ N% b/ }& }, b( R$ a检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

过程例子：


8 [0 b- @: |* H. o3 N2 p
8 g8 u! y9 \# j/ I建⽴⼤根堆（代码）：


9 |2 J9 |4 W- P& m: u( i2 j
; m: d# m% Y+ ?9 w// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
1 _* d3 k: G2 `& X  m        HeadAdjust(A, i, len);
" D: |; H/ P- f  \7 W}

" I2 ?' ^; l& E9 G- C// 将以k为根的子树调整为大根堆
9 h9 R" w1 e) wvoid HeadAdjust(int A[], int k, int len){
6 D% |  f% A: p7 [  G. o    A[0] = A[k];
8 |- j- N* w2 K    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
' z% ?( b7 Z( P4 s. F            i++;
1 I$ i* f2 p" q4 X% c2 p& t6 \        if(A[0] >= A)
            break;
        else{
) B, g/ @, f; F8 X            A[k] = A;                        //将A调整至双亲结点上
2 I1 ~; c' t% b5 i' ]            k=i;                                        //修改k值，以便继续向下筛选
        }
" \2 Q5 s  o) R    }
    A[k] = A[0]
}

% W, s* k0 w5 ^! t6 ]& E# v1
- n% g$ R8 l( d3 q# J3 w' e- E2
3
4
5
% m% U. J# @9 C1 v7 o6
7
8
+ ]; j5 B- h/ M9
: {. V- D# p5 S+ C& v7 E- E10
' z- @" w# f! H! ^& R* F11
2 z  W4 `- k* Z1 |12
5 T! J9 I7 Z0 x7 U# S  j: c8 @0 m( C13
14
8 ]$ Q& c$ Y' j15
16
; Z! t$ P/ V0 m7 h/ ?; s& K7 C2 ^17
18
19
5 F$ G+ v5 H; B20
21
& @6 }; c, ]: G# j5 _* P( @③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
7 {8 t/ Q) j/ m% }+ j3 j
0 E+ F3 }# @+ K+ x堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
0 B5 Q! h$ M" g
过程：
! j- L; `" ~9 l( i5 M9 f; l
' ^+ b( y7 ^4 f  A9 C// 交换a和b的值
void swap(int &a, int &b){
0 b5 h4 C2 {3 z' _    int temp = a;
8 V0 B; ~5 `" E" N+ m    a = b;
* D% e; V- W) g" _9 o- b  Q6 `    b = temp;
}

; A( ]1 n$ ^, R, z  q// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
        //初始建立大根堆
6 W. o' I* g. V% j0 `4 v9 f    BuildMaxHeap(A, len);                

+ X1 _4 v' w5 V# v9 Z' u9 c; d    //n-1趟的交换和建堆过程
+ x% J8 Y+ e4 l+ k. [  Q4 q* Q    for(int i=len; i>1; i--)
' Z+ s" d# a& `# x4 }    {             
        swap(A, A[1]);
        HeadAdjust(A,1,i-1);
+ P! y$ N+ _4 Q* G0 s- Q    }
. x: N$ D( h* l1 n  _1 m% E8 G}
; L- e% D0 e, {7 l
1
# Q3 h" R" N2 G. G2
' J& g4 e9 l7 d4 z3
4
; b' D% }8 f  }4 w5 o3 D; P) V" R0 f  F5
9 p$ r  E/ Z; T! _2 o5 N& @6
7
8
9
10
11
12
0 Z: K" L. D# T+ m3 Z13
14
* v' i& q; o; g* |! O& r! Y4 x15
1 A4 _* U/ D9 R2 f! ?- e16
17
18
19
时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
; v) F' a0 Q1 x: }9 ^0 w, D* H) N故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
% Q# i4 M: h6 G" t  P' I- h- _6 y
空间复杂度 = O(1)
  {' F: m0 X, `2 H4 T7 o
结论：堆排序是不稳定的
) u# S5 O7 h+ ~: U/ \
5 A* @' G" J* S* T7 H1 X
) r! _& Z9 A6 J8 m④ 补充：在堆中插⼊新元素
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
0 }' X- J, n5 F5 {/ x/ b% f新元素就这样⼀路“上升”，直到⽆法继续上升为⽌


1 G- t5 Z4 [! v
0 _5 C" R) p$ F, _9 ~& B- B⑤ 补充：在堆中删除元素
2 k/ S8 d2 X% @; c被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌



2 J6 b" D6 h* _4 ^+ |1 l& |

4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个
: F" _, ^7 _; `5 R9 ^5 \3 Z
① 明白什么是“2路”归并？——就是“⼆合⼀”
: T$ ?  ]& s  o) ?! w
多路归并：
. l! z7 c% K0 @
9 b' q9 D( q5 A! M1 O; I/ R: e- p
: _9 U! A5 G8 E② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

$ Q' p, {; ~1 J+ BB[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

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

" [% V8 V0 |  X2 w
  O0 D2 W5 k! b3 Y3 ~6 ^, ~④ 总实现代码
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
' E  d; J. M: Z6 [
// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
. n  u+ h! u4 cvoid Merge(int A[], int low, int mid, int high){
( f' {! S: O9 |    int i,j,k;
: U$ @/ {: s3 A    for(k=low; k<=high; k++)
        B[k]=A[k];
8 _9 {$ C# A% g, H8 U9 p    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B<=B[j])
* \5 y( m- E% _& H& M            A[k]=B[i++];
. h6 z, d! @3 V$ f: O! T        else
: J, |% `% c4 p. n: N            A[k]=B[j++];
    }
    while(i<=mid)
        A[k++]=B[i++];
! r9 C' L" W- i/ M& T    while(j<=high)
+ P. u$ v" W# U0 l4 |% R        A[k++]=B[j++];
! C  f5 i( i2 z9 Z2 h  L}
. V9 o5 U7 B  V7 S7 S" W- p
  L( Z, t" V7 Z' [8 }8 v
7 R4 ?. {: Q# |* Q// 递归操作（使用了分治法思想）
- g2 E, r2 V2 _& Z7 t$ ?! s2 }' Avoid MergeSort(int A[], int low, int high){
' S( X" V  X9 c3 G7 g    if(low<high){
; d2 p+ `- ?& s. d' |        int mid = (low+high)/2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
9 ~5 K) ?+ t% ^+ c        Merge(A,low,mid,high);     //归并
! ]% |. k- }1 j$ i  w' [9 I    }
}
, O$ z7 b  c2 e; z! L, |: w+ o4 f, q! D  t
# `7 j9 X0 \! }! m4 g: _1
2
3
4
5
) ?5 t' D* p) D' X( \6
7
3 T. Y3 E+ N* m: X/ }8 f9 o# |0 a8
9
10
11
0 i% g3 U6 N, ~. D. e4 }12
& f! L+ f- l% G13
14
0 u( q. H& P$ r, H15
16
. k; i5 q: v5 c17
4 U* L3 _+ w. v) ?( B18
19
" q3 W0 r4 z9 D1 j20
21
22
3 }" Y+ X, v" C" [  ]9 c2 F' G23
: S" D7 j9 v9 |; T; U/ I24
25
26
6 L" U8 N% i1 z9 o& f7 m* g* c( P; D27
  O4 \2 s9 Y+ f- s/ D5 ^28
29
30
时间、空间复杂度



# e7 ]& C, S* N% S4 r6 G; ~. K
5. 基数排序
直接看课本的过程图来理解P352

再看这个例子：
0 g# g: y  [2 W% k1 e' y7 s9 z

算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
& d" K* X  o0 U! v! T分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
+ w9 l7 j& c3 \  |9 v2 x; q③ 数据元素个数n较大。
9 h( \% J5 T' d( b. u算法效率分析：
+ g# ~$ L$ N% a时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
  \# S1 W& x9 p, _空间复杂度： O( r ) ，其中r为辅助队列数量。
; x' L1 Z4 C7 |; y. ~稳定性：稳定。
9 S% g* ~3 I2 n+ {
' _; W, `% @6 C
内部排序算法总结
) r7 B2 M( B+ n$ Y2 g% d- a8 z4 Y
% S; P, W1 q* n; Y6 f————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969

+ n1 z$ ?" ?1 ]