数学建模社区-数学中国

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

---

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

排序
  [" J1 y9 D; d7 }$ d. f6 {- z% a1. 插入排序
! n/ G2 C, K# G5 c+ m5 m1.1 直接插入排序
1.2 折半插入排序
4 s9 s% h  F- P. _1.3 希尔排序
/ ~0 R) s/ R6 s% m2. 交换排序
2.1 冒泡排序
$ g8 t' `; u) x/ ]) a( d2.2 快速排序
( f! P/ ~  I7 @2 Y2 o7 i3. 选择排序
3.1 简单选择排序
. i% T+ K$ x* n. M3.2 堆排序
4. 归并排序和基数排序
4.1 归并排序
$ h% G: E! O6 a* O4.2 基数排序
5. 内部排序算法比较及应用
5.1 整体比较
: r6 @# G. ?3 B( s+ ?5.2 时间、空间和稳定性
参考资料

# t/ H# F4 ^! Y2 G% o! @8 Z内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
. f7 A6 W6 l  c( L0 K1. 插入排序
1.1 直接插入排序
图解
! v2 O3 R* v- K/ K4 F! R  \

1 e6 M- i# {3 E% r7 M基本思想

  B  n  V  f3 A' k* h) p* t2 E1. 查找a元素在第1 ~ i-1中的位置k
* o8 A6 a5 j& ?. i9 h% e  e( E# r; E2. 将k ~ i-1位置上的所有元素向后移动一个位置
3. 将a复制到a[k]



代码
/ g% x  R2 t+ @& X% Y9 s
方法一：
5 a+ a6 e8 y  Z9 o4 E
; k* R2 y" ~) K! @6 W0 }7 Z数组的下标从0开始，如上图。
( }1 b; `: n1 C, R
; K+ N, E& v$ |#include "stdio.h"

typedef int ElemType;

void Insert(ElemType a[],int n){
    ElemType temp;
    int j;
9 h: |, ?( g+ \/ D3 N* T    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
. T* P+ F$ |. Q0 u* b& a        if (a<a[i-1]){
            temp=a;                                                               
1 C  o$ A; j% x9 `: h  E            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
                a[j+1]=a[j];
% X( b; h7 V; \            a[j+1]=temp;                                                       
        }
    }
}
( q2 {2 W0 z! v. ^% n0 C; _
0 Z6 \: K6 R4 ~) v) Nint main(){
* V, Y$ \5 U# U: e# k) A. C& {    int n;
    ElemType a[n];
. G& T) d. G! R$ y  u; T    printf("一共有多少个数需要排序：");
  |+ {0 U( R0 P    scanf("%d",&n);
: r: @9 R6 G7 P% e- z( n+ i    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
  P& }( x$ _/ r3 h6 O8 R* N        scanf("%d",&a);
    }
    Insert(a,n);
    printf("排序后为：");
: i* {' \# g7 t+ j! t    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
}

1
  ~: n6 H' Q8 o! ~; @2
3
4
: ~: v! \" a/ |) S7 ~  p, ?% I+ O% X5
6
7 `# B: \1 T5 m2 x# o/ J7
8
9
10
* J2 U, |. o' R# [11
12
13
' Y, v8 q$ G, d, D2 Z' P  p7 D14
4 y8 j% d& r+ x8 e# f15
+ o& J+ n" M8 l. d! P+ B16
17
18
0 z! n/ {/ \8 P7 p19
+ W8 j! N7 I6 }* n20
6 {" W0 I+ J9 d$ H8 q21
7 ]/ D& f  X# t0 a6 \0 N) S22
23
  }# X, }8 S9 A$ P  }5 w9 F24
! U* X# D( B- y25
26
27
+ X$ Q0 \, `  E28
7 i3 S+ R$ @; P: n0 j. n) ~+ b29
+ e! ^$ q" n4 i- I9 c6 d2 ]30
31
32
方法二：

% G. A0 P( f* ]" L

#include "stdio.h"
, C; _) b1 z: I9 @" C0 V+ j
typedef int ElemType;

) b; s9 T/ N6 U7 U7 @" Y) {% z! Avoid InsertSort(ElemType a[],int n){      
, q7 P- _# h8 J, @! w& J9 z    int i,j;
    for (i = 2; i <=n; i++) {
        if (a<a[i-1]){
+ L. B$ ]' c! r            a[0]=a;
            for (j = i-1; a[0]<a[j]; --j)
5 q& H( I, J3 Y4 }% k                a[j+1]=a[j];
! a. e# W& L( ^6 Y( A8 [" a0 y# s            a[j+1]=a[0];
# E& q! s( B) H2 L" V        }
    }
}
int main(){
# }' U* m' E, m2 q    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
; A3 [1 }) J( C% Z4 d) T9 [    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
( E5 _, c, V6 g        scanf("%d",&a);
! G$ q4 ?  R3 \3 V    }
+ T' X$ S" }- T; w    InsertSort(a,n);
0 h( Z6 k+ f5 q    printf("排序后为：");
; s& `& z' L2 k5 `7 `! w( c6 T    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
* C1 L  \3 n" ?5 U0 W    }
}
3 O" U/ q, u  p# T
# m: U1 a8 R$ ^  F) j1
# B) p$ h3 f) u' ?5 z5 M* N6 L2
3
4
5
6
7
8
9
# u+ U) Y( P  M' C$ @10
! k& W! u0 [% q! |. ~4 y11
12
13
14
15
  U$ [2 }7 M1 J3 B: K, o16
17
2 ]9 ~, N5 V: s6 `' M! s+ R18
2 M5 L3 W# p* A- \+ w8 T2 y2 ^2 ^19
20
21
. I8 `! E' B6 W4 ^$ O; x. [22
  @% w7 S' o$ h8 i# i23
, l( O  B7 G, u$ n" x1 L' G24
25
: D2 T4 D, ]% A26
27
5 W/ ^- ?* r: f5 v# Z28
29
) t1 l' Z  i( a9 v30
算法性能

空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)
; x# W  {9 g5 L# t2 g2 y% |
时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
0 U- d" [1 X5 | )
: |; t- p8 T! \/ Q7 p5 a( l

稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
. ~  C; \! R4 O! Z# C4 z
2 `$ {! a/ l' h  o. Q' J适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。
* d4 }4 s; a! \1 h$ g- v
1.2 折半插入排序
图解
& A6 u+ V5 w. Q' r0 g  A2 _4 z第一趟：

第二趟：
& q5 h- z" `( b* C  U3 [6 l7 b
1 @) i* Z1 `/ u3 \5 Y
, M" {  {0 ?" `- @8 o! a  ?) J0 r第三趟：

2 Z6 j) `, P7 }3 U) V第四趟：略
. H9 x( f. i' L  [第五趟：略

, r. T% v1 P: [' |' Q4 ]8 h基本思想
5 [" g; E1 ?! b# Y$ p  f, U* f
与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
代码

#include "stdio.h"

; f% ~" t3 p" z9 otypedef int ElemType;

void InsertSort(ElemType a[],int n){
( a+ c% W1 p# ?+ T/ |    int low,hight,mid;
4 P7 u, U7 F, C3 \4 @* M    for (int i = 2; i <= n; ++i) {
        a[0]=a;
        low=1;hight=i-1;
        while (low<=hight){
            mid=(low+hight)/2;
) r/ s! X; p0 W* {, m& x! Y% t            if (a[mid]>a[0])hight=mid-1;
            else low=mid+1;
# C3 y* L2 {9 x; V* D9 V        }
        for (int j = i-1; j >= hight+1 ; --j)
5 }; j$ P% S- B. u9 ~            a[j+1]=a[j];
. G7 k, ]) Q" G$ V1 b        a[hight+1]=a[0];
8 R7 L6 I" d2 @+ \' O! {    }
}


int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
# o0 `5 Z2 H$ V% }  y    printf("请输入%d个数：",n);
- _5 H% V1 X. H# g9 _* R% Z- p    for (int i = 1; i <= n; ++i) {
- @3 M( M3 ]+ b* l% C        scanf("%d",&a);
    }
    printf("排序后为：");
5 G7 @! n  \! E9 ]# E" J6 b2 _    InsertSort(a,n);

8 ?, ~( W; T  I" e1 ]7 }    for (int i = 1; i <= n; ++i) {
, o' q0 e; C. `4 f        printf("%d\t",a);
    }
" g+ G. H  i& `$ A' z% ?- ~}
* D- Y7 d' g7 ~
2 U4 ]/ n7 ]0 ^# {1
2
; S/ u: Z2 m9 a3
4
7 x! r+ c1 p" r. k5
6
7
; b# l5 c3 \/ E. j+ \5 ~/ n7 U# H8
9
10
( [( L; x6 @4 @  G* G% v4 x11
% P6 H- O7 T( N0 L. A) Q, [12
' b% g# c, L/ I! \; J% I6 F# ]& Q13
14
! J) I+ q; |; M4 ~) D, j: C0 l( c# D7 k15
5 p6 p' v: W# ^9 a9 r16
17
18
19
20
: V! N+ U. N' r1 C  F' T& i21
/ P) i' Q$ ~2 d' p; [( B8 R22
23
24
9 Y+ X9 A* Q7 e+ S* n25
5 k1 {# [* _$ [& d! c! d8 v26
27
/ `0 V- x9 U/ [3 L3 c  A' Y28
" Z% C- E8 d) \5 E. b4 x9 m29
30
31
32
33
34
35
/ T- m# ]2 r; n: N6 m) _7 r% Q36
* Q4 W' K/ N0 H& l0 p37
性能

) Z; r( x  `% r3 d% P+ b" A空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
2
)
, h- I: E  a7 M$ E& K稳定性：稳定
适用性：仅适用于顺序表

1.3 希尔排序
图解(动图)

# S# y: f% x5 A* p- k
基本思想

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

0 {3 u. c0 H4 ^# H; r' M' P/ G: L代码
/ ?9 T: D  p3 K& o
#include "stdio.h"

( z+ h# l7 U# _% a. @0 F  Y8 z# Z8 @typedef int ElemType;
9 q9 n6 d- ~" o1 M
void ShellSort(ElemType a[],int n){
2 t1 d) |3 x! p* [1 Y" K    int j;
! W% @# x( h- M8 K: v: m% K5 t    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]){
                a[0]=a;
                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
7 L: M; ?# g5 `                    a[j+dk]=a[j];
3 H0 A6 U$ k& L' j3 d, g  E                a[j+dk]=a[0];
& e" F. z- H! h# e2 f% V6 [            }
        }
    }
! q, Z, Q5 e/ L8 t& M}
2 N, n2 L  t1 n! m3 C2 a
1 x- G, m) b% @5 f; l. B7 a; Y/ xint main(){
* L$ T# R8 k6 u* t) ~    int n;
    ElemType a[n];
" R7 A" `- i+ Y9 @, s. f/ ?; n' V: I    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
" P( n2 T" E" r6 S9 C    printf("请输入%d个数：",n);
9 y8 w; ~/ z% \+ X& o    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
' `0 A- M. G( D9 \& `    }
$ a( {, u( D  j    printf("排序后为：");
1 h4 O( I# j. u. K    ShellSort(a,n);

    for (int i = 1; i <= n; ++i) {
% J2 a) g7 q4 u" `        printf("%d\t",a);
8 ?) W( S, g" Q    }
0 y& X' s+ ?- e. k) {6 |( @}

# g3 L/ ]& u: _4 N/ u1
2
* `7 r9 c4 p4 |/ R6 }3
5 h  O4 v7 q0 \# z& J% c) ?/ E4
5
6
+ l. g9 {0 H/ d- \8 X5 I7
' J/ V, R$ M" R& e# M3 k0 K  n( z8
8 M1 a: l, m$ K/ ?/ X8 v9
10
11
: j' H- P3 N7 F6 a* _' S12
13
9 T- s) O- X9 u* f5 s# ^7 H. C: }14
15
16
6 C  ]$ u$ c5 s3 j/ b  S9 R  F! g! k17
4 a: G( z5 h  s4 z0 T9 A18
19
20
21
2 @5 u% G2 X) i" X22
23
24
25
! T7 w% W1 m3 P  L) W6 n3 i26
. |6 K4 F3 s. N+ f9 I- C) I27
  |8 P- I/ r9 n- Z28
29
30
31
32
33
+ c: e# U: s0 v; s% ~. k& n/ ^34
性能
8 {: Q1 v( t4 s( K) X0 U
, T# y; R2 r8 C0 Z7 o& |空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

+ T$ D% w( R# W5 b时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
1.3
)，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
2
' G$ e9 V! }. v5 q% P' v; H )
" }4 B0 n8 K% [$ D( O6 Z
+ K! ]  _$ B/ l0 {8 g& u% B稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。

- B- _* D/ d# e  b  i# r
适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。

2. 交换排序
# I5 Y, Q! e6 K0 W2.1 冒泡排序
# K4 K1 h2 y: q5 o$ j! O图解

" ^2 Q' [) a2 V5 B# ~
7 X9 @" x3 E7 t基本思想

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

" [1 M* F2 ~/ M4 B+ D4 J代码
, F+ B( N  B3 ?' ]' |5 y
; x3 [- Q! |6 g8 k" b. c方法一：将最大元素交换到待排序列的最后一个位置
) S  P) c3 k% p* f$ z% |+ ^
#include "stdio.h"

typedef int ElemType;
4 m+ Q6 u4 r% q: i1 k' m, L  D6 X6 Z
6 }+ Q& M; D. A5 xvoid BubbleSort(ElemType a[],int n){
    bool flag;
1 T+ R1 y; S! f/ q7 c# {. o    for (int i = 0; i < n-1; ++i) {
        flag= false;
% e, j3 B! d! L6 {. }2 N* }1 m- T        for (int j = 0; j < n-i-1; ++j) {
4 G% h# O! N7 M7 Y- f8 ]- K            if (a[j]>a[j+1]){
                int temp=a[j];
  x- F  Z$ d) F: k1 ]( V" ?3 A) V5 C  i+ s                a[j]=a[j+1];
2 @, x- y8 p# [6 v9 Y1 W2 R                a[j+1]=temp;
                flag=true;
            }
) ^+ i& ~. F8 W' R4 F2 t9 p% R9 t        }
        if (!flag)
9 D3 X  J$ P5 ^5 v9 J6 K( T8 V            return;
2 t0 N, D# A/ h3 d1 H    }
$ j- @; l6 J1 C1 v}

( ~# o& L% O) a  r
int main(){
    int n;
1 ]$ d; a0 h. p7 ~    ElemType a[n];
    printf("一共有多少个数需要排序：");
. s$ A- f' z$ C& n+ b5 G' ]' G5 f    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
% x% q+ w7 o+ q6 u/ z! c8 G    printf("排序后为：");
/ @4 G! E) N( R: `  j    BubbleSort(a,n);
7 b% R  A% ~: ?    for (int i = 0; i < n; ++i) {
1 c2 r  N* D; h! i: v6 [        printf("%d\t",a);
    }
}
2 ~* r5 c( L8 B" H( ^
6 W3 c& C7 E( [+ v$ \5 f1
2
3
4
5
4 x* [) O+ j- K) j6
7
8
9
10
% ^, X0 m2 ?( \) p) a7 U11
9 K, N4 A# z3 v7 b$ z/ n' I12
13
9 b) l% \! G8 N! U14
15
+ p; H  j6 K3 \- R16
17
18
19
20
5 i" D" E" V' A2 d7 y' t: r% o' j: k21
1 r% a* N4 a1 f% }5 ?: J! |" m22
23
$ `7 i# f2 X* o( I6 v/ W1 C24
25
2 @3 X2 w  y5 {# K26
27
28
29
30
" s) X- D0 N) n) K31
32
33
  h1 n& o& D! V1 f% r34
9 O: h+ Q2 K0 ]$ N: w; A35
; v7 b3 s- l; `/ |. @$ w5 M36
37
运行截图：
! D+ [! c; v: K/ i. a* `

1 J$ A; V) P- n* K5 y8 x- o, Y方法二：将最小元素交换到待排序列的第一个位置

. L0 d6 g  K8 h. R8 ]& h. M$ E#include "stdio.h"

typedef int ElemType;

void BubbleSort(ElemType a[],int n){
    bool flag;
/ b3 `, T! G' e0 D    for (int i = 0; i < n-1; ++i) {
- ]7 M& G; B8 @# V4 p$ l        flag= false;
        for (int j = n-1; j >i; --j) {
            if (a[j-1]>a[j]){
                int temp=a[j];
                a[j]=a[j-1];
7 E9 v7 k$ [: x. m1 f                a[j-1]=temp;
                flag=true;
            }
        }
        if (!flag)
            return;
. l. x+ ~$ _. l2 j$ E& h$ Z: k    }
}

8 l- G( @( `0 f
0 b' b& W1 S  i& P  o6 iint main(){
    int n;
    ElemType a[n];
; \; B5 h* e' H, I$ ]* K    printf("一共有多少个数需要排序：");
( e. d4 a0 v) p/ O4 Z    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
/ s- F9 I3 d7 o- i5 F+ {8 l        printf("%d\t",a);
    }
! S; l5 p3 Y8 O# e# g}

5 T' \9 a: `) G0 [9 D! e1
2
3
4
8 e+ l0 q% I& \! {$ |/ U8 n/ ?; k' ]5
8 ?/ g4 Y; V2 Y) R, k- |8 L0 }0 G6
8 a2 D; R# u, b/ o6 y( i1 [, ]7
8
4 I- J! w' F5 Q, C9 _9
10
, t* t) w& n. e$ E5 {' X+ E11
" i& s" q6 E: i+ v$ s: T; b% c12
13
14
( @& Z- M- v' ~5 O4 e15
3 d8 b5 [* M9 e; v! U5 e' b16
17
18
. j  l& V/ I0 {$ k" V! ~19
. V, t* |1 u; x2 s+ Q6 G20
4 Q) C  M$ s% @21
) ~5 }' s! E: O, c4 C0 Q22
# K2 o" ^" n$ W4 w, @$ W  I23
+ H, `' G3 ]4 W" O* W# ]2 u% H24
5 T& c: ?9 X5 v1 X! x1 g' x. F25
9 E" j( c% ?& f! F! K26
0 x1 f; U3 r; A0 l7 `6 o27
28
29
& T2 v+ ~) x% L. k# C30
31
& j9 ^% t' U; y" K32
) s0 ^. Y; U( |$ Q- z8 X7 F33
34
5 B& ~: c, Y& Q1 N/ y- |+ G3 u35
36
37
运行截图：
1 t$ N, z, M: z8 G  z* I) x+ M

性能

& \; l: v  R  U; K空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
' s/ O5 V7 b8 l4 S1 r& v
时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
% h/ f/ L% j- f7 b, y& Z7 w: b2
)；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
)；
. l& ]% F1 G1 ^- U* e- R
稳定性： 稳定
' v6 X8 F2 a* h, K' o
适用性: 适用于线性表为顺序存储和链式存储。

: e  N/ T8 f* n$ ^" x2.2 快速排序
$ i& K3 ~: p% y0 }图解（动图以后再补）
) V  s7 r! ]4 H* E第一趟的排序：
) S  e4 w' R( i$ l# L8 e9 A
8 p% \- `5 j- {; x8 h# P8 x第二趟：

5 {4 I; A  Z# f9 ?- c( V0 g9 H第三趟：
; q5 |0 N% c5 {- q9 c( n6 q
- A* U( d- L6 G, d9 n
# y1 i6 ]* b6 T# n& G基本思想
& r: J. Y% E, E" U7 g
快速排序的基本思想是基于分治法的:

在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
3 f, }* ^: Z6 a% ^通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
代码

#include "stdio.h"
& U4 S# Y2 H0 w  f+ g/ m, X& i
4 Y9 l! ~; y0 Q) S& Xtypedef int ElemType;
/ g) |0 D* {  U# L% N1 X3 D$ W
int Partition(ElemType a[],int low,int high){
    ElemType pivot=a[low];
- U+ C+ [- j. S  B    while(low<high){
        while (low<high&&a[high]>=pivot)--high;
# ?) I" V, ~' b7 d, d: V) }3 C, @        a[low]=a[high];
/ E- i" ?; ^7 e1 G/ Q        while (low<high&&a[low]<=pivot) ++low;
2 D/ p3 o4 E+ n! {4 f        a[high]=a[low];
    }
    a[low]=pivot;
    return low;
& c# Q3 u8 I5 W' s1 W9 Z}
4 C, }- D0 i; U. Q* @6 S
7 V! a) ~0 ]  X1 n- @4 d& E( Lvoid QuickSort(ElemType a[],int low,int high){
    bool flag;
    if (low<high){
" M4 w' k. P5 B  g$ B2 ~        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
1 q$ `9 c; f% N    }
6 T. d, G2 Z' G4 ?9 @6 m8 h! G}
- P# u# ~9 c8 ~% \
int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
8 `0 g. a: K) [9 U    scanf("%d",&n);
6 D3 P  {3 N. U6 i. ^% m    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
; X, l, v# n: |( @! w/ X        scanf("%d",&a);
; y3 @2 u& e# l6 ]3 N, F    }
    printf("排序后为：");
    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
/ i  K# q* J$ ~% _# Y    }
}


: w1 j! P' s- \% z4 m) {& v1
2
3
' t4 m7 H4 d' y9 _* n2 z: k4
5
6
9 ^* m/ F; K: P0 g1 _  P7
+ x5 r0 ^4 ^6 m. p. j8
9
/ Q9 q9 a) b. i) T# V- n' ]: B( w10
11
12
1 _0 e2 w# ?  b  }13
' }- D" p) c' u" V8 B6 ]6 p+ e" d9 K14
15
16
4 k; [- Z  W: ]' ~* d. e: B17
5 c* G2 j% p& C6 `3 u) W2 t) @' @) A! U18
19
+ D, }$ l$ ]8 e+ F) q20
  N& G# t& T; }  _% x) c* I( ]" M21
22
" o4 A4 e  o& \+ Y, [: E! e. I' [0 W23
24
25
26
$ w6 @2 H8 X. z/ ]; F' o27
, X, p/ b% M* b. @0 t9 M) `4 {8 D28
29
5 f0 I% P  ~7 f# L( O* A30
31
8 O( Q3 w+ e/ T9 K( v5 t32
33
34
0 |+ w/ e; x, r, r! l) G35
7 H" m# g6 X6 |) S36
37
# a2 B& m9 C& a7 A' |38
39
" ]" l( f  t* z/ o40
/ }6 J; U' b" U1 k9 V+ F$ D2 d2 s41
性能

时间复杂度和空间复杂度
4 \% h. V5 [9 V" D& l0 R) I稳定性：不稳定

0 Q/ \! f5 S2 o3 a+ m3. 选择排序
6 ~7 R; d4 Z6 [$ u# V) [9 k% z4 k3.1 简单选择排序
7 S4 d. m' m. X: z图解

" z9 ^- A# C, e7 k- f7 B
4 G' i! t& `5 G基本思想
, @) Z" X+ A0 {/ _* A$ T/ x, B
在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]进行交换，第一趟排序完成。
. [4 S  S+ g3 J; P: ^在a[1…n-1]中继续进行排序。
代码
0 L4 H, ~# R) t! v6 A
  C2 \& z1 g/ N7 o( N7 L9 b, R#include "stdio.h"
: A' [% C# C: h' H( T( `0 ~
typedef int ElemType;

& J5 p1 e/ I. ]' A2 @( ]8 S1 [void SelectSort(ElemType a[],int n){
    for (int i = 0; i < n-1; ++i) {
        int min=i;
9 V4 Z# D/ B) X& l2 P3 p        for (int j = i+1; j < n; ++j)
            if (a[j]<a[min])
                min=j;
6 v3 }5 S7 e5 ]$ |        if (min!=i){
            int temp=a[min];
/ m9 z( w* l/ m# b; D            a[min]=a;
9 _) _" i& K1 j6 [9 E            a=temp;
        }
3 ^; S; H1 o$ Y' B/ G/ h6 o* ]& H4 N    }
7 c3 b+ c* r% n' w& [, T- B- X}

int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
) x% Y3 k0 c$ `, N/ {! W    scanf("%d",&n);
% p  S$ q+ {# m% r' Z    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
5 y8 D& s& M) P/ q    }
    SelectSort(a,n);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
* Q+ y2 m9 h% W9 e}
4 Q! w) V/ Y; a4 E% L* R
; t9 M# s2 f$ Q  Q7 v7 R4 P1
2
3
6 x  \% `, ^7 @( J" p% ?4
: a0 H( K2 C4 n5
6
7
$ B$ c8 E1 r0 K8
9
/ f* o9 W$ j' S5 T10
11
12
* `. `' S3 Q4 Y8 I, v7 @) P13
14
15
16
% M0 l, U* d# b+ [17
$ v% H. V# f! g% B6 k/ _. I8 |% F4 ]0 Q18
19
! P: M0 |6 [* Y* M# P7 B# i' B20
% m8 ]2 P2 p- q; |21
+ D( z" _0 P- v1 L% E22
3 W6 O% ?8 x, w; U* I23
24
25
26
7 {8 [% Q! y1 ^+ x9 W. _27
28
& y8 b1 G: C/ m$ P2 E. E29
30
* F1 o8 E+ C3 H31
+ a2 S$ k5 w, O/ H6 J1 E32
* ]; G0 R5 c+ d4 |6 m- N0 K33
性能

空间复杂度：O ( 1 ) O(1)O(1)
3 M! o, E* `/ s$ C: m* ?% n/ N) F时间复杂度：O ( n 2 ) O(n^2)O(n
2
)
# Q$ V: G; r+ p稳定性： 不稳定
! T; i( o  _' i8 K' v; S
使用性：顺序表和链表都适用。
+ f, j8 z6 j: c2 T& Y
3.2 堆排序
5 [* ]) C0 t' B看堆排序的点击这里！！！！
- G  ?5 z4 K2 [/ C
4. 归并排序和基数排序
4.1 归并排序
图解
2路归并排序


基本思想
1 ]( t- W4 A% I9 D# N( P1 F1 ?) [
将待排序列分成长度为1的子表，然后两两归并，形成有序子表
' z$ y( [4 \: M1 p9 I
然后将子表再次进行归并，直到子表的长度=待排序表的长度。
8 R1 L1 m8 }5 u代码
7 s) j5 E1 D5 h. Y& p, O
#include "stdio.h"
#include "stdlib.h"

# ]7 i3 [9 `% \( ptypedef int ElemType;
* Q0 F- W' v, D* C$ J
ElemType *b;
! P) `9 L3 h3 E1 U' N6 h- o. B
" a. t& v: V0 M% o' V1 Zvoid Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
    for (int k = low; k <= high; ++k) {
9 b; Q  l& D, l( v* {) c2 P" a. ~        b[k]=a[k];
    }
+ }* `! _, I9 b$ t+ L    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
        if (b<=b[j])  a[k]=b[i++];
; F: `: W- S; G3 i" m: o        else a[k]=b[j++];
    }
    while (i<=mid) a[k++]=b[i++];
, \( U# V7 o& q0 q3 g' d    while (j<=high) a[k++]=b[j++];
}
6 P+ E: n* n1 ~3 `' K
( X$ j3 j0 {; I$ ]' ]void MergeSort(ElemType a[],int low,int high){
4 E9 s  I  R# A3 N! [$ k    if(low<high){
8 |0 o" L# {( x3 _9 H; a        int mid=(low+high)/2;
( L6 D, v" w) s7 c        MergeSort(a,low,mid);
+ q5 P/ S1 w( F$ Y5 `: C        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
% Q  S2 g& w2 J' _    }
}

int main(){
    int n;
. B2 }; P9 K  a' f    ElemType a[n];
    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
# z4 l- H# \! b7 o5 y! U    printf("一共有多少个数需要排序：");
, h4 o* x& R8 l/ S* N2 t1 L7 _0 f    scanf("%d",&n);
) E) ?. q) m- O6 ^    printf("请输入%d个数：",n);
$ Y5 ]; x- p6 Z# \1 u! n6 {    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
* R6 Z9 K: M1 _* q    }
1 ^5 q) `. L, K# T1 S    MergeSort(a,0,n-1);
% k" e6 q) Y3 q7 Z/ `1 c    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
}
1 M+ @# R8 E! d. z# V2 e
! C( D' n  o9 |0 D3 z8 |8 s, f
0 }) t: W6 A% m1
5 f+ b" O, p; B- l1 m: K2
8 V  P# e/ y' M1 c  m: b5 ^; w3
6 O$ `6 m- P2 y; ]+ z% d* w4
* Q' U: g9 u! w4 V& W5
6 y8 b( o. W) |+ B6
7
8
9
10
  m! O/ t* \. J* x0 v% J3 u11
* n; W2 ]# l; N# U+ h4 p* o  Q12
13
* Z$ }* e' z& e5 c) g14
1 u! i% h1 T" R+ [! `5 P) [15
16
1 t0 a) j% q9 K( R# I3 D% x17
% Z8 G$ }/ p0 x) X18
: ~1 i/ u# q; E' b% E19
6 B2 E! G. m9 [8 o- Q3 ]; F/ @# o/ @6 T20
21
1 y2 b' E' x1 u* ^3 y: g; U22
23
24
: F! c* [; l) W( ?25
26
8 s3 w! c% F* [( u% k3 m# Q: A27
28
; }$ A8 R& h0 `1 K- |2 g- V- D29
2 z" U; @' C- k% ^30
; L1 i. z* ~: s% O  A5 [31
" l! h8 W$ ~: l& W3 M6 |32
33
, N) \( q/ F7 v) X9 ~34
# a  D0 M2 g" j* F8 [. {35
36
37
38
% D4 t! I/ g8 a6 o* z39
) L2 }0 }4 i& V8 X2 f6 m0 i40
41
0 I( Q8 w& n* B" Z42
4 S2 A; R; S- Q  u43
/ j2 m0 v# ^2 ?9 P- B3 u4 B; n7 E44
: Z& Z/ a0 c2 v6 e5 ~+ Q4 T! i. g45
" t. X5 S/ {: i5 o) O2 E$ ^- J46
2 g8 j/ g* }) w) G- P8 B9 y4 Z性能

空间效率：O ( n ) O(n)O(n)      创建了一个数组b
' V! G6 h# J7 ~3 b( x. }时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
4 x# W7 H( {0 ~k
0 {" W, n7 b2 e/ J) [4 q( @​
- p0 \0 x8 y8 J, i7 K; `; ~3 Q. X; V( i# x n)  k指k路归并排序。
稳定性：稳定
. M1 f, m7 R& |) g
. i  ~0 I! ~- y% j, R: D$ }4.2 基数排序
图解


; W8 T- S  E& s基本思想
: o' q& P( k: s" K! G1 h
+ v# c& v, n1 b  L; y7 l! I0 T将各个位数（个位、十位、百位…）进行对比。
) g: }- P, c6 G为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
5 ~' d( i% C9 ]% A/ Q3 g
# ?: b2 u; i* n1 c1 c性能

& H. T5 R' Q6 \' P空间复杂度
" }" c+ ?" o  l6 a( x0 u
时间复杂度
* F' G( w8 P, _5 z3 \3 @
+ _0 H2 s( x# X6 c9 ]; j/ ^- s
- F& q% R1 f  ]) O# d1 I9 f稳定性：稳定
+ m0 ?; @3 L' j* J0 c' X8 ~
5. 内部排序算法比较及应用
5.1 整体比较
" K/ V7 o3 n  e: K: Y

5.2 时间、空间和稳定性
6 C1 L: G! Q  f4 ~

) {# v' `& K- b9 x. H5 p参考资料
《王道：23数据结构考研复习资料》
6 h) t. P$ [8 R. l* M: h————————————————
8 P- K; K2 T2 z8 _. I' h版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678

---

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

Powered by Discuz! X2.5