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

杨利霞

【史上最全内部排序算法】（直接插入、折半插入、希尔） +（冒泡、快速）+（简单选择、堆{含元素的增删}）+（归并）+ （基数）排序 + 对比总结
文章目录
4 t6 {$ o7 l6 c4 A8 L排序
1. 插⼊排序
, B, Z# B- N9 E2 Z& S（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
时间、空间复杂度
（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
0 j) q8 _7 n9 U- a' T0 h/ k时间、空间复杂度
( [5 V% y4 P  u6 Q1 V5 D4 v, k（不稳定）1.3 希尔排序【多次直接插入排序】
" v# K) n" y% t7 A. l% w& b时间、空间复杂度
; g: s  A& t9 k$ j9 n2. 交换排序
2.1 (稳定）冒泡排序
& `- _& b8 j' P% \时间、空间复杂度
  T  ~2 {; N( {) O' U3 O2 `9 u2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
时间、空间复杂度
3.选择排序
& g  ]: u( B' A8 @7 s5 @: d) i3.1 （不稳定）简单选择排序
' J: x. P: {5 o0 n- {时间、空间复杂度
8 v# N$ k# Q8 y+ B3.2 （不稳定）堆排序
# i3 P7 z& i' x+ j0 @$ t① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
② 建⽴⼤根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
+ \8 o0 [7 A" w' p/ H7 E③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
时间、空间复杂度
2 r5 K& L0 Y. I( E④ 补充：在堆中插⼊新元素
⑤ 补充：在堆中删除元素
4. （稳定）归并排序
$ W3 S! b0 @' Z* e0 n' Q① 明白什么是“2路”归并？——就是“⼆合⼀”
9 n& [3 U; E! T" Z; ?: s5 I② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
- k( b% |+ h' r" X4 x  C  E4 U5 D" g$ O! d③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
9 [4 v( d! x' c) ~6 V: B% W4 n时间、空间复杂度
$ _6 o. D. t( a; O& n  e6 U# O. L9 [5. 基数排序
( N6 `, h$ o8 r: `& {! O& O9 C内部排序算法总结
排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。

; y# i  }; Q8 O9 b8 s9 W! J排序算法的评价指标：时间复杂度、空间复杂度、稳定性。

2 F: ~7 _  c0 a' ]% p算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
  F* ^* s6 e  ]% A% g1 q/ \& W# [稳定的排序算法不一定比不稳定的排序算法要好。

% d1 F" J2 S( f9 Y- A) H
. A6 u. c& d# a/ f: D: j% K# o( w; V6 f排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
( ^& @: A3 M  m9 t  }4 {/ u外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

! I6 _  G- K/ q! i8 }0 X- P各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html


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

, E' K' B; `" M. h算法解释：（从小到大）
1 X5 C6 d" X' u

算法三个步骤：
, j. V! [. `, u. R. m
先保留要插入的数字
往后移
/ G$ ?0 H$ ^# p插入元素

% r' B- v% ~1 c1 ]// 对A[]数组中共n个元素进行插入排序
# }( k5 |- A, J1 i! O2 \. vvoid InsertSort(int A[],int n){
5 {' R; f# A1 F! }; T: D. V5 u% K    int i,j,temp;
3 e# ?, ]7 _$ X2 _, t( _- d    for(i=1; i<n; i++)
    {
! }$ M1 i& y* e' r+ ]$ I5 H% D            //如果是A[i-1] <= A，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
        if(A<A[i-1])
        {           
4 h2 \, O2 M% K* J            temp=A;  //保留要插入的数字
/ Y2 d' |, r! E  p3 A- o
9 \/ P( q5 h2 \            for(j=i-1; j>=0 && A[j]>temp; --j)
! V; G" n) ]- ~: Z                A[j+1]=A[j];    //所有大于temp的元素都向后挪
! D9 q+ G! O4 k
            A[j+1]=temp;//插入元素
        }
3 ^& ~' _9 q) F( n) d& d    }
}
7 L/ f  _8 J! e
1
2
3
# B/ c5 S4 U( S) T$ s4
5
6
; e5 A" t# q, q- {  k7
8
9
/ L9 C$ A1 E5 s& @8 X10
5 d: K0 u4 Z' `% z11
( E4 c2 S2 M, u6 p- u9 m* B12
13
14
$ U, e" T! q4 R1 c7 ?15
16
3 {$ C% ~9 j' y8 f6 w6 R- }17
; }; v0 I& Z2 d# |$ u3 p& g用算法再带入这个例子，进行加深理解


! M0 \; c0 c6 ^0 @带哨兵：


" Z' l: w) s/ x% ^补充：对链表L进行插入排序
0 e& g0 L  L1 j( s' `% A$ b
void InsertSort(LinkList &L){
; r9 }% S% y0 _+ D" M8 V    LNode *p=L->next, *pre;
    LNode *r=p->next;
    p->next=NULL;
    p=r;
    while(p!=NULL){
- t: i2 W; O( H  Z! i        r=p->next;
        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
& W; B& T2 l( b        p->next=pre->next;
0 M$ ]( Q. Q5 T/ }* v1 e' Q        pre->next=p;
" Z" I+ L) ~4 h6 c" H9 u7 l- m4 W        p=r;
3 b$ b0 I+ m( ?    }
}
1
& S$ ^, I. s; |6 h4 P8 S2
# n" p8 ]; Z) \2 M3 ]/ ?  |0 T3
: h9 B/ J" t: d) n; _& g1 m4
" O1 X1 F6 \' }: @' [' B) x5 X5
9 {9 s; G8 X; V2 g5 }8 S- @6
: t4 C$ b' M4 k  N4 r; B" Z7
8
9
10
11
3 B# I+ r. x6 J5 Q, f9 |7 j12
0 d  O& O0 y5 }$ |13
# D, u# q/ o& w0 c14
8 p9 M) d5 s8 j" ]3 t15
时间、空间复杂度
% Q' ]! f* a. r) T# _6 Z/ Y7 S
7 A4 k4 P: T: j7 s* |
: ?8 i/ g* Y; ?! R3 h3 _$ Z最好情况： 共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素
& y' L2 A$ K- B9 c; [4 `$ |- \* l5 B最好时间复杂度—— O(n)
( v2 U: _) [. E- {/ H: @
7 y- G* V2 O: V最坏情况： 【感觉第1趟：对⽐关键字2次，移动元素1次？ 】
; z' @4 P! ?! V5 p第1趟：对⽐关键字2次，移动元素3次
4 B, s$ ?- {, ]( ^6 f第2趟：对⽐关键字3次，移动元素4次
…
5 K5 F2 h- ^) `8 A第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次
' X  r2 _! G1 i) f; A5 L2 Z最坏时间复杂度——O(n2)


8 j+ j- ^! ]# h  _
) D! L2 W# |/ ^0 t: c
# _7 E% {# K' H9 E; y6 b
* N. W. z3 J4 U: R9 {; }（稳定）1.2 折半插入排序【先⽤折半查找找到应该插⼊的位置，再移动元素】
过程：

4 H3 I. ?* S  W' B' @0 k  U

' W& D$ q. e" _. `//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
{
) d9 m. _- I4 s6 k9 z5 r" ^    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
    {
- ~" @  i# Y; P        A[0]=A; //存到A[0]
' I5 E- w3 Z& `        //-----------------折半查找【代码一样】---------------------------
        low=1; high=i-1;
  T5 ?6 B% |! h8 R, g$ o  d        while(low<=high){            
, @0 c7 b  j- ~0 j8 ?/ M6 F            mid=(low+high)/2;
            if(A[mid]>A[0])
$ l+ F( Y7 f! \3 `                high=mid-1;
            else
                low=mid+1;
8 q4 c5 B1 t( ?8 L8 S4 Y        }
( p' M- q7 b( I) T+ j$ V. W2 ^         //--------------------------------------------
  J( N6 U- U, f" \        for(j=i-1; j>high+1; --j)//右移
            A[j+1]=A[j];
0 n+ z( `6 Z5 @9 j9 v: J/ f
        A[high+1]=A[0];//插入
, {, o* x8 |! y2 G  r$ J- e0 M  T. O    }
3 F0 Q# K# l* R! L}

1
2
3
4
5
6
7
8
9
10
11
6 H- O  R8 |( g! N12
$ {, `+ }1 ]5 i13
0 X& R% G) n5 J, b. w/ ^- F14
* B0 `& ]+ ^& i7 c15
16
17
# L  E: W# v- X) D2 |18
" A& L( V) R4 H; t+ `19
20
21
22
23
时间、空间复杂度
空间复杂度：O(1)

, ?( @/ B8 I/ |, G& N) T【右移】的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)

6 k+ d  O0 u( q! I
（不稳定）1.3 希尔排序【多次直接插入排序】
$ L9 j6 u( k* {" R( o3 P& K是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

算法思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
- ^' t* [4 I3 f. O. [图解：
# I8 v% C: T% w9 d1 u


0 Z/ C! z0 h5 g# S  d* c$ J$ W代码实现：
5 W% Z9 \/ W7 ]+ J8 i+ b1 C
//从小到大
- p1 P+ B  P* z8 _) \# Pvoid shellSort(int* arr, int n)
{
        int gap, i, j, temp;
        //小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
1 Z/ U8 q* i; @        for (gap = n / 2; gap >= 1; gap = gap / 2)
+ {' l4 v. n8 T- s, k( \        {
            //**********************************直接插入排序（只是步长改变）**************************************************
$ R# J8 e" P  {; N; ^: e4 ?3 X            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
7 o$ m" k6 D3 I; ?2 D) B% {            {
8 A5 B( c0 W: ~# }) q                if (arr < arr[i - gap])
; k4 [: {9 E/ s7 D! r  ]7 d5 Q+ d                {
                    temp = arr;

                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
                        arr[j + gap] = arr[j];
* ]) `& T, Q! ^7 A. H
' p; U  W2 O3 M$ ?                    arr[j + gap] = temp;//插入进去
                }
4 x% l* Q8 [# D5 `0 w2 r            }
9 ?$ _0 r5 u) V: c$ I8 R& T% y            //************************************************************************************
+ f; Y' h0 \% f- W/ m0 _        }
}

% r% N3 ]2 x7 w) B+ ~2 T1
( y; r& X9 @! _& `+ m2
3
) J* l  f7 R+ c4 p$ a! p% y: T9 W/ O4
) {( P1 f( Y. R; Z5
* F% V  \! \9 U4 J* ~6
$ O$ Y* U# l; B0 s( G7
* _' [: {/ [  I, V8
9
10
11
12
2 _! T: I/ u( S13
14
8 D3 ^$ X  A- `; h+ ?' e15
16
2 x0 {( Y! H- ?4 h( B: v1 J( {: |7 @17
: i9 E9 t- r" r1 Q0 Z18
19
( H) l; A& ~" U3 H$ Z5 ^20
21
  c  d8 a9 ~6 P+ J22
; x6 c: R, f6 E  D) A23
24
时间、空间复杂度
空间复杂度：O(1)

& s4 y- J' Y7 S% a时间复杂度：和步长的大小有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
. Q3 C$ ]9 M: P2 B: [0 p7 `
稳定性：不稳定！



, S  M* n  n2 L6 I' T3 s适⽤性：仅适⽤于顺序表，不适⽤于链表
6 f: J& |0 m# P6 ^* Q- t


2. 交换排序
2.1 (稳定）冒泡排序
- r- i; x" ^5 ~* K  f1 {英文:bubble sort     (bubble 动和名词 起泡，冒泡)
" X- c- C# q$ E- _1 k, E% @3 N从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
$ Y  s* y( A' ?, K  M/ N
每一轮比较会让一个最大数字沉底或者一个最小数字上浮

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
7 U. k. ?8 R  `+ H
实现代码：

//从小到大：
( H8 j: m# j$ o% N# u2 C+ t% nvoid bubble_sort(int arr[], int len)//冒泡排序int*arr
{
        int temp;
        for (int i = 0; i < len - 1; ++i)//循环比较次数
3 z: m. T* G/ ]% T) W        {
                //for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
% @) b" b4 V% [+ n4 N4 A' N7 X/ u5 R                for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
                {
                        if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
  v+ E& t1 i2 S; f2 q3 z8 `( _5 b( G                        {
                                //交换两个元素位置
3 H  o% j; H9 L3 a/ I1 L                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
7 D# Q6 U4 ^5 \0 U8 b                        }
1 t" S, E/ I) k' I                }
6 v; ^% }) B, ~        }
: Y% t/ w' @: ]& ?7 ?( j}
* L4 {6 O2 I, g+ M4 }2 I. o) T$ }
/ x6 ?# _; O6 m: u$ q, l1
2
$ p) `* ~5 P! ~3
4
- \4 O& F0 v1 q" x* G. T5
6
7
* U% h1 L% V; Z! A; x! g8
1 ]- F( A) c' R6 A% A/ Z% V9
% b$ t% ~2 }7 A# ]2 }10
11
6 o6 M/ }4 w8 S4 }( ]6 d; R12
13
14
15
16
17
' c2 G5 ^; r4 k1 m$ M6 |& z9 ~+ S1 |6 D& V18
" w) f) b3 \. z/ R  ]0 H19
  C6 D/ W& K( n. J优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：

//从小到大：
% ^$ m! a. t, F" Q. y! {void bubble_sort(int arr[], int len)
* x- M0 M. t- @) o2 E{
        int temp;
  a, ~5 x0 H8 l1 t0 {4 X        bool flag;
" W: A, h3 c8 G: j% E        for (int i = 0; i < len - 1; ++i)
        {
( a+ t* D6 j5 c            //表示本趟冒泡是否发生交换的标志
  L8 H( t' s0 x. n0 Q* E2 I                flag=false;
               
                for (int j = 0; j < len - 1 - i; ++j)
                {
                        if (arr[j] > arr[j + 1])//稳定的原因
                        {
                                temp = arr[j];
) s& R1 D* p0 D                                arr[j] = arr[j + 1];
  P$ I. c% t- v* O/ ]) ~8 e                                arr[j + 1] = temp;
                                //有发生交换
                                flag=true;
7 Y6 K  |7 L. W) O4 |) S6 E  j. x                        }
# w" H  Y* P- K  C; b+ S  k- f& I                }//for
5 J9 F9 F  v7 f               
+ V, U. b0 T1 r: l6 W                //本趟遍历后没有发生交换，说明表已经有序
                if(flag==false)return;【1】
        }//for
}

1
1 Y9 K/ ?% w+ X; B7 F; L2
3
; V3 ?( f+ |5 q  Q* _( G4
5
9 v; A+ C7 H/ |* _/ X2 q6
; H5 |$ N' d" S* S) ~6 j% c- E7
8
9
10
' _" U  {( H4 ~5 E5 Y: Y11
12
1 j2 P& [3 c! r% C; e9 u+ @13
14
15
16
0 w" f: b5 v- K8 d1 Z$ [17
18
' ^7 L$ F/ l' H+ S! k$ J19
20
' @# Q5 {! T7 E' N# i2 Y6 ]. T21
# ?' ?* H4 l( I" v22
23
4 {& `' H( _; Z/ I: ]0 T0 N24
  b( X# y: D. J+ Z3 D7 M4 n25
26
时间、空间复杂度

! h6 ]( u7 T8 ~4 F; O9 m1 N适用性：冒泡排序可以用于顺序表、链表

. L# P4 S! T& \0 E% u8 j

" X2 P' p0 H0 Q8 k3 J0 k
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），
* }3 Y& {: T) d- r通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1] 和 L[k+1…n]，
. F6 d$ K9 \3 {2 x$ h: L' l! s( Y使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，
再令pivot放在位置L(k)上，这个过程称为⼀次“划分”。
* E% _5 J: F! Z3 h( F5 l9 X" P& ^; u
6 M2 N& R3 u. U, j+ `) L: v然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
0 U3 @& D; c* a
划分的过程：
+ q0 L2 P$ H2 M. F
初始状态：取首元素为pivot，定义low，high指针

- k+ t' @& y$ u2 Z1 |& ^  l首元素为49
& n& i% [$ F* f5 c9 f7 \4 K+ k: H2 `  Thigh指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置


. b# X# {" X' v3 ?


// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
        //取首元素为pivot
! j* n4 G1 y) \: w' }4 Z4 \    int pivot = A[low];
9 W, N% I  b+ |, U  I% s% ~
9 Y+ C6 f( ^# z7 D! ^& E    while(low<high)
  l; o" ^8 o7 E5 v5 M9 D9 h- F; {! @; q    {
            //先是high开始向左移动
        while(low<high && A[high]>=pivot)
6 m4 y+ X, a. E! m7 c            --high;
( q: V9 u! G7 W+ W$ Z$ |7 n" J* z        A[low] = A[high];
- ?& n0 s9 e! l; z& d8 K
5 s, W; c3 z! p: d+ T7 ]. a: ?        //随后low向右移动
7 e5 L+ ~5 s3 K/ ?5 [9 H0 c# R        while(low<high && A[low]<=pivot)
            ++low;
6 l; ?; g9 n, N3 @0 a% g) p& f% n        A[high] = A[low];
    }
& Y+ [( [2 i! P: d, ^9 i. {9 z( P
( z: w! @- X2 p: Z2 @/ b    //low=high的位置，即pivot放在的位置
9 z: z8 [; u$ y4 o    A[low] = pivot;
  E* N$ s9 v. J% L
. ^( N2 e: I7 X  C9 W    return low;
}

. \" _3 ~! `; l) a% f7 w3 V' Q# {// 对A[]数组的low到high进行快速排序
$ |; m3 {1 Q4 x" ivoid 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);
% H! x1 w6 K, Y4 v) w4 m    }
2 d3 |2 m, i+ X0 ]+ u}

1
2
$ P# e1 x7 X  p* ]4 z# W3
9 X1 B2 o3 F; Y' ?5 m# W4 T! C/ i4
5 }$ I/ {- ?# |2 P( C9 x5
6
7
3 G0 S' z' |' q% ~, V9 j! w% ?5 F8
9
10
11
) _; G$ L! K, z& i12
5 U& U' R" U. b! T- o% t/ D. ^13
14
3 S2 i+ s0 `* q4 ?  F2 P5 n1 H15
16
17
18
19
) |% I' k2 ~3 A+ k. @20
21
22
23
24
25
4 q* l1 I9 J- ?; ]26
27
28
29
' Y8 z8 \7 n; k, J- q30
' }* M. f3 F4 ~6 f: H5 a" x31
: ]7 s* ~; m6 ^' O% M32
时间、空间复杂度


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

4 t6 X2 G. i+ _" s! Zn个结点的⼆叉树： 最⼩⾼度 = ⌊log2n⌋ + 1，最⼤⾼度 = n

$ T; v3 |+ W. J% H% n4 [; Y6 S时间复杂度=O(n*递归层数)
* q: V3 }/ ?$ _( ]5 w最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法
7 g# L# a  z. _" D1 r3 i
" M9 E3 @( Q# @空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
. `# X3 R4 E  R3 D& j  c7 R* N最坏空间复杂度=O(n)
- X+ k: Y9 Q. x( `8 I) k8 g4 p
  \1 P& X" V9 e8 [$ i+ Y最坏的情况

- D7 b4 ~7 W9 C8 C
# m! u; j. b% _% R4 f4 l* u
$ h  C$ k- k3 c( R⽐较好的情况



) b1 |) s# T( S+ w) I; C6 F" b3 b不稳定的原因：


% j) d9 A, y/ A  Q
4 I- t4 {6 L, l+ e
$ I' _2 y8 O- H  q6 s; B+ O4 W
, q9 y" o. d0 V* F( O+ a" n3.选择排序
7 M: d- ^* Z* j  S+ S# [0 P, q' X选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
7 V4 K6 x- S0 g* t
3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置


- Z1 @' e) A5 T9 I8 D
// 交换a和b的值
* I  r! A. ?; C0 C& Y. t% t# yvoid swap(int &a, int &b){
    int temp = a;
    a = b;
9 U. k) Y$ d9 Y. ]    b = temp;
}
5 h2 `0 h$ N2 g/ G0 g6 q! J
; R' z( G' d" r9 i, ?/ k& ?// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
{
        //一共进行n-1趟，i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
    {                 
        int min = i;
$ _1 n& C5 W# j( x0 _! k, s( a7 g        for(int j=i+1; j<n; j++){                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
( x6 E$ g7 B, Q% d                min = j;
' A, }+ E0 N, Q, F9 m        }
        if(min!=i)                     
            swap(A, A[min]);
    }
}

5 h( W8 X" b; J2 v6 \& [1
7 A$ C8 }2 `1 w2
3
6 r) s- j' H3 C( [- K1 U- J4
5
6
7
8
9
. c9 ^' N' ?7 T10
11
1 d/ \: U9 \# e0 E9 W0 v- t12
13
14
9 v+ u, Q  C1 A5 r  @15
16
* X) s2 N8 Y2 r7 D5 A# e6 U17
: e5 M8 X9 G  F4 L2 G4 E' B18
19
20
' {2 n% g6 o: W$ U9 a& K21
/ R. q: H# j; v9 k. V: |22
9 {6 _% B, H4 j1 h补充：对链表进行简单选择排序
8 ]& S. c& v) Z) {- C
void selectSort(LinkList &L){
/ y  d; f7 ^! p2 c    LNode *h=L,*p,*q,*r,*s;
# G3 [4 j* g1 |4 x7 ^2 u* x- j    L=NULL;
    while(h!=NULL){
        p=s=h; q=r=NULL;
8 U9 `5 L) M# B6 C% E        while(p!=NULL){
- ~, Q$ C* |: K' A; a# V* ^            if(p->data>s->data){
                s=p; r=q;
# E% C" }: @+ ~1 P: N7 u$ Z            }
6 x  [! a4 j# M. H$ w) x            q=p; p=p->next;
1 ^- d2 v' D' U* B0 C        }
        if(s==h)
; s/ q, e1 C) R8 R            h=h->next;
        else
6 h  P5 a- z* [' z            r->next=s->next;
& ?: o' `5 I3 f8 ^        s->next=L; L=s;
    }
}
. X# J4 |4 ~- S8 \& k% d
1
2
1 c- ]: Y* C1 ~* ^3
9 @( {5 ^: S( N  [4
; R' i5 b9 w5 u5
6
1 W! w# r/ }% [& v" J7
8
9
- Y( s5 ]! |) J10
11
( ~0 E+ r2 h! l  i3 f12
  M9 J. j3 q, \" i0 P' L2 t13
; @( x2 P5 y6 H' [14
# E& E8 l! N, w: q  A: @15
$ X0 q$ j* Z& h$ z7 L) r16
. T) x7 j- Q4 j% s3 q% A! d9 h" y/ c17
, b5 F: V) ^7 _& `! ~: n18
时间、空间复杂度


+ w$ L0 r7 Y0 r5 V; y. l, i

适用性：适用于顺序存储和链式存储的线性表。
- `7 ~1 \" W7 o! n) f! U2 b

9 b( i& d. k4 J, |4 A) `! n7 Q
% x7 K3 X3 F! r, m$ h3.2 （不稳定）堆排序
; H) P! S" ]) D0 _+ S& b' c① 什么是堆、⼤根堆（⼤顶堆）、⼩根堆（⼩顶堆）？
堆是具有以下性质的完全二叉树：
& g' I9 s; V- J' K每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
- o7 k, j5 L7 ^( |8 F- j


  I5 t4 p, [" @  v- F即：
若满⾜：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
0 z9 b# m3 o) p7 R& X; p若满⾜：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)
思路：
把所有⾮终端结点都检查⼀遍，看是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋，也就是检查 i=1 到 i=⌊n/2⌋ 之间的所有结点
+ M& V4 v2 ~) Z) Z/ k* n. S5 C% m
' [! E0 E, J; q# @+ }检查内容：是否满⾜ 根 ≥ 左、右，若不满⾜，将当前结点与其更⼤的⼀个孩⼦互换

过程例子：
; t% e" D" ]& E7 ~3 [2 K

) O. n: _7 K' V! Q* p
建⽴⼤根堆（代码）：
! p' [# t: U% u1 W4 t7 F$ f


// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
1 @; v4 K: N3 \) {8 T/ R+ z}

- O3 Z" V0 _" b% L// 将以k为根的子树调整为大根堆
) N; Y1 [! n) `6 B1 m  V# k  {void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
. N8 N: R% [7 w% a! l    for(int i=2*k; i<=len; i*=2){        //沿k较大的子结点向下调整
        if(i<len && A<A[i+1])       
            i++;
        if(A[0] >= A)
            break;
% `0 `5 M5 S" S        else{
            A[k] = A;                        //将A调整至双亲结点上
% C: l+ r, L* J7 t: i            k=i;                                        //修改k值，以便继续向下筛选
        }
7 Y- o" U# f7 x* q: ]3 I    }
    A[k] = A[0]
}

1
5 l6 g: \) t. o( F' [- T, ~! i2
# k" M: O1 y2 |( u* [, s+ A! ^3
  ~6 [# n- V. ^2 G4
, z. W9 Y0 I5 C/ U* m5
9 z/ q, N  m& A6
7
$ {" F8 j, T5 ~8 Q# |, I# a  G8
) U; i( ^, J* |" a+ k% N9
10
11
12
13
; v6 W: A0 {8 F2 f  x4 `6 a; {14
15
  f/ ]. y' X$ a16
17
/ r+ u3 ^0 }. m18
6 \7 X. m* ]! o5 y4 b1 V19
20
4 R, K1 u* \, ]  }, m' T0 s9 A21
③基于⼤根堆进⾏排序：HeapSort(int A[], int len)
- _, S9 x/ }* Q/ Q2 J选择排序：每⼀趟在待排序元素中，选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

1 V7 [7 n- n" ~; v8 S0 l1 W) J$ C堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（即与待排序序列中的最后⼀个元素交换）
, y0 a* R, w5 U6 w( C
过程：

) e8 O3 B- N; f5 e- W- ~/ W- E// 交换a和b的值
4 f( x$ m) v8 ?; ivoid swap(int &a, int &b){
: J, _% K" i7 h# ?  h    int temp = a;
- G% ~. U  j2 D- w2 D    a = b;
4 p: {7 U5 M; ]4 R0 a    b = temp;
}
- a: Q" v7 y9 l/ t# j' O/ B8 K
) v. x8 Q& a. P3 S// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
, \3 r. R" v/ U        //初始建立大根堆
    BuildMaxHeap(A, len);                
: v. ?) b, Z4 j) s) J8 z
    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
8 c9 Z: T9 T( A. ~4 `# K0 E) t. @    {             
' Z) }2 i; _8 y) r% z5 u& R3 j        swap(A, A[1]);
, T! }8 d- O3 |        HeadAdjust(A,1,i-1);
    }
8 G! b  j+ q2 g2 W# K}
9 `- s5 r9 N# W) \( L: b' J
, M( ?* J5 X$ A' [' R1
+ H+ v, K  L: c2
/ w' V# j7 r' C  f) A( S3
; E; s8 J5 B, Q$ y( R  L% f! P- W4
9 d/ r( d, J1 y- P5
6
7
8
9
10
$ _( O8 {$ }4 H, w$ _11
12
13
' n0 W" @% k. b$ g5 x; b( Z) y14
% f" a0 v( j5 q4 |3 Z  B, O15
" T# Q) C9 H; b# z5 W2 J5 {6 Q- t16
& o2 u7 H6 B) S! U6 d/ N3 e17
6 Z) |3 i  m2 W$ J7 V18
19
时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

空间复杂度 = O(1)

6 ?- c+ Z# l& S1 g5 ?2 C+ C结论：堆排序是不稳定的


$ }" y9 g* A' q9 ^2 y④ 补充：在堆中插⼊新元素
# o$ I1 k( J& C6 L对于⼩根堆，新元素放到表尾，并与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。
. J% t2 d, u/ }( i3 t8 F0 _% |新元素就这样⼀路“上升”，直到⽆法继续上升为⽌


% x/ r  N2 K7 l# f- Y2 t; f
⑤ 补充：在堆中删除元素
被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌




" W( Z6 [5 D. g$ K6 T* r) F( F4 o* u7 z
4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成⼀个

① 明白什么是“2路”归并？——就是“⼆合⼀”
" g" a/ x5 K& w6 _7 I  a. _5 s. j
- A; D% o1 L: V# A5 C( D6 d多路归并：


② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
; b3 y, t6 ]" r1 S( f1 |1 c
③递归进行分治思想【MergeSort(int A[], int low, int high)】
, B; G$ r) j: @' t7 j2 `

* c# `0 W& \) I  s+ j④ 总实现代码
// 辅助数组B
- g2 q. k: h! vint *B=(int *)malloc(n*sizeof(int));
- j" O4 Z8 b1 x# N
( R' K. W# O+ b, {9 _// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
- S( M" O; u6 J" l; ~- fvoid Merge(int A[], int low, int mid, int high){
+ `1 ~' Z5 [! f) Y7 I    int i,j,k;
1 y8 h* l3 v% d- X% v; d; S    for(k=low; k<=high; k++)
        B[k]=A[k];
5 i, G% _7 o( C! z    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
5 ^4 X4 |0 S/ k; [1 m: ]        if(B<=B[j])
            A[k]=B[i++];
        else
: Z8 F/ \) l: F0 Z, |6 v* c& z. x2 |            A[k]=B[j++];
* y1 L( p0 S0 \# c& h8 \' q! a7 q    }
2 i8 k% |: f/ B    while(i<=mid)
        A[k++]=B[i++];
    while(j<=high)
8 Q* v! g0 v- |: h% ^$ ?        A[k++]=B[j++];
6 O, X( p/ Y6 Y% y}

+ ~4 G9 v- f! X8 h
+ n5 q' K- \9 C% I& e// 递归操作（使用了分治法思想）
# T3 V* ^+ ^: Xvoid MergeSort(int A[], int low, int high){
3 |& H* @4 h& x& Y5 t' p1 `" r    if(low<high){
$ d  w3 y) {" d9 F# t0 z        int mid = (low+high)/2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
- x( e* I7 V# C        Merge(A,low,mid,high);     //归并
8 B0 I! |" H0 m2 {: p6 i, t    }
}
3 W) _8 e; I9 f9 R1 L0 N7 s6 Y
: q: |# s" c! v, ~. O  `* K0 ], s% Z1
" t0 N  j+ u, F' c! o2
1 N* o5 D& e9 `3 L& Y( I& f3
4
5
2 y0 b5 a" s& o5 V1 ~' f: B/ p6
7
( \& I% n9 S" A4 A- E- |8
/ G% K8 _  [* x- `9
10
11
, Y2 D( i. K; J12
13
, p  s4 Z: `1 x/ R14
15
16
17
* k0 y8 A+ K) u18
5 h5 L4 h8 \! V) U, V19
/ A/ t. v' ~" I. |; S5 J0 D20
9 C! W3 q3 p4 b1 ]21
22
) q3 l8 f  S+ \0 D+ h23
24
0 m' u+ B" Y. j, W$ y  F25
26
27
$ s$ M, n% w, R! @# B# h28
29
30
时间、空间复杂度
2 L% y+ b; I. ?- Q


6 ~/ a9 D& |, U% h9 R
1 G. t3 T% x& ]: p5. 基数排序
" M. ~0 v4 B# f4 z5 A# [# |  J直接看课本的过程图来理解P352
; C  [. H( t4 m) G
再看这个例子：


算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。
. K' c, p8 I$ Q收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
# |2 ~3 X8 l) j0 R1 e: l6 e; v  d基数排序擅长处理的问题：
; Z# O& U6 ^3 N4 U- \  V①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。
# D3 n5 ?7 H. x# k$ F: K2 m* d6 R算法效率分析：
+ D" X) j/ ?) W2 m# ], I7 i, ]% w时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.
空间复杂度： O( r ) ，其中r为辅助队列数量。
+ E: u$ H. [# m; J; r稳定性：稳定。

0 ~2 u, ~1 i1 k( j" _
! @* B! B* Z  T  S+ ~9 l( w; p内部排序算法总结
) L5 o8 ^6 @8 J! {( x
————————————————
版权声明：本文为CSDN博主「我把夜熬成了白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! g+ E! g' l; d' f* @原文链接：https://blog.csdn.net/weixin_42214698/article/details/126520969

; _- h" o" e3 g! F6 y6 I
! n; N' |# {- b: k9 X& H" m: Z