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

杨利霞

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

排序
1. 插入排序
1.1 直接插入排序
1.2 折半插入排序
1.3 希尔排序
0 `) ~1 t4 Z. M% E! l0 b2. 交换排序
2.1 冒泡排序
2.2 快速排序
3. 选择排序
3.1 简单选择排序
3.2 堆排序
- L" u2 @; H8 F$ y4. 归并排序和基数排序
& e0 K2 }- `0 I6 L& c0 _4.1 归并排序
% x, a3 {' Z5 J# w$ E/ ]4.2 基数排序
" b$ v9 ^- N/ K: J5. 内部排序算法比较及应用
5.1 整体比较
5.2 时间、空间和稳定性
" ]9 j: W( M, A! D4 ]' s参考资料

# B9 d8 Y1 }  d$ B内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
) Y- O" }" o. G  q, l. v5 M1. 插入排序
1.1 直接插入排序
* i+ L% o: M# D0 F图解
4 i" A, z; o) b5 n- `) Y3 j
5 Q0 C' z* E. C5 y8 ?, l
3 O: h( {# b7 I  P1 z4 H基本思想

$ `* G+ ~4 D# E+ V8 H1. 查找a元素在第1 ~ i-1中的位置k
2. 将k ~ i-1位置上的所有元素向后移动一个位置
! C7 D& b2 g2 v+ k  B- ?3. 将a复制到a[k]

: K1 v+ X+ }. U/ d) h/ a
! Q$ ^' ^7 f: @) X9 `$ ^
# x: p& l: T" Q- a代码
" o6 _/ o/ d- V" |7 a# Z5 s
& k& C: v2 Q7 j3 Q方法一：

) t. M9 F7 P( F, F数组的下标从0开始，如上图。
( l3 p$ h' d- ^# |
2 U' e# w0 y( L5 Z#include "stdio.h"

7 p( R& g1 G  u3 Y- r/ p4 k- Dtypedef int ElemType;
& B2 C6 [2 L9 s/ ~5 F0 l* s
void Insert(ElemType a[],int n){
7 p* H, A  u9 t$ y: R6 |0 b1 \$ ^    ElemType temp;
    int j;
    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
' V5 ?, O& l, M0 L8 p( e, j        if (a<a[i-1]){
            temp=a;                                                               
# V( ]$ ?6 S* v7 V            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
                a[j+1]=a[j];
            a[j+1]=temp;                                                       
4 U4 Q6 u& e" z/ ]* }        }
    }
2 I* w# f) T: V0 e}

int main(){
    int n;
" ^$ ^6 ~! ~3 I0 ]/ g2 w    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
$ G& I  o" B: t# U9 k# J        scanf("%d",&a);
    }
( B* ^7 |7 }5 \; S3 V& e    Insert(a,n);
2 o6 l4 b' ]# r: l) G$ d    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
4 D& r9 N% t8 m' p8 o7 [" I1 }" n    }
) k' j  T2 G0 U) S4 w5 g) h}
  u3 [" U6 m# D4 E$ k
1
2
3
+ }0 C0 v" ^' y2 k0 t( r& w  L& T4
5
/ F1 D) U5 k& ^8 D8 |6
6 g9 O, j, Y( Q4 k9 Y3 `' [" K7
8
* K  m% e" P% d% V9
10
11
, K& e) `: G  b. m12
13
14
15
16
17
18
19
7 F  r# E: {; i1 A20
0 b8 ~7 W2 ^4 N21
4 \2 e+ M* s3 T2 S- O: u# a22
23
4 f! O2 C. O) |0 A) r24
* {* X$ Y$ T3 g; G7 p, o- h" U4 J25
# M4 z5 _! h* B2 I8 j5 c! I26
27
* t  e$ P  N/ k# u" B4 d$ o28
29
30
8 U. m3 T  h! R31
  O+ B$ w* E! N9 J$ ~32
( q% Z1 M  a7 r, r方法二：


/ V3 V/ g. E( G$ `! N' l
#include "stdio.h"

4 H2 u4 U9 A0 ^% C( [* q' ?typedef int ElemType;

: O' `. g- M6 Q7 nvoid InsertSort(ElemType a[],int n){      
    int i,j;
. t* t8 H, U1 x1 D    for (i = 2; i <=n; i++) {
        if (a<a[i-1]){
            a[0]=a;
            for (j = i-1; a[0]<a[j]; --j)
+ x: w6 ~/ n4 X9 O5 {; ^                a[j+1]=a[j];
# x# w0 z, w  u8 S0 `$ O" W6 P            a[j+1]=a[0];
" K" h/ t8 [) J        }
    }
}
5 D/ d* p, M$ B+ S' kint main(){
    int n;
9 `$ ~& o: H5 }  Z    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
  h6 s, V2 @0 b, t  F* x    printf("请输入%d个数：",n);
. y! W! z6 l; j4 [, m7 ^  R' h7 _    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
    InsertSort(a,n);
    printf("排序后为：");
# P& S+ B" Y8 N/ h% ]) e1 d    for (int i = 1; i <= n; ++i) {
5 W8 {: b$ n+ h        printf("%d\t",a);
$ ]$ S- o5 |0 e    }
! {. L) M2 w: O}
$ I) }6 z4 D/ Z4 H9 k
: q, |% t) V$ s4 {2 o4 q1
5 m: w3 \; o0 k/ c, }# u2
3
4
4 j7 r! S* V; y2 }5
# f! `' K: ~3 W! ]6
7
0 f# u, Z8 q5 @4 W8
9
& [4 {/ }/ t. g5 P10
  v# d8 o1 g/ ?, N/ o# ]11
12
+ d5 M8 c; E5 k+ y" Z13
14
: V( |& q) N: E8 y" G) q6 ]15
16
9 d; H" t9 h) t17
18
( b; p4 I& F( G- s) P19
/ ^6 p. C, ~* ~+ H& ^20
, }4 }7 |! [/ G4 F) z6 D21
& L+ M' S$ N8 J3 e4 }8 D2 O22
& @$ H) m1 J& z' [/ j0 n/ s) Z; h23
24
25
4 H1 A+ [! Q; s) }: J3 ]26
4 s) y% m. s5 k9 e% V* w# |5 P27
" k6 ~# S4 U# d28
) ?/ I1 |/ g% c4 Z% l29
30
8 J7 g% Z: q, u  y4 ~/ U" ^算法性能

空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)
1 l/ @- ?9 m' }, l: k- H
时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
% C8 Q8 R$ x! b2
4 m7 H' U' w! t* z  V* c% P. S )

. a8 f' t8 w. B; v3 D
# {6 x9 C! q: Q( s稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

4 F1 K9 g% u- |: E适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

3 \3 J' D- _3 N+ B1 ^1.2 折半插入排序
图解
第一趟：
- r5 P% `% O% u( {1 a3 w( m  ?9 c
0 R; b' {5 h& D" U/ _  L第二趟：
7 A! \4 t: s! ]" g: X4 J* c

3 m3 y7 ~: g8 b* U5 e第三趟：
$ {. g% i$ l* g& ?
第四趟：略
  U% {  {# x/ ^第五趟：略
8 J& {& L6 k2 T  s! z5 v$ a5 Z
/ N! G8 X) F' C$ `: Y* a" \5 I基本思想

: i! `. J) x8 ^! G# h, q与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
8 C6 V& ~8 n; W. V* e找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
# z  B6 r; f/ P& L8 d- |6 u代码
3 X7 ~0 F, g& W- A
2 M& U" a6 }& i( _  H#include "stdio.h"
: W- U/ d4 O% v0 A+ O% H- G
& d& c( @* N2 v: X9 B$ g( Rtypedef int ElemType;

4 |# r+ z; R# f! U% `3 J* avoid InsertSort(ElemType a[],int n){
2 a" t6 l9 g: Y' v; L  t    int low,hight,mid;
    for (int i = 2; i <= n; ++i) {
        a[0]=a;
        low=1;hight=i-1;
        while (low<=hight){
$ b! k* H* z3 S# w            mid=(low+hight)/2;
            if (a[mid]>a[0])hight=mid-1;
            else low=mid+1;
. m& o; ^) g2 J8 r        }
        for (int j = i-1; j >= hight+1 ; --j)
4 O) {! H6 D3 S) k5 J            a[j+1]=a[j];
8 ?7 u$ m. [7 t        a[hight+1]=a[0];
9 Q; u9 s  m; j3 r% T2 M! R    }
* T% v+ M  V  U! D2 H3 U3 H& H/ G2 `}

+ x4 c) n" c3 f0 J, c$ F- c% \" n
int main(){
: a0 O2 u3 y# [  M1 V: }* E    int n;
    ElemType a[n];
7 h/ ?( z/ }2 ~    printf("一共有多少个数需要排序：");
  e/ Z" S9 a! c& B) z& r7 y    scanf("%d",&n);
    printf("请输入%d个数：",n);
. k5 {& M: Z7 Y" e* k    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
2 O/ H" [$ W* B. j. n" g, o+ h    printf("排序后为：");
    InsertSort(a,n);
2 l; X2 L) [; W4 t& N5 v% y
+ U/ V8 M* X% `' |3 k    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
3 C; v8 r  k% f/ {9 T    }
}
* {5 G% S0 u% g$ T% U
" |/ c  c5 y4 A7 p# K, c1
9 E) k3 d) N# g) c# w2
3 r4 V" N3 i% Z6 D) A, S3 p/ V2 n) C$ ?6 o3
% A$ ^) _& {+ _- N- F3 E$ v0 i4
  M" z1 e+ \" N: m! D5
6
7
8
& V7 J/ r5 \& I- d/ a7 z6 m9
2 F, M! Q$ _8 D3 Q5 e9 ~( ~10
11
12
" w: x* x7 c. m3 i13
14
8 w' F2 g; _% f8 M: o& ^15
* j, b# n! q( e% ~+ ~/ e16
17
. w/ V) Z* S% a/ _18
( i8 s  _- ~$ V! P% t+ o19
20
; a* A* z8 i% Y7 |21
$ S  F9 H+ e. J! n) o22
23
24
+ @5 F0 ?6 `1 a+ ?& _0 `& R% a25
$ w; p& H0 b+ c5 V$ v) r26
+ Y/ F# b2 L( S# Z% p27
28
- G' n& R: A9 R) E1 W29
30
31
32
9 b+ o" H5 `/ P  G9 {33
5 n7 ^" J. p0 g& W34
35
; @, y! o3 H: v* I36
37
$ R5 ?* j4 E% w$ K: F' ]$ d4 y: b性能

空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
, ~% `0 r$ A7 K4 ]$ e2
" y5 `$ h, J' f% s )
稳定性：稳定
适用性：仅适用于顺序表
/ @( b+ X& q0 `9 E; B: k
1.3 希尔排序
3 h/ a% L# S0 |, u+ {( k图解(动图)
8 M  _) x* }6 ~3 v
; _2 C5 n0 e+ w% g. k& f4 q
+ w& C9 E( N( ^基本思想

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

代码

/ J1 @  h0 Z% J. X/ F% ?1 o8 s9 S#include "stdio.h"
$ G8 m; B" K8 K2 u; |
1 t. M) q% O) U/ v$ e' t+ ]- B) o- gtypedef int ElemType;

void ShellSort(ElemType a[],int n){
# A. w4 g0 j; [; M+ d* i& R) R    int j;
( O$ W$ z4 W$ g, ~    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]){
% ?! K2 z0 Z. Q. z6 r0 ~% q                a[0]=a;
8 d  I6 h, ]+ r, w! r                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
* c  D- }# D# b* X, R0 e; W7 `                    a[j+dk]=a[j];
                a[j+dk]=a[0];
            }
        }
% I& N0 u% ?, l* \1 V" M    }
8 ~6 ^7 U# r% P3 ]( m}

int main(){
" N5 b( f( v9 b* }    int n;
! y8 t5 y4 g7 e; Q, C  q, e    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
+ K1 J; e6 W) j5 c- n2 o6 M" \    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
* p8 @7 |( n" v- V  z# i/ N        scanf("%d",&a);
, S: i; J. y  ^0 q- l7 F    }
+ V, e/ i: T2 p$ G    printf("排序后为：");
    ShellSort(a,n);
5 Y7 l( `3 Y( Q$ R  I
0 k2 m  K+ E9 r& F. n    for (int i = 1; i <= n; ++i) {
5 i- ?; Y3 e, X- _3 m0 e        printf("%d\t",a);
    }
( h- {4 J  {" x/ C- {0 X}
9 z4 W  ~8 N0 l9 q$ Y. b/ ]
% s2 i! Y, o; n" X& _- Q* c6 H- A1
1 N2 m3 N0 {! b( J1 {2
3
4
! c4 ~! ^, _& ]: [) C) z5
6
  {1 G, d1 K. A  h7
6 G/ g& Q& u; z2 v2 r8
3 Q% ^6 m$ O& p. F7 M& D" y9
6 z  i, H  j, `10
4 S( Q! o; P7 |* ~  Y: I11
12
% Q8 J; k# z; K- m9 \13
14
15
16
17
18
19
- Y+ O2 i% L( e& U20
6 V6 g% H: _3 P' G9 ~) o# A21
22
% O4 l6 F2 ]/ k& m1 O23
24
25
26
27
28
: o0 a$ z; Z+ p29
30
% y$ S& b0 s- }2 T+ p31
; j/ G0 x# c+ m6 A; n32
33
& B; [0 V+ g+ c" n34
性能
& W: P  o8 Q2 V! n
空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
! o7 E3 O7 C3 [( `3 Q% J1.3
1 Z7 X& C" w8 R% }. Q7 r/ W8 Y7 S )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
, \2 d8 L! X4 A4 U$ O9 O2
)

, v& {. ]8 W& G稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
  o  N, [3 \5 x

适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。

2. 交换排序
( N  h- R* N4 ~6 Z; T2 B2.1 冒泡排序
' [8 ]- a1 K& G$ F5 U图解

0 V0 \, b) g  z9 U5 c( A
基本思想

从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。
& p! a+ }3 n0 W
代码

方法一：将最大元素交换到待排序列的最后一个位置

( X% Z1 {# ^  U6 Y. [' z5 x#include "stdio.h"
" [. F* f( T+ w' T1 O
typedef int ElemType;

void BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
- H! L; k" I8 N' E        flag= false;
        for (int j = 0; j < n-i-1; ++j) {
            if (a[j]>a[j+1]){
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
' l0 m4 Q9 j; F1 G3 }8 |* H                flag=true;
0 f+ Q: p4 ]# t$ q: _, O            }
        }
& M; f- n, Z; y% ]% }        if (!flag)
; ^- s. @" u3 l( S- f            return;
+ Z9 F" q" p; ?. j% s. D! h; Z    }
1 Z! {' \9 M) E0 r) a5 y  u}

) L9 M& c+ p% y0 L% d
, r. ?' w7 w- x, t( Q: b+ X5 cint main(){
    int n;
    ElemType a[n];
* o/ B6 ]9 h" ]; g7 q0 j    printf("一共有多少个数需要排序：");
1 H. F6 V4 D- M0 r1 V1 t* T. Z$ s    scanf("%d",&n);
    printf("请输入%d个数：",n);
5 o5 K9 N0 B7 `+ t5 y    for (int i = 0; i < n; ++i) {
: m9 ]7 f; [/ ]        scanf("%d",&a);
& H8 j7 p9 V+ M. Y) E* K    }
    printf("排序后为：");
' U) J0 j6 G* I9 x    BubbleSort(a,n);
% j+ A$ s9 P$ `1 x8 @    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
}

1
2
5 f& f# I+ V8 P- F% I6 `1 V; M3
4
5
7 f- K" h8 G  h+ P& L& d6
7
8
9
10
11
12
13
14
15
' s( T; `& n( {- o: k) p16
# a5 c5 R" x1 _/ [" ~1 r0 Y17
18
# Q1 ~& m9 n3 }7 ^, v19
20
' ?$ |' U4 s6 n3 b8 X3 r' h21
22
23
24
25
26
27
28
$ p/ `; s( J* `$ n29
30
31
- [( S, z0 X2 P5 F3 I9 x32
. @8 X0 {7 X7 V+ q' A  S33
+ ]# A+ v) a9 v' }. e% I34
35
# V( i% {6 c' J" l/ F; h- w36
9 T: D% U4 s5 ?+ O% e! G; T: Z37
运行截图：


方法二：将最小元素交换到待排序列的第一个位置
& C$ I; s* x; m  r3 b* ~5 W
#include "stdio.h"
$ j! _* Z7 i& P. Z: R
typedef int ElemType;
3 D7 x: c. S3 W1 O
- q+ r4 S  T) K" @void BubbleSort(ElemType a[],int n){
/ P6 E& n; E: m2 d    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]){
2 M0 j) H* |( d5 V                int temp=a[j];
" H/ [" K5 N& y                a[j]=a[j-1];
                a[j-1]=temp;
8 [2 ?" Q2 h% D                flag=true;
            }
0 O6 Y2 h3 b' K* M        }
1 X: j4 G" R$ Y  x        if (!flag)
            return;
2 L5 T8 Q. K; X: }0 d    }
}
# E! T: \- X- i0 d6 B& j
$ e/ b6 O7 b$ A' m# F( B; B
5 |6 M, d7 ~% {% V) u0 |int main(){
    int n;
    ElemType a[n];
9 k- Z6 ?+ C) H& v# c1 S    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
0 a$ I* Z7 |- e# A: a( h    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
}
3 q; l  Q* Y* `0 _
! v5 I9 I; z. g1
- V+ L* D. v5 H: [; G2
% Y- k& e! e  o0 A3
4
5
( W1 \" @1 L. l4 Z6
7
8
9
10
* i# i+ z3 V: C, I* v11
12
) _: @2 U2 r0 I13
14
0 K5 U5 j6 Z1 o$ k15
16
% J( c6 s# k3 q, l7 Y9 ]  ]' y17
& i3 w% |  H! R: o18
! t$ i9 m7 X$ Y6 Z1 a8 r8 k19
1 [0 m" u3 z8 \, U- y) H20
  ?8 \4 [- b9 ?- J% o* C  A. l$ o21
22
1 f, @" B3 ?- X7 j" [  P, A23
24
25
26
& Q$ }0 `3 ~5 T' k; y27
* B1 w7 H, i( u, B, E5 m28
29
- t+ O: n$ i% Q6 A30
31
32
) X$ ^( q9 e, h' M33
0 b2 k; _7 A; y# o4 u% b34
: W) a; p. \) g35
" V$ I$ _$ w: q2 E& m36
37
运行截图：


性能
; P3 K- X; d" g; J
" T" x! C( a) b9 e空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

3 X  O) c: n, t. [! A. w& @时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
2
)；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
)；
: P+ g7 j4 C' x: D) e
; g) M6 D1 j5 }; `4 P5 }" N稳定性： 稳定

4 `/ B0 _& ?4 U2 H4 [. h适用性: 适用于线性表为顺序存储和链式存储。

3 d! P5 L. V0 ^; H2.2 快速排序
  H! x$ X* l/ {& I, l# y. h图解（动图以后再补）
0 x2 m8 U2 v& D) ~& d+ u' V第一趟的排序：
8 O6 v% U4 z2 m
7 J" C- D6 N8 c, U/ S第二趟：

第三趟：

9 {" X3 |. m) f3 ?! Y' @
基本思想
3 r- ~; V) T. a7 w5 X5 h$ d& P9 L
& q; [; A; t2 Z快速排序的基本思想是基于分治法的:
; t: k% y% P% }
0 a  |- Q5 f$ a* ^. w在数组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步骤排序。直至所有元素排序完成。
代码

  L' ?- _! W- P7 b5 d. ?#include "stdio.h"
; _/ e) Y: s6 P1 \- C
3 c+ m; X; X1 S4 qtypedef int ElemType;
7 {% K3 G* W4 n, c" K2 K  @& C
4 O- ]7 X; y5 V. X, `6 Hint Partition(ElemType a[],int low,int high){
    ElemType pivot=a[low];
    while(low<high){
        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
        while (low<high&&a[low]<=pivot) ++low;
        a[high]=a[low];
    }
    a[low]=pivot;
    return low;
}
) E" |& l6 _! p7 e1 P0 ~( ]
3 M( y8 P( x# I, Z& e; z' Xvoid QuickSort(ElemType a[],int low,int high){
, t3 R6 C% X! A4 Z4 ?% T    bool flag;
6 _% y+ }& Q) d' H3 w    if (low<high){
* i: g# R0 C0 r8 q) a  c' b        int pivotpos=Partition(a,low,high);
3 L& f3 ^$ j* n+ P1 g        QuickSort(a,low,pivotpos-1);
1 d) O8 s0 e9 Y  s% e8 a) f- \        QuickSort(a,pivotpos+1,high);
    }
8 u+ O+ l2 W6 K: }9 c' u8 G; s}

2 t0 \5 q3 u" h9 Z/ yint main(){
  |" L0 E7 {( w4 i    int n;
    ElemType a[n];
! T; t8 q& f; b& X# h. Z4 s    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
$ V# h* i0 t, C2 \, }    for (int i = 0; i < n; ++i) {
' l6 X/ J7 z6 s        scanf("%d",&a);
5 O0 K2 k! D( w, k    }
    printf("排序后为：");
% o1 S7 W2 o0 Y& u- q    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
: {! c/ i% w. W+ i$ O/ u}

% m. s1 A( u0 V
! P& o4 v4 w2 t" Y* t' Y+ C1
& o: e5 c2 c9 Z8 w* F2
3
. R/ S# f+ r. E' o0 U9 J4 I4
5
4 B' U& p7 X5 N/ R* [" @: W& J6
7
5 |% c( J/ h. M: ~8 e8
9
10
1 e. C# z% I( O  W& ~11
; H/ ]0 h( n6 ]. A4 _/ c8 E3 p12
3 Z% y- n4 x& A13
# \4 ?; O, O/ G' y14
/ x2 l( N4 a# d15
- a4 a* E7 k; A& b, }8 p16
17
$ A: h2 `2 }$ S! x18
5 h9 N* B5 R" d$ e9 m6 e9 r# u19
  s: P6 t* p3 x6 c- f. f20
" a% m9 J3 e& U5 m- q! P8 H- C21
22
$ w5 U* f/ c9 G* f: {  u23
24
3 b+ j! K& `" P5 g# E25
26
27
3 U0 \5 g, ~1 N$ b6 H/ i; Q28
, z  W+ J( _- d5 i8 {, q29
+ f5 K4 c  H; e6 k8 h30
31
- F' k0 i5 n! w2 ]3 t+ b: j32
33
+ X4 {5 e! {: u5 c7 c34
0 I2 G+ J, a& x% Q( j35
3 j, h9 I$ r5 Q/ o36
* O1 h& w+ O" A% W0 F37
! _6 }% v1 b4 u38
8 g0 h( a* Y; b, ~9 ]39
7 F& X1 W& k* Q9 j40
41
2 v6 F! D/ W6 H1 C+ e" I性能
/ A) b+ v+ v$ k. v& S) V2 B
( t# X8 \$ m; l% O, y  C时间复杂度和空间复杂度
稳定性：不稳定

3. 选择排序
; V; \+ I! S7 U5 M& F- t4 B3.1 简单选择排序
图解
4 |8 u  D* e# x# y+ d$ `
" b, Z6 A! R5 S4 x2 h& y- b* R
# c3 c/ J" Q) h基本思想

) y8 U) U2 u$ |3 J( o* N在a[0…n-1]中，将a[0]设为最小元素，设min=0
4 T6 n" A! ]: K  ]在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
7 D7 U4 n: z- X! x2 }若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
0 }/ g+ N( `5 M) T7 _在a[1…n-1]中继续进行排序。
代码

- F5 E. `* N, o, k$ T/ d/ y2 q7 ?#include "stdio.h"
, o5 e' P4 n8 ~6 A1 T* ]3 g1 |
* m; `9 E5 D% s- ^typedef int ElemType;

void SelectSort(ElemType a[],int n){
    for (int i = 0; i < n-1; ++i) {
5 f% R* T3 d! ]( ?# ^% O- E% S        int min=i;
4 Z( l( H# A- l; H+ {        for (int j = i+1; j < n; ++j)
            if (a[j]<a[min])
                min=j;
3 |% q  N2 h  F0 X8 A+ b        if (min!=i){
            int temp=a[min];
! i9 b: o  A% ?            a[min]=a;
            a=temp;
        }
  h/ k' J- _2 j  B1 ]    }
}

8 C) C- ?! k* w! aint main(){
9 a* d$ g3 I8 d5 ~4 k% r    int n;
/ y. ?; x6 k% U. y. O8 ]    ElemType a[n];
    printf("一共有多少个数需要排序：");
1 k1 t. r& j+ S7 j& P" p    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
2 {+ Q9 e  G* H! \8 A( Y5 _6 U    }
. k: }! w  q; ~6 a2 E- q% y$ a    SelectSort(a,n);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
  J  T6 S1 {) z. O        printf("%d  ",a);
    }
- h9 q, {6 S; J# [1 G: M- Q7 E}

1
2
2 G( z- C- o: ]3
4
" j& K4 ^  Z" l2 r1 ]+ U5 d& @5
6
7
8
* t$ l3 \9 \; d0 h% N9
# E& ?* s3 k3 T5 x- F6 u6 Y10
9 d8 {- v' c% e- D11
4 @( h/ ]- [  ?* O12
13
14
15
5 }& P% M# p4 k; h7 r16
17
* {4 w# s8 p+ z) ~# n- E18
: p! o% `3 \. j/ Z- Z$ k9 e19
20
; p6 f$ O' @0 ?21
22
) X. K! r4 Y* m4 X. [& ~& O23
24
1 W# {- R* ?( N* w$ N/ ]" S25
9 V: K/ y1 A& K/ H$ d, q( u26
0 l# l  `" }5 @. R5 W( k- [" o27
28
29
! _* T4 s- P" x' }# V8 w30
% t1 v( s" Y% r31
32
33
$ N, d2 d3 t0 B; z性能
' R. V2 E4 ]1 A  ^( @+ B
空间复杂度：O ( 1 ) O(1)O(1)
  m8 I( Q3 \1 L# ^3 U1 c% D时间复杂度：O ( n 2 ) O(n^2)O(n
: ~0 B  u& p2 E4 f; ?; [" S0 _2
)
: e0 P4 `6 ~6 S/ d稳定性： 不稳定

使用性：顺序表和链表都适用。
) n. ?3 Q4 O! R% a$ c+ T5 S7 c
. e! F. ^' _( x# c1 t3.2 堆排序
看堆排序的点击这里！！！！
6 O( R" E7 X+ q- e& C: N. t
4. 归并排序和基数排序
4.1 归并排序
3 I4 z3 h/ l2 N7 I2 D0 m1 C图解
8 L% g/ T" h& w# u2路归并排序
% M7 ^% U+ a2 |  g

基本思想

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

然后将子表再次进行归并，直到子表的长度=待排序表的长度。
代码
5 V- P* m- D; @) D5 l
#include "stdio.h"
9 l4 j% F2 t& p4 ?4 v3 A#include "stdlib.h"

typedef int ElemType;

" F; g% o: z* b% D' w% p+ f# cElemType *b;
9 S7 Y6 O$ d2 D( n' }6 B. z
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];
7 ]7 r  |' G  w5 b    }
    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++];
    }
+ L3 b: {' h; e* w% E    while (i<=mid) a[k++]=b[i++];
' ?, }! Q/ O5 v! P/ X' m    while (j<=high) a[k++]=b[j++];
& o3 ~% S2 s. a) P) w/ ~}
6 u9 {' j4 t* T: h1 T
  r; g8 y7 N) F) G2 kvoid MergeSort(ElemType a[],int low,int high){
! C$ Q+ m3 R' B+ o2 f. T" n+ ?    if(low<high){
! |) m( R6 ^+ G& E        int mid=(low+high)/2;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
$ j6 F/ G# e8 _- D        Merge(a,low,mid,high);
/ Y6 i) j9 G3 b$ I    }
7 t, X( B! K8 E7 A* o4 x0 V}

int main(){
    int n;
    ElemType a[n];
: G  s3 ~( ?0 ?5 E    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
( ?4 i: U8 b+ l8 d$ j+ f4 S; ^# H% y    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
% n9 T* h" W. `6 \/ T: g    for (int i = 0; i < n; ++i) {
) X  P! a: U  v# E        scanf("%d",&a);
' _; \: _$ m: x! P% p7 W    }
    MergeSort(a,0,n-1);
7 u( s6 j" G1 ?  v2 R. \    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
8 F3 o7 _! f- }: ?1 X4 I" e3 c" h7 g        printf("%d  ",a);
9 Z' w0 Y( D( m6 q! j2 W/ v. [    }
}
7 I7 Q( E; [2 F8 z

, |8 s- `* k; Z, s1
" x/ i1 X( t" @* n* A5 c0 U2
3
# K2 t$ e" U$ T1 Y' A0 q4
0 {4 T/ B# h  `! D5
6
# K$ D( M( I4 d7
8
9
10
11
12
13
14
15
16
2 j9 b& v( h; _  f17
18
5 R5 P3 f$ n& |( Z0 w5 _19
20
+ m, \) i) V$ ^) b: T( ^& N21
22
" ^- _- y# ]! N0 Y. P2 D( W23
* r% k# Y9 W, C/ F( z0 C# M24
2 U% o# D, h1 \. j5 _* t" B25
$ @; W; L0 {, {0 `: H; E4 m# ?. l26
( h2 z" `3 j# `27
28
# v/ u$ f, F+ v. |5 m2 Q29
30
- h' D! x; I% h: D; b7 e2 t31
32
33
34
35
8 k9 K# d' i/ u- v/ G7 m36
; [/ O6 U3 J4 R% z$ V+ K; N# |37
38
39
1 ~  P# f5 S+ I5 T# H40
41
. R* U; K$ i5 t  @1 |$ g* ^4 O& K42
43
44
4 W! r1 q3 X9 {- E; `9 G2 `45
- }/ S7 _! G- I8 i0 I9 O7 b( T# x; @46
性能

空间效率：O ( n ) O(n)O(n)      创建了一个数组b
2 b% H: r' D8 j* x时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
; q/ H8 Y2 [. U: |, j9 D​
n)  k指k路归并排序。
' P: n, u- o9 ?7 r  p* t: C5 L! K稳定性：稳定

4 c/ N3 w. o. U0 b4 n4.2 基数排序
图解
+ W2 S- Z2 r* i  G- o
( g* q% M* \9 \: R
基本思想

4 R2 [0 T, L) Z  n将各个位数（个位、十位、百位…）进行对比。
为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。

性能

, u( r6 Z0 l; ?7 p7 m9 f. c空间复杂度

9 _' e3 p2 I2 P& A; T: S$ o时间复杂度

  T5 V! J" L  H5 P* h8 L9 O5 p
- K5 c$ B) O  _/ p; J" i' [稳定性：稳定

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

1 Q2 E, ?6 c& y; }. C, I
5.2 时间、空间和稳定性


0 _5 r% e% O9 N) m( H) J# I( X4 F参考资料
' [* [. D" g: V, y《王道：23数据结构考研复习资料》
/ c6 H- }6 z! ^% _( E! i————————————————
" r1 \( E# f9 S版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 P5 [1 g/ Q" l5 `' X原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678