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

杨利霞

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

% h& R* K$ y3 x6 g2 M, x排序
1. 插入排序
+ s# e( {, {; u" H* a& j1.1 直接插入排序
1.2 折半插入排序
  j7 `# B- R2 y1.3 希尔排序
8 A) n3 s* h0 }) k7 B' O; a& x2. 交换排序
2.1 冒泡排序
2.2 快速排序
3. 选择排序
3.1 简单选择排序
3.2 堆排序
4. 归并排序和基数排序
; F) q1 O. C; p4.1 归并排序
4.2 基数排序
. D% ?5 X8 e7 [3 ]1 F3 f  G; S. p5. 内部排序算法比较及应用
5.1 整体比较
5.2 时间、空间和稳定性
参考资料

9 ~! V$ v8 U4 l  m; U! \内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
7 E3 C1 F7 x: \( x) S* c$ F8 u1. 插入排序
1.1 直接插入排序
图解

# G$ M8 M8 o3 f9 h+ L- L
基本思想

9 p/ m- z/ _) y8 v; _; {1. 查找a元素在第1 ~ i-1中的位置k
) O5 R; [. c4 x2. 将k ~ i-1位置上的所有元素向后移动一个位置
3. 将a复制到a[k]
2 Z& B3 Z- ~4 @' }0 z  Z
. Z0 q% i/ H, U8 g$ T4 Z  k% B; l

% V9 o+ G( T0 I+ ~" O9 {& N- n代码
2 w/ L+ K: [$ O, ^! c: w0 d
方法一：

, }' |5 h+ U* X1 R8 z  P. \" V5 E数组的下标从0开始，如上图。
9 N. c& p: t. u7 O) m& w- m4 q
' |3 I3 {$ a& V4 R#include "stdio.h"

" Y6 q2 ~  D' p4 u. g5 _1 c3 ]typedef int ElemType;

/ O8 h5 J4 c: |- Vvoid Insert(ElemType a[],int n){
    ElemType temp;
$ d  o7 \' B/ P" ^    int j;
9 K6 {. ?3 w( k5 e3 ?9 e    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
( \& I  b1 n  j8 F        if (a<a[i-1]){
. u9 p8 x- J3 ]& A+ O6 o$ |5 C            temp=a;                                                               
0 ^. E  M. s4 }1 ~3 L) d" p& C            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
                a[j+1]=a[j];
8 J. w5 }' [% H% s8 w/ V6 ?            a[j+1]=temp;                                                       
3 j3 J4 j- |9 b( m        }
5 Q% ^1 F5 X' z  o( Y/ Q    }
4 o3 M5 X* P/ |}
8 G; ]# V7 ~, y
/ J& C* n' \9 P; }) \int main(){
    int n;
    ElemType a[n];
; J# f& j1 u% |# R    printf("一共有多少个数需要排序：");
/ y6 b* l& V: d; w; H7 b    scanf("%d",&n);
    printf("请输入%d个数：",n);
4 H" P" e1 D) t* c    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
9 F& I- t1 n$ Q2 ^2 |, r    }
    Insert(a,n);
) U9 x# |  I( P    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
6 y8 O0 h" r) k: z5 `    }
}

0 {5 _8 x% b+ u: z8 G* N+ m1
- D, y) a$ T0 M2
3
4
7 f0 v; y% c* j1 h$ t5
8 h" [; {, _1 ~7 b6
  c9 s0 e* {: {7
1 V: W1 i9 b; ~, x" ?! I+ Q+ c8 L, }8 o8
5 O2 I2 I% }2 Y( q" Z* ~9
" d7 a4 [! N! d- Z6 D2 G* s10
11
12
13
5 i; S5 G/ g! S( ~14
15
16
17
% U7 y' K7 @8 v" Z; b% C  y: @( ~18
19
20
" _) Z6 {0 O+ b1 U" C21
7 R& R8 V& a' |; ^6 C' \22
23
24
25
26
9 a  W5 x+ y1 P5 p6 O27
7 d( q6 a! j: C1 w' T28
29
30
31
32
/ C; M4 C/ j% W9 Z9 `  G/ y' T9 n方法二：

' G( t( L: V( \& j& Z! z) Y
! d9 y/ N% @) t1 W
  r4 w" O1 \: Y/ n+ N1 `#include "stdio.h"
, V( r  n9 l8 S
- ~9 u9 A7 t  t1 K2 _typedef int ElemType;
# U) z% d4 l2 ^  p
void InsertSort(ElemType a[],int n){      
    int i,j;
7 S) P& h; X3 C. {3 q0 \4 {& |    for (i = 2; i <=n; i++) {
        if (a<a[i-1]){
4 R2 u& ?: G, z( f3 ~            a[0]=a;
  {$ a+ n) L4 ^" d4 {4 [" S+ e            for (j = i-1; a[0]<a[j]; --j)
                a[j+1]=a[j];
/ b# S5 j1 ~! E7 M3 d. K            a[j+1]=a[0];
        }
, ^) M" j# h6 ^/ b    }
  [) E: S. m  ]) ]2 i  |; A. d}
int main(){
$ g! s3 j( |+ L* Z) l; P    int n;
3 b* m% R1 R0 e, `: \' N    ElemType a[n];
' f3 ?; b/ E- a: B3 g! h+ C    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
/ T6 K8 z8 L! a+ \+ U    for (int i = 1; i <= n; ++i) {
$ z, F! J& V$ z: \        scanf("%d",&a);
3 \  T! J, l) J7 W& `    }
. ^0 d5 z% n" q0 l6 N; @    InsertSort(a,n);
7 @6 a' V7 r  Y0 W( ^0 B2 k. A. O6 ]. v    printf("排序后为：");
6 p; s  O9 }- D7 c  b& n. b. q- T    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
}

# {& p; G( m, q* W4 F1
7 N; P! z2 k* i" ?, F" V  l1 Y% F7 E2
3
4
5
6
7
8
* J* j: G) J( O. z" B9 \$ w9
1 I* `  j, U, k$ ~10
$ }) }- q+ l& F0 |11
$ c2 u2 m9 R" u9 j12
13
- p; x2 `9 q8 ?0 ^& P14
15
16
17
18
19
* x9 O9 \4 o+ |8 l, O20
21
: p9 s* ?: H4 i22
23
  M" J% q& A4 X. o" K. S5 r24
% [' ?8 q. f: a1 F25
- X% n2 b, s! F! C26
/ g* H5 K; V& f3 u27
1 \9 m3 f1 P) b9 T28
29
30
/ q, e8 y' t* u算法性能
6 |- y( C3 f: n, `* @
: O# R, k$ }# h: W  N; l, g空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)

( t6 z* v  Z! U, Y& R, M8 j' r时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
& D. V; L* G9 f. e3 r+ _2
)

$ ^! V3 h. d' g8 T. ~
稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
1 a: j- F6 M& _' ?, O9 J2 P! c% S8 I
+ u3 \9 V! Y* s+ e" C适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。
( g7 q2 S1 t) ~
1.2 折半插入排序
+ K5 F% Q% J! r) t9 W4 J图解
第一趟：
" I3 P+ S/ L& p! Z
第二趟：
! |* J" z! h9 A! z% u! m
1 K/ A+ ~6 w* E# i
第三趟：
/ v3 u5 w) `9 m3 I
第四趟：略
第五趟：略
" N; |/ x' R9 R" s7 B6 |
基本思想
/ B  a7 F* L0 I5 N4 ?
与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
9 |: Z$ j) S1 q; K3 B* Z/ m取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
4 u/ M' ^* C/ K) I代码
' }; W6 X. j4 R  }
9 a8 J$ `1 x6 Q#include "stdio.h"
6 N# I) z2 F- q: Y. n8 ]! o2 P
typedef int ElemType;

& n% B* @/ N2 Y' i0 Evoid InsertSort(ElemType a[],int n){
8 w% c; S! e; y8 y    int low,hight,mid;
    for (int i = 2; i <= n; ++i) {
        a[0]=a;
        low=1;hight=i-1;
        while (low<=hight){
            mid=(low+hight)/2;
            if (a[mid]>a[0])hight=mid-1;
! }: x5 J9 H5 q" c" N$ Y& _; A; r0 X            else low=mid+1;
        }
        for (int j = i-1; j >= hight+1 ; --j)
' x  `) p9 p$ D  |- G. Z            a[j+1]=a[j];
! F0 [9 u+ {7 O; x# e$ [7 y1 g+ {2 L        a[hight+1]=a[0];
2 k4 t& q6 P2 I3 l0 J7 i    }
6 t, [' p5 }4 Y+ e}

) |) G/ V. j4 l# `* R/ Z6 O
" C5 s( P; E) q, u; Sint main(){
( j* r7 ?2 s" K& m- D8 ?* S    int n;
    ElemType a[n];
5 h- U8 d  |$ _+ H5 a8 E" t    printf("一共有多少个数需要排序：");
! N, a& F0 R) @+ f% Z/ L% \; Y. a; i    scanf("%d",&n);
! L9 V! p; G5 m* c. L2 C2 K    printf("请输入%d个数：",n);
, S& Q$ B- d8 g    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
    InsertSort(a,n);

- W  F2 u* @1 A) ^( }6 \1 b( ]$ ~    for (int i = 1; i <= n; ++i) {
. I, w& `, K& Y4 v( L        printf("%d\t",a);
    }
/ Y. R* k+ C  X8 X# ^* N3 H" r# Y( `}
1 @1 D9 J2 f: ^+ y  j+ w7 F& I
0 `8 I6 ~* H' u1 e1
+ r! q9 @& ~- T8 I) S2
3
0 y, V2 K. {5 L: |+ c4
6 _9 i9 W9 o6 v3 f5
6
7
( G6 _1 I0 Z& g  j. ]0 l- G+ s4 y8
! |1 L  [$ F1 k4 F! W% w9
9 D" B+ W3 U5 ]8 }; c" K- t% g10
% R- R' r8 C; X) r- W! B" m11
9 U/ b4 H7 T! j$ h12
13
14
15
16
6 n3 ~9 R  D, N9 V" Q$ x% G17
18
19
  S( ~; y+ `1 V; y20
9 \8 U0 I  [- v1 f, j3 Q6 e21
$ U' ]0 b4 I: P; Y$ M$ \22
  g! G" ^( C, z, ~23
24
25
26
- @8 Y) |+ S' Z, k1 v( j: f27
28
29
: K. t) C0 w& a: U30
31
32
7 n# ?8 E6 }% \$ M$ c. e! F% y33
' H1 k- k; ^5 g34
* N/ {/ Y* K. c9 g8 W* o% N35
36
37
性能
  E( t9 Y1 L* R+ m$ b( ?
3 N2 W1 n9 y$ i6 w% R0 }: Q* `空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
2
, y0 u6 {: e- Y% B' y. A, ^ )
2 X, ]' T# `5 @6 z稳定性：稳定
适用性：仅适用于顺序表

8 K$ ?$ r  W9 D; U! E1.3 希尔排序
$ K% m6 o: _8 o' C2 \图解(动图)
" C, W/ Y: L, |9 t3 U

1 {3 @9 \+ A% c9 h基本思想
. ]4 B7 ?: `: A6 O  B
先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
1 v/ J( R' b/ S5 {, a; c& s  o
& D5 R2 c" p* B* S代码
' h% D% g  [: Z" e# {/ t' v$ j
' d# b* [7 E/ F# a#include "stdio.h"
) q5 n; Q" C1 D' C
typedef int ElemType;
' y3 s4 U& }9 x  N5 Y6 y/ w
void ShellSort(ElemType a[],int n){
    int j;
7 ~% B' Q! G7 M3 ^: s7 b; Q- f    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]){
* k1 ~( b6 t# U1 l/ {                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];
9 }! A7 b+ Z' B$ d6 g# n            }
% s; ~8 u7 q$ g$ w* Q* z        }
    }
}

int main(){
7 ^0 j: J* O. g: z% W" @    int n;
7 Q; J: W, ^7 m, {    ElemType a[n];
  w, x2 R! `3 ?  S9 X6 N  j    printf("一共有多少个数需要排序：");
  C3 B9 V6 @# W/ @' Q    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
" G6 B$ u. U! ~! l+ M        scanf("%d",&a);
6 `. ^) @. p' E5 ?5 j    }
    printf("排序后为：");
    ShellSort(a,n);

! h1 B: F! i" L1 p, w& |    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
4 m# W. t3 Y& }( N9 U: t    }
# y- U) V/ ^+ U1 Q) o" t}

1
2
& }0 |/ q% t) t0 s) ?3
$ z% [  x2 [4 t0 k6 Q9 u- V4
$ T  }, X8 P3 Y+ l4 c6 ~" }5
6
7
8
9
10
11
12
6 \* P2 O" [! ^0 R9 s6 A8 i" f7 R13
7 q" {* }& N& U* [2 n14
15
# w) C/ s7 f( b2 m! ~16
4 G5 v8 s! `' S9 X: V17
; U! W: W3 \4 e18
19
" @- \; p' }2 [* }& c# ]2 s4 z( s20
21
22
; w1 O( e. a; |# U8 |23
. z# I- C  [# j  [8 X24
25
26
27
  u( T1 ~, W& y9 R, B: C/ X28
29
30
2 Q0 b: |( y4 |0 G  D* S4 _6 B31
0 V$ t/ k8 u1 K) ~! D1 Y32
33
& L& t' X# d9 E6 D! a" q4 [34
性能
& Z& w4 X! u% j; }* @# K
空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
5 t' q2 o2 B; I6 M5 S
" A) p4 g+ a9 N时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
# O7 X: ~; _! J# K1.3
$ p2 z0 G+ h# ~ )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
5 X( a5 x1 y0 `2
)

稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
; }, M2 y3 L" `$ I" M
1 n1 E$ V+ ^' h/ j
适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。

# d4 w4 A: j2 e2. 交换排序
+ L6 W: x5 y$ M! N# Z5 E2.1 冒泡排序
& x: w7 f# j3 V+ d/ R图解
$ d8 l5 q  e1 i& A/ J
( ]/ J1 V  X, `
基本思想
/ h5 X1 E4 P! M8 k; M* X+ N  k% O
% f2 \8 y: }# G4 Z% e, ~从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。

2 a0 {: ?& D- G$ _$ w9 d代码

方法一：将最大元素交换到待排序列的最后一个位置
2 Q! F* z3 X$ F) V( s, r& E
8 r  _2 v# V- C#include "stdio.h"

4 m3 }/ V' Z3 h* G8 C- s$ atypedef int ElemType;
" w, U  b" E1 z" E/ X9 l4 U; \
void BubbleSort(ElemType a[],int n){
) ]& o5 o' o2 F5 ?+ C    bool flag;
0 N( J* F$ \! m2 b: C$ }    for (int i = 0; i < n-1; ++i) {
4 G6 `. `! B. }        flag= false;
        for (int j = 0; j < n-i-1; ++j) {
2 S1 C$ f1 H3 X            if (a[j]>a[j+1]){
                int temp=a[j];
+ `  Y4 g' E" n0 f3 B' T                a[j]=a[j+1];
  l- k/ _1 n4 ~* \6 x8 ?                a[j+1]=temp;
                flag=true;
' u9 [- g+ V4 `0 {0 J7 i7 K            }
        }
6 y9 ~5 E2 \" }: O        if (!flag)
+ K( h, `- D9 M  k& v            return;
    }
+ D2 t* y' D6 x  `}


! l; J. L" A+ B( x+ W% M3 Pint main(){
/ M0 O$ a4 ]* y( T' B8 m    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
: `7 c7 e3 m; n1 T! j7 p4 M    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
& B# T1 h5 D& I        scanf("%d",&a);
    }
    printf("排序后为：");
2 K2 k! `0 g5 I  h  J7 k- u4 O    BubbleSort(a,n);
: Q) |5 A( L0 E$ s    for (int i = 0; i < n; ++i) {
( v& y  F" o) b* z6 a. [        printf("%d\t",a);
    }
& i; N8 r; v- Y4 n, q}
  K! G: ?: x3 _  s8 o
! D' R2 ^$ I2 Z3 F+ Q* \9 D1
6 {- d  G7 G3 u& l1 |2
& K( C+ ?6 [4 q4 {8 u4 X3 R: z! e3
4
5
/ |& [1 L7 T8 d/ Q5 w5 M1 R6
6 _4 `: R9 x7 B2 ~7 r/ U! a7
8
9
10
11
+ ^$ z7 u9 o' F( E$ S  g. j12
% G2 I9 j" @1 I( F( a! V13
14
+ }& M! k" Y1 h. a# Z15
16
17
) |' B  [7 I7 H1 d% v' D4 p18
19
  V# ]9 z7 o* z9 s0 O20
21
$ g/ N: x1 z; I# F* G22
2 C8 Q" T4 g+ J6 q' Z23
24
) l8 {+ u- n9 u9 V25
26
27
( e. k1 W/ X: Z! t  ^- e" B2 d28
29
  q8 s2 N  J' e/ \5 n30
0 p$ T8 p4 F9 r* ^* i31
32
( Z& x$ f4 T( d, G, v* H33
- d! D" m' ~* a34
35
' }0 T8 H0 Q: M4 o3 {% w6 h36
37
, {( ~# C( @9 M  N# J( u9 ?- Y! h运行截图：
& ]3 |' a4 A- G0 g6 J/ d/ F9 h
- p  V( [' T# K5 R: t2 X4 h. {: u
方法二：将最小元素交换到待排序列的第一个位置
# M  A9 }. c8 c% r
) q9 j3 \4 g  k4 ~. p  Q+ y#include "stdio.h"

: \8 k) o# a$ `3 i- w$ Dtypedef int ElemType;

void BubbleSort(ElemType a[],int n){
* ^5 n. b& f3 v" }  @1 k    bool flag;
! v$ u/ _  r8 H6 M# @+ ]. X    for (int i = 0; i < n-1; ++i) {
        flag= false;
8 c0 T5 q$ d& ?$ h  U- q        for (int j = n-1; j >i; --j) {
( ^6 V& M5 J2 s4 C& J; D            if (a[j-1]>a[j]){
/ O) u$ m' P+ |; `# z" j6 a3 Z                int temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
' Y% H+ z1 z8 {9 ^! z& C                flag=true;
' p8 l4 H% ~- x# [4 h            }
- h' |4 H8 I- M$ Y        }
8 Z) D" E5 l0 Q7 Z        if (!flag)
0 ]* G# k+ P5 }: q5 m* C8 f            return;
" \. V5 E$ q: b0 Z    }
" O4 E  N7 j- p$ H9 F4 q}


int main(){
    int n;
( X" [7 o7 {4 |, s0 z: ]7 g) @    ElemType a[n];
" l0 W, O, E, R6 v0 G# v8 i    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
8 a! O( _! U) R2 {: j- {    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
9 @) M/ G  B* C. Y" X    }
7 S) y/ e9 ~% ?8 `, f    printf("排序后为：");
2 e* L+ w* D! ^7 x% A    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
5 ?. F0 I8 y7 D3 F  R% T        printf("%d\t",a);
    }
}

1
2
3
4
( |3 `. l5 `! k' G! `5
6
7
2 @0 o) ~& d/ t8
9
6 d! b  t" t& B' s' y2 M9 F5 o10
8 s! ]7 h, R5 I  L) C$ _9 ]5 M11
12
13
/ k, E( i0 s  Z14
15
& o) Y) Z- v  u/ x2 t1 P$ |* z16
1 q. N" q9 s7 D, t- l" x6 W. o17
% \* P2 Z  [* H/ }* H# [) v18
4 I0 d0 Y7 i2 Q) p* w+ ~6 B19
- d1 Y& q! j( q0 X& N20
21
22
23
7 W# i! N; x1 @& p24
  f+ u) h+ z  L1 T- R25
26
27
28
) N; ^9 a: k/ |' v. b29
' c% m* D/ S9 y3 c6 k: O30
31
32
33
: u6 V4 q( {) |" s1 y2 N: ~34
35
& z3 G% p  ]2 _6 w, E; m# o36
! c6 M+ {/ }4 h8 _. U+ S37
4 \1 W( Z4 D) o: t3 j5 U9 l+ j# Q运行截图：


1 c- p  n5 g$ _8 k8 r. i' w性能
2 c* r( g" B/ L6 g7 x; d
空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
2
)；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
)；

% Q3 ^/ G. n, L. }1 w稳定性： 稳定

6 J& k& b/ D4 L, a% t适用性: 适用于线性表为顺序存储和链式存储。

2.2 快速排序
图解（动图以后再补）
% i7 ?" c4 k2 b8 D3 B第一趟的排序：

8 X, K5 R4 @! P0 Y第二趟：

6 Q. \3 t, i. Z4 d+ g第三趟：


基本思想

- e* S/ y- W3 q, \. O' R) X% Z快速排序的基本思想是基于分治法的:
; _* Z' u$ F4 f' p' L6 r, U" L0 K
$ V* W) `' R/ E3 o在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
5 s0 Z9 j% X5 F通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
) @! a) z6 I4 Q, a/ c+ t/ D6 R代码

. W0 X. ~% j$ H, W/ l#include "stdio.h"
' J. D% {; o- F
: _* A* P+ d( g; |typedef int ElemType;

- b! k! v9 s+ Iint Partition(ElemType a[],int low,int high){
0 s/ m( z5 ?* l3 g1 d9 T. M- G    ElemType pivot=a[low];
1 a) ^0 q. f8 G    while(low<high){
3 }4 r. x5 h( \1 o, q& @        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
        while (low<high&&a[low]<=pivot) ++low;
        a[high]=a[low];
$ ^0 ~: k* Q7 u/ n    }
    a[low]=pivot;
% n  d, I6 J% k: F, U    return low;
}
& Y  c( H! h7 c7 i& z( K
# F4 \/ G6 V: U8 _% l) ~. {3 lvoid QuickSort(ElemType a[],int low,int high){
8 W/ B1 v% s. Z. {# i    bool flag;
    if (low<high){
        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
* r, _2 S+ `/ \/ i    }
}
' D' k7 R. |$ g" G0 S/ f' K& h) ~
! ~5 h8 k6 n( A0 k% i6 }7 Bint main(){
    int n;
0 ~/ G# M- ?  ^- d    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
  j# b  U  p. u1 C( n9 s    for (int i = 0; i < n; ++i) {
4 _: p; Q2 p& Q0 O        scanf("%d",&a);
    }
7 e7 L3 r6 C# ^: I( ^2 _    printf("排序后为：");
: w! P' d2 Q0 i, {+ P  {8 \; ~    QuickSort(a,0,n-1);
5 S# b5 w' ~0 B+ }: y8 n, N    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
}
6 A" ^3 e- c" `& P! ?

1
2
3
  B8 N5 L  J. j- t6 U- L- _4
5
$ Y( c$ F) g$ @/ [6
- D. s( i( h& l' \; N6 x! k7
8
9
10
11
12
  C: D. @& @! L2 }) Q* B4 Z( T0 W13
14
) J- d9 C, }8 {' |; |+ x7 O15
, d  A' h% F, J16
: `& K* U1 _7 d3 ?8 P8 m17
! w! C) F; m" R18
19
20
21
8 J7 _* `2 Q" `) F+ }  j22
23
' Y2 W  T! X$ {3 a6 f: J8 r' @5 o/ L$ b24
8 m7 Q% w+ J1 q6 h* t25
  [4 Y( z" n+ J) @. R) ^$ U, C5 }; Y! F" M26
27
28
3 Q' V+ W% d; h7 n* [: B29
30
& K  g- Z3 H: t" }; K31
- h) E! X! {1 N; [# K6 U32
# g5 d$ Q) q* G8 A, ~33
. j& _. z- A# G8 ^1 q8 F/ w* b34
$ i; Q8 {3 Y& }* |$ S& _/ d35
( Y3 j; a2 V" @2 B& R/ ~6 p. Y36
37
: n8 o8 E& u+ o+ s# m0 R& t2 Y/ L38
39
7 Z" F3 j' o7 @( J40
41
性能

8 w# @% Q& y. I& U& u5 ?  F; m时间复杂度和空间复杂度
- h9 a3 N4 q" ^1 j稳定性：不稳定
% G0 D9 }  d) K3 x0 x
, r/ ]9 p% l1 o7 g, z) a3. 选择排序
3.1 简单选择排序
- i4 O& M- x: P$ a: h图解

! t5 a: L4 r" h. U
基本思想
  L, C+ ?  H9 x* b/ x6 b: l7 z+ y; ?
在a[0…n-1]中，将a[0]设为最小元素，设min=0
在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
在a[1…n-1]中继续进行排序。
代码
/ \0 y! U- }( }" w. v% H
) C5 |+ x  ~. Q0 o#include "stdio.h"
/ s# j- T2 M3 z
9 k$ e! J  R; ttypedef int ElemType;
+ Z+ H. D# ?) V" X* y( `
- [$ y# i+ L- T# O; q; }9 Z% _void SelectSort(ElemType a[],int n){
    for (int i = 0; i < n-1; ++i) {
        int min=i;
$ W6 F1 p* W, ~        for (int j = i+1; j < n; ++j)
' T, W7 p4 Q6 G: i/ V            if (a[j]<a[min])
                min=j;
8 e* U. x- w# ?, i; D        if (min!=i){
            int temp=a[min];
            a[min]=a;
            a=temp;
$ e  J5 N9 u7 L# o8 @6 d        }
- Z3 j; q' Y' }3 I$ j    }
& ~0 a: x4 p& H7 \0 h}
  f: t4 n# X4 ~4 E
int main(){
9 V: i$ T" t  g  A    int n;
    ElemType a[n];
% K" B8 e1 h; g    printf("一共有多少个数需要排序：");
, `& E3 O$ {+ ?, i7 e4 {0 E    scanf("%d",&n);
    printf("请输入%d个数：",n);
- {- _+ t- L+ [" _/ {* H    for (int i = 0; i < n; ++i) {
  J0 R$ u  a, T7 O6 V9 N! E6 Q        scanf("%d",&a);
' Z' s' v# W1 ~6 J0 H7 s& h$ s2 U    }
  G: T* ?1 P! r0 ]3 p  k. U    SelectSort(a,n);
! u7 |1 K4 z& q0 P; r. H0 k    printf("排序后为：");
! R) b% ^$ Z5 Z    for (int i = 0; i < n; ++i) {
# k5 Q  f( B) A$ \6 X& R8 p        printf("%d  ",a);
6 V! ~( K  J' o( l( q' u+ Y    }
3 N6 F2 u  W: w}

- s# Q1 g6 V! ?" T1
2
3
4 B: R1 Z( W3 |7 q2 h. w+ e! `4
5
6
$ p3 g. \, j. M/ k7
8
( G  C3 j0 k$ b" J/ n. m1 E9
10
, |: A% [4 ?* F8 s8 h% {8 C7 C, O11
7 h0 c4 O4 Y8 m8 Y12
% u7 G- q& j- X1 A& O13
14
. p8 z! B7 m& w9 s1 Y$ _! M15
16
17
18
19
4 w5 [0 O2 L" g& i& @; A6 V& n20
1 U# G: z8 I/ B21
' v4 E  x4 _1 W) r: X: z22
23
& }* ~  y( s+ f) ]6 K24
; x- q: g( m1 K1 I$ E$ X: n( M' I25
26
- A% {/ B. U4 X& ^% l4 l6 ~27
0 Z% }( B( b& ^, |# {4 c28
7 p3 l$ B* p& N! I  y, i29
30
* c% F2 o( l" S# m' F31
32
33
性能
- F2 c0 C, p& F& W+ P+ }
! d! @  e5 w, N( H8 ~6 ?) X! C空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
  j/ r8 C. n  n7 i2
)
稳定性： 不稳定
- k: _' U+ H0 K# X) d
9 d2 p. r5 w$ b2 D, Q+ N使用性：顺序表和链表都适用。
8 ?* O/ y. o* Q$ j3 n/ ]' k
3.2 堆排序
看堆排序的点击这里！！！！

0 H+ \7 E6 P) `% H' G, }4. 归并排序和基数排序
4.1 归并排序
图解
2路归并排序
5 X5 A- E; ^& E% Q
! p& q: M$ U0 _$ y  _
基本思想

$ Q4 Z& B1 D+ }! O+ B$ G8 }. V将待排序列分成长度为1的子表，然后两两归并，形成有序子表

然后将子表再次进行归并，直到子表的长度=待排序表的长度。
1 |5 j8 M2 y, i. d, O7 w代码

#include "stdio.h"
5 j) @! u2 q; _5 a#include "stdlib.h"

typedef int ElemType;
. x# {* q( p7 _$ }/ p0 t
! W/ Z* E) Z' @2 y! @; \) MElemType *b;

void Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
    for (int k = low; k <= high; ++k) {
        b[k]=a[k];
    }
    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
        if (b<=b[j])  a[k]=b[i++];
/ }0 [! Y* h) [) I8 h$ Z! V        else a[k]=b[j++];
    }
5 ]1 o/ V7 \: p3 F+ k. n    while (i<=mid) a[k++]=b[i++];
, V  r: S  ]% ?    while (j<=high) a[k++]=b[j++];
/ J" g' d! M5 e: G$ O$ y}

% O% t8 S/ x: g+ B) Svoid MergeSort(ElemType a[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;
/ J0 a7 i& f% M3 f        MergeSort(a,low,mid);
% }0 L3 _& c" V7 p7 `: e; d6 x# X        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
3 K5 p1 K/ R8 e* p+ f}

5 K, ~, \8 o- ^. {6 S+ Oint main(){
    int n;
    ElemType a[n];
# ^3 {* J2 K7 p4 f# T! i    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
/ e# n2 j& a4 b8 M    printf("一共有多少个数需要排序：");
/ O' k0 h, o5 l4 Z- \    scanf("%d",&n);
" ?4 |) v) M( A+ N    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
& J. ]# Z  R! K1 ^        scanf("%d",&a);
: z. q% j3 r% c! I+ E& l    }
    MergeSort(a,0,n-1);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
% N/ ]0 A/ Z" U# Y% P- `8 t0 [        printf("%d  ",a);
    }
% O% R0 ^4 @4 A; n) {+ p}


' f# C" k4 f0 D. g5 w2 A- i1 {) z1
2
3
% w8 Z8 N: ^' }7 w) V4
5
4 d1 D7 x* I8 D  `6
7
8 F: B9 B$ C: [% s8
9
10
; A1 H- X" Q7 C. ~11
* d$ K* F( \8 A( W3 e12
2 j: [  ^5 Y4 p, E; Z0 p/ i13
14
1 A6 I! S( F5 k7 @) P15
16
17
% |8 m5 G1 k* E* Z( Y, e18
19
+ R0 n: F8 `7 T# I20
* y- v( ~( s$ h. U4 |) m) I21
22
23
24
) S. j3 n; L  M$ H$ m# t: z( p25
26
; _! T5 R: e. g# ^6 @. F# P/ S, k1 R27
28
; v2 v3 m4 S9 \% t, B+ f29
30
31
, {# X; i/ V; E6 j- l32
33
8 ]) h. u) G9 n2 c34
/ c* k. J/ G2 ^# Y5 E% Y! _4 m2 N35
# d8 S' F. T8 ]* j36
* C9 t) I& M! q8 g1 s+ ]37
' O) R7 e$ a) @" S  f38
39
40
$ n' {7 d1 G* N( ~( _41
42
43
44
45
2 R+ p2 v& o9 {1 N! g8 P: A  o* R46
0 G( {1 ]6 T/ X% ]" Y( F性能

空间效率：O ( n ) O(n)O(n)      创建了一个数组b
时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
1 x' l0 e9 ]; D* b( M  g; q​
8 p; w7 \( K' r5 v6 F n)  k指k路归并排序。
$ I* V" ^. l3 R1 l/ L稳定性：稳定
- C4 z8 l/ b' @
; _5 r9 |4 S6 w4 n1 K) c4.2 基数排序
3 K4 O' d6 p* M/ Q' g  [图解

$ h6 [; G. Z  [. w
基本思想

6 F" H* Q. w+ m' d3 |6 e4 L将各个位数（个位、十位、百位…）进行对比。
为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
: K! a+ v, @5 x' p! H4 ]: y
  d; O+ x' Z3 s+ F9 w) U2 k性能
* F$ g; d" ?$ [7 P; @
! I" H" h, @$ B# H/ @0 s空间复杂度

时间复杂度
7 K& }; M: @4 L4 G. B5 {0 j

" _3 ~! T. G+ o4 S% [. K稳定性：稳定

; }# f$ F# U# L) r8 H$ @5. 内部排序算法比较及应用
5.1 整体比较
9 p/ a( M: c, S) w  e1 ]
* O; h7 G, b$ a" o1 t
2 F' x9 x, X0 {# m; C* I5.2 时间、空间和稳定性
: @' ?1 A) T! e' f" W, W

6 y" O0 H& \4 C参考资料
. B; ~6 e# M  L" e《王道：23数据结构考研复习资料》
  f* ?% ^- y% a# R/ H) k" Z————————————————
版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678