数学建模社区-数学中国

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

---

作者: 杨利霞    时间: 2022-9-8 10:09
标题: 数据结构：九种内部排序（动图+完整代码）
数据结构：九种内部排序（动图+完整代码）
, p/ ^+ g* d( i3 K5 v1 S2 w# m
排序
1. 插入排序
! W5 l: E) X7 E& w2 [4 W4 S. n1.1 直接插入排序
/ P* q# f9 C- g3 \) T1.2 折半插入排序
1.3 希尔排序
2. 交换排序
3 ~: u" ?0 |, ~% \# v; q( }2.1 冒泡排序
3 s$ ]9 U$ A4 h5 [( w( M6 ?# ?) V2.2 快速排序
3. 选择排序
3.1 简单选择排序
; Z) z4 S1 B  R5 n! Z) M7 J3.2 堆排序
4. 归并排序和基数排序
9 n7 q4 p2 ?0 ]  g4 [4.1 归并排序
4.2 基数排序
5. 内部排序算法比较及应用
. O( n: u5 W5 y- i+ V% D5.1 整体比较
8 v! Q! I6 I9 t: D$ y. i5.2 时间、空间和稳定性
) A& v1 {9 J: G) V, q8 ~  H  l参考资料
: ^4 K+ U* ]2 ]" }
- @- h4 |  X, s: c* x- |& t) c内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
0 ?, Y# n8 P! M4 L  [& P% h1. 插入排序
1.1 直接插入排序
图解
  f" ^: p. A- |

基本思想
1 M  {# H5 W. l4 u9 R( j  u
1. 查找a元素在第1 ~ i-1中的位置k
2. 将k ~ i-1位置上的所有元素向后移动一个位置
3. 将a复制到a[k]



: W0 }- F' t! e+ D& g: }) |$ |代码
7 `1 l9 [/ B6 @- {( v, S
方法一：
8 f: e9 c# [/ t8 q
* V( B2 Z' n) ^# L  r* D数组的下标从0开始，如上图。

#include "stdio.h"
% l+ y2 z( O$ h2 s
5 g$ W$ Z' M/ t/ qtypedef int ElemType;

void Insert(ElemType a[],int n){
    ElemType temp;
    int j;
7 ?9 W2 Q+ U. d1 Q    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
! K+ E! D1 Z+ R% n        if (a<a[i-1]){
            temp=a;                                                               
2 s, V0 t6 R. a            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
                a[j+1]=a[j];
            a[j+1]=temp;                                                       
        }
    }
1 a2 Q& d9 b9 X6 j  d" j9 G+ p! A}
5 g7 P% i9 v# c
( B& D% s6 D" a( S( a! Q/ [int main(){
0 V$ d3 I/ |/ R% B7 {4 g% @    int n;
    ElemType a[n];
( I5 M" o! i, z9 d3 V    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
- F) {, I( ^: x+ ?7 y9 L+ I    for (int i = 0; i < n; ++i) {
+ C/ {! y- ~$ R; |        scanf("%d",&a);
5 j+ l0 j; n! ]    }
. d2 h  i! m) G: w    Insert(a,n);
- p$ F) F$ e  O2 _    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
! d2 F" L* Z/ q; U3 M4 V        printf("%d\t",a);
( c- O; g3 S. N* E    }
}

1
+ L" f' w/ j% z1 R, [3 P6 t; g& t2
, |! n6 P& z+ ?  u4 q3
" w5 ]  X$ }+ ^- N4
5
$ d  c3 h7 x2 s1 ^6
0 g; {5 l6 A& Z# @% p. O7 n" k7
" \( D; s3 |& p  B8
. w; x  C7 J; ^7 s+ X9
10
$ n8 {. v4 Q* \3 I11
12
) x: k0 |# p! L13
- L! M( f& e2 E14
15
16
& _! _, F/ f1 Q# ^  ?17
18
2 x$ L1 Z; Q6 o5 P" n$ n, x% D19
1 e/ R% O  N6 d: b20
" a5 x/ U- v2 z) `: \' X21
22
23
24
' h$ |( B; f4 I# Y; N25
26
27
" N  ]- f4 D  ^28
( L& g! ~* Q1 u6 Z. @! \8 ?29
30
! u& S! t, \% j% G31
, u* I$ H1 X9 [. L32
方法二：

6 j% }" `# V, |8 `
6 }) ?3 l' R7 Q" ^) |
#include "stdio.h"
; o6 c3 _& }* W( R, J
typedef int ElemType;

void InsertSort(ElemType a[],int n){      
- m1 C* Z# Z0 Z8 V8 B    int i,j;
. \) y- v7 f6 Z: H- T* \    for (i = 2; i <=n; i++) {
3 n* Z2 I" u; w( v        if (a<a[i-1]){
7 Z; Z: v9 ^/ `$ q            a[0]=a;
" S; B  n$ ]; j! Q" g1 @, U2 E            for (j = i-1; a[0]<a[j]; --j)
                a[j+1]=a[j];
            a[j+1]=a[0];
* E' Y+ s$ Q" I        }
    }
}
! K. e0 Q; Y" N# kint main(){
/ g& ?6 n" v' @1 J& m6 A3 ^    int n;
! m8 k$ `9 J. Y! _) X+ ^5 G% T    ElemType a[n];
    printf("一共有多少个数需要排序：");
+ @* `9 i: D% o# w    scanf("%d",&n);
    printf("请输入%d个数：",n);
1 k" x6 t$ c6 ?9 _% k- [    for (int i = 1; i <= n; ++i) {
/ I5 R6 F' Q. a9 [/ }8 F+ j        scanf("%d",&a);
9 l0 y0 |4 A4 X" R    }
+ r- R) P; B4 h+ r6 `2 X  {    InsertSort(a,n);
9 E8 p' T4 [. A1 c2 i( Z$ v, D    printf("排序后为：");
- G! [# y3 t) P    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
+ a, {% q0 Q& {7 t7 ^" P+ r}

/ h2 T, A8 K! D1
2
5 g. K4 T  o+ v2 k3
0 B6 p- W$ ~8 Q+ ^5 K( q4
+ E1 X* E+ ^9 I5
. [0 S, b3 T  C. }3 z6
; d; R+ O  }3 S! i! I7
- @- T/ L, a8 }. i6 V; P! V8
9
10
11
12
* N3 k7 U+ F: I# i4 m13
14
8 A, H6 s) W: v. p( v15
6 a+ p5 D: P1 K% c16
1 l! O8 P2 c0 S. r6 I2 s6 Y- _6 y4 Y1 Q17
% T5 J$ B3 z' u- n, I# g6 V18
; R& S/ G. v5 B% z7 d" Q7 J19
2 s* z' ]9 y# {5 u6 [5 k20
21
& U: U% |: x8 h% x3 @7 Q7 L, D+ Z22
8 q' l' G& h3 \0 B- o5 E. e; Q) |23
24
3 |2 J# @1 w8 H' X/ ^5 J25
26
, Y# B8 k+ N/ q7 U: f6 V2 ^3 t27
0 t) l2 a) v: ^1 o6 w' U28
" x+ n2 T! z% t0 f- i+ x9 i29
30
$ Z4 V4 y. d/ T2 W  U算法性能
1 c) V  A' Z$ ~3 _8 w
8 p7 [) A" X. [- _9 j9 j/ g空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)
2 q" p/ q! y8 ^0 t; ]  }
2 u7 s, @7 w0 b8 F: E! k- ^& _0 \时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
. U, `. L+ `* c$ Q2 y- ]8 U8 d( T8 n2
)
" z; t' T6 ^  R) e6 q" n

稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
4 [0 }; y# p% A$ W' r& @
& D- i$ P$ D, `8 _8 E+ H适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。
; w; y9 g- X  e# v
1.2 折半插入排序
/ @# `) N0 N; x9 t; e3 m; `3 O图解
; \* Y$ \3 [, Z6 }2 T6 J( P第一趟：

第二趟：


第三趟：

4 {; J  o6 T3 ~) V% h6 E第四趟：略
第五趟：略
$ c3 S; F. m1 j) i2 a' ?# ?
! I. V0 m6 b7 z/ \* ~# U7 w基本思想
) L: Y5 e5 [. j; X+ I- X0 S) m8 ~
& U$ i# v8 u5 [6 y% q4 [, m6 n与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
* A6 o! _0 [5 P1 u; H8 H! @找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
9 ]3 ]8 R" l1 I代码
5 R1 V& D5 T1 }  C9 M; @  H
/ z% _) ~* N8 k! Z5 E) {8 z#include "stdio.h"

0 W- Z$ ?7 z; o! r& ]5 ~typedef int ElemType;

/ R  P( l) q! ~0 z4 h' r8 avoid InsertSort(ElemType a[],int n){
    int low,hight,mid;
    for (int i = 2; i <= n; ++i) {
        a[0]=a;
        low=1;hight=i-1;
' A) a  P- h8 E* s) J; f        while (low<=hight){
2 t, U7 U* ~. y            mid=(low+hight)/2;
            if (a[mid]>a[0])hight=mid-1;
9 Q- I* u3 J4 E) ^" q6 g3 L" r) w            else low=mid+1;
( ?- N6 a( M* E3 k$ u        }
: W" Y/ R9 Q% s. ^! G8 E, M        for (int j = i-1; j >= hight+1 ; --j)
            a[j+1]=a[j];
  C9 e2 s# E  G1 I        a[hight+1]=a[0];
    }
}
& o+ m, S5 V4 [3 y7 X

int main(){
  ~8 W  T. W, y! e$ j9 V    int n;
. U( |8 |2 O- i8 e: c+ N& m    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
  {% e; ]& D* {& ^; T3 M* `7 B    printf("请输入%d个数：",n);
+ a- ]4 d7 n! _/ e9 w) K    for (int i = 1; i <= n; ++i) {
, M3 A2 g1 l# n: W1 W        scanf("%d",&a);
5 d  l+ t$ r; }& z3 \& W' z( d    }
0 U) @4 o/ O6 Q; q- Z    printf("排序后为：");
: D# X( c. g4 T8 J    InsertSort(a,n);

9 M3 n8 w3 i  X+ e4 O& \6 Q    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
: ?! }8 U0 w1 B1 s2 K1 V    }
: _, t6 N- V1 ?0 N2 ]& B8 d) ~2 o6 S}

1
/ q1 J% d9 M$ z6 A1 S- ^2
3
: P: M$ Z  b1 ]4
5
1 w( g, \; u6 T: H4 k& V1 m" F+ ?9 V6
7
8
* X9 z. w/ \3 f: ?7 i3 z: c  H/ M9
" g+ h2 ^  V  ^' X, A4 o8 w10
+ x; Q) g& G& d11
12
% b6 Y8 I* b, d+ }4 h/ p. l& N0 T13
: o- ?/ ]0 ~$ v& t6 I+ _14
15
( a5 H% |' v3 e. m4 F% l16
- u4 q3 C" {+ k$ y& \6 S17
18
19
1 p+ I2 m  M# c% }7 z: @  J20
21
22
23
24
# R# M* ~+ X. `& G25
$ W7 f  o$ D! H2 M1 [26
27
28
" e. L$ r. X8 K7 q" E' }29
4 K* |8 M+ ?5 D30
/ C9 }& X  d. y: M" H31
1 u* t. q4 C" {6 H+ a# c2 B$ t32
9 a+ v* O5 N; a7 f33
34
2 d7 m& ^( p' Q2 H: f35
36
37
3 y9 \& l* U9 L7 B# {性能

空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
9 v5 Q' d$ @! q7 f2
)
7 y' E+ w1 r7 o" x9 n7 X; X' d% Q稳定性：稳定
  j) z/ X/ X7 E% V适用性：仅适用于顺序表

1.3 希尔排序
图解(动图)


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

& f! m9 m  k2 b! y代码

#include "stdio.h"

7 ^, R3 K3 t- i/ Y7 J; xtypedef int ElemType;
0 z6 Q0 p8 {6 t# \1 U
void ShellSort(ElemType a[],int n){
    int j;
    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
; G# J6 D% R1 P  I" V* a        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
+ j) l1 V! _0 V5 m7 e' z% r            if (a<a[i-dk]){
& g9 B; [, D: _  v0 T8 {( H                a[0]=a;
                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
$ b/ o+ M! }# O& L1 w                    a[j+dk]=a[j];
                a[j+dk]=a[0];
/ ]% y5 f. f1 Q- @0 d4 p  c            }
        }
    }
}
% }7 ]) u5 a$ G# g5 B* x: P
: q5 [+ Y$ J' z, n) a( t' fint main(){
2 h6 C+ v3 N% @% j. d4 q    int n;
1 |. ~/ T# j0 P, p    ElemType a[n];
0 Y: w1 Q; Q  L/ m- \- a+ Z    printf("一共有多少个数需要排序：");
) W8 E/ h5 u" M    scanf("%d",&n);
    printf("请输入%d个数：",n);
% \0 ?. h! S2 t4 `& T    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
7 C7 Z! ~! l5 {+ Y7 x    }
    printf("排序后为：");
    ShellSort(a,n);

    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
$ M( ]: e# z) K$ V6 x8 H  h1 T}

; }- g8 S9 n) k" b0 N3 c1
/ `6 V# ]* O! z1 _, g- t2
3
4
5
, g2 k# F/ W4 |5 G/ i' u6
+ V$ r% z5 o1 W  e7 O- \7
8
2 ?6 e4 S* r3 F- X9
# [; p$ ?. E% `% A10
* q8 D, f) a5 c  k$ x5 {( }11
12
; l$ I3 W# i3 H9 f7 E7 [13
- X4 L' `2 L1 D! T9 c14
15
16
  {/ o! i& B. F/ g3 O: Z% U17
18
2 j6 @. s( r  I4 Y) ]7 _" Q19
20
21
( u4 [" m8 e6 h3 I" W; c- q8 S22
23
, K  }* D. j" \! Q0 p: S24
' N% j5 F# O: l; |: y. @& s/ n25
26
27
28
4 S$ Y0 N( s/ G29
' Z7 i% i& x( h6 t30
  c7 h$ ]4 O: R, T, v- k' E& l: Y4 Q31
; \" }1 B- E$ J* w& ?4 n8 I32
# V/ _% ]% }/ d! q. r* h6 U33
34
性能

% s9 k5 Z( D' I) ]3 Z空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
7 q# ^; u5 j  T8 y2 ]: p# r( w
2 Z) n  {% r0 ]* [' f时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
9 y# i+ v0 x/ i$ i1.3
& _; B$ R# V" }8 v6 F- X% A# j+ k )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
4 i( P7 J# B: x# }" t8 b* N% u2
)
9 J2 c- D- |4 Q1 M4 G
稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。


适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。
; y' p9 X2 u* ~: p/ Q) c, K# Q
2. 交换排序
2.1 冒泡排序
图解
1 n, h8 I* u7 c2 S
2 s8 P! Y) }7 H' b
基本思想
" H- H- ~- E4 b. ~
从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。
: h, ^/ z5 H" Y
代码

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

#include "stdio.h"
& A  T; H! j1 B( `
# ~: R/ n) w7 C  J. Rtypedef int ElemType;

/ w* w' x5 t1 k2 M- a. cvoid BubbleSort(ElemType a[],int n){
( J' w2 ]8 ]; Z' H! [6 o% g    bool flag;
$ q2 C% S1 H  E+ k$ }; c0 R# v8 K    for (int i = 0; i < n-1; ++i) {
7 R0 k- z$ j. i+ p4 }) Y, X+ J        flag= false;
8 o( k; r2 @# H2 v0 x+ J        for (int j = 0; j < n-i-1; ++j) {
8 s! b7 [! g" q, d            if (a[j]>a[j+1]){
                int temp=a[j];
                a[j]=a[j+1];
& w2 |3 |/ I% O                a[j+1]=temp;
                flag=true;
/ y1 |+ G7 F  v& f# ]9 g& A            }
7 z' {1 [( b2 n2 D) z+ M6 E        }
6 k8 n# E# s# t& ~0 y0 l8 v, _        if (!flag)
7 {; a9 z  ?3 _. v( g2 {) _* h! f$ ]            return;
! w/ v* p: _2 u    }
}
6 `" ~" X2 z5 P5 i. P' z% H
, B& q6 u1 I" X1 @
6 Y4 P1 m  P! Y- C8 W$ E2 ]int main(){
    int n;
( i2 x1 ~% M2 I    ElemType a[n];
# y( y, p8 T, A6 |; }5 t: \$ v# [    printf("一共有多少个数需要排序：");
    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) {
5 i  G% A; Y& e. S- m, t5 g        printf("%d\t",a);
  t8 Z$ R! v! t" W" K. E# T6 e9 \6 l    }
! B2 F! G+ M& N/ Z8 K}
0 E3 F. c3 w' f7 y
1
2
( |) E% E2 n  w; O: L, ^: ^3
4
5
+ T* H/ s9 Y3 A9 U6 ~6
7
* ]+ E' B4 @; o2 l8
9
10
11
12
13
14
5 h, @! L! g5 t+ }- Z: e- ?2 C15
16
17
" F3 D! `/ ?8 j  ^- }' t1 v18
19
0 W) d& N( X3 y2 ~! B% Y20
& k0 n6 x" N# n, K2 L21
$ s' J) e* e+ q5 v% y0 Q# E: ~22
" \4 \8 q2 h+ ?8 y/ L23
+ A3 T/ Q! ?! F24
4 R3 M. x0 Q1 T2 \: s  }25
26
3 }7 k5 g. f1 F% r7 u27
28
29
30
31
32
1 i( i; h* [6 H3 Z. O$ x+ ?33
34
! c, X, W7 u2 v35
  `. @( ]5 x% L0 u36
37
运行截图：
+ q; j, ~& X: g: J% ]
- A  n' d: I. I/ j# U& V6 z9 z
  p! l, `6 s8 G, C1 j: a& Z6 h方法二：将最小元素交换到待排序列的第一个位置
2 U8 s1 M4 N2 W* u
#include "stdio.h"
: p" e1 t( c$ K# V
3 ^( O7 Z, n5 H1 Utypedef int ElemType;

void BubbleSort(ElemType a[],int n){
    bool flag;
- L6 Z: q# C% r8 e) f    for (int i = 0; i < n-1; ++i) {
        flag= false;
& M& T& b: r* f$ E% |        for (int j = n-1; j >i; --j) {
9 a: C# d; `7 F5 k; ]8 y% {            if (a[j-1]>a[j]){
1 x& P' e& H' J* `4 B6 y% N                int temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
* D1 j% N& h  i) t$ Y0 ]: ?                flag=true;
            }
  v; Q; [+ m  E        }
        if (!flag)
3 R( {/ a. I$ Y+ H            return;
' B7 }9 S6 v# V) q: Q    }
}
6 P- E+ N! e8 s1 `, Q- Y6 T: x

int main(){
    int n;
% Z5 o7 I) H% q9 }( S9 e    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
7 h- o0 f9 @! W1 g8 h    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
/ F. w! w) L' [4 W' G( M( L# C        scanf("%d",&a);
- O8 d& o1 i. S* T+ F& x7 f; R    }
7 G) [  Z3 K/ ]+ a, ~  W6 A    printf("排序后为：");
    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
$ m& Q9 a4 \7 y3 r; k% l        printf("%d\t",a);
9 V( A  a& Y8 S/ k# c6 o    }
6 L: l% h% {* ]5 ^( M! U, W}

1
5 `/ v! Y8 {' \- Y9 n2
3
4
5
$ `: b) ]& n% ?) `. ?6
& i) m& H/ r) t4 v7
1 ~% @  ]# K6 q; z: ^" R8
9
) |2 Y& `- U/ n8 E10
11
12
+ T$ `8 @* H4 g13
. P9 }, D4 k' J$ `' n, Y& ~- X14
% s* K5 D6 W( Y0 S' l15
16
( Y" G- y, |3 H5 W7 D/ V4 ?# s17
  ]4 X( v6 _! P1 I18
, P4 D. [- P& o% ]8 N2 O! U19
20
1 t: U, z/ s: F9 n$ J' Z- h8 a21
) w& `4 P! ]) Q22
23
- w; S; w7 x! U: a- v9 }24
25
3 ^, p$ D- Z1 q7 I% n8 Y26
27
28
29
& |% d3 B/ Y* S% ?2 E30
" I0 W. Q/ b6 ~4 O5 u# y" i31
2 w9 \, E. {# z0 K  Z32
33
34
35
36
' c3 n/ G7 O1 D" ?/ Y; `5 c5 `37
! u( t. @5 S3 o运行截图：

- W" k( J' j3 N8 X; t+ {3 B( @
性能

7 z  E8 a. E7 r& P8 A空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
5 \. b- F/ G: ?: b2 z; Q% Q2
, [7 K/ N) c$ m! S" R- i )；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
0 J4 f/ E/ f1 p, Q  T )；

稳定性： 稳定
) o! Q( |# A# m- _( @$ Q) W
适用性: 适用于线性表为顺序存储和链式存储。

6 Y1 B, i) _( F# a. K; n. v3 K2.2 快速排序
* K: h3 h* K) O, O* @, \1 `图解（动图以后再补）
- \- x: z% T  E1 s* [4 h3 T第一趟的排序：
& q4 |9 m4 s: Z( n
第二趟：

第三趟：
4 @# F5 u$ Y) A2 ?

0 u; _+ k& S. O. s' |基本思想
2 ~) a8 l3 `  d" k
/ j( u) L2 U6 V& e# W8 }% {! J/ v快速排序的基本思想是基于分治法的:

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

; o& t8 U% z( r#include "stdio.h"
' N4 e& v- Y9 O; i0 s, V
typedef int ElemType;

int Partition(ElemType a[],int low,int high){
9 `$ \' a, o7 a" ?: r" Q    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;
}

void QuickSort(ElemType a[],int low,int high){
    bool flag;
! ^" k& Z1 n; e, f  W    if (low<high){
        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
' j' T  _& a8 [; |' s    }
}

2 m3 y* K  h7 H0 {: p: Lint main(){
8 R3 \* k1 _8 K7 I3 s1 c    int n;
$ p  S9 n  c) R4 Y1 Y& Q$ i8 ^    ElemType a[n];
2 j$ \( m- ~1 |2 h0 c) l4 h, M/ l7 N    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
9 n1 b; l, Q5 f3 R7 B- N; N        scanf("%d",&a);
    }
    printf("排序后为：");
    QuickSort(a,0,n-1);
8 l( O8 V& t8 R) }- s    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
- r! q. a8 t5 @# `    }
6 H# C  K' H" l, c4 A}


; T8 h9 P+ l& U3 b# ^% k1
2
; z8 n5 q& y( H- D9 T3
4
5
" P; T8 b2 C# N, k( K5 d8 x! E' M6
' r/ b& F' ?. l% c3 I7
" Z# X0 i5 @) I7 M8
& x) m% U# y$ v, h, _( c9
10
11
12
13
0 o3 F# x4 f/ T) V14
15
16
6 G4 n. n9 W: k! ], x" M" c17
, ~" c" b; D4 p18
8 O1 v' b, q* r" H; R/ A# N19
20
' l+ z+ Q0 K) K- i$ |. u21
; X  C6 L+ @& N, S22
23
24
$ b' g! ^3 U/ C4 y: L4 @4 }3 _25
26
27
28
29
30
' B$ G9 Q0 {3 J3 B1 z1 a* ^* w7 @31
32
33
34
35
* e; p0 K1 c4 Q3 R$ m) W36
37
. H  s: G% Y& Q) p: z" d) \7 t38
39
7 y' a# s! t/ Z$ O40
41
" B/ m# K% a3 ]- J7 T% W性能
  H* ]2 J2 P. A6 m7 f( w
; T, k+ x5 y& b, p时间复杂度和空间复杂度
1 s1 }0 I1 m7 p  u7 e0 s. C稳定性：不稳定

) L1 X9 t: x. r3. 选择排序
/ W. U2 L+ d7 G' b1 F! f3.1 简单选择排序
图解
( ]; Y# p, ]! n

基本思想

7 z4 C8 ~) N( T8 e9 @在a[0…n-1]中，将a[0]设为最小元素，设min=0
8 k9 H8 _  L7 h, X在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
* \" }$ @) @4 v+ Y3 E若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
4 d0 q4 X* t# d7 ^在a[1…n-1]中继续进行排序。
代码
" z3 R, }2 z% h( d. J+ W4 |
+ O: ?8 A1 m) b+ Y#include "stdio.h"

typedef int ElemType;

3 `, `1 w* I) o- X& E3 Nvoid SelectSort(ElemType a[],int n){
! u" }4 G2 Z# M( i5 U7 C- r/ ~    for (int i = 0; i < n-1; ++i) {
' I- b9 W6 g& J" b' J( z        int min=i;
9 N( Y( t" k3 Z8 H- m6 y        for (int j = i+1; j < n; ++j)
            if (a[j]<a[min])
                min=j;
        if (min!=i){
, t3 }: R1 t% l4 B            int temp=a[min];
            a[min]=a;
* y0 i$ Y) E6 V            a=temp;
        }
$ k/ e5 c$ n3 d3 r0 _0 e* F    }
}
% f' F- x! ~+ X7 U* L$ V
int main(){
4 B$ d4 }9 {: ~# R- O- S% ?    int n;
    ElemType a[n];
1 X$ N9 @/ [5 |+ D4 B$ d    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
, R" E" g# I; g2 ?! B" {    printf("请输入%d个数：",n);
( d. Q1 K, B+ m    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
' X4 g. f- l4 E( Q8 Q! d0 h+ b    }
$ ]* T' ^' d* A, d9 O3 e    SelectSort(a,n);
4 Y. z$ `4 H6 O/ H* w* U. |1 q% @    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
- u2 M, D, g9 ?' l- D( W( O2 r    }
}
  y$ L. @0 Q+ A
: w" g' J6 ^2 ?4 {1
2
3
4
1 @# Q* s/ B5 p1 r/ h; q, `5
6
7
8
7 X. K! c  |# U" j# S0 i/ }9
! D! ^9 c5 u) q  O% a10
11
8 W! m& u* t- Z9 b. O$ ?12
  t/ {. t" [* v! O" Y13
14
15
16
0 T- }) v+ w2 J5 ~17
18
19
$ Z: ^( T( X1 d& G/ C20
3 H+ l6 C: U& y6 G# P( t21
22
7 I$ w' s% N  S1 D23
24
25
26
27
28
29
$ F! ~7 y# K0 {+ j8 Y( u: w3 Z30
5 d6 N& d9 l9 l* b; P1 M2 E31
32
$ w1 g! m1 u. y/ ]0 Q1 x33
5 s  F- M( h; B( y+ k+ N* V/ e性能
& u1 \- ~+ N; u: Y- }0 g" Z
( b3 Q5 M! a6 s  z空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
1 G' M) p3 k' ?. b/ k( f2
)
稳定性： 不稳定
6 a# y7 _. v& j+ u+ x
使用性：顺序表和链表都适用。

3 m0 b: x9 g& T6 S' G) l3.2 堆排序
7 m" d& v9 U# V看堆排序的点击这里！！！！

4. 归并排序和基数排序
4.1 归并排序
图解
$ E: @2 @# \  q0 |" u% s2路归并排序

8 H) m* g! ]& |: L3 E2 D
基本思想
0 B0 [- G' ~" c: ?: x+ T
: ^. {+ N1 `, G. I2 V6 u1 j& `将待排序列分成长度为1的子表，然后两两归并，形成有序子表

然后将子表再次进行归并，直到子表的长度=待排序表的长度。
' m8 p! L' t  Y9 Z5 s0 b代码
6 k3 o! V5 b. V* |7 s
6 f3 J+ N+ j4 ~% H! L#include "stdio.h"
#include "stdlib.h"
5 _. F0 `, h% Y! p7 N: P% A
, l5 }3 U, x7 _9 {typedef int ElemType;
! ?/ ^8 @# `) n  i
ElemType *b;

void Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
    for (int k = low; k <= high; ++k) {
; I, Z, M' l9 L6 P- V, R% S        b[k]=a[k];
/ A! T1 o. \% ]6 e, c' s1 `    }
    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
; d+ [: C1 |- W; T        if (b<=b[j])  a[k]=b[i++];
# r; Y1 V" ^5 A+ e        else a[k]=b[j++];
    }
+ Q6 m- C2 E  r5 H% }5 g    while (i<=mid) a[k++]=b[i++];
2 Q3 U' O) |  u! l$ R    while (j<=high) a[k++]=b[j++];
}
/ y9 W& i, r2 w) j
% S/ T' E" z  R( Vvoid MergeSort(ElemType a[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
4 t* [3 C+ S3 R        Merge(a,low,mid,high);
    }
5 n& s5 E* c8 u9 y, U1 E}

( r. Z9 [" a& P* {- Bint main(){
    int n;
3 g7 m; \9 W+ Q% N" A% x. }    ElemType a[n];
    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
+ g1 K9 X# P8 Y* e9 c/ I        scanf("%d",&a);
( r3 l$ L1 m7 a4 l/ N    }
; W& V+ \- S7 U    MergeSort(a,0,n-1);
0 F% n6 L! {6 [( e& I: Q    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
" U4 |) ~+ m& J+ @3 L    }
4 f- k; C& b; o- y+ W1 g! ~}
, |9 S% D2 o4 @' x7 |
) e% G. Q9 E8 ~" n
1
2
3
  r5 _+ U0 u; ^  I+ m4
0 D: Z8 K, G. s" p1 r5 g) t5
6
7
& D6 C6 G, O" [' Q9 G8
- N& {0 x1 W. I+ O9
10
11
12
13
14
15
16
17
18
, u- g! G4 U. a  r: V19
20
21
6 }- q* m' J5 D& {4 J22
23
  h* b, t/ J- o# ~  V" y24
+ a5 b7 [( q6 D- m' g& ~& y0 Y25
26
5 R/ _+ |" C+ r' g27
3 m/ j4 w; `( [0 H28
29
30
, Q/ {9 S9 s# g# f6 ^31
! T& ?0 R3 `3 {& [' ~5 p32
33
34
/ ~( O$ a0 N( e! W& |: x35
3 S: V# `2 r7 v36
7 x# C7 y5 q$ u( z, t37
38
9 J: `6 {' g9 P7 I( Z39
5 J: D- @- g% K0 a8 G' v40
41
$ [. Y2 V/ d) b& \: V6 O42
: O$ w/ S- h. w, F$ H43
- M# t0 Y4 y5 w* g2 y9 D" i; k44
45
/ i; d5 q( H8 L+ W: E% |3 A( m46
" B1 n  E/ t7 |/ R性能

空间效率：O ( n ) O(n)O(n)      创建了一个数组b
9 h. F/ `/ `& E2 _* t4 }时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
' o% F7 w3 ?: i- I: i+ ?k
​
; j# N5 |2 \# b+ o n)  k指k路归并排序。
稳定性：稳定

4.2 基数排序
* W( U& u) \  B  B) U* l# x图解


/ w, x% p$ t+ j; m) b0 y基本思想
" z( N: G( o* t
将各个位数（个位、十位、百位…）进行对比。
为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
( R  \  ]1 H7 |4 Y
性能

空间复杂度
  u" I' ]! `7 G0 P! @, r
# D& t2 m" D, s2 w+ V/ \4 `时间复杂度

9 c& F: w! g( ^( d( x+ _& x  S
稳定性：稳定
. S1 N  C4 S& Y- S
5. 内部排序算法比较及应用
$ U* c9 k2 G% h5.1 整体比较
) ?& ]0 u8 `, J' K! U, l
; M2 J% ^- ?9 Z; \4 m
5.2 时间、空间和稳定性


& G* J5 q) P& F, L+ T6 I参考资料
( i" V/ F7 I" U" K. z《王道：23数据结构考研复习资料》
8 _( Z( K, W) E' G* _" L  @2 M————————————————
/ ~% [, _9 Q. N/ i7 Q版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% S2 S& q0 l5 ?* I原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678
7 v# k; q" K$ v" Z9 a8 d

---

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

Powered by Discuz! X2.5