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

杨利霞

数据结构：九种内部排序（动图+完整代码）
$ d& H% W) D+ Z# m" s
- a, [2 ?# O% C% e+ f排序
1. 插入排序
1.1 直接插入排序
1.2 折半插入排序
- }/ G- t5 `" z( U1.3 希尔排序
2. 交换排序
, z( Z9 Y: U0 I- b2.1 冒泡排序
2.2 快速排序
3. 选择排序
3.1 简单选择排序
3.2 堆排序
4. 归并排序和基数排序
. z/ ^/ @& M! I. G9 d+ O4 ^0 k4.1 归并排序
( A5 L  E4 a% C; w2 A# _4.2 基数排序
0 h- u  E, c, q( m! ?5. 内部排序算法比较及应用
5.1 整体比较
6 H/ w" ?8 P0 {& O6 `  T* J' n5.2 时间、空间和稳定性
! t- g6 h6 q5 G8 l& m9 ?参考资料

; u1 I/ h: a+ H% D& R/ M) u- W内部排序：是指在排序期间 元素全部放在内存中的排序。
6 G- Y) j0 U0 x+ x8 r内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
1. 插入排序
1.1 直接插入排序
图解

; m* W8 N* ]- Y" u2 G
* M5 C# ^! L. N基本思想

2 P' u2 m  q/ s) z1. 查找a元素在第1 ~ i-1中的位置k
6 X9 c" M& m+ d+ m3 r% j2. 将k ~ i-1位置上的所有元素向后移动一个位置
( U6 z8 D, v  F3. 将a复制到a[k]


9 h4 u9 k6 P" W1 t2 x
代码
/ n! O! v0 V% U1 d8 D0 p2 B
$ ]# o+ y7 R2 j. g- G/ B. i方法一：

数组的下标从0开始，如上图。
6 @7 s' {( ^6 X4 I* k* ~
#include "stdio.h"

typedef int ElemType;

void Insert(ElemType a[],int n){
5 Q0 _* {* c& F. \% B5 w/ a    ElemType temp;
    int j;
2 T" \3 F! Z) X8 T) G    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
        if (a<a[i-1]){
9 W8 l4 O0 g8 k' M            temp=a;                                                               
3 C8 Z; r: u. y) p" R3 C% c2 r            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
( H6 x  Z- M% o' u6 k                a[j+1]=a[j];
            a[j+1]=temp;                                                       
* R& J9 T" b" |, n0 x        }
    }
}
$ e: e) q5 j# T+ U
int main(){
& M! f6 i9 `8 M* O    int n;
    ElemType a[n];
, I4 R: [, D$ b2 b6 w  ?    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
' \% h, D3 _% {, z. ~; Q* Q    printf("请输入%d个数：",n);
3 t2 W& ]4 l4 R* n' b    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
# _0 l0 w8 [! t7 z: _6 Q    Insert(a,n);
    printf("排序后为：");
$ ]( I4 t6 o2 S1 c+ i( {2 n    for (int i = 0; i < n; ++i) {
% _: g- D. }& T" k. A; R% ?9 y        printf("%d\t",a);
( m  Z) |( `: `3 t    }
}

1
. e- m) G1 E4 @; V2
7 S7 i* `) \* S) N, W2 ^3
4
5
6
7 W( x9 o- n# S; g7 M, u7
8
9
10
8 j5 w7 A1 j# M. O. ~$ o( T2 C9 v11
4 a" h& F3 q/ u1 f12
3 Z1 I9 U) t- n0 w1 v5 t13
+ ]& b, T, M# [" o  S14
$ ~& v) U( `% o7 ~6 h15
16
7 C, A& s! u+ a6 F  p% s9 q; F17
18
# P9 m; M# E) o" O19
# a# k8 E& a5 P1 n20
1 d7 ?3 `  t& W9 K7 a  O21
22
& r$ v. q7 ?8 q( a) _, R$ Y23
. ?3 q( S- p8 n% Y" K) X& O24
25
26
" E1 W. e. [7 c+ x  b6 V27
" j' X/ J! F! }28
29
" l( y  ~8 r3 ~5 a6 H2 F30
! P# k( e, z0 E; Q* Q& J31
32
5 L1 a3 s4 B. `方法二：
- C+ A* k6 T3 j


#include "stdio.h"
- A7 n& ], Q1 a8 ?! |5 Z& v
* V3 L7 s8 g+ T4 x1 v) |; Wtypedef int ElemType;

, ]. T6 r7 L* G1 U: k8 mvoid InsertSort(ElemType a[],int n){      
( f  Z9 f; ~, C2 W0 M  E    int i,j;
    for (i = 2; i <=n; i++) {
        if (a<a[i-1]){
/ {1 G9 ?7 b. f0 U            a[0]=a;
            for (j = i-1; a[0]<a[j]; --j)
                a[j+1]=a[j];
            a[j+1]=a[0];
        }
    }
}
int main(){
    int n;
; S. g* z7 a( O& G/ a5 ?9 C7 A; h    ElemType a[n];
7 [! u" T, p5 C1 [    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
/ o, t# i1 k* Y( G    for (int i = 1; i <= n; ++i) {
4 y2 k% o0 q3 x        scanf("%d",&a);
, x$ @. z  W4 B5 O& O9 i% o    }
# o3 S: R' L' F7 A& R7 D    InsertSort(a,n);
5 b' K. a. |) l; n5 P    printf("排序后为：");
2 b4 d$ d: |1 a% ?    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
}
5 v8 [& q- ]* v- n) w" f) q
9 ^( Z. v$ |9 R1 y5 n1
2
3
1 v  J2 z* l2 ?6 _/ H6 I4
3 {9 t; y. ]/ g& V; y5
6
7
8
9
3 p' S7 I) j  B: `* k5 ?10
11
' q' g' I6 l  [2 p& y0 B, x12
13
8 s6 ?: Y" z1 m6 Y7 F( O+ G3 j0 S  X' N14
8 N( {5 C* {$ X15
5 u% R4 y$ ?! f. }, R( C9 a* W16
17
18
. ?9 O; w" ]7 K) D3 I4 _19
20
21
22
' H- b. y5 n$ Y# h, @. F23
24
2 e  j1 F% I% ~& @9 m4 z. i25
26
27
/ A1 ?' r6 V% T0 U! x' t28
: @* y- g& V% h' ~) l9 i2 }4 c" ~29
30
. P- H! o, \! d* A( c6 j算法性能

" X" X5 U$ ]% K9 e4 f" G空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)
$ U; n! q9 m, A* T+ o& Q1 k
时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
1 W5 V$ n, K, X1 ~% A( \ )
0 W1 _% G7 p& L! Z

" U/ F4 G, H0 t- B+ K稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。
2 n$ P( [! p5 U9 d, I. k: t' Y5 t
1.2 折半插入排序
图解
第一趟：

第二趟：
* s, k( ?& p4 J# U
3 b6 a3 x0 P; q) u
第三趟：

& |  @4 n# d0 g7 D0 G第四趟：略
( `% P; ], v' o  {% b+ \" y第五趟：略
& L- E, g' V- W+ a$ W
基本思想
4 [. y3 x+ W. G8 O
与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
1 o7 ~# V! |8 i. E  h: M& Q找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
代码
( W7 B5 B" I7 j: J; e/ C4 P
2 o4 T) E. o- z0 y#include "stdio.h"
  O. F9 y; l- j
# w4 d9 U1 i9 G4 b. {- x) F9 Ytypedef int ElemType;

, ~  F# z: _( m* w9 Zvoid InsertSort(ElemType a[],int n){
    int low,hight,mid;
5 ^( n. ?1 q5 N0 M. y0 n2 B    for (int i = 2; i <= n; ++i) {
        a[0]=a;
8 H7 T5 a8 _4 g3 p4 v        low=1;hight=i-1;
        while (low<=hight){
1 o4 N  X& U* d; F            mid=(low+hight)/2;
9 X, k& c# G* n            if (a[mid]>a[0])hight=mid-1;
. z3 S7 |$ y2 @2 K' p$ j* M; W            else low=mid+1;
        }
% Q) d) m' K' m6 p5 D) W9 `5 w4 a        for (int j = i-1; j >= hight+1 ; --j)
            a[j+1]=a[j];
        a[hight+1]=a[0];
    }
}
% ^8 L; x* k5 F0 J3 p

: i4 p6 u# M. \& a. \# _int main(){
    int n;
  l, x" A( O5 \6 h4 r. z    ElemType a[n];
/ h; Y# j3 a' _' k- Y" h/ O4 I    printf("一共有多少个数需要排序：");
' @) l  l+ T4 l3 d    scanf("%d",&n);
' ~& a( w. P: `' L! o: `    printf("请输入%d个数：",n);
0 e: X# ^- o; T  X4 R    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
  {- j) a9 |: u( z* d6 {# L: [    }
    printf("排序后为：");
    InsertSort(a,n);

8 \* B" N, K1 q5 H8 F* o    for (int i = 1; i <= n; ++i) {
3 C! y/ k* \+ H! @/ p        printf("%d\t",a);
; b% e$ I6 b+ `* [9 H    }
}

1
2
3
4
5
: S3 B$ T1 V1 X8 K6
- B/ C& z1 N) @7 i; l7
8 E" f: z! v8 w0 G8
# A4 I& `' K' A) d0 o. m1 d9
10
11
12
13
/ N9 C* t* s- [' N) A% @14
' F; t. ^$ [4 \( P# h- X15
16
: ]  \' R; N6 y* x+ _- h" [) v17
$ }' y! H9 J# E" |18
$ }% [( F( b3 a: O2 Q19
20
21
22
23
2 P% f% e5 M) W4 p24
25
  `) P8 R0 g9 C26
27
2 n. {' s: E! N! L' x28
29
30
31
0 N: n! H& v- d' j& u2 O0 Y  y32
33
9 ?, p6 i! X  y- z* x: i34
& [2 f% }! E' `: v" U. }8 i35
36
% e) g. T& G! ]37
性能
6 ]" i! n6 W) N' |
空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
2
; v% o" G* W/ t+ C: `, }7 B )
稳定性：稳定
) d- _3 Z  ]' s" D适用性：仅适用于顺序表
3 _4 |6 n0 n' @& t- y" }8 L
7 d( K0 P# L- x4 r* _  u1.3 希尔排序
图解(动图)


基本思想

先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

7 R$ [: J+ I3 \) l" k代码
& c/ l& ~3 X" j
#include "stdio.h"

8 d2 S( ^. f* d; ^5 otypedef int ElemType;

: a; X$ R: H4 e1 Z1 zvoid ShellSort(ElemType a[],int n){
    int j;
    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
) F. E# M) r) s  e& G        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
            if (a<a[i-dk]){
                a[0]=a;
                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
                    a[j+dk]=a[j];
1 K/ L) n4 C: M! U+ ^                a[j+dk]=a[0];
5 m$ ?2 w$ s& X$ L            }
, a" X7 p2 U3 ^2 ^        }
    }
}

2 C. `( s9 O& O: m. N) b0 m" t# `3 Gint main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
% p# I7 i# x  C: N    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
! B% a5 ~' ^0 Z7 R        scanf("%d",&a);
    }
    printf("排序后为：");
    ShellSort(a,n);
; j1 k( M4 y$ N* _9 u2 c& X% ^  v+ ~' J
    for (int i = 1; i <= n; ++i) {
3 n/ l1 U- g6 m) O' `; R        printf("%d\t",a);
# M1 L3 _% B1 \2 G3 t* A3 F    }
}
1 r: @' s% v) q& |
1
2
3
4
% R6 t+ W' l* ?( M9 O& _5
6
, g1 m1 U) T1 a4 A# W" ]& K7
( f9 l* w3 ?# k% [, ^8
9
10
6 V" M$ W/ u$ \8 K6 a, m11
12
; l' W# ]# t6 y. T! a& @13
8 m$ s1 _! W3 f14
15
8 M% X7 O$ d! s1 V16
17
( Z  E& R+ y9 j1 ]0 I8 z; m% ]2 R18
' d) k; P, x9 w19
20
' x( L% K0 E3 X; |* S- x21
22
23
6 W  u  o& S& T  _24
- \; W, l, l3 ~25
26
27
28
29
30
' B( B' t7 U: L- p' j* C31
32
2 u/ S# x2 T& }9 w" s2 q33
34
" I- N- K! N. _5 y" r, Z性能

空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
5 F$ z8 R! i( w
时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
1.3
, k6 T- _" X" X- E )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
2 R+ ~- n& W5 i; N" j) s2
)

稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。


适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。
( b. H9 h$ a7 a. n1 M
0 U% _# }% W+ f# |, B5 J6 }( v( S2. 交换排序
: y0 d2 g0 b, Z2.1 冒泡排序
图解

7 ]2 O6 f/ H# c0 l% N, \: ~& h
基本思想

从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。
3 ?6 j# P9 ]' {
6 P0 h2 u( b3 w. m- f代码
* L  W8 c: X* k0 V1 Z. W
方法一：将最大元素交换到待排序列的最后一个位置
7 V0 h' m* w" w5 K- m
/ I0 R8 @: J. t: B6 R0 K9 Y#include "stdio.h"

# t" r* t) N8 b+ O& ltypedef int ElemType;

void BubbleSort(ElemType a[],int n){
    bool flag;
9 e# f) D( m5 o# B2 _- ^    for (int i = 0; i < n-1; ++i) {
, t7 S* K6 G* ]0 ~% a% U        flag= false;
        for (int j = 0; j < n-i-1; ++j) {
" A' |/ s( g; b1 i- U3 }$ q- ]) k            if (a[j]>a[j+1]){
& `5 Z2 ?) }6 {1 E' y                int temp=a[j];
                a[j]=a[j+1];
4 z* T: D  `' r( V                a[j+1]=temp;
' u  _5 ~  ^+ N' }/ p% Q                flag=true;
            }
# Q1 j) l# ~" J  I3 }        }
  x; l& C$ w" T0 x7 [        if (!flag)
# a/ w! L. V2 e+ a% |) k% v( g# T' }            return;
    }
}

2 m# d; E1 K8 b& ?/ b
int main(){
# x( m- O4 K) T" I+ U4 \    int n;
7 r7 x( O. z5 {9 T4 a    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
# W7 n! }6 i/ {0 s% m9 v    printf("排序后为：");
1 u. p  T1 v' {; Y: _    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
: z( q$ }6 p. b: R. `6 u}
2 D1 O! L0 P' j  O
* x9 ?6 w0 T' ?2 f1
2
3
+ _. u6 O& ]; }" j- x4
5
6
7
8
9
10
* {* m+ I8 E: P11
12
13
14
15
6 f9 _7 Z$ E9 N9 T$ ?( J16
17
/ ~1 t( I$ F0 h" f. L18
19
+ x% k8 e5 ~$ e$ v) j+ D20
* O3 L1 W/ t/ ~21
, d" O  h- e' d8 z. C1 M22
23
24
25
1 J' Q% l: P* }/ z" t26
27
28
2 D& P/ M. S8 B29
5 Y# t7 c" @: x2 D  ^8 g% t4 F- i5 h- {30
: u2 {: t- Q) v) t* ?  L: |31
32
1 o$ q& X9 a8 B33
34
4 s1 n* E7 B4 S1 T: b* ]; k35
36
37
运行截图：
% L9 H5 Z! M. _2 t6 M

9 F9 `& l7 L9 o6 r" }) j方法二：将最小元素交换到待排序列的第一个位置

#include "stdio.h"
" C. \; b% {% W# T0 E
0 \" n4 F" h# w1 btypedef int ElemType;

; n! U& G5 C6 I1 N; ~9 q, tvoid BubbleSort(ElemType a[],int n){
) e# T" Y: B7 ]" L1 @7 w; n# d    bool flag;
, T; W; y! U* h5 ], u1 Y    for (int i = 0; i < n-1; ++i) {
: S3 h* r$ T7 s        flag= false;
' b0 R$ }6 @8 M6 ~5 {1 ~        for (int j = n-1; j >i; --j) {
: h% o2 D1 o* ^            if (a[j-1]>a[j]){
                int temp=a[j];
0 H$ U" Y/ ^; K0 @                a[j]=a[j-1];
' W0 ]/ }$ \' ~, A                a[j-1]=temp;
                flag=true;
0 l2 s: I+ F+ u            }
        }
        if (!flag)
* x+ A6 M& u' a+ [' d            return;
: W$ c0 O! ^0 B+ H4 u* m    }
}


int main(){
    int n;
    ElemType a[n];
9 T/ h4 ~  n/ m5 Q9 v  A5 m: i    printf("一共有多少个数需要排序：");
2 `% S: I" ?# g5 ~  p    scanf("%d",&n);
    printf("请输入%d个数：",n);
  L% F2 U4 c# Q2 u4 a/ j& q# |    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
5 n' X% a7 Z$ l6 O1 @6 ?5 i8 w    printf("排序后为：");
( x4 Y% m! \( T7 P* P8 @. p    BubbleSort(a,n);
5 [4 r6 t4 {9 t" }7 {    for (int i = 0; i < n; ++i) {
( s( m4 ?# I& G        printf("%d\t",a);
    }
& B0 g; v) F/ E8 U" Z0 |! N2 h. D}

+ I7 I3 N/ g% O. }$ m# g8 t+ o1
2
3
4
, V8 i0 |. d8 {/ |1 ^5
6
) v* v% Q8 }3 \. ^7
$ W/ |* o& X9 Y/ V2 [/ O1 K8
% A3 i0 N4 q7 X' [9 J7 D9
& I& f) P" E  J7 W. Y8 P" v10
11
12
13
  i" N  O, F* K0 \: s" \+ h14
  d7 E, j/ P& p15
, f+ w0 @: O& B, j9 p16
17
5 c2 k* i  K9 \% E  x18
  l3 B9 j# J1 g& U19
$ g! i& o- ~3 v% V+ H0 h20
  A& P/ M8 V+ ]( w21
  C3 u0 m5 p2 x* I3 h5 G22
23
24
25
+ R8 |6 j5 \4 J2 l26
27
28
& A+ w0 t9 U7 o+ |! G3 h29
30
31
" `: B2 f4 m9 _5 O' W2 W32
33
. w" \- n2 H( l34
35
: N. R8 L, F) `# w36
( y) D& O6 Y9 o4 n) _37
运行截图：
7 `1 m, ], E; i8 i! E

性能

空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

2 L: \; N& ]) [! a( z* a时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
9 v3 Z: q7 m& ]2 |* L! g/ B2 z2
)；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2 W) e. P$ _& j- k3 ~2
)；

( j% n1 L6 S8 p稳定性： 稳定
- c, a$ U4 ?( |) f3 q; n0 l
适用性: 适用于线性表为顺序存储和链式存储。
4 l- V  n0 T: N) S5 h
2.2 快速排序
: |7 O0 H  w! |3 g$ F& j图解（动图以后再补）
第一趟的排序：
8 G0 D/ p! u& l3 v
第二趟：

; f7 |6 }0 z1 E$ f第三趟：


基本思想
# b) R1 j- r7 g$ u" @
快速排序的基本思想是基于分治法的:
; y! Y8 Q  a! U$ y& _
- K! ~" o6 C* T" ^1 U( J在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
) j. e2 ?# |% v7 _通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
* V% `+ K+ J$ W3 p- W代码

% a+ D5 A6 N( ], S) e% c#include "stdio.h"
) g. w- T! u  a
typedef int ElemType;

int Partition(ElemType a[],int low,int high){
    ElemType pivot=a[low];
    while(low<high){
9 }7 s' N* i0 C1 R- j; Q( c; N        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
& Z, K( u3 U( e; d, l" l        while (low<high&&a[low]<=pivot) ++low;
        a[high]=a[low];
    }
$ K+ {% Q8 J* y3 `& ~    a[low]=pivot;
    return low;
) t1 _4 v7 M6 t9 J}

void QuickSort(ElemType a[],int low,int high){
2 X/ U. f# a' P* U    bool flag;
    if (low<high){
$ l% D/ j, r5 V, f        int pivotpos=Partition(a,low,high);
4 n! J  R7 R& A9 C( p% f        QuickSort(a,low,pivotpos-1);
1 a. `1 p. G9 |: F        QuickSort(a,pivotpos+1,high);
( W: Q9 P. h* h1 R# r    }
: }; M# X, c+ `}
& T7 v& s/ H6 S' |: j/ u
, K. }/ R1 p- `4 r! \9 Dint main(){
4 {! C% Z  K1 N6 W9 p. r    int n;
1 [8 v! T" w5 f2 a  R    ElemType a[n];
    printf("一共有多少个数需要排序：");
; \* R; o# k) v9 K* v    scanf("%d",&n);
  F: s( e8 j& x/ @6 x    printf("请输入%d个数：",n);
6 l+ U" Z* Z% A( Q+ E5 o    for (int i = 0; i < n; ++i) {
& N* B" q  \! m; ~4 X        scanf("%d",&a);
    }
0 j4 Z# E" j, `* a! P5 u6 Y0 a    printf("排序后为：");
4 A9 f1 g9 J% T; E7 N+ l/ \/ R; j    QuickSort(a,0,n-1);
0 K2 k* K& z0 n0 P  {    for (int i = 0; i < n; ++i) {
& |" i/ R1 k& K/ k( H5 W5 v        printf("%d  ",a);
) h& W6 L' X" f" g' v; i# a    }
0 N- ?( B5 k5 H& j0 s! h4 k}


1
2
3
: |: U( O- \! Y4
5
. @0 e8 F! I* O0 ?2 R  b' w( D6
  M% ?+ X1 t) l3 s7
8
9
10
/ Z) B4 }! s1 P7 X. G3 w+ {11
; @. d2 z, ~2 C! j6 o5 F5 T12
13
# |9 g. H6 ~- ^2 f14
15
16
# @" t6 [+ a! j17
- @' p* |' q" t18
9 y* y5 X0 l1 v: x19
) d# k+ C- @! F3 o$ o( d20
6 A7 t9 z& `& J2 F5 Q4 J' _2 i21
22
, K/ Z: R% k4 W* `23
) n7 W2 T7 W0 x& n2 Q24
$ ]# m( L1 t5 R  x* t25
) ~- {; J6 A2 ]9 m4 j4 _26
27
28
" b* Q( o% d/ z6 V29
* V4 o! u# K/ x: ~: [+ o30
0 L" g8 _6 }7 d  G% _1 n31
32
# M( h- K% x  @0 t" Z( ]4 j33
34
35
36
37
5 m. `$ p0 f! \38
7 t& J! E3 ^0 A) _2 G0 K5 [/ U5 p/ [39
& F: _- C1 C$ |, P7 l$ b% E40
41
性能

时间复杂度和空间复杂度
稳定性：不稳定
+ ]6 k3 n$ }" m+ U/ N
0 \' w. j1 Y0 X7 u7 K3. 选择排序
3.1 简单选择排序
2 O* g' a8 E* E- k& C图解


4 y) s0 N" h! l& {' R基本思想
2 H0 x3 H: R/ v
在a[0…n-1]中，将a[0]设为最小元素，设min=0
- u0 S) u2 @4 Q6 V7 d# S/ v& Z% y在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
在a[1…n-1]中继续进行排序。
代码

#include "stdio.h"
& \4 W: N$ o, W5 g  o7 A
+ }5 y- p/ C1 A# z% c. j" n! e0 mtypedef int ElemType;
& J% C( c; v! W3 B! `/ I
void SelectSort(ElemType a[],int n){
3 J" `1 y" A7 k2 B; g    for (int i = 0; i < n-1; ++i) {
3 G6 Z* R( s/ N  R        int min=i;
; r3 }. Z7 W% p( K! R0 `        for (int j = i+1; j < n; ++j)
* M. M' n; f8 o" k( E  J  x            if (a[j]<a[min])
                min=j;
        if (min!=i){
2 D* q8 o' x- j! Z            int temp=a[min];
            a[min]=a;
# s4 v0 r" q/ w( ?: b            a=temp;
7 v* h" X0 ^- o1 c& P" q! p* S        }
3 n* q' J- p5 R. T) K7 B3 {    }
: y# q2 S- z8 S# F7 W" @$ O}

7 M6 h7 S$ }1 Y5 Fint main(){
    int n;
    ElemType a[n];
9 f+ s* l' K; H. q- g" a    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
4 l# C% R; R2 y2 l( D    printf("请输入%d个数：",n);
8 J/ S0 e9 ?+ s$ ]+ z0 F    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
- @3 L! L: x/ ^6 \/ B    }
    SelectSort(a,n);
    printf("排序后为：");
  R4 n; G4 ^& E4 F6 b. g7 a, B# w    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
; U7 Q7 J2 I' _: c    }
}

+ F& t2 {) b0 B) t: H1
2
3
4
$ M) A& J( }( [" z: U5 T* i5
6
7
& B- B1 p9 d  U# P( n8
+ c" g4 D/ m1 E4 H" ]( R% O( S5 c, O9
7 {+ b6 W8 [4 m& Q  Q10
' V. `' P  K3 [, N( E* u11
" o3 x, t# Z! N12
13
14
15
  @) L3 i& U& l  I: t. k7 x* H3 c16
17
18
# p; F$ g+ f0 Q) z! n( \19
20
21
22
23
( p3 ^) t; {; R/ [24
25
, B' F1 y  l5 @  f26
7 X) }# @- h/ S27
28
29
30
31
32
33
性能

( M. ?: ?5 s6 d' X. ^5 l2 d空间复杂度：O ( 1 ) O(1)O(1)
, x8 P2 y& Y; g& c0 r时间复杂度：O ( n 2 ) O(n^2)O(n
9 V, g+ X, R7 z5 t* a0 d2
7 Z7 k& C2 G& M$ M$ t- J) a, C) s )
稳定性： 不稳定
1 z+ Y; X3 o  i
0 p6 P( M  w# b9 w使用性：顺序表和链表都适用。
% k( W4 D' B# q* Y* e% n5 B! p
& b% s/ h$ {5 F- w3.2 堆排序
1 u" M, F& x# G3 V( o看堆排序的点击这里！！！！

! r) R' w, ^# _- q4. 归并排序和基数排序
0 l8 N! l0 D7 G& k4.1 归并排序
$ `/ [/ o6 h3 r图解
( M( C6 `# c( I, _2路归并排序
4 Y3 w  \9 h; {  @2 M0 \) |

* s2 T  I5 H- K$ j6 k* W# [基本思想
4 [& K% x' y) h$ Y
; x  |8 m) f9 v% H0 g将待排序列分成长度为1的子表，然后两两归并，形成有序子表

然后将子表再次进行归并，直到子表的长度=待排序表的长度。
& M3 L9 C2 m% q' m# d& ~# L代码
, a! n$ Y  H* B$ v7 U9 y# j
#include "stdio.h"
#include "stdlib.h"

typedef int ElemType;

ElemType *b;

! @/ U) `0 S6 C. i/ J* d7 Nvoid Merge(ElemType a[],int low,int mid,int high){
' Q, X7 V3 z) n; t: s6 R5 |% Y  n/ A# V    int i,j,k;
    for (int k = low; k <= high; ++k) {
7 x% n+ t) t- f( j. ]9 d( R        b[k]=a[k];
* X0 h2 d2 Z' c; n    }
: b  A; y. t1 @2 ^. y    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
        if (b<=b[j])  a[k]=b[i++];
1 h, _- @* v2 `/ j2 H4 t4 |+ Y        else a[k]=b[j++];
0 g+ ~2 R* I9 j7 V' X$ I' F    }
    while (i<=mid) a[k++]=b[i++];
% Z+ x* X4 }" e  D1 l- ^1 w    while (j<=high) a[k++]=b[j++];
7 \/ J0 e) K% z. M# i}
, f) ?' O3 d: d+ W; M1 J0 K8 K( R
! {& l; t/ i% A3 J! N6 }/ U6 X. Cvoid MergeSort(ElemType a[],int low,int high){
; |( B7 i/ {- e' j( t' L    if(low<high){
6 t# ]( E7 h5 N. e& h+ I        int mid=(low+high)/2;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
$ E) {( e8 m, W" `3 k# O: i1 b        Merge(a,low,mid,high);
8 s$ k+ A1 u+ M1 V; Z, s4 t3 p    }
8 q9 E6 A2 L/ A+ p1 |1 Q' J7 [  k}
& [  B( c* c* f/ S; S
int main(){
' h3 m# W3 h) _* Y    int n;
7 J& m3 {/ u( s) \$ Q- D7 f    ElemType a[n];
, V  B) v* A9 D    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
. n2 K* C. f$ m& P4 K- M- `    printf("一共有多少个数需要排序：");
" o" r8 {2 n/ p, y! J, j8 @/ |3 f2 P    scanf("%d",&n);
    printf("请输入%d个数：",n);
1 o( A  P7 t7 t  s% ^- G0 ]6 L1 X    for (int i = 0; i < n; ++i) {
2 {2 T# e* L* U, U        scanf("%d",&a);
    }
    MergeSort(a,0,n-1);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
& ?8 Z# F4 E2 a. m: M! F" p        printf("%d  ",a);
( y7 L$ A6 u: F9 E7 m    }
0 K) t1 ]' R, P, A% t: E2 u}


1
7 Z5 z; H# z( c" d2
3
4
# K) ~$ n& q9 M# c2 r, p5
6
) F, ?2 T0 q4 R' ]- O7
8
9
10
+ H7 ]' C& a5 q9 Z6 t11
  ?1 F0 V- n" F  I12
2 V' s; l+ b" b8 x2 ^7 a13
- A: L$ H. [4 N8 m14
15
% F5 c- e! l3 V) S4 S7 y16
17
18
19
20
: S6 k0 X2 O# L6 \+ _7 a6 L) \21
# q9 K6 s6 {5 @22
9 s, X9 \! Y3 g23
24
3 B# o) f! V9 M* v  M4 O25
8 S' V3 N8 M6 C7 A6 Q26
27
' F1 c1 Z' R2 |8 g. E28
29
3 P: {1 l1 _. s+ N5 `4 U30
31
32
+ i; e1 K0 \6 }33
$ @' n& N% {+ [% {5 n0 L" P34
35
$ F+ S& k7 |* a" |5 q* G36
37
38
/ w+ Y0 [' K$ Y1 x& n# x39
5 v2 d9 l; ^. S3 p, p% N1 t8 g40
2 C  R4 a4 z. V- f5 X41
* y# s( q9 q3 y! T- f/ S6 c0 s42
, U0 R! u; D; k% B43
44
45
46
性能

0 ~. P) ~$ I: n: R空间效率：O ( n ) O(n)O(n)      创建了一个数组b
; d( i/ D1 U0 C  v8 |& [3 }时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
​
9 p% ]: ?2 S  h* x) ]9 ~0 [, ?8 l$ l+ b n)  k指k路归并排序。
稳定性：稳定
2 F) w" X1 _+ Z6 g+ g
! T8 F! T6 t6 ^1 H0 A  q; K7 p4.2 基数排序
; S- Z& N* }" S* _" {图解

2 Q! p$ s4 p) ^& n
: N* Q! B* Q8 A  K$ D# ^2 }* m基本思想

4 X9 Q( a8 c0 R4 w" E- U% n将各个位数（个位、十位、百位…）进行对比。
为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
4 N3 S; u8 R" A! a! U, z, h1 F
性能
: V9 _8 e& F# V7 v4 F
空间复杂度

4 t/ W5 c: u, E  ?' b) T5 V时间复杂度
' u9 A1 H/ K1 X8 y

% }4 A& k2 ~7 P& O& I稳定性：稳定
: E; a7 X" u8 L: O
5. 内部排序算法比较及应用
5.1 整体比较
  l* _5 X3 x' H7 O! G& U' z
! T) c/ c. t- ?: ^
1 E* K" I6 f6 M/ J5.2 时间、空间和稳定性


+ X. w* q" h! M: x) U$ u' Y- F参考资料
《王道：23数据结构考研复习资料》
3 n% A# \0 o+ y7 v3 `————————————————
; q5 f& J1 _, n9 R* A$ y" w版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
1 u; p, N+ u' c# P( {& D; T原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678

8 }( j" b3 y. ]
2 n% @1 k7 @3 n, _9 O9 P