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

杨利霞

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

% R9 i' [+ b; R: q1 S6 ]排序
+ l. V% b8 S6 d; w  @  y1. 插入排序
3 w  I- F2 }  }3 q7 I1.1 直接插入排序
1.2 折半插入排序
0 Y. f. U* M# c: t% l  K1.3 希尔排序
2. 交换排序
2.1 冒泡排序
2.2 快速排序
) u) Q" G+ i8 l4 W: t3. 选择排序
3.1 简单选择排序
3 W# t& j' ^5 j8 B5 `; }3.2 堆排序
6 n. r% I# l" A6 v4. 归并排序和基数排序
4.1 归并排序
% h. W! o9 \; P' J$ F4.2 基数排序
3 t8 r9 J/ @3 c' r# b5. 内部排序算法比较及应用
5.1 整体比较
5.2 时间、空间和稳定性
1 w% F3 L3 V9 `: _/ [+ w+ p参考资料
1 F9 w/ Z0 f0 }' O- q
5 ?! m0 ~1 t$ f7 ^! `3 N内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
1. 插入排序
2 P' Y# Z. \& N: {. m7 U" D0 f( q7 B1.1 直接插入排序
8 F! c0 o8 V/ h- r. g; H' ?0 p3 L9 d图解

. Z. o7 q9 B$ J6 q/ n9 B% p
) o' Q8 E0 J/ t  O+ A9 U5 p% R/ p# S基本思想
1 M5 ?/ |  m8 i
1. 查找a元素在第1 ~ i-1中的位置k
. w0 F5 O  z: B. |4 A2. 将k ~ i-1位置上的所有元素向后移动一个位置
6 E5 y3 N& C: A  o0 C, p' S3. 将a复制到a[k]
+ z/ z. o6 O# Y& x. b% F
1 N" ~5 t0 z3 @# c4 k, J1 F
( w( A8 @- E: v5 J* ~% Z. b
1 {2 h7 ^0 c. H3 t代码
# I4 k" l& y7 E- S
方法一：
! G$ u5 A; b" J6 m+ H
数组的下标从0开始，如上图。
; D6 J, Y7 g4 m5 E
; Y3 t8 K2 v1 F! W% h#include "stdio.h"

typedef int ElemType;

void Insert(ElemType a[],int n){
4 F, I0 l4 T/ ^8 X: s    ElemType temp;
    int j;
    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
( p6 f0 Q8 [! @1 g$ O        if (a<a[i-1]){
            temp=a;                                                               
+ Q( B9 {& t; F% d9 n/ t( @# ?  c            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
                a[j+1]=a[j];
2 }: l' e3 R+ k6 V5 Q5 h            a[j+1]=temp;                                                       
- u  F- P+ |( X1 t        }
    }
: v: F& y! P9 R( x: @8 ~& B, j}
! |. p; q2 T- x8 R/ w& R
int main(){
- ~) K) ]- I" F( [0 c1 @# n    int n;
, R9 L3 V: D" x- S2 Q2 K' {    ElemType a[n];
    printf("一共有多少个数需要排序：");
" M! d1 f+ ]1 Y* N# o0 \    scanf("%d",&n);
    printf("请输入%d个数：",n);
3 |3 Q& h& V1 }) m3 {- F    for (int i = 0; i < n; ++i) {
, S& H2 A# C- I        scanf("%d",&a);
    }
" k9 P" T) b* h; m% {* R    Insert(a,n);
    printf("排序后为：");
9 b  c% g$ I; H6 x4 i# H& L    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
}
$ M6 q6 t1 h7 F  a0 H- t! v
1
2
3
4
- N, r! \0 O) a, K2 D; m5
6
7
, u- V7 F% B6 N0 M' ]8
- ^+ j4 G/ E$ t4 z3 P9 D  @" T9
10
$ Q3 f' y' B& M1 H" \, r11
12
13
14
- b/ k! ], a2 K1 B0 o  E+ u15
; k9 j7 [; y  _2 t16
3 |1 ]9 w/ @7 A+ z' R! r4 h17
7 Y3 w; N: S! a$ f; a* N8 d) i18
' O3 Q. H# `/ R% h0 V19
$ Q+ B) l  a! a: [7 l+ e1 ]! k20
21
22
23
3 H- A6 Q5 |. e' ~  Q* c24
25
26
: y" A5 `* N! |  ], T27
$ L; V" J2 [, u0 l28
29
30
31
32
方法二：
: U4 J; _$ t+ L4 R1 R8 [4 A


5 L& H0 q# U) Q#include "stdio.h"
+ R: Y( O5 J% I! s+ K
3 G' D0 N- `! N( jtypedef int ElemType;
; V8 Q, ]3 h, V2 `
: p  M1 Z! q0 I( L: b0 Q. B7 jvoid InsertSort(ElemType a[],int n){      
5 o2 A8 t; K% M, W    int i,j;
" b8 J' v4 l% l5 L8 U    for (i = 2; i <=n; i++) {
  F: m9 n4 K) m" b9 ~7 o- V9 @        if (a<a[i-1]){
            a[0]=a;
4 \0 w8 z6 _& w) V: F) ]            for (j = i-1; a[0]<a[j]; --j)
                a[j+1]=a[j];
            a[j+1]=a[0];
2 i& R, _$ u+ @1 ?  c        }
9 g) i+ G2 Z' m, K1 ?1 I1 Z    }
% r4 P9 e$ n3 E1 _}
int main(){
% i2 x- k) E( N0 \$ ?    int n;
    ElemType a[n];
$ X! m# J- R! j$ D    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
    InsertSort(a,n);
' b; B( f2 S( }, x& {2 E    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
0 W' {3 G5 o/ e4 G4 S" i/ @- W! e$ M" Y        printf("%d\t",a);
, V  I+ h( P7 z1 e    }
6 X( \1 s$ L! h( G. X) Q) r' `2 K}
) R. I( ]( g# N! L8 |5 T1 [  b
/ E+ `. \. c; j8 t6 r" y5 _4 G1
  ?0 S% f; g$ O1 W2
3
0 w( L+ r% m# f. ]0 r1 D! ?5 m9 X4
5
3 ^1 f1 T. J( m8 v& u% [6
* c1 i1 J9 A5 Z7
( F; j0 p# `3 J' u* U3 I: G8
- T5 |$ Q4 X2 V! e9
' F; g4 h+ |+ Q+ u+ ~4 m  ?2 P4 \0 c10
, s6 m. [  P7 c: w$ j11
12
13
14
15
16
' H5 |5 x4 }" m9 D/ k8 d8 ~17
5 O! y  H' a( M) L8 d18
19
20
' r% P4 L- M9 e21
$ d7 `! L2 Z0 }( `8 G22
# [! y* ^1 Z1 {9 Z/ h7 N7 J- `23
) V8 b3 i1 t4 ~3 U, K24
25
26
27
28
29
30
! V  K" f" k9 T% J/ n6 {: O算法性能
0 U3 E# T2 B! j
/ k) h, S7 E6 M, i1 X空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)

时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
% ]' g  Q# d2 C& K0 c2
. N( I- [6 k: \( h# Y  B )
0 ?$ ^4 m- _  K8 ?4 ?4 M( G" \
2 q1 Y0 n! I7 [& ]! ^) Y! O4 s
7 u  B6 a: d0 G) d" b2 U稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
- u2 `# q, J* Z  C
3 `0 v' Y  C1 Q+ h适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。
) B/ Q" V) a7 Z
1.2 折半插入排序
$ P" |9 G# B5 m, u0 h% E图解
第一趟：
  I, K$ H: c8 X* [( Q+ @6 Y+ ~
第二趟：

  @$ _. P: u; I% W; W% r
第三趟：
# N1 |% ?: D8 Y: g! j9 z' ~  A
第四趟：略
第五趟：略
; A5 J3 Q: e* o2 i* p# A
1 Q; B" p5 G/ ]8 i+ f基本思想

与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
9 b; t# j( N' G8 s取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
$ |& _/ s' ]# T' K! v找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
& s5 g7 o* G. W) G; A6 Q3 `) \代码
4 \7 H/ R: h1 A" W: v/ b) A) `+ Y
#include "stdio.h"

$ Q# E# a5 ~; @4 I3 o5 y% Mtypedef int ElemType;
2 J& p3 J8 q5 l4 O+ H
& R# P5 ]( d! r9 R# R; uvoid InsertSort(ElemType a[],int n){
    int low,hight,mid;
) ~1 }  o! N' D+ E" F7 h5 u$ m    for (int i = 2; i <= n; ++i) {
        a[0]=a;
        low=1;hight=i-1;
        while (low<=hight){
5 A+ c  e5 V$ a" u% v: n            mid=(low+hight)/2;
            if (a[mid]>a[0])hight=mid-1;
            else low=mid+1;
4 S% S% u2 I, _        }
        for (int j = i-1; j >= hight+1 ; --j)
; E* p$ J7 Z( r9 f" k9 r3 K            a[j+1]=a[j];
        a[hight+1]=a[0];
    }
0 B0 Q& V% ?0 h- ?) y* L}

6 z) f9 @) g, R- h% [
+ q% w6 @  h& S: T: Z4 v9 Oint main(){
! ]# a$ f& S% N/ T& M% F9 T    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
; }! I8 U4 B1 C/ H# e9 u    scanf("%d",&n);
7 O8 ?2 W8 y2 H6 j0 j7 Y    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
' `. F9 @( L/ Q# G        scanf("%d",&a);
$ A  V  J1 k/ g+ [! V8 N    }
    printf("排序后为：");
# t: s+ |' J8 f6 Q+ h2 G8 J, m" k    InsertSort(a,n);
  S- u/ X! V% U  i1 J
" F8 o* c1 }0 k7 r    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
7 @1 h% o2 |/ A. y0 x3 Z1 w}

2 d( D' f3 p4 n& D9 x1
2
- I8 ]! P3 z: s' c) W3
% d8 ?0 S1 F( s3 f  u+ B4
5
8 p; U/ B8 `6 v, q2 a$ `6
7
8
! \: t; }! I# P& O0 Y9
6 s8 l0 ~- F' s- M10
11
12
13
: D" a; e% W) C4 `2 B1 b- n" U14
15
4 b8 v! Y$ T) J  e5 L16
17
18
19
20
/ r8 O/ k. \. w6 h  Z$ ^% T21
, z7 U5 r( S* z8 I2 ^7 N22
23
24
; x0 [6 G& ]! |( U3 y25
1 R, h9 A1 M+ Y26
27
# w- ]% r" X7 l. ?8 T28
29
30
! x1 d8 `1 i7 o2 V# g" }31
2 p8 A* C- b' H& G32
33
34
35
36
37
性能
4 \" ^  U3 r( M+ ]
空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
. y5 g5 K, T# a% ]! J9 H$ Q8 L* j2
)
* l# C( \. b  K& f稳定性：稳定
9 S; J0 u% P; H- y( V适用性：仅适用于顺序表

1.3 希尔排序
图解(动图)

! E& C. d1 v- o# i7 Q1 g- e
, S8 e+ D2 r: E5 D  @) O( Q基本思想

% r# k, K# ?/ i5 w先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
; V* `5 @+ F' A9 ?- G0 Y
代码

#include "stdio.h"

typedef int ElemType;

void ShellSort(ElemType a[],int n){
    int j;
    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
' h- h% B: ~2 Z9 X( e' ?* m% y        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
            if (a<a[i-dk]){
                a[0]=a;
, P9 G. ]1 s! u) Q( |9 w                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
                    a[j+dk]=a[j];
  Y6 n' d& r; Q& E( f9 k6 x                a[j+dk]=a[0];
, a/ G2 v: h+ i            }
$ w5 F. E) m, m. I  F; u        }
    }
$ A" H+ q. }- R' Y}

int main(){
8 {/ e' D: H( e( R, ^, {; E9 n    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
& I  n8 g' s# Z" E& t3 |; e2 y    printf("请输入%d个数：",n);
' L' k  Z9 j% |' Q/ F" L# V    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
9 J. \3 w6 b. {" l; b. O5 @    }
    printf("排序后为：");
    ShellSort(a,n);
; I" N; Y* d5 r2 V
: h/ ]; J1 w( E* t- E+ J! ^    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
}

1
2
9 E# H7 Z, ^9 `$ Z1 y& b  G  V! o3
( M( q  Q+ A: A* N' A, Q) c$ Y4
3 T8 w7 S) n( ^" }5
) x  W5 D# x" ]7 _6
7 ~$ e( n4 x, {3 v' a7
9 e5 W2 m2 ~3 }; J8
0 S$ x1 w& d- A2 ~) S; c& y9
10
11
$ W4 e7 {* f2 q7 J3 `12
13
14
15
9 Z" N- a7 n3 Q8 |, g# m# x9 V16
17
18
: b6 e' \2 s* V5 [19
- N" `" K0 q- Y7 h( T% h+ q20
& {+ f" u2 L. h4 u' n21
22
23
24
- D8 Q3 K2 H8 }% W25
0 @! M" D) d4 K3 y26
27
28
* a' D; h' C8 q/ O$ w29
30
31
# O' z" }$ E4 F32
33
34
性能

空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
. k3 d6 n% I& e* S5 }
时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
8 f. h4 D4 f+ x1.3
)，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
7 v; j3 I3 z4 }: \7 {" y$ Q2
)

/ p/ B  _1 h6 I+ @2 V! @  ~4 F. M稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
2 x. F. F2 U& n2 v' O
4 e/ f7 h: A- m3 W: W' W1 x
适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。

2. 交换排序
2.1 冒泡排序
图解
9 z" n8 X0 T2 [! C0 j

基本思想
( t6 i7 V* X0 V0 v4 o" P5 }8 \+ d/ P+ f" u
从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。

代码

" s/ f! Y8 }5 B& J0 k/ G5 @# E方法一：将最大元素交换到待排序列的最后一个位置

7 D, X6 d1 O3 [2 V* f; b# g* k#include "stdio.h"

2 p& z4 n% {: B0 u' Itypedef int ElemType;
) I3 T  [$ \9 d) P0 n( c7 w
void BubbleSort(ElemType a[],int n){
    bool flag;
! i) Q1 [+ q, Q1 l* H    for (int i = 0; i < n-1; ++i) {
5 Z: m; c. v3 z& P  k) a8 i/ G        flag= false;
& e( S5 s6 i& H        for (int j = 0; j < n-i-1; ++j) {
            if (a[j]>a[j+1]){
* |1 k: R. A" {& M, L# A                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
' q: C8 E: k8 a# m3 |2 x                flag=true;
/ Q4 o+ D7 n) _6 n: Q8 ~            }
        }
        if (!flag)
            return;
" Y. o- \) ]4 _3 P/ B3 l    }
}


3 w+ u' i& W" ?int main(){
" z# P7 j( b0 a    int n;
    ElemType a[n];
! z. R. L1 M' Y    printf("一共有多少个数需要排序：");
  g4 f  i8 w: O6 V$ Y. Y    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
6 y1 M- w4 P! t' [  R* ]& n8 Q8 \        scanf("%d",&a);
( w; Q" i$ X! L- E    }
& l# l3 _! z$ B/ A8 K, c- W    printf("排序后为：");
    BubbleSort(a,n);
$ ^4 m, X' _; [4 x6 L% F    for (int i = 0; i < n; ++i) {
- b9 @9 [( I, t3 e+ Q& D, R6 k7 o8 S        printf("%d\t",a);
) k1 |9 E& Q4 N9 {5 J$ d" E    }
}

3 I6 g' h: i; Q$ X1
- E: M+ e2 A5 T2
3
9 @4 H) s1 S9 ^$ Q( J) N5 _4
2 Y, p. b4 F$ v5
6
  O3 ~, l; [. a. V- R4 r; S5 R/ x* x) b7
9 `; h& P' t2 ?& ?8
9
1 h' ]( E, _, t9 m. |2 t; M10
8 w/ Y" {3 P' E+ D11
) S# Y' q% a* k6 h4 ^1 }+ R# [8 m12
! n2 Y$ i/ ?5 R* Q6 Y- U+ g) Y13
6 S# C2 U/ {( M14
15
16
$ x! G/ s  w( j17
0 p7 i: F9 v, a5 Y8 i; x18
19
20
21
22
23
+ I/ R2 z' ]  B0 \) T8 E' M24
25
3 Q( c- R- Z4 g2 n; {" O8 M26
27
1 r" r% J: v5 @( E- [/ ]28
) ]( @" `5 H% y% V7 A' Y29
30
31
32
33
  ~% k! }- e, j/ G+ _34
35
36
8 g+ c" m( G6 i$ ^4 d" R, l+ V9 c9 z37
运行截图：
- p: f! [# ?5 b7 J4 D2 R

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

4 W- ?( [& }& V9 M2 ~% f#include "stdio.h"
/ y. w8 t6 B$ ?- j+ R! s4 S2 l) C
3 F3 j0 O+ o- R/ {typedef int ElemType;
2 }: E5 I2 E4 I( W
void BubbleSort(ElemType a[],int n){
    bool flag;
% O, T* X8 N% E1 {7 X( E- q* w    for (int i = 0; i < n-1; ++i) {
' l; B4 z% O, @: @7 c& h- _5 M        flag= false;
        for (int j = n-1; j >i; --j) {
            if (a[j-1]>a[j]){
2 [, r6 ]/ s6 i& R/ j% N                int temp=a[j];
: Q# N9 Z; x% {0 e                a[j]=a[j-1];
3 x0 V8 m  @- o- N6 f                a[j-1]=temp;
                flag=true;
            }
        }
4 ?3 f( l* A$ m        if (!flag)
3 ?' W7 V2 P) M( [            return;
    }
}
5 W+ l/ w% Z9 f& W' g
5 p4 I! z7 l$ J8 |
4 _! G) P3 K- ~4 k. N2 Vint main(){
- R6 B7 R3 q9 V9 i# k0 L- K    int n;
    ElemType a[n];
1 B+ P6 {. y* t0 A! z    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
# n7 J. s- l5 A5 T        scanf("%d",&a);
$ I1 a3 H2 W$ d/ U+ [+ G) d    }
. B$ e$ e/ s6 Y8 J. v! P$ H& n    printf("排序后为：");
# U( n; K2 |* `7 b0 E8 X2 r    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
- p9 T3 t: I3 `3 Z  }6 D: c6 J}
) D% l1 T" `: B# o! j, n, s- r4 t
! F) A( ~- r& @* m5 s. `1
2
3
5 Z! f( g/ b1 n" Y& _4
( j2 T3 u* V' o$ ]% i2 P5
6
" L# A, h' F" M+ R7
7 ]4 A' d" R' b! O8
5 p6 J- j  G7 d1 ?5 C9
10
& R7 N! i2 J! c5 g/ o11
! W, L6 x7 G+ J( s& q' k0 J12
13
" ]# z. o; z4 B4 i0 d14
; @% g$ @9 n2 x( W8 D/ R15
16
7 _7 v# U0 o3 ?+ l( M; p  X17
# V+ U5 I+ q) S8 [  c( `18
4 e" l& V. O/ u, B19
% \4 Q# j. t& d! _" {20
21
22
, Z( H& n* l! s8 Q8 n23
# J7 j" A( |. v' ]4 j( v24
25
26
27
! G7 D& L( ]& K0 L28
29
- ]) h; J% u* k* z30
( Y9 j$ ?; O- b1 c) K  R3 b; B3 c31
9 Z# J7 q* H- T( {& T- ]32
33
34
& ]( M1 D; N! `% R* j35
36
37
运行截图：
+ o( S$ P& q6 p  w6 Z
) q! y* d  h& O& k% o
' H4 ]! s# k! c2 j' V' D性能

空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

( p5 v; h  x5 c7 N+ N时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
, x0 l' V% Y; n# R- f" B  B8 J1 g2
)；平均时间复杂度：O ( n 2 ) O(n^2)O(n
- `0 D, G8 M4 |0 k2
0 u( `2 }! F5 b  u" |$ C1 R8 ? )；

稳定性： 稳定
. h- c) B1 A8 S4 t
! c3 ?. X* {% B; |0 }; x7 f适用性: 适用于线性表为顺序存储和链式存储。

2.2 快速排序
图解（动图以后再补）
第一趟的排序：
4 d) D1 s0 ]2 L# S. ^: s- S
第二趟：
% w2 s6 C# @8 T
第三趟：


基本思想

快速排序的基本思想是基于分治法的:
1 x. q& ?' }9 I5 l8 m- [3 @
在数组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步骤排序。直至所有元素排序完成。
代码

#include "stdio.h"

' z) K# R& l; x3 N  U, m6 z) ftypedef int ElemType;
4 ]: n) U( U9 J9 d& s  ^
! \* Z' Y  j5 a) e2 Bint Partition(ElemType a[],int low,int high){
5 L) O* ^9 `( s+ q0 e- {    ElemType pivot=a[low];
    while(low<high){
        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
( Q# a: H* w& X        while (low<high&&a[low]<=pivot) ++low;
+ n; A9 K* z3 e0 X        a[high]=a[low];
  X- Z7 O( n' e9 b    }
    a[low]=pivot;
1 I* T" u. x9 n; ^- Q    return low;
}

void QuickSort(ElemType a[],int low,int high){
5 n7 i6 S; w: B5 r* X    bool flag;
    if (low<high){
; w5 L8 F* ?2 j9 q. T( ^/ b        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
$ |9 O/ ?6 w1 O1 ~$ E        QuickSort(a,pivotpos+1,high);
    }
}

: U6 {1 m* F7 yint main(){
# b3 i1 u8 x6 C8 C$ @    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
/ R. H0 ^1 F- _/ Z9 ?5 [    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
6 i; L3 J; C9 i8 M  L1 c3 w! Z    printf("排序后为：");
    QuickSort(a,0,n-1);
5 F3 X* U5 M* z4 J' R    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
}


1
2
; B3 X! y8 Y/ B! ~% X+ f: z; }3
4 z0 ?% B5 @; t% G8 Y4
+ m( y* Z& R: F3 C" c. S: b! Q5
6
7
6 k! |* q; ?, M* G8
9
3 Z% \  W" [, x/ d10
11
12
13
' `; F6 [$ W, Z14
# h& u9 |6 T5 U; A$ a5 \2 t15
' ]- X, ^' u$ o: N) z5 H- H16
3 V' B* B% t0 F- g0 W6 I17
18
: \" j+ A( N/ L3 y0 Y19
20
21
22
! F; x" i: y) x" |23
24
: M8 P8 L4 \$ x0 f0 I+ w4 R25
26
27
28
29
30
31
7 G$ t6 M& C9 ~7 j, N6 {32
33
% k. H, z& V, L5 Y) }& A34
3 L6 f/ u: ?1 o& ^35
) Z9 U1 q5 P) i4 D% t% x2 @36
37
9 G* ]! R9 z+ w# j5 A+ ?. Q38
5 E' R; r3 X4 S* ~39
0 G. Y8 H4 Q  V& g+ u: c40
41
性能

时间复杂度和空间复杂度
稳定性：不稳定

) n7 j9 n+ ?' `3. 选择排序
3 {8 e, h6 M* U+ f3.1 简单选择排序
图解
% S8 X- g* _/ G! X. r* B9 o5 B
8 Q( O2 T% M2 s& e# f5 j
, x7 }! S) |: r4 H; j基本思想

- M% n9 R% x, P8 ~% N8 k6 X# _在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]进行交换，第一趟排序完成。
在a[1…n-1]中继续进行排序。
$ o0 p8 g7 G+ f8 D) S7 e$ E- K代码
* o7 m& S8 s: U' f0 Q
* A# I' M9 r! Y/ n6 Z; x2 _8 M+ z#include "stdio.h"

+ h6 L% O" h4 P8 [9 U% ^; Ztypedef int ElemType;

void SelectSort(ElemType a[],int n){
2 E) D: O( m* o( U( E    for (int i = 0; i < n-1; ++i) {
! u1 h9 ]0 ~' S8 q        int min=i;
        for (int j = i+1; j < n; ++j)
            if (a[j]<a[min])
, f( n: _8 N. J$ @                min=j;
  b" V+ G7 _& R! p        if (min!=i){
$ U# P( `" ]+ }            int temp=a[min];
. c" a! _* h& R8 s- G+ O            a[min]=a;
0 G( I9 z5 W. C0 ]2 F            a=temp;
- d" |0 f; [- i. q3 {        }
& L: T* [! ~2 E    }
}
9 |( G: Q4 ]! a6 {- i% E7 e
int main(){
3 J  X3 a/ A* V5 d) t: E    int n;
/ _! r3 ^. N8 K    ElemType a[n];
# w$ \" `) I) O0 o/ j9 P    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
! J6 V6 M/ a3 [  k. ?0 }    for (int i = 0; i < n; ++i) {
2 Q+ a" V! r, H, b. }6 `, _        scanf("%d",&a);
$ V; T) B9 Z& l/ b0 O+ p' V    }
" z; w. J1 f! q# K: ?" S/ z    SelectSort(a,n);
  i1 b4 o8 A2 i3 G* }    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
  j/ J4 ?; U) q6 Z        printf("%d  ",a);
    }
}

1
5 }- P' I8 D7 Z2
3
4
4 K+ l5 D) `0 x* X' e- n5
' E6 L+ H2 z/ F6
7
( {1 d4 p7 S, i# p* G8
9
10
11
12
1 r1 l, u# A  @: I, S) M3 b6 P, s13
2 I4 a+ R. ]' H  T1 T( s14
15
( Q) B% m  v$ x. Z  I16
17
$ i. ^% G4 j/ U# V1 j7 o2 p2 i18
4 _+ g5 @4 d. T5 u19
20
21
8 ~. K5 g, F7 V5 r3 k/ ~' V22
$ o- U+ v! `& O4 l; |6 E23
7 @7 i3 \* b1 q' y- T! x6 F24
25
26
$ @4 |4 _5 L. Y" E% t! `27
7 j$ g4 ]0 u" S9 Z. U# O28
4 r5 t! ~6 F/ S29
- i# Q# }, O' \5 t+ v- d30
  |% j  i5 I* ?& U! [$ P31
$ O: C6 m" f' _5 E7 X32
33
" r% ~$ v+ S5 t: R% q! h" r性能
" q; D6 d* W9 Z5 @8 h. T
; L' G  A1 Q" A! t. l* @空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
2
- n% X8 ~; G  j; h! A9 J: t )
( \- Y9 ]+ o! q2 O0 _) @4 a! Y) z稳定性： 不稳定
, @# d( G/ ~9 B: ~! B7 z7 E
使用性：顺序表和链表都适用。
$ d; u' O6 Q* C7 _
3.2 堆排序
% h6 m* ?8 V; W. a看堆排序的点击这里！！！！

4. 归并排序和基数排序
4.1 归并排序
  F* i4 ?8 g) t1 r. l5 i8 Y图解
- B) {  Y, H' E- I7 c2路归并排序
0 m7 y# A' B% O# Z4 U, Y8 K

基本思想

将待排序列分成长度为1的子表，然后两两归并，形成有序子表

7 \* N( O4 J: z5 u然后将子表再次进行归并，直到子表的长度=待排序表的长度。
$ v* w! F: ]% |3 ?9 a9 n5 p代码
7 S  ^& k, }( r# n' R6 i; ?
# Y0 K# h3 d* ^. P8 _. U#include "stdio.h"
# ]. h8 {! \/ E. s) y, K9 C#include "stdlib.h"
1 S- P* d" }6 T0 A7 q
9 O! [6 O$ a; A) J; o: K2 Ptypedef int ElemType;

* L# Q. S/ ]4 ]" \+ P8 l3 w$ @' cElemType *b;

void Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
; p) b' [1 R5 Q  H3 ]8 R* n& E    for (int k = low; k <= high; ++k) {
        b[k]=a[k];
    }
3 T- o6 X  j/ n' i    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
+ c; D! A1 h7 f( j2 D5 o6 D        if (b<=b[j])  a[k]=b[i++];
- {1 l2 w, b* C+ E4 p        else a[k]=b[j++];
+ h' A$ p" u6 d1 a& K. J  {    }
    while (i<=mid) a[k++]=b[i++];
    while (j<=high) a[k++]=b[j++];
" w8 G/ E. j; w; [0 B( t0 i}
- @7 j5 M, M; z5 w" Y% \3 a1 E
void MergeSort(ElemType a[],int low,int high){
( [9 c2 F( h- R( f* w    if(low<high){
        int mid=(low+high)/2;
8 F1 K2 u  N: t; A        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
7 k, ~$ g# y: Q4 J}

int main(){
& H" p  I! o) e$ [9 h    int n;
0 c$ V$ e, [: U- r8 s7 ^5 U% k4 c    ElemType a[n];
8 O, J3 x$ j& v8 Y! ~    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
1 U7 h1 V5 Q& i6 _; [9 u/ C    printf("一共有多少个数需要排序：");
4 ?  I1 v2 `: o5 h( c1 B/ s    scanf("%d",&n);
8 O; j: A! `9 `7 T9 i4 y    printf("请输入%d个数：",n);
, @0 r/ y6 M3 v# N- @    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
5 K# K$ \' S- t2 @3 c5 K* P    }
: E4 @0 B3 n' {7 l% e. C; F    MergeSort(a,0,n-1);
    printf("排序后为：");
( C3 v6 a" w/ c. G    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
: T* z; ?6 q0 c/ W6 T. C; H}

- l1 P/ @' z: ~
' k/ S- E: a: `& ^  h+ G# C1
2
: a1 x; u4 |- M6 U& l3
( k9 r" u) Y9 k4
3 I: U5 u' \2 D5
- [3 p: y+ q# d0 W* a6
7
9 `% v0 |' G  X0 R. }; s3 T9 ~8
9
10
" B" f) G% k5 |8 g8 Q5 [11
12
1 I! V2 K; p8 b1 ]) W13
14
15
4 \9 p4 j# ?% e16
17
18
3 F, b( L# Y) T19
% k6 j- }: B% X1 j, `20
. B& N& t: c( F% y9 y21
; h' q, {1 P4 \: {' X6 h7 [22
23
24
! W% J$ Q6 ~' a7 _% r25
! s8 W. o# O6 q26
4 b8 x4 ]. G7 H+ R6 Z27
' E, g3 k  b- }" `28
5 h; t# X8 c" t$ N8 t5 w29
30
$ U  \4 z8 Z* \9 U31
32
33
34
35
36
37
' m2 N: a8 {9 _* f- Z) h38
39
40
5 O- B4 z, @0 ]8 R8 a$ h41
42
43
, q. N# Y6 D4 k! c! ?. F44
45
5 `0 ]* \/ `1 T46
# n- C! y& Y6 Z2 A. `8 B, D. g性能
8 N! F2 c! B( u( c6 r
空间效率：O ( n ) O(n)O(n)      创建了一个数组b
4 L& G9 w% K7 o3 b7 o- B; q时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
+ _+ y% g  O' J# Uk
​
n)  k指k路归并排序。
稳定性：稳定

1 [: G, G& Q% o5 H6 q2 A: ]4.2 基数排序
图解


基本思想
( V$ r) b: w! O# W3 s' x7 D
将各个位数（个位、十位、百位…）进行对比。
: g1 b0 J7 E" A, Q7 Z% ]. j4 `2 J为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。

性能

+ v* o7 M6 p0 m1 Z5 x7 C  H8 v  m空间复杂度

时间复杂度
- e7 Y: e2 u. O* a+ {1 n
3 h& E* w0 D2 Y3 n0 l7 h
9 e/ a/ f5 p% N1 {) c稳定性：稳定

  M# `- [# X  S3 L$ q3 |, s8 C5. 内部排序算法比较及应用
5.1 整体比较

; _. L* U: f$ h
5 S& F7 n, _! c0 E% N# t1 B  h1 [+ ~5.2 时间、空间和稳定性
* g, o8 c0 P: Z( h0 O
+ S# `+ ~' V# S9 Z$ k- o
. e( C1 A( o7 I. F参考资料
% F9 G7 I9 U* t, P2 t. {9 I0 ^8 s《王道：23数据结构考研复习资料》
8 ~- l9 A" Y+ y( J, D————————————————
版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678
# Z% k  Z+ y  E) p2 B- u, A, {
7 k5 U8 n, z. M5 C