数据结构：九种内部排序（动图+完整代码）

杨利霞

数据结构：九种内部排序（动图+完整代码）
1 _" t7 C" {* _- T9 _
排序
1. 插入排序
( Y: e& `' i* |4 S' p1 L1.1 直接插入排序
1.2 折半插入排序
2 g2 G- n+ ]7 i/ c7 q6 ^* [4 R1.3 希尔排序
2. 交换排序
7 E6 P( g& o1 u% P, u" L0 A$ o+ G2.1 冒泡排序
, D# @: ]: Z2 q( S2.2 快速排序
- d# j3 P' g9 {) y, N' K; U3. 选择排序
# j8 _2 x/ U* d6 u3.1 简单选择排序
3.2 堆排序
* O2 W3 l5 Z" h4. 归并排序和基数排序
4.1 归并排序
9 i" ?5 I/ H$ [% S0 d8 w1 h4.2 基数排序
5. 内部排序算法比较及应用
5.1 整体比较
5.2 时间、空间和稳定性
, E2 ?# T$ Z  T5 B- l; I8 z+ v参考资料

内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
1. 插入排序
1.1 直接插入排序
图解
( m9 v: |2 N4 {: H# G
* W' U9 k* k2 p2 h
基本思想
: p. O7 f( Y/ F/ G6 d( I
5 C; A7 S; z# }% b) T$ z1. 查找a元素在第1 ~ i-1中的位置k
' r' Y$ K  U+ ^2 D2. 将k ~ i-1位置上的所有元素向后移动一个位置
/ z% q0 a7 d2 `" g' _& n3. 将a复制到a[k]
: O. w1 T4 `8 T4 T
( ^/ M4 Y; P: E) r/ C& i
: R0 I# m" P+ d* Y$ c' A3 L) g
  A2 D5 i1 x4 \( x% w. I5 S0 z# y8 X代码
7 Y0 g$ T7 O7 v
5 h" }6 b7 K9 N1 e- s方法一：

( ?' U) G+ V( t' f1 ~) \: |数组的下标从0开始，如上图。
0 g. B; X& g. X6 Q
#include "stdio.h"
& u5 M) \9 p+ F; f2 P5 D5 ]
' x- ^9 X4 L$ o: J3 K* K: mtypedef int ElemType;
% G* g5 i& D5 _3 M1 W
% T2 s* M2 o/ Gvoid Insert(ElemType a[],int n){
    ElemType temp;
    int j;
2 Y% Q) z; v0 t5 E$ q    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
        if (a<a[i-1]){
            temp=a;                                                               
9 x5 G9 t. |& r5 g+ Q8 P            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
2 [! {, [9 F- H% C                a[j+1]=a[j];
            a[j+1]=temp;                                                       
        }
    }
}
& \) m7 ^& _$ s5 F' J! Z0 x
int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
% f' a9 \5 g/ d  H, o    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
8 p8 _+ X, l0 _, u    }
    Insert(a,n);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
) c& c3 d/ o& p# c        printf("%d\t",a);
    }
+ H& d( o% @+ f}

1
' V7 b' y$ [' R% h* f2
3
$ a* J- [8 \5 Q% n9 Y7 z7 D4
: `) N' F2 ^) w9 Q. f5
* m( @1 n6 U  |  w$ q6
. @- O8 F# ?. \  w( Y1 J7
8
- s- w3 d# V% |$ N4 s+ Q9
10
11
: _9 C: S6 W9 O/ k6 [12
13
14
15
: A5 @9 t# v1 i16
17
9 I* H9 n! N: i+ [5 ]! `0 l$ T/ F18
19
8 j* Y6 b+ z. s" |1 z20
21
, j) t5 Y( D8 a+ z# X; i' [+ |22
23
5 y; ~+ k( {1 x8 P; a. S24
. `2 A# n/ p2 \) m* g7 H25
! L- f/ g2 w9 Z- ]' R  h% V5 x* h26
27
/ x  [9 \, ?+ `  b1 Y2 U; k: ?28
4 g' L7 h! `% K1 F/ r29
; q/ Y5 e: F6 d  |$ S30
3 }7 ~% j$ T4 I" }. T, i+ L31
32
方法二：
& U- s' F# G( G% ~# O1 c
) N0 Z# ^7 D7 m/ U
, E$ B# c! x, s  ]9 a' Q
#include "stdio.h"
0 P  q0 r' F. J
: Z; V: S0 m3 Ntypedef int ElemType;

void InsertSort(ElemType a[],int n){      
    int i,j;
    for (i = 2; i <=n; i++) {
. v3 C8 A( r+ ^$ Q) m8 w  F% I; v        if (a<a[i-1]){
            a[0]=a;
: p1 q+ `; Z8 E7 U2 Q$ L            for (j = i-1; a[0]<a[j]; --j)
$ t; J/ P9 Z& @/ B                a[j+1]=a[j];
8 a+ c3 [) y" y' y; m+ w0 I+ ]( |            a[j+1]=a[0];
+ u4 I' e' ^8 m  c: i4 J2 m        }
    }
}
$ W2 G5 |* A- Q" o( Pint main(){
' Z; s/ a7 {  L7 K8 |' n$ B1 G    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
9 \3 }0 Y, y: S2 d    for (int i = 1; i <= n; ++i) {
& ~/ d+ ~' S* t3 }5 }9 Q        scanf("%d",&a);
8 J* o+ Z) t- k0 n    }
    InsertSort(a,n);
8 L& Q! T4 i  ^7 ]1 J$ M6 C    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
, z' z& b5 K  j: Q, I" z. \4 C}
/ G* k5 v  B" l" C+ _+ R
1
5 `5 c# ]) P  L# G& n2
3
/ P- z* {) i: S* j; n* [4
5
6
7
+ N8 O0 t7 t5 t+ d7 y8
9
- e6 B% S# e+ g+ z* I; ?0 L10
11
3 W4 I4 [! ?7 s3 a! F4 G12
6 r/ \- _8 m$ n7 H  U* R/ z' x13
14
# ]7 W' E" _. l6 D15
16
8 ]8 [+ H" R# w% F  {17
18
19
, L0 q  M* {: t) ~3 A20
) g: ~- e+ D" y1 C4 i21
22
23
: g  ]6 t; b; I' G! P  M" H24
) B. M% Y2 B, \25
7 H5 w$ V; d( Z2 W. s, Y/ [6 S$ v/ t26
9 m3 p: I7 }7 c: S5 U27
* D" C6 k5 y2 P; C7 Q  Y- k28
4 U: A4 G' H3 z/ w) i29
30
算法性能

6 r% \# y$ Q# }8 j空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)

* H  f7 _. b$ B, F; D6 ~$ E时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
" I7 j4 Z/ v1 h& A: |& K2
)

* C4 M' J2 l8 b% q
稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
, B7 d# E; I9 z2 V
适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

( Z( n6 K* V: _7 o3 m7 A1.2 折半插入排序
图解
# {# \+ {* W1 {  u7 X* b* p! {第一趟：
0 D; m6 ]8 x% d* o8 T
第二趟：


) B- C9 O/ a- h# y+ R! C- f' ~* a2 B第三趟：
5 v0 f! N) s. [! E: z
' u; j7 B. O3 f" {0 T# b' i第四趟：略
: A6 C6 w/ K, Z8 G( h, h第五趟：略
7 U5 G1 Y* a4 K
基本思想

与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
3 Q2 a3 `/ c1 R* W$ t% N找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
代码

8 W# q* k+ I/ {7 L/ Z#include "stdio.h"

& f- E0 Q. z% ~, p" \& a' }, dtypedef int ElemType;
  \. n7 }* m. z! E% U; u! }
void InsertSort(ElemType a[],int n){
; q( v- ?+ }! F2 A    int low,hight,mid;
4 ~0 c8 H5 ]: g8 v' Y/ ~, j; z) M    for (int i = 2; i <= n; ++i) {
        a[0]=a;
+ f; I# ]/ Q% Q0 b        low=1;hight=i-1;
; b" A0 w0 A, D. V4 Y6 {        while (low<=hight){
            mid=(low+hight)/2;
, `2 e  T; f1 x3 a% V, n5 t' y0 w' h            if (a[mid]>a[0])hight=mid-1;
& J* M5 L( `$ W5 s! ?            else low=mid+1;
        }
: y$ P. Z  C* W& w        for (int j = i-1; j >= hight+1 ; --j)
- Q" A# m/ v* e. R            a[j+1]=a[j];
5 T0 k& \/ s2 |8 E; E- ~        a[hight+1]=a[0];
    }
}


int main(){
6 Z3 c$ y5 B3 x3 \' t; _    int n;
3 S  g3 e1 d0 z. V$ y    ElemType a[n];
    printf("一共有多少个数需要排序：");
( Z0 Z8 e( h9 A) s8 N    scanf("%d",&n);
8 y. Z6 O# J3 C& z    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
) ^' K$ \# Q- H2 P9 J8 ]$ j. a7 R        scanf("%d",&a);
& H2 ~  F- B2 Y  B  v: J    }
! Y0 ]+ d2 X! [# j, e( T0 q" z: g    printf("排序后为：");
    InsertSort(a,n);
& i7 \. `" }; t" A8 Z
    for (int i = 1; i <= n; ++i) {
5 H5 u) u$ U5 Y9 _5 e) ~        printf("%d\t",a);
! N# ~; N8 T9 q( y8 `    }
}
( ^+ x' r3 r" f' P4 G1 s
1
  }# g5 G5 k  D% h2
8 H$ M- @. @3 u) p, ~3
4
. T# p* X  P) O" ?; O5
6
7
6 ?- N0 ]0 n) n8
9
10
11
12
13
: w5 A2 t& K$ o8 h* Z14
15
16
17
/ ^$ S5 y  q2 ^( z1 }18
5 m$ ]8 M* y6 G! Z19
  d0 L& D# J( y8 k' b20
21
22
23
24
4 P9 B9 e# ?7 A: w6 y7 b* Q25
26
27
0 \( [2 y( k' a) S& r28
29
30
31
32
33
" d. O6 f# Y) U1 Q% Z9 T0 {0 ~34
35
36
/ E. P# ^0 c, W5 T$ N. h: ~( p37
性能

空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
2
9 \4 J4 s0 L; [$ |/ q2 ~ )
& }8 b) e+ F* J# f7 ?+ H( E  D' P7 X稳定性：稳定
' @+ Q" |" n% j0 ]1 c% t9 g适用性：仅适用于顺序表
2 T0 I% f) Z* q* D) ?! z
1.3 希尔排序
图解(动图)
; i$ i9 ]4 ~+ ?! ?
' R! J% ?3 ?1 j& a( ]) ]
0 X/ c; c" w* O% S- r1 X7 G+ S基本思想

先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
! D" Y, m$ c, N) @
% Y& G1 K5 Z9 s; j代码
& W+ Q8 e; M, N$ R7 v3 q3 s
#include "stdio.h"

, m: {+ Z/ i% [( Vtypedef int ElemType;
, Z1 k- e& D+ Y" H9 y8 ^
+ F- u. C- O5 D& p$ A: cvoid ShellSort(ElemType a[],int n){
0 }: P& [5 U, C    int j;
. g2 U! N: R/ V3 \+ d  A0 C- ~    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
            if (a<a[i-dk]){
5 }( ~" K  ?/ T1 o9 [  q, s" b                a[0]=a;
                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
                    a[j+dk]=a[j];
                a[j+dk]=a[0];
% j4 @: B, d$ H  U( N# A( R) z0 _            }
4 Y2 Z4 u* ]  ^        }
! c  F* Y/ T6 [( E8 _  R7 u0 B- T2 ?% X. t    }
}

2 q; @3 `% c- \2 E- U) C. Oint main(){
    int n;
+ n5 r' P* X+ W& ^7 a) z2 _$ k! W    ElemType a[n];
    printf("一共有多少个数需要排序：");
1 |7 ~2 I( D8 G( m. g7 t    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
" K' {; e. B; Q4 I6 n- U- {0 N    }
0 t4 K- V9 o! B* g" i  Q    printf("排序后为：");
    ShellSort(a,n);

* L; ^' |7 a5 w    for (int i = 1; i <= n; ++i) {
0 O( P1 @8 u8 C6 \& C7 }        printf("%d\t",a);
/ Y' w# S2 k" F& o4 c    }
}
8 ^3 Y( `' y5 h/ z" H
; \8 b" Y% _. E) W0 C& C% z: v1
2
3
4
5
6
) W* Y, R& y/ s; Z! K7 \2 }  o7
8
9
10
8 Z! ^7 J( z) `% C11
12
1 S& ?1 N0 \3 ~4 I1 m/ y13
$ w4 x6 L' t$ X5 S14
/ j9 N+ ?2 k. `4 q15
+ g  _& Y: B- d: K) g16
: p! M$ ~3 `0 v3 T9 U17
18
19
20
* {" b: `. [0 ~, c  {5 o21
22
23
24
7 P7 G, S) s# a8 l. f: E25
* }/ c- m4 A4 e* J9 u* I& W$ `) V26
27
- S* q6 E; W: u' V28
* h4 N6 @3 ]  B9 d$ Y) v+ J29
30
" |; J0 u. p: h8 S& k8 Z. I31
5 i( A7 {  Z8 C( E2 k" _32
2 D0 b# v& Q" L1 C33
, w' A% D1 S. }# w34
- C5 l& v/ v5 f# A4 h7 t7 x性能
6 Z* S3 }0 o( h6 I1 i- Y
1 e% U8 M2 g7 z( A! r$ C) w) k空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
4 J" j' r/ r1 g! a" g: \1.3
/ Z. O2 ^+ T1 _. u6 S' ^9 l0 [ )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
2
, v+ f: T5 a* K; s )

2 v/ \( R& C/ A! a9 Y+ Q稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。

4 [8 w) Y9 z" V; g% C7 C
适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。
9 [: U2 X5 u# s* u9 q! y' U1 u
2 a, i! i! x. t* e; X! V2. 交换排序
2.1 冒泡排序
4 Q! \, n! }! B, H$ Y图解


; O% ?  o2 Y/ c' ?- K0 {基本思想

+ `: P- u# ]2 n! F, M1 f3 z从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。

代码

方法一：将最大元素交换到待排序列的最后一个位置

2 i2 \& X" X( B: p6 b) I1 m- H' c#include "stdio.h"

' v% y. c* K: r1 c0 @7 _typedef int ElemType;

) m2 j. j2 m( h' C' q9 ovoid BubbleSort(ElemType a[],int n){
8 ?* s- p' T1 K* y- ?    bool flag;
    for (int i = 0; i < n-1; ++i) {
        flag= false;
        for (int j = 0; j < n-i-1; ++j) {
- E$ r+ U/ o: r4 O0 ~7 a            if (a[j]>a[j+1]){
                int temp=a[j];
, V$ v, b) N: d) F8 L                a[j]=a[j+1];
                a[j+1]=temp;
# L4 n3 M2 }! l% d/ W7 l- A                flag=true;
            }
+ D9 w0 P3 e2 v5 ~  B" ?# I- z        }
        if (!flag)
            return;
# e" a1 t0 J7 l, C    }
}
+ f0 s4 g6 m/ V: R% q' X  G

& n6 L( y7 D! a- Q0 D9 [int main(){
) a: H/ t% A* a. W/ a/ U- B    int n;
    ElemType a[n];
& U" W7 {5 A# }) f5 X  Y    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
& s. Z& L0 q& [3 q2 \- w    printf("请输入%d个数：",n);
( h2 J- P1 l$ v: u8 e# u+ V$ i3 W    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
6 o* y' I' _# l% D. O! d5 n+ C; }9 ^6 o    }
    printf("排序后为：");
, c1 K" j- K$ m' S8 w2 N    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
: V8 e8 |) b! p9 w0 H. C        printf("%d\t",a);
& w  @/ r$ @, @0 K    }
6 z+ I( ~5 f" L4 r+ ~}
% }; i( J% t/ O# m1 f0 O, T
& L3 C1 l) R$ t3 o+ v$ ^- l1
8 y, L, D* C; i( P8 b$ ~2
9 n4 J- G2 K2 x) ?$ U& r3
4
; M- ]' @2 h2 A4 h8 W5
6
7
8
5 v' v  i+ c& Z( Q7 W, ^9
10
11
12
7 s4 O/ i2 s* j# ^( `& K, N0 K; N, R13
( M' \1 _5 Q; N14
15
16
- g8 `, e2 |' S6 L3 r. y, v' O17
* z' ~8 N- O( c18
* Z: U$ a& \  w19
, u, `8 s( S( f1 [8 W20
21
9 m8 A+ h0 o  x' o5 y4 H22
23
2 r% v4 K! q. g) P' W5 z: @24
( T: j' q4 S5 u+ V25
3 U0 Q$ M5 `* Q4 E8 t26
. U" M6 J- X  n2 C6 q  F27
8 w8 @! D" c0 r5 [/ n0 c% i  C28
: V. i5 ]5 E, E: H29
30
6 k6 M0 n& z, w* u" q31
  ]' F2 g8 S/ o5 z4 L) V1 A6 {8 g32
5 ]6 n- G# M" _( H" j* _33
34
$ x. M3 v0 ]8 C. s7 H  M" u35
$ Y. `/ e- |1 o) m" l5 y36
37
运行截图：
2 O" D, F- ^! z; R; S& I
$ M/ y3 Q& J2 d5 C) @
方法二：将最小元素交换到待排序列的第一个位置
' C4 m+ w3 X5 a! X) b9 K9 L
+ R3 d: m5 L" M#include "stdio.h"
' q7 B3 v, a  z9 P* Q2 n6 }
" c( K" l' ^; G- \7 d8 F* Btypedef int ElemType;
2 y$ S3 K  m# q6 p- q# l0 c3 A. d. Q9 r$ o
void BubbleSort(ElemType a[],int n){
4 T+ s! R) W& j5 ?8 ?8 Q5 H1 y    bool flag;
    for (int i = 0; i < n-1; ++i) {
) ?; X7 v% Q9 Y! Q" x5 F        flag= false;
/ p/ `; M4 I" _7 p        for (int j = n-1; j >i; --j) {
! O+ H+ k/ ]' @" }1 I% I            if (a[j-1]>a[j]){
4 {- q( L* e% P# G$ r" T4 b                int temp=a[j];
& Y) h- [1 ?4 e5 G0 V4 o                a[j]=a[j-1];
                a[j-1]=temp;
' ?7 l$ h; u/ l9 u5 V7 [3 {                flag=true;
            }
6 b7 V, v5 X( }) y$ S, c! K: L        }
9 Z: d" [5 m5 U6 C7 T$ d        if (!flag)
& i# ]' K. s5 y# i2 Q& L            return;
4 e6 P8 Q5 K' B3 A    }
}


# D/ n0 \( F6 S3 @4 Iint main(){
    int n;
    ElemType a[n];
- J% B+ |  \8 i5 p    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
; K( d/ ]# r! B    printf("请输入%d个数：",n);
6 @; ?: b! Q5 A    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
    BubbleSort(a,n);
; s# L1 n" T9 A* f% g( y    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
/ E2 |$ `' H" \& x1 @  G8 c}
/ v' v7 \  y3 U
! P4 x7 _; U& J+ X9 e# _0 @( ^5 s. [1
: b  s* _  ?7 [1 ]  ]6 j1 W- i2
3
4
5
2 P! s# R9 n  x. ~) x2 ]( s# K6
  X1 \; U: t. Z- K7
8
9
10
11
6 D* \- d* ?6 Z! G12
13
14
15
16
17
18
$ [1 a, y) n& |1 @3 S, \2 p19
1 s! u( ?3 x) G20
0 K% K. T8 \& P* b/ ~21
22
23
, J3 l1 x/ c9 }, {& H; Y6 G24
1 ]& {. `4 n3 i# O/ h25
26
27
* b' L; E* G7 q& P0 m28
7 L# n# o$ D' v% q, P! f8 O' Z29
30
7 N( ?0 @& {- D31
+ z* e% m. ]5 B2 |* [32
33
34
$ }8 a" n. X/ p) E35
36
. T8 @" L: C6 i/ Q# n1 y% o0 l37
运行截图：


+ g0 _- b2 }* d7 O性能
7 ~' n6 H! w, K9 P: m
$ E. d+ q; Q6 T. F$ ~2 g' o空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
  b( V+ s2 K: E5 b
时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
3 Y. H4 b( i( X7 J' z2
! n  w" ]  _# K4 J3 C) N/ |3 A2 F2 K )；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
)；

7 S( X$ F. x+ ?; p# h- [稳定性： 稳定

适用性: 适用于线性表为顺序存储和链式存储。

2.2 快速排序
图解（动图以后再补）
第一趟的排序：

第二趟：
1 J- i/ i  i( d3 k  J# E8 A
第三趟：

2 P, Q' i- F/ |+ b
基本思想

快速排序的基本思想是基于分治法的:

# z* a# i' n* H  V0 [: H在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
/ t8 ~0 }/ V: U  z; ~然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
代码
+ I% f, I" S- f- B( b0 A1 ^
#include "stdio.h"
6 J- |# O0 O) e5 l6 v
typedef int ElemType;
3 {! t& p& p. i. T5 {3 b
int Partition(ElemType a[],int low,int high){
    ElemType pivot=a[low];
# Z# K% X! h6 p6 f    while(low<high){
        while (low<high&&a[high]>=pivot)--high;
7 d' D1 U, o% j7 b2 p        a[low]=a[high];
        while (low<high&&a[low]<=pivot) ++low;
# ~  P* M8 x* J1 u1 |        a[high]=a[low];
  B" w4 N, q7 x% \2 m; E8 W    }
% }8 W) k& @. Q. h2 t( j# R7 B    a[low]=pivot;
3 t9 W# D& q) v  V- C    return low;
9 z1 F: {% b/ |8 P$ S}
& O6 n; p% C& W& p( |! J/ N
' x2 Y# D) B0 w+ ]+ Evoid QuickSort(ElemType a[],int low,int high){
    bool flag;
    if (low<high){
1 |, ?0 b! a1 Q4 F- ~        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
( P7 t$ q% w7 Y- o. M        QuickSort(a,pivotpos+1,high);
/ i( L( |- K/ y- M% `5 d    }
+ r' o% u( Q& l) I( Y; n2 x}

int main(){
    int n;
' n+ T4 ^4 \5 ^    ElemType a[n];
    printf("一共有多少个数需要排序：");
; y7 N) z6 A3 }, C+ E# @    scanf("%d",&n);
    printf("请输入%d个数：",n);
9 P1 B& x6 q2 c9 D7 K& f4 d" ~    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
    QuickSort(a,0,n-1);
, \* K0 b' l# e0 O& e8 j    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
6 o- U# u% B3 P    }
}

8 q! y/ i1 a* A; V9 k
1
& p% f; }* I! s* m; m9 U" m2
( k2 I3 a) `( ^( I1 x( I3
8 ]0 t9 q- P" z" V* k& P" T4
" A) d5 g0 T+ ^/ `5
( }7 F3 K# _- a7 z6
- _, H9 Q* c% _( }# l, Q7
# L. B$ a& ?1 f8
9
10
11
  u0 j- v- p& R12
13
; K8 t5 r; k  f: v1 N( O) g14
$ Z; P6 ~+ f" q/ G! t4 c2 T15
16
' V' z4 k  O8 @7 z17
" Y+ W4 [' x  ~2 h18
9 G/ C! V; u4 J* n19
2 r3 \, h& T* D0 O, @9 K! p; E5 r) T1 t20
21
) r4 [0 l2 P% e, J/ ^22
3 {1 ?0 V+ W/ |23
24
25
26
# c# H" V9 v; Y7 k27
28
29
30
/ ^( }) W% i! L31
: V3 M6 y% G* i* y  f/ Q32
7 `9 a* b  p/ w2 |8 P5 g33
34
2 V  p' [# i! Q8 v, v35
7 g: H" w% d5 ^0 W+ A36
6 U# p" n' K4 u2 A! {" V6 U37
: e; i2 A8 O' z9 x! P( u9 x  ?' P38
6 C+ ^. s% {: I: `$ I; x( S" R39
! q5 g3 w. B! r. C0 c7 ^40
$ l, T) ~9 W& ~1 X; U/ y41
性能

时间复杂度和空间复杂度
9 F4 E$ e. h: @) Z稳定性：不稳定

: f2 Z% _$ D" k- d9 C3. 选择排序
5 k6 L7 U6 O4 f/ l3.1 简单选择排序
图解

4 L, z' o8 L) w- K4 m! c
" _% t6 S" }! C基本思想
$ X5 m: ?6 u2 @* K
7 J8 _8 b8 Z+ S& ^) ]在a[0…n-1]中，将a[0]设为最小元素，设min=0
在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
2 K1 c* t. r* @3 }* X4 Q) `若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
& i# d$ g( `  Z% C在a[1…n-1]中继续进行排序。
代码

5 J) S$ E- ?& M$ h8 U4 \1 m0 p5 v#include "stdio.h"
7 J( R2 r8 E2 O$ [, z' Q  K$ X  i
typedef int ElemType;

void SelectSort(ElemType a[],int n){
    for (int i = 0; i < n-1; ++i) {
% R  w4 W6 o: N2 }# U( ]0 b        int min=i;
9 k9 f- g& b, Z# c        for (int j = i+1; j < n; ++j)
6 C; s! G) ]; c% ~+ `/ U4 ]- R- _            if (a[j]<a[min])
                min=j;
( [4 \7 M6 U0 r2 I" T% f+ D        if (min!=i){
            int temp=a[min];
5 B1 h1 T6 x( F" x0 U0 S            a[min]=a;
            a=temp;
& O' `, c4 F4 w" N- r        }
    }
+ N5 e5 K5 k) f. E% |# }5 f}

* M# b4 b7 D# S, bint main(){
    int n;
    ElemType a[n];
% F; B% l- F# k    printf("一共有多少个数需要排序：");
& j* {% `" D) c% r1 |    scanf("%d",&n);
    printf("请输入%d个数：",n);
! C0 K! N' e6 w; p$ h9 Y% a    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    SelectSort(a,n);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
4 p7 n/ y4 H4 q3 t9 f5 _    }
}
( x/ J  k- @( D7 a  b" A/ F2 q' ~  `8 }% b
9 Q$ ^( a* V1 d9 W% f5 ^/ I1
2
, `: B5 U$ L( S5 R( l; o; R: x3
4
& K6 [: L2 @& b5
6
/ H5 w4 V% h; y( l/ D' h# c7
. n6 y- D7 u# L- h8
9
10
( `# ~+ A" n/ U4 k; d* P11
0 V- s. ?4 b0 l; u! i7 Z5 _8 y* K% T12
13
$ n8 Q; O! C. S* `& \+ p" y8 A14
* J. C* D3 y7 X; x. P  j) Y15
: \0 R. E# e% G3 q; G/ M" C16
. I, ]* b# q  w+ m17
18
19
20
+ K# H& u7 z" F$ Z21
22
  r' V6 u1 `6 z( C6 c1 t23
' F8 k, D* H- x: S24
4 D; \; o! k( Y6 p# F3 w25
26
27
  k2 |4 i! ?4 M* J28
: n8 ~) ^: T: N# J" S8 ^; V. X29
( }1 ^. J/ e9 \  i7 w1 W. R30
- V; t" S- c3 [% X8 G31
32
33
% Z" a1 q+ N5 L/ j1 v" F& o7 _性能
: {; j( c: B  V, m. O
空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
2
)
" q6 \& d4 |  Q稳定性： 不稳定

使用性：顺序表和链表都适用。

3.2 堆排序
: o2 ?- N: _6 d! D- j4 N9 g看堆排序的点击这里！！！！

+ r. F! J2 X8 J+ @4. 归并排序和基数排序
9 A# c0 z( K$ O8 p: l2 C4.1 归并排序
8 Q6 d: o- D0 R! i" c图解
2路归并排序


+ V% O" |( p3 s0 g9 F1 ?; e3 R基本思想

& h: k  y5 P2 c( t将待排序列分成长度为1的子表，然后两两归并，形成有序子表

然后将子表再次进行归并，直到子表的长度=待排序表的长度。
; }, i& j8 f* ~8 }2 U代码
8 _3 i1 |# y+ Y
#include "stdio.h"
#include "stdlib.h"

typedef int ElemType;
7 r. W3 u. T  ~0 x. {1 G- L; o2 |( X  r
7 h2 m. W) L" y; ?; ?ElemType *b;

void Merge(ElemType a[],int low,int mid,int high){
8 M6 n% U8 w; e) u+ Y; I    int i,j,k;
    for (int k = low; k <= high; ++k) {
        b[k]=a[k];
    }
7 m' y  r1 V+ ^2 s6 R2 L* C1 ~2 h    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
        if (b<=b[j])  a[k]=b[i++];
  _! p4 B% Q" u8 B8 v2 ]        else a[k]=b[j++];
    }
: U4 Q1 g: I. I. ]  X% w* ?    while (i<=mid) a[k++]=b[i++];
  l& X" e3 r6 f8 w( N8 l6 J    while (j<=high) a[k++]=b[j++];
6 C1 W  ^8 E0 t0 A! a+ S}
( N& `: b; a# B
+ H6 E7 I7 T& e' N  R7 nvoid MergeSort(ElemType a[],int low,int high){
& u4 X5 D9 c" }7 i    if(low<high){
" Y+ V0 G3 m8 _% i        int mid=(low+high)/2;
! R: L% _  T  }+ K; i        MergeSort(a,low,mid);
3 h5 R: N. A0 j) K        MergeSort(a,mid+1,high);
" S$ g( v  T9 B5 Z. w5 t) Y; b        Merge(a,low,mid,high);
3 }; b( W/ p% U4 b( i$ W    }
" T" Z! L. \! f}
: b: p. D' r6 E! l0 G  b% Y  M
int main(){
    int n;
( d' d6 p  E) j; O    ElemType a[n];
    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
2 u1 }+ y: A- {( z, |    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
3 m4 o& \2 _: b! i    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
7 K8 M( K: w, K( r    }
% O2 h, u: Q" R9 y5 J    MergeSort(a,0,n-1);
, B2 ?7 I) [; ^! p9 v    printf("排序后为：");
7 f, \# L$ k% ~3 f& X    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
8 U2 I; r! y- }) Z% i+ v- |4 J}
/ W/ ]5 S( E: ]0 D: {- `8 f; X

1
2
, L( u2 H# ?& {/ Q3
4
3 J; N& P% w& S! F/ O- Y6 x3 F5
6
; s% s, t4 ~, Z- z7
; D8 c) _' l2 |0 S5 z7 w0 U8
9
1 T7 o' W( X( U+ g% ^2 [10
2 _: C3 R6 u2 H: U2 e" l11
( Y$ F8 g* ]- Z+ n; r9 Z12
# I& q$ G0 [5 v: o5 T13
14
3 t6 `  P% V; b% l% e1 R15
* P3 _, \0 U3 j5 E3 U  j16
' D" e$ h& u/ ]8 C8 p) l) }+ V17
. f9 T. c4 S; v# b; c18
' S$ O7 E0 C2 w3 w19
2 t+ J' m2 w3 w$ q" t( W20
21
7 H* y, u+ C2 s: {22
! X4 z4 F! f2 B" K8 x; H% X2 _" {23
24
25
& K' G- O# R3 C" \3 t# S26
27
28
29
30
" m- a# y: L4 Z2 I- E+ X, X; j) K31
32
* N) b4 z/ A2 L- W33
% {' S6 ?$ Z4 m1 E34
$ a$ e( Y! {# j! g35
36
37
: q. e% o2 G" y2 V* {. P38
+ w3 u4 ~5 g3 Y. r) F) f39
1 @) Y/ H8 }, O, }7 K9 l4 q40
6 h* R6 y$ n; x+ |8 J+ ^0 D% S! R41
42
) [$ O* J( `" l! f' O3 A+ a+ S) @43
1 d! n2 R8 w  }- J9 D) p3 y7 Z2 P44
7 [8 l8 }2 s& j" x45
46
: N; L, e+ M* j6 z性能
* C2 Q/ Q: Q9 L! c% h$ `" |) w
空间效率：O ( n ) O(n)O(n)      创建了一个数组b
时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
" `' V3 j' r5 ^​
n)  k指k路归并排序。
稳定性：稳定

4.2 基数排序
1 H7 w1 B3 J" _& c( c8 c/ L图解

9 Z$ ?: Q9 A# k, L8 v6 g
基本思想

7 r' H. b; d: [1 @: u. h将各个位数（个位、十位、百位…）进行对比。
为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。

7 B9 K( P" _. O; j性能
* Q9 }/ J" [2 n
( R6 p% c+ i$ G/ b* r4 S1 a0 R空间复杂度

+ m/ S) V0 L! a% S时间复杂度


稳定性：稳定
8 h( o! W7 m, b
- ^! @/ O- D+ t7 r+ A# H5 T5. 内部排序算法比较及应用
5.1 整体比较


: a6 Y: e" w" z5.2 时间、空间和稳定性
" B" Q! K/ Z% H% x) [" M/ o% I

参考资料
《王道：23数据结构考研复习资料》
————————————————
版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678

% E5 x+ X- L  B, C1 q