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

杨利霞

数据结构：九种内部排序（动图+完整代码）
8 _' i1 o& q# L3 |' H- t
排序
1. 插入排序
1.1 直接插入排序
1.2 折半插入排序
, e& d6 J5 x# k. {% |* A1.3 希尔排序
2. 交换排序
3 G# w* X! I/ x* ]" K/ G2.1 冒泡排序
2.2 快速排序
3. 选择排序
3.1 简单选择排序
3.2 堆排序
4. 归并排序和基数排序
% h7 q/ N8 W- T3 ]3 r9 G+ h4.1 归并排序
4.2 基数排序
5. 内部排序算法比较及应用
# ^5 L. y! T. N, T& s+ \5.1 整体比较
5.2 时间、空间和稳定性
参考资料
0 ?- d8 K3 M, p, T1 J3 d1 d; Q! I
内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
1. 插入排序
. y/ I1 q5 Y& Q7 M) ?7 e# {1.1 直接插入排序
图解

. I5 z8 f! @; D4 a; B
6 j- z+ R  f6 K2 A; j# }基本思想

1. 查找a元素在第1 ~ i-1中的位置k
2. 将k ~ i-1位置上的所有元素向后移动一个位置
3. 将a复制到a[k]
$ q) B3 `& s, f. i3 ~


3 v. N' r8 _5 I1 T) i# O代码
+ u# `% q; S/ b. e# o
5 D! v7 |+ h$ l方法一：
7 g9 C6 a5 ?  h0 f$ @+ U0 c  E0 i
: _- j3 N: k" i  K3 @  U* y/ y数组的下标从0开始，如上图。
* k/ \# a, c+ i) S# N. ^2 B
* a0 f$ F1 {& d; F#include "stdio.h"

/ J4 E0 K$ a9 B2 J5 gtypedef int ElemType;

void Insert(ElemType a[],int n){
/ i* f8 j' M! D- Z1 Y$ `! P8 z    ElemType temp;
) B( N" m* t: u1 h3 ^    int j;
/ x4 j: }; j# |6 B    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
. x1 E. y5 Y' |+ A/ [" \        if (a<a[i-1]){
9 G. j6 ?& C7 X0 D3 q6 j9 S            temp=a;                                                               
            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
                a[j+1]=a[j];
3 t# U  ~: M$ ^            a[j+1]=temp;                                                       
5 @- Q5 e' W6 z8 z- ?! ]0 e2 G        }
# a4 g8 `1 l* @/ d9 m  |    }
& o' D) X2 ?7 u: s}
, g  Q9 P4 H+ x, ^; j+ Y, m! J
int main(){
% B" ^/ ]/ S6 J  l# _    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
7 q. w7 ~1 R: z$ |* [7 M3 q6 [    for (int i = 0; i < n; ++i) {
/ Q% }& d, Q* j" w7 X# U        scanf("%d",&a);
1 s+ B1 ]" [# ^0 p3 S) O- G, P    }
    Insert(a,n);
7 z6 z5 \# v/ Y1 \- S# z7 W+ ?$ ~    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
7 z; j7 n$ Q+ J3 D% O}
$ U$ m, J  z7 i& ]5 o+ L
8 |' H/ q) l8 g# J/ H9 L. Q1
8 o& j) r: w  j$ f# E' V2
' `5 I! o& ~' J/ ?3
, _  n; w5 S/ D% |- O4
5
0 Z, m) B. k( ~  w2 O6
7
' `8 o9 R3 G$ T4 {. @8
7 u7 e0 ^4 M( Y. A0 t6 R9
5 E) X* J$ ?% b9 p6 ?10
2 {2 z1 L, k, m2 b! }11
12
; G2 l. v, D7 x. ?- K7 s- L, m2 y13
! V* _+ j  `/ ^3 e14
9 {0 a: Y: H# A: e! Z6 |7 P15
/ ]& f% @( f9 R- D/ x16
17
. H3 `- y% v6 \7 R( c4 C1 K5 g2 D$ \( k18
. U: ?; P9 P4 G# G$ W& L8 ]19
( A2 \0 h) v! E' `5 ?20
21
4 |% j# O$ X% f  i; A. [& B22
23
: q: j8 j! b6 y' t/ p24
25
26
, B( D# A/ D1 W6 ?' X27
28
29
30
' X$ W% ~1 X& t1 M/ o31
32
: N/ t* |* J) v  l. J4 b方法二：
. J- t( w; I5 m1 V+ f# I/ j

4 R% ^' Y2 E0 w( w8 u. j  w
, U' R: z2 [. i2 P#include "stdio.h"
8 j# H7 A: G( U8 S  i/ `2 h; l
typedef int ElemType;
/ A1 Y9 N$ Z# s8 E
/ @  H! {& G9 D/ Bvoid InsertSort(ElemType a[],int n){      
; b! @; U2 Y2 A4 O3 u    int i,j;
- E- h$ K; v  B% b  @$ ]! n    for (i = 2; i <=n; i++) {
* m4 M) U. q- D- Y3 v. a  o        if (a<a[i-1]){
            a[0]=a;
            for (j = i-1; a[0]<a[j]; --j)
( c2 b! L3 g5 j/ q8 c2 J( p                a[j+1]=a[j];
6 ?2 ^' e* B& ]" Y' W( l            a[j+1]=a[0];
        }
. e9 I) j! O; \9 V! K    }
}
int main(){
    int n;
8 |7 Q6 x1 U# l# s* G    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
- C+ t; v" i4 U9 N/ `        scanf("%d",&a);
4 k9 U; ?7 |  E/ o7 m# \1 W/ e! o    }
    InsertSort(a,n);
    printf("排序后为：");
6 ^1 H$ }9 ~/ y$ r4 @    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
' x" B# ?3 L) a4 r. \5 u8 P' `3 u}

& P+ y# s1 a: @0 }1
" A5 J+ h3 E! y0 I: x+ [7 o2
3
4
5
6
7
8
3 q! {1 B  ^5 Z) C9
2 J1 c- M: n- r7 S+ {! o; E8 R10
( T' ?9 }" a/ u1 W! E; v& y4 v11
12
13
14
15
6 Q4 G8 @' E) x0 m16
17
18
3 {. L) w6 `8 ~( b  E% [19
20
21
22
23
24
5 G! U, d6 ~0 K1 ?" n0 U' p0 i: U25
26
! @/ V: ~4 _2 Q' n27
( U) h  A3 A7 a$ k, v- ]28
29
: Y, z! a' K1 n) ]/ B30
算法性能

空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)
( X2 H  D" u- y* u
7 E2 ], ]% Z" T" \0 ]/ q) f时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
. q; w* x" q3 b- y3 u# b )
7 W5 K& e, U. f' n' }3 d
4 C' `; z3 X2 [/ X- u
  C" y: g" n* A8 h! ?  I: d9 |) t稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
- v2 P: w! X4 d/ G
& `- A! f8 F, T; R7 R: G4 y% Y' `适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

1.2 折半插入排序
图解
第一趟：
7 r  E, }2 A7 \; k; R2 X
- S3 E+ e2 {/ O, B1 ~第二趟：
* S7 z2 ^- U- E( s

, f/ g& R4 A+ ^8 _: r0 s8 z# I3 t第三趟：

第四趟：略
' K- X/ P7 d) U7 s0 ~第五趟：略

. Q+ l4 e2 R/ K$ L% N基本思想

0 R; J8 q& ]9 J% y! @1 _与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
3 e/ Z: G( c7 p5 K取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
代码
% E4 u" J& s1 F7 H% p
#include "stdio.h"

typedef int ElemType;
5 `# g6 o$ h  @$ N6 c, [
void InsertSort(ElemType a[],int n){
    int low,hight,mid;
    for (int i = 2; i <= n; ++i) {
" ?4 L& E4 g& w        a[0]=a;
: H" o, Y& B5 \) Q: P- A( d! i        low=1;hight=i-1;
        while (low<=hight){
! M$ P! w" n3 @1 ^& X- l' }1 I; L0 F            mid=(low+hight)/2;
' L) ^! ?5 ^% F7 U( \1 I: _, N            if (a[mid]>a[0])hight=mid-1;
7 K8 m. d8 C( O* s+ @" ?' R5 R            else low=mid+1;
* ~) W) S( Q. y3 v        }
        for (int j = i-1; j >= hight+1 ; --j)
; P: T4 E  ?8 N# J' c+ s            a[j+1]=a[j];
! f: a3 J0 K0 N; R# r; n: L: Y5 m# L/ P        a[hight+1]=a[0];
    }
+ U, i) a" [- @3 b. \( R8 T/ _3 y1 }}


: ]8 o- {2 s8 A( i8 @int main(){
+ j6 I$ W5 f' a    int n;
" u4 B/ l$ U9 w    ElemType a[n];
    printf("一共有多少个数需要排序：");
8 I) O2 [5 S2 p, s  r7 j% `7 I% H    scanf("%d",&n);
" w8 f- ^. S$ E3 o    printf("请输入%d个数：",n);
- ?" {1 d7 \- Q( J3 _    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
( s! Y) w+ d& A5 `- ?; C    }
& i! \1 p0 b0 U7 L) z& }    printf("排序后为：");
2 ~2 r; A7 u; q/ R' t/ ]    InsertSort(a,n);
9 \/ m, F5 i/ p2 b. m( p
- h3 O% q/ G  M# _" _    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
7 @0 Z1 j( ^* o    }
" r1 a* T1 s3 I9 q- S1 w}
) D) m2 P3 v9 B: u/ R7 o7 P" V& r, A6 a
/ h/ x1 E9 N4 l1 Z1
% F4 `+ I0 m* f4 x2
' f+ g+ {0 D7 W: ^! v3 h6 T/ C: l3
4
+ H) Q- {7 k' ^; f0 v5
6
7
8
& ?( L& D2 z9 E- f. k3 }9
10
11
; V+ g0 F3 {! @& {* f12
# S/ a& W. }+ b4 R6 Z' s13
+ x3 y5 u" M. p  y- s! `14
15
16
17
18
19
( l2 Y' c# p% a+ J. I4 q( `20
21
( ~( i, y: n# P& m! Y# ]22
1 G" s" d: s' ]1 ]1 m$ W" p23
24
) G2 o+ r5 V) G7 ?1 D# O1 E* h& {25
4 t' e4 A8 e- K( _" {, b9 V26
9 ?+ i9 g+ A1 I& m27
. U& Y6 \/ z5 e7 o28
. Y5 P) L! a% [29
30
31
2 P4 }6 q, v& t: A32
- S+ C. ]  E) A- D) L/ g+ @9 z) i. Z33
& I$ Z) e! g, n4 D% l34
35
# }# a, ^: k" n3 `3 V* ^# Q36
( v9 K5 D+ H1 U6 h; Y37
0 C# n+ u  y  T0 w( k! S性能
, W; `  s$ V; {; G0 S
  c% ^  i& |; V! C5 W4 t% n  s空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
1 K8 C! D" Q6 t5 N! L2
1 S" [/ N6 o3 E4 `+ k3 ~ )
稳定性：稳定
适用性：仅适用于顺序表
/ L$ F& `: G9 H( ~5 D9 |
1.3 希尔排序
图解(动图)

$ m) o( }. |+ p" A
3 |) s" f: j7 f5 k' P基本思想
8 M* [2 f& g: a0 F6 ~
: w" D4 a4 J* c' @先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

% M) D' Q! T& Y* }* K& ?5 o代码
$ [8 a0 w- L, ]4 b# d" k$ N$ F
#include "stdio.h"

typedef int ElemType;
1 w) Y3 n/ U7 F+ D8 C7 Y
void ShellSort(ElemType a[],int n){
$ [( h) C" D  J    int j;
    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
& \( ]4 Q8 g$ T* }& m3 |  R; z( M        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
            if (a<a[i-dk]){
  B6 Q% w( w2 R% I7 T& X* I0 v& H( t                a[0]=a;
6 N$ y0 M" C. S                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
- n  f2 f& r: y9 r  \3 R                    a[j+dk]=a[j];
4 z1 ?9 T+ |% N- j9 c! i                a[j+dk]=a[0];
            }
* L  f* |3 `# J5 D$ S7 @        }
/ l) H3 T% v1 {- [" c# M# d    }
}
/ V% h1 F  d8 P1 \
! [. V( k8 V, {( ^9 p" @: A, T; Mint main(){
% R; R5 a& h) ?+ }" X    int n;
* Z% M) a$ P9 O" x2 ?2 Y    ElemType a[n];
/ v6 }& a( O4 d8 q+ E+ w    printf("一共有多少个数需要排序：");
! I! h- h1 G2 |4 A; ]5 m- D- ]+ O    scanf("%d",&n);
. e% E" M, x' e1 \1 b3 t    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
% I% {1 s. t% {! J/ l8 t        scanf("%d",&a);
7 ?7 ?/ Q6 }% j; ^6 F    }
$ N) w$ E: @0 v; x2 t6 y0 G" E    printf("排序后为：");
    ShellSort(a,n);

    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
# }4 v7 o$ _5 d! q' t3 {8 X& p    }
: Z& v! N- y. D  _' b: k& l2 O}
5 @$ r7 O  b; `+ r5 G5 s
; B0 W6 M* a! D* R1 U1
, v# o' W9 I: H5 P2
3
4
5
6
7
8
9
10
* T9 m+ L9 F3 [0 Q- Y/ G11
" s% X  L0 d, d  P+ \12
1 @7 s- p0 p4 W$ K, d2 m13
14
- K3 l7 C* u$ x; S1 W15
8 \, l: h+ g8 W0 o16
: Y, `5 R: a, B17
18
+ g+ x) X" L" Z& z0 P: e0 k) C( J19
1 k5 V0 C3 u9 a/ p- y20
21
22
23
: w8 o3 D3 u% S& {' h0 L. ]24
25
$ K- P: s+ w& d$ }) i# S9 I26
27
5 g9 g# `7 G- q  F$ p28
5 |7 G( m' L) g0 [+ V29
! d; m0 @6 D; H# ~) }) k0 P5 A30
31
  S( N2 C8 S; C; |* @5 S32
33
34
性能
) R. [7 Q$ n( }3 v
空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

$ W, v: c+ T0 U时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
1.3
8 i5 ?" b/ j4 S )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
# k: E! n- K: J1 @4 \3 [! D+ Z  T2
)
" G  E0 G. }6 i8 f) ^* Y
! l* d2 Z# g/ E8 e稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
) D& O  i  i* I3 o/ Z

( p5 _( O  l# p- H# ~! N6 R! h' T9 [+ t适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。
" q5 V6 U& G3 n/ t4 X$ b: `8 h
7 g3 ~2 [3 D1 L# V: T2. 交换排序
4 \# l) [9 |, ?& q$ ]/ N2.1 冒泡排序
. N# Q6 ~- F, Q: n4 _$ D4 |图解

% H9 ]( p3 g2 i3 Z: H
! f$ M* f" b/ P, x基本思想
5 F! v2 i  s  ~) @9 y
从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。

8 U" i, i6 W! z0 y代码
4 `7 u9 Y  ]9 w) i& S, }# b" x
5 Y* w9 Q: D3 x, {8 E# m2 Q6 Y$ M3 ]% v; H% [方法一：将最大元素交换到待排序列的最后一个位置
7 K% F  u6 J! S: Y7 A% x
9 P( r6 G% U' ~# v0 O4 o#include "stdio.h"
. g8 H9 j- R" I, e3 j9 [; I6 i
& N' w3 O$ p9 [8 Q: g" u* stypedef int ElemType;

- Y) k* }. k7 C5 c- {# {void BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
        flag= false;
        for (int j = 0; j < n-i-1; ++j) {
1 }" c* N# u6 N% f, Q: O            if (a[j]>a[j+1]){
/ B+ S7 _" m( `6 q5 n: C) M                int temp=a[j];
3 l# a, c6 w8 r5 p: C  T                a[j]=a[j+1];
$ b! O: {+ V) K6 N$ ]                a[j+1]=temp;
7 h' M1 D) [3 [% ^' X9 D# b                flag=true;
- x% G' f' q/ s            }
        }
. l% j- ^' r0 N! J. n        if (!flag)
) R$ x5 p0 s2 i& T9 K) ^, k            return;
7 ^, C1 K/ U* [/ H    }
4 E3 K+ P! y1 C; L& s# A% U. X}
: ~* a3 i3 i8 R8 A3 \

; l2 z* L' I, }+ v: \  n  Pint main(){
    int n;
. S. P( ^+ o6 G    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
7 ]+ s  G& _, ^4 u5 B7 C1 A    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
4 V" {2 C+ \/ A" e    printf("排序后为：");
    BubbleSort(a,n);
9 x9 W; R) z* E1 _    for (int i = 0; i < n; ++i) {
& w6 I" U, E' \9 o/ e        printf("%d\t",a);
    }
, i: I6 l" z3 M" C& S}
2 V. }: j& G3 c7 x' g+ q9 y
1
- x. A4 b! ~4 E6 K6 @5 K2
3
4 }0 j& b1 R+ i4 ?2 V4
2 b# y3 U  ]0 x* ]6 _5
6
+ D, _; q  m1 j1 s9 E7
: r: b  q' v1 g/ ]! m! B8
( G# _- J' W. a- W, A  [9 F9
10
11
12
13
2 B0 b  E& o1 C( }14
0 u' q6 N# i' ~) }15
16
17
' t0 U7 [6 K  `; B+ p18
19
20
" A$ X7 A9 I* U- T21
22
23
; m. {7 ?/ @9 I6 D: @24
  L" q. P7 \2 ~, n1 x! y25
  h7 l! ~, m8 h, X7 W) X26
# q# M- z4 B1 F( {6 f- ?. o27
4 h) o6 E* G" s28
29
30
31
6 `) p1 L1 W1 U/ a' i+ I0 |  G32
33
, L" d) I! n' L& ]$ z34
! _' Z8 t/ i* h9 W' N4 j35
4 g# Y' m8 E8 H  t36
) w3 c9 p# T8 D+ R) v37
6 l6 K0 _) A' B& W1 e2 P7 x运行截图：

* M3 _/ K9 m  ~  \
, }4 q/ a6 {. O1 h3 n方法二：将最小元素交换到待排序列的第一个位置
6 K2 ~. ?* M/ `" I$ o8 F
/ O3 @6 v+ M0 |; _) p3 x' P. V#include "stdio.h"
& h. W# ?; [0 ]4 ^' `; K
$ l" w8 q) o* `/ ?- mtypedef int ElemType;
# T) v5 l% P: Z* H9 b& m; W
. A8 n$ i) n2 t' e& Z# O8 cvoid BubbleSort(ElemType a[],int n){
0 O% L* {7 {3 r$ H    bool flag;
' N# y( f9 R# T7 d, |, p5 q) c    for (int i = 0; i < n-1; ++i) {
        flag= false;
        for (int j = n-1; j >i; --j) {
5 ^& T: B7 U6 I' o+ r& e( C3 }            if (a[j-1]>a[j]){
                int temp=a[j];
                a[j]=a[j-1];
+ x, g9 Q. u9 I                a[j-1]=temp;
                flag=true;
4 m0 Q; e+ M2 q6 N$ z7 P& C            }
: O% U  N, d5 Q( D2 }2 L# [        }
9 V: O) H% O* }% j* H) d        if (!flag)
3 t/ q2 V- @: [3 ^            return;
    }
}


& O0 v. s2 m2 C' ~" S' ?* dint main(){
2 l0 O/ W: W4 k% E( ~5 E8 x    int n;
: v/ Z0 H' c3 y+ i    ElemType a[n];
    printf("一共有多少个数需要排序：");
4 n2 A, S" M- V7 g/ u8 ^    scanf("%d",&n);
# i7 f, X  ?5 O    printf("请输入%d个数：",n);
1 A8 `9 Y- d. c2 \; X' y% A    for (int i = 0; i < n; ++i) {
# l. _* N! N6 }$ U  l        scanf("%d",&a);
    }
; I( X$ f+ w( V, L! ^8 n$ X    printf("排序后为：");
    BubbleSort(a,n);
: O8 _' h8 E/ e/ D- J8 B    for (int i = 0; i < n; ++i) {
1 n" O* l1 X2 B; k        printf("%d\t",a);
    }
}

9 F4 s; U9 U/ A: H8 V+ ?* c1
' g" g9 `  k5 R3 L2
3
$ {% W) T$ y- g4
5
6
- Q. a2 }) \1 X( J1 ]+ M# ?7
4 [* l' j  G3 [# W+ }8
! }& N% Q1 P" _( [; q. r) [5 Y- z9
10
11
. f! o  K" O2 F) G12
4 |+ R: c( P" [$ H& d8 b4 K: T13
' \  j0 t; Y5 s* Z' B. v: B4 Q14
( K4 z9 w5 Y9 }6 A2 _4 d15
3 X0 x& @% `1 B5 b3 {) I16
17
* w, E& f, v0 w: h+ I+ C& Z18
19
20
21
22
( F9 y. g3 {& K2 L4 o3 H23
; A' p4 ^  m+ V2 C24
25
( l# h4 Q7 z/ g% q. _# L) r+ N, L9 ?26
27
- o7 q" x9 ?/ Z  P# K8 t  I4 C/ L28
29
30
31
- J# o: L# \4 j( `% a; H: f' g32
33
34
35
4 @; N9 s% b8 e; b  N36
# h4 u% T+ U1 N" z- E37
4 t- T4 N- F7 Z* w: o运行截图：
. @) a# j7 R0 @
  d+ C: l. {. o+ t+ j
* m7 v# @9 f% _2 D( ~9 {' o性能

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

时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
% z0 P( s# ?, {8 p- K2
)；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
)；
. i% @% R' y& M% [1 Q
稳定性： 稳定
" \8 B5 B' V" H: A
适用性: 适用于线性表为顺序存储和链式存储。

6 ~, p# y# `1 B3 F; a6 G* a- v( x2.2 快速排序
图解（动图以后再补）
第一趟的排序：

' ~1 O7 x- t$ ^4 S! \第二趟：

3 r7 p# P) |/ O  r3 a7 U第三趟：
- Z( p" c9 ~) k# T' e! G

3 V5 |' i% l# {2 t! g% D  g基本思想

快速排序的基本思想是基于分治法的:
* s$ _+ @# B4 J  |7 D8 i8 v7 E: N3 `
在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
7 Z4 K7 R( j$ q& \  o然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
代码
7 A( f* p6 X) x/ |' N. G
* a, e8 M* \* u& ?) [" J' H3 G#include "stdio.h"

! p8 d- n  r7 K8 y6 [# xtypedef int ElemType;
, a& b( @" N& j6 Q
int Partition(ElemType a[],int low,int high){
- @' J0 B; B) Y3 X    ElemType pivot=a[low];
    while(low<high){
( |; b+ }% `& I$ G- C4 U& g0 R        while (low<high&&a[high]>=pivot)--high;
- R# V# W4 y5 C        a[low]=a[high];
        while (low<high&&a[low]<=pivot) ++low;
& b* A* E7 s7 F# x+ s- ?        a[high]=a[low];
    }
    a[low]=pivot;
! f  D. d8 K# T7 w, W    return low;
}

void QuickSort(ElemType a[],int low,int high){
0 z8 C- v; O6 Z& F9 B    bool flag;
    if (low<high){
5 E$ J/ i" b/ {! F2 h        int pivotpos=Partition(a,low,high);
; P/ Y0 |4 f2 ^+ c        QuickSort(a,low,pivotpos-1);
, n8 `5 H2 ~& z/ O( p1 s        QuickSort(a,pivotpos+1,high);
    }
}
/ s2 [; z2 {4 N9 H
int main(){
- m$ i+ B$ f/ W7 O- C2 q5 ?' C    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
% w# N: y8 S+ u+ g: w& j9 |    scanf("%d",&n);
: F) p% w( ~& m; M6 P, B    printf("请输入%d个数：",n);
( ^; Z4 Q7 m8 R7 R    for (int i = 0; i < n; ++i) {
- {! `4 e! @( y: ~, X        scanf("%d",&a);
    }
9 u  `4 J$ G7 {  b" Y  d    printf("排序后为：");
! u% Q. `$ x1 P& Z" Y    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
8 B( {( I: N, A  y& ^7 {" D0 B        printf("%d  ",a);
    }
* B: Q# f* }, ~}

6 |" r  N+ n6 R$ D/ Q
1
2
; \* h5 A, _) z) H3
1 ^5 l0 p; F# o5 o4
6 f0 L5 i/ Q; K1 S0 P7 ^7 Q; o) y5
+ J% `/ X8 w& y6
7
8
+ n* s% l8 k$ @/ f+ d' G; H6 U9
. M8 o, U: u) k& L% }# O! l, E10
11
; n" V6 B# a$ _6 l12
13
2 v/ B; `+ Z, T: T2 G" o! S' G14
" B; k( g! f5 X, d2 i* l$ H15
16
17
18
: d. q5 b+ T' O2 I( J( p! A* b19
7 X: m* f6 ~  I% r5 _/ T% o20
" X4 t% H8 |' g- B: ~4 i  Z7 T0 H. |21
! }' N8 {& C5 q) W22
: m+ T3 h; J. V' Q% q, r$ j23
24
0 I  d* L4 N6 k6 |$ N. W25
# ~+ ?9 N+ G* p26
+ [) R% u4 m: I: E! I7 R0 X; y27
28
29
30
31
! A3 `2 i2 Q/ y9 g0 B3 \32
/ o6 N( i% D( k$ A- L9 m- g, Q33
34
- E  `; p3 r9 y0 [4 k' a35
36
37
9 g! ~9 |. ?& w* z: q38
6 O, S$ ^& A  r3 `) h: x) s39
' Q& q5 u3 u+ I& X' n5 s40
* H# i8 o& R  i+ n41
性能

时间复杂度和空间复杂度
' v9 Y& @; r) a+ Y# X稳定性：不稳定

3. 选择排序
+ B2 }. p! T  g9 C2 {3.1 简单选择排序
, p7 ^' ~# C- ]2 g# O图解
7 |1 `* K9 S0 X  o& k. d% y# x5 H
* ^, f; e' H: e% }
基本思想

在a[0…n-1]中，将a[0]设为最小元素，设min=0
0 D5 r- m4 Y( M) C在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
0 R, {" |5 ^/ x! ]6 e! R若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
在a[1…n-1]中继续进行排序。
代码

& ~! h* w3 m9 r8 `2 \#include "stdio.h"

typedef int ElemType;

void SelectSort(ElemType a[],int n){
    for (int i = 0; i < n-1; ++i) {
        int min=i;
        for (int j = i+1; j < n; ++j)
            if (a[j]<a[min])
                min=j;
        if (min!=i){
            int temp=a[min];
: J, v) o/ E6 I1 x  d5 X            a[min]=a;
            a=temp;
        }
, ]" Z2 M2 \. ^# C$ a' o& T    }
}

" j' Z1 `; l; X* \2 i7 cint main(){
' s- ~2 `0 l% U    int n;
  L$ B- C: @- ?5 q    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
; k3 G9 ~4 i5 Z  [) t0 E3 _/ G' h    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    SelectSort(a,n);
/ G% t, f) _+ U& ?4 u! A0 h! q$ N    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
7 n* z9 ]! x) k$ {        printf("%d  ",a);
& M7 D1 b6 m) K! R  `" q    }
7 T& _6 y6 S& l$ J4 j! }}

$ N* p' G3 H& ]3 a1
8 s7 P' b- H8 z/ {2
8 D% `7 ?' q% M8 B8 Y, C3
& Q. _6 x( g. U" ~- n7 m' \4
& `; G) n9 E* I6 c2 U! J5
6
7
  S1 o1 M' u( I0 m0 L$ I8
9
10
2 V# d$ u- W8 s11
0 f4 u9 x( ~, Q+ F12
; c) w2 u& G6 Y; L13
. Q9 R1 ~7 k+ {( ~14
15
9 a9 O4 o! a! r: _! E3 Z16
17
18
# {9 N5 `" X3 t( J! ]- J: o19
9 s6 B# b# c  u7 R* V- ~. D+ g20
21
22
# _( H) d, ~4 P5 J. C0 I8 K$ E23
0 g, Y* t6 V" b: H9 ^24
25
26
27
28
( d( j. K6 c' _9 r/ R. X29
30
31
/ {5 k1 M4 x) @! c# g: a32
33
$ ]9 N, q. d4 I, ]; b" G性能
+ [1 P4 r$ O5 {8 f
空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
2
) C% I* }+ m2 ~% i )
稳定性： 不稳定

使用性：顺序表和链表都适用。
' P# k4 D% h3 y
3.2 堆排序
0 J2 p; ~7 Q! |看堆排序的点击这里！！！！

4. 归并排序和基数排序
4.1 归并排序
图解
" I& v, J2 g, Y4 o2路归并排序


6 r9 P6 g% Z, P2 Y基本思想

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

然后将子表再次进行归并，直到子表的长度=待排序表的长度。
) w% G) X: }" Q- f+ S$ p" `, E0 B# K代码

#include "stdio.h"
9 X  O) O6 w, P, m' z2 \#include "stdlib.h"
6 Q8 B# A6 M3 F% I% {. N) L
; L* E/ x9 w( F9 T5 Etypedef int ElemType;
9 y) X7 N$ ]' J% N! i
2 h' r* S# v5 [ElemType *b;
5 A( f0 R( _2 \: S7 h# g
! Q; F; \/ G; G+ J5 _. kvoid Merge(ElemType a[],int low,int mid,int high){
! o3 s' n9 L: X8 l    int i,j,k;
" z5 ]0 Y1 V6 [    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++];
        else a[k]=b[j++];
    }
    while (i<=mid) a[k++]=b[i++];
    while (j<=high) a[k++]=b[j++];
7 q# c9 l3 ~9 O}

! t# ?/ J* N$ B, P4 ~/ o6 E5 Avoid MergeSort(ElemType a[],int low,int high){
& Z0 t( U1 w2 K, o    if(low<high){
        int mid=(low+high)/2;
        MergeSort(a,low,mid);
# F1 l# J" e" b, m8 W        MergeSort(a,mid+1,high);
$ R7 J  E2 l1 }6 _) j1 ]        Merge(a,low,mid,high);
1 @; E) p, \" J" P$ L0 ^9 g    }
}
) Q/ f* c3 S9 ^8 A+ T, A+ \% ]
int main(){
    int n;
    ElemType a[n];
    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
* j5 j$ ~" v0 I5 ?( V0 ?    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
5 V4 B9 v3 z" `    for (int i = 0; i < n; ++i) {
+ x- M, l$ \8 i        scanf("%d",&a);
; T$ G5 t) L: c4 C    }
- \, F. d5 j9 t! K. N0 T    MergeSort(a,0,n-1);
+ ]" l. w' m2 z! t    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
6 P* y) f; C! _- T    }
}

  C' U- ~+ y* _0 x
" q8 {1 ]7 e! s! ~1
2
3
4
8 E7 a8 }" M3 C7 z- ?5 a" m5
6
+ ]& P$ Y. `% F0 f7
! u, w% L6 G, o' J8
9
/ @( Q$ V8 H9 ]. H6 W( b) e6 \10
11
12
$ j. P- H' p- ?3 s13
) x- i( E: G: R" r* B, K14
% Y+ U2 o" M; P" k& b, q15
- R! y1 E# ^8 v16
. Y: F& S7 T9 R4 i; Z17
18
19
* ~9 J; h- r. z4 r9 ~20
21
9 z8 I6 O" L$ Q  H2 Y22
4 m/ V2 N" ~4 M* m6 @/ g4 g' g23
24
25
4 e  `. Q8 f# P: }4 {8 j5 z26
27
& D9 Q: j- F4 |6 Z) p4 K/ a# V# Q28
29
30
31
32
2 y% C6 K/ i! d" h2 q33
34
( d) |/ L, Z; v1 b0 \7 q( _35
36
37
  `6 e# C4 t9 @3 u0 z6 x38
* [: Z; p+ b& ~! E" G. b39
; p2 y. \& c! }40
1 ^/ U) A6 B* P41
42
. ]" g7 H! f; H: B9 V" k! i. y' f43
& }: C! M6 b* M6 ]9 `44
! y2 B- D9 N1 H7 u$ H2 H45
46
2 t9 z8 s3 T3 I) m性能

空间效率：O ( n ) O(n)O(n)      创建了一个数组b
* x5 [2 S9 O% ?! T$ P! |; p; r时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
​
7 C" j7 z/ K5 X& V+ Y5 [) B4 Z. N n)  k指k路归并排序。
稳定性：稳定

4.2 基数排序
# L' G" X+ T$ N" K. m图解
$ k) ?; X- G* Q4 y& G" b4 Z- X

* Q1 m: ]( }" I5 `4 r基本思想
, f4 E% y3 S7 {' z8 i4 w
6 X7 ~; x( p! Y1 G2 l4 C8 S) p3 \将各个位数（个位、十位、百位…）进行对比。
& i3 p/ u- V0 d7 H7 B为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。

) F/ ~8 b  _$ X  r/ |7 p& A! d性能
: h1 g4 T# p7 Q: T  ^
空间复杂度
* `% d9 g( _7 K. _9 G1 N
1 N: j: J9 ?) _  T, I/ c时间复杂度
8 V0 O! c3 r* B$ A8 ]* L4 b, B

& k  D/ E9 G! w% M1 k2 _稳定性：稳定

5. 内部排序算法比较及应用
5.1 整体比较

. ~$ `) |% V+ d: ]4 i
5.2 时间、空间和稳定性
+ I) U: `  d) c# ?% s& D" {, K3 z

参考资料
, s9 S- _) m7 H& O$ a+ t: ]+ q《王道：23数据结构考研复习资料》
————————————————
版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678
$ Z2 {3 C6 E) X, B& y  S

# U. R2 t7 l) |+ h- a