数学建模社区-数学中国

标题: 数据结构：九种内部排序（动图+完整代码） [打印本页]

---

作者: 杨利霞    时间: 2022-9-8 10:09
标题: 数据结构：九种内部排序（动图+完整代码）
数据结构：九种内部排序（动图+完整代码）

排序
% e3 e; r$ e1 P3 l& e, c1. 插入排序
! M" Y5 ]0 g4 e+ {1.1 直接插入排序
! |! z2 s, I6 Q+ O# K. g2 V- l1.2 折半插入排序
- l0 \7 U) D( H6 G' Y( A& J1.3 希尔排序
- {# T7 ]% x9 r3 s: ^" _2. 交换排序
2.1 冒泡排序
5 P% [0 e0 j* C% J( U# \$ J/ R. ]2.2 快速排序
6 b; y* P$ o: G8 j3. 选择排序
3.1 简单选择排序
6 }8 t, f$ B3 ]& `3.2 堆排序
% d2 H( [  [2 Z8 E' S3 N* j5 M4. 归并排序和基数排序
4.1 归并排序
. F# o1 Y- K) l4 W" _4.2 基数排序
5. 内部排序算法比较及应用
5.1 整体比较
5.2 时间、空间和稳定性
参考资料

内部排序：是指在排序期间 元素全部放在内存中的排序。
$ k6 v& @# R# e) r% d4 y内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
4 O& y" `1 a, w; }9 ~1. 插入排序
$ F. K: a% G& h6 ^, p1.1 直接插入排序
4 c: {( w' M1 F( d, i8 i( k图解


( ~: q3 g# Z5 T: s8 y基本思想
) e% B( y7 Q# E  `3 w8 ?0 ?
; t: ]0 Q. H. k6 j9 R+ e3 S1. 查找a元素在第1 ~ i-1中的位置k
2. 将k ~ i-1位置上的所有元素向后移动一个位置
( m! y+ g( h6 _7 v3. 将a复制到a[k]
( x: x; G( E5 e1 {3 B6 [


4 E* |2 h/ A" b代码

方法一：

3 A0 e/ U+ J; |; y0 m数组的下标从0开始，如上图。

5 _0 @$ e% l4 J8 G0 ^#include "stdio.h"
0 H" V2 u6 `; n) I% `+ k
typedef int ElemType;

void Insert(ElemType a[],int n){
% \$ Q0 U. q! Q1 o9 Y/ C- N* C    ElemType temp;
    int j;
    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
        if (a<a[i-1]){
            temp=a;                                                               
$ y$ q1 o! Z3 ?* w) u            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
7 C! I( E. m, P1 ^" d6 ~                a[j+1]=a[j];
            a[j+1]=temp;                                                       
7 }( m7 A  F; K& c( O# j7 P5 \        }
& g* r- d2 F5 L1 f, E4 s9 r( R    }
* b1 ]# K. Q* @}

- W) B2 d: g& ^! aint main(){
    int n;
1 i6 s% i# L$ o  s* a6 q* q1 A    ElemType a[n];
    printf("一共有多少个数需要排序：");
% m9 V- Z9 o; H9 N" ~    scanf("%d",&n);
) Z4 g8 D# W4 r0 I4 l) x; ?8 Z    printf("请输入%d个数：",n);
& K' }' H0 o* p0 E* f/ i    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    Insert(a,n);
    printf("排序后为：");
/ z8 X' I0 A2 V1 a' f7 u+ s    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
0 r9 [. }7 n" ?}

" ~- d% C: ]+ B1
( y5 @  A8 M+ F) w' f! @- q. `2
2 |' N& |0 A- y/ M! F1 C4 D3
. k! \0 ^/ o7 A. R4
3 h" M" x, J( D: L3 n; z5
6
0 Q' h0 w! d$ V7
8
) @6 K3 _; @9 ~+ p, j9
10
$ _) K5 U$ Z" {; m7 k11
12
13
14
& ~1 ^7 G0 K% m  w1 N) ]+ R7 f15
16
5 Q8 W$ O/ N8 h( y7 C% V# C17
18
. s& M) Q  Y/ o  L" B  c19
20
" M3 f9 {. o) y" b2 C* E" d21
+ E3 |2 k5 t$ `/ L# G22
23
/ [7 n3 p, G0 b# }: l24
25
26
27
28
" E2 f; R+ p: ?3 q- s29
30
31
32
9 ]2 e- X2 k  P2 b/ W9 T0 n方法二：
, B7 K$ U" E* F; R4 D2 ?1 q5 A

# @5 z( U4 }* Y% V' h- c
#include "stdio.h"
! T2 q: Y& g( P, y0 y
typedef int ElemType;
/ {, ~+ f6 i/ n- @* I
void InsertSort(ElemType a[],int n){      
- G; y0 p% G, y; V, O/ a    int i,j;
6 ]; Q3 [6 ?+ b! M/ X9 F    for (i = 2; i <=n; i++) {
        if (a<a[i-1]){
            a[0]=a;
            for (j = i-1; a[0]<a[j]; --j)
                a[j+1]=a[j];
1 e# H/ r; U# a  j            a[j+1]=a[0];
        }
3 _% h+ R  S+ q* M8 n    }
( @- d* p, y4 z" e% B6 C# J1 t}
' E9 k5 b$ C4 X9 A0 n' Rint main(){
    int n;
' B. A8 ~  R1 x! j9 e% z    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
0 L, T1 P- F- y# @, `- \% @% a  V    }
. o8 L8 R2 |8 z: [    InsertSort(a,n);
    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
4 w) |) w- s. k6 T}
6 J  c9 S8 s2 |0 T" r" ^, G6 ]+ c. _
0 B9 R! U4 a1 ?8 W1 ]( ]7 R1
. ?: R( j0 j8 x2 R6 b" E2
3
4
* N$ P5 t' T" B5
5 \, [$ I( }" O" R/ J2 O6
6 V; [7 i4 `. v, |7
8
9
+ @. G# p9 h& w10
- w' g! t7 p5 l* j11
12
13
14
6 @; u& V: u  M15
7 C/ Q6 L( @! ^( P2 A2 I3 k16
17
18
: c' `3 Q* O5 _5 D. Z* l. h19
20
$ {+ r, D! M9 x: T' w21
/ }1 Q" T7 d: Y5 x! h/ O22
23
24
25
9 d  U4 D# H# ]+ _. ^9 _' A' n: {3 A26
1 v; ]2 c; n& m: B/ _' f27
28
! Y  G8 p, m" C" v# s; s# c: Z* {2 t29
/ Z2 u  ~, m/ X! I. Q' p9 L30
算法性能
  z" q; X' ]: ?
空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)
! G6 t1 V# y- s5 t3 Q' d
5 W! `  x6 M$ g0 D% A# Q! w时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
$ M9 ?' y; w* Q' Z )
7 t/ C& a- F' H+ w8 g6 M
2 C8 R) e; R" s* h5 j( J6 l
6 Z; g2 `1 w' V5 O+ ~3 v& R1 I稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
# ~) ^- i3 G9 Z. F
适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

1.2 折半插入排序
7 W$ k6 `8 ~- [# {2 `) B( _图解
" A% E% E* a7 d% f, o# `5 e$ H* _6 J第一趟：

8 \2 q. E# N, m# v+ y, Z第二趟：
' `% T$ L' Q4 q# v- ^8 t
( {5 K  k% U: z
8 [" F/ E) j/ d. H/ {第三趟：
) P8 |, V5 f" m: _6 [" O
第四趟：略
3 P4 U* {# S+ K第五趟：略

; [, d. z3 y2 s# p. ?. v基本思想
6 b' ^# l1 J- P2 Z
$ Y+ @4 C; Q6 b与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
$ ?' ]0 V. [& m% O$ U取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
代码
; ]! c/ Y, w5 D. U# x' n
7 s6 _% M* k5 o0 `#include "stdio.h"
8 Z( V& @! L8 `) b
4 p/ J8 w, x% L  p  Y3 a6 wtypedef int ElemType;
( l+ K  L: S# ]
5 h* i. F0 `6 z) }void InsertSort(ElemType a[],int n){
. {6 [8 O- h# x1 P: j8 W    int low,hight,mid;
7 {+ `9 y4 z% b7 g7 J+ I) M    for (int i = 2; i <= n; ++i) {
5 E$ i9 _- Q- r        a[0]=a;
        low=1;hight=i-1;
        while (low<=hight){
5 a$ x; V5 n- V2 e- X% s6 Q, i            mid=(low+hight)/2;
            if (a[mid]>a[0])hight=mid-1;
            else low=mid+1;
# f& Y* k; k( B$ b( t& D; u0 O        }
        for (int j = i-1; j >= hight+1 ; --j)
1 m4 U$ z( P9 Q' f6 t            a[j+1]=a[j];
        a[hight+1]=a[0];
    }
}

! v- v1 s& s9 |: c4 l% B& s
& v, m" N2 q  }- _7 ?int main(){
% J3 `, Z! O# U8 ?    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
% F9 L. n9 ?0 N8 B/ ?  B7 u    printf("请输入%d个数：",n);
& {& C* u9 a3 {$ z- b# V) `9 A% q    for (int i = 1; i <= n; ++i) {
1 d$ n# i# y; N% ^8 G% t0 J        scanf("%d",&a);
    }
$ M2 N; ~% ]: o; ^    printf("排序后为：");
) W( v8 H# w/ @& N. i" G5 g( `    InsertSort(a,n);
: e2 Z4 V0 u; _% j9 `$ R6 m1 P
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
}

1
2
3
9 Z/ e8 G3 E& w( C4
1 \" {7 t/ Z# I9 p1 L5
6
7
8
9
/ Q/ M3 j8 }, i( Y6 S+ o10
11
12
& m8 r  G7 P2 I13
2 @1 M3 F* Z* X0 I, I! T% ]1 N! w+ Z5 S14
+ N. P/ b2 l$ ]/ \15
16
17
% p5 P' L5 z: M( `6 {18
19
6 ?1 P# o: l& R+ ?  J0 u1 s20
2 [, Y0 x. @9 c% `. ?8 R9 ]21
4 W% x+ E. Q# Q1 n' o' q6 }0 c22
9 S1 ]+ C+ y. N+ X# R23
24
25
6 z1 B& G; K7 O; m+ j26
3 {% ~. y  C* r27
  x0 b5 e6 U6 H8 |! A3 A28
29
" g" X0 q' [% ^, D30
1 D" x) z2 S1 j8 t31
1 z. |: p: R( N. o; F32
33
34
35
" C# i' m. y8 o6 h36
  P) l" ^* N/ q( \- }. m37
" X7 o$ w7 r3 Y) `8 U2 h" K性能

空间复杂度：O ( 1 ) O(1)O(1)
" o' k' D$ _9 A* N5 Y' \$ ]9 M时间复杂度：O ( n 2 ) O(n^2)O(n
2
5 H' Q% L  I' r) T0 q* f( t8 ` )
5 L. D- b5 l$ X% U稳定性：稳定
# r3 c8 M6 E* t% H! Q$ r适用性：仅适用于顺序表
3 \- i- ?. c/ z4 b) N, f- x
1.3 希尔排序
图解(动图)
5 ?9 a5 `/ G  z( d
9 q3 u. ?" d+ @8 M, z' i
3 E- o3 _, S- Q: o8 C基本思想

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

! V- a, {  }; z0 |) k代码

#include "stdio.h"

4 |" p' i2 _. ]0 ttypedef int ElemType;
0 c* t4 I  H/ c# z. Y& i2 h3 }; H
2 K" U" v0 |* p& Y3 o4 Kvoid ShellSort(ElemType a[],int n){
    int j;
    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
8 M8 \9 D0 @  r( X  z1 u        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
            if (a<a[i-dk]){
% c8 K. R4 L( v( f( i; F/ j5 {2 m                a[0]=a;
                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
; ~5 U- L6 e" g5 n! }9 R5 l5 o( N                    a[j+dk]=a[j];
2 Y5 H8 H4 S8 @' v9 {                a[j+dk]=a[0];
            }
        }
4 ^( S, l! |6 r    }
& N8 S: b0 x/ R2 @+ m: B}
/ V- b+ o2 y4 D3 e% y2 W
int main(){
# E' I% t- g) R    int n;
0 {& B8 T+ q/ N: L9 _. d3 n9 O4 @    ElemType a[n];
8 R+ @0 c+ H( J5 d    printf("一共有多少个数需要排序：");
$ @1 M* `3 C5 v" `+ a! B    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
4 m6 P) W% A2 n+ u5 X) |) f    printf("排序后为：");
    ShellSort(a,n);
9 L8 ?/ H) h7 h) L! P  [9 Z  U
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
}
% T4 R: g; G8 z: B
2 j' V7 X5 ?: K# E, ]2 N1
3 x$ N* o% l& M7 v2
' P3 W  B* k# G" A3
4
2 @% t; P- W. u5
6
1 y# z. r6 j: [5 }7
8
9
10
& E0 R; G, E8 }$ |11
12
# o! S8 r9 o6 M( ]% D& N+ d7 X& w: t13
" g/ l* p! d* O# a" `14
' J$ l5 e% ?0 e) ?7 Y, ^; u+ @& j15
16
17
18
19
2 W' T1 F5 U* t+ v. r4 C20
$ T. Y5 O3 H/ _) k, @# l21
22
# p+ j, _- c; D& V23
24
5 g/ q; V& }4 y1 L( R25
26
& a# ~! J, w/ d7 C! M27
28
29
30
2 m3 r* e: g9 f# i: n31
# Q( o0 S9 _" s32
33
34
2 |0 \" q# c- b1 n性能

空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
9 V; A) A  s, X" J: x
时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
+ N6 m8 r& s$ ]" [1.3
)，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
* z# |/ g4 S  n0 e8 X# p, \( G- q7 B2
$ _) {% H3 s. o2 k7 `* K. u )

" N0 ~0 _$ q  c* d2 K1 a稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
% d+ ~& A; {1 H& D

5 i; a4 l1 `, h: C适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。
8 g( j- D4 x9 S/ T: L0 x6 @: q
2 v3 J+ _7 Q( d8 V2. 交换排序
' O; J# z/ s5 u% O2.1 冒泡排序
+ r, a8 q( D- k* N, r+ c4 M图解


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

代码

方法一：将最大元素交换到待排序列的最后一个位置
1 H( f# t3 Y* p/ q: Y' g1 v
, H( q0 h; G( H' O1 s& g#include "stdio.h"

typedef int ElemType;

void BubbleSort(ElemType a[],int n){
. O$ a# l1 R; K. X& I% \9 o, u/ A    bool flag;
  g+ f( h3 d5 S4 P" z    for (int i = 0; i < n-1; ++i) {
        flag= false;
1 g! T" w" Z0 I* O1 Y        for (int j = 0; j < n-i-1; ++j) {
            if (a[j]>a[j+1]){
; r! y) u& ^/ a) w' R* z                int temp=a[j];
4 n$ O9 i3 ^: _  Y                a[j]=a[j+1];
2 v& R( ?4 s* y' }5 [                a[j+1]=temp;
                flag=true;
, o& h% S2 S/ }. |8 ]* p. h& W            }
/ Z! k( `$ L2 J5 h3 E# n$ d        }
        if (!flag)
# {! h; v. ], i5 ~3 F' C2 a            return;
    }
) }: y4 H3 h0 |+ P1 i) \}

, ^8 ~% [) h+ O! A' i$ o/ j
int main(){
6 t7 x# _& B8 Z% ?$ k9 h    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
* `9 O4 I  O" V$ g1 ~    printf("请输入%d个数：",n);
# n, x6 a1 g: {" D' }    for (int i = 0; i < n; ++i) {
& k0 g. y- R- D% ~& j# ]8 {# w+ W        scanf("%d",&a);
/ Y) S& y' q, b! c9 ]    }
    printf("排序后为：");
    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
0 L9 h0 H- u( k        printf("%d\t",a);
7 q+ E7 a6 }" J1 S9 U9 h    }
4 W! R+ U, v0 c0 ^1 r$ J2 \) ?( l# k}

1
2
3
4
1 p' l9 j& G* C  E2 v: [4 G5
/ `  o% j8 W  q9 N" C0 g8 v0 ~+ p6
5 s6 k  Y1 C, d2 N7
8
# C' p6 V" m# `2 i: ]: g: O  o( T( X# [9
4 R5 m+ t! g6 V: c8 O$ P4 H& `. E10
* ^: A8 O* p5 V, q) K11
# N9 X+ ]- A* R) q12
2 n! v0 w) X  v13
14
* q( a0 X4 o3 y) M5 z15
16
  b  i" y- t; }17
18
19
2 B+ D5 a, f  M4 [20
: N5 G! R* a5 P21
5 l; d! k/ V  L4 N6 @22
23
8 e% ?1 r' B. v8 [+ V- D( t24
/ V/ k$ h, s/ S2 w- \- _" [25
26
! U  z1 w3 n. i# \& X8 O27
* }/ r$ J# m% `- |8 }" I8 A28
0 w* v- e; `; _  K29
30
31
& N! z2 G* X9 n" o+ B0 A32
; R+ `5 M, I% ^. {33
+ R& M2 X8 H/ D. n# N  @34
35
36
37
# D+ f2 t! J5 @5 b, V运行截图：
8 V% k; B( l$ Y  A9 }/ G
! u3 A6 c% O5 z& V7 f
方法二：将最小元素交换到待排序列的第一个位置

/ D4 z+ E. i8 O0 I5 S#include "stdio.h"
0 ?/ D. |% P* e! M& p& E
' K7 }2 ]- i+ x% P) etypedef int ElemType;
  f) K7 c" P" b; e; ~' {- A
void BubbleSort(ElemType a[],int n){
    bool flag;
, i5 n+ ]5 g% i- @- g    for (int i = 0; i < n-1; ++i) {
" \  A$ v' U5 w9 j* t: O        flag= false;
4 e/ B; u" R& `- v9 P        for (int j = n-1; j >i; --j) {
            if (a[j-1]>a[j]){
( K# t- k0 l5 D( ~1 O* d                int temp=a[j];
: n6 N; [* l$ n9 Z* e" C/ U9 b- {+ l                a[j]=a[j-1];
) r; P" s0 _- T0 q8 f. T* q                a[j-1]=temp;
# f: E6 h4 ]& p9 ~                flag=true;
            }
) ?: ?7 A# ]5 O/ @6 g* x        }
        if (!flag)
6 G" d' y! y7 _) S2 U            return;
    }
}
8 C5 L8 I8 A( ~# V9 b, ]

6 d% z! D7 ?0 s1 X7 M9 a  _int main(){
    int n;
: L( K7 X0 ?, o1 q( V    ElemType a[n];
    printf("一共有多少个数需要排序：");
4 l: X/ |8 |! H. X' z2 U( b    scanf("%d",&n);
    printf("请输入%d个数：",n);
- f( t. o  C* t    for (int i = 0; i < n; ++i) {
0 y( R7 ~: R2 _' F; }6 h        scanf("%d",&a);
9 h" ?0 }' d- q( i4 L    }
% ^% ^- ^9 N  a8 {0 O  {( K7 y, _    printf("排序后为：");
    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
8 y8 L; @+ e; t: l4 U2 H- |        printf("%d\t",a);
7 \- S  P# u3 P6 u6 f    }
}

! s. y" x. W9 m6 ^; ]1
2
3
4
8 e2 @2 w+ m3 q( P! |6 y: w- L7 @4 B$ X5
( n9 p" e; \/ C5 A: A' \6
7
; ~* l3 \% ^0 g- G; A2 p( r! X/ w8
9
10
11
12
  v) X6 `( E" r13
14
15
16
17
18
4 _- T* A1 @! J8 a19
- B3 B0 I2 l3 z, a. ~& _20
21
22
23
24
25
; E/ W+ l$ N) s0 o26
27
1 A: o3 [) D7 ^1 L28
29
30
. D* y$ G2 K# j1 d1 b# o31
9 e+ D- Z) e9 o' t, q1 `$ @6 h32
* \. x  H& d/ n; L33
34
35
36
37
, l! U9 s/ G9 c运行截图：
0 z, Q9 d6 M- u  b

( S" U1 m8 u0 i2 |7 r性能
7 s: g( v  u7 O9 D0 A& t1 Y
空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

& Z; g' S8 n# \3 z时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
! V  L) G% u% c# ^0 s2
" S1 O) e5 E- T, H8 l. \* C" c )；平均时间复杂度：O ( n 2 ) O(n^2)O(n
# m5 |* U! j) b6 b# m9 R) f2
)；

/ y5 N* ^  m' G稳定性： 稳定
$ e1 I% y# E+ a6 G
适用性: 适用于线性表为顺序存储和链式存储。
3 ?, g1 {0 @  s
$ U3 q8 x( P) a# L; e* p* l2.2 快速排序
图解（动图以后再补）
. M8 q' S# Y) G& X' b7 z4 ]第一趟的排序：
' i  G' u& F6 P5 R
# y- f' F+ x" R: [+ Z; Z& l# P第二趟：
1 g, H' V2 u) q/ \+ J7 Z
1 G# l- b: n( s- L5 m+ Z第三趟：
: ~& {) b7 d' r2 e- ~
5 y, V: M% g  ~! }* \/ c" o
) k6 ~3 c: Y+ F; b  C基本思想

( c+ A: t/ ~( Y) |) _' t! s$ ]快速排序的基本思想是基于分治法的:
! S6 @6 K, S- s" a+ g
( w4 C! F. w. u, O! F在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
/ b/ l; s$ u5 s, N/ y通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
+ n. b$ D7 K) [6 e* E- g$ a然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
) H) h! E& t$ ?. ?0 ~代码

& L, j, n8 L# J1 ?- C#include "stdio.h"

typedef int ElemType;
5 y3 I# x- }' x  p! A4 T+ J
( L5 P3 A; l. W  }int Partition(ElemType a[],int low,int high){
  D% B8 P( C& u/ z7 h9 X    ElemType pivot=a[low];
1 d2 A& z2 p  F: J9 U3 e4 o. k: ^: b    while(low<high){
6 t4 t' S3 C! V* o; K/ M- @2 V* n        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
" {& C6 V6 g# |5 x: e        while (low<high&&a[low]<=pivot) ++low;
        a[high]=a[low];
5 J/ q. ~% c3 n# y2 z    }
* |0 v& u' ]) r7 w    a[low]=pivot;
    return low;
' Q3 @7 {6 R3 K. R}

% J$ I* _$ S0 Dvoid QuickSort(ElemType a[],int low,int high){
    bool flag;
    if (low<high){
7 l) W6 p. e8 H! ^8 x        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
. [: q. r5 e, U& D- T& J        QuickSort(a,pivotpos+1,high);
    }
}
6 X8 Q- e1 a7 p- \- U5 K1 j
1 z+ h, e! ]7 I' b" ^int main(){
" P0 H  l0 |; |    int n;
/ c) |( y5 O2 E& ~# {    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
2 d: X* R- e( ?% o    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
0 |+ i3 a& F$ ?# x8 D  x        scanf("%d",&a);
    }
    printf("排序后为：");
+ s! _9 }+ t) c1 S2 m! i3 _% `$ [! i    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
" v6 e6 n2 O# w: b, n! @6 @        printf("%d  ",a);
    }
" \# F! O. Q+ X}
  f. r! n* I2 j# g& B7 c- e

; ^9 P& r; G3 |/ ^8 T1
' u6 l) p1 R3 ^8 P; J4 h/ S! D2
. v9 y2 a0 d7 g( f8 |9 @3
4
5
6
7
' i4 G) r$ p( {8
2 T5 c# [4 [# F! A: T9
10
11
2 j2 s: \# M, G* P- |& I9 Z12
13
* R7 J  E# s6 J. N. b5 i0 }; u% ^14
' P. I+ O1 z: X8 n" w" q15
16
17
18
19
6 y& T- r3 J4 I2 w6 m$ P) @20
$ n( T( y7 |1 W/ h: ~21
' e, ]/ _) Y& D: F/ N22
23
( j+ T5 {9 {5 A2 L: E1 x7 t24
0 g8 h" B( l# L+ j9 V25
26
, r* k0 k2 l5 T4 q1 p27
28
29
30
) ~6 l3 {$ C# b8 X, u31
) I0 W( i# G7 d" a32
33
34
35
" j& {4 Y' n2 W# s0 I7 z& i+ {36
$ V6 O0 K1 e, g# @" y37
38
39
$ b7 U8 }$ L7 D- B- \/ _3 l/ c! e40
41
性能
. q$ Y1 ]) d$ a/ j: D0 g( v: T
时间复杂度和空间复杂度
稳定性：不稳定
$ v! m* X; C/ N0 {
, Y9 t+ C' i7 {0 ?2 g3. 选择排序
3.1 简单选择排序
' y2 ?$ j! G; ]+ s- r9 E) Y图解


基本思想

3 \; {2 O+ M) p  }在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]中继续进行排序。
代码
2 \8 y* r! J  r1 h- p" X
#include "stdio.h"
* l+ m5 t, O6 G8 V4 b4 {
. n& Q; T4 J. Mtypedef int ElemType;
& ~  V( H0 Z/ W9 G, ?
  E9 `( C0 C, D' L" qvoid SelectSort(ElemType a[],int n){
7 f/ m5 n( \1 Z( b    for (int i = 0; i < n-1; ++i) {
        int min=i;
( R. }5 A& ]+ Y        for (int j = i+1; j < n; ++j)
            if (a[j]<a[min])
' m; V1 m+ O: q2 k0 t                min=j;
# f# Y/ H1 M* r& U8 E/ q# G        if (min!=i){
            int temp=a[min];
) L8 N# p, w! N' L7 `% o, p5 o            a[min]=a;
% T, r4 }! q6 N# x9 }$ c            a=temp;
        }
    }
}

% P" N  J& B0 w$ W8 dint main(){
    int n;
    ElemType a[n];
! T8 q& ]5 K0 V$ X    printf("一共有多少个数需要排序：");
' n9 ^/ r9 d/ Y, Y: ~5 n+ r    scanf("%d",&n);
- x+ Y3 F: G9 P6 l9 u) _. F: u    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
* h" c: J( \1 u- U        scanf("%d",&a);
: X7 a0 k7 @) e3 y4 _    }
: ]% U% s- @2 j- W3 `" l    SelectSort(a,n);
! f  I% G4 [3 `- w% Z' }7 l/ d, K" G    printf("排序后为：");
% J, h- @( H6 ^# t    for (int i = 0; i < n; ++i) {
2 n8 W1 H2 \& g% U        printf("%d  ",a);
% u0 \# l8 T5 _    }
}

1
& ?1 K; D7 N) N! K2
; @$ ?  o* x( d* v3
4
5
6
7
8
& |- _+ u( d7 M1 l1 j3 t7 b. w9
10
11
12
! |) L1 E& \, M( O8 a13
14
: `7 N4 |4 j) z7 V( `2 e0 f9 u7 m15
16
. D. v- J& ]$ p17
" U: [1 Y5 Z2 F* N2 V/ m18
19
/ Q( q$ l9 ]4 j2 ?20
21
22
& o# ?4 U+ Y) d7 q2 w23
24
6 B1 B8 ~; }( p7 g% u( V7 u25
5 ~7 n' e+ M4 @" i: B" {+ U26
  G' S& F7 j/ Z/ a, @7 {27
28
, r- X! P- Z! u7 ?# \! r29
30
. z' Z/ s3 {# v31
32
, H  [! ]/ E/ H# O# R3 W33
1 g0 S) h* J/ e) r性能

. Z# k/ _  x! O空间复杂度：O ( 1 ) O(1)O(1)
6 X  C6 d5 c) B  z9 n* r时间复杂度：O ( n 2 ) O(n^2)O(n
2
)
稳定性： 不稳定
& ~+ }- t5 Y# U6 l. y
6 @, A0 J( L2 \4 t使用性：顺序表和链表都适用。
0 E# _4 {, y* e  ?
3.2 堆排序
看堆排序的点击这里！！！！

- m- m' `& Q& U' K  N9 ]4. 归并排序和基数排序
4.1 归并排序
& s  i/ o9 z3 I5 [' l图解
2路归并排序

4 Y3 w; y- `; @7 l
基本思想
+ T& j) h* S5 G" G- v
# l3 G+ Q, t. i: q( B) @: ]+ v0 [将待排序列分成长度为1的子表，然后两两归并，形成有序子表
: Y! |! X8 Z* m* C
然后将子表再次进行归并，直到子表的长度=待排序表的长度。
代码
$ Z4 z, w3 K. \- \& Z
#include "stdio.h"
4 H  A7 r0 n8 h& Y$ m8 z* t! r#include "stdlib.h"
! E5 Z  \1 P* \& ?; Q4 w$ y
' `  p# }4 Y4 etypedef int ElemType;
9 F# s' z& e1 \0 a( o& x, u
ElemType *b;

: `+ ?: X- Y# M& Q4 n4 g: Gvoid Merge(ElemType a[],int low,int mid,int high){
0 x# K' q: z' E( Z* f    int i,j,k;
    for (int k = low; k <= high; ++k) {
4 U' I& t/ B  c* v- r. t8 i        b[k]=a[k];
# L" w1 j; u$ G! ?+ h  ~/ {( t    }
    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++];
. t( a  d& u  C- l9 z6 o0 M    }
; w3 X" _3 g$ P9 G4 k( c    while (i<=mid) a[k++]=b[i++];
    while (j<=high) a[k++]=b[j++];
}

( W) g/ S0 \2 l0 pvoid MergeSort(ElemType a[],int low,int high){
- v$ e$ Y$ v; l. q3 s% N& a7 P    if(low<high){
        int mid=(low+high)/2;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
' w- h" y( g- |* i% H1 A        Merge(a,low,mid,high);
3 m: q: z: T2 z2 ]$ ]- z! @8 d    }
9 _% s6 V0 ~( I1 O( B) b) ]}
) }% v. d8 l+ z2 ^3 S, r1 s) t
  S4 D) w9 s# w6 b: \. J& `int main(){
- N1 l/ Q: u. r    int n;
    ElemType a[n];
    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
6 v. W& {) e  O( a) E! g' L" ^# ]. u    for (int i = 0; i < n; ++i) {
$ m6 y; ?0 q, X2 f1 @* i        scanf("%d",&a);
    }
    MergeSort(a,0,n-1);
! F9 R8 n4 a. z    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
' b5 Z. m! x) I5 N        printf("%d  ",a);
' X/ ?' z, I0 I1 @7 }" d    }
- b/ K% @% o# h}
- N+ @- d( _$ D+ O

* Z. `  O1 i1 t6 o% P- _# ^6 _1
+ J' [% ]' }& U" l$ t5 G2
3
' b; l$ z2 g- |2 H4
4 w2 E/ U. E8 V5
( V# @" r9 _; I# b, b6 L6
7
* ?: e6 F. e$ h: h0 T3 p1 n9 L8
, v2 Z6 Q' U) d6 t1 i: E; R5 U9
10
11
12
+ [% K/ q( G9 y, w' G% ]# F& a13
14
15
16
# m5 d8 U3 L+ |8 a* Z: d6 ~17
18
19
: |5 _6 c- Z' K2 g4 W- Y20
21
22
23
$ P$ _5 H2 P1 T3 `24
1 s. k6 ]  e8 t5 c25
26
$ }/ Y2 N( Q/ T9 n  z27
28
29
30
31
" O( F2 F  v6 C2 D  y, s( [' K32
7 H) L; G& W& v0 I3 X& I4 n( J33
34
2 _7 g2 _; Q0 n4 [9 V  S( O% L/ I% \35
+ Q8 F, V( H6 x: E9 B8 F* O36
37
38
39
40
41
- t( d- r9 ?! E" v  p42
! Z6 y7 Y; L6 E: [43
/ \! J6 N' k5 |8 F2 @44
45
46
3 Z, F% @% G2 c+ Q& p4 h性能

空间效率：O ( n ) O(n)O(n)      创建了一个数组b
时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
​
n)  k指k路归并排序。
稳定性：稳定
# B( Y4 D  ]( z# w+ A6 ?
: B( o0 b) ^2 R$ Z4.2 基数排序
图解


# m' m" t- n9 M* a基本思想

将各个位数（个位、十位、百位…）进行对比。
5 ]# {# O: `8 D# B4 l, n- ^为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
: ^, p$ Q0 o( e- V% d
1 V0 y- n2 A/ `! Y- A/ w性能
, S# r* v1 l1 L+ P3 B
空间复杂度

时间复杂度
  E# J/ U7 p* h  g( a% J
1 i4 x1 R( x) d7 h3 s
, v3 t' |1 Y8 `9 H, y# L稳定性：稳定
3 \& V$ x6 t7 [+ r5 F- e# O
5. 内部排序算法比较及应用
5.1 整体比较
' O( j& W" D2 d$ U2 O; z
3 ?* A0 t+ _# i& N7 ~9 f( T. f$ G, X
5.2 时间、空间和稳定性


; B: B6 c! ~% V% A, s4 r( B7 c参考资料
《王道：23数据结构考研复习资料》
————————————————
版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# t1 ~& R  @2 k9 g  G- n) f1 _4 c原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678
2 y: E! ^% v! M# Z
# J7 R8 m$ m, D0 U
3 F- _% {0 p$ E* S$ G4 y

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5