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

杨利霞

- |; f4 z: f* V% `) r【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
排序
  Q8 t7 B2 I- u1. 插⼊排序
7 Y% n! \, n/ g4 n  {' `% Z/ i（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
' Z, Z  Q, {; ]  E( l" ?7 W, }时间、空间复杂度
' K5 M9 ?! o9 R+ a1 t（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
时间、空间复杂度
9 b, R# X, K2 i; [. A, O（不稳定）1.3 希尔排序【多次直接插入排序】
8 c$ ?6 V0 i: s- u& }& h时间、空间复杂度
2. 交换排序
5 V- @0 t. y. n2.1 (稳定）冒泡排序
时间、空间复杂度
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
5 s$ U/ [$ c' s  j4 C时间、空间复杂度
  M( ]! S  G* [  M+ S: A# N3.选择排序
3.1 （不稳定）简单选择排序
时间、空间复杂度
. b( t- L+ u$ ?2 V- E( m3.2 （不稳定）堆排序
% b( C4 B4 @0 @( A8 b' q. G① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
( u' Q6 ]1 I: l7 L( w; A* e6 k时间、空间复杂度
5 i% M: H  A6 v# h④ 补充：在堆中插⼊新元素
9 r2 C* o0 \3 h3 s⑤ 补充：在堆中删除元素
8 w4 N$ f: U" Z1 q4. （稳定）归并排序
① 明白什么是“2路”归并？——就是“⼆合⼀”
' ^" P: B. }* t& s② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
③递归进行分治思想【MergeSort(int A[], int low, int high)】
9 w' C* v& ^8 s  E④ 总实现代码
时间、空间复杂度
5. 基数排序
内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

$ h) ^+ O+ ]6 \. Q排序算法的评价指标：时间复杂度、空间复杂度、稳定性。

6 O( g( c# c% Z- ?) z4 A3 }/ f! |算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。
& J8 M4 Y, v0 }

排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
& _/ C% m- ~; J/ u外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
. O) ^; p& u; A- q
3 h% ~+ n7 Z9 v4 D各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
% b! h7 `3 i! u+ ]

. K# H6 J9 }6 A
+ v" m. W( m6 J* p+ ~, f+ o1. 插⼊排序
, l6 J( A' T* H+ J. o7 k（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据
* i( p& C- j9 K7 s7 J5 \- R& a
算法解释：（从小到大）


算法三个步骤：
+ x1 w5 U' s7 a" A4 @
先保留要插入的数字
往后移
插入元素
/ O. n+ w1 v1 a, U  ?2 z
// 对A[]数组中共n个元素进行插入排序
8 p* t, C6 z6 w" }void InsertSort(int A[],int n){
" G8 |) [) V0 h" r. q    int i,j,temp;
    for(i=1; i<n; i++)
& v: v- p2 G" n: [3 ?    {
            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
& R& |# K) s$ L0 m+ ?. ~( U        if(A<A[i-1])
        {           
            temp=A;  //保留要插入的数字
1 o: A& g5 R7 m9 O1 w
  A1 f4 g) K& W& S3 y            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪
# w6 U3 T6 L- Z! ^* C+ ]$ r) Z
            A[j+1]=temp;//插入元素
        }
    }
2 r& W- `' q/ f: B}
" G9 V  k" l  d% V: F+ J5 Q) a
% _, n# e( q% J" y) s& O( e0 ^4 b/ b1
2
  ~& D: q6 ?  ]4 {( j/ [3
4
! f% k  n/ e% c* ~. P2 N5
6
+ Q/ R7 h7 F$ o9 W0 w4 K1 f* [7
8
9
10
0 Y% }; ^$ _6 J: D  z5 K11
* v4 ]  A: C- t0 _" }$ e4 q12
3 S5 x$ c* w, O# u0 E# E1 I2 J13
14
6 s/ T4 ^+ q6 [/ d. `5 s) E15
16
17
用算法再带入这个例子，进行加深理解
2 u" k, ], ~4 a4 [! G) b4 E1 |
6 Q# ~" l, n) J/ }% u
带哨兵：


$ V1 o; E8 j1 P& s- V' r1 ^/ z# r8 h补充：对链表L进行插入排序
- D$ V. @3 L% V
2 D: \0 J9 T4 ~/ z: Yvoid InsertSort(LinkList &L){
    LNode *p=L->next, *pre;
2 }2 ?3 z6 p3 g- t+ Q    LNode *r=p->next;
    p->next=NULL;
5 U- W  n1 D+ u9 c0 ^    p=r;
$ `8 n: L# n2 f3 {    while(p!=NULL){
' h9 D- b7 @5 S2 a; V        r=p->next;
+ v2 F* {6 f+ C1 V3 A* R+ R        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
        p->next=pre->next;
, @% t( g, ?! x7 c        pre->next=p;
; F, [3 X, x4 m        p=r;
    }
5 ^. Q9 r) ]) H, P: y+ K; ~}
1
- i+ q0 N$ v3 x# j. N+ f, x/ ^2
3
4
' h' S, u8 p+ ?/ B* Q5 `; u5
. z; Q: e) S) }0 D2 q8 A0 G0 S  |3 r& X6
7
" W+ v/ Q( b2 h, R9 q8
. x+ C3 a) e( V4 K6 G9
" k6 T+ O3 O" ^# q10
11
5 f$ X; _7 x5 c9 B12
/ j$ R; k( d7 Y( p: f& b7 D13
' Q. m: Y1 S% |5 K14
4 c4 g  G! \1 z15
% ~4 F! e! I; Q1 I9 Q7 |+ r! v' Q时间、空间复杂度
7 B# Q/ L5 [4 ^+ t: ~- p7 O  ?, M; v
3 H" o6 o- h4 q& v* C/ M! c
最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
最好时间复杂度—— O(n)

: u2 B- E0 b  R; \; \8 K7 y, X最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
) p9 ?( z0 Y' r& J第1趟：对⽐关键字2次，移动元素3次
第2趟：对⽐关键字3次，移动元素4次
  Z0 d7 x/ y7 ^…
第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)
! P, T' G( ?3 q9 R' n; m
- O. h# z2 ?# B0 f0 I

! _$ Q" o; }8 W* ]

6 ?- H+ s8 H8 _" \( N0 U（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：
$ c* o. L6 ~. P8 i: V


//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
3 {! D6 B0 q: Y) N% {3 b+ o1 R{
2 q, _4 y1 E+ p2 u8 {    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
) _. [0 m! }& f    {
        A[0]=A; //存到A[0]
5 V$ y) X0 z/ p6 @        //-----------------折半查找【代码一样】---------------------------
9 }- J! V+ X* E) [        low=1; high=i-1;
        while(low<=high){            
6 h. x5 u( S! \/ S, @! F            mid=(low+high)/2;
* a8 f6 Z+ ^5 X* P0 W) _            if(A[mid]>A[0])
8 x" a; A3 d0 L' |7 D* W                high=mid-1;
            else
                low=mid+1;
        }
         //--------------------------------------------
! L! E6 i2 c7 q+ }" C        for(j=i-1; j>high+1; --j)//右移
/ R" H9 |+ `7 v2 S( j            A[j+1]=A[j];

1 E2 _3 t$ q5 |- B        A[high+1]=A[0];//插入
    }
' c- ]$ a( R# E' d% c1 M4 I}

  B' B* H: D1 |; S5 P" V) G& `) x1
7 j- a. C8 z) o6 k3 {' }. @- G2
( d% S' X' G4 ?/ ^9 h7 F9 g3
4 g- b- }. ?& e4
5
6
7
1 A5 i6 s, X/ `: U3 J8
9
10
( x  t. ^2 K; g  Q4 k11
12
13
14
. t0 i  J* @- d15
16
# B+ z( q( _3 q" }17
6 E0 i, c% |$ _6 {5 j% d( N18
19
8 N( [" t+ f+ z8 Z' y8 H2 q20
21
- r* K, J  H$ s1 q8 P22
23
时间、空间复杂度
: ]5 O8 I6 A4 {: M( z! T* N0 ^空间复杂度：O(1)
2 ?  Z* J. m# \  p0 S9 x8 U
【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
, p! p0 B$ c2 y; @5 {
5 U8 Y8 P; _! c9 e4 t9 Y: x% x
( t" V/ B; ?& ^4 W& u6 d/ Z（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

  H0 b* D9 I  _; L) W2 a! A: W3 d算法思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
/ j3 s. r% Z/ L$ H( l  V2 n随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：


6 {* e2 V0 v& G* x, S
  T! k/ l& D. \5 \代码实现：

9 W- k  S- H6 G% Q1 ~8 G3 |3 F, z//从小到大
1 |, K+ z3 h4 |void shellSort(int* arr, int n)
0 f6 T# |7 ]; c" r$ ^4 n{
        int gap, i, j, temp;
8 b  l5 `1 R7 x( ~9 h1 k3 M        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2)
6 {6 Y! u" [% B, U! ?: G        {
' {8 I8 t4 S+ E6 y            //**********************************直接插入排序（只是步长改变）**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
            {
                if (arr < arr[i - gap])
                {
                    temp = arr;
* u  v- y  a1 T* u; @" l* I
! @: y. P" ]7 {4 v                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
. ]0 t6 F: M9 Q0 K3 O4 X                        arr[j + gap] = arr[j];

                    arr[j + gap] = temp;//插入进去
                }
0 C9 \/ L% o4 _# P8 u; F8 j            }
% f+ Z) N3 P( B; b+ c, F            //************************************************************************************
: s2 j0 D. J# V* @: T7 L  Z        }
}
( U; X4 g+ r, ?% }- {
1
7 |: E1 W3 }% w4 o- \2
  Y/ u( e) i0 r& F0 m0 h  T  x( @3
3 ^% j: e6 ]; O/ h# ?! y4
0 m2 V- F& ]$ B/ K5
$ w  s4 B# v4 ~0 t. f6
7
5 q9 A) n; D+ P  U8
9
1 R  U) C$ M0 @* n10
11
12
13
14
15
5 d4 Q( O( b0 A( G7 e5 I5 V16
17
/ J: w) j9 z8 F% e18
19
20
# Q% L( O& k# A# P0 p21
22
1 ^, P4 E9 n* H9 O23
0 u* H3 u  G, @0 Z" {) X24
时间、空间复杂度
空间复杂度：O(1)

' t! @; ?/ ^( @* W) G时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
. T. M# L7 }* n2 a1 r; {
6 g, W9 N  a9 l稳定性：不稳定！
- G" b  @' ^) N. t" T9 K$ g; ~

, j5 G' `& z0 g  Y
! U1 [8 P- D3 k  f# E适⽤性：仅适⽤于顺序表，不适⽤于链表

' B7 j( w" ^4 V- \& x' l
- L. ^7 R8 n' a* t
7 {0 U. `, f) L6 L' X( R1 _2. 交换排序
$ c% v7 y$ _9 O7 ~2.1 (稳定）冒泡排序
英文:bubble sort     (bubble 动和名词 起泡，冒泡)
$ F7 {; G5 v: \7 ?从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

' {$ x) g/ A( F+ \8 s9 Q每一轮比较会让一个最大数字沉底或者一个最小数字上浮

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
" f4 U5 p/ Q) R4 e- z
7 d! v) [0 A/ t; H9 a实现代码：
  E, L; y7 ]% a: @
//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
/ W; o+ F# M' g7 l, N{
        int temp;
6 ~. r7 {4 l+ J* ~6 L( j$ L        for (int i = 0; i < len - 1; ++i)//循环比较次数
        {
                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
2 @9 M3 ]4 }% _  q4 W                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
4 n+ A* F- C+ m; s9 r                {
                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
                        {
- d3 _8 }: B' q6 U! m( K                                //交换两个元素位置
7 I" K: P- O7 {6 H2 Y                                temp = arr[j];
. S) s1 R2 i3 t! s                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
% F6 @! @( @% X; r. N5 b                        }
                }
        }
& _7 k, A$ [( m( y- c) W}

1
+ I; J6 J7 J8 E% d0 n2
; b4 ?: \7 `& u  m% L! L. _3
. v' O: H" `4 E; j! }7 w4
' k" v3 g" ~2 n# \% r& J5
, }& }0 z( S: u7 W  x" o6
* r/ a' M  Y% H) N2 k% X7 f7
: V- m. C- o7 d1 @1 ]* ]8 \, W; c' C8
9
10
11
12
6 B# e2 r7 U! ?13
# z( y( c; s' x* z3 [( f! n; x14
" p* p& T9 t6 e3 B* a/ y: f15
16
17
- h$ V4 x1 I' L3 j# {18
19
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

! f, [/ }" h5 s4 t* L8 a//从小到大：
8 D0 b2 K2 H7 U* vvoid bubble_sort(int arr[], int len)
{
        int temp;
        bool flag;
        for (int i = 0; i < len - 1; ++i)
        {
  u6 h; g, q1 g0 |1 l8 b            //表示本趟冒泡是否发生交换的标志
! u" a* ?$ R6 a# Z+ {; l                flag=false;
# U- Z- m+ {+ h0 T' n               
                for (int j = 0; j < len - 1 - i; ++j)
8 o0 W' x" o% T& `                {
* h! u) e  q3 r8 Q- Z* T! H* \, \                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
; _4 o8 t- j8 P& w/ X( ^                                temp = arr[j];
# A1 F( _+ B& F  a                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
2 j3 L9 b- F% X, n9 c                                //有发生交换
1 n( t3 P1 d+ Z2 T3 i- j) j) h                                flag=true;
                        }
0 ^" v* o$ T% I; M  i                }//for
7 l3 D1 {- B0 E3 T% W( B1 y1 c6 |               
. X/ |7 c& n) }/ @* `                //本趟遍历后没有发生交换，说明表已经有序
: L, d$ a( b7 a% m5 N                if(flag==false)return;【1】
        }//for
9 d: M4 X: y) D) h}
4 D4 s1 ?1 L2 ~% c# U9 [7 ]2 R
1
7 z! o/ R. e' B2
7 J5 Y& i( Q+ V$ X! U4 _3
4
5
; d+ E; n3 t- [# l" a( `; {. \8 s6
7
3 V' z4 a% G* `7 h' N: a; Q8
9
10
( `; m: S! U  o% d+ \11
12
13
14
0 R$ n  t2 ~/ h15
* E2 j2 p4 F& T/ o  e: d; _( r16
17
9 j& m$ F" Q9 n( @1 e18
6 U% e9 R$ K8 m8 {2 d; J19
( P$ W$ q  W  A: b20
; J+ b9 p0 `& y# E" O21
+ r# a3 i: i; K. n  r  Y! c! p+ A/ A$ J22
23
24
2 ]3 R: P4 F. a8 B" G8 q25
8 h0 L/ Q- ]2 D6 K2 c26
8 L( [. u! R% r时间、空间复杂度
1 p9 y) h& f, n; R9 g. y" _6 X% W
: f! T5 M" |% ]$ K适用性：冒泡排序可以用于顺序表、链表

$ J9 R' o' N3 _! F$ c


2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
' C  y2 Z, D7 A/ `) J! E算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
' o% S' q0 l+ d9 v7 Z通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
' A7 c. Q0 b1 }9 w$ A再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
3 Q' S; A' x/ A3 O* J! n
然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

- t. s+ _7 E" y, ~9 R% k1 V4 T3 P划分的过程：

初始状态：取首元素为pivot，定义low，high指针
1 T4 @9 N$ }% s" `# A
首元素为49
high指针指向的数据小于49，就放在low指向的位置
/ E" _' Z5 z! a% blow指针指向的数据大于49，就放在high指向的位置


; R5 z7 \# u8 m) t9 P
. f6 n1 c0 C2 ~6 J

// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
1 `- s2 l, `, {8 p2 z2 l7 @        //取首元素为pivot
    int pivot = A[low];
7 E3 p1 \5 H2 j, E% T- n7 q9 b
# O) ]( X# z2 @" v8 W3 K    while(low<high)
2 O: y0 f' @0 J8 Z* ~    {
            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
/ o9 D- F7 _: w& A3 N9 h9 e            --high;
$ }) S  A& k1 K: e        A[low] = A[high];

' c# \) d+ V( `; o# f7 r        //随后low向右移动
, Y  `+ a3 J0 [8 S+ _) C  x        while(low<high && A[low]<=pivot)
) F- _2 h$ y0 z" F5 o# N. U            ++low;
: H" y$ h1 s: j! X: f# J- F* W6 z3 q  C        A[high] = A[low];
  C  J3 G' h( H: ~- a    }

    //low=high的位置，即pivot放在的位置
7 n( \* q  h( A$ i# ]+ L* |' J    A[low] = pivot;
: M3 ]! i7 r, `0 y$ A
    return low;
}
8 ^, `7 L: \4 |& y1 c: ~- H
7 R$ q/ L0 O' ^6 I2 A; S3 \& A3 J  h// 对A[]数组的low到high进行快速排序
8 ?2 K4 l1 ^2 Zvoid QuickSort(int A[], int low, int high){
    if(low<high){
        int pivotpos = Partition(A, low, high);  //划分
% q4 A  E( [* @8 T: L# z( I        QuickSort(A, low, pivotpos - 1);
" R) z# r8 _  ]3 n$ Z& p; L/ c( x2 ]        QuickSort(A, pivotpos + 1, high);
    }
0 ^% F6 V; B5 x5 a/ Z, p5 X}
8 L0 ~+ G# A  D# F0 C' \
1
2
/ ?; a3 s1 X* ^( T3
4
5
" m# P0 o) _1 U" \" Q& |- f6
7
3 S$ j- @- D! ]4 ~8 e  l- s8
9
10
11
12
/ J4 G0 ]) |$ ~8 M7 y* I! c13
14
15
9 X4 z6 Z1 v% }. i3 ?6 h+ U16
: I" J$ f7 P. V5 ~1 [17
4 D7 b% ^4 ?$ v2 W9 l2 }18
9 q0 R& m% B  K- w19
20
1 a2 j$ K" X% L, j21
8 x5 P: j# c* E$ c1 @4 u" f5 c6 ], \22
+ y: ?/ H& `6 s( J- D0 r4 ^23
: G  m' w, Z1 S9 ~( w- y% b- B24
; a* E- J* l& c% q25
26
+ k( j/ `- z/ |* I3 B27
28
5 R2 k6 X/ G' |29
6 _' }5 p$ w& o8 L/ @! k30
6 M# r  h' ~! k9 Z4 ^31
32
- Q% Y" J  H* e6 o! M/ [时间、空间复杂度


把n个元素组织成⼆叉树，⼆叉树的层数就是递归调⽤的层数

n个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n
# D. ~+ b) n: \4 h
时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
; z! f' z' o  A' g8 s/ Z+ J" U最坏时间复杂度=O(n2)
& m7 A3 U& X- ~1 L! s平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法

$ c2 d) M' z( }1 \0 c7 f! r; O( k空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)

最坏的情况
6 q6 m4 F  X( [! ~, |& a
3 n: q2 u6 p5 F. v9 P, j
# |. p3 C. U# C% E- Z: o6 b' j% @
, _1 C" O* N) M# i. z⽐较好的情况

' L5 K. D# P, Q/ Y, ~3 R" K. x

不稳定的原因：





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

) c: `) c7 U/ y  N% O3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置

" O5 _8 V& q" H- C7 C( ^; N
' O9 Y+ A7 O. `- g
// 交换a和b的值
void swap(int &a, int &b){
" q" f# \* d6 o$ e    int temp = a;
8 D  _8 g) w. }, y    a = b;
! X# K7 }+ e' N* ^2 i0 _7 P) J    b = temp;
}

7 X0 {9 Q) u) f' f4 F. f* h8 V// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
3 s0 K- n- ?5 R! U0 u{
  n9 X6 E; A# ?. q: y7 `! J: e        //一共进行n-1趟，i指向待排序序列中第一个元素
& K9 m2 |2 A/ {7 l# \% D! i2 D    for(int i=0; i<n-1; i++)
0 Y0 A0 [5 e2 S    {                 
, b4 v, J1 |; Q1 q% r2 F        int min = i;
        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
. S; ^9 }7 \% E* Z                min = j;
/ O9 O0 E3 u( ]; \& n6 K        }
        if(min!=i)                     
3 d0 E( Y% J4 h3 b3 P            swap(A, A[min]);
4 p- F) u1 X; n3 A    }
; A" k( X8 o  N. m}

1
2
3
- z4 c9 K8 F- U9 p+ z( C0 R4
5
6
: l+ e- |) @* Q: b0 D: m2 {7
8
, X. x% a- p7 [9
8 @0 x5 g* Y% G- j+ d) d10
11
12
13
14
& p$ r$ t1 h( n  b  [15
9 M, _; P+ O5 H8 F9 g16
17
$ F: b1 _( S6 H* u18
19
9 R! N$ \) e5 ^$ F. k4 _: B8 r20
21
  p2 J4 L' c3 N7 i8 i* b' O22
% l7 F' I7 ]7 R9 B4 s9 Z# A补充：对链表进行简单选择排序

void selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
    while(h!=NULL){
        p=s=h; q=r=NULL;
        while(p!=NULL){
            if(p->data>s->data){
% @4 A  n* i. R: m; K" d+ d4 v                s=p; r=q;
            }
            q=p; p=p->next;
        }
        if(s==h)
            h=h->next;
% G# T/ p/ Y- d& S( o* F# v9 a        else
2 ^) c$ [1 ~/ l. o. q            r->next=s->next;
8 x; F; P$ z$ i+ A0 ]) L. c0 p        s->next=L; L=s;
& o! A. O) E1 L, N6 E* B    }
. O; p  ^5 W9 m4 r7 f& i}

1
2
+ e) C/ t! D6 s- @# E: ~3
4
5
; `. e, w4 J( o4 u0 O4 B6
5 Y1 j) b/ U1 R0 D. B6 k7
/ Y/ S0 }; g4 M. k" ^8
9
10
11
& D8 V2 B+ d- Q( G0 k7 u5 n* {12
' Q* i0 d2 V1 t0 [. X13
14
" B; m2 S# x& P1 R" T* }# K, x  P15
16
0 v( c2 R8 x5 ~1 O; g3 d$ g17
18
时间、空间复杂度

+ J. g$ C4 k: E/ f% q/ f9 w" o

. G- f4 E* q! N6 k7 ^- M* H
适用性：适用于顺序存储和链式存储的线性表。


& O; m* k! _7 {# c1 O! O6 k9 W
3.2 （不稳定）堆排序
6 u5 l& Z# ^6 h+ {! F0 q) U① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
! E. P4 @* I+ Q$ H或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。



即：
若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
8 o: z6 c- _4 v. ~6 O6 I, K7 n若满⾜：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）
( O, Z* V# u* A
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
) x- c/ R) j, T5 H) s5 o) ?. K* X7 x
" m* Z: P$ c2 F检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

+ `# k4 ?$ Z" q5 q6 i过程例子：
9 x# r+ ?; y# S# `
8 \/ K: J3 z( O* `( I
  C6 P6 G7 v; _$ \
% i1 I0 H1 W) ^& _; n& U8 W建⽴⼤根堆（代码）：
- Y7 w$ x- b1 w( |. g7 J. {

  G& ?0 z1 J) D" k
// 对初始序列建立大根堆
" ?% Y. A. ]1 Y8 y! R, ?- Pvoid BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
4 d0 w. f5 Z0 G/ [. O% ?. }        HeadAdjust(A, i, len);
* g( k+ [% [- V& ~7 `% [}
9 u- M- V6 S3 P$ m$ Q
// 将以k为根的子树调整为大根堆
& E9 w& o! ?5 b) F0 Evoid HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
7 c. w. y; O9 ^+ a9 L0 @5 B) y        if(i<len && A<A[i+1])       
7 S1 H1 i- I4 |  O. |+ f% f2 C            i++;
        if(A[0] >= A)
( E5 k; j+ P6 ]/ H            break;
8 S+ M' ?) Q" k$ r9 f        else{
, ^5 r$ B9 c( d/ [            A[k] = A;                        //将A调整至双亲结点上
: f' [3 K* _- `  f1 x. r: J            k=i;                                        //修改k值，以便继续向下筛选
1 U' X# `1 }+ h# W# T        }
( S9 F  p4 O0 H7 l8 W2 Y    }
    A[k] = A[0]
8 B$ T! I( G8 \* y2 x. X! L}
, M5 m6 T) d8 s4 S& j% B( |
: t$ Z. k# L( v+ {) }% z4 @2 E, v1
" F* S) T# Y- Y* ?( f2
3
4
5
6
7
8
3 @$ x* L2 ?# D7 r& F- u5 g' B9
1 {; n5 X2 H. K& H2 D+ W& ?10
3 W. Y9 F! |/ `7 B! ~+ H+ `4 i11
3 I3 g" F7 \! }: N4 p, i2 V; ^12
13
14
. ]9 z, e6 \, U* T" J2 k15
* Q3 H1 P$ P% V$ m16
17
4 ]' q" M# N( |- t0 P5 o18
% {2 ]% B  W2 @0 Z8 i) s  {19
20
) {$ B& O4 U2 y$ z7 V21
( X  B& [( {& U& `③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
: i1 d  s8 h* S) }7 W/ u/ n5 \
过程：
0 o9 n$ k' l, l1 e8 @
6 G/ f- y' c. K4 O0 l( G// 交换a和b的值
* a- ]# I8 T' H. r* Gvoid swap(int &a, int &b){
    int temp = a;
+ H- o# c. ]. N, k7 [    a = b;
    b = temp;
! S* I% L: c& l8 Y0 f( p}
4 e" c' h: x- r! ^, |" P$ V* z; h
/ M$ x3 ?# b6 G" W) u" H9 C' O2 y// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
4 ?( P8 m) X2 G" H& \, Y5 V+ O        //初始建立大根堆
) G6 x) y; ?0 N$ K* A    BuildMaxHeap(A, len);                

    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
    {             
) t1 {  H$ y* R) q/ l' V! }& O        swap(A, A[1]);
        HeadAdjust(A,1,i-1);
+ x3 M( s% z# ]8 G% H/ [8 L    }
+ s+ {! V7 l( \  Y) v4 o}
" T8 @" W- r5 ?. i
1
3 x( x5 f7 ?; I' c2 o/ z- [+ g2
3
  p9 k; Y! x1 l3 F! m4
) o' ?+ R5 x: Q8 b  I5
% _/ g- L9 z2 H% H6
7
% [; X0 o8 T/ a% b- h6 T7 t) R8
1 r" r8 T4 f1 @+ E& T; q* h9
: N6 ~. w5 C7 y! w* M; n10
11
12
13
14
15
# c$ y6 d9 i( n# o( b: ?; g16
17
18
8 i- x2 t/ u4 J- p& W0 X19
时间、空间复杂度
2 Q+ T  u. C, K建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
" w# H6 y2 V, A, b; j故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

: f; s9 j- I( \( N空间复杂度 = O(1)

结论：堆排序是不稳定的
. s+ ?4 X' L( I! ^" a
& p. ]: [- E5 H' L; C# `
6 b9 G  @: v9 c8 _④ 补充：在堆中插⼊新元素
对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
新元素就这样⼀路“上升”，直到⽆法继续上升为⽌
- C3 L. ^  j3 @: q

% g/ W% j( ]8 M/ n
: b* q* u8 l# p7 P6 `⑤ 补充：在堆中删除元素
0 Z4 B& {: t& Y0 @2 x被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
+ `6 S$ c4 \1 c+ @7 Y. i* w7 h

7 k) n1 q! ~' a. J. g6 a


9 F4 y# w; y2 n, J' J4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个

① 明白什么是“2路”归并？——就是“⼆合⼀”

6 n' i0 j4 K9 s/ T" O多路归并：
0 ^+ K! V& [: z) t) ?0 t: ~
  q, q3 M& h" A: s/ h* m, k5 v
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
/ `: ?. h3 P9 G# b$ S6 N& o
B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定

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

9 `! u) @( |  }3 s/ z% H) ]# [
④ 总实现代码
* f& V( D& U" N// 辅助数组B
; V! G2 D7 X- }% S' x* j7 m. K6 ]int *B=(int *)malloc(n*sizeof(int));

// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
5 A6 U- A% G. j9 u    int i,j,k;
# M# U, D4 D4 k+ J6 a7 w* r    for(k=low; k<=high; k++)
5 V0 v) ^- t! s2 H# D        B[k]=A[k];
* ~# |0 P+ L$ b( X/ S    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++];
    }
: c: v$ r7 c2 {- C    while(i<=mid)
1 I" w/ Q/ m/ d        A[k++]=B[i++];
    while(j<=high)
; I* K5 @" E2 Y) l7 f3 z) }        A[k++]=B[j++];
2 p- B2 B/ ^, s1 Q' X  ]- s9 b}


% a! I! [5 p" M6 s  C2 x// 递归操作（使用了分治法思想）
, X4 M! r- e* X7 Rvoid MergeSort(int A[], int low, int high){
! a* S4 _. f3 t) l3 j: N    if(low<high){
7 v% V& b, X9 b* R# i        int mid = (low+high)/2;
+ @4 n+ P$ x- x& V: q1 O  Z1 P2 @1 }        MergeSort(A, low, mid);
0 i" [- p; ~* C: z/ c* _0 |$ `/ o        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
    }
}

1
  T0 y/ ~$ n5 D. Y% {& F2
3
; K$ P- q1 |$ Y$ e& Y% v8 e) h4
3 ?% L, @  `- H* o5
6
7
8
9
10
11
12
8 P; K& `8 h0 e; r13
5 q- t" [2 y* W' K$ f! x7 m0 D6 v2 l14
15
# [. h5 o' L; C+ c6 g+ P9 ]16
8 }' e  [) }- {, ^1 o! m$ v6 H17
. g3 U3 T, k9 y/ z18
. A7 Q& Q  d# ]: ]  l19
; {9 c  X1 D$ X  }20
$ F. Q6 j/ F; l7 }/ {  f& O21
, G" J9 d( k2 [4 ?  H" O22
! B% _. Q7 M; _8 h23
: f" l$ V  g1 u( A! U24
8 u! x% E8 T$ e' Q5 T25
26
8 \2 c- |9 [8 |9 T# I# T4 C27
4 L$ N4 R" @, K28
29
30
时间、空间复杂度


: l; Z+ @  L- [% {1 r/ G1 c
3 A4 C- d, p$ R
5. 基数排序
3 G$ |( M, p: z% ^0 t直接看课本的过程图来理解P352

再看这个例子：
7 ^5 V" c. c$ K7 e
8 U+ m( l6 B% F/ l' G
0 i+ B% n& o" K( }4 W4 F) m算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
; C9 ^: k6 e3 k5 G7 _3 m2 P分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
  V& F1 C0 z5 Q3 j9 y7 `; _收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
基数排序擅长处理的问题：
①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。
算法效率分析：
7 w: t7 ]" {+ J' w时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
稳定性：稳定。

9 b8 S$ |0 x2 U& i/ k$ [  J
内部排序算法总结

9 f0 h! P7 C3 r3 P6 J; [————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" _& b+ H$ Z* I8 C- `原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969
  g- o  r* B0 x- P* B
; Q. z2 R7 I0 c0 N
4 O- U8 j% m4 K$ Y+ x+ e  h; Z9 b