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

杨利霞

数据结构：九种内部排序（动图+完整代码）
1 |; u8 H0 i# S, ^. {+ I- e
排序
3 ]0 f4 L( O  Y4 O4 M1 |! [8 I1. 插入排序
1.1 直接插入排序
1.2 折半插入排序
+ ?% ~& Y' W4 ~  T3 }( b" X( M6 S1.3 希尔排序
2. 交换排序
2.1 冒泡排序
! ]0 k! z) p5 m% o1 @8 M2.2 快速排序
# G0 x5 X  b8 m% j( w7 U+ ?9 H1 S3. 选择排序
3.1 简单选择排序
; Y# x, a; i$ C3 s2 J3.2 堆排序
- d' H  Q( m8 e2 s7 M7 W4. 归并排序和基数排序
4.1 归并排序
4.2 基数排序
5 D1 {3 ]: p/ u# E( f6 B( N5. 内部排序算法比较及应用
8 {6 a" J# N1 t$ s* W5.1 整体比较
5.2 时间、空间和稳定性
/ j% l" C6 N5 g- j4 a! V参考资料

内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
- e' O6 j0 \& ~& J0 c1 |% L1. 插入排序
1.1 直接插入排序
图解
& K# U  o% m9 i- t0 D& Q
, Z7 u3 c" p; j( \  z3 W
基本思想
7 ~* _  c( M5 ~! s5 o
1. 查找a元素在第1 ~ i-1中的位置k
' p. O; s3 ]; ^+ E2. 将k ~ i-1位置上的所有元素向后移动一个位置
3. 将a复制到a[k]
$ s2 V/ ~7 I6 j$ L2 V9 V

* Q9 E% q# [" i& T3 \2 r+ V/ w
, P5 \1 H0 t2 f  ^2 S8 U1 s! s+ Q! F代码
& ~4 C5 ]- W- M0 Z7 f. l
6 y6 W( s3 \, L( u, k/ p. H' n方法一：

) M8 j5 Y9 Y+ I9 q  J1 V# |数组的下标从0开始，如上图。
/ M) V/ y! L+ y7 `
#include "stdio.h"
2 u3 ~  [+ |$ w5 N
1 a. l) o% ?: i7 Ptypedef int ElemType;

void Insert(ElemType a[],int n){
. l9 z. v2 \2 [8 G0 `    ElemType temp;
* h9 E8 ^  p4 T5 `; r    int j;
0 f% i$ c, y4 R    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
4 S6 U6 D  ~4 P# V* N8 u; Z        if (a<a[i-1]){
( j+ E' J. _5 ]& J. l- R            temp=a;                                                               
8 Y2 P0 J2 V+ |1 J! B            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
: [, u3 `# Y0 q- V% `                a[j+1]=a[j];
; i0 t1 |5 o& Z' H            a[j+1]=temp;                                                       
& g) p) K* x7 Z! A0 Y: `        }
8 o8 b/ S7 w& @8 G6 v* q    }
}
8 }; i- M8 m, y. g" |% x3 r
int main(){
, V, A" U1 v* h    int n;
- e; D, Z% B( B8 p    ElemType a[n];
    printf("一共有多少个数需要排序：");
7 b4 ~0 W5 {: |7 O" A& Z    scanf("%d",&n);
    printf("请输入%d个数：",n);
9 K' a: {8 X" b! I6 K  }    for (int i = 0; i < n; ++i) {
  E; g, |( w( N0 U( L$ _        scanf("%d",&a);
    }
# q! E% V' b3 a  O1 X; Y9 O. o& V2 t) k    Insert(a,n);
    printf("排序后为：");
1 h0 g" F8 M6 B% @0 c$ ~8 A    for (int i = 0; i < n; ++i) {
/ e" G2 B6 Q& b6 n) I9 p% l        printf("%d\t",a);
1 g2 ]8 V9 n2 ~! A5 d; l    }
1 ~5 f  v" ]; c- J}
0 R/ k0 j' @3 [9 Q5 {3 \1 b
1
) \; C: ?$ H* z$ m' _2
3
4
5
( a$ H  r3 T5 [1 W) p) T6
7
8
9
10
11
12
13
8 m& |) @4 v8 |% b9 H14
6 h& j  `6 s2 _3 c15
- @7 C: g+ \2 q  ]4 B16
17
18
19
. y9 V2 u; I6 d20
21
: X  B' G* T* V. `22
23
3 J1 |2 J3 `8 x5 d# W24
25
. M1 W, I+ V) k: G; ]+ k( t26
& y) }" M9 I  O4 a27
28
" A& E( `; E: |, ?$ Y1 I2 d29
3 }" S+ J6 J9 J% y* X- \) {; R! k30
. |4 C3 |6 a% ?6 l31
32
% G, o0 C' h! V' ?3 I; r, V% a方法二：


0 `) e' H) Q& N# ?, ^4 j6 W
% N+ N$ d- Z, [. w/ l  m#include "stdio.h"
7 _2 f4 i; o& Y& Y9 o
6 A& ]/ x0 L; m6 \. L% b! rtypedef int ElemType;

void InsertSort(ElemType a[],int n){      
    int i,j;
    for (i = 2; i <=n; i++) {
        if (a<a[i-1]){
2 Y5 ]0 v$ M8 }% e6 p) b            a[0]=a;
4 c' R# R5 [6 Q# Q            for (j = i-1; a[0]<a[j]; --j)
                a[j+1]=a[j];
. E3 \9 u& Y8 a- p  `7 T            a[j+1]=a[0];
% x* |+ K: w: p5 N9 L        }
    }
, M8 Q. _) _2 \  i}
int main(){
    int n;
    ElemType a[n];
! ?" i: B7 t& W8 F8 ~/ W2 S    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
) v9 f' W# U% }' K    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
0 g  C/ a$ \! H  Z7 P2 c- x  c- \        scanf("%d",&a);
* K' ~: c- f" ]) V    }
    InsertSort(a,n);
. H+ V. y1 L3 T6 ~$ h0 S3 O    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
8 h  ]+ K( H& `  K! R2 x    }
6 G! X7 E- o( C$ Y4 J7 {}

1
: T  F. X2 ~. ^8 m2
/ }6 B" w: H) _. g& Y3
+ l1 V* i) p+ d, i; u0 i4
5
6
) D# m  M  p  P7
8
9 A) s4 y& m( V8 ]* D9
10
5 B) F' N  q& a7 {/ t11
12
13
. `( l7 V) y8 D: \14
! y$ A# H1 t! h6 G% ]) C1 b8 j% l15
16
/ M. j: J8 k. b/ g17
5 I4 @. A2 S4 q( P8 _# j) u% |, X. M18
! [2 Q. q, ~& l" j; ?19
3 K! A. [/ W8 d8 @! f7 j20
21
22
2 Y2 }! k4 h. S. @2 a( W" ]23
24
! n; {6 e+ |: O4 m. _# J, ~25
: r" ~5 D9 f% S7 T$ m$ t26
$ R# s% [; g# V3 O1 h' d2 ~27
/ A6 [: N* O$ i" W28
! h; G  x. G, @% p' c29
6 {* ?4 ~4 f6 z% Y0 W! Y% \' M30
算法性能
) o9 |5 J) z% m" ~
空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)
- h. y" P' E1 ^, X% `* R# I
0 D* h, C  `. a. ~4 w时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
% u8 {( F8 P) }3 ^. e )
1 |, W* ?8 O5 K0 `" l9 Z1 k- C7 W

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

适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

1.2 折半插入排序
) A5 n. l1 `% m; O2 e图解
第一趟：

1 O  a& ^: h# p! ?, S( F  _' S$ a第二趟：
: W1 o2 a4 z2 G& H9 p
7 r1 D6 [0 D4 f- B% N; i7 J
第三趟：

( _  b) |8 ^* {2 `9 S第四趟：略
) `: f# p3 x' i/ i; r4 i' P& E第五趟：略
* ~% \8 ]+ X& k: _5 G2 q& o
基本思想

# S3 w% u* ^( |( t6 k9 e与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
代码

/ u1 T4 _+ Q* M3 O( r6 T8 a#include "stdio.h"
+ t% V2 Q" X$ e! `
typedef int ElemType;
* S4 _/ C  H% l& T! Q/ i: j
void InsertSort(ElemType a[],int n){
9 K  U! _6 ^% |    int low,hight,mid;
    for (int i = 2; i <= n; ++i) {
        a[0]=a;
        low=1;hight=i-1;
        while (low<=hight){
! H2 [- i+ x8 |$ ?            mid=(low+hight)/2;
            if (a[mid]>a[0])hight=mid-1;
            else low=mid+1;
9 v  x. A$ A+ R, L, ]        }
        for (int j = i-1; j >= hight+1 ; --j)
. z$ I1 J7 n2 }, A. U' i/ B: g            a[j+1]=a[j];
2 q7 Q8 K3 M% E" L0 G        a[hight+1]=a[0];
    }
}
& X6 r8 q, V2 R. J3 |+ `3 Z
& X  N) h1 k/ b  c" L9 @
int main(){
# P2 }  p1 f7 d) y! [0 u    int n;
- [$ W4 D9 Q- @    ElemType a[n];
9 O# X2 R0 }0 g% [    printf("一共有多少个数需要排序：");
4 o4 L  Z- i$ [7 X8 @0 x1 B    scanf("%d",&n);
    printf("请输入%d个数：",n);
: G5 r6 r9 z. x" D" q/ o    for (int i = 1; i <= n; ++i) {
5 n3 A4 h& [) b) H+ E/ {        scanf("%d",&a);
    }
3 n  p3 V) Q0 b$ }& M8 n    printf("排序后为：");
    InsertSort(a,n);
+ f. n2 o4 `2 ]  D0 E  a1 [" u
, I% _* |' {  y! e+ A    for (int i = 1; i <= n; ++i) {
) B$ ]1 v4 {9 z/ a3 T( Y        printf("%d\t",a);
2 z% \: c% W, v% h; `    }
4 e3 a/ H4 M& Z' X& o$ t# h* D. v}
2 v2 R: H* o5 Z8 I. x# X& K
1
2 Y/ E% t# r  _- W5 `2
$ \+ x3 ?" Y5 Z( v: x' q' w3
4
7 C, [6 j5 B" U9 {5
6
7
  s/ D3 \" I, h: q1 e8
, A! w; N& e' Q; B7 x9
10
4 ]- C0 B) D+ a( f5 K; q1 ^$ n5 d11
12
13
14
* ~( o0 q$ v4 w. G, A% W15
4 C( K8 a& {" F( S% A8 ]- y16
17
18
19
20
21
22
23
24
; B; s6 y8 X5 E, R+ |+ a25
  T5 L* i, l& y7 k. G) Y8 S26
27
4 q* p9 p( Q% f7 I" h0 {28
29
9 f1 {* I6 S! ~. j. y/ z- Y30
31
$ B8 T2 Q2 m$ G3 F32
' t. i) z# \1 X  _# E" e4 T1 W33
$ z8 q6 B* J! Q5 {% N34
35
1 B. U0 O2 R8 i) {36
6 _% u$ U% j. b, n, t/ q0 ^37
性能
+ e$ N( u9 @+ G7 W
空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
1 y, p, d2 U5 B. t% k2
)
8 |# z' E( g2 `' V稳定性：稳定
: ^6 A4 \7 Y2 ?适用性：仅适用于顺序表
+ j" b  Y( w. n& C0 j+ C' m  G
( U( s& M$ K0 M8 b  H9 T1.3 希尔排序
) }" J' d/ g2 t0 O! c1 J4 @+ q# S图解(动图)

! R0 [7 s; W+ j: i
基本思想

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

代码
7 P% B( O) D0 W7 w
% R: V& n1 N. h#include "stdio.h"

typedef int ElemType;
  h+ B; ~4 Z7 B# o3 G
void ShellSort(ElemType a[],int n){
/ I% s; w6 t6 V    int j;
. P1 c, x, y) O4 i2 ]$ P) i5 _" n    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
9 T2 k! d# T7 t$ j, \            if (a<a[i-dk]){
                a[0]=a;
                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
2 I; ?# [4 V% T3 T& u                    a[j+dk]=a[j];
                a[j+dk]=a[0];
# M3 C& z' t7 _$ L            }
# R, c/ {! I8 \  k& }+ [2 G6 o& \        }
    }
( ?6 C7 r1 f' e5 i}
# }6 F: f4 Y+ f0 D# d4 S
int main(){
    int n;
* V6 L9 _, j; T  z0 X    ElemType a[n];
    printf("一共有多少个数需要排序：");
: W8 V, i- B) u$ Q    scanf("%d",&n);
( ~) w+ h8 j6 Y& F1 Z$ @. l    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
0 ~0 z  ]& Q0 ?9 e% X" B6 h0 G    printf("排序后为：");
    ShellSort(a,n);
1 R; U: ]: i" J, C& K
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
% o# v5 S3 R5 q0 z, }    }
# M0 G# ]; P! V/ m8 S}

  y) d) z) m/ I: X/ m1
* ?$ I# J# c1 `6 H% C- P" H- a2
3
4
5
6
7
8
9
0 E+ ^7 b/ U4 \5 R# A% F10
11
12
. j0 B& {8 n9 H7 H% j# `8 l13
3 {3 D: y+ _+ z0 B( S& q14
15
16
* n# c+ F% D5 m# h9 O  ^) C17
18
, W% n; `2 s; f, e% M) D19
: |9 v' q( @" P7 b4 b20
& W; k5 }  v9 t21
& t5 Y2 }; E7 |* r2 M( `( |22
, Q' r+ t, J5 g2 X23
' u4 w2 w3 V& S24
4 r: f% ?, D8 k0 g25
26
27
28
# G: w' q7 D' S. `4 e8 O( t7 Y5 T29
2 J% o; `' t8 h+ S) R6 o" h30
31
9 y4 x* Z* W' K' @) j+ y' o32
# r; v4 |- F8 n. X8 u+ u& P, F1 u2 o33
34
) z# l, t! O( X5 F/ n9 D; r1 V性能
2 ~  C& C: x  J. l. S
: `7 W4 g( r' C4 J# p空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

. c7 f" v( m' Q2 H7 E$ S时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
1.3
$ d1 P/ R- u5 s, ]- @8 v* r )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
( k" g0 }! T' @; A$ J" U% y" z2
)

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

8 T6 d  ~6 z% }* K* A# F4 U
适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。

1 r5 V8 @/ _5 ]3 i6 D' h: j$ @3 y2. 交换排序
2.1 冒泡排序
图解
$ o/ G" g* k: n

基本思想
7 `( f/ ^4 m3 ^6 Q; F0 b4 M- l( l
" u2 c1 ^0 P% D6 E3 Z  X从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。
9 x. @  m; |# n- j' `. J$ G
代码
2 {0 k3 Z6 R  J1 n
方法一：将最大元素交换到待排序列的最后一个位置

#include "stdio.h"
$ M3 k& h1 [( D
) B$ F9 `$ ~' j' k2 Itypedef int ElemType;

/ y6 V9 ~" P& n# `void BubbleSort(ElemType a[],int n){
3 ?8 w2 ~4 W8 _# M" ]/ F7 k    bool flag;
& w! ?/ J3 S$ M. v* t    for (int i = 0; i < n-1; ++i) {
        flag= false;
        for (int j = 0; j < n-i-1; ++j) {
2 L) ^2 C9 [( I& e# F% E            if (a[j]>a[j+1]){
/ K- d3 r- N& w8 x% r                int temp=a[j];
                a[j]=a[j+1];
* J7 h! o$ P2 ^% H$ }5 ^                a[j+1]=temp;
1 m. x1 r- J8 M( O) G                flag=true;
% \. J, u, S# Z            }
        }
- V" {  V  p5 |. T2 }; }; i        if (!flag)
            return;
    }
}

8 m! l5 |5 K1 N9 J. Q
# ^  D% A6 V- X: }2 Eint main(){
    int n;
: @& j  A$ D) ~% v  I1 W% }; y    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
' R( B$ f" h7 F+ d+ G    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
, e  t( Z! e' m  a5 {        scanf("%d",&a);
    }
    printf("排序后为：");
    BubbleSort(a,n);
- Q/ y# D& X: F5 M: s7 a& l    for (int i = 0; i < n; ++i) {
5 S* X, a6 O/ E( w7 T1 D- L7 A0 p        printf("%d\t",a);
    }
}

1
1 p0 w2 R6 Y9 V; ^2
3
9 _: d5 a; k) E' N' G9 d4
: E, V. _% c7 N. h5
+ l% l& L( ^* {" {6
& C& A9 k+ g( n7
8
1 M' _4 d; U$ y* J0 g) c# W+ O0 o9
10
11
. U" |1 w8 l$ `3 a  f# H& ^& i: h12
1 \4 y7 D/ \; g0 ]: G0 z13
8 C- t$ k! K' W+ d& X' I14
' S& w" b6 g% p4 n0 ~15
16
9 G" l, L% b9 Q17
  ^4 w2 q  r+ H; N3 p' a18
19
20
4 T* s* K' x2 K0 ?8 p' ]21
5 a( U- C( k$ F. g1 D( b$ F22
23
24
25
26
8 N) T( P" z- H! ~; F; u27
28
3 q: @: T+ G) B4 R4 Q29
' M! X$ P, c: ?( b/ K# _7 V0 G30
- {# s, _9 Q( i  O  u1 m- B31
32
2 B; Y/ Q+ q5 J/ n2 [33
) O% s- c& l3 B6 B34
35
36
37
运行截图：

/ R- K4 N" E4 d8 b* a3 y1 r+ B2 T- B
0 f3 t  \3 F& I; m' h2 c方法二：将最小元素交换到待排序列的第一个位置

#include "stdio.h"

typedef int ElemType;

void BubbleSort(ElemType a[],int n){
    bool flag;
4 y  @  G8 \/ z+ O. n1 F, g: ?    for (int i = 0; i < n-1; ++i) {
        flag= false;
# V- d! @8 b9 J% R, w: y# x& m# A        for (int j = n-1; j >i; --j) {
5 V5 V8 z0 w* e. u            if (a[j-1]>a[j]){
2 [  P1 U+ z1 [+ _/ [                int temp=a[j];
                a[j]=a[j-1];
5 R9 m, [0 Q* j; _3 F( m( N% d                a[j-1]=temp;
                flag=true;
9 \* v, R9 q  {$ U# ^2 \, l) q            }
        }
+ M5 T" y- v% x8 I7 b        if (!flag)
            return;
    }
}
: q2 ^5 n+ t; k' o) G6 {. K

int main(){
3 o# \* ~+ B. r4 U0 S    int n;
& y6 ~$ }( u- P+ _% P    ElemType a[n];
/ R7 h3 a, \. M3 e# e9 {: J    printf("一共有多少个数需要排序：");
4 h3 d! _  r0 v, A3 @1 M: {    scanf("%d",&n);
    printf("请输入%d个数：",n);
" ], F! ]0 b# B* q4 l6 f+ v0 h    for (int i = 0; i < n; ++i) {
6 Y, m  R) g8 S" i        scanf("%d",&a);
" h  X* K9 i& b, h. o    }
$ j3 E1 e$ ?& P    printf("排序后为：");
    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
1 ]' _. K; z" Q2 S$ s; Z        printf("%d\t",a);
    }
# d. D) n% _2 I) g3 _/ z0 J}

" P; F' g( O- ^/ H  R" \5 f1
2
3
4
, k+ i! d/ W: z1 w# W. c+ [5
6
7
8
7 c! W1 s, o* O+ F. u, d9
10
% s2 }5 L/ Q/ b" K. S5 ^11
12
% A/ B' m) i! f13
& }# K" R! ]  o# x, s14
0 a; v: Z/ x7 R4 o- p1 L  h% A" p15
, D, C. \3 d+ n16
% [; `- p0 h5 C! N0 Q! {$ f17
! W" e4 z+ t/ L& `" j; f# C18
19
/ U0 M! g! a) z) Z: d) z( V, E9 d20
21
, t* p, S! `5 w) Y7 z22
23
: ]( F3 Y- I. m  \' f- Y24
, B/ q5 C% H+ G7 o25
# L( d5 d7 r1 S2 y1 a26
) Z( d: l( d. |2 Y  n6 ~27
28
29
' a' J0 L$ i& i30
31
32
33
34
35
! J' I% e+ ~4 I% ]( x. ?36
37
运行截图：
/ S6 X8 u3 \6 K$ d
  O% ]4 f0 e6 l3 K0 E
8 E0 g& N; G3 E6 Y7 u9 f; ?- Q性能

8 {' G/ O) j* x; S& z. m$ g空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
4 M# p, _3 T" l% P2 r6 m
时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
" M3 q0 D. {9 B9 n! n7 i2
& n6 t/ D- A' y; n )；平均时间复杂度：O ( n 2 ) O(n^2)O(n
& `! w7 a. Y: \2
8 ]1 t* Z/ M3 n1 [5 C7 c# T )；

  g% ~* j4 r5 n: c: u( ]稳定性： 稳定
3 z: A* d) q$ B( b# O
$ k3 W: Z- H* q3 q/ p( K适用性: 适用于线性表为顺序存储和链式存储。

5 k6 x8 ]! H$ S1 s2.2 快速排序
3 x2 W1 Z/ N. _! p: }图解（动图以后再补）
$ _9 g6 a/ p5 _, b第一趟的排序：

, V: g8 F" ~' M1 Y7 m8 |第二趟：
5 q& x1 u" L3 I9 b8 y% O/ J; P
* M/ v# O  z; G5 o第三趟：


基本思想

! g; ~+ U! \. t# u/ ^7 O9 r/ S快速排序的基本思想是基于分治法的:

& z& k, J: P& @* ^2 g" q; q在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
1 e9 a- ^8 }) k8 y- @3 Y2 B4 U通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
% u6 O* n* h4 J7 X; i1 i然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
8 n/ K- d- B, z* x& A3 q$ S# c代码

1 j! j- w& y3 D( I8 i#include "stdio.h"
4 }  E* b, x/ }, X# X0 V
typedef int ElemType;
# V. ?6 S3 `& `+ r3 L
int Partition(ElemType a[],int low,int high){
: u" ^0 l  Y1 }' J    ElemType pivot=a[low];
6 \1 }( G- P8 e4 W9 c% J' P' v! X0 r    while(low<high){
        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
) ]# V0 _7 d& |5 l3 Q        while (low<high&&a[low]<=pivot) ++low;
        a[high]=a[low];
" ~% g/ ~) I, j4 y% j    }
    a[low]=pivot;
    return low;
}

3 B& a: l) G! m" p4 n$ Cvoid QuickSort(ElemType a[],int low,int high){
/ r7 |0 Z# S8 F    bool flag;
# i" ]  }  z1 O6 z2 G8 U    if (low<high){
9 O+ p$ j( e! E9 p2 e7 ?        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
    }
( ]( e  M2 D% i$ j  f) s- T}

5 h2 {4 N7 S4 k. f2 z! a$ Pint main(){
    int n;
    ElemType a[n];
) }. X% D' y& o7 q+ b0 a    printf("一共有多少个数需要排序：");
7 g( v# W/ \. O$ X0 S/ g& u    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
4 M: ]9 b5 M, k0 K    }
3 j' j& P0 s8 h! c: s    printf("排序后为：");
" g6 d& a0 Z( p; W; N    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
}

" y6 S# ^" S1 [, m( Z. D  n& F
: U5 J  k+ r9 g1
+ i7 W* u' g/ d& y8 i6 n2
  I1 A6 l# g; [6 }: @: J3
4
" v0 a! @6 c: x' E2 Y0 i5
; B6 w* C% ]( n6
  W, S8 q- \! s4 C' z+ J% h7
3 _1 g0 n- g! s3 U8
9
10
11
0 C& d; t4 E) _2 Y) U12
13
- Y! f0 _3 t/ r2 R7 @: J) D14
15
: s2 I+ d" G& a6 }( X16
/ {) q& m0 R" q# @0 a% H17
18
. ?7 C" D! w" @3 Y4 p19
20
4 u' T& i% v6 g1 F* ?21
) l0 [) s9 }( M  m6 [0 X) z22
  G2 p! d9 K  Q; n23
% g, l# Y. u# O2 ~24
. Y% h% w! B7 ^25
26
6 u/ N2 \: x, W) I# S$ W% c27
28
29
30
, Q9 ^4 P1 P( b+ J5 J3 P31
+ f# ^, u( A: w  V% e( a32
33
34
& z$ p8 B  E, e3 N9 ~35
36
' X, q, ~7 w9 E; J37
! N" u& l# U2 V+ O38
39
  v* M) f, U* e1 C- F) o40
41
性能

时间复杂度和空间复杂度
稳定性：不稳定
" n# J  l' b7 }% |
3. 选择排序
3.1 简单选择排序
图解

9 L; {- T! \& d8 F. U
% G3 C5 x. }5 P/ Q基本思想

在a[0…n-1]中，将a[0]设为最小元素，设min=0
在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
. Z/ ~  E7 M7 p- t" X1 s若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
在a[1…n-1]中继续进行排序。
代码
. O& f1 [. A+ w- K2 G4 K! R
' N& K( v6 l# B, M1 W#include "stdio.h"

# M) g3 E) @- ^; N( dtypedef int ElemType;
; H) Z9 n/ F8 @) |( e( ^
6 {# L2 U8 P6 r" i* x9 j- ?" qvoid SelectSort(ElemType a[],int n){
    for (int i = 0; i < n-1; ++i) {
        int min=i;
$ P) q( B/ a/ D: m( h        for (int j = i+1; j < n; ++j)
) ?4 t7 g) @: U            if (a[j]<a[min])
                min=j;
        if (min!=i){
            int temp=a[min];
0 k& n5 }  g, \9 o: J! @- t7 v  P            a[min]=a;
( n) g; Q& C3 [            a=temp;
        }
) T* }7 }2 v1 F! I    }
}

int main(){
* W% G2 Z; G1 x) p    int n;
" g! C+ Y. p; G' g    ElemType a[n];
; K" L$ E, `- j    printf("一共有多少个数需要排序：");
% @- A- i1 S9 d( E    scanf("%d",&n);
7 z1 @, c- \% }) l8 s    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
- L# z. d  S* {; O        scanf("%d",&a);
    }
( H: J0 F, B4 t2 j" a! m9 N0 D    SelectSort(a,n);
, ~- e! g4 B. q    printf("排序后为：");
# I" l0 |  z; h( n* @5 H    for (int i = 0; i < n; ++i) {
7 r. Y. Y8 Y. T) D7 Q# T        printf("%d  ",a);
. \' Z* ]1 K4 k  k1 A    }
}
% W3 i: k8 F0 q+ A) Q% {
, M0 ?& O& W8 Y. v: l% w3 Y7 ?3 B1
2
! q  y2 e; A& e- i3
4
$ P9 R( s  R9 q( Z7 t; |( [/ ~3 z5
6
* o( S, L7 F$ o. f3 g: J& D- C5 o7
3 O; V! m6 q1 [) z8
9
10
11
) |7 s, o; [! o# l+ O12
13
  X1 B1 J! d# B8 m- X6 Z8 o14
, ^8 t) _( `$ N/ _15
7 l3 W/ T4 n) X: D5 D& y" q16
17
0 B. {% O$ H  V* I# b% y18
' F# N, {) q' ~/ e19
20
* G8 `9 x4 Z/ d- _) e2 V* ~. ~21
! V! y+ G) N# W1 x22
! M# _5 M5 h$ n/ a- ^23
/ @2 @; w7 D  t8 }24
25
7 h! r$ M3 @: N' n  b, G- _26
( Z- D; |4 R0 ?) M6 r! `27
) h, s1 M9 d' n0 T# A9 J) Q28
29
( @" ]) j3 [! v$ ~9 Q- v, w30
31
32
33
8 F! u9 {$ ^2 h# L性能

空间复杂度：O ( 1 ) O(1)O(1)
# h( N- D7 u- q$ b时间复杂度：O ( n 2 ) O(n^2)O(n
( Q6 C) r' q: f2
; b) Q% |# t& D/ T1 h )
( g* }$ Q% X0 t1 y" N, g稳定性： 不稳定
! A. T. s! `. i5 J8 F: \6 H4 H
, ~2 B# S' H4 T" x使用性：顺序表和链表都适用。
$ c( N5 M8 L. @1 @7 s" ?
3.2 堆排序
( Y) S( }$ }3 Z# A1 j& M  X( n看堆排序的点击这里！！！！
2 R. m1 K& O' K0 h; y5 `4 K6 W
6 g6 y8 t& X+ P* t4. 归并排序和基数排序
4.1 归并排序
图解
0 x/ @% {8 z( H6 @$ X' a2路归并排序

% D6 y0 K2 T# w' m# [2 R: H, b
3 M0 }7 H) }! P9 |5 h( k$ i基本思想

将待排序列分成长度为1的子表，然后两两归并，形成有序子表

/ e6 J; h3 i- z0 ]$ P: U% y然后将子表再次进行归并，直到子表的长度=待排序表的长度。
2 M3 J4 p( a- [+ H2 s代码

#include "stdio.h"
#include "stdlib.h"

4 Y+ B" C+ n/ Z4 i4 q" \/ ntypedef int ElemType;
# h  i9 Y5 b! Q6 ~$ x
, T( V9 t  t$ qElemType *b;

void Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
( v9 @) u1 T3 V/ l: T# V    for (int k = low; k <= high; ++k) {
# w& N5 [- ~+ L  S% T        b[k]=a[k];
    }
3 M7 I' o8 q, I; i. ]9 U& ]    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
        if (b<=b[j])  a[k]=b[i++];
& g$ H' g" {8 E- }4 D. i* k1 b        else a[k]=b[j++];
2 N7 e4 S$ }" b# g5 _$ Q5 v( j    }
/ l; f6 f" d5 @, \! j! U/ W: [; b    while (i<=mid) a[k++]=b[i++];
    while (j<=high) a[k++]=b[j++];
, e5 o! n2 w! o) d: ]3 s7 T7 v}
* R, T. @( o- Z/ d- D+ E' Y( |
7 y1 F* ^$ I/ v9 ~+ Ivoid MergeSort(ElemType a[],int low,int high){
* b2 M% i9 B% w1 Q5 e1 F    if(low<high){
3 H# l) O4 Q/ x0 d+ i! x5 s        int mid=(low+high)/2;
& m. F3 O4 D- @" B! A. n        MergeSort(a,low,mid);
7 h( Y  t+ D, u  X  {        MergeSort(a,mid+1,high);
1 U5 K# j1 A9 v1 n% {+ w; R! R  W        Merge(a,low,mid,high);
    }
}

( R+ T' p8 `% Nint main(){
    int n;
- e2 {7 ?; x" B    ElemType a[n];
5 j& u0 S) }* V* o' i: W    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
8 w0 a1 U7 s2 w1 n+ {1 h    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
6 V* u: l( I5 F    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
- g( D& q+ S% H$ U        scanf("%d",&a);
; A3 u4 e6 S7 c3 ]0 O4 u5 r; w1 z    }
    MergeSort(a,0,n-1);
' k7 b' W: }  b/ D. g    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
% p/ l! M0 B9 y3 K+ `& |    }
}


2 y. d, Q" T( ~: |# R' c1
, T+ B1 [: n) N+ i4 |) O6 Z" }2
3
( W: \" _8 W- \1 N: t4
5
6
; \7 m% F1 L; p( t4 Z7
8
+ I  B- q" I1 f% E  z7 B9
( n5 q- b. F" s# v10
2 q% ^# N. L" h; P* C11
  A. [( R! B7 n, n12
13
$ F6 F; y! s( Z4 i5 L# @' u+ L14
/ M* O; @# w3 m0 |% ]% i15
16
17
2 H$ k: K! @) I" z, }% f3 P18
19
20
21
22
23
24
25
7 d2 q% }9 t2 r9 i, [26
! ^( B$ J% {/ v( H' j( W* d27
3 Q1 u4 l2 E$ O' J28
29
0 x  ~5 i  K' D% }30
; M  m3 u( R6 i+ E0 f, z4 ?31
32
0 @8 m8 S1 H, n5 o7 j$ a* Z" G8 w33
4 S& m( [+ r' K9 p# V2 X4 c34
  [. q! J2 F7 b% u35
$ e& e& o, E& y5 B5 H6 m9 m7 H36
37
38
$ @$ m- k1 x" [: T+ E) }39
; a3 G6 I" E* {  ~: g1 n40
2 e$ A. N; `5 e. w41
42
43
44
0 Y: @# }( f0 Z45
% ~3 y4 `' O: D/ B9 [46
性能

空间效率：O ( n ) O(n)O(n)      创建了一个数组b
时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
" V9 k2 U/ `: }+ Z​
2 ]+ ^2 R6 S' I3 N4 D: v n)  k指k路归并排序。
稳定性：稳定
  ?5 Z! m' p) B; c2 w# A
/ d( h( {6 I. V, V2 I% F4.2 基数排序
图解


3 v8 F- |5 F# b% d4 l% T基本思想

, a  @; {5 _# |4 ?, f: p将各个位数（个位、十位、百位…）进行对比。
为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
& c. K0 W+ D0 K/ w8 V
  b! _; x2 D" X' ]性能

空间复杂度

时间复杂度


稳定性：稳定

5. 内部排序算法比较及应用
: ?7 K  Q. ^  p# t# M5 o) p5.1 整体比较

- l1 ?5 s* u, {1 Y; }/ J
5.2 时间、空间和稳定性


! Y  j% u; h, d参考资料
. W6 {9 |; f# h( M6 ?6 Z4 @  D$ p. K/ f《王道：23数据结构考研复习资料》
; }) h' u! y" _/ _5 T7 z2 s( v0 m. ^————————————————
版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678


/ ]3 ~0 Y' O" X% V3 Y$ y- y