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

杨利霞

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

排序
1. 插入排序
( l6 G4 J" X: @6 K9 ?6 I1.1 直接插入排序
1.2 折半插入排序
1.3 希尔排序
- A) X* s0 R" l2. 交换排序
2.1 冒泡排序
, P9 E/ [2 t- T: s7 M8 d2.2 快速排序
5 E# Z0 y* {. A3. 选择排序
0 Y# |( n- v$ m$ S$ }3.1 简单选择排序
! I6 a* m" p# g3.2 堆排序
  i: m4 ^8 G: R0 R/ p! d2 D; @4. 归并排序和基数排序
4.1 归并排序
5 k0 z- r3 `' _4 ?' ~1 W4 s4.2 基数排序
5. 内部排序算法比较及应用
5.1 整体比较
5.2 时间、空间和稳定性
2 X& I+ u6 J1 u  d( u参考资料

& {  x; c7 b. h' v  @内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
1. 插入排序
1.1 直接插入排序
图解

* N0 l3 t  M% M3 y% [
基本思想

1. 查找a元素在第1 ~ i-1中的位置k
2. 将k ~ i-1位置上的所有元素向后移动一个位置
3. 将a复制到a[k]



' ]/ r) k! G; l, U代码
/ @1 H, q8 |) w
方法一：

" X+ H8 {: [- o+ b- R数组的下标从0开始，如上图。
! Q  F+ x. {% v' t5 E
#include "stdio.h"
1 t' W9 x" n1 T( Y1 i
. D8 G: N) a1 ^3 b/ o. \" J6 Jtypedef int ElemType;

: |5 N2 D1 @. z2 P: @void Insert(ElemType a[],int n){
    ElemType temp;
# j  X' {% u* q$ y$ \    int j;
1 t. D, e; b" [2 u+ K    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
$ ?& P1 D* Q4 D! c) v" _$ ]+ A        if (a<a[i-1]){
5 _4 x; U9 W0 K. J& V' z9 n9 v- k            temp=a;                                                               
            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
7 o6 R  [* q6 M$ \, k% V1 K$ e                a[j+1]=a[j];
            a[j+1]=temp;                                                       
        }
9 n2 c! ^: u- M' V# Z; d/ S    }
}
3 s" S7 S7 ]. J6 r- Y! _$ O
int main(){
6 |1 e( P$ S; y- p: [    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
* J0 \4 Y5 I% ~5 m    }
    Insert(a,n);
+ Y# A" ?: C/ A2 Z7 g    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
) J$ x+ b+ i3 u7 n% B6 U        printf("%d\t",a);
    }
}

1
) ]# g. {3 l0 y7 j2
4 `( ?4 _8 S! n/ G3
3 M" L! N& W$ ]4
5
6
7
8
6 l4 ?' b; U4 M7 I$ I4 _+ V9
2 I9 c9 ]# l& D9 k: L# S# g- o" V  C10
* h  e' [' O' X- g4 F$ u11
, `" i' M9 ^( n" b/ [6 g12
13
& k- Z9 {; x# w: h% V14
15
7 I& o: H4 W7 _' v16
17
- I$ s* n( O1 b, m) C$ ~- G/ V, y9 ]18
: H; ]3 s* i0 O# a! T  d& ~19
+ {) l  X9 z% Y  I! ?  e20
: W1 i3 o- G+ s( ~- S$ c; l, k21
22
( N: t$ {; x* i: F, R  T5 C" N5 P! u  m23
24
6 w. z# N' ?- _6 R% G8 G& {3 b25
26
27
/ _+ X- J% G# k28
29
30
+ ?! [2 g4 y1 G8 |31
# v9 w+ y- w) Q5 I* ~32
方法二：
( s* \- _. m3 Y( H
& J4 T- S! ^# N8 _. ]- }5 z

! X/ E& e% P7 u4 S- c#include "stdio.h"

' y! V; E2 f; O: Xtypedef int ElemType;

6 T8 K# b+ c7 x$ c2 nvoid InsertSort(ElemType a[],int n){      
    int i,j;
    for (i = 2; i <=n; i++) {
1 z$ H9 f+ @* ?1 [( V/ n. P/ {        if (a<a[i-1]){
2 T  t. J& Q" M7 C- |8 e            a[0]=a;
            for (j = i-1; a[0]<a[j]; --j)
                a[j+1]=a[j];
            a[j+1]=a[0];
( I- r+ M% m/ g3 I. g: V        }
    }
}
int main(){
0 l! e; {$ B/ b  |8 Q1 M    int n;
2 \1 e3 E- S8 x+ O4 u3 K7 e8 H* k! [    ElemType a[n];
  P+ O5 C7 N% X3 L9 c( C( q6 o3 G7 X    printf("一共有多少个数需要排序：");
) k# V& ^9 i4 G  @9 @* t    scanf("%d",&n);
! i* _3 v3 Y( \    printf("请输入%d个数：",n);
, k# ]0 s5 z; l0 }; |    for (int i = 1; i <= n; ++i) {
- a; e# v( ^" ^6 E        scanf("%d",&a);
$ e+ F) T' r+ C) t4 l/ ]" D    }
    InsertSort(a,n);
    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
2 x0 V; q$ x' k: Q) E    }
}

1
. D7 E) g- k& z2
3
& L. E& E7 N8 t) A4 k. c7 |4
5
: ^" p6 E2 O- f+ M8 x7 h6
% }! D5 A/ \" S7
8
9
" |: }7 k, d/ n10
: r' r% P$ f! E$ k! i' B( d11
12
  m. q# S5 \; Q2 [$ [- Q13
% R% W8 W  c( y14
15
16
! {% L- t: n2 s17
18
19
20
! ~9 E. X* I$ O8 B3 M, V* y21
22
" Z. _. K3 z: E7 I/ L6 W. f- W* \* _23
24
4 t8 v1 w8 ^1 j1 m7 c. o25
+ X) P* I2 H+ `4 Z8 R26
, R8 S. h& F: ]0 ?2 Z* G27
8 ?: S* d! }" \0 B5 w' m4 J28
4 X" `4 y" ~7 `/ d  n  O29
30
算法性能
$ Y+ s  k- c0 d+ K
空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)

6 [" _5 @! C5 N6 d8 U! h  E时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
2 r8 ^& b3 }- i+ J2
3 w4 \" O; D8 p! P )
2 V, ?2 |$ F2 J: @& R4 v
+ U( H! r- _; A3 `* u  H6 _
0 I+ F* i3 K% R+ N/ J5 I稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
. h- l6 _- ?+ j: P( S
, t5 m4 r" b+ I6 n* O适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

1.2 折半插入排序
! d- v% R$ ^3 Y7 [+ X" k1 s图解
第一趟：
) `) G4 b  Q) @. v$ K. B* m
9 b  G* w0 F# C( }, M1 a% J第二趟：
$ U- j# V7 U# J2 p
: b: f4 W: {# k: L& N% h% X
  }3 U) K. M3 s$ j第三趟：

+ ~" g, T9 e  A! }第四趟：略
第五趟：略

基本思想
/ R/ U8 V' J0 c7 N$ Q, x
与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
0 v, r; V) s% K) V+ ]' I取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
代码

#include "stdio.h"

" s+ @% s7 t5 g  e: p* ]typedef int ElemType;

void InsertSort(ElemType a[],int n){
    int low,hight,mid;
    for (int i = 2; i <= n; ++i) {
8 F4 o, j, n6 e) ~9 Q        a[0]=a;
1 c" S9 ^. O% Q/ J2 U( e        low=1;hight=i-1;
        while (low<=hight){
            mid=(low+hight)/2;
, E7 b6 `) W: n& e            if (a[mid]>a[0])hight=mid-1;
  c6 Q2 g, ^6 B. q  ~            else low=mid+1;
        }
        for (int j = i-1; j >= hight+1 ; --j)
: H3 G- [/ ?7 N) K6 U1 _            a[j+1]=a[j];
        a[hight+1]=a[0];
    }
}

- W$ }9 ~  H5 B9 ^
int main(){
! ?, n) q  h  S+ y: t8 W    int n;
2 h. m; n1 @; w8 Q    ElemType a[n];
    printf("一共有多少个数需要排序：");
& v' \7 H  Q9 x- k$ L    scanf("%d",&n);
    printf("请输入%d个数：",n);
9 v2 p( X" U2 H. o    for (int i = 1; i <= n; ++i) {
4 p8 O) h0 M; k, {0 q# W4 b1 d2 _/ B5 L        scanf("%d",&a);
    }
    printf("排序后为：");
    InsertSort(a,n);
: T+ I8 _5 T& I& E7 O7 Y
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
5 q3 m! ?1 u2 ^% o8 v" Q; o6 [8 [  i    }
# G; m' @- [& G& a" F& e8 x# c}
  d7 P  \* k' [# F
1
. c  f/ c  M% q2 U/ G2
' ]/ z# k8 w: ]% ^* @" b3
4
5
5 G9 m  [+ R4 x6
! Y( C8 ~" A, F# T5 C7 }0 d+ ?" [1 B7
4 D9 E8 R' M3 p) h1 c" u, v8
* y/ m1 N% s  `  X, F9
10
11
0 P: b4 U( t$ ~0 d) x12
; w8 E# i7 D" {# V13
0 p7 v: U  h6 x5 L* k14
15
5 U9 X( j$ O; y+ X/ g  r' ^16
& F7 C  R8 u' p$ S$ A  x0 N0 h17
$ ^, S8 {0 K1 Y4 d( p18
19
20
21
* `- `0 |1 x! R8 m8 A2 N) Q3 F$ _22
8 a1 T/ i* a$ a2 n9 L' z- ]23
24
25
  ^5 v) r0 a0 [26
* G! ~* |0 v7 s# z6 M4 z1 m" T3 G27
28
2 O; _" b1 N: A( E29
+ G. `# q: Y9 a! Z2 k30
31
6 C1 `0 \) K) r- G; o3 r7 A32
33
4 q/ W5 J3 x+ \* r+ ]34
% N  {/ q' _; `35
36
37
) q, g3 Y- b5 P! S  ]4 q* [性能
4 a8 q( z. @' W- g: C: ]4 I: h
空间复杂度：O ( 1 ) O(1)O(1)
# ^( V$ ^$ n1 x: w9 p时间复杂度：O ( n 2 ) O(n^2)O(n
2
. l( p1 X# m1 A )
; ]+ s- k7 n  u" z) A5 l稳定性：稳定
适用性：仅适用于顺序表

1.3 希尔排序
' n- ]5 f3 w3 t# e1 M图解(动图)
0 ]9 ~3 d& g  \
$ f, p/ B9 \2 ]" u3 N
基本思想
1 ^4 @; r! [2 p5 v
- H! I5 e9 G7 t先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
! p  ^3 U" {5 D, T
7 X9 N+ V6 O0 C+ r代码
, \$ h$ W8 Q) K  F! B, n
#include "stdio.h"

; ?6 s; \; f: ?% A, htypedef int ElemType;
7 D4 [; ?! A: N3 d, b; L
1 p: S- O6 l& w; ~void ShellSort(ElemType a[],int n){
8 G. x' x( N' a5 ]# ~# N, g    int j;
    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
7 S& q) V0 Z! Y        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
            if (a<a[i-dk]){
                a[0]=a;
' b: K2 Q; c" R/ ]                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
                    a[j+dk]=a[j];
+ z- v9 X* i0 r. s                a[j+dk]=a[0];
  \' H3 O6 S6 `4 \            }
4 m+ `" o0 u5 G+ K        }
    }
}
3 `0 L9 p' e2 w! ]
int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
" I5 t* ^  Q: p8 ~    scanf("%d",&n);
+ i9 r; C- b4 u+ M3 n$ ~7 B    printf("请输入%d个数：",n);
6 h9 ?9 Z, O; B) ], I    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
    ShellSort(a,n);
' [5 f  K- x% \' \' L
    for (int i = 1; i <= n; ++i) {
% T. t$ H7 L" U! ]% Z5 n  I        printf("%d\t",a);
    }
}

1 g/ E+ N0 B! M/ O3 H  x3 j1
2
3
4
( w  Q% g& d' B  _5
6
2 q, e! z/ \. j$ ?- i. e1 e7
! _) }4 V7 {1 u, r/ B/ G8
9
" g1 _; l+ C9 S  }+ @10
3 p6 q$ v; g/ {11
12
; |) A; I2 o, d" ^. d' H9 Y13
14
15
7 k! z- g2 U) o) D0 ]2 X+ {16
17
18
19
- l& J/ _, l7 ~* Y; A, {8 |20
6 d" S4 r! \# O/ L; h* X  ?21
  y3 |! S8 J$ y2 ^* I7 w22
9 C2 c4 M. U- F! X23
24
3 a0 [' Y1 _, S" V1 D& }25
26
27
( D, {- i$ z/ I" u28
29
+ B+ ]; l  o, D! z. U30
7 S6 u0 n% o. g' Y31
32
33
% J. a6 r3 N' t+ y7 P8 p/ M34
性能
5 b1 j0 _! g  w2 W' {9 K& t8 I
2 S; H- G) ^0 b空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
( e4 k6 v" M- A4 \6 S, w0 o+ ]
, Q+ @! c( I( m9 S: u) @, A, U% n时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
8 \7 K0 \3 {9 s8 d! I. `1.3
! `3 k7 H: u$ [7 c7 Q9 I* p )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
/ l" e. e  Y9 X4 e4 }4 B4 n2
)
! b& H- _! c7 |9 J& n4 i, V
稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。


适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。
! b$ i3 m. z' z8 }' P0 e% ]
2. 交换排序
2.1 冒泡排序
" y6 x& Z7 j1 F, K) k2 r图解
- v# B) }/ ]4 @

基本思想

从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。
" T4 r3 E8 \% ^# S0 q
9 D$ D6 V* I# ]& w" s代码
% a; e  c  j3 W
. p& k3 k6 Z. v7 g% m& W! t- n# C: R方法一：将最大元素交换到待排序列的最后一个位置
0 Y6 i, S! f9 ]4 z" `6 K
#include "stdio.h"
5 h7 h( W& s* l% ~: }
6 u3 H0 _# V' B  P. l, Y9 Etypedef int ElemType;
! y" j4 {8 o! G" _- i" L) z
! }* Z# m: {4 k$ h; z) L  A) q7 `void BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
( c1 k3 \! B  n+ p  n        flag= false;
9 I& I7 i+ u$ _4 i& ~" x# s" S        for (int j = 0; j < n-i-1; ++j) {
            if (a[j]>a[j+1]){
4 j% A! M9 q4 S' Z3 Z: @                int temp=a[j];
                a[j]=a[j+1];
, H( e' n1 s3 n                a[j+1]=temp;
+ s" d6 C9 N( u  l/ u                flag=true;
            }
        }
5 x0 _  p+ H& @  ?$ p4 M        if (!flag)
            return;
) ]( d" p" r9 g7 m  P  f3 c! ^, h    }
+ M8 P; }3 S! z5 a% U( B, r}


int main(){
$ H2 V8 y2 s* c  {! ?    int n;
, a) T) l& a* `6 T    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
! R9 A1 b% X1 G; F6 ^    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
5 H5 U5 M  J2 u8 Q0 ]' u: ]    }
    printf("排序后为：");
  B; R& J$ j) h: x2 [8 Y    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
" E2 P5 j- z& a+ x  _* Y+ e    }
7 W! l# Y2 ~/ f9 ~. |& M- g6 t- ^1 b}

, M; y  E( W6 i2 A1
2
1 A" Q8 x% w5 U! D" E9 q( y8 c  J3
, R/ [% b* F# z4
5
6
7
8
9
10
4 }" _; i2 e* ^2 ^11
12
13
14
$ D- Z2 f- d3 P15
1 v# T0 t7 d. R. C16
17
3 E* v- [% r+ k- |( h5 a! R18
4 x: X8 \3 q. R, ]5 n4 x) Z19
! S; C9 |! ^* {0 ]. j20
6 k' f0 T) s& ^0 N% `/ W7 `6 G21
22
4 b+ n. T: W4 b' z23
24
25
26
8 h4 o4 i& D3 V. s& g' P27
28
29
30
31
32
33
2 {$ k& j" j# l1 A7 z34
4 D2 a: V5 q1 r2 q8 E: U35
, J+ ~) e' i* I3 l9 a36
37
运行截图：
! f7 ?5 K& G' |4 D

方法二：将最小元素交换到待排序列的第一个位置
% ~/ {/ b" n4 i/ K1 m
#include "stdio.h"

4 t( b% l* ^8 p  C& Btypedef int ElemType;

void BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
        flag= false;
        for (int j = n-1; j >i; --j) {
            if (a[j-1]>a[j]){
                int temp=a[j];
8 n. N0 q2 ]% l1 h4 y3 U: k, `0 L                a[j]=a[j-1];
                a[j-1]=temp;
8 ]1 j1 f- K+ Y8 ^1 Y, w6 E- a                flag=true;
            }
: C1 |# a8 k( X$ l$ J0 P- e        }
; }. _5 t  l( ]" g        if (!flag)
& a0 ^! O) \6 u& v; Y3 {/ k- W* F            return;
    }
}
/ k2 `, s; n$ C# d* R
4 l. j# N# ^+ ~
, ^( p- d! Q) \' f/ q6 l5 O9 F5 xint main(){
    int n;
: O3 q% i  l" j6 _    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
$ w) C$ F$ b" e# g" Z) i1 e% u% J    printf("请输入%d个数：",n);
+ s- F$ h; t! p+ ]& w) T: n    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
4 ~/ d- m) I  I/ n: I8 A    }
0 {- ]2 a& P3 e, y6 g7 l9 @5 l}

1
8 w2 R3 b$ k) d5 [; ^. n% n2
3
& y5 u0 ?( C* M* @/ e/ ?, f0 x4
5
7 }3 g& Q& \0 B3 N' _6
0 s' f4 y/ p9 c9 I# O$ N7
" S  f$ ~& f% B- a8
9
10
5 l8 a( g2 ^9 e3 M( {11
  h  Y% L& k' n9 T+ d, P12
13
14
15
9 i1 Q- n- ^0 m( k! H) A" `/ d2 D16
17
7 \* z3 r- H" B' r18
; t3 ^, J6 h( @! S  i19
; f1 I# X: s( N' ~7 j  _/ U$ N; Z20
21
* V5 }2 n3 G  }22
23
24
25
' I% H, k+ |2 O! C; L/ [" W  x26
5 `# c2 d, a* M# q; O27
28
29
! U# z$ _  l+ @- H; ?30
) k; _& Q1 J4 w& C5 y7 M( s31
1 V" c- p0 q1 a/ X8 B$ F/ T32
33
& J" v! K8 ]! t5 B/ S34
35
/ Z$ c+ x3 R3 O36
# c1 c) z# m. }37
运行截图：
; z8 {# X0 x' f) z+ \) d8 e( h

性能
3 W! f+ r6 ^3 M: F
空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
2
" f# O; I( p0 \+ Z; g9 T8 p )；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
9 \* g$ b3 k4 ~3 t* Q0 A2 W6 Z )；

- ~* I+ `; P9 H7 G. {. v) Q稳定性： 稳定
8 A9 {, [/ U$ l8 N- X) C
适用性: 适用于线性表为顺序存储和链式存储。

$ @0 n: a3 c: ~; H# N# [2.2 快速排序
图解（动图以后再补）
2 v0 m( D, L4 E/ o& e' J, L第一趟的排序：
$ h0 w5 z4 `4 k- X2 W# k8 A, E, }
第二趟：

第三趟：
/ L) A; S7 |# L  P
3 o0 d% Y6 i" Z* n9 j
基本思想

快速排序的基本思想是基于分治法的:
* _& c, ^& ~$ n
在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
代码

. v1 L+ r+ z/ L1 \#include "stdio.h"

# l7 q. A9 l% C6 c1 G. atypedef int ElemType;

3 o8 |/ L5 E3 |7 z7 Pint Partition(ElemType a[],int low,int high){
: m$ ]) L; L4 S% Z    ElemType pivot=a[low];
    while(low<high){
        while (low<high&&a[high]>=pivot)--high;
9 v5 d; U8 u% j# Q+ ~1 `/ f        a[low]=a[high];
        while (low<high&&a[low]<=pivot) ++low;
        a[high]=a[low];
! l7 }' U9 l6 A! M0 @    }
    a[low]=pivot;
    return low;
% ?# k3 S- Z- ?! g8 a/ @}
. {) H3 x( J: e* E
  ^" U  a' r( N7 @  n' n, nvoid QuickSort(ElemType a[],int low,int high){
    bool flag;
7 _+ k7 _4 w# z7 Y* \3 U" Z& _    if (low<high){
( M/ u9 c0 q8 ~, }0 m4 D        int pivotpos=Partition(a,low,high);
8 O% J, m. d) Z0 n7 s  F        QuickSort(a,low,pivotpos-1);
4 j! Y' j5 x4 |5 q) d/ q1 j" M+ }        QuickSort(a,pivotpos+1,high);
3 M% k4 `' U* ?    }
' h/ ?  P- @0 s3 s8 }4 C. N}

1 _# ~1 |) R8 ?int main(){
    int n;
9 n' X- J. ~- i0 b" F    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
3 W0 r$ U- g5 W* J  x  _  I- [    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
. s+ _. ]. W* B( P- B' D    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
: ^+ `  g8 ?$ L2 p% H6 ?6 ^        printf("%d  ",a);
    }
}
7 w& k1 w8 K& m( [& d
2 T& H7 }+ I  }# [$ a, k0 n+ d; L; r
1
2
3
4
7 T1 m% t, q& B) b5
% [9 m7 H; E, L: V$ p, R6
7
; N( H+ j( U3 b5 b' h* F! m8
, m- c! K7 G: C9 Y  C; G& N9
10
$ h5 _) C) q3 K& A% r2 H# G11
9 \5 [4 i6 r) R& m+ e12
13
14
15
5 x3 I: X' ]* b) H. Y16
17
% b! @* q  k# x) Z* ]& G5 F18
( n2 ], q2 T/ d: S  Z6 ]5 F19
20
21
) p% u5 v+ p2 J" b- c$ E/ q22
5 M* Q! p, g$ X) {! ^' r23
24
25
26
" {& x0 q0 p, U+ R8 }27
( C' M( ?: `% H2 R$ @( d28
29
30
; X6 O/ w) l/ B  \4 j31
+ i9 t( `) r7 l3 Z3 s' t32
33
0 i' p3 T8 A, z3 o# F/ _34
" E4 X- D6 K2 L5 U& F! a5 y35
8 z" F# f- C8 t7 v! v7 |7 \- |* D4 Q36
5 l1 T( |* j3 c& i4 S8 s37
38
39
# {; V0 ]& t6 C7 o! U2 x) `40
41
性能

时间复杂度和空间复杂度
+ Q& v. M) _. v5 h. }# j稳定性：不稳定
! x! f/ C1 Q1 C. L2 g6 O
3. 选择排序
2 L( ~' ~' L: }2 d0 Q3.1 简单选择排序
图解
, G# `1 h' z/ `6 z' I6 d0 @3 w
& h- |0 I2 y- z7 {
基本思想

在a[0…n-1]中，将a[0]设为最小元素，设min=0
在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
7 A8 c4 ^% Q" r# ^4 W  H, z若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
在a[1…n-1]中继续进行排序。
代码
& J  _8 G+ h" I2 s+ K
#include "stdio.h"

typedef int ElemType;
, ^5 L5 f% s, y, B" N$ `0 U
7 S4 U  F; J: |0 [7 v2 _! Vvoid SelectSort(ElemType a[],int n){
+ u& ]8 R- \) L$ R5 }- ^. s    for (int i = 0; i < n-1; ++i) {
) @/ ?" L/ I# K2 T, x$ r1 b        int min=i;
        for (int j = i+1; j < n; ++j)
            if (a[j]<a[min])
1 ~$ u# x9 Z: j* n8 M                min=j;
        if (min!=i){
            int temp=a[min];
            a[min]=a;
            a=temp;
        }
8 D/ F7 K9 A( z& l& [7 c- k; Y    }
}

$ T& Z, `# B7 C& n6 r6 p* Fint main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    SelectSort(a,n);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
3 I" ?& J$ {5 k% e# f        printf("%d  ",a);
7 x  |0 X! O: ^" C    }
  N4 ?% k+ o% x$ I/ U# Z0 p; {}
: R+ ~/ u* {1 d( @0 A$ Q
1
2
3
4
5
6
7
8
8 v+ o. P' }% n* \, w! f. u9
$ O5 g3 g' x! j; I10
* R* O# [' ]( O, ?( f5 B11
* _3 f# }0 E0 h  Z0 Q' v+ C12
13
# n  M; f, v6 y& J, G* J4 s4 a14
15
16
17
3 v. s3 O5 r3 \18
19
9 G1 c5 c0 o! h3 W20
21
22
23
8 K8 \) I+ A0 J9 C3 c( r7 a24
25
26
% O8 }3 X& W% X  M1 C2 ~27
) p3 _3 ?- i& f+ _& l1 ^# I28
29
) Z: v6 @- S5 y! m30
- w( d: h$ }5 L! S$ b31
  y) v! _* E- I- G6 `32
% X0 S+ l' A- ^# g4 u" C33
性能

空间复杂度：O ( 1 ) O(1)O(1)
/ O) U8 ]0 Z0 E5 Z& T7 ]" s; V时间复杂度：O ( n 2 ) O(n^2)O(n
2
$ P% G& D; g1 J. m )
* j4 x1 o) j  R/ ]稳定性： 不稳定

4 {. R# \) D4 y! J; J8 ~, p$ }使用性：顺序表和链表都适用。
' u+ {4 S# F5 U
  ]- S. [/ C  _* y2 A3.2 堆排序
/ ]0 l; M1 z5 m3 g# I. f" f7 D看堆排序的点击这里！！！！
% X# T! Q  r$ c/ D2 [
4. 归并排序和基数排序
4.1 归并排序
) I* f$ K- Z4 r; p1 ~9 L图解
  P7 z8 d& d( B2路归并排序

4 R, S$ [  n1 n3 I% H
" U. v6 C5 R' ]! u( D& k- W基本思想
$ \' g  j, z! Q6 A0 K4 _
: s3 F9 I0 s( ]1 K, P* A# e将待排序列分成长度为1的子表，然后两两归并，形成有序子表

2 s8 `$ A& i, g& A$ a0 p然后将子表再次进行归并，直到子表的长度=待排序表的长度。
代码
% z% x; `. e  W: ^. E, D% u
& K0 D% {3 L, f1 W' D#include "stdio.h"
; V) h8 Q1 b: Y* j7 n#include "stdlib.h"

typedef int ElemType;
' K- A% x( [  M4 e
, T9 `+ e! z4 K4 `9 _1 N" ^0 zElemType *b;

+ ~# g5 J4 B& q3 f4 Ovoid Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
    for (int k = low; k <= high; ++k) {
. B9 u' M* S/ J        b[k]=a[k];
    }
* z0 x/ z9 i! ?6 {) m    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
' l* S$ ]3 H: ?, j3 D. p+ v: d        if (b<=b[j])  a[k]=b[i++];
4 i/ {7 W, N$ S" f9 B$ h% \        else a[k]=b[j++];
. _; M0 ?# i& O    }
1 d* _: ^  O7 f  [- ?    while (i<=mid) a[k++]=b[i++];
    while (j<=high) a[k++]=b[j++];
}

  ?8 i# }3 ?+ }0 R' Z& ^" nvoid MergeSort(ElemType a[],int low,int high){
1 P5 {" V' W. u$ H    if(low<high){
        int mid=(low+high)/2;
2 C9 J5 r3 K6 a7 F4 c3 i* [/ {5 p        MergeSort(a,low,mid);
% q/ w/ X& v+ t4 U$ j# |8 s        MergeSort(a,mid+1,high);
3 Q7 l( [$ z$ @2 `2 \8 F        Merge(a,low,mid,high);
1 _; b7 O, l  t. E! @( j% f    }
}

' c: W* ^6 s2 N& Y' Bint main(){
    int n;
" _7 p/ T( l* p' p# A* B    ElemType a[n];
    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
) K# {, @# Y2 A! B3 V    printf("请输入%d个数：",n);
: r& E, Y" R, W( W, N) W    for (int i = 0; i < n; ++i) {
9 m) }  o+ S* k0 _8 v1 M; l( b: o        scanf("%d",&a);
    }
    MergeSort(a,0,n-1);
1 O6 y1 `$ g$ J. t3 R2 g    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
( i+ T9 i: l- ~  n: @4 i$ B    }
7 N) \2 k" u: z. J}

+ j6 i- Q5 h+ {$ f" M
7 d% P4 C# v' f1
2
' V' h3 o6 H( U* \$ u4 l3 X$ |3
4
5
) Z( r- H# ]+ b. w$ K6
7 l4 h# I: U2 {4 l# W: U! ~7 K7
  D: F5 p3 ?5 f) E+ U. s- I$ }8
9
10
5 G3 M2 F" f" s- ~8 i) q, y+ _11
12
13
14
$ I9 z- Y7 Y" i15
16
17
& Y% t7 l" Z% D* V8 `) l18
19
20
  {* V/ H# Y' K4 P21
22
23
24
; l! @; x  a& b# Y25
26
27
28
  u( F) {2 F) _+ Q' G29
1 S$ S; K" x- c+ j3 `$ m+ ^30
4 N5 z4 A1 O+ l* l' U. C31
6 f+ e; Z% [# ~: p' l1 g' n  k32
# L: v! E4 C& ?33
34
: @* n/ R4 m& B% G35
36
37
38
39
* s' n& _. J# k/ k40
41
6 l1 N4 M% ]2 J42
43
44
9 c9 Q; R/ g  y. z* `45
46
性能
5 N; c8 g. H2 A/ d( s
空间效率：O ( n ) O(n)O(n)      创建了一个数组b
时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
​
n)  k指k路归并排序。
稳定性：稳定

/ d; s" K% w& Q/ B5 w5 M4.2 基数排序
图解

' L0 ~7 P" R' t# {9 T8 F+ [
基本思想

0 Z9 N3 Q6 N4 H% T2 \( p将各个位数（个位、十位、百位…）进行对比。
8 `. @! [2 J" y* F' U# m为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
/ n" Z, R# F" G2 F$ b0 d7 H
' R6 m; M% t. N( v2 I3 {性能

空间复杂度

时间复杂度


稳定性：稳定
1 C1 _6 F& P  C8 x" S
5. 内部排序算法比较及应用
5.1 整体比较
- [; ]0 k, v/ r! J" }( k2 {% O
8 c  ^- m& B; U, A  b
5.2 时间、空间和稳定性
8 O9 p; R  W, d. B- j0 D9 f! V
( l, v1 A5 g! N( a, X9 y- n
* j% {" v/ y' a. N' B参考资料
《王道：23数据结构考研复习资料》
————————————————
( S# U, l( [+ X* z: J% C% B2 {版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678

7 k, m. i; D/ Z8 u1 e  X4 o