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

杨利霞

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

; J5 C, k# K6 x5 q  D排序
2 S$ k' Y! e2 W4 g' [1. 插入排序
( n3 E. Y( z+ t  f0 L1.1 直接插入排序
1.2 折半插入排序
( Q) G( ]# Q# `1.3 希尔排序
, J( N* q5 j# E; V9 G( Z$ T2. 交换排序
2.1 冒泡排序
2.2 快速排序
3. 选择排序
3.1 简单选择排序
3.2 堆排序
4. 归并排序和基数排序
+ T  q5 F% `. T  x4.1 归并排序
1 O7 W! X5 `% W: @6 S4.2 基数排序
& `/ g. H& }* U2 a1 t5. 内部排序算法比较及应用
- w: B" v3 a! }5.1 整体比较
5.2 时间、空间和稳定性
& T: I1 [0 `, M' S& |4 |参考资料
4 x5 \* r5 K( f+ X% e# y/ W
内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
- q( [! O' O$ Z+ Y+ b) S1. 插入排序
, e* |# D/ @$ I5 d& o1.1 直接插入排序
# y3 d& R: l3 Q图解
4 A$ m/ l+ \( n* S) r- `6 N9 b& g

( z" {2 F+ |& ^% Q6 f0 {  b: I& x基本思想
7 J; p3 L( J- s- Z; n1 z
# K3 Y; s  m5 h/ A% `& Y0 B& o1. 查找a元素在第1 ~ i-1中的位置k
2. 将k ~ i-1位置上的所有元素向后移动一个位置
3. 将a复制到a[k]

0 Y. l$ p1 B& L+ J8 P, l" ]$ j

% J6 k) a" L5 O! L1 k代码

4 z2 Q) k- E8 ?5 {1 Y方法一：

8 w; w0 J) t( v& x% S数组的下标从0开始，如上图。
* J# o% s% T1 C' B6 a* r4 }9 \3 D
#include "stdio.h"
* W3 T0 T4 f" i
! L! p, v% {; g8 @. R& U( \typedef int ElemType;

2 {( X5 B, n. J3 d1 xvoid Insert(ElemType a[],int n){
- Q& R0 }; V; s& |* K7 I0 k+ D  m9 w    ElemType temp;
0 N4 F& n" C5 t# @1 n* M2 r+ e    int j;
    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
3 [7 x) p2 K5 v# ?- ~" m7 Q& s        if (a<a[i-1]){
            temp=a;                                                               
            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
! J& _: [3 s) A' t9 }! F% e! f) o) y7 h                a[j+1]=a[j];
            a[j+1]=temp;                                                       
        }
    }
}

int main(){
    int n;
2 x6 V7 A7 ~  D, Z# U% Z3 P+ ?" c    ElemType a[n];
' T- ]9 T5 }. T4 }/ Y9 _    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
: w6 [+ K/ b/ W    for (int i = 0; i < n; ++i) {
* \: T1 L) h  k. w" O+ K        scanf("%d",&a);
    }
    Insert(a,n);
5 j9 d2 h. f. i3 E; K7 }" ^    printf("排序后为：");
6 B, Y2 ~, [; O    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
4 k7 n- W. a3 M# o, g& O    }
/ l; h; b$ F9 L7 H}
! p  a; n/ j) D# Y0 s$ t
1
1 k" [& b7 s* R' a# D2
5 ]) @# z' `9 A+ `3
0 m  \& [1 l+ \: E1 [5 D4
5
6
4 H& T' ?" m8 e. z& ?7
8 i9 W' C8 g5 N+ ?8
! T* q* F) |: t3 M9
  Y: s2 _. T2 I/ J& z+ e10
11
5 I  n6 }, k, U3 u0 |' {12
. w* C; d5 J- f! l$ v- K13
! L, l/ X) q, U$ ?0 ^14
. h9 t4 I& p- n0 H5 W& C5 X! Z5 p! b* z15
. t6 m) t! q) N" R2 ]! R4 D16
7 D/ ?( I8 r7 V6 r% H17
18
* ~' p( x" k2 [* C/ w, M2 M19
20
$ [4 B/ q5 P/ f- h1 M6 ~  O1 p3 Z; e21
, m, F4 q0 o6 l8 p22
) E* U/ ^, ]1 V5 j) \23
24
/ \$ A! M$ h$ p' \25
2 Z5 x: ?  b: H26
27
# N& I- A4 \! ]: `  J6 f28
29
! u1 `; J) k$ k% G, g& |30
3 i4 z4 V1 c* Z* O% A31
7 u: R. l' W  C; Y32
方法二：

. u9 e: ^! @) H+ J
! v. x# Q$ K- I* B9 _2 M' T
* m; [, w9 }. a# c6 I#include "stdio.h"

typedef int ElemType;

6 I, i4 ?4 b) D& nvoid InsertSort(ElemType a[],int n){      
    int i,j;
: F2 Q+ R- G8 x; S    for (i = 2; i <=n; i++) {
        if (a<a[i-1]){
            a[0]=a;
            for (j = i-1; a[0]<a[j]; --j)
                a[j+1]=a[j];
            a[j+1]=a[0];
1 l# R% e7 q( S% ?, \; H; ?        }
    }
}
' J/ N% A/ x4 `6 Oint main(){
; f2 a, T( i5 O) L% o9 I9 g. O    int n;
    ElemType a[n];
4 P9 [7 B4 D/ L% C0 d1 N    printf("一共有多少个数需要排序：");
+ W0 b! e8 P% {; w    scanf("%d",&n);
    printf("请输入%d个数：",n);
  i' ?: @4 R- ?7 Y* @4 q    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
  R+ K; [8 w0 e5 a/ o    }
& `6 z* [' N7 c! O# _3 E    InsertSort(a,n);
* D; D2 b- i$ ]& {    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
. w  C5 w+ |. e  V- |9 o4 h/ Q9 z    }
4 k3 j* b$ }6 a( k# M# _" c}
  Y! y, T1 T: V+ U+ s
9 L+ \7 _& E4 V4 c( w: J- x/ k: a/ i1
! k0 [3 r& ]8 F- u0 ]$ B  g" W. }2
3
: r/ r* c5 {! I+ e2 L7 M" ~: G4
7 p0 P* b: R: ]) ]5 U5
3 d' K; j2 u5 k; _. B) j; b6
5 T, z+ v* U' Y) V0 X. {8 O2 C7
- `: J  \& ]7 Y( K0 `9 a. c8
9
10
11
' a, ]6 T* C+ [12
8 Z  i( H" Y& P  ?. t13
14
" a/ s9 e1 R* V0 @3 B15
16
17
. D. }$ m2 Q, X0 o0 x18
. W# v# ~$ T/ A9 V; l8 ]. s9 H" W19
+ _8 g3 H! W; e" M6 L1 c. b20
5 D. i- p2 [+ W3 u  b21
22
23
24
) k' o' E: {+ K5 w; A+ d25
' L- J# i8 @6 y. Q$ F5 C26
- x. J0 P; i- e7 B27
28
+ ~) ]! v! h5 S( Q4 v29
7 ]* |, A' h: Z8 j, O30
/ o; }7 L5 e5 A0 ]算法性能
. x# U5 m; z, t! D7 {' K( Y9 Y! H
空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)
; z( b6 ?" g. c% I
时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
)
8 o, E( ~5 {8 _1 \9 c- \* ]9 l
: c8 P6 k. O2 |, P+ D# y. P# i
稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
3 q3 C, L! o2 c" K' g" m2 T
8 P) W- a- {" _$ e+ ^适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。
# |8 J1 Z; K! o2 D# K4 i/ G
8 J4 N/ ^6 O8 _1 n4 X4 n- Y9 ~$ V; f1.2 折半插入排序
图解
- F3 I9 o7 \8 W! K7 @, m  P第一趟：

) _" n) `$ `( @/ t1 D+ B第二趟：


第三趟：

4 t* r, k( Z& @& x3 i. p- p# w第四趟：略
第五趟：略

基本思想
1 w* _& i) a3 n' c
与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
; H, Z; O' C0 S& H( l1 i取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
代码
- K- v6 l2 s/ E8 b' }
#include "stdio.h"
2 ?. ~7 d/ \3 `+ |6 g- z
typedef int ElemType;
; {5 h3 M9 I" B* n5 I
/ I- c( e7 p2 N( cvoid InsertSort(ElemType a[],int n){
; |# N; r. n8 r0 {) }    int low,hight,mid;
( A7 V3 m, G/ b- Q1 O1 R* |    for (int i = 2; i <= n; ++i) {
( k7 v8 F: Y7 U4 U        a[0]=a;
        low=1;hight=i-1;
        while (low<=hight){
+ d. Z9 T$ b4 \( h: d            mid=(low+hight)/2;
            if (a[mid]>a[0])hight=mid-1;
            else low=mid+1;
        }
        for (int j = i-1; j >= hight+1 ; --j)
            a[j+1]=a[j];
" b  H" s  x9 T  {2 d/ u& F        a[hight+1]=a[0];
    }
}

4 {* `" E, I! p: j
int main(){
, U& q5 Q/ |6 D" i# p1 x    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
) m* I( Q6 h, m    scanf("%d",&n);
: u9 T) q6 w7 B7 }& e0 p! O    printf("请输入%d个数：",n);
; Q% T0 f! [8 t) q    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
    InsertSort(a,n);

    for (int i = 1; i <= n; ++i) {
) |: }, f& o  \1 z3 @% {        printf("%d\t",a);
    }
}

! p$ m# v& r& V7 l2 S1
2
; ~( c: v/ ?& ^2 @) [* j3
9 Q1 Q, y: n1 Z4
5
6
7
8
9 Q) B$ G7 P1 [7 n0 I9
  [9 A5 W6 o6 c10
11
12
0 ^1 ?* C- v3 e- b- m/ J13
14
15
16
17
18
19
20
21
  j4 l7 B: n. k  p5 I22
/ X1 e& ~' u0 ?* \- e9 l, E; E" z23
24
% l; k6 ]6 L6 ~2 |& k$ a25
26
4 k2 W3 |0 v) O27
28
2 S) Y. h  P2 y1 S, b6 [29
( l# V) m# {- {/ v& d  x30
31
32
' Y7 U0 T* z) V* P33
34
35
36
37
# A& p) I9 {9 B6 L5 N性能
8 e2 A6 X$ e/ w+ B3 t; [: G- G9 q% Z
% |0 ~+ e6 }* u9 T! x3 w! a空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
$ g1 d4 `5 W+ E2
)
稳定性：稳定
适用性：仅适用于顺序表
: n/ M% W* a( L
1.3 希尔排序
图解(动图)
1 q! j. \7 K8 i) M
8 ^6 Y) l2 w3 i! k* s% L& h
! G) V( F4 ?- i1 q0 E. F基本思想
0 z; E- {- X" I3 F# e
) B3 u& c2 K6 R+ U先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
! L4 D9 Y8 O7 w' N/ R
代码

#include "stdio.h"
+ [+ ~8 Y2 A5 B5 i
typedef int ElemType;
, k) q  K9 E4 `& L% [
1 t8 ^9 }& Q$ U/ t) ]void ShellSort(ElemType a[],int n){
    int j;
$ P# M, m+ M! x% ?/ B! L    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
2 t% C% a% q/ c# V" T  ]# y        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
            if (a<a[i-dk]){
" W7 h; \/ Y, Z4 O5 v                a[0]=a;
5 V3 m* m9 c9 X                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
                    a[j+dk]=a[j];
& O9 K" o0 s# n2 C                a[j+dk]=a[0];
4 w; R& V' q# q            }
: |3 @2 N; ]! p7 g* p2 \        }
, w6 a+ L9 j" T7 h8 t; t% m% h! a    }
' `7 e0 v6 ~$ _5 O9 }* T}

* C, A5 G  z" j, V# R7 Cint main(){
; ?. [% T& T* _0 U6 A4 f0 Z    int n;
    ElemType a[n];
0 d2 `6 ]' C) \# H    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
( B  Z2 X5 Z. m, d- B    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
* c5 B5 u$ U" e" D: i    printf("排序后为：");
    ShellSort(a,n);

" p) g+ K; C( a. ]! `! p, p    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
+ Z  |) v! ?+ [6 ?. P    }
}

  O, |7 ^0 a. f; Y" K9 z4 ~1
) }& e3 E9 k; ^" P2
3
4
5
6
7
3 N' a# \0 t8 I7 E+ h4 y8
9
10
11
12
13
14
* f+ x  j' b3 c0 Y15
4 ?& u# A* A. v. H16
17
8 P+ m! ^: F# s+ c% W4 x6 C18
19
2 @! @4 v: I2 E( |: o, K! ?! k: m7 G& U20
21
+ V5 q! T) l) W4 _22
! t4 g- ~5 E7 D2 |4 W23
24
25
26
27
28
7 _3 P* W9 a. T29
& C+ ~+ \" Z6 m" u& c! q  S2 J30
31
32
33
34
0 ?( I% q1 E$ ~* f/ A& P性能

空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
" r5 A1 z! k. ]* x# @9 B8 b  n
时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
/ }/ x# A* _+ j! D  B4 n1 _& f1.3
5 {8 D9 m2 X9 O6 w' G, d( W )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
2
)
1 X7 T8 Q: X+ s8 T/ ^7 {" s4 \) A% p
稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
, z. a9 J. P3 E' ]7 `9 U

6 Q0 y5 }" z5 |' k4 o6 d适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。
4 U" E( @8 }9 w" _% ]
2. 交换排序
2.1 冒泡排序
图解
+ ?( z; n3 Z6 e  ^: L
6 N9 S  f0 C2 t! a
. }; A5 x& }8 y$ ?7 o3 F基本思想

1 c$ r& t4 U" j) M& l6 R' J从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。
! Z3 ~1 h" Q$ Y; O* ]
9 b+ R# u) M+ F4 @1 G代码

( t4 ?5 k9 m/ `9 i  o方法一：将最大元素交换到待排序列的最后一个位置

#include "stdio.h"

typedef int ElemType;

void BubbleSort(ElemType a[],int n){
    bool flag;
4 x( _5 a9 K2 b; T8 U    for (int i = 0; i < n-1; ++i) {
        flag= false;
        for (int j = 0; j < n-i-1; ++j) {
- c$ f9 n! s. {/ _" N* z8 Z            if (a[j]>a[j+1]){
; T. h/ F* y# l/ d                int temp=a[j];
                a[j]=a[j+1];
. S6 q$ Z' I$ x* ~9 m7 A                a[j+1]=temp;
                flag=true;
+ H) k% Q$ Z) {8 d" h            }
( s0 J( x* e8 C& U- K        }
        if (!flag)
- T9 r4 I# E. q            return;
' o  Z6 _: }$ ?1 h  G) Q    }
+ ~0 `7 z- v2 n5 j4 Y& U}
" X0 A: v# |9 ~- M/ y
/ F) t  O3 x) [+ C$ M
6 {$ s: H, {5 }int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
4 G& s- B0 m: |7 Z% u    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
1 V0 j1 K7 U1 W& n! I$ B    }
; Z" S/ n& \3 q2 r! e    printf("排序后为：");
    BubbleSort(a,n);
5 K( s2 z, Z1 A' B' S    for (int i = 0; i < n; ++i) {
& s: C6 ?( x- ?% E+ O  {        printf("%d\t",a);
    }
}

1
1 {- s3 C- O7 `' Q9 F7 t2
- B3 l- ^, T4 v* }- w; p3
& s1 \4 ^- e2 Z; F& ~  f1 e, _4
- U& a: `3 x0 A, y5 h- m5
( D6 P6 @) _$ k; |9 i6
; m( ^0 |& e4 m, t7
8
9 k- ~/ Q/ V5 v9
4 e2 _1 ]& ^- T5 l+ U+ M! F10
: g+ o! Z7 a+ U( {11
, y+ q( c6 f8 e, M. B12
13
14
* n+ b7 _5 ?/ v8 ]& \15
; }( i2 M5 Y% ~# c+ j16
3 u% x1 T) K, R: H  |0 ~& ]17
18
/ r3 A0 v1 o/ d/ I/ q19
: r/ f, r) S2 F1 i+ d; D20
' t) @7 c9 \" k  t' l7 O, T4 r, p7 M21
22
* U+ |$ a. \  R23
: A7 }  H) T* [2 M7 y24
25
26
27
28
29
30
31
32
33
34
/ b; k$ }+ J! M1 l- k( F! g1 t35
36
37
' b1 U3 `2 N5 @6 i运行截图：


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

' k! P& h7 @  x# z7 `#include "stdio.h"
. Z' U1 m# O0 v) J: ?# W
typedef int ElemType;
) X% _, y6 G5 y
+ o% K: K* U. x" avoid BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
7 C& E( e5 c" x% P        flag= false;
        for (int j = n-1; j >i; --j) {
9 ^# y9 j. L6 U% g  `            if (a[j-1]>a[j]){
                int temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
                flag=true;
            }
        }
1 ^% T3 l" R0 q5 F4 Y        if (!flag)
            return;
    }
}
" ]/ S5 f% ?5 U, |
% M: z% s% Y4 A9 @1 }3 e1 e0 d3 C
int main(){
    int n;
+ m$ [5 N  K$ o( T( \- S3 i; q    ElemType a[n];
# K8 ~/ D) M9 ]( P    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
2 m1 W; @6 M- S( R. u    printf("请输入%d个数：",n);
) `: ^0 {% T* s" @# I    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
$ |3 {# P$ c6 T2 _    }
}

/ z6 f: Z2 `2 `7 B5 g% B6 ~2 h4 d/ ?1
2
6 b: V0 d! f3 F. p& i; C3
- t# U( K5 }1 O& o, J7 z4
+ \" D0 S0 B" k% [$ X5 l4 E5
6
7
& D; d9 ~( u; z/ `5 g% i+ f! ~8
  W. v0 a8 O' |9
+ ~, J, ?. N- @- ^5 v10
$ u( M: ^3 V  C" c9 i2 h- A11
4 U4 K+ {; T) h: n9 Z12
13
; V1 k4 e  {* ~; {: l( E* }14
3 w0 A( M/ S1 e15
+ X; G* k, {8 M6 Z; z. e1 l16
17
; u. @; p7 l8 {% b+ D1 @, K18
8 ~( O( _0 V" B6 Z0 f) n7 m19
) _3 l6 s- g% J- O4 y20
21
+ t& @" w' }% Q) P6 w22
23
24
% H" M' o( G/ \8 y25
/ \; L( p7 B8 I& p) N8 X( S$ h/ w6 ^26
27
& y0 P3 U8 d. S28
$ `* e1 _4 U  q7 E4 N29
2 Q' y3 O2 w3 r+ W" K! k8 b4 |30
31
9 J$ h  j+ a2 I( a8 {32
) [- m1 S! i3 t$ P/ ], l33
34
35
36
+ ~7 J2 ^. q5 i1 o37
运行截图：
1 T) ?+ j9 y+ W$ i7 x& p% e
" C# j: c- c: t8 h) {, S4 d1 Z
性能
- v; q1 z8 k$ u" t+ P- r% H
空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
& `& ]$ I7 ~2 _+ R2 Z8 D7 e
0 T' Z; b- j* }# L4 y& g时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
2
)；平均时间复杂度：O ( n 2 ) O(n^2)O(n
! b" c5 g0 T- W9 q2
)；

稳定性： 稳定

, Y0 m* W9 v6 w( j; I适用性: 适用于线性表为顺序存储和链式存储。
3 `$ p# S8 p5 }
' }8 ~9 N/ ^( ^. g% Y, O9 P7 L7 a2.2 快速排序
图解（动图以后再补）
; E$ x4 L% Q; s$ ~第一趟的排序：

2 ^  o: w4 C/ N  B3 k; |第二趟：

; G  l+ Q% n! u8 Q第三趟：

; T0 R1 d+ u7 @# t  i
* L* ^) ~2 k1 a& i3 V3 j7 `基本思想

0 M, ^& ?8 g8 \9 Q. f* ^% L) I- g快速排序的基本思想是基于分治法的:

9 @( j$ c+ r0 F8 K; u, L: d& \在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
' N1 a- R( N" f6 M' f7 X然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
1 W+ y% d8 Z( ?' L5 E6 E/ u代码
+ u0 h8 _1 B7 a
6 r! X0 }8 C% I1 B#include "stdio.h"

typedef int ElemType;
3 U* _1 v! f' z+ g- L
int Partition(ElemType a[],int low,int high){
' d/ g, `# m; ^3 r    ElemType pivot=a[low];
, g: j, D' ~8 ?. e8 C    while(low<high){
+ L# d# F1 v- a# S, P: E  N4 V        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
6 F9 n5 u% A: \        while (low<high&&a[low]<=pivot) ++low;
        a[high]=a[low];
( H( X6 w7 P4 ^9 b' |( d% i    }
- b* S4 U  ?3 s  H8 q! I1 N    a[low]=pivot;
$ \" I+ a. |  G2 R, N    return low;
}

: p" c. z4 F3 L! r9 w- lvoid QuickSort(ElemType a[],int low,int high){
. [4 T- t: B$ y, B: D* b. r    bool flag;
# `% L' |2 ^. v8 d6 }7 Q    if (low<high){
        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
* O1 s/ n6 H' D        QuickSort(a,pivotpos+1,high);
    }
}

. {0 v' g) |7 V# y4 z/ ^9 R6 `int main(){
    int n;
* r' F! j$ x' I, D    ElemType a[n];
    printf("一共有多少个数需要排序：");
4 y4 J( N4 @" _    scanf("%d",&n);
+ G0 Z, x0 c, I3 B1 b& t  A4 C    printf("请输入%d个数：",n);
  L) T6 }, }( B4 D* G    for (int i = 0; i < n; ++i) {
: D) i. @: r) i% _$ W( p. o        scanf("%d",&a);
    }
" O& }/ [/ b* M, M% y    printf("排序后为：");
    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
' I7 l: A9 B4 ^. p3 _9 H/ A" [% e  L        printf("%d  ",a);
    }
. z( u2 W* Q! i, v( l, T}
2 }' Q  N. i8 p8 j( W, g

1
2
# V7 t9 P2 V  L2 p8 g3
4
: r0 t4 _; B. J" L, N5
6
7
$ b9 y  T) q% y; q: m3 n/ D8
, ]  U1 ~( Q- O( g/ }- n) u5 i& t9
3 B  M' Y* \; z* _/ O5 Y) F10
11
12
9 {' m2 D6 g7 |" @  A" B13
2 a0 n; k6 g9 H" X4 o4 C/ g14
15
16
3 ?9 g: ]0 U- V# f6 d. ^17
18
6 C% L* O& B; Y+ N5 d+ w$ B0 u0 h, G19
20
& G8 t/ e' Z( t21
22
23
! x, T. ]5 g( ]+ U24
" l) v* e9 H1 ^, {0 K25
26
/ O( H. I8 k% k, b" V3 G27
  m* m0 A" |. }. W* r( m: X+ Q6 V28
29
* G  e0 q9 b# f% w4 r4 I, {8 a1 ^30
31
32
. r) N# C4 @. U+ f33
$ q. S& t( k# Z; o4 f9 ~34
35
36
: v6 k. f8 y. j4 P, k7 S37
38
39
40
41
性能
$ ?, |7 r0 Z- p# Y
时间复杂度和空间复杂度
$ q5 E  h) b$ {稳定性：不稳定

% D! n7 k. X+ v3 A- ]$ m, V3. 选择排序
" c) F  z4 n# W& G5 ~2 K3.1 简单选择排序
图解


基本思想
) V/ ^$ X( i2 ?# c0 \
  q) D" {7 `5 S% _1 F- u8 x在a[0…n-1]中，将a[0]设为最小元素，设min=0
在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
8 S. y  C7 b; b# j" r& {6 N若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
在a[1…n-1]中继续进行排序。
; v8 n) o% L3 o1 H" E% T代码
: M! P* {  M, w8 e% L4 t
#include "stdio.h"

typedef int ElemType;
  y1 X6 ~6 K8 [% }" Q8 a* P9 y( }$ x
void SelectSort(ElemType a[],int n){
: F. A1 u$ P0 `4 M& |9 ~& X    for (int i = 0; i < n-1; ++i) {
        int min=i;
& y8 b0 S7 u3 ]: z% @5 \        for (int j = i+1; j < n; ++j)
7 Q$ {% U6 M7 O# F2 S" R            if (a[j]<a[min])
- l- F& H. Q" n. [" u3 M- B                min=j;
0 N- e9 ?! j* ^        if (min!=i){
            int temp=a[min];
* |# N4 w9 _- q' V. C) B! Z            a[min]=a;
8 R* }  w; t7 p' V            a=temp;
        }
1 `* f9 ^' S2 n$ @; r    }
}

int main(){
    int n;
5 b9 |( C& ]$ I3 F; k    ElemType a[n];
5 ]: ^( M1 `3 n/ E7 ?    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    SelectSort(a,n);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
$ g2 e9 z4 `3 P1 g" Q( l        printf("%d  ",a);
" K2 t  i3 |& G7 B1 x& o# D# ]    }
}

$ w5 B- n4 Q7 n1
2
2 d8 S: ?; }; B+ L" d3
4
5
. l! n# U1 H" K2 U( d* J$ P6
1 V5 Y7 N* i: O+ C6 R+ l2 Z* `7
" J  Q  r7 ~6 U8
" g+ |! P, z& F$ |: R% E8 Z9
2 @/ h* ^/ b; \- b7 G- @: f4 [) `+ r10
) C9 R! u+ w( z0 N* j- t! {" V  z/ V2 f11
12
13
' _  Y* T* K* ?5 @6 c& c# X' }14
15
16
: f& h% X+ t; T( p8 l& ?7 U17
/ `- R6 A  q3 ~: b18
19
20
21
22
9 b( T2 q' O1 ^- Z23
+ n: a5 s. N. T$ z9 @8 [24
25
* f3 ]/ p3 N: m9 j$ H26
27
28
# |* k3 R) C) V6 R! D29
30
31
: m3 G5 p* b3 J  M; Z9 _! ^+ }: ]7 }32
33
, H& [9 Z+ c; H( h' f8 ~7 I性能

. C! m4 Q' D0 ~7 G4 q6 y空间复杂度：O ( 1 ) O(1)O(1)
$ c7 y: b1 Z, \7 ?. y3 h1 o时间复杂度：O ( n 2 ) O(n^2)O(n
2
- y$ H2 V- A9 c9 G/ C: B )
* r4 Y6 S: I' b0 M  {稳定性： 不稳定

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

3.2 堆排序
4 {7 w# X: g3 \' m- K' r看堆排序的点击这里！！！！
; |' V" o! {3 H1 h6 ~
( f1 M- f0 {+ z0 h4 |/ u+ q! f4. 归并排序和基数排序
4 T4 I) f5 u* v) s/ x4.1 归并排序
图解
2路归并排序
; z6 v( e. h% o  o+ V( C# s, o
; Z2 ~# k$ S4 n
; Q# O3 o; u; h( j0 S- u8 m基本思想
3 m+ U' C" @+ ^* i0 F8 G4 X
) R( w! n  ^5 F/ ]4 f% D将待排序列分成长度为1的子表，然后两两归并，形成有序子表

然后将子表再次进行归并，直到子表的长度=待排序表的长度。
代码

4 X  e& J3 L) B3 W#include "stdio.h"
/ [1 s0 x. w) F1 k& y8 g#include "stdlib.h"
' Z# B7 ^( f" p6 b
typedef int ElemType;

ElemType *b;

void Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
2 |+ t' B& {" Q( |5 Z1 V7 x. l    for (int k = low; k <= high; ++k) {
        b[k]=a[k];
    }
+ M* {7 r& z* b; f) w; \; \8 V    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
& O% J0 w6 y6 t. r3 \9 b        if (b<=b[j])  a[k]=b[i++];
        else a[k]=b[j++];
; o4 l. ^+ ]  @( |/ A    }
  i! C! S* q2 O4 @  m# Y    while (i<=mid) a[k++]=b[i++];
# ?- B3 F) W$ [5 I0 ?7 b2 R0 m: B    while (j<=high) a[k++]=b[j++];
}
6 G% y2 T+ B( u' r  m3 K; ^& S% I1 E
! ]7 e, Y3 c( @2 B0 Ovoid MergeSort(ElemType a[],int low,int high){
( X  a1 q$ D8 d2 Z    if(low<high){
        int mid=(low+high)/2;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
: d' a$ f1 L: G! N" @3 ?        Merge(a,low,mid,high);
    }
}
0 L, a( Q* `' u- o) I$ `# r
: n) \2 |2 h8 n* y" c) lint main(){
9 D; m% |% S  p/ _7 j' z% z0 F    int n;
5 F: {4 n& K( i" K) s3 ]    ElemType a[n];
, r6 @, P# h6 m& Q) {% Z& m- T    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
! X, T3 y; _' j- P    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
0 P& s+ K& I# K. k9 H    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
% D) z( X" T: C; N5 h  B        scanf("%d",&a);
    }
  g, |0 l" d0 f! ^0 G. S6 _3 H! ]    MergeSort(a,0,n-1);
3 G. {: c  n  f    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
! \5 ^! m' c8 |    }
" b% g6 A) b- ]" k}
5 Z+ k1 J3 P0 C

1
2
3
4
( ^/ x# Z0 K$ t6 V$ a7 c5
6
7
8
9
10
11
" Z6 Z; c* ]6 k3 a12
13
14
15
. e9 N' b  n- }: @3 u1 W8 m16
/ m% F$ T5 d$ K% w! O17
: k7 |6 v9 C7 S  Z8 g; I' F18
; Y1 v9 P3 A% P0 I19
20
21
22
; ]  n6 a! u% y- U+ |" T23
  }; W* A7 A* q- R& \( |24
25
26
" j' g/ n) n! b+ V3 u3 ~' Q9 {27
28
29
30
* i: v/ o" S2 a1 B31
- x9 `& L/ e% k( ]5 H8 e6 i! R6 M+ t3 d32
33
34
6 v' o7 e! L9 k2 b35
2 j" s5 v2 r" q) ^36
1 n" I  T% n, \# ^+ ^1 j/ ^37
38
$ M! D9 L" P3 m) \. F39
" P2 H! L$ Y0 A" H40
! Y/ Y/ V1 P- \5 P& r41
42
3 t+ S- Y7 G1 q4 r9 }8 Q43
44
8 V/ }& m& I( r, K/ q45
$ Z  N4 d; s% c# v% B8 s# S46
9 O$ _' C3 x9 Z1 u2 R2 F* E3 k性能

2 e1 j; g) s3 b- o( K空间效率：O ( n ) O(n)O(n)      创建了一个数组b
时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
​
+ k; D3 A/ Y3 L' Y8 V& ]+ Q" y n)  k指k路归并排序。
7 [: y. D& D) \- ^1 ?稳定性：稳定
/ l, B  B# @8 ~8 Y7 ~
" U$ s5 u' Q& F% s/ w4.2 基数排序
图解

8 h. V# L8 r7 [
( n4 u# D& e/ C8 t% O基本思想

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

性能

+ V* c2 Z: [, _6 m. H空间复杂度
5 T7 j8 X  W/ e
9 i$ B( J, r0 s, W$ k% b时间复杂度


稳定性：稳定

( l" ?% I) [% M# y, h5. 内部排序算法比较及应用
2 h& |) A7 x% m& O" E5.1 整体比较

: C% r( m" a  m- N2 b" z7 u
5.2 时间、空间和稳定性
( j0 s& n; k7 Z& r# A9 A9 ~
" u+ N0 P% V6 N/ `4 f1 D) p
- O! \0 _' U2 D+ V1 r# Q. k参考资料
《王道：23数据结构考研复习资料》
————————————————
版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# S. x& ]/ N0 l- F( o) Q原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678
4 q6 o( g: R+ |8 k" c. w