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

杨利霞

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

排序
1. 插入排序
1.1 直接插入排序
1.2 折半插入排序
1.3 希尔排序
2. 交换排序
2.1 冒泡排序
9 ^8 |* G5 u' |4 M, A- K2.2 快速排序
3. 选择排序
' T: N/ r- }3 G2 C3.1 简单选择排序
: _! O) b0 Y! G' Y; S) I/ }3.2 堆排序
4. 归并排序和基数排序
4.1 归并排序
" Y& C+ J6 |0 H/ q  D. X* a4.2 基数排序
4 P) W! Q, b( h5. 内部排序算法比较及应用
  U* m2 y+ @3 o5.1 整体比较
0 Y3 C9 t+ ~8 d7 p( ~$ j9 w: j5.2 时间、空间和稳定性
参考资料

内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
& R5 Q) p9 v# d. s0 W3 R$ |1. 插入排序
1.1 直接插入排序
! f" j( R- p5 y" O图解

- p- F  B3 x$ f3 E1 p6 G3 B0 \
基本思想

$ e( R& ]3 T# G, K7 s1. 查找a元素在第1 ~ i-1中的位置k
2. 将k ~ i-1位置上的所有元素向后移动一个位置
3. 将a复制到a[k]

$ N0 m! F3 m" U

代码
- S6 Q! }' z. j7 T8 @: U2 g; E
方法一：
% o7 O0 I! u' `- v* B5 a, U" q
) b1 a% J) o* C8 g/ I数组的下标从0开始，如上图。
" W9 u: B8 ~6 C
$ P2 T/ ~- ?7 w6 j9 ^#include "stdio.h"
# D; `: L1 K% o9 R
$ X+ M8 ?! d4 A2 G6 z& }7 t* Gtypedef int ElemType;

5 q: E6 d0 x5 i, z' m, z9 ovoid Insert(ElemType a[],int n){
9 {7 Y( Q) P: I! e, N    ElemType temp;
, c7 z- `+ d2 ~    int j;
    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
        if (a<a[i-1]){
  m% Q8 Q8 e% r8 [            temp=a;                                                               
* z9 I2 T# D1 V- r# B1 |! v7 d/ _            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
                a[j+1]=a[j];
* H0 U7 g4 @3 ~6 G! p: Z' q) a0 o- M            a[j+1]=temp;                                                       
9 ~' z  |- T4 `  Q        }
- `  t2 v  Y! C, g! ^' ^7 K3 U. |    }
}

int main(){
    int n;
8 T+ C9 X. A2 E% }( R    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
1 D4 @, Q9 q- B8 _8 k& n    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
, U4 c0 o( [3 w6 @( @        scanf("%d",&a);
    }
    Insert(a,n);
1 B( \9 w# ]/ k2 _- ~    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
7 |# l7 N- C% ^" y    }
}
* g: s$ e# ?. ~! ]/ g0 ?8 o9 i" R
1
4 n; h) ?9 t( C# f" O  L2
3
4
5
. R2 Y: w/ G0 a6
8 q4 x+ V8 ^9 F2 o2 K7
8
9
0 y" ]1 i! k8 s4 r10
11
12
13
9 i! U( _3 d% ^, H. k$ K& l14
1 l& s0 j& r4 o5 a9 }/ A! o15
. \: ?7 ^6 a6 V4 o16
* m* I2 |" a9 R, s17
" D; w" B! t2 y; ?18
19
2 L4 M  x- w: o% Z/ i20
21
22
% _. m" ~* V6 \23
) a: c' {( B4 S24
25
) {1 t0 v9 O  q  G9 p6 \26
27
4 E! r' Y+ m; }28
29
30
31
32
2 b# X: V7 ]/ I: @& k  J5 z方法二：

  H8 D! p' o$ o
) d+ S( W4 e5 U+ B' f" D7 L2 L" y5 y
1 w2 w1 m4 Q) |, T( Z5 ]#include "stdio.h"

0 z+ h3 {  Q3 q$ w! I. J+ i" Ttypedef int ElemType;
! {3 Q" o/ f1 `! m" q5 y/ I" F3 n
void InsertSort(ElemType a[],int n){      
    int i,j;
    for (i = 2; i <=n; i++) {
        if (a<a[i-1]){
            a[0]=a;
) o/ n0 J4 B: g& }( v            for (j = i-1; a[0]<a[j]; --j)
                a[j+1]=a[j];
& k8 \* ]/ l$ x            a[j+1]=a[0];
        }
    }
: P' g% k1 m& c" v}
int main(){
  ]3 S8 r  @( O- X) \7 N+ p    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
- O1 u6 F4 U  D% s, d1 i2 W+ g3 n+ X    scanf("%d",&n);
3 n: y( m  A/ x    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
8 i$ Q7 _  g" R$ B* [    InsertSort(a,n);
    printf("排序后为：");
' N& w* b0 y6 p# b3 o! h% O+ v    for (int i = 1; i <= n; ++i) {
  u6 r, G- |( f$ ~8 K* _' l        printf("%d\t",a);
) X+ c) y. r+ ?" B    }
}
" P; W: N& K+ [- @/ W4 t; c
1
: ]1 }( ]+ }8 I2 w9 W% E' ?' q2
3 j, C6 @% g9 t/ ~- r3
9 A, n4 _- v4 c/ V( r4
5
6
! c, Z% i# u! [; d7
8
9
10
5 e$ ]1 M5 Q& D+ {" P% j3 K11
% G3 c6 f) Q6 Y5 @% D' u6 }& F12
13
14
7 `; G/ F; Y/ ^, }7 x15
# M2 D: C) m( q( V2 d9 u16
  M, q+ a7 A4 ?. K+ Z) L  _9 x. [. w/ k17
, l) u. Z( O$ O! E18
! _4 Y$ |8 p4 b$ R( u19
9 t2 M" U1 [: C9 p5 {! T! k20
21
22
8 e" w3 ~  B! I23
24
% ?1 U. V: j  F0 L3 `: G25
1 X) j0 g6 n/ k& F1 h26
27
! F3 Z# k* ?1 b28
( q" r3 E$ Q' w' P5 i29
30
算法性能
' d7 K& g1 F& j5 W
空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)
1 ]3 M* A3 {" {+ K* ]0 w
! U7 o& _- j5 L  t- V3 I' K时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
* |4 W! B3 y7 D1 R2 a; {2
)


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

% N" W1 |& Y/ t, |" A  E3 a8 _适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

1.2 折半插入排序
0 z% l: q- a; ~# R4 Z( {+ m3 |图解
第一趟：

第二趟：

7 h( n. ]0 A' g5 M, v0 D+ \5 ]1 e
第三趟：

. L  n5 y0 c- k; A) r5 }第四趟：略
- B: R' ]4 P# _1 }# A: ~第五趟：略
2 j* [" R0 W; G) q" \# \5 d. r- P$ v
1 D- c5 B) T8 o: j/ g/ x2 ^基本思想
5 `, P& d  H8 l& ~2 w. F
与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
" ^( h/ ?4 G! N1 D! N4 ]代码

#include "stdio.h"

typedef int ElemType;
9 k$ Q/ b* B. C/ s- u4 n% w
( P5 \) Z- |/ w6 A5 d4 }. r" H1 t" a1 x, uvoid InsertSort(ElemType a[],int n){
3 B* N- j! P& r& U$ R+ R    int low,hight,mid;
  N9 _* t, [% T- U    for (int i = 2; i <= n; ++i) {
" }+ Y1 j, O1 U        a[0]=a;
+ a; K) [8 h" x& I2 F& \. K* x        low=1;hight=i-1;
        while (low<=hight){
            mid=(low+hight)/2;
: j. I$ V" m" g2 X            if (a[mid]>a[0])hight=mid-1;
8 V+ l/ Q; L6 n4 s) J            else low=mid+1;
5 X) a4 G: G, O+ Y  @5 l" H        }
        for (int j = i-1; j >= hight+1 ; --j)
/ U' o# |# A' Y7 ?            a[j+1]=a[j];
* O/ k: P) u3 E4 B# Y+ t        a[hight+1]=a[0];
: D+ \$ ]; Q! N, X8 P0 x% C/ U. H    }
( h" W2 d  x: j: u; t}
1 c( i# l9 o4 I
( S6 D+ i9 {4 a2 z# \
- z6 e9 A: d8 _( rint main(){
$ a; ]' S) ^( a8 B2 E, v    int n;
  L. B$ _: a0 |# p" x    ElemType a[n];
    printf("一共有多少个数需要排序：");
& [! D' [! B/ d" f6 X2 U    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
! v/ v$ `; [! |7 K  l    printf("排序后为：");
    InsertSort(a,n);

    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
}
: K7 a) n  J- g2 e
- m% L7 b0 k3 j( `% n6 \0 f% s1
9 h4 M3 O/ ?4 d) Q( u3 [2
3
9 z  A4 U5 O; |6 F, W9 Y4
0 A- Y$ y7 E' ~# a- D  X5
$ T  t# T% S) M! T  b3 G0 h% M9 G6
7
3 M- y4 E2 G0 U6 W  S8
; b/ r+ l$ u6 E9
10
  ~  j" `+ B, V+ s( }11
1 ^0 [& n0 s+ a" d/ }6 B8 k12
13
14
15
- V5 J, y5 w8 A- I1 Q( ?1 o16
17
18
19
; O4 ]: m" e8 n/ S3 D20
21
8 l( ?. t5 y/ r" h# q22
23
24
25
2 T8 _+ c! f# T- Z0 m% H: m26
27
28
29
" s; J: C, O* P# M9 E1 U" R$ T30
31
, ~: z/ e: \. D2 F) u6 E9 O32
0 c# M1 g; l0 s33
34
1 |" x; a; X% f6 J: a35
36
37
性能
& W4 ]7 d2 h. \: U5 k% S1 }+ h5 N
空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
1 F+ G8 [$ i( J; ^! B( W9 v2
& {% _% ^4 {1 K/ j1 c, x )
* W, N& U$ h1 V+ t稳定性：稳定
适用性：仅适用于顺序表
4 e2 R& w1 r) l- s* G
3 b  J' ?$ p8 _! C3 G5 Y$ [1.3 希尔排序
1 d: G) V& e3 Z  u) ^, q图解(动图)


( ?7 P1 t) V* x基本思想

先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
/ e2 K1 j, G/ c6 u3 @. F) o
3 h" {7 x. B# Q1 N& w代码
3 ]0 V, z; o5 j2 O- ?& g4 |
; f$ m; }4 }8 R1 A#include "stdio.h"

typedef int ElemType;

* M/ C$ F% C! ], g+ I2 ]! cvoid ShellSort(ElemType a[],int n){
    int j;
: F8 U+ R& {' x: y+ M/ Z4 e& T    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
1 S& J$ y! `" ]! z; p$ r        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
            if (a<a[i-dk]){
4 \9 X) M/ P, I. S                a[0]=a;
                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
! h3 B1 t2 u  k3 q3 W% E                    a[j+dk]=a[j];
1 F2 B. B& h, W" B& z                a[j+dk]=a[0];
  N4 N9 L. l' s# Q! i            }
# |4 T/ n& [2 B2 s  A5 Y3 V/ n8 c        }
/ ?: [4 q0 t- V6 _; e9 e; a# @: p    }
}
5 R0 Q9 H( Z9 ^9 K0 |4 q
% _7 U1 X/ P9 j2 f9 bint main(){
8 d" N: P6 [6 [    int n;
; K$ l4 s. I7 k' J7 U    ElemType a[n];
    printf("一共有多少个数需要排序：");
# Y( O; H; g6 S$ f, L6 r% U7 r    scanf("%d",&n);
    printf("请输入%d个数：",n);
' z3 h( y/ L. u/ M' W; I8 ?    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
. ?6 F5 \* R. m; ]( _4 |# F    }
    printf("排序后为：");
5 v# p9 G2 U" R7 o* P+ o% m4 y. {    ShellSort(a,n);

# e1 t8 K+ |" r. p' p7 p9 U    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
) v: L6 s7 s$ t/ h& J* m    }
1 E6 E$ P# ^, z2 X1 c}
; Y; ^" L1 H& `3 ?
1
2
- q* L; ~/ n+ E) y/ z6 Y3
4
+ U( r, k0 V9 U6 R' l* M( y5
+ x6 h. J/ d1 _# h* y7 c6
7
' f( Q' Z* s: v, a6 v8
9
10
11
! z/ K7 R2 J' K/ I' P- `& I12
+ n( J& b$ r) N6 i4 L+ i0 o* E8 ^2 I13
( X& t4 M) R1 a% I/ s/ V- V14
15
* h% w- L- _  u: V9 E) ^16
17
' l5 q% v, r, N. M18
19
9 R- D5 @% `7 c6 Q  L20
21
$ }) _, |' d' _% h7 D; a. |  |$ v22
5 m0 S- |+ W0 P3 W$ D2 A23
1 m1 Z- M4 {( {5 k" @+ s; D) U& n+ F24
25
26
27
28
4 f, j" G7 w4 G- B29
  a& g5 I5 n8 _1 R$ }+ B30
$ x8 F+ z+ W, w' p; m31
32
; d" T- Q: t& R% m! |9 H+ a: y33
$ \- \( Z( v, |& |0 T34
性能

# l; D" r: I+ a1 [- L3 y5 e空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

9 p& c+ Q# p  g* ?( v1 u$ K" K! q时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
( I8 r/ Z- q$ u1 @- L1.3
0 j4 V( v1 V$ K. a5 E5 P )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
2
)

稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
5 b2 J1 @8 q9 X2 ^- p) n6 i
+ N" s: x5 R. i5 R
# Z* v6 I& c. T; T4 v' R* _适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。

2. 交换排序
7 I( F+ v' s# D# S/ E/ C2.1 冒泡排序
图解


基本思想
9 z* }" j: l2 w! |( [
1 Z3 b7 p! j) l3 D& C7 x2 z8 i从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。
3 `( j- _7 e% s1 H# j
5 g& T& Z& e5 q代码
/ |/ T* D5 {# F  P
方法一：将最大元素交换到待排序列的最后一个位置

#include "stdio.h"

typedef int ElemType;

void BubbleSort(ElemType a[],int n){
6 Y1 D! Y# \) O$ S- e1 M$ s5 q- y$ p    bool flag;
" }. i7 j  }8 q4 U    for (int i = 0; i < n-1; ++i) {
        flag= false;
  J! ]; y; ]5 O9 P* f3 O5 [        for (int j = 0; j < n-i-1; ++j) {
            if (a[j]>a[j+1]){
                int temp=a[j];
, o1 d% ^: d& t8 \                a[j]=a[j+1];
                a[j+1]=temp;
# w% L8 ^. z/ A/ s. _                flag=true;
            }
$ q5 l# G5 j6 A1 ]$ V) }        }
. Y% D% `( q- ~0 f# T        if (!flag)
" _$ Q5 r; F# Z            return;
6 G+ a0 X$ P% ~    }
}
" d% @% M* l5 c- v

int main(){
5 u4 Q& S1 i1 [9 c% J/ Q: U. b$ U    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
8 i  h" B* U4 E. Y7 _& F2 {. r    scanf("%d",&n);
! m9 \9 H$ |/ m" t' g; |" @' G    printf("请输入%d个数：",n);
3 R% ~  @! s! a6 q' [    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
% _4 }9 i+ _: m* r$ K. r    }
1 q! F- F6 [0 N6 ^6 F9 S) u    printf("排序后为：");
    BubbleSort(a,n);
" Y' @7 ~! q  B0 F" c1 q1 Z) s    for (int i = 0; i < n; ++i) {
1 k) x" b. s! Y+ w# `( W) U        printf("%d\t",a);
    }
1 ]9 I: }) c" a  Y}
9 {& g' i: C/ M
1
% e* @- B. ]: j, o2
3
9 ~  h6 [. N0 V$ x: T4
! p6 ?# D8 M1 o1 b( V  I0 N% C* T5
6
% A. ]/ }0 L, B2 s& V+ l7
8
: J, \9 U) R+ P/ `7 y9
10
11
12
13
8 k/ B' x' ^) k" M3 Q# ~- a14
0 @/ {2 s. @3 _& W4 D4 P# A  C3 ~$ }15
16
17
18
19
20
& s4 b/ }8 P* i% L21
22
- J; U4 w. b, B! n" C23
# T3 r; U- D8 ]/ {% E/ V- W. {4 F( H24
+ z* Q9 {& q) ^. Y% j$ g1 J25
6 b0 Z3 l! X2 U- P26
27
28
% d7 w$ a1 D, @( a9 T29
8 y9 X% v3 ~3 \, ]  ?30
31
! _3 X/ R* {0 V0 q32
33
34
  c: s7 z" e7 s7 D! x35
36
37
运行截图：


+ {. `8 ~) S+ M" Z' R( e8 W3 F# `方法二：将最小元素交换到待排序列的第一个位置
7 w7 ?& G3 |* x+ }8 u, l* C
#include "stdio.h"
# p# t& J" @- K& m8 ^
typedef int ElemType;

; N  R1 d  v5 l- u% tvoid BubbleSort(ElemType a[],int n){
    bool flag;
; X' [  m" s; H    for (int i = 0; i < n-1; ++i) {
        flag= false;
        for (int j = n-1; j >i; --j) {
            if (a[j-1]>a[j]){
) W5 @0 M7 a- E; u                int temp=a[j];
4 K0 @/ i. H+ C0 r% u/ ^2 ]                a[j]=a[j-1];
                a[j-1]=temp;
0 n5 H3 ]* `! }& v8 M: R                flag=true;
            }
        }
        if (!flag)
  ~! U2 x4 N) s            return;
    }
}

; s* {8 d' q9 t% _1 Y
int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
8 B9 c& W( m1 k! J$ G9 G    printf("排序后为：");
$ T; v7 x6 R2 h4 i, A    BubbleSort(a,n);
" [- a4 g8 J; z1 U2 \    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
) ]2 f! g# f7 I! A0 T}
+ p, {% J+ f+ X6 w/ @% A
1
2
3
4
5
6
& ^9 l2 N" U8 \! p6 ]& r) }4 Z. n0 I7
: q8 B' F5 l. {6 Z1 g: t8
/ R+ ]' T. o3 C, B9
) r9 y2 Q  o! A2 @  h! L, D10
( ]6 Z* x  ]$ O1 X11
* f( g) ~- A# c% S' h12
13
14
6 D, v1 q8 S5 X" Y! N15
; d2 [9 b9 \- \3 Q8 Z16
17
& ~2 {9 I# _5 V18
19
8 ?7 p& q7 Y) a  c2 s20
21
22
" j/ E: F1 l5 o: I" A, M23
24
5 R! L2 V" G7 S+ c+ P# G25
26
' S' l* E! ^$ @27
  s, y1 F1 G# \! D7 t28
- n! P4 Z/ l3 f9 v+ ?. y) ]* ~# B29
30
" I# t% T) V" \; r8 \, C31
32
33
& c# ^4 N' ?- A. J! I' {8 q: P34
2 [: A# D: O) p- a  s" n/ d& c4 ]3 M35
36
$ c# H3 S/ r" t/ K/ }37
* I% ?5 G0 |. O# o运行截图：
6 ^. ]7 t7 M* v6 t% i+ {

性能

1 L2 ?9 J( j4 b9 P空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
2
)；平均时间复杂度：O ( n 2 ) O(n^2)O(n
: D5 I0 {- p2 b- o" z, B8 U$ {/ g2
8 O# U+ t" @/ Q2 j( R9 w )；
8 h# m3 u$ ]. o9 ^% g' q# q
- v) Y# Q. ]% k稳定性： 稳定

适用性: 适用于线性表为顺序存储和链式存储。
/ a& X+ i( x5 }1 X' h5 b( H
) h! e: e4 K) e% B7 d- N2.2 快速排序
( Q$ N9 j) J! `! Q# t' a图解（动图以后再补）
; a( ^6 S' q: {第一趟的排序：
8 w1 N, W" C( f
第二趟：
, b8 _2 v. ?1 Z/ [
4 H1 F- ^0 I5 w6 [9 b第三趟：


基本思想

快速排序的基本思想是基于分治法的:
$ B3 _, X$ r, [, k1 X: K, Z* G
5 k/ v& C3 ^- ]- B+ M! R在数组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步骤排序。直至所有元素排序完成。
代码
# v/ a; W5 ~" P6 J1 Z2 n$ O5 ?
0 Z, O$ s. U  z8 Y/ t! a3 D#include "stdio.h"
: ]% p. |6 X/ d
typedef int ElemType;

  a. \) b/ M* S# d7 m$ rint Partition(ElemType a[],int low,int high){
    ElemType pivot=a[low];
    while(low<high){
* B  a6 D* @' j- G  E' _        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
        while (low<high&&a[low]<=pivot) ++low;
1 F; t" A/ t9 J        a[high]=a[low];
6 {+ ?4 x6 ]/ }: ^4 Z* f    }
9 ]9 e- T) P6 c  B    a[low]=pivot;
    return low;
}

void QuickSort(ElemType a[],int low,int high){
    bool flag;
    if (low<high){
        int pivotpos=Partition(a,low,high);
: t$ }& q8 J; `% Z( M  h$ @; o        QuickSort(a,low,pivotpos-1);
$ T+ [) F& s3 \, C5 m        QuickSort(a,pivotpos+1,high);
# ]: {  ?8 R) e+ t- Y    }
' {& b7 p1 g; p1 q}

int main(){
    int n;
: p4 c) e5 T3 C9 j4 s' a, G    ElemType a[n];
7 F# ?' }* [7 K- g( r; p& F  g4 D" f    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
3 u  v" _# P/ |, F( o  R1 Q6 _, e    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
* G# a. k6 t3 y1 Y4 g! {    printf("排序后为：");
9 i3 u* c' |8 U1 }, U5 X    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
6 J5 R9 l  [& T}
6 G( B7 b; z2 [( Y: K# l8 W. D
# V3 U; @- F2 ]$ a9 j; a: i2 {- n1 t
1
- \: R7 W- }1 P, O2
3
4
" X6 [8 c2 |: U! m7 g! s1 a4 e9 M5
6
7
8
9
10
11
2 t2 f9 [9 L% d; n8 H12
13
2 |2 S( g& k, B5 \& M; Z# f" b14
7 t: W6 F" u" [9 K+ w15
16
5 U. Y0 d4 q$ \& l3 q, c5 {+ G% p7 S17
18
! X  ?+ m" ?# M& V4 y1 V* s: F19
, A' _/ h+ n: _& a  d2 r20
21
22
) p! t: a1 c; K* t23
  ~- C& v  h: `24
25
  g  q% J& h6 T& y( G  ]( [9 s26
2 v) r, N( e% Q27
28
29
30
31
32
33
34
' N/ }; ?+ e- ?* t0 d4 u) x35
3 ?# [+ ?3 L" P$ t" h36
; J- Y# V7 H9 s& L37
38
2 r0 \5 p; e+ f: q39
40
41
性能
' ?& S# d. `  c4 Y$ A4 ^0 p
! [! t6 x6 W7 j- n% M- L时间复杂度和空间复杂度
9 Y2 s' q2 r5 {% M& w稳定性：不稳定

3. 选择排序
3.1 简单选择排序
图解

7 e9 i0 y. C  d  V7 ?, s2 U
基本思想
5 B4 E# p  |1 s. `
在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]进行交换，第一趟排序完成。
3 f; q9 Y1 \7 F! l* U0 w+ @3 A在a[1…n-1]中继续进行排序。
代码

) u# C4 u0 N2 i0 a#include "stdio.h"
: R. ]" e* v- r7 t
7 u7 x, S0 V0 ^& x! l: A# Ttypedef int ElemType;

void SelectSort(ElemType a[],int n){
    for (int i = 0; i < n-1; ++i) {
        int min=i;
        for (int j = i+1; j < n; ++j)
            if (a[j]<a[min])
9 w. `& K; g7 W0 q9 B) C4 R                min=j;
0 D$ q: G% t( q; K- a/ q9 z$ s7 G        if (min!=i){
* k' q( Q5 a' q, U5 \+ O# n9 i. Q            int temp=a[min];
- V& B2 I- V& l            a[min]=a;
            a=temp;
& G/ t$ G. V7 z3 V" G        }
    }
* |, B9 C/ E0 u% V8 I( O}

int main(){
    int n;
9 s6 u! X" n4 @5 A( ]4 t    ElemType a[n];
' X+ J& Z. @) h3 Y6 I5 W    printf("一共有多少个数需要排序：");
+ |- I' S' g) x2 P& F# I    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
2 q/ b0 u0 T5 Y4 ?    }
    SelectSort(a,n);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
9 G. \( [5 Z$ Q. [2 N+ E: X        printf("%d  ",a);
    }
}
% d8 e. c  @# X2 q
$ f' a9 o7 n7 n3 o0 j" W! d1
0 d# O; e# g0 j6 V3 U2
3
4
. y; Q( O2 x, {6 K) f5
% l8 O( ~5 H0 X  P5 [, J  {6
: S" T1 @3 g4 h  C# q2 m! M, W7
) R( {% b4 n6 H8
9
10
11
12
13
* i! d% E- |- D$ x  X. E4 y14
8 D" P6 ~' l4 y! {: C15
16
17
18
* I" A5 z" y# n19
4 z0 b! M( O  k' {* A* B' D1 I20
9 g' Z/ r0 _0 _5 C# l% h3 e3 d+ ~21
22
23
- _: ^" z# k+ _4 r5 p24
25
26
27
0 F/ N( z1 o! N" c- F28
0 }- ]- s: s% Y( N$ W29
4 y* V2 _! T" i5 ?4 Q8 T30
31
32
# \* l' M+ o6 y7 @' T33
性能

, b8 u9 g: Y2 j) m空间复杂度：O ( 1 ) O(1)O(1)
# C1 e% _! P) m0 ^3 Q时间复杂度：O ( n 2 ) O(n^2)O(n
2
)
. B: U+ J3 n9 o. [5 E4 Z9 D0 w稳定性： 不稳定

使用性：顺序表和链表都适用。
7 e3 v. m2 L. H
3.2 堆排序
看堆排序的点击这里！！！！

" l( a3 \; E: C) F! a/ n3 j4. 归并排序和基数排序
9 ?" S6 B! r( `# f$ c2 j0 B* S/ B4.1 归并排序
3 f# r5 P( B: T- c/ ?图解
! N& e# {" f& w/ E2路归并排序


* V$ j* z9 y* g" d基本思想
3 H7 M1 D1 \9 t- b* ?
) T  b" \& D% {# H将待排序列分成长度为1的子表，然后两两归并，形成有序子表

然后将子表再次进行归并，直到子表的长度=待排序表的长度。
代码
  R) e% A$ w8 O6 X2 O& J( f
" m. l  y( ^, D' n5 S' x! |#include "stdio.h"
#include "stdlib.h"
" N. R( ?$ T0 M$ H# H
; _9 z5 q# o3 Otypedef int ElemType;

ElemType *b;

' Z( U$ e4 e5 Y' F) {% M/ i1 Rvoid Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
( L9 t) l2 L# h2 a# Q3 \( I; E    for (int k = low; k <= high; ++k) {
        b[k]=a[k];
    }
) n/ Z/ w, U) x. F. d3 C* Z6 k9 D    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
8 A! }/ f) ^  z5 |        if (b<=b[j])  a[k]=b[i++];
* c: s% B8 F. Q$ L4 V        else a[k]=b[j++];
2 Q7 b7 r0 H1 v7 B, T% q    }
    while (i<=mid) a[k++]=b[i++];
    while (j<=high) a[k++]=b[j++];
}

void MergeSort(ElemType a[],int low,int high){
    if(low<high){
: j6 Y7 u- v  e/ m/ I        int mid=(low+high)/2;
+ j6 u& |& }% A3 n4 |" P! g( ]        MergeSort(a,low,mid);
4 q  ~, H  ~4 y  s9 Q& w7 C        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
& _' L% g3 [  Q+ S4 n( h; B, ^}
, C% a  w) L, _( f* q
- c" A$ w7 J2 ~  v3 N) G& K/ Gint main(){
8 J3 j( i% ~6 ~6 m3 c    int n;
    ElemType a[n];
    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
    printf("一共有多少个数需要排序：");
& c: |7 ~7 Y' z8 b    scanf("%d",&n);
. z/ N4 R2 M6 T- S3 A2 E/ E    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
+ H# T6 l: g& U8 z0 a, L        scanf("%d",&a);
" G4 E1 H2 \- g9 Z% `    }
    MergeSort(a,0,n-1);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
$ L" D5 a! N: m/ V0 a* |        printf("%d  ",a);
6 b5 O) T5 V6 J3 M8 ?) x! Q/ Z/ X4 X    }
# o) q) @/ V, ]1 p2 x1 Y+ H}
+ |- C# ?, N: T/ A
7 B2 Y1 H1 ]; \
1
2
  j$ W* V, R/ ]0 c: y' B! Z% Z, T4 d3
% T6 R. ^( T7 q9 g4 r4
5
: k) E9 v: ]/ I) v6
7
2 a+ G" S# h- _3 d/ r+ n/ R6 _8 ]8
' N9 B# {: y- ]" v- D. A& Q8 A0 h9
10
9 I5 z5 r1 L2 H& n. G4 j, c11
12
0 C- D3 u! h: E3 v: }# H1 }13
3 G4 @5 k7 f3 T; ~14
5 s5 a9 j3 l1 h7 c0 _15
, @; d3 }) }6 Q4 c9 F# m. F+ m16
17
- ]$ x: ~' o0 F$ C  k) W1 R/ a18
19
& P" A, s6 S2 j% k) l! M20
! ?2 Y  u  {8 |21
; U3 z4 P0 Y. ]7 _+ `, K3 \; j22
23
2 g1 C  q+ J7 x* t6 `2 L# A" T24
25
26
27
28
; u  O( ?: Z" k% \0 u8 T: U29
30
31
# Y+ g. z9 a: M$ a* q6 j% X32
33
5 y: L2 `5 O, t' d34
35
36
37
9 z7 w" I* |8 c# l, D7 ^$ n- u  {38
39
40
41
42
43
44
45
46
性能
9 o/ Z4 Q/ N% a4 E) T( K' `
( _# b; S. F4 K: _空间效率：O ( n ) O(n)O(n)      创建了一个数组b
时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
6 K( }5 ~$ J1 t  A1 rk
$ @1 {% u$ M* E9 a( g​
! M  \3 {7 U) @% e n)  k指k路归并排序。
4 `7 v9 ?  _' b/ ~2 f4 w稳定性：稳定

4.2 基数排序
* k$ }5 t& W) {% ^3 U; w$ m. T4 g# Q图解
) G% L8 T. B8 M% E0 K7 P# ]( P5 ~

基本思想

将各个位数（个位、十位、百位…）进行对比。
3 e4 ~( f% \) S9 U9 U为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。

性能

/ q+ q, e2 t+ Y/ p5 p  X空间复杂度
# b. N1 f0 U' T' ~' h
. d/ Z2 H' K. ^0 g+ T时间复杂度
! ^  i: t+ T9 `+ D) h9 o+ }

稳定性：稳定
7 W& r) U) a" g9 l( i$ B
; u  [5 L5 j/ V/ {$ G- H5. 内部排序算法比较及应用
; P; U  t) p9 t3 G4 U( s. W: U5.1 整体比较


5.2 时间、空间和稳定性

. _4 ^* K; `! }% p
参考资料
3 F6 _7 z. y" W. P& Z《王道：23数据结构考研复习资料》
5 S+ A8 u# M# q/ R& k2 n) H# y0 L- T————————————————
: {1 ?8 y# c% k, l: j/ ~版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. Z" P$ [0 U- U: _" _原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678

; V1 T/ m  F2 ~0 k% [7 t% O& N7 ~