数学建模社区-数学中国

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

---

作者: 杨利霞    时间: 2022-9-8 10:09
标题: 数据结构：九种内部排序（动图+完整代码）
数据结构：九种内部排序（动图+完整代码）
- x; V' d( [2 {
3 a( @, ?8 T  F% }2 Q) x排序
7 E( Q8 H! j  [: e4 M& ^1. 插入排序
9 D; Y) c0 ^+ g+ ^/ @1.1 直接插入排序
1.2 折半插入排序
1.3 希尔排序
' g/ O7 d2 l5 C% y5 }. E2. 交换排序
% B0 l: I$ }/ c. O" }& \2.1 冒泡排序
7 O7 [9 I2 e) o# R2.2 快速排序
3. 选择排序
3.1 简单选择排序
* N3 i& L9 M0 O3.2 堆排序
1 b: Z8 @# n( b' y  Y4. 归并排序和基数排序
4.1 归并排序
4.2 基数排序
/ X. \9 X: L" j& r5. 内部排序算法比较及应用
5.1 整体比较
5.2 时间、空间和稳定性
; W) \2 `' h2 G; b参考资料
$ J0 k) m4 ?) R4 w" [. E9 ~
内部排序：是指在排序期间 元素全部放在内存中的排序。
& X9 O  ]# {8 y% b' ~$ h' A0 W" Q内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
) w7 E2 g% v& G/ [0 o# N& z1. 插入排序
1.1 直接插入排序
图解


3 Y" w: E0 ]+ {9 o! E基本思想
+ Q$ L/ |) T! p( T4 i
, o+ i* O' f* a7 a( u7 O1. 查找a元素在第1 ~ i-1中的位置k
6 q% X, Y; J% K" H2. 将k ~ i-1位置上的所有元素向后移动一个位置
+ z5 T& x2 D5 P) X; y3. 将a复制到a[k]
1 ?! o8 y& b( V' {" R& c


" E2 |1 U5 d& o. O代码

. W6 s( S* R, R' |. u) z% ]方法一：
6 L8 |- Z, j' T: d
' M! G' J% a2 O6 |3 ~, |数组的下标从0开始，如上图。
/ C7 o, m- v$ J) C7 Z5 \4 v, p
& S. r) G' U- z  A& b#include "stdio.h"

3 G5 [: j6 ~) G  m% ctypedef int ElemType;

( Z1 Q2 \9 O4 i' m2 N/ ]$ i. A2 C" ovoid Insert(ElemType a[],int n){
( I5 v3 d# [* q% L, x- p% H' \  ^    ElemType temp;
    int j;
    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
        if (a<a[i-1]){
            temp=a;                                                               
            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
                a[j+1]=a[j];
% W' u( \& Y# {# P            a[j+1]=temp;                                                       
        }
( Y5 L$ u! |/ k    }
}

int main(){
    int n;
4 E$ b0 y/ c4 S9 c- D% U- k3 C    ElemType a[n];
    printf("一共有多少个数需要排序：");
# Z4 V8 i8 J+ k! g: \6 b8 P: E% i- A    scanf("%d",&n);
2 M2 B( I% G8 H    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    Insert(a,n);
+ R) b. j5 b! P    printf("排序后为：");
  L! f8 O, C( J    for (int i = 0; i < n; ++i) {
' L# [0 }/ m, L' X        printf("%d\t",a);
+ k* x* }9 _4 t$ z  h; O    }
}

1
8 Y  \$ C3 W) P; \2
3
0 R$ L% Q% U  ~! F" j; d4
( R( `% p8 U$ ]$ w/ H, |5
6
- q7 u2 l* r0 m/ R+ ?9 [7
8
9
10
11
12
13
14
: _5 H+ ?" a/ m& H15
16
17
18
/ @- r  C% Q' M' D19
+ w$ j2 K" L" |4 a" P20
21
/ J( ?5 F  g5 B: w7 N7 I22
( u0 h) O8 I3 Q) K: a! h5 ~23
5 g) L! a, z: P% v* M24
25
26
27
28
& Z" x" P' ^) g29
30
31
' F0 l9 R; m3 C/ c32
. }5 t! _1 k/ I  I& N0 e方法二：
# @% O9 e3 w( I# b. }; a, \

) C+ X; K5 {/ I5 M: r- F; H: I
) d! N6 p' C2 o; Q! x; P1 T#include "stdio.h"

typedef int ElemType;

void InsertSort(ElemType a[],int n){      
& E) C" \) {+ f8 X( c    int i,j;
    for (i = 2; i <=n; i++) {
        if (a<a[i-1]){
5 ^6 o2 b" i6 E! }            a[0]=a;
            for (j = i-1; a[0]<a[j]; --j)
                a[j+1]=a[j];
            a[j+1]=a[0];
. i) F' ~$ E7 n' Q) G0 `        }
$ ?; E: _1 K3 T3 L' J    }
- b- X- L, F; ~2 d: k: [}
* @' P* ~+ ~8 M" g2 O( Mint main(){
    int n;
& ^) R. v5 W# j- E0 d    ElemType a[n];
    printf("一共有多少个数需要排序：");
4 Z4 n, n2 p8 b/ U& E, c' p# h    scanf("%d",&n);
    printf("请输入%d个数：",n);
# V9 r  b' h# k8 _& g6 |    for (int i = 1; i <= n; ++i) {
! g  o* d4 ]  X! Z+ J3 m: Y; y        scanf("%d",&a);
    }
; [0 R1 w5 b3 g5 Q+ c    InsertSort(a,n);
: L& w/ J* K0 h5 M/ v1 Q/ |    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
9 l" C$ q3 ^. N  k- I# V+ d" e% N}
9 Y; x0 T  l; \; c0 l& g3 H
1
2
0 p. a1 Y- H2 A: B7 M3
4
5
6
3 i5 W1 `4 `  P, `6 O7
8
9
10
11
* J9 n4 a) }7 F' q% i9 @12
; @" {5 S. h) R$ c& w: p7 |13
14
15
: ^) h7 U. `4 P" a7 s9 F+ h16
. s% V9 H; U- Y% E5 c; v* t. E17
18
19
1 p7 h% c# Z6 S& k& S20
21
22
23
1 e5 Y( B) r% R2 x2 F' b. y24
5 q' o: s/ U6 d25
( `6 H; B6 Q) {1 _26
27
% K; W1 Y& `- j/ u" s. C3 M* e, s28
29
30
算法性能
! l/ G, }9 K3 w+ O- r9 i) \" Z: b
空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)
5 Y+ T- U9 ~+ T& _1 w! u/ Q
# B+ t! w- e6 n5 D; n时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
$ l4 T( o1 z& n# S4 m- o* n1 p2
)

$ y6 ^7 [. U7 a4 s" O' k
( `0 N) C- W) ?3 H* J稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

# K' m8 q9 T5 y% K1 D9 V( c) j% v适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

; h6 ^1 H' j; i2 R0 t$ [1.2 折半插入排序
图解
第一趟：

4 C$ |8 f$ c) p第二趟：

1 G0 _& _- y/ e: N5 \6 Q- u6 E
第三趟：
- y  k1 W( I- z2 c  j7 B" X
: M8 O& e' W  q- f( i! i# O第四趟：略
* Z9 l- `- n4 @) L+ }第五趟：略
0 F1 H  w0 t- @. N. y
' \  J: r; q) O+ K% ?基本思想

& Y9 r- v7 R1 \* W* G) T/ }6 x与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
代码
1 v$ p& c2 y% B
#include "stdio.h"
8 C. C. W# P3 a4 o6 b& H3 O
typedef int ElemType;
$ ~. q. G& i2 c2 ?/ V
2 v- e1 e" X; o0 uvoid InsertSort(ElemType a[],int n){
    int low,hight,mid;
' [- U$ R/ d* V' e; E: X1 N5 g$ }    for (int i = 2; i <= n; ++i) {
        a[0]=a;
. _' q+ H2 I4 b. F        low=1;hight=i-1;
        while (low<=hight){
            mid=(low+hight)/2;
; U9 @0 ?! f8 |, N            if (a[mid]>a[0])hight=mid-1;
            else low=mid+1;
        }
5 A' A4 D2 J' A, H1 ?8 h& H% [) K        for (int j = i-1; j >= hight+1 ; --j)
3 A( Y$ s3 {3 j: r: u& Q" p  @            a[j+1]=a[j];
7 E% \9 Q  v  u+ J2 Z& F( G. w) [        a[hight+1]=a[0];
' o6 O& [+ X6 w* a8 A" f0 k9 O    }
}
1 m" q+ _6 I6 u: V

' m' _: [6 R: v5 |) Aint main(){
    int n;
    ElemType a[n];
1 `0 H$ G8 a( H% c3 Q. Q1 e2 l4 {    printf("一共有多少个数需要排序：");
, e1 J% ?) R1 o) p    scanf("%d",&n);
    printf("请输入%d个数：",n);
: M3 V' }! ~0 r% e8 ^& k5 Z2 r! O    for (int i = 1; i <= n; ++i) {
! T3 c% A6 u1 s2 U, z% M* x/ ~        scanf("%d",&a);
" @3 o* v2 g+ v' ?0 J7 s3 i    }
  Y5 l% ?0 a+ F$ m; l3 r, |    printf("排序后为：");
    InsertSort(a,n);
6 R% B9 j. a$ R+ m5 W: ]5 H* v" `2 j
    for (int i = 1; i <= n; ++i) {
& o8 R6 C# e5 k* {* x        printf("%d\t",a);
    }
5 J1 a% _! @# Z- }6 a}

7 R4 @  `$ ?9 D$ m2 `, y1
, N: W, w4 I" m3 w2
' ^5 d* \6 n7 ^* {/ M  O3
& J( T/ F9 O' W, ^3 {: s4
5
6 ^( Z, @9 W# |) e0 v! J# U6
: i/ a5 S& o/ z/ S7
$ N+ d+ X3 |3 s$ d% F1 p8
4 l6 v' ^! x7 v, S. ^* @8 X# H' T9
10
/ J) x8 p6 H  }! w/ [11
12
13
14
15
3 {) z! g5 g9 E* k) V6 {16
17
* z8 r8 F. t# b; Y! N3 p/ D18
19
- Y& s& e' y' Z. S8 X20
21
22
23
24
25
26
3 P! ^  W' F6 F; Q- N3 Q27
( B% n3 _8 Z3 `' N28
29
30
31
3 S' |4 l% _0 E. s32
+ Z" J8 V4 `. l$ D3 a2 _33
34
35
36
, S& E& I6 K# R" U& n37
性能

空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
2
- ?6 r& C/ j& c! V3 S )
5 D4 G# V: s* a0 |5 e& o稳定性：稳定
适用性：仅适用于顺序表

1.3 希尔排序
9 \; y6 A; R( }7 t) O& U图解(动图)
+ w8 ^# O4 z4 @6 I- S
( |" a0 b/ ?' i- {1 ^9 s4 T+ U4 |
- K. {, j2 _2 |( W9 n* R$ T5 s基本思想
& |; L, C7 }4 o3 L0 b1 [
: A0 S0 ~0 i8 a先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

8 i! M% j: q1 ]5 v/ ?1 S代码

7 J, f# P; ]* T: O#include "stdio.h"
6 S$ ~/ p; \% l8 ]$ S1 N
/ n' a6 @* l  x6 B/ itypedef int ElemType;
& X( x5 z% C( M# ^3 l
void ShellSort(ElemType a[],int n){
    int j;
1 X1 C7 _% Z# o8 `1 t6 D0 T2 i$ G  W    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
/ ]: X4 L4 L8 A' A& f9 ]3 j2 e        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)
                    a[j+dk]=a[j];
                a[j+dk]=a[0];
            }
9 i" U/ `9 ]* U6 r6 u/ A        }
" v1 M" d" t7 L$ t* p" V    }
}

int main(){
) z, N& Q% P: E* K/ w    int n;
4 n, @0 C4 @6 j+ V* X3 `    ElemType a[n];
1 ]! f& b' a( U; @# c% `9 B$ m    printf("一共有多少个数需要排序：");
( M* e8 V4 f* T    scanf("%d",&n);
( O8 Y9 H, P. w! v: {! ]8 Y2 v    printf("请输入%d个数：",n);
8 Y) E6 [) Z$ v! z/ m) T    for (int i = 1; i <= n; ++i) {
+ O* {3 Q# m9 V/ H) J# O4 A        scanf("%d",&a);
    }
# ]1 a4 ]. g5 H, |  k  a- Y    printf("排序后为：");
5 i6 q; ~% i9 _4 t    ShellSort(a,n);
/ ~2 P3 E2 c5 ?/ l+ @
. J# @# c. k5 U& I* `    for (int i = 1; i <= n; ++i) {
2 c  O/ `0 `7 q! [% y! F        printf("%d\t",a);
) [& u' z6 a7 |. u  N! o    }
* k- z- P+ o0 |2 u4 E4 `}

1 @' ^7 e! @8 z1 r2 ?  e) X6 k( h1
2
3
  u  }. F- H! Z8 u8 m4 E' C4
, d- p7 S6 v: U" c3 f2 M5
6
7
. A( _( b) j" c8 M) \7 W! [* ]$ e8 J8
9
10
' h+ T9 W* B9 E* P11
5 F  ?, I% V* s/ r( l12
13
& h) S# r: z! L  c% n0 m14
# `7 [2 H' f, j9 S15
# X5 Y% c6 L! V/ M1 R1 S16
17
1 ]8 @7 f: L$ ?( I; |# }18
19
20
21
2 O2 N$ Q/ p, ^+ y2 @- k2 z# p22
* N, J9 k5 F/ {2 s/ Q( w# W; Y23
24
25
! [" ]$ j0 v( c; `2 t26
0 c( ~  G% J8 i27
1 t9 z9 K1 o8 F  ^4 t28
  E  o/ }: R  H) n29
- h7 U. a2 A. E) L( w30
31
$ |+ x  U' v( L% u5 ]32
( n6 B* O  Y4 e$ x: G+ M33
34
性能
( J- G( A7 o* r; Z4 s; n
空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
* S! n: Y+ J& p( W0 g
时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
1.3
)，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
9 E+ F' h4 {6 @9 D7 F1 N8 A2
)

稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。

4 D0 A+ h" J( d/ d/ b/ Y: R
/ d: p! q4 g8 Z) Z' E! ~5 s4 Y/ B适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。

6 ~/ N7 R; v) r$ ~& T9 C! i  p2. 交换排序
3 m; u( Y8 \6 c1 H- ?2.1 冒泡排序
% [. N* v8 D9 q' @图解


8 w# P8 Y) y: @% U- J  T: R基本思想
1 u, J% T1 m* Y' k
从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。

代码
$ T; l! N  U9 r
3 a6 I2 }1 w: g方法一：将最大元素交换到待排序列的最后一个位置

#include "stdio.h"

" [1 l# ?" s) ?3 wtypedef int ElemType;
4 p, h. b/ I1 \6 ?
void BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
. [" k; v  f+ U$ Y        flag= false;
/ P( j5 a6 r$ @# c& k        for (int j = 0; j < n-i-1; ++j) {
9 V% _6 C# h" }            if (a[j]>a[j+1]){
                int temp=a[j];
; u( K) ^3 O+ x8 I8 A. R, f                a[j]=a[j+1];
" M6 j1 p0 c& U2 [                a[j+1]=temp;
                flag=true;
            }
9 C! j6 g- c3 `+ A        }
* O# f# }; U6 Y2 s( {        if (!flag)
, ?  A+ \: a1 w            return;
    }
}
  X  J: @' U& T/ Z
) u2 h2 @5 m: ~$ d  h
int main(){
$ k$ ~; Q1 A$ J    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
5 Y. y; E& M, {' r! N* G    scanf("%d",&n);
    printf("请输入%d个数：",n);
. |8 v9 B0 @! \2 W- Q    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
9 [2 n2 j7 ^: R4 [) v    printf("排序后为：");
    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
* E: k7 F! u- ?4 N' H4 r        printf("%d\t",a);
    }
}

$ ^/ o& N! s1 c2 v& Z1
" l: P8 K" R; f2
3
4
5
8 p: X. t! d. f( N! j- P  }6
7 f7 `9 l% b( ], H7
) Z$ B' F+ Y" {6 F8
9
2 Q! M4 N* E5 ~! ~1 W10
11
4 V$ f4 M  x! _) N5 C% I12
13
14
15
- i# x% N2 C8 p# \) V  V16
17
* y6 o' }& ]3 |/ S$ h$ _. v3 y18
9 O& @2 p$ x! A, R4 S; Y19
, }% f( z5 j& D+ S20
# c: [- B# A8 ]5 E21
6 M4 |9 c2 {; N, j) y22
23
24
4 _! D( R- `0 |& b8 k0 G" Y25
26
/ V/ l0 d5 Q1 K( q& i27
28
1 m" w$ X3 d$ c/ y& J* c+ [% e9 j: R29
30
8 ?: p; L) q! \" e1 t" Z. A31
& Q& a# J/ _" x' _3 y/ m32
33
1 e! }# u4 \; o, z+ k% h34
/ x: o- x5 ^- s9 u35
36
37
运行截图：

' U  c& t3 P7 E
方法二：将最小元素交换到待排序列的第一个位置
9 M$ U2 B: G6 A/ X6 J
#include "stdio.h"

  L. g5 v: n' u; E, L( F8 ^typedef int ElemType;
/ e; f! x+ s5 m  c: ^
void BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
        flag= false;
6 ^) ]. g  b  ~6 I1 q! v        for (int j = n-1; j >i; --j) {
3 h( b  {& w: t% g3 [            if (a[j-1]>a[j]){
                int temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
4 d9 M7 k+ M' ?- A% |7 Q                flag=true;
            }
0 a6 f( Y1 e' b; d        }
8 j3 B8 G# l, [; ]( d        if (!flag)
* H7 f& D, m  J, a) e4 c7 {            return;
    }
}
$ e3 C- w# y* ^1 Z  g4 z

int main(){
    int n;
( V: p2 r; [: `. K3 j    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
2 `2 ?5 a& i$ @) ?" x; x        scanf("%d",&a);
    }
) [5 ^& C) @# Q7 f    printf("排序后为：");
    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
$ H6 ]9 x: `( n6 ^2 B/ `9 |5 V: \0 C    }
}

7 x6 D6 o* M; \& g' d0 F' I7 n1
' C) D7 k5 G1 d2
3
4
5
) Q7 j- u- |' ^7 x% B3 H/ [" U6
/ L0 D* }4 P( H2 K. b' M; w& r) u7
8
9
. `" q* {) {6 `) [. e2 L10
- s; u# X; ?, Z; C; u11
3 u0 X! B0 L  q; M  E12
0 W" Q& L" |6 \( `$ j13
$ Q9 b) ~( `0 i* V/ @9 e) F/ u5 m14
4 L' L! g6 _# L; K& m15
  F' D! y: b6 t; I16
17
18
( E% n6 G5 a' a$ ^! Y# d5 w: }19
: F$ W& u. R# {! ^  F' o20
21
) {! k" r; S/ d5 y/ B9 \22
23
24
25
/ C$ t3 u2 r: s$ l% H26
0 X& r" d9 U9 ^* H. {, H1 v27
  u6 b: k3 r4 e) z# Y" X4 [28
29
30
7 m& U( S6 s) F* S0 n2 i. R31
32
33
) W6 T* C  Q8 Y; L1 u/ v, K6 w8 p& E34
7 T+ f- t7 F! O35
36
37
运行截图：
5 g) B: q. E9 |+ R* f' I4 k

性能

空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
: K3 P9 z( ^3 M! C  s
5 N% @0 \9 f0 [1 K9 C, m时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
; V) k6 N) C  W* |' {, }2
)；平均时间复杂度：O ( n 2 ) O(n^2)O(n
4 |2 G  P( G- e' }2
)；
) s6 N+ H" w% {) ^7 N- b, F/ t
稳定性： 稳定

( c- a# k( N/ L适用性: 适用于线性表为顺序存储和链式存储。
( K$ \8 D2 m  b% P8 }: m
8 P6 ]8 O2 ?* p! N6 k( z: C! ^) R2.2 快速排序
图解（动图以后再补）
- N1 N9 |/ f8 Y/ s1 G/ I第一趟的排序：

0 ]4 Q3 F/ v4 D# ^4 G第二趟：

第三趟：
; i0 [) M7 |, f* A" t  N# F

基本思想
  |5 `$ \! Q4 b" X, C/ |
快速排序的基本思想是基于分治法的:

在数组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步骤排序。直至所有元素排序完成。
9 N- n( q2 M/ Z8 t6 D/ B5 g( F代码

0 w8 J1 K; Q* h#include "stdio.h"
9 j* Z3 H& V7 X3 z! x, T& _$ r
typedef int ElemType;

2 E" T+ T" p4 W8 {- hint Partition(ElemType a[],int low,int high){
% J+ r/ `2 x1 L; _0 Q    ElemType pivot=a[low];
& q+ c. x) T3 g. n6 C    while(low<high){
' w' H- k" s& V1 {7 ]5 N) N        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
        while (low<high&&a[low]<=pivot) ++low;
3 h3 c& N( f# b* x9 B        a[high]=a[low];
  b# H# K: S5 ~# J6 J    }
    a[low]=pivot;
    return low;
) U3 F, i8 c9 O6 \}
1 Q1 N( v1 w) F2 B$ d
void QuickSort(ElemType a[],int low,int high){
    bool flag;
0 N2 v- k1 q1 X6 C) c, G9 g5 y5 a    if (low<high){
        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
    }
0 k3 j2 e- t# c' r/ e  w" ~}
) i% J  }* T, X& q3 @& E2 |6 n
int main(){
    int n;
    ElemType a[n];
% ~+ t6 a1 H" i( k* P' E7 `3 _0 `! n    printf("一共有多少个数需要排序：");
8 W+ Y5 B: T6 b/ s0 [) m3 s    scanf("%d",&n);
    printf("请输入%d个数：",n);
  ?+ I: U. e/ q. K  z    for (int i = 0; i < n; ++i) {
% ~8 l9 a! a( l% f! q* s+ s- l5 J        scanf("%d",&a);
% i) ?+ @$ `9 U# }% `9 M& G+ p    }
    printf("排序后为：");
6 F, u4 w+ e0 D# a    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
}
; ^6 e8 J. }$ W, S, O' W
, i' L3 T7 q6 L# U5 e. Z  x
. U5 q% h$ Q& O" A( s1
9 T" }/ ]9 [4 S, v2
3
6 T; {( n' R4 P: Q4
5
6
. H3 R1 ~: y  D1 l7 k7 g) m' ]7
8
9
10
11
12
' X* G/ z5 f" L3 b) J13
& P  m8 n) Y% f! ]; G: V2 O4 d2 h14
( r6 n+ P; Q+ V15
16
17
# S: I" \' i* Y) D* ^- x/ u18
: H4 H7 K* g' q7 @, [19
8 y- X* M$ K! S, V  N2 t7 c20
# n, ~1 l* J9 z6 c3 r7 p3 o  N, G, z21
22
5 K2 x4 ^& a1 ]0 i! p23
24
25
26
& P1 k7 K- M& P0 a3 u( r27
) z  L7 Y7 s2 R4 b$ I28
29
# g# H5 y" l: F. C30
9 O/ G1 W1 m8 {: a, q31
% c# q: V( F; W0 E% S32
! h! L  R8 _! o9 I33
7 G9 R$ l# u/ h+ b0 J5 M/ _34
35
9 s% Q' c! r5 z5 Z. m4 o* x36
37
38
39
40
7 K5 I1 w0 C: u, U! }! a41
5 F7 w" @7 c+ M9 ]: T8 R* ?& i* c性能

时间复杂度和空间复杂度
稳定性：不稳定

2 a& @1 f; ~( D/ P2 i9 B3. 选择排序
3.1 简单选择排序
图解
8 w, J) |) l% q2 N% k- V- c+ T

6 o$ e( ^; ^# ^" s7 s基本思想

" g% u- ?" D- d8 Q在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]中继续进行排序。
: B; n" X' ?6 q  T9 V代码

0 u# h  L2 ?8 l#include "stdio.h"
/ O. z' J- ^, k# n# L* v
' X  M2 V+ c  v' ]# ^typedef int ElemType;
2 s" s. B6 d' t: {; F
$ A/ C8 a6 k3 ~. T+ {! m5 y# P3 Lvoid SelectSort(ElemType a[],int n){
    for (int i = 0; i < n-1; ++i) {
$ H1 D3 p+ ?" ^6 E! c# \: @0 f' c        int min=i;
        for (int j = i+1; j < n; ++j)
            if (a[j]<a[min])
! V8 u- }9 h3 {9 e! X; j$ t                min=j;
. m! c  i  U! S8 {. N        if (min!=i){
/ q" g3 ]: s' b3 x- H            int temp=a[min];
            a[min]=a;
            a=temp;
        }
+ x* f. U/ ?. ~9 a    }
# H  i5 A2 l) v' I! B2 _}
8 g% k4 w. p. K- I
3 R7 u7 M1 G# R" R; V- }8 G2 r' e1 _) Aint main(){
* g% e" y7 x7 Q* D3 g, N; b    int n;
3 m/ _: E5 l: C- k, M, T    ElemType a[n];
    printf("一共有多少个数需要排序：");
8 b- f7 E; _  S) a5 u( _3 O    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
& A; R: I1 u+ ]6 w0 T    }
    SelectSort(a,n);
# V7 ~3 [$ @) V( U2 G. p    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
( |7 s; i) a* E, D: }: D        printf("%d  ",a);
    }
}

! a4 U5 _* W$ _2 L( N1
2
3
4
" W2 d9 H% H  |; H5
$ A* A# V( I/ }' \/ u6
% g1 {# u4 l9 r6 H% u+ |7
8
9
10
11
12
13
14
15
16
17
18
& ^4 H. S' c: O, p) W19
20
, i! j, ~4 \) J, \1 _% q( g& }21
22
% L' j, P& Q$ J+ l23
24
  E# A: C3 v& {) T' q/ P25
26
/ H, M4 [% q1 \7 I9 ^* R+ X7 f27
2 i) C* `4 t3 R& Y7 B28
29
! r: |' F! W4 M: [0 E. P' n, s30
31
) z% {$ p8 b$ m$ f+ |32
4 \4 c! V3 O* e" n8 `+ x& S1 c, N33
! z' W1 J: u8 ~& a性能

7 N0 y% x- }9 J8 ~空间复杂度：O ( 1 ) O(1)O(1)
0 a+ c) U/ {* J  q4 H时间复杂度：O ( n 2 ) O(n^2)O(n
: w# P1 m1 ?9 p; l6 s# w  t! M: B2
)
稳定性： 不稳定

使用性：顺序表和链表都适用。

3.2 堆排序
3 [, U0 @' [! n看堆排序的点击这里！！！！

  @, x4 m, h7 t2 `4. 归并排序和基数排序
' M# ?3 G$ ~3 G- U2 Y, X0 Y; M8 E4.1 归并排序
图解
; c1 K0 N$ m. Y( r2 E; T2路归并排序


7 [4 r7 o" P" W* g2 m2 Z- n, M, z基本思想

将待排序列分成长度为1的子表，然后两两归并，形成有序子表
' T6 s) ?6 \6 g5 M
然后将子表再次进行归并，直到子表的长度=待排序表的长度。
代码

#include "stdio.h"
#include "stdlib.h"
! H: [( M1 R+ }' h6 V1 L" E
% x7 z* S, [( D9 ]typedef int ElemType;
( c4 F2 s' w, y
ElemType *b;

void Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
9 e( N/ C. P, Z; d( T    for (int k = low; k <= high; ++k) {
        b[k]=a[k];
6 e1 d8 k2 L9 Y% J; `2 g+ }3 S    }
    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
3 Z* {* S7 y& ~5 v5 C" o$ c$ J        if (b<=b[j])  a[k]=b[i++];
        else a[k]=b[j++];
$ p1 N2 {8 u+ h/ `/ j' o! z8 L( [    }
    while (i<=mid) a[k++]=b[i++];
    while (j<=high) a[k++]=b[j++];
9 |: d* L) l2 Q5 x# j$ K8 e}
0 k; R$ _4 x7 y  m$ T0 r
0 a6 n% j: l- fvoid MergeSort(ElemType a[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
  X3 O/ o% j3 {: b$ L9 l' ~4 _1 C8 B        Merge(a,low,mid,high);
    }
3 N! M' [; B4 ~* l0 k( |5 z0 G# t  _}

int main(){
( i0 n1 F' q' O  K) `# e1 m  x    int n;
7 n1 g3 v1 e  J    ElemType a[n];
    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
    printf("一共有多少个数需要排序：");
( U7 D7 k, |3 M    scanf("%d",&n);
. l5 T9 {: {. [1 \- Y/ Y0 H- z  h    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
' b& k3 F9 T" _        scanf("%d",&a);
' A9 ^) p! w; \  N9 O    }
2 H9 r4 ~" K8 C3 E8 e% h    MergeSort(a,0,n-1);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
}


1
2
) B+ A0 Q8 e$ k- m' M3
' K- z! p. o2 v4
5
6
& U9 [6 h9 B; p. C5 o/ Q$ w7
6 ?3 b$ R- p$ }% [# j4 ^, D5 c8
9
10
11
  w  C& B" G$ e12
) x$ t4 V* ], X8 {# I) Z13
/ a! o; I+ Q" c! d$ f14
3 J7 N% Q0 B  R8 u$ W- {# G8 i15
16
17
18
4 a: I# C$ H! v7 A19
+ I: B4 D* T; |! l9 B20
21
22
( e& b6 c% `, }/ Z8 D23
- M8 N$ D0 F( Y! D24
25
- d3 J1 E+ s8 U* y26
5 w  f( ^/ q; _8 G- D* |5 ^27
28
29
30
31
3 E6 G  ?1 c9 W! }7 d, e4 k+ U32
33
. }  A& Z5 n8 a- E. O- X34
) S8 h# Z  a$ S- a3 h- F35
36
37
38
$ _: n; K  V7 \+ g6 z' b; Y39
7 J( L' T% G: X, Y0 Q* F( `40
41
5 Y' B  P) V' D. Z5 `; [42
43
44
45
46
2 X* t  j; a, {* Z% f3 A" ?$ Y! _性能

空间效率：O ( n ) O(n)O(n)      创建了一个数组b
4 m- }4 E/ i, n时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
​
2 T7 `$ w, {8 L& f+ J n)  k指k路归并排序。
1 r$ q% f& h( r: x' v稳定性：稳定
0 T9 T. b! f( j' j3 D
4.2 基数排序
图解


* I, x. H6 i& l& i/ o基本思想
  B. G; b* F7 t3 g& i7 W( Z. ]
/ U* Y- |" l& \) O$ l1 }将各个位数（个位、十位、百位…）进行对比。
为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
# Y# e; v7 |4 t" `3 y6 W' ]* a/ |$ t
# d6 I5 Q% ?% I3 N5 k& t* Z0 ]性能

2 r+ E% Z% v( b% y! R空间复杂度
# D6 ?, a5 ?0 M) Y) F
: n% i- P' l0 r时间复杂度

4 ]+ S' |- r  |- m: M- B
. W; y9 x2 y1 }; _; r, y" O# |( Q稳定性：稳定

" m* e+ k) c1 [; N5. 内部排序算法比较及应用
) v1 U+ I8 j$ s, @$ k- m5.1 整体比较
) I3 P; {2 _$ h" Y' k7 k, [/ W
3 p5 _0 Z( V: l( c7 F+ `) Z) z1 B+ u
3 b7 E1 n$ b, K  E, `2 Y3 `5.2 时间、空间和稳定性
% G+ {; L$ b& O, \* x0 i
1 K5 I3 j2 {( F# y, W4 p" u
参考资料
《王道：23数据结构考研复习资料》
————————————————
( d* E6 W' U2 H! o版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* F7 T6 x. U3 N4 L原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678
1 l# p( u$ e/ I, t
2 r9 K7 b# I3 p# f3 Y
+ t' d/ r2 N. b2 p% b! y& p

---

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

Powered by Discuz! X2.5