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

杨利霞

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

排序
1. 插入排序
1.1 直接插入排序
1 M4 t$ k) S' x! G- j( {# k) i1.2 折半插入排序
) a3 I7 S2 h! B2 u1 L* q' J; R3 }" y$ F1.3 希尔排序
/ \4 h; }/ ^' Y2 `5 j$ W8 _2. 交换排序
2.1 冒泡排序
, C+ z' _& U3 r) o! Z' D+ J; v2.2 快速排序
3. 选择排序
3.1 简单选择排序
' Y2 ]( J  p6 I+ P# _+ `8 t3.2 堆排序
4. 归并排序和基数排序
& K: Z% d' M: u* s2 K4.1 归并排序
4.2 基数排序
8 u+ E, F. k; ~- w/ G9 I5. 内部排序算法比较及应用
5.1 整体比较
5 V% U8 U, h1 ~- t9 t5.2 时间、空间和稳定性
1 J2 U2 L' C0 p( H/ [# R( l. m参考资料

) U1 T) w4 u. r/ w内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
- e. T$ j5 ~6 i1. 插入排序
4 K* w  b/ b. J4 x1.1 直接插入排序
图解

5 y) G* Y6 _, g; n
( i6 s0 W" d, ^; `基本思想
" A+ V- N' M5 c! a0 I( f9 D
1. 查找a元素在第1 ~ i-1中的位置k
2. 将k ~ i-1位置上的所有元素向后移动一个位置
3. 将a复制到a[k]
; g( D( U4 z9 r9 S) U  ]4 {


* O2 d* L+ j' R" d1 w$ F5 F1 _0 q代码
* ?2 K; [) r8 [* S
方法一：

数组的下标从0开始，如上图。

* D  r7 [3 C5 J: Z#include "stdio.h"

typedef int ElemType;
; Q& P1 g* T5 ]5 T- o
# [0 E- s5 \8 X" M$ k; Lvoid Insert(ElemType a[],int n){
+ s+ G/ t9 G7 F: s. H' i7 X    ElemType temp;
    int j;
    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
" J( v3 ]! ~+ s: r        if (a<a[i-1]){
) C. K3 \- G; s8 J8 }! h            temp=a;                                                               
            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
  c9 B: f7 @2 a+ w0 _0 h8 p                a[j+1]=a[j];
            a[j+1]=temp;                                                       
        }
" B; V  t0 [6 d# C% W8 ]" R, g    }
* Q& r- [+ U$ p, Q* W  T. e}
) v6 Y$ S% V6 d* ~
int main(){
7 z7 ^, b+ W7 A/ U! B0 @: V    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
, j3 k2 J/ i; ]6 t1 {    for (int i = 0; i < n; ++i) {
3 r& j; S7 ~$ C) R0 q; T  v; L        scanf("%d",&a);
% a$ l6 z8 I4 |( u0 k- }  ^    }
    Insert(a,n);
0 @; p7 {( _" M; u; }    printf("排序后为：");
* i7 ^" [: g  i" v) h    for (int i = 0; i < n; ++i) {
1 |7 v2 i, J6 u3 {: }1 u, \( n        printf("%d\t",a);
    }
}

- f# L3 f6 X) M9 [0 ?1
2
3
3 P/ {/ O& t. a7 y1 [* P3 N) {4
5
6
  q. k: y# P: ?- ^6 e* H7
4 I% q$ v+ `$ H) ]' n9 D* O8
9
& P9 k2 d, X* z1 h- D( k10
11
9 v) R# l# s3 ?7 K3 r12
13
, _* M: x& h3 `14
* L' Q1 u2 c$ C6 `6 Q- t15
. J* ^/ E$ C* Q; q9 k16
17
18
19
20
/ C. `) C  E( e7 B9 u21
22
6 O/ b. E4 E: O4 @1 @! C+ q! B: `" q( }23
4 f, Q' {  B  Z24
25
26
27
+ Q& u$ g4 J3 L, ^/ }9 p( U' \28
0 q4 G& H2 }0 _$ |" S: z( Q29
1 P- S0 G3 y* {* C1 ^% Y30
( V( }; e; s* A8 [) v31
32
方法二：
9 a. V8 h6 w) a9 f+ |8 p7 H" K


) @& N) h* g/ {#include "stdio.h"

- _9 V8 R& {6 R9 Wtypedef int ElemType;
' L# j: d' L& d0 c* L
void InsertSort(ElemType a[],int n){      
  V! C* I/ T' c! h$ [6 o    int i,j;
' a6 ~; W7 C6 B( C3 s9 t    for (i = 2; i <=n; i++) {
" a8 K( b# q/ i6 g/ B0 \        if (a<a[i-1]){
            a[0]=a;
7 H9 ]9 n0 q: }/ {6 g            for (j = i-1; a[0]<a[j]; --j)
& f9 H9 j' y& F9 J) }                a[j+1]=a[j];
0 Q; q. O! P& a) |5 _" ?            a[j+1]=a[0];
! \/ |, \( S% Z+ p6 }        }
    }
}
4 b9 W3 A; A( D$ {int main(){
    int n;
! c2 s6 [6 u/ S# |7 G    ElemType a[n];
% m2 u3 j  m7 `, m" P2 r    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
% j! o9 `1 _) P: M) _; s; i    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
# O# O0 P7 g, |2 F' _( \& a        scanf("%d",&a);
" n6 \& @2 @6 R3 m    }
. \5 X) e4 L0 c2 |3 z& y5 c- \    InsertSort(a,n);
4 r' Q; O' z, E) x+ n) }    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
7 r2 h$ k. J- [: x        printf("%d\t",a);
" {5 [# L: e0 s: ?$ l0 E    }
1 A' p2 V: S5 n1 m}

1
. f' I% G6 U* g- G+ {5 M2
8 O! @% \; {9 U% {) S3
0 P$ {0 n% s3 M! y# T' o( @' x8 p4
; M# R9 q& r& |/ ~& f! `" G5
& a0 n" ]( \3 T6 M8 E6
: T: S' M( A4 R& O; @$ _; {7
3 K; U/ R* `% J" I) t8
) t! O! F- |1 S, j- x8 q9
10
11
12
* Q  }/ ]& C5 n! ~13
2 q/ F2 k* d" u6 q4 \6 Q14
- n5 b$ G9 r: K; m9 ~2 v8 Y! u' l/ V0 m15
' U0 O) m6 j  ?5 D. d- A# O2 w* |16
17
18
3 o% h" N. t6 S% J19
( @) M- ^/ T7 |+ g: _1 `20
21
22
23
2 K; r+ [- A8 w: M5 w( w$ ?: S6 W8 k24
25
26
* {8 v8 W8 i. @5 M/ w+ I4 l27
" Z4 o* `/ P* [4 C28
29
; Q3 ?, A3 l+ ^; [1 E1 n0 i; X8 f6 r30
  y# ~$ g( o; U2 z/ V4 R+ E6 a算法性能
: u" z5 k+ o( K
空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)

4 D+ p' m: \! v' v. }" {2 e时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
)


: b$ t% }: V- Q1 K& Q稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。
! ]. F) [6 w9 f4 A6 w
, B& Y8 M6 ?7 C1.2 折半插入排序
图解
第一趟：

第二趟：


; \+ N" K& b: U5 I5 t8 r8 I4 S第三趟：
7 a7 {2 [! k! `) M6 t) v: F
第四趟：略
2 `2 m! J* b' |6 t第五趟：略
0 e0 P2 s, ^+ k4 J" j* `% ?7 J
基本思想
7 S) P/ `& S, K: S0 C  \
/ ^! P; h8 `. R% y9 [4 N与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
4 |; l1 d6 h1 W2 H代码

#include "stdio.h"

typedef int ElemType;
& O2 `$ B' H9 n
: X1 U5 r: S. }5 Y0 ivoid InsertSort(ElemType a[],int n){
2 [5 P" o' ?" Q; S! x# X; {    int low,hight,mid;
    for (int i = 2; i <= n; ++i) {
7 O3 v* Q' o) ?% x9 F& J  H        a[0]=a;
# f, I6 w* z" q        low=1;hight=i-1;
$ W& e4 ]- H) i, A& e8 a% ]        while (low<=hight){
            mid=(low+hight)/2;
+ i8 M; \9 V& M/ s            if (a[mid]>a[0])hight=mid-1;
5 V+ l) v- M, Y% \! d1 A            else low=mid+1;
# L# Q: J; I" W1 l& C6 I) v% f        }
        for (int j = i-1; j >= hight+1 ; --j)
            a[j+1]=a[j];
        a[hight+1]=a[0];
    }
0 Y. F# i& Z; k. K  j, i' Z6 X+ y}


int main(){
% W$ c& u+ K/ O) M) `    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
. _, \0 h' f  t$ z    printf("请输入%d个数：",n);
' K. m! P# ~- f" {" ~( U    for (int i = 1; i <= n; ++i) {
6 S% r, T# _# l8 A! C2 j8 n, t        scanf("%d",&a);
    }
3 q- t9 `# M5 i  s    printf("排序后为：");
    InsertSort(a,n);
& y; `1 o8 H# G9 ]& y' t8 ^% {" r
; Z3 X. |# D- ~/ y6 O    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
}

; h% G2 U0 o5 P. E1 Q7 b1
+ Y9 i0 r- e/ S! V2
3
4
& j3 Q# r3 P8 D4 j5 b6 t5
6
7
: u$ I  t" q4 X+ `$ J+ L8
5 @9 N- F7 O' P5 I+ |9 A/ i9
10
11
12
4 X" A) o* x- q4 I$ H7 X3 [13
14
, c) r  g6 z5 P  V. X. O0 Q1 e2 @15
16
17
- `( v- U, y6 j# y& U: L18
, A" |$ `/ T7 ?; O" w5 R6 C8 K19
, ?0 y5 _: l/ |% Z20
21
5 J- {0 c  S- {22
4 Y) {# C1 q; u, M23
24
25
7 b8 t* i; ^# F  U( }. Z2 K, Y26
27
28
29
30
8 _2 K( V- Q* i- d31
32
, \1 i( {4 Q4 M% j1 a1 i- h" H33
34
35
36
37
! j! |: m' u4 u性能

* k, X+ K3 m1 @, a0 I$ L, M空间复杂度：O ( 1 ) O(1)O(1)
% _7 l% j. ?: l# b0 c% p# _时间复杂度：O ( n 2 ) O(n^2)O(n
2
- i9 Y$ U# w( y6 X )
9 K6 o7 N. y( I" n% M稳定性：稳定
- y( e8 Z6 }) x/ \) b0 \* b/ `适用性：仅适用于顺序表

3 Q( w& O8 I( n% O( a1.3 希尔排序
图解(动图)
9 Q: \  a& c; t9 ?# o

: i( ?% u* O4 v基本思想
, X2 j8 g2 L+ l* A" ]" ]2 p
先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

2 t! ?% ?) o( @3 l8 Y7 Y" b% e代码

#include "stdio.h"
3 g* x3 Z! b7 w  [2 q
9 U3 Y) x+ W9 @6 w" Etypedef int ElemType;

void ShellSort(ElemType a[],int n){
) n2 ~3 R: c. H    int j;
    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]){
' `1 s4 J3 E( o; t* A                a[0]=a;
                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
                    a[j+dk]=a[j];
6 i" z: M2 p4 y  L6 D$ B: q8 Q                a[j+dk]=a[0];
5 Q' e7 q+ n* w            }
        }
0 [$ Q/ Z* l' D' V! C    }
3 ~9 {. e  b: r- P& D3 R}
; a1 D. V- r8 @" n
int main(){
* E+ t7 ?% |7 U6 I& }    int n;
    ElemType a[n];
0 a: s3 i  T. r1 {; k8 V; o    printf("一共有多少个数需要排序：");
, m# K! q1 @  s    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
0 n4 ?- v3 B! v% y7 `    }
- E, y. K8 z% G; ~. v/ \4 _  C    printf("排序后为：");
    ShellSort(a,n);

    for (int i = 1; i <= n; ++i) {
& ?3 S8 |1 |  J6 W+ c$ V" h        printf("%d\t",a);
    }
}
& S6 A$ a, T, e6 [3 i% P
1
& G$ M5 j$ w* w8 f" F! m- Y. k2
3
4 i* m+ U- }/ N& r4 d! b4
5
7 ^( q$ C# u4 b" K& C" `6
8 ^1 X0 k/ v8 ?4 g) i" X7
8
* _4 x/ U! L1 m7 U1 @9
# ^! j3 o& |+ O' l& {( \, ^/ X10
8 q- P3 X$ H) N7 R  Y$ M- O/ Y+ _11
8 o6 n6 h* i5 ?% ~1 k" z  P12
7 Z/ u0 @: O- e2 z9 q. d13
14
4 p8 ]8 X* k3 l: I15
! L! @' P! k# L/ d: @7 r; N0 I16
17
18
1 D8 G6 c* F8 U. G8 U5 O19
, T0 w0 o0 m" M. T- W20
) _; }8 ^& W2 H0 l/ i21
# q3 {& {& x# S+ N. x8 l22
9 D3 l: C% s6 z: X" Z23
1 J$ C% B& T* m: U8 _0 w24
: @* y  R8 I6 z5 U' J+ ?+ t5 V25
26
/ w- H# B4 `& ]# \27
% y! u0 K+ t/ r28
8 d( |/ p5 v* D( u1 K! U29
30
31
6 h! |$ `3 X# Y. ~0 F) C) C0 Q7 e' Y32
33
34
% s2 o  ]& c$ V9 s" u性能

7 S* P( S" j+ S- V/ w. B9 `空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
1 ^7 e! J5 T8 D- N( P
时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
1.3
+ P+ u) b% q# o* `  ~ )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
2
- K1 r/ T7 j) ?7 C& D )

' g$ \6 f% z7 h0 l/ C/ T稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。


适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。

  {$ ?! n5 r  L! g' s2. 交换排序
2.1 冒泡排序
图解
' W  i# \* y" ~
6 q. U/ E- M6 a: t9 x$ E4 ^8 W. \
: d# D7 T2 G& n4 M# B3 i基本思想
8 {/ Z4 i$ Y2 x" T3 p% G/ x( w
从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。

代码

3 G) \; l; |1 S3 K1 R; r方法一：将最大元素交换到待排序列的最后一个位置

$ Q9 P' K  a( `! }2 k5 d! z1 N#include "stdio.h"

typedef int ElemType;

void BubbleSort(ElemType a[],int n){
    bool flag;
# ~! D) }6 s- f1 f& _    for (int i = 0; i < n-1; ++i) {
& m7 v! K+ W* X" u2 `; d! @        flag= false;
        for (int j = 0; j < n-i-1; ++j) {
& e. s' }/ H& ]! T% _* _            if (a[j]>a[j+1]){
                int temp=a[j];
2 n* q$ e+ e# w. V                a[j]=a[j+1];
                a[j+1]=temp;
4 V3 |/ K" s! E1 @+ W' w: J! L                flag=true;
0 i6 \5 K4 C  w1 D- V1 D            }
        }
        if (!flag)
            return;
    }
2 g. O0 l8 T( R( X}
$ j! r3 e, {; [  u

int main(){
& H& A8 o! P6 ?7 E, ]    int n;
    ElemType a[n];
6 [1 }5 u! j. s" c% j( ^$ W  y    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
) G- @* y& n6 Q6 Q$ a9 C. V    for (int i = 0; i < n; ++i) {
) c+ B2 x; ^8 k- _2 k/ H. `8 j8 u        scanf("%d",&a);
6 K) B; e7 S" k    }
    printf("排序后为：");
+ a9 }$ e3 f* Y3 ?7 j( T  o# K    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
}
0 r  m3 H2 a! {
# X2 ~6 [7 ^2 n1 S8 Y- |1
& X; a; T: F0 @# ]" j+ ?2
3
$ z' @, x/ c2 J' }4 b1 m4
9 y& E4 w  g3 E( l; V6 q5
6
0 M3 u/ p, C# |( [* w" C& T3 H7
8
3 \* f2 V4 c2 w0 U% n# b5 q9
10
11
# l: G  C+ Y0 P9 F" p. N12
) i$ {( m5 _1 ~. ~13
4 m' l+ G: _2 a. D/ E14
6 }* e! H; H) a# y( `! y15
16
( P4 ~5 A. s2 W17
18
0 E4 V9 i2 W9 @' K% i19
! l, D& J5 B2 s: q& p20
21
, `  m: i& p- H+ r. {" c22
" `3 G& c( D& X23
24
25
26
2 `! U4 i+ Y/ W/ O6 P  h; Q8 h27
28
29
2 q, y; v* e6 N1 {30
31
32
4 ]4 m$ A/ Q- k% E33
' c4 g6 f; ]. u% ?4 U+ H) o5 z' o34
35
+ m2 O6 }+ U$ U: P/ @36
37
运行截图：


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

& k. W9 @/ H/ C- Z% t/ K#include "stdio.h"

6 c* a/ K1 b; U0 z* q9 _typedef int ElemType;

4 y  v8 i& |  [7 R) k- a. Avoid BubbleSort(ElemType a[],int n){
    bool flag;
* m5 z# q1 p+ e; ]5 e    for (int i = 0; i < n-1; ++i) {
- ]+ R) l8 F& n' X! U        flag= false;
        for (int j = n-1; j >i; --j) {
            if (a[j-1]>a[j]){
7 ?% i* C9 s2 _0 H                int temp=a[j];
                a[j]=a[j-1];
4 B. n$ |, z7 P6 k  t) l                a[j-1]=temp;
                flag=true;
            }
; y4 Y4 e- g% ?' c+ R9 }: p        }
: Y$ C! |0 D! i5 K; e) ^0 v        if (!flag)
% i8 ~% @4 R' r/ t; b- E+ {            return;
6 d$ \, V) P3 u( K8 w: i5 k' x& @    }
}


: \8 s1 l/ W- }/ M$ p) y8 l( j0 @! Fint main(){
% B3 |% d8 t+ O6 A% `    int n;
0 F. w  i9 t' f) x    ElemType a[n];
    printf("一共有多少个数需要排序：");
0 ]; @5 S+ Y+ F7 ]    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
% m) J1 }( U. J, g6 v- N    }
& d1 t5 T3 t7 S4 K. Z4 m: `7 L. C    printf("排序后为：");
, |$ i4 {9 s1 ^4 X+ y: D  x    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
}

$ x( q7 m4 H; M: q( c) q3 |1
8 L+ p0 w6 d; W  K2
1 q6 Y6 J: E$ T$ ^3
! h  {% T( H6 D  p: h) d- R4
5
2 I( s, e/ }+ G; d. X6
7
8
9
* ^& a2 ~$ X3 k$ a6 P4 o# [10
11
12
1 J: Q: V; u( d9 F13
9 E4 @" Y6 u$ P' c0 H( q& Y14
15
16
17
18
19
20
& s/ o9 x' f0 `( K: c( t21
22
7 K$ U1 C, B$ U/ S  U) c23
, \7 z$ P( o, t& Q9 s24
25
- @! V* z9 N8 L7 `( ~/ T26
27
! ?) o( l5 W0 [5 E: n28
; j( |! c1 |8 E6 X+ h9 y29
30
31
, I8 g, S0 c1 q4 f( f6 z0 m32
33
34
# q6 X% s& p6 Y1 l* K* m35
36
37
运行截图：

( ?! F. Q9 ~$ s$ c) _7 h7 K
性能
, _- V" U! H! ]. i
空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
" g/ O' |! a  ]( W/ z" H
5 X2 }: q$ m( W, B9 b$ V时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
4 r9 C( Q6 a4 p* A* q2
)；平均时间复杂度：O ( n 2 ) O(n^2)O(n
8 e' \+ G. o' f( E2
$ }5 @* F) P2 G$ j )；

稳定性： 稳定
8 g; A7 n) K# n* D% c
适用性: 适用于线性表为顺序存储和链式存储。
7 H1 ~, z5 u8 c1 V/ E
2.2 快速排序
图解（动图以后再补）
1 ]) \- o$ n& d* V第一趟的排序：

. j$ C0 I* h) W) m第二趟：
! w* q2 t! H. [7 r1 V
第三趟：

8 `1 u1 c; Y8 h+ W( \
& I- i: b) Z- A基本思想

快速排序的基本思想是基于分治法的:

在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
" b; T3 t. Z$ v然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
代码
1 i1 K# |' E* W. h
#include "stdio.h"
: G+ J9 g# I* ^4 g$ c
* K6 f' R+ c1 ftypedef int ElemType;
. S3 \2 F3 u  Q1 x3 z% V4 d4 @
. O- Q5 f9 c! ?7 N# h5 Dint Partition(ElemType a[],int low,int high){
) a: V1 s& k4 q" A    ElemType pivot=a[low];
    while(low<high){
        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
- o1 h# i" w: f% X        while (low<high&&a[low]<=pivot) ++low;
: A! `1 [8 \6 ~        a[high]=a[low];
    }
3 e9 Y! ^7 f% w    a[low]=pivot;
% }2 i" a. Z! g6 Z, U8 y9 E    return low;
" s2 e* f) T+ c! c7 z}

3 T/ B7 i8 @2 l; Y8 ^4 nvoid QuickSort(ElemType a[],int low,int high){
$ K; E# E* M4 P! i7 ^# F    bool flag;
    if (low<high){
        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
+ J; y8 V/ w/ c& Q3 T' E    }
5 m  _/ {- \6 R" h6 R}

+ @% x5 L; F9 F! e; s2 I+ y5 |int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
" F' v6 O( Q2 i    scanf("%d",&n);
    printf("请输入%d个数：",n);
8 ?1 j! f9 t  j4 c$ |    for (int i = 0; i < n; ++i) {
9 N6 b/ n0 Q0 R9 ?2 k/ H" j        scanf("%d",&a);
    }
    printf("排序后为：");
$ z  H5 T! h# o    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
7 J$ F) Z! z3 Z2 x. v        printf("%d  ",a);
6 D1 K; l8 q1 _" b7 Y    }
0 d0 ^8 V% b6 L# f% P* C& |3 l. r}


1
. T1 ]: {4 h+ D' W) D2
( o( y6 A$ j( L5 ^+ Q1 h3
4
5
6
+ M$ \* G, x- Y, U; \, p7
8
9
2 ?: |2 ]1 T. o10
11
- J1 T6 C4 p3 K$ F12
8 e( c* R5 R- X" P6 e13
: S, J. \; \$ {& k: H14
- y; l& W4 G% C- ]7 g* \15
# ?+ h0 |0 H% F$ |1 A6 W16
17
18
19
, a7 Q2 ^! C8 f( A+ W7 s% b20
8 q! p# i. a: O7 B: u. t21
22
23
3 O& w! x" K& Q& u24
* L4 s) p/ Z5 j8 ^; A25
# Y! s$ x" N( L, d# l26
27
$ p/ }8 u  B1 X( r! ]28
4 Z9 M! b) X3 Z5 c+ f; O9 i29
1 f! ?! Z3 p6 H. N30
31
32
0 r$ |1 J7 K; T! ]! r8 m. s33
34
35
36
6 x. V9 F+ Q3 W5 W7 m8 G37
38
% A8 }7 \9 @; ?! B/ X39
40
8 Y' q% v- u1 i/ \  B+ x41
性能
6 F! H8 p9 m2 M! Q5 c, E% @. o0 ?
时间复杂度和空间复杂度
稳定性：不稳定
$ b$ l, s! T' j. t7 h) G
; ?! l+ I! J/ _2 r3. 选择排序
3.1 简单选择排序
# g9 ?& c  ~$ \' t图解
0 Y3 F0 i( I4 n' X/ e* [  e+ x4 k
: B9 ~8 P% b8 |- m. j- o9 A
基本思想
' V- e# e; x! {8 w* ]1 I
4 M, B* Y4 m* ^& N5 d' ]0 o9 I; ^在a[0…n-1]中，将a[0]设为最小元素，设min=0
# N! n$ j, W  z3 _在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
# B. f8 n* j6 E% A) y在a[1…n-1]中继续进行排序。
3 S' i! ]9 h# N$ A+ ^& F代码
$ J- p% V$ w* m  G; g) H' q" m/ ?
! I6 m" h$ ?# _  n( c2 D2 W#include "stdio.h"

typedef int ElemType;
$ h; r; A- Q% A) i2 K4 f. T' }
void SelectSort(ElemType a[],int n){
    for (int i = 0; i < n-1; ++i) {
        int min=i;
% y3 h, |) B! Q! s        for (int j = i+1; j < n; ++j)
7 A! p1 }2 p; q6 n" ~& k6 ~/ x            if (a[j]<a[min])
5 ]7 F: Y( R2 x/ l1 b2 I* j( h                min=j;
; l, f6 b8 T% E8 ^7 Y* P        if (min!=i){
  O# Z. K  q/ G/ h            int temp=a[min];
            a[min]=a;
. I. M! d+ y5 R3 l3 e            a=temp;
        }
% a, I7 y# _6 Y0 Y) W: Z    }
}

6 J2 N! ~7 p/ ~6 X/ Oint main(){
- X) _* z( Q2 U* @- y% m8 |. a    int n;
8 r2 d9 z3 A" S- }7 F0 I  v    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
$ Y! E3 p$ C) j+ W  [$ T) h    printf("请输入%d个数：",n);
5 E2 Y2 r) D' a9 \: Z4 ~0 O2 S# \$ V    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
. s6 w7 j! [" E    SelectSort(a,n);
    printf("排序后为：");
7 g3 `6 x( ], o    for (int i = 0; i < n; ++i) {
+ M3 J% O  H; `        printf("%d  ",a);
    }
}
3 C% z' k7 N' [- c
1
/ m# u2 w. X, {" s2
6 K4 E; d3 w8 q- t7 T% b" g3
4
5
6
7
8
$ s, M! O/ d# Q/ \, F# E9
10
11
6 T4 n1 t; u2 l& |0 l; v8 @4 A6 d12
13
14
# ~7 y5 h7 h$ O  |15
16
2 w) w7 S" L1 `7 `1 F& V( U* D17
18
19
20
21
# l8 a! J* p7 u/ \7 D: [1 A22
  c6 F. A4 O: P! F23
. y" i1 u8 H+ B! {% G24
+ z! Z3 k+ `3 Y25
26
27
28
29
( R) p8 M4 l+ q3 E6 j9 @& H* T30
+ ~0 i5 m; T8 A31
32
6 g! ]! n; s+ y. z5 F33
性能

2 C3 x; s5 f( q- n8 s# E空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
+ u; O# \" T9 {3 u: l2 P; e; @/ p2
5 H6 s5 Q+ }8 F; u- t! }$ c2 K )
/ C# [2 u$ _' e  ~. n稳定性： 不稳定

  n) p& `# j; m. i. i+ W9 G0 w使用性：顺序表和链表都适用。
8 S8 }3 X* N2 h8 t1 m# _. m1 |7 T. F
1 ?$ u+ l6 f; N) B: m' M3.2 堆排序
. s( C! y+ Y! B0 ?看堆排序的点击这里！！！！
- o0 D9 _1 t0 }
4. 归并排序和基数排序
/ l9 M" z4 B3 [3 `4 r2 F# q0 o& G4.1 归并排序
6 B8 ~' n' y* G- Q" I& ]; h图解
3 k' g5 o, v7 O; t  D+ f3 @& n) L2路归并排序

. Y' o8 k5 [' P, v) Z1 B
% e. P+ I$ Z% e  s  j基本思想
- o9 f% `4 x0 R2 f
将待排序列分成长度为1的子表，然后两两归并，形成有序子表
2 Q8 G; O4 L/ B; V/ A) T, ^
然后将子表再次进行归并，直到子表的长度=待排序表的长度。
( y7 H2 s6 A: }. J2 f( D3 O3 \代码

#include "stdio.h"
#include "stdlib.h"
- X! L+ N$ a+ i  g* X5 c; S- d" p
/ y% e1 Q# ?# ]9 H1 l( J8 |typedef int ElemType;
# y; C# I0 }- w7 j: a- D
ElemType *b;
" k! P' t9 j+ _; [" x% f
void Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
    for (int k = low; k <= high; ++k) {
        b[k]=a[k];
% K+ E2 s+ z# G2 Y6 e* z    }
    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
4 t: \$ N/ M$ f* n" [  N" ]        if (b<=b[j])  a[k]=b[i++];
: R3 ?. @5 x% K% S* f        else a[k]=b[j++];
: {/ X- b1 |; j+ ]+ ]3 e; p. W    }
    while (i<=mid) a[k++]=b[i++];
    while (j<=high) a[k++]=b[j++];
}
4 U6 f1 T& M, Q2 f! ]4 B" N' m
" q5 j( P4 ^. Hvoid MergeSort(ElemType a[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;
        MergeSort(a,low,mid);
, c( }) A0 [& A$ ?        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
, q, V/ S5 @+ q1 M+ H1 a. P5 U    }
7 z7 I' R; d, ?. A! d4 r}
3 u% e+ B; D9 j+ [9 ?' B; G
$ w& f$ [7 ?' r0 \int main(){
/ J* }4 p; K8 l! Q( [4 ~' j    int n;
    ElemType a[n];
    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
9 O: ]' i, @6 f6 ]    printf("请输入%d个数：",n);
' h. R9 S- z- X) ~$ ~" b; v    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
; u+ A: Y0 i# Y' b# k    MergeSort(a,0,n-1);
    printf("排序后为：");
5 g8 l6 }3 i$ V7 y2 q    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
: j& h. _1 k+ @" e0 y    }
}
. j% H$ i% C! N, ~& K
0 X5 t9 ~* T  {9 Z: ^7 I# x
& j. o1 j% s  |+ l& P1
# R* l( o: ^6 T. X8 k2 i' y2
! @9 U1 f0 s( [* p* h, P7 `3
4
5
6
7
; U1 V' V. J( ~7 O# s- o8 U% E8 W' O8
) E5 [9 K/ x8 \1 y( J9
10
11
12
13
14
15
16
6 R4 D8 Y. Y. ^0 h- k5 r8 a( t17
1 b- |/ j8 h7 z) b18
. D8 c& z! [2 v5 s5 x/ O. y19
20
21
22
23
! `, A4 M7 o+ ~! x; P5 ^% w24
6 o* _, m1 P  C" V25
26
" V8 E/ j6 a7 m, o: }4 A27
, \% e5 p1 I2 z' j/ @28
29
30
6 G! U2 l3 g7 @! \- E+ O# \' k7 X31
6 Y! Y( ]3 y% ~9 W32
33
' g- [) b. V# `7 ~4 a0 X' p34
& x$ E$ g0 A/ u+ C" ?3 V35
36
; a- D$ j% a4 a6 M  X' Z( \37
38
3 y+ `# Z2 _( j1 y# l39
- x* k& ]  k; L! J3 i) t40
6 S8 C- N8 `+ M% Y41
% G* I2 j' @8 x42
1 a0 Z/ p# m/ u$ ]43
44
* T$ X# Q. ]& J* Z7 ?" y45
* q+ U6 P. F) y! E: a6 b% E46
0 A8 u& |* s# K) P性能

6 n8 y4 B1 l! x8 D' D" F/ {空间效率：O ( n ) O(n)O(n)      创建了一个数组b
时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
% N. U7 ?9 J2 }k
$ i- c" _! Y2 `4 e; b​
/ r  y3 T6 Q5 f& h5 O n)  k指k路归并排序。
0 d/ @# p9 b/ y; I6 v5 e稳定性：稳定
4 j) u) Z: l% @* A
2 z; O; z( a- C# n- L4.2 基数排序
图解
" k2 X9 |, l, t) b
) \  n3 ?0 M" Y. z2 z0 W) [, K
基本思想

- W) m) ^, r2 {5 M将各个位数（个位、十位、百位…）进行对比。
% h1 `" ^. _. a$ H: @3 ?( f为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
9 d. A. K- ^% b  F
4 F8 N) d! u8 v  B: T& ^性能

空间复杂度

! i- B6 P3 _$ i( M3 i# m* i时间复杂度
! V8 l; m  r6 e- V8 m" b

稳定性：稳定

3 x3 O8 ^$ H6 w6 O2 i5. 内部排序算法比较及应用
5 P, S* [: e% J3 m5.1 整体比较

% _- E1 n. ~  B. V8 [5 }
6 Z, x% ^( @2 Q; Y" J$ R; `5.2 时间、空间和稳定性

) g/ V8 t6 s2 z) {- D4 P
& E! ^2 o2 d) V9 K2 v参考资料
; z) {0 ]2 P, y! c: m《王道：23数据结构考研复习资料》
! T* F: [2 P" K  t7 ^4 i————————————————
- d$ g( R" w' [. d/ |  G版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
) S, D  S: m( I原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678
) H6 O9 s) Q1 t! W* b$ [