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

杨利霞

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

排序
1. 插入排序
1.1 直接插入排序
) j, y3 A; Q, n: b1 V1.2 折半插入排序
1.3 希尔排序
2 r( J+ K/ }4 y# v  [: u. k2. 交换排序
" U8 d1 G: n2 {7 E0 f2.1 冒泡排序
  m  U; @; T' C; B  [2.2 快速排序
6 e0 M$ Y  x- v3. 选择排序
/ B: A9 l+ J. [. D4 `3.1 简单选择排序
3.2 堆排序
2 b$ X" `/ b8 X& [4. 归并排序和基数排序
4.1 归并排序
4.2 基数排序
$ Z1 V! E3 y7 ~- z+ h$ I; ]) [5. 内部排序算法比较及应用
5.1 整体比较
5.2 时间、空间和稳定性
' L) c4 T9 o. q2 e, s# [( V参考资料

内部排序：是指在排序期间 元素全部放在内存中的排序。
( F) `3 K$ ]3 [6 `3 a内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
1. 插入排序
1.1 直接插入排序
图解
5 Z; w: v: Q0 J) g3 K
2 U! ~! m) g" m0 E
基本思想

1. 查找a元素在第1 ~ i-1中的位置k
2. 将k ~ i-1位置上的所有元素向后移动一个位置
+ y: U" h/ e3 F3 v) C3. 将a复制到a[k]

  o9 w0 e% {& Q9 j. q0 W" \

代码
' I  Q: m+ |! C0 D, [
/ D" |# s+ g& I& ^+ E方法一：

数组的下标从0开始，如上图。
5 I* m9 M! ~, [8 [( e
#include "stdio.h"

3 U9 p$ F+ z! V) h0 Etypedef int ElemType;
6 |- N8 ^3 v* N9 e* |$ P4 `6 p+ f
( G$ _& Z1 c2 c! `. |% q3 b) i+ D4 ]void Insert(ElemType a[],int n){
- F' ~0 o5 i0 g7 s+ n+ [# Q: k    ElemType temp;
/ F* f/ Y9 J- F& k% y    int j;
6 u. K1 t4 K4 M* |, A% ?" K    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
        if (a<a[i-1]){
            temp=a;                                                               
" g  A* }5 k. E, \* T$ s            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
                a[j+1]=a[j];
1 U" f0 D! _1 \: v) f            a[j+1]=temp;                                                       
        }
    }
, T, P. V" E1 v}

1 ]7 e! s5 C! k2 U* I8 U* g9 |6 Iint main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
" w: e$ i8 ]; ^, o: v% |" b* M; P! `    scanf("%d",&n);
    printf("请输入%d个数：",n);
4 h8 P/ s+ g) |- l; [    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
7 [4 ~8 j+ q& T; E3 X$ H- X    Insert(a,n);
    printf("排序后为：");
) m" x, q4 }3 ?! U# q3 }6 p+ ?+ Y    for (int i = 0; i < n; ++i) {
; v2 t0 {8 N( e! r) `" N/ e) F        printf("%d\t",a);
2 c8 H- b' Y* S; H* T+ S    }
}
% D' |! K1 K  n; G9 N4 U' A6 O  W0 V
( q& P7 x: O% Y' W* ^! w1 ~2 M1
. Z3 h5 {* l2 \& Z* |2
3
( H% Z6 v  Q$ H. ?4
% f- _# L7 V1 z, R: [; D9 T5
) g- Q/ t$ [% y5 x$ }& v6
7
/ n4 f9 v4 W) h' e% k8
, V! U6 G8 R2 P9 R1 n+ ^9
) `2 K' @% n; x) y10
$ N0 v& a9 f( P0 y# _11
+ d" N  N, m8 r6 h1 a5 w$ }- h3 C12
9 C  x2 O: ~# T. S" A$ \13
14
15
16
17
3 m( T+ A6 P- w18
4 b) l6 b" y9 U  D19
20
21
22
" F! F8 ^$ D' Q23
8 e( f, r+ X5 \/ v" U2 [( g0 X24
! j  \/ {- V- C4 f3 p25
! x. A& d4 n* Y3 m$ k, ?( q26
27
5 @- R* v0 ]$ C' @# U28
29
30
31
2 Y; S* }+ k6 A) y& J) W' [2 N32
方法二：
4 g3 n% R' L) g5 I' s) Z( z' f- F: w' X


#include "stdio.h"

: b0 ?0 G* h8 a" ~& rtypedef int ElemType;
0 f% C  t: f% u8 M
7 N  ?& _$ Z- Xvoid InsertSort(ElemType a[],int n){      
$ D' I* W) n6 R: n. D# M7 \    int i,j;
    for (i = 2; i <=n; i++) {
        if (a<a[i-1]){
            a[0]=a;
" D/ D% a1 }& l8 v) U/ _            for (j = i-1; a[0]<a[j]; --j)
                a[j+1]=a[j];
            a[j+1]=a[0];
        }
    }
}
% c4 E8 K5 m$ B+ tint main(){
. L0 _) c  ^/ R2 S  Q    int n;
; w# X1 m/ _& q  E0 V9 N    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
2 w7 C6 \7 ?3 J5 X5 i7 m7 d0 J3 X    printf("请输入%d个数：",n);
9 Z' u$ O% {- B+ ]8 @4 W% a    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
$ R# i8 V4 m' D7 L  T7 _9 B    InsertSort(a,n);
    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
  p" z) _) t9 F9 b1 j    }
2 d. S0 M) F- l/ F8 e}
& x' C4 S9 {1 X/ O* C3 N9 o
8 I5 \3 |+ x, L4 X+ T1
% w9 \1 M/ S$ K/ n6 {5 O* g+ S% _2
3
, [& S  V8 u1 m- Z4
5
6
7
8
4 u4 E4 n! T" m$ D6 r& t/ s- u9
10
# f# ?4 o. j9 r0 w) k. D3 e/ Z! m11
12
1 [6 e" D% {/ O! n13
14
15
16
7 Z$ D/ l; n5 V8 h' E+ [17
2 K+ r2 l! r& [5 w18
19
20
7 |' B! O) X- }+ F" J7 d21
: h, G' d9 Y  J( |22
0 _7 O& i; L8 g23
24
5 ]4 |& b& q3 W6 f0 G25
26
27
2 A! y9 n. X+ I5 k* W28
29
30
算法性能

空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)
) u6 z  ?$ p1 P* Q3 Y
: s( R4 M5 ]8 a% e, R5 p$ T时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
: M7 _  @9 |, \# \3 z4 D) E! F- c' F2
; q3 t( L7 v! J )
9 H4 J& A& a7 o
. b1 r' k* J1 ?4 ~* v6 L" j( @/ o; f
稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。
% F* r* x& v: r2 w3 q
, H6 Z7 y7 M/ i. ?) p1.2 折半插入排序
# z( K. m2 O- n  V& a) ^图解
第一趟：
) n$ M3 g* l3 b; Y+ R, K
( A8 x3 C& A* C, h2 p  ]% [' r第二趟：


$ y# ?4 u1 A# j% o第三趟：
: y" m2 l- H) q( f" i
第四趟：略
第五趟：略
0 z$ k, j8 `- P& F) U: u+ \0 r/ P
基本思想

与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
; n/ c' M# H# |, N取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
代码

#include "stdio.h"
4 Y) C5 I: `4 i( \8 T& ^. v/ [
) k. L+ r* S. r, o) M  u' @typedef int ElemType;
0 u1 P* a2 V! i% y2 U# G
void InsertSort(ElemType a[],int n){
    int low,hight,mid;
9 O8 t" p7 x3 v- R, x( d    for (int i = 2; i <= n; ++i) {
        a[0]=a;
  E, U# T  _* w/ ~9 L9 j2 s        low=1;hight=i-1;
        while (low<=hight){
            mid=(low+hight)/2;
! e- ~1 W- j, h0 Q- b            if (a[mid]>a[0])hight=mid-1;
- B' E1 t, l/ V6 y' z& [5 `            else low=mid+1;
        }
        for (int j = i-1; j >= hight+1 ; --j)
2 J8 t6 i9 C3 b# f& U. K            a[j+1]=a[j];
        a[hight+1]=a[0];
1 a! t* b! B' g    }
}


; n( j3 t3 W2 @5 N( u  A( Pint main(){
    int n;
    ElemType a[n];
. f1 R, T0 J) B    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
6 R! r0 t) `' z; f% U9 i0 V        scanf("%d",&a);
    }
* J7 ]# K# v; l* a    printf("排序后为：");
    InsertSort(a,n);
, G. o+ R! K! A0 r. e4 q- n
! k( |& D, w# @3 J1 F  q6 H( x( F    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
* |6 V, k& W" \! h    }
}
' g# |: k" \) B. }  L& F
' S7 ~! s3 A' v1 T1
2
9 u1 e" V5 t& X" `- _3
% D9 E+ ?. T* \6 i" n. F% q. F4
5
, L9 y! t9 d% Z, [6
7
* J$ N4 f/ K6 S- ]& t  _) W' v8
9
10
! u- c: q1 G, e, s9 _, R9 u11
12
( E& d9 L  e- g  c4 |9 {13
14
3 c* q+ M0 e0 z$ f15
16
17
% Y8 f. U: H. L, C* Q7 P18
" y$ _' V" m; {$ j: U19
, n# P5 J" V4 U2 A! d20
21
22
23
. ~3 p' x3 l4 l" m/ W. u24
" u" B6 ?8 `( w, n' J* h- x% V25
26
5 Z3 R& u. F  i7 n7 M; j27
28
29
30
# V+ n, m, G0 \; _31
32
33
34
35
8 x, V  Z, g! h- T36
37
性能

# w' k) v- [; [+ t. p4 E0 F9 X空间复杂度：O ( 1 ) O(1)O(1)
5 T% \6 d) K$ O( u$ S" m时间复杂度：O ( n 2 ) O(n^2)O(n
, G5 s' y1 K% T2
)
! \2 ]  W6 h; @" [- t稳定性：稳定
适用性：仅适用于顺序表
) D+ u. q/ r+ b& f5 q. ?+ c8 F6 H
1.3 希尔排序
4 A: j+ u( t+ B图解(动图)


基本思想
# Z& S* I) t% R) o( a
先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
* \& U9 s" Q: l
4 F- A! D% V" B代码
2 |. d4 v$ z; @9 |  M8 b
#include "stdio.h"
' F% z1 f- H  P' `
typedef int ElemType;

void ShellSort(ElemType a[],int n){
! @2 H9 I0 v. U" `6 @0 t    int j;
5 h. w. D! e. K1 U& O    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
, ~7 t$ Q/ D% Y; l# m' W4 D, \4 a9 [            if (a<a[i-dk]){
                a[0]=a;
                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
2 U+ U0 e' V8 M6 r! c7 r, e                    a[j+dk]=a[j];
% @0 T: T- k3 p                a[j+dk]=a[0];
" Y" @4 K% ]( |5 K4 G- r$ l            }
        }
( N# M% k9 ~- M; U% u    }
}

int main(){
% U' z; k% j+ k# e  H/ k  v1 H  n7 Y    int n;
1 O! y: _: x! X1 b    ElemType a[n];
    printf("一共有多少个数需要排序：");
. [7 L$ E- d+ f2 ~    scanf("%d",&n);
7 h" g  Y, `$ ^    printf("请输入%d个数：",n);
& H' ~0 q& q+ v    for (int i = 1; i <= n; ++i) {
) o# T2 I7 S: \" f5 M/ s7 i& r2 P        scanf("%d",&a);
    }
* S3 [6 \+ M: s3 z+ f6 F/ X    printf("排序后为：");
    ShellSort(a,n);

    for (int i = 1; i <= n; ++i) {
1 M0 n. `7 n. j3 m6 ^( {2 j        printf("%d\t",a);
    }
}
3 f4 d% \* l8 j
1
2
3
4
5
% |5 R4 p3 B$ @6
7
) B+ }. @& x, j2 X  G" d* i8
9
10
3 m& R4 v  G1 x" P11
* u  N) T% I, n$ \8 x. y' J12
13
14
- r: |5 n6 n* B3 s8 V. T15
16
17
! i; d. G8 s' F" b18
19
20
21
22
: }; a& ]' _# }1 S% Q# Q* S( b6 h7 d23
) |8 \: i' d7 F; q  h24
25
* p  T6 M6 }5 X/ m7 }26
27
28
. i! @3 N1 ?/ O: j, p29
, H4 M; F+ N( W! W30
1 V' ?! J, N$ E+ D3 t31
% G) R+ j* F2 O  A' C  {32
33
34
* ^# U' V. |" g5 D性能
; ^4 A& G, _7 F$ C, _3 |
* s9 Z$ s  z& {# q空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

; Z2 w1 q& j" ~7 O+ M  P8 N时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
; u0 r5 o, \/ C6 ~: k1.3
)，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
2
' f$ Y2 j2 K% z- @6 A" S )
9 h4 D8 S4 @9 H( [! _! V
& b, S/ _- H+ y2 G* o! Z/ x稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
6 y/ U3 W& O% ?& y* E- ~% j  J0 y$ ~

适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。
3 P$ q6 C8 H( j; o% `8 _
2. 交换排序
2.1 冒泡排序
1 P4 r3 I6 ?1 Z* ?图解
+ d& M4 f  @; k# Z3 T
6 ], @5 }, V9 f
基本思想
; E$ u' O! Q2 |6 w' ~6 T
2 g2 b! O) t' ^+ q9 i. `4 ~从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。
: a$ k2 {$ Z! K, d. }! ?8 i
代码
* d  }3 L/ c' u
方法一：将最大元素交换到待排序列的最后一个位置
- i& E2 D9 \: k2 ~0 \4 c  ?  _
; M* m6 z  O5 Q  o#include "stdio.h"
, [6 r1 o! T& E9 c$ ]8 A& ?
typedef int ElemType;

void BubbleSort(ElemType a[],int n){
5 g. f6 A7 `4 B2 V' [  `    bool flag;
    for (int i = 0; i < n-1; ++i) {
        flag= false;
* N: n/ F2 H6 D: `0 i& \2 ~! e- I        for (int j = 0; j < n-i-1; ++j) {
            if (a[j]>a[j+1]){
, p1 B& R7 k6 P, E0 ]  n                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                flag=true;
( G- j/ \; N0 i2 X: Z4 t3 k            }
2 ]4 H( z0 k6 i1 b: U  T        }
        if (!flag)
            return;
    }
% f; M5 h/ K6 |  Q2 w! n}
' S$ f: y: ?  R( N6 e" k
6 p% N3 r- Y0 Q! p0 `# J$ e
( ~9 v+ _! N. N. ^9 Yint main(){
    int n;
1 p0 _- ^1 k3 k6 F6 ]    ElemType a[n];
. p+ y# g7 N% o6 s& D$ D2 V    printf("一共有多少个数需要排序：");
  z# K" }. O% N6 s: [" Y* I    scanf("%d",&n);
    printf("请输入%d个数：",n);
- g9 _% P9 t- f4 J    for (int i = 0; i < n; ++i) {
- K) K' M2 q* e+ D8 u5 X3 x        scanf("%d",&a);
    }
    printf("排序后为：");
* b# k; b( g* U5 D7 u& ~. x+ O    BubbleSort(a,n);
4 j# F( X$ M- D7 E9 s( o    for (int i = 0; i < n; ++i) {
' ?" o3 u) g; U# s* p) b        printf("%d\t",a);
    }
}

1
, t3 i6 S) b& c2 Z2
3
" s: g* C+ A  E0 K3 J4
5
5 O* ?# P$ \/ }6
# p' U) Q4 t. k+ D5 ]# [+ M7
8
9
  t  |/ g. F8 b4 [2 |10
11
. X. N$ [! j: @3 H7 z: @12
13
14
- N; {* A$ T0 H15
16
17
3 t; n6 m4 f7 A! D18
- }3 |2 M0 C2 Z% Y9 _19
- i$ r! w: D+ z1 _. a% S% ^; l- t20
; W7 n7 j0 s% ?) b4 w21
4 z% w$ s' y3 j2 O0 {22
! V& }% n. ]3 N6 z* r23
: \5 W; j$ b7 N- P, f  p24
25
$ C1 W- l8 K$ m" N26
27
28
29
. R# l$ o! g% ~/ H1 T30
31
32
33
34
35
36
37
运行截图：


方法二：将最小元素交换到待排序列的第一个位置

#include "stdio.h"

typedef int ElemType;

; _! w* L4 k1 @; m) Jvoid BubbleSort(ElemType a[],int n){
    bool flag;
) X1 _3 o( b' Q$ \$ c3 r# o    for (int i = 0; i < n-1; ++i) {
) e' u' u6 h, ~2 I        flag= false;
: _1 A1 K. n8 ]* ]        for (int j = n-1; j >i; --j) {
4 e# C& @. I  j3 A1 j$ T4 p  z            if (a[j-1]>a[j]){
                int temp=a[j];
( s: Z3 K. A9 |% w                a[j]=a[j-1];
                a[j-1]=temp;
                flag=true;
1 @) R+ A; e  M8 m' h2 i            }
        }
) Q7 ?6 C. R8 x: i) b( R8 X4 r        if (!flag)
2 j  x) T  j$ d& Z+ z( w3 w: Q            return;
: L0 p. A; W# t    }
8 Y& |) M0 ^: c2 v}
8 Q2 O$ f5 e) a3 C! e; F

int main(){
    int n;
6 q0 A# D% f5 u9 C, Q! K    ElemType a[n];
    printf("一共有多少个数需要排序：");
2 ?1 e4 P: q5 Q/ u: x    scanf("%d",&n);
5 i  n: O' |: P! f' a5 e    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
0 j, j9 p; X8 q8 g* g" e8 c6 ~5 E    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
}

; I( f! \6 ?# N! L0 t- l% c1
2
6 ]2 Z" Y3 d' s6 I* ~  |3
4
+ a) z8 @; n! l' Y% |+ @: I5
6
% Y% l" S* W! }* R/ e" y+ z7
8
, T" g# z' J8 ?9
10
2 q( @8 C/ c+ ~5 l# Y11
12
13
* t( W1 h1 ^3 N8 N% Y14
15
16
17
18
19
20
21
22
% t5 ^* Z& ^. h23
24
25
- @+ t- [: ?' ]4 ^7 s0 s7 }26
27
6 F# X, f/ T: X+ C, ~9 X% \28
" H& y) l; ]+ |29
, C# f4 C6 [1 T30
$ z: p, I) o9 q* m+ b31
: i1 z6 N8 u( Z. W1 S32
5 Q( w7 [; P- r7 V9 w" g33
34
0 N! }" N0 x* W$ S35
36
37
8 Q# y8 o0 b7 R6 T& {! `6 z% o运行截图：
! l0 }+ \4 Y' q% {5 K

2 L: E. d+ _! A: }性能
& @( k( k$ C0 Y* P3 f$ n$ |
. c% H' o" b7 k; Q) i4 W0 Y空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
0 V, C0 W: u$ p- ~; A
$ c+ L' D$ Z' j9 x2 n时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
2
)；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
)；
5 J7 e- d& P8 t8 k9 G
稳定性： 稳定

' s: J1 ?0 o" q适用性: 适用于线性表为顺序存储和链式存储。

* p, r0 z/ h! L2.2 快速排序
图解（动图以后再补）
9 V" h) s- _( g6 k1 J第一趟的排序：
6 c, v8 a1 T9 z  o
7 T( m& p4 s3 L第二趟：
- `5 m7 k9 y6 a' O
第三趟：
9 d2 |; j9 s* B

基本思想
0 _* R8 H4 @6 h6 B3 S5 S
快速排序的基本思想是基于分治法的:
& E( Q# D; n( D- b2 d
在数组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步骤排序。直至所有元素排序完成。
. Z- Q7 O( w9 k! ?, O4 g: H代码
% z( E. u* k/ s
' t7 x+ m- h6 F# n#include "stdio.h"
4 E0 H$ w/ [- e) ?: u  j
typedef int ElemType;

int Partition(ElemType a[],int low,int high){
2 l. h/ J6 Y( R    ElemType pivot=a[low];
3 d; F4 w: a# g# r' l    while(low<high){
  F5 K& ~  q# m        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
        while (low<high&&a[low]<=pivot) ++low;
! \* I: ~2 @: V$ h' H        a[high]=a[low];
$ j7 A# `: F: b! E, O3 i    }
    a[low]=pivot;
; `1 s' T  i; b7 E8 V! r    return low;
}

1 n& W6 R$ Q$ w- ?) z8 h- zvoid QuickSort(ElemType a[],int low,int high){
' ]4 d# x  ]- F" R. n3 A, H  M    bool flag;
    if (low<high){
        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
0 j! d( L0 K: ~( l$ }7 X        QuickSort(a,pivotpos+1,high);
    }
9 ~$ q6 k9 l) B) `4 t- c, S) V. t}
3 S4 g9 m( c" W( ?) z7 g8 q; P
6 m) P& U, d; V; W0 Vint main(){
* z+ e* w1 f1 k- A; v: k    int n;
" t6 v! T( V4 n7 K+ F0 n    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
( X  m4 E8 s, K5 O4 q$ A* ~/ v        scanf("%d",&a);
" n% ]9 y5 Y9 L& S8 P5 C) U% O    }
) x! X# [" j' |2 s    printf("排序后为：");
& H" R( A, e' V, ~9 V    QuickSort(a,0,n-1);
* ~9 {4 w; @/ r7 K" h    for (int i = 0; i < n; ++i) {
, B, A2 Q9 p2 `0 @4 _        printf("%d  ",a);
    }
( R* h% n. @* c1 O' i}

- l; J  G1 P; r: b
1
/ @$ o% ^/ c8 m$ O/ L! P/ P" `% `6 p7 T2
' Q1 U$ t: {5 G1 Q0 Q! ^8 T0 Z3
4
5 M- y( u! _" n' m3 y. X4 K5
6
* d, C2 y9 e( O* o& H7
8
9
2 O4 x# S2 T* o. m$ E10
+ H+ K* |% o- n' W11
12
13
3 W- W, e2 g) ]14
15
/ Z7 t4 R, P8 J* r16
9 K. D- M! [$ }17
1 D2 c( u/ P5 E, g18
, O" I/ [0 G( P6 `# }19
20
21
22
23
* D( y$ }* Q% j/ y24
6 Y" p3 M- v. j7 n25
' b5 ^" R) L' G" R# L1 \- b! D26
! a0 {/ f7 _3 S* L& q7 z: ]27
28
& Z3 B3 a; N' }$ l3 V  g29
$ O7 R1 _8 F0 \( m0 C2 B3 p. f30
2 K* J+ b! i7 a' Y6 F6 K31
32
33
! I% u' y9 `! o6 G& e8 d9 B( H1 i! j! e3 ~34
7 s; v/ B0 Y0 J0 ^35
36
37
38
. {) O9 K/ j& ^/ S& H6 l1 M39
40
41
" [$ X; u+ [) T( a! i# l3 N+ }性能

" S$ F: q- J; q7 ^时间复杂度和空间复杂度
稳定性：不稳定

& a- ~. B8 @+ L# L3. 选择排序
3.1 简单选择排序
图解
0 [+ q7 C' f3 x
3 q  w/ |4 G. L) k* z
4 W6 |- [0 ~. r# S& E# U9 R8 k基本思想

  I2 b* f/ C4 c' B+ Q在a[0…n-1]中，将a[0]设为最小元素，设min=0
在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
$ W7 s5 y8 D, I$ b- K5 A/ u若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
9 N. x, t$ g7 s; v: N2 Z0 }, C5 U在a[1…n-1]中继续进行排序。
代码
% k# e7 j/ j; L
#include "stdio.h"
2 F! @& d; K+ l0 T" t( O
9 `5 ]& `2 H  t  j& jtypedef int ElemType;
# `! z/ F2 T+ k! |& r! F1 h
void SelectSort(ElemType a[],int n){
: b( ~1 _& r( Q    for (int i = 0; i < n-1; ++i) {
( T( i& v3 Z( F* y/ _        int min=i;
        for (int j = i+1; j < n; ++j)
            if (a[j]<a[min])
- @0 P7 r' S. }                min=j;
* ^2 ?. ^( r5 u7 N8 h( M8 n        if (min!=i){
9 A! i4 ^( F2 m! V. w! R; [            int temp=a[min];
            a[min]=a;
            a=temp;
: D4 {6 X6 E8 l  @8 A5 l% l        }
0 D1 n7 Z+ y; @. Z) e    }
}

int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
- u- k% d5 Y( d8 B    scanf("%d",&n);
    printf("请输入%d个数：",n);
1 k9 R0 X+ D$ k; X    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
+ R) P( f; p& L" U    }
    SelectSort(a,n);
- g( }2 [/ V( w9 Q* u* B9 p9 L5 v    printf("排序后为：");
$ M5 }! h# R, e3 V! p    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
}
4 F4 s+ |$ e/ Z5 z
+ }2 C- p; t/ P8 p0 M1
" \7 U( O( t/ O3 A8 \2 A& D# C- a2
3
! v) ?, T& N- {; j. R' [; p4
5
- K4 z2 f6 J7 w4 K. v6
7
8
4 K# B2 V. I: z7 M* F9
* L0 `/ j- r$ Q3 i+ y10
11
3 w/ e1 _6 @0 U. D. F& B) T12
13
14
15
16
17
18
* j9 r+ ~) a* S* M0 [8 O19
20
6 W; x* b$ U  o( M* |- n21
22
23
24
25
+ S0 E, r* s. \& G26
: B3 D5 ?) H7 n- b: S27
; w( R: W& Q3 [0 L: x7 V" e28
29
( c6 f0 B1 J0 `8 r30
31
32
33
, u8 p7 l# S- j3 j4 ]) H' [5 j/ y性能

空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
, ?" P% F  O6 d2 L; d- C2
4 _; R9 J) L2 y! V0 {6 g )
* l& e' q# u" E) t! D8 N稳定性： 不稳定
' q* X" ]: c  }, D, D
: C& V' g1 {) x) P4 W使用性：顺序表和链表都适用。

, |- M. M, f% _; D7 F2 m4 n3.2 堆排序
看堆排序的点击这里！！！！
6 I/ @0 u  \( H& @
) `5 O7 c6 Q9 l% @3 e4. 归并排序和基数排序
4.1 归并排序
图解
" F% T6 _5 Y9 t6 F( D0 O$ J2路归并排序
) l" n" P: }* ]0 {, F) t
( r  z2 w- J5 f1 t8 U0 ?) c' \5 O* p5 \
' S! T5 ^' w( ^# N0 O基本思想
* `4 x' Q/ B, [' z; R' v
将待排序列分成长度为1的子表，然后两两归并，形成有序子表

然后将子表再次进行归并，直到子表的长度=待排序表的长度。
) I( ?7 ^% P2 v! H  d/ E代码

3 d& R$ t2 F4 S6 c+ r9 p#include "stdio.h"
" B4 Y. I" C' p# b  b6 I6 q#include "stdlib.h"

typedef int ElemType;
/ |1 K, _+ p5 [
$ o# H7 l7 a; b# uElemType *b;

6 b3 v- ^! G2 M; w% Q5 B  ovoid Merge(ElemType a[],int low,int mid,int high){
, O8 M* |$ a( w7 i7 h: D    int i,j,k;
    for (int k = low; k <= high; ++k) {
        b[k]=a[k];
8 @: j% Y1 ?0 z7 U. i    }
( \* F5 q; a: I; p* }3 v/ A    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++];
    }
    while (i<=mid) a[k++]=b[i++];
    while (j<=high) a[k++]=b[j++];
7 S4 I& N. |- s6 Q! Y}
9 u) Y, b0 |$ B8 X$ i
0 c' j6 D$ }2 r2 u0 f7 a& cvoid MergeSort(ElemType a[],int low,int high){
    if(low<high){
! [2 D: A' p3 Z7 ]4 o" T2 v        int mid=(low+high)/2;
+ |, ?% N  u" Z3 E6 L4 l" ~        MergeSort(a,low,mid);
' q/ k( Y; @$ j        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
}
1 `3 f% j3 k# `! h" R" q3 M# k
+ |5 Y- l: H: p5 N# L! jint main(){
    int n;
* \2 l' }( F( ]. A) G    ElemType a[n];
    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
    printf("一共有多少个数需要排序：");
! G; X1 @% ]* @$ R6 Z$ d* o    scanf("%d",&n);
9 _% |0 p; T+ b# r4 t0 m- S    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
2 Q& k" h4 }5 k+ i" X        scanf("%d",&a);
* g: P- u0 c& q, V5 A    }
    MergeSort(a,0,n-1);
    printf("排序后为：");
* c0 }/ T8 `0 N  t4 m  k    for (int i = 0; i < n; ++i) {
1 j. G4 P$ i2 U' S, s        printf("%d  ",a);
    }
}
3 I# C- T( C# K" D8 F. d2 v' a; n

! ~2 I% `; q9 {. g1
2
3
4
- Y% a9 d/ x& k* `% f% _5
6
7
8
9
! y) W0 \7 a1 f6 \$ g10
11
12
, j$ G$ I- k6 o/ q13
14
( k6 [, ^2 y9 E. ~15
16
17
18
19
' ?0 U0 x9 a- O( m& \% w# B. R20
21
22
. J8 [/ f" p; o/ G* a3 X23
24
25
; O. C0 D2 y8 p4 k9 Q" S26
7 H! n( V" [, b$ J5 O' c27
28
& o# y1 \5 H% o) i) J& m, B29
: m0 D' j4 x/ e  h30
1 N1 ~/ M' q2 |2 t( }+ n' l31
32
5 N/ @3 X' G( Z' k33
( y2 S5 j) \1 Y: S  n3 R3 c% I34
' j8 m' t+ x% m) y35
36
8 C- }) C" x; f0 b37
" X, Y' ?. [4 m2 E' a38
39
40
41
! {2 J' V: |4 `: U* y: f# k42
6 ~" H6 x# _! |9 g$ ~43
44
45
46
+ X6 ~: o8 V9 ]( F( |性能
- r! T* K9 b( p9 r  D* O/ A' W
9 E- ]) n) S9 p. h0 @4 p空间效率：O ( n ) O(n)O(n)      创建了一个数组b
时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
; {! o1 D/ p  r* i; x# Y& E​
n)  k指k路归并排序。
  H% W3 I8 o7 h# ~8 t/ x稳定性：稳定
8 c: c: j6 m* [$ g
: r! o! S7 D! ^. l" W8 v4.2 基数排序
图解
- N/ e' P( y9 v8 g; M
# F, s& c: s6 j3 C: H8 X/ C
基本思想

+ x0 K" A" u. \- k) [/ t将各个位数（个位、十位、百位…）进行对比。
为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
- u  J* s* H7 k: }% ~8 u
性能
$ D# M7 c$ D) V2 I8 ]9 v" x: D
% i/ t$ E$ p- \# z空间复杂度
4 K# ~- W. e$ }+ V) c/ z$ L$ \0 I
时间复杂度


稳定性：稳定
" H& ^% r; J' S' d. U5 {% \
5. 内部排序算法比较及应用
/ H) s# J. G. q0 ~' K' z( D  j5.1 整体比较


) W; i* T/ J! e  f, h8 E5.2 时间、空间和稳定性

; K3 |$ H& I- V" W( Z
参考资料
《王道：23数据结构考研复习资料》
( q" B: k- y1 m: t5 b& ?————————————————
版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678