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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
$ C- ^, A) c, \+ K8 D文章目录
排序
1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
（不稳定）1.3 希尔排序【多次直接插入排序】
& i* j* w% U+ U. k: z. q6 h时间、空间复杂度
7 B/ ?: Q" X7 k9 r  O. v! v* [2. 交换排序
8 y$ G8 ?3 y( ^4 Q: b- a2.1 (稳定）冒泡排序
% @4 i9 S8 p" ]时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
3.选择排序
" |5 I& S2 K! h+ K$ f, J* ~3.1 （不稳定）简单选择排序
5 X# S+ f9 c4 M& b8 b6 g9 l时间、空间复杂度
5 c1 I, c$ C' S. d( U6 _3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
" p/ `1 _6 }" s' Y5 h② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
+ m/ Z" v( `0 h8 B8 A④ 补充：在堆中插⼊新元素
  n. ]- c: f) u) k; a4 T⑤ 补充：在堆中删除元素
4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
; a5 b8 _9 A5 L2 {时间、空间复杂度
5. 基数排序
内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

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

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


排序算法的分类：
1 u+ G% Y6 ^8 Q* o内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
1 o1 U' Z# u1 F* h: E' l# @2 E
各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
3 O- |  y; k2 l4 M
6 V. e- B4 o7 l
5 _1 t5 ?2 `. |
1. 插⼊排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
) h" {6 K- F. t2 d& d- w8 h; o基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

算法解释：（从小到大）

  Q( O* j  i! x6 ~0 I
算法三个步骤：

先保留要插入的数字
往后移
插入元素
, O0 F2 C! f( Y% [3 c4 Z: L2 [
// 对A[]数组中共n个元素进行插入排序
( y2 @- o9 f% z" Nvoid InsertSort(int A[],int n){
. x: B4 E% Z! v# Z; Q6 \3 y    int i,j,temp;
    for(i=1; i<n; i++)
    {
/ t3 {/ a% L) m8 q            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
  L% }, r% A7 y* r0 A        if(A<A[i-1])
) y( ~% |( z8 N        {           
$ T* ^# i: f- i. \# r2 `            temp=A;  //保留要插入的数字
) S& S" @0 t* o
            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪

            A[j+1]=temp;//插入元素
. P8 \+ b$ G: e& K4 R        }
    }
* }" @% B8 B) J$ v" h}

! k" [6 j+ w8 F, G1 m% M1
* M* C, Y3 A/ D% b( o2
% E, C( R- a; O9 x, B2 l. j8 N3
( x- H* s; t+ m* L/ F4
5
; a# {& Z2 w) I) x" P+ d3 [, E9 |6
7
" P! \! B$ X0 F; \' \4 \3 R8
3 q7 S/ J! u2 w0 L9
; j) v  J% y& @# \10
11
12
) a5 P+ X3 \4 G( ~% _13
14
  v6 y5 `- {# q1 {) K, V7 k15
$ g: g0 k: Y% M/ S! v- u! c0 t16
' h! @* y6 {( B; l1 }17
: X0 b& f( }. m6 I* h用算法再带入这个例子，进行加深理解


/ S$ J: B/ M4 j9 x带哨兵：
( N! g+ \& x' W- S

补充：对链表L进行插入排序
' G, ?. W: ?, l. ?$ Z
void InsertSort(LinkList &L){
# h' F; Z$ s& \7 b4 O    LNode *p=L->next, *pre;
$ U) N8 D6 f& n) T+ m* F    LNode *r=p->next;
8 }/ d1 E7 R9 [1 J9 f, p( l    p->next=NULL;
    p=r;
, f$ R" W# V$ v. X( r    while(p!=NULL){
        r=p->next;
        pre=L;
# y/ B7 P! D  m6 Y; }+ p- R1 p# b4 y        while(pre->next!=NULL && pre->next->data<p->data)
1 F6 ~) T8 P& e0 r            pre=pre->next;
        p->next=pre->next;
* }) P% g) X; o        pre->next=p;
        p=r;
' ?& Q" G1 j, @4 w8 |    }
}
1
9 Q" f, l" L# h7 M2
% R( B$ ]" q" l" q$ g' t3
" L3 j$ h6 U# R4
5
6
7
8
9
9 E. E) H6 Z- L6 U: a1 {10
11
12
& v6 u( Z3 \1 h# c13
14
15
时间、空间复杂度
7 g* B! X" l! S8 `( T
% I$ f* U# S/ Z" b& i
最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
最好时间复杂度—— O(n)
' M' k# C+ ?% Y3 u8 L9 \3 C" S: B3 |
最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
第1趟：对⽐关键字2次，移动元素3次
# |3 V; e1 ~) ~2 P% y2 I* y第2趟：对⽐关键字3次，移动元素4次
! F! o4 P; x) D: R  r% Q/ \…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)



1 r; j7 I# [5 K7 v4 {" h
( D6 {# B, V4 d: ^8 K
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
1 ?) h2 C! Y; V) ^& r: T  x- @过程：
7 x. w- I# u! ]' y8 }


//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
! _# N6 o9 X' R{
    int i,j,low,high,mid;
3 _- @) _7 \. u; e    for(i=2; i<=n; i++)
% g$ v& \# g* h    {
4 j3 R$ a: n+ G6 c8 Q        A[0]=A; //存到A[0]
( \/ l* }+ X: Y6 H& r6 @* q        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
        while(low<=high){            
            mid=(low+high)/2;
0 O' F0 O2 j( f' X' A# ?2 ]            if(A[mid]>A[0])
                high=mid-1;
6 _$ Y* `* x6 J            else
                low=mid+1;
5 C! Q1 ?9 m) b! H        }
         //--------------------------------------------
$ l6 W( X, P! O1 L  k        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];
, l4 |( ^& P- {# f0 s3 Z
        A[high+1]=A[0];//插入
2 }! c! S! R; W5 Y$ ?! l    }
+ }( `1 W1 {" S2 r}
' v! g. b4 o9 k$ X- V! x* K
1
3 g1 @; J% @3 r" [2
3
4
5
6
7
$ J7 u. L# g7 g9 |8
9
, w2 ]8 v9 ?( z# k" D! Y! L10
11
( M( J, X3 O1 h; ~+ {12
6 p$ T  u5 X7 j: D13
14
* R0 S7 a" `& L3 v9 a15
- B1 F  d2 P% J( l) Q16
17
' u! _- d" r8 ^4 w18
( w4 o! d* d: n8 @6 `4 U" A19
20
21
22
) d2 |8 J* h5 S9 H# N1 |1 _  Q23
时间、空间复杂度
& a; b, a3 B/ o8 F1 ^5 H空间复杂度：O(1)

9 I6 k0 ~5 z% A# S【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)

; ^! y/ i* l, _" t8 W1 r! \& ^
" q- ^. T' G/ M  O: ^, Z# X* e0 y- G（不稳定）1.3 希尔排序【多次直接插入排序】
% R' w* A, A# g% b# K是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

算法思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
+ n& n8 J% O: I0 K) g图解：
2 I* ^9 @; f; ^+ |& @% D

2 ], s0 g: R  J% a+ a/ V
代码实现：
; c1 s0 Q1 q. Z: y
//从小到大
( |. f1 j/ s' s6 }* D( }# Dvoid shellSort(int* arr, int n)
{
" ?( I; t3 R$ r        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
" B8 o2 X9 `6 s( J        {
. u8 {4 ]) \1 f' F; y1 |            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
2 c0 Y; ^! |& v7 _# a                if (arr < arr[i - gap])
                {
# Z- K( J  d& @8 f8 D8 D! H3 @5 M+ L                    temp = arr;
/ t9 g5 u5 u+ ^& ]# q7 L3 ]
# K" k8 b: h: P5 W3 L! f+ [                    //后移
2 D' c$ W) I4 Y& M$ Q& v                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];

                    arr[j + gap] = temp;//插入进去
                }
            }
            //************************************************************************************
        }
}
; _7 S2 L  ?  Z2 c8 |
1
9 e: u" p( o: R2 S& {2
4 b6 A2 g4 Y0 y. B2 X, {3
4
5
6
7
- U9 o8 Z0 [# r. g( m6 H8
$ J4 ?  @4 y: C1 m! L9
1 t( I. g* h7 J3 V6 P( P4 O* g$ G% a10
11
* R' X, v# j4 i& u' C12
13
$ t) b. z9 y- m, {5 g) P14
9 S, w* }8 M6 d+ J15
16
17
$ x( j, d( I* ]" U18
19
20
21
22
23
! t% p; M. }5 F) u7 o" H: i24
! v+ d! I) _2 Q7 p0 V4 x时间、空间复杂度
空间复杂度：O(1)
* [( X' q8 ~7 H' X- R) d
6 @& B+ q, {+ W/ B时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
9 G( A0 [% Q! v. n
1 ?+ v6 W  f* I! g4 I# Z稳定性：不稳定！
$ P0 q: e: J  ^. F

% A: {8 k& k" m# l1 h0 U. i( i
适⽤性：仅适⽤于顺序表，不适⽤于链表



  O8 C' X3 p. d& w& L# `: l6 p" C* x2. 交换排序
( H, [+ [- B) u+ g6 c; t6 j2.1 (稳定）冒泡排序
* c7 d8 Q% z; G: X+ I( x英文:bubble sort     (bubble 动和名词 起泡，冒泡)
从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

每一轮比较会让一个最大数字沉底或者一个最小数字上浮
& ^6 x  ^/ H0 h/ }- q
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

实现代码：

//从小到大：
2 p7 q; T7 E* r5 dvoid bubble_sort(int arr[], int len)//冒泡排序int*arr
{
( b0 \& P' f, e  W( p  I# k" V        int temp;
( y. m+ x/ ^; Q) h/ d3 Z5 R4 H        for (int i = 0; i < len - 1; ++i)//循环比较次数
0 y% C. _+ }$ g        {
                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
2 d% L7 N' O. l) i                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
  [; j- e7 c7 q* _5 s$ [7 v/ }( B. b                {
3 `0 W% i5 V$ S  C( ?4 m& e* M                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
$ Q2 B8 {* J- X* ~' V' S& v                        {
3 t0 Z3 S- |" h1 |                                //交换两个元素位置
( q3 M! c- K% h( G' z% A1 z* F                                temp = arr[j];
                                arr[j] = arr[j + 1];
6 i/ c) e+ M' s                                arr[j + 1] = temp;
                        }
                }
        }
& Z/ T1 \' z' h8 ^; I+ w* H}
, r0 x2 b$ B% h6 w" v: m
1
2
3
4
5
6
- N( _2 A% R" Y1 ^/ ^8 D7
  R7 v' g1 Z9 |( `8
8 c; c- [+ Q) \8 q# o9
. F; r' w, Z8 G* C: g10
+ H; H" j5 W4 b( z8 d$ @11
& B5 H/ x# `) v( ~12
13
14
15
16
17
2 C/ v  o7 a/ m+ u18
9 A# H4 H0 `  ]9 d19
' ^4 t% i5 u0 X8 h  R优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
) Z) ^* A6 B3 x$ u- ^% T
//从小到大：
void bubble_sort(int arr[], int len)
( Q: S# l, N+ o8 Q0 d{
        int temp;
  m: |* S' j" v5 m        bool flag;
        for (int i = 0; i < len - 1; ++i)
& r8 Q( X( \: S# _7 Z        {
/ x! `+ O7 m; Q! ]" s, y: }) G- P; p            //表示本趟冒泡是否发生交换的标志
: }3 m" g, F% ^7 }8 X  U, M                flag=false;
               
                for (int j = 0; j < len - 1 - i; ++j)
                {
2 N9 `7 N4 E9 R* o# K6 m8 p9 y                        if (arr[j] > arr[j + 1])//稳定的原因
% J4 L8 {9 h) {                        {
, M- @) }# e/ m/ K1 H, c                                temp = arr[j];
3 \! V, R6 X$ }# J; n1 O7 I                                arr[j] = arr[j + 1];
* X) @' l5 I) R+ u( C                                arr[j + 1] = temp;
9 R. w8 J: F0 g9 m3 L                                //有发生交换
$ J+ q6 J4 R: x" k1 t- v+ e( C6 B                                flag=true;
  X; ~7 N8 o. O4 F' c                        }
                }//for
. l' d* L& E7 R               
0 r: y( u/ C9 m1 d                //本趟遍历后没有发生交换，说明表已经有序
8 k8 }% Y% \% `) q4 h( B+ q                if(flag==false)return;【1】
. f$ V: p/ y; a( j4 S! `" E6 H9 Y- c        }//for
}

1
2
3
4 B- V+ i7 O" I4
5
8 E! K5 g7 b; F4 z$ T! c9 U/ w6
7
8
9
10
11
; B6 u9 t; r- ^) j- ^8 E12
13
14
15
3 S$ D! X& k$ B/ ^, j: k16
17
; i" k/ V; r$ o3 L6 l  [( [18
19
20
' t4 J) z6 N# r1 X21
22
23
6 R. Z5 ?9 E' \8 R2 c! Z* r24
25
( w1 E' l2 W! `+ r4 w2 I26
, ~  `  d' y" |' |5 }时间、空间复杂度
4 a( Q% H* u4 v
适用性：冒泡排序可以用于顺序表、链表
( j4 ^  s5 Z2 f4 |/ T

: g) o7 X& v6 ?+ ?

2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
1 D/ I2 \( c: P6 _* C9 F& c通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。

然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

4 R9 [' ]; Y, ^$ {划分的过程：

初始状态：取首元素为pivot，定义low，high指针
: u6 }% G9 r4 G
9 C3 l2 D& r& U" w首元素为49
high指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置
  s$ f/ J/ m, x9 l" j. @; ^! Y

' w2 }. H8 j: ~$ g0 z1 t# L5 ^

* I9 h* i/ P6 z6 b
4 |, ?1 `$ M0 Q// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
" F  j+ L3 f# {  e+ P, I$ c; {        //取首元素为pivot
3 u% O# }6 d5 z+ k4 y. J4 @" e1 ^: B    int pivot = A[low];

. |% l' j$ u) w5 e: f5 l    while(low<high)
9 S( K# Q! ?$ O- g    {
            //先是high开始向左移动
" j% _8 q* W$ I        while(low<high && A[high]>=pivot)
            --high;
        A[low] = A[high];

! Z  A" c  t$ q& K8 I) H        //随后low向右移动
        while(low<high && A[low]<=pivot)
' v  [9 U! O6 A. ?$ E) f6 u            ++low;
        A[high] = A[low];
    }

    //low=high的位置，即pivot放在的位置
    A[low] = pivot;
' S+ K1 s1 I% p7 K0 x3 {
- d6 d! T) V9 S& ?4 }% T/ T    return low;
}
5 d3 @* u8 S- S6 }5 s0 E' p
( @, g% g# S: F* T7 a9 u% M& M0 o// 对A[]数组的low到high进行快速排序
1 z: \/ ]5 _+ W5 ?5 |void QuickSort(int A[], int low, int high){
  M0 c2 ~1 j0 }* v/ Y    if(low<high){
        int pivotpos = Partition(A, low, high);  //划分
( _4 R# B6 m5 j+ C% U' V$ r        QuickSort(A, low, pivotpos - 1);
  u: r/ y+ q0 w& H0 `: A        QuickSort(A, pivotpos + 1, high);
) ~& C- q* z! e3 s5 D    }
$ k2 z) ^& H2 E2 g}

1
' h/ O# L2 {' n6 i+ j7 c2
$ c& n2 \6 j( v  y8 H3
& V& w' ~: I$ f; o4
& t" S7 G/ w' }8 j( x1 w# R5
  ^& @. e* F6 ~6
3 I' r- h0 W8 A0 D7
! P4 C/ S1 h* F" v# ?5 n/ c4 Q8
9
3 S- }) ?" }! ~: ]: D' a" E* ]4 R10
11
12
13
" ]' Q$ F: Z4 Y. D8 i14
15
16
0 P) K9 i4 x; o. e( F/ y" c17
18
' m( e/ Q2 o! @% U19
7 z2 U% }: d. `, J' V20
% j! |4 N1 W& j  o6 C21
22
23
# D3 G' H4 l. ]' W/ j/ k24
25
26
27
28
29
, R% ?$ P+ w- `2 i( p30
31
, M5 |! ]/ e; d6 ?( S* u! x32
时间、空间复杂度
* R8 g/ }! g7 {' G- k# R

! {4 O- W  _( r! f! B把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

' S; ?+ S. C  A9 [( O1 {+ I时间复杂度=O(n*递归层数)
: ^' f- y! w8 I9 G最好时间复杂度=O(n * log2n)
% y, V$ x1 Q! W& ^) _; ?最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

空间复杂度=O(递归层数)
0 f  I8 g! O; q, h4 m$ |最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)
' m) i, S# i7 H, `
最坏的情况

0 h9 K- R* g* A7 e) c9 g4 g# N

0 r6 C4 r, g1 z; e⽐较好的情况

) \( T: p, `' ]  ]8 q) X" M( t; Y
& a+ O5 \; s  H2 U
不稳定的原因：
: ^9 ^- q; R- y/ [
3 {. i( n$ N+ f; R; ~( J


' v6 t  z) G7 b4 M0 Q$ Z
; z( y  r4 R; `8 @- o/ _3.选择排序
/ f0 k2 s2 o* v选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
2 _/ ^# V0 o9 ^& W$ h3 k+ o
3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
$ A( R  q3 [$ N) N3 i
/ m! ~) X2 D8 y' T0 @/ ?
& @, |: k" c" c" G; L4 ?1 i. d
// 交换a和b的值
- P( K5 C, t- M$ ovoid swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
' c" A" D7 v8 ~" c1 }# K$ J}

// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
{
        //一共进行n-1趟，i指向待排序序列中第一个元素
9 |; Y2 n' N! z, y6 D6 @/ k! R    for(int i=0; i<n-1; i++)
4 ?9 }: B, V( Z# O, a" L9 V  V    {                 
        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
                min = j;
        }
        if(min!=i)                     
            swap(A, A[min]);
    }
8 l% K! E( p% {9 M/ H}
2 y) i4 N! w" ~6 p
1
$ R  Q6 F2 A2 V! m2
- P0 q3 `# x) P* }( T( u3
4
, D  m, ~) d* G  Y6 O" n5
3 W1 e4 }) P9 k5 I1 K# I4 o& D" L* t6
1 k0 i/ {5 \; `) J. }2 I  d( d7
8
; `6 [  O2 Q. Y+ l% |" h9
10
11
$ q; f+ p# ]( L5 n3 Y4 G# i% M12
13
6 \& c$ m$ U# J2 ~2 f1 o14
15
16
7 R' d- O6 p! F0 F17
18
19
# O' V  x/ G# ^0 |. c* a20
21
22
# P2 m1 x9 r% O/ E# p2 Q补充：对链表进行简单选择排序

void selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
1 b$ c- }# \+ b$ w( A    L=NULL;
    while(h!=NULL){
        p=s=h; q=r=NULL;
        while(p!=NULL){
! e, Y+ H1 @$ c' d) o0 u            if(p->data>s->data){
                s=p; r=q;
( u8 j9 Q6 }, W: K  h% U; R6 R            }
            q=p; p=p->next;
        }
        if(s==h)
            h=h->next;
        else
% X+ X3 M2 r- K' X5 y4 ~+ v, ?            r->next=s->next;
& L8 b( t/ F8 T4 s        s->next=L; L=s;
    }
}

9 m8 H( h0 J4 b) u( k6 N+ n! F) k1
2
3
7 i  v. u6 H% C) [5 @' G: S* c4 r4
! Q8 Y# [' s. ]; f- A1 ]% {, u5
6
7
8
9
( I3 l9 u+ s9 Z, L4 Y+ X7 S$ W9 R! u$ i10
11
12
& h3 i8 r( a' I, l* M13
# T9 p! f0 y; f4 T14
15
16
( O2 m- }& W4 J0 a" q17
18
  t# D# J8 h( ]* ?0 P. U时间、空间复杂度



9 v( ~8 R5 t1 P  a" F- r
2 s6 g/ Z" K6 v; ?; l8 m! ^适用性：适用于顺序存储和链式存储的线性表。


4 P3 H% }8 u* Q4 R
0 W7 H6 V% d( J3.2 （不稳定）堆排序
① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
9 `( {, E2 j5 z1 f! o% D每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。


3 b( S' y4 o7 [  _' s
8 v5 u& }. l8 T; h! H, P7 p即：
若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
4 H1 P! k" @4 z+ h; p' ~/ d) D若满⾜：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)
  m2 m# [. j8 S, b1 f$ k思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

( v; V1 A: P# y: W+ m2 U( ?4 v在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点

4 A9 H2 L2 H4 X. y+ s检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

3 n, V2 o' C% P) v* D  d; F过程例子：


1 O5 L) H7 c& q! e0 Y2 K
2 R; u# h$ ~  r: K建⽴⼤根堆（代码）：
! H6 c/ a, w- j
9 _# j- {4 o! t/ N* s8 j* E3 E" `
3 P; Z, T) R  V( k7 q
: q8 m; T. f$ J" \* f5 ^// 对初始序列建立大根堆
. |8 L% e2 V* |& T& f, qvoid BuildMaxHeap(int A[], int len){
2 Y+ R$ f9 n2 t0 m0 d% f' Z& i    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
$ O  u7 B/ H1 D9 k9 X; @        HeadAdjust(A, i, len);
8 g1 \8 }! H$ \2 `4 G2 Y}

// 将以k为根的子树调整为大根堆
+ e% X$ W  \7 r6 Uvoid HeadAdjust(int A[], int k, int len){
2 f2 _3 [9 b( P    A[0] = A[k];
    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
3 a& A; ^: O( R8 l, [# @" i        if(i<len && A<A[i+1])       
  p0 ^) r! W( I$ M9 _            i++;
        if(A[0] >= A)
. C9 J9 R) d  e8 m* C5 v            break;
        else{
            A[k] = A;                        //将A调整至双亲结点上
            k=i;                                        //修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0]
}

1
2 ^( u% r( K: U4 U8 G, Q2
3
, e  E3 M; M8 ~+ A' }4
0 e: q0 Y; T2 g5 o- I* r5
6
7
- _8 M" M1 T6 |  L8
- b5 |3 k2 \- ]: W) p9
10
7 D  v( |3 l2 N' \8 P11
12
0 _$ ]& i1 R: O13
( `8 J' l) {- d, p5 ?- k14
" i- Y( o: `5 s3 i1 d2 _4 J! H9 t15
16
17
5 }8 T# u: j1 S& V. }3 k18
2 ]4 A8 A, _( e# Y6 D% k19
: M- l! |. C. }& P20
21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
. [; l3 M  {/ b7 T1 }" G6 i选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

5 `( ^# _+ I  Z( A5 \/ m- A5 X/ R堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）

9 w3 ~% W3 ^9 y4 Y: V过程：
2 O5 ^5 X8 q# s7 {% V
// 交换a和b的值
void swap(int &a, int &b){
: O  B4 w8 S  Y' N& T& K7 D    int temp = a;
    a = b;
5 l! v; n+ u) J; Y& z* }    b = temp;
8 W/ P' S8 n6 U}
) ~, E' \2 I- S4 z* ?) A: j
// 对长为len的数组A[]进行堆排序
- b8 s/ Y: w+ X- R/ Mvoid HeapSort(int A[], int len){
9 c  a* G2 {3 y5 G, d        //初始建立大根堆
* r1 S* c' i- W: A    BuildMaxHeap(A, len);                

    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
    {             
        swap(A, A[1]);
* [$ N3 J" k& J( ^! ~        HeadAdjust(A,1,i-1);
    }
}
; A( a- B# S; p9 T$ i% y+ I; g
: W' q% s0 u: c1
9 t& G9 g4 |( n# k( r: A1 J2
, K* y$ b7 i' C& e0 t5 J! [! Y3
4
; z' Z/ y. M1 M" i+ l0 [; K0 |& [5
6
7
& K: j8 x2 Q8 t7 d$ N* Z9 N( S6 X8
* Q! e- s4 ^: F9 f. T% M  H: U9
10
2 ~' m" w# h/ V- h3 f3 ^4 X; J4 y: T$ |11
- u! J/ p' ]1 h, O1 P$ H4 H3 c& ~12
6 {: S: _& h' u5 K3 `5 W$ g0 d$ T13
* d# Y/ Y: N" G  K* P14
15
- \2 S6 B7 k0 M' P2 i16
; m* t, d5 l, V; H2 x& ]17
18
19
/ r& W$ G/ M" s3 W时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

空间复杂度 = O(1)
: l8 ^/ o( f: m( Z; D% u: E& n0 O
- o! U2 r4 v( s4 z) X3 u" F结论：堆排序是不稳定的
3 b7 _1 {. i4 h% y6 A6 i6 P

④ 补充：在堆中插⼊新元素
/ P( M2 b# H0 H8 [+ b对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
- p* E5 H+ i3 e) `" `/ {新元素就这样⼀路“上升”，直到⽆法继续上升为⽌

  G) ^9 e; f; R" F. X# j. R
" ]& N6 y5 u; A+ Q0 V
5 H( d7 ^( w4 A: \( Q1 e, T⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
2 G( Z: R. g5 ?4 r
" u+ P  {1 T7 y" ]+ k/ l! P
" h  R8 R3 @+ {; g. E6 m/ k
9 f8 m% q- R6 [& P" C) `
4 w) f2 i  Q# g6 \9 p: r& B7 D) J
4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个

* ]9 }' ?- Y. A' d$ Y① 明白什么是“2路”归并？——就是“⼆合⼀”
( [- D: T- y7 H8 a- s) O! n/ O$ f8 v
& ^/ t1 g* R, `" ~- s0 G多路归并：
) c4 _; w: t2 a% o
1 B' X  }: e0 }; d
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
" V- C# L- \4 j% o
③递归进行分治思想【MergeSort(int A[], int low, int high)】

/ n3 H0 w( B. g  u, `
. v# z& B9 M& ~( c( e④ 总实现代码
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
4 t  M9 v- N' v  ~
// 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];
) ^3 x+ a# m) l, C    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B<=B[j])
            A[k]=B[i++];
        else
            A[k]=B[j++];
    }
" d' X8 D& R7 a, \$ _    while(i<=mid)
" d2 Y! g- U5 f        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
}


3 a5 I+ j2 i, a( i/ y9 w! ~// 递归操作（使用了分治法思想）
void MergeSort(int A[], int low, int high){
    if(low<high){
        int mid = (low+high)/2;
: l) S! x( W7 Q) S) a: Q2 w        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
- v4 A* B% ^9 E: L! K8 K        Merge(A,low,mid,high);     //归并
6 V; ]9 f1 I7 _+ e4 G    }
}

( F8 z/ E8 w: T8 K7 L1
2 c1 T3 O) Q8 e0 H: c  x2
9 Z0 ]' f( ]( G) F3
. h. z% P. J4 P. l* Q7 Z. j) p; p4
4 a5 k# o! r7 n5
6
7 C$ d7 Q1 s7 E  y+ G& e" P/ N7
8
9
10
& t. N; x- ~) \11
3 q) _' ~$ M5 H& C6 z. z/ w- q& X12
13
" i" ?# Y" C& v# K5 ?: C. @6 ^14
# b8 `" w" }6 Z) e& A1 o' P15
: o3 e$ l3 H+ @' k16
17
' e& W& i& T+ r( t/ W18
19
' r" k& w# [1 U$ k4 x$ d. t20
21
22
23
24
6 p8 O8 n. g( k2 C; q# W9 [! s25
0 c9 a. D. g, L" U" N! _2 }26
% d1 e/ `; x7 Y" _/ p  H# D27
28
29
2 f" g: i1 Z0 m3 r+ U30
( s1 X8 M/ X! h$ W; ]" E: P, R时间、空间复杂度

5 {* J2 i" f  N; }9 |0 A* i9 N' C
0 l6 h$ U" L2 j/ V. K( R; g0 c; H

5. 基数排序
* k+ a6 N2 Q# G  i+ ~& m0 X直接看课本的过程图来理解P352
% g  s0 U* o/ M5 h1 B
再看这个例子：
  S9 g1 }% U% W6 x5 Q
9 h5 ?9 K  r# v& Y# X/ h* c5 d
算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
: s$ G. X& C* ~2 t: J4 i5 Q2 Q& }①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。
算法效率分析：
- }( O5 y( i0 G+ Z5 T' L! l4 e时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
稳定性：稳定。


+ ?5 s8 Q9 E5 ~1 v( Q; Z内部排序算法总结

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

" W6 r) P, e/ W. ^# X
( G  v2 m, ~- R$ q. ?/ ^# {8 Z