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

杨利霞

数据结构：九种内部排序（动图+完整代码）
- ]3 g9 r' p6 s
! ?0 J4 s2 f! A6 h排序
1. 插入排序
1.1 直接插入排序
1.2 折半插入排序
1.3 希尔排序
3 `# q* N) y  y7 V; T% n2. 交换排序
2.1 冒泡排序
2.2 快速排序
3. 选择排序
3.1 简单选择排序
3.2 堆排序
' v3 Z+ ^: u' n$ w, v: T4. 归并排序和基数排序
! Q* b6 i, p% f, `5 J4.1 归并排序
4.2 基数排序
3 ~: m8 }/ G" a/ Q1 r% V5. 内部排序算法比较及应用
5.1 整体比较
( C  `6 H, z: A2 p2 a$ `5 H( _+ p5.2 时间、空间和稳定性
参考资料
" H$ ^; }& O. z$ j
内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
) t- x' d* H, t! Q' H1 h9 n& P1. 插入排序
( @- E6 G: T+ K3 ~$ ]+ ~1.1 直接插入排序
! H: _: p- }1 i& k8 b  V+ l图解
/ L3 }# d* }* v  ?: ^: W

基本思想

1. 查找a元素在第1 ~ i-1中的位置k
2. 将k ~ i-1位置上的所有元素向后移动一个位置
! k1 l) j& C3 p3. 将a复制到a[k]
. F' r: ?9 H' V% [8 O

+ J- ~. J3 `( L# _5 q% V& o
代码

方法一：

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

#include "stdio.h"

! i9 r* k# E4 P, O/ p& btypedef int ElemType;

" O8 t& l' M. T, S+ Yvoid Insert(ElemType a[],int n){
6 W. J) \% d* l    ElemType temp;
    int j;
; i7 }2 C7 k' m+ g; ~! y    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
        if (a<a[i-1]){
            temp=a;                                                               
            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
                a[j+1]=a[j];
1 w( z8 |: I- d3 T0 A" M% }. F            a[j+1]=temp;                                                       
        }
    }
}
9 g9 [# I2 m( G' y
int main(){
8 f2 R; e5 |+ X. u7 n) h    int n;
9 z8 I& k. W! d8 E5 h- d    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    Insert(a,n);
    printf("排序后为：");
; Q7 B$ e1 h% N    for (int i = 0; i < n; ++i) {
7 t" R$ ?9 n, a4 o. M# B" G) H        printf("%d\t",a);
    }
, d# s- A  |: z}

, x6 N! `: a: ]5 }$ o( I$ o1
2
3
* g; C/ i1 z* g2 a1 }2 p4
5
8 {; y3 Q3 M3 X* \6 ?" T6
) i% a# Z4 ]8 T, F% |9 K0 n7
$ `% c' k2 @' W; k0 a* {8
9
) p! r- T- H: k" l10
8 z7 |1 Q7 a- s2 j11
12
+ ^; I& H0 W5 ^( e6 t1 e13
4 }% G8 k" S. W, v14
' K( G) G- V+ w8 ?; E! l) p; [15
16
  U8 D" h' O+ R$ }2 q7 g/ d9 n) O17
- R- \8 M! V+ y- d7 H; q5 n18
9 i4 \9 J  }7 }: y( W, e3 I- Z9 @19
5 P) n" `* z) U20
/ R" F2 h: y# P# n) I0 c21
22
( _1 E. J3 I7 J- e; Y+ f# z1 W" q23
24
25
26
27
% {( X& \) r3 B7 w- N( ^28
29
; u$ ?; B2 t% R6 {30
31
. i! y  r2 i5 j& M+ k32
方法二：


+ F5 ]" R: |* g& ^
#include "stdio.h"
6 W2 p1 b% x+ _% {) @4 K* d
# P' I( C4 F1 u7 Mtypedef int ElemType;

  B! ^1 n) b; D" n" \: F7 x# kvoid InsertSort(ElemType a[],int n){      
    int i,j;
    for (i = 2; i <=n; i++) {
        if (a<a[i-1]){
. ^: J, K% J; E% t0 L) @0 X$ u            a[0]=a;
            for (j = i-1; a[0]<a[j]; --j)
- f* c% j5 y$ G, H& v                a[j+1]=a[j];
1 x7 y% }# |9 ?: N! F: ?3 U            a[j+1]=a[0];
        }
! J8 C- U! U8 T% X5 L: m    }
% K4 v* \# d9 c: l}
/ K. v( H" x6 U( H3 [int main(){
, I% Z8 F) h( y    int n;
" N; m) e! J7 L" Y6 z    ElemType a[n];
) e1 m  L7 i9 I) {+ T7 u    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
5 |1 A, R) o: K) i: B9 E    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
+ ~+ ^. ]" l) f5 `6 Y' a4 G, Q6 h        scanf("%d",&a);
    }
    InsertSort(a,n);
    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
) c" w8 I8 p/ ^; R, [1 Q1 q6 g( z        printf("%d\t",a);
" Y! X# p, z! K; d6 H# t* U    }
}
! B$ R; H6 ?3 X* P$ y! J( y2 S! Z. U
1
2
8 k+ L, R( f0 m1 J1 `3
4
5
: d  f! o1 j& R; b! F6
7
8
9
  O* q8 _9 L2 B4 i10
- `' Z* k0 M) K" V+ m& A0 J( I11
12
/ b! \' a8 I% K' x13
14
15
" g. d2 g9 w# h5 `3 O16
' Q+ ?$ ]% V. p. f  I17
$ w8 q$ c- u! W) d+ L& T8 x18
19
- r$ X8 t% K% r% c8 P! b+ U$ f20
21
22
23
6 m* ^7 v& L3 N' V/ b24
25
0 `1 V& b$ e+ I26
27
28
+ B* @) j' \+ F29
30
算法性能

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

时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
/ F  L* g9 |( [" q( P" f )

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

% R& q% L1 G$ e' [. m- n适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

% s- T' l2 t" N- s2 g( ]1.2 折半插入排序
图解
第一趟：
/ `5 j  d8 J3 a5 B: N' ?
+ P# H% B8 ~8 L4 h) y. L$ m第二趟：
+ i; A9 U6 S7 Y2 Y. h+ w( V

0 @: r4 |' x8 K4 d4 v第三趟：

第四趟：略
3 I& {# P! t5 g, E9 l第五趟：略

基本思想

与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
6 m+ O0 ^5 i5 P1 a4 m/ P3 Y取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
8 _; j, z1 {6 T9 j9 P# }( i9 f找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
代码
, M1 \6 R, x% R3 f
#include "stdio.h"
2 a6 [$ u7 |2 e- w2 Z3 }- v2 y
typedef int ElemType;

( ?/ N/ m, {' p. b) V  Dvoid InsertSort(ElemType a[],int n){
    int low,hight,mid;
    for (int i = 2; i <= n; ++i) {
        a[0]=a;
        low=1;hight=i-1;
. G+ e( S9 q# h$ N9 z1 u) _" ^        while (low<=hight){
* H" d9 d; L7 u            mid=(low+hight)/2;
6 k/ o$ @8 Q$ y* e0 x4 f            if (a[mid]>a[0])hight=mid-1;
. T0 X. e( Z( C; _" o            else low=mid+1;
6 |6 y6 _1 \: m0 w/ I8 t9 }        }
0 E0 D8 R8 j: R' Q0 W        for (int j = i-1; j >= hight+1 ; --j)
! L2 N! j( \# e% W2 \            a[j+1]=a[j];
        a[hight+1]=a[0];
) [' B4 d8 e- i+ Y$ d; D% Z6 P    }
; L0 @, g1 h/ T# {}
9 T2 Y& m2 P: H
  R. R$ M& K$ t: a1 u( h& O
int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
' a1 _0 X- V) u' N8 D    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
( Y3 K% ?. _" c9 ~3 D6 U: ^    InsertSort(a,n);
3 e9 b/ G1 o# u, n+ H$ M% i
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
0 v; q4 y/ ]2 Q4 Y    }
* T! e, r! d4 [  f3 P+ t( `}

8 K6 i+ b' l7 t0 N# @2 P1
2
  y) Z4 T  c  b. a: P6 I, r3
4
: h0 ]1 C: T' v9 u5
6
5 Z% R/ e  E, _7 Y7
( E# F3 {- |3 K0 r' {8
9
10
/ a: w( N( A8 `) m11
12
13
14
, p/ V! n  o! C2 i6 l5 @15
16
17
3 y  {, r! j" L0 Y18
19
20
2 n3 D& g9 c( o& {+ C  {7 B1 f21
22
/ e  K* x+ b8 _% v. [. p3 ]* o- M2 m23
& ~9 h; m9 M# O24
" G0 c, J3 P4 h# N6 l25
26
27
28
- a. d& ^8 q/ A! G4 P7 G, b29
30
31
32
33
34
35
36
, A2 ]  s# e# w) y37
性能

空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
( }7 }9 S6 |, Y8 s- g! x1 M4 {2
)
稳定性：稳定
适用性：仅适用于顺序表
3 ?7 `" f7 x* ~9 V& |# g& p
1.3 希尔排序
# m% @8 {. r2 u' s8 i. Y图解(动图)
; c# A0 P4 p  I* W  i" g; K
" e' j1 S. {( U* c' j& W0 J5 _
7 N# l- m4 p3 X/ j" t基本思想
  ^% \( _* y! r, Q2 z0 \
先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

代码
% Y. t, F, S5 @& I2 E; c
#include "stdio.h"

6 f) D* U' ^8 @" ^2 gtypedef int ElemType;
+ f- |0 s- K6 y* ^* W
9 C& v5 j" f( e. G4 L! A: K1 hvoid ShellSort(ElemType a[],int n){
, Q# a* X9 W( j  t( d) \    int j;
    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
0 `, R5 g+ t. ?  a/ B& |+ _            if (a<a[i-dk]){
                a[0]=a;
                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
& M4 q& G# e4 l* C( K, c& @% A  V                    a[j+dk]=a[j];
7 ^5 U7 \; h1 E* \8 B  U! C                a[j+dk]=a[0];
            }
; @* b- w( v0 Y6 Z" q2 E7 \        }
    }
}

int main(){
; {/ K+ G# T1 g* T9 N    int n;
    ElemType a[n];
* g# L8 \, M/ [* D. T9 f( z# J( N    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
8 X2 j2 Q! v- J1 y/ J    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
6 M' J7 J7 @& [. u# z        scanf("%d",&a);
8 ^0 P( |" d; e: a% l' P: I, K    }
) }8 z" Q% z- Z3 j! K! }# j7 v+ p7 z    printf("排序后为：");
    ShellSort(a,n);

    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
& e, G- L( i% h+ n}

$ l- c' s. `4 s  O" T1
2
! Y% O; g4 a% O# U/ ^" L3
" A' r; |+ M& h$ u8 I4
. {8 g* ]0 {/ ]' z. _5
6
7
9 e! U) d* w" b8
/ |5 x% F4 j7 r; D* y' \9
! c" A% Y! `" t) J- P8 t+ u# r10
) h4 S% S2 V8 D; W! r; u+ S1 E11
12
13
9 `& Z0 Z  _" R7 U$ p- i* s14
15
16
* U# h* Y/ P6 s- C# N1 L17
! B) r4 K, t+ e18
19
; K* t" I+ V/ j$ Q2 j+ B& R20
- ]/ P% B2 o! S6 ?8 q+ a: [6 a21
# h6 ~4 _! i6 E* O22
23
) e/ W  b7 m+ h2 _1 {0 D7 P24
25
! _3 ]1 k% N) [$ P3 }" _, Q. S26
27
28
3 B2 U% F+ N  K29
1 O3 e/ [5 S/ `# i3 u6 L+ q30
31
32
- h% u' Z; ?& q& r33
34
- c+ p- j7 x( ^) K性能
) V2 z8 f# W+ w9 J
空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

; C$ H7 R0 {! i时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
- X0 X" k8 G# b  b  ?* ~1.3
)，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
2
)

) j% f* u' z( p稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。

' H7 N* v6 S/ `. |$ z
适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。
0 j4 u: H8 l0 K
2. 交换排序
3 R9 P; p, ~( ~- C. A2.1 冒泡排序
% g( m& G5 @+ K# a图解


! b' w! Q: _4 {基本思想
6 m: C$ Q* S: X: ~+ ^  C( g5 n/ m
% X, Q8 h8 y3 S' b( x( Q从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。
$ P+ ?6 a( Q+ t6 y9 Z& M
: F8 W1 u- b/ F# f代码

+ Q! Q1 g! C: M) A* C$ k$ H4 j" D方法一：将最大元素交换到待排序列的最后一个位置

3 j* L2 _: P% H5 |3 G. [#include "stdio.h"

typedef int ElemType;
4 q. r# c, \' s1 d# R" O
void BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
5 a7 L2 n1 ]' S# A$ t        flag= false;
        for (int j = 0; j < n-i-1; ++j) {
% s$ w- J1 \. e9 ^% H            if (a[j]>a[j+1]){
6 \" M; z* S9 S6 V                int temp=a[j];
# ~3 c% ^& L1 {7 L                a[j]=a[j+1];
. X( B6 k- |) m8 ^6 p/ L9 T                a[j+1]=temp;
                flag=true;
* ~6 m8 S8 d' N4 Y: T' f4 {            }
$ L8 n2 w& h- [6 l        }
( V3 X: t, w4 l        if (!flag)
! F  t7 J6 r0 [4 ?            return;
    }
3 H% Z% p8 Q3 Y6 ~3 s- z}

9 P/ g2 y* i8 U+ G2 Y; K! Z
int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
2 f- W- V+ M! \  h: {# \0 {' G    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
' a  F" m% v* f5 q        printf("%d\t",a);
5 Y# z$ e& q4 K" @" X    }
1 o5 G  M* K0 e% Y2 G1 R}
- Z6 O+ i1 r' t. b$ ^1 P2 S  c, W" C
+ C! e" x8 R; i; a$ e& G& K. r. m1
+ \  {" E# h/ ?+ U2
3
4
  [/ O% H, v- J' C1 C# M5
3 q& k9 Z+ A1 A; p. l# q6 N( S( _6
, |1 r. c1 h/ l% F8 B7
8
1 p+ z% I# z* R! y: Y9
10
11
12
13
: V$ r. a! v# R- t14
15
16
17
18
$ z, S* }4 G' h) q- K% R4 w19
4 @( v5 |5 K" O# a$ [20
3 T- S) i, Y: g* K8 R; m* I21
22
23
24
+ I; R1 p8 X, b3 y/ o# K25
1 x( k0 I' Z& ~! Z7 Y/ K0 X+ h26
27
28
' _0 e+ i% h2 Q5 ]) x29
30
31
32
33
" C& ^1 o4 K) ?1 P4 n! d3 D6 o34
) j+ w5 ?: x( I" U: w6 q( k35
; b. O$ h" V0 Z/ n. l. E  p5 S36
37
6 v6 d# G& _; G* ?运行截图：
- b( s2 W. y& K. ^
5 h0 ]$ ^) e& K0 f$ d9 r7 b
方法二：将最小元素交换到待排序列的第一个位置
3 \. @3 C. G) ^( O2 d
#include "stdio.h"

typedef int ElemType;
, g8 s: s$ s& c- z; h4 _) N
void BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
3 N0 J6 h" [" W, x& D: Y$ G) ]+ `        flag= false;
        for (int j = n-1; j >i; --j) {
            if (a[j-1]>a[j]){
5 Q3 D! {$ k& w                int temp=a[j];
, ]+ O0 t' b: p( q* |1 t; O                a[j]=a[j-1];
                a[j-1]=temp;
) C- s' t+ U: a' H4 e! ]                flag=true;
, U& ?" R# s6 ]8 r. O            }
        }
# X6 Y7 Z& s5 ]+ v8 O        if (!flag)
            return;
    }
}


int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
$ p( ?' D' H  K    printf("请输入%d个数：",n);
+ }* O3 t1 y5 N5 a! }" S    for (int i = 0; i < n; ++i) {
8 ~, `5 S% i# M+ e  h        scanf("%d",&a);
    }
2 ?( [* h, K( E+ i5 n1 ]5 L    printf("排序后为：");
    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
: @3 L# W# s2 o& o% v}

% @% s" t- d$ R$ a+ ]3 r9 ?1
2
0 e8 s% G; F% I4 L3
4
5
5 f/ ?4 v. X. B9 w5 G6
7
& g+ v% k0 @. F/ l8
9
$ P( F( [% f! l1 [, L10
11
12
3 e+ I& ?6 {1 O5 P13
8 Z) Z7 N$ w8 r. ^/ v14
15
  c2 D- B% o" R16
( x( Q. ^' D9 L1 r, S# N17
18
5 X$ F2 m" f1 |8 N19
9 O  L9 j7 I/ p8 |( d20
21
22
* V% A0 h: q/ B4 D23
  S# S5 U9 P" E9 L24
25
7 }9 m4 u) A% K' p26
- C2 ~6 z. L8 w1 f$ r2 f8 D27
28
9 J# D' o  @' o  @& e29
30
31
32
9 x$ \: Z: |* N, ^- `( A! Q33
34
- |+ q$ }; {* F/ y6 r5 v) K35
- s- u0 I2 o6 _5 Y36
' ?! u# c# C, b) i* b! c7 z; q37
9 o1 A$ D- ~) Z6 ^* K+ B运行截图：


. y3 D/ g" b! [- W7 \性能
9 @/ r6 L- i% Y
( {2 {# ^$ ^0 h空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
& m& w) _4 s+ I. }5 \
时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
2
% Z7 f0 g2 J# ~  H) v! G )；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
)；

6 l' \* l# ?  p3 c4 \+ `; w: B& o稳定性： 稳定
1 W  S: t% H) j2 ?
7 [( p1 ~6 z% o适用性: 适用于线性表为顺序存储和链式存储。

/ z' f1 C$ c* a1 k4 |& e- |2.2 快速排序
# F) A4 p# [. J图解（动图以后再补）
' F5 C7 A% z* J第一趟的排序：

7 _/ |* T, M/ ]2 I1 v第二趟：
4 f+ E; Z# w( }! u% Y" T
0 d2 T: ]7 C: {* j0 `( v1 ]第三趟：

. f$ |" y2 [1 w6 H8 B
( D8 l3 i+ J% e* Q* g  a6 v# G基本思想

  P  c8 h3 I  l3 O5 \快速排序的基本思想是基于分治法的:
& b; {4 h8 M. T
! C9 K$ G: L# F! d2 n在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
! L) I& D7 Z8 A& T, G9 t通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
/ {4 K( f* N1 K) n4 {# E代码

#include "stdio.h"

! |. }+ d$ e3 ~. Qtypedef int ElemType;

# j+ `. h+ {; C9 |4 k) D5 |" J3 Oint Partition(ElemType a[],int low,int high){
+ Q, v% F+ B5 k% I" Y    ElemType pivot=a[low];
    while(low<high){
        while (low<high&&a[high]>=pivot)--high;
1 B2 K6 J, k! [. X        a[low]=a[high];
+ t) i8 b( a7 Z) w! [        while (low<high&&a[low]<=pivot) ++low;
. _& G: ^) ?3 L: s        a[high]=a[low];
    }
. j, o8 S+ o9 y( p    a[low]=pivot;
1 E: ], v5 b% Y. W7 N    return low;
1 |$ L  b5 q" n+ x3 ]}

void QuickSort(ElemType a[],int low,int high){
    bool flag;
* ~4 w# V) i; E4 C" s; t' w    if (low<high){
        int pivotpos=Partition(a,low,high);
+ }' B; y/ E- O; X* H        QuickSort(a,low,pivotpos-1);
9 _2 l* ~( _9 m: H, w6 u- F        QuickSort(a,pivotpos+1,high);
' p- d# P$ t+ |& f0 \    }
}

int main(){
9 i. U" M( J4 P1 V- R' ^5 a    int n;
    ElemType a[n];
: t* J. j3 n# R! p, P5 x$ F3 a, S    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
# V, b3 |' S- H) n& l) e    }
$ m$ O% ]4 W$ t  t    printf("排序后为：");
    QuickSort(a,0,n-1);
8 I( o; [. v3 V: X; k& k' q    for (int i = 0; i < n; ++i) {
! i! v; c5 q! ^* j: n' g        printf("%d  ",a);
    }
}
' U" C1 V: I1 h4 a* Z
# H$ A/ a. R. Z  e; z/ q
( i; X5 ~1 I. X% S! c5 }$ D4 ^1
2
3 P# \9 e' Q* {( M3
4
: O* u( s  v# j& \' v6 s5
6
" Z. j- F# Y0 @4 m; r3 k7
/ P# C9 V( ]' q0 a8
9
10
11
12
, q4 t0 d& |6 @9 z9 x2 g& ]13
14
15
16
17
18
19
20
# F& l1 P6 h+ B3 I; K. ?( {: g21
22
23
24
25
26
27
28
29
7 }4 u$ E6 k6 a: M4 v- g30
( E) G# O* E1 K* ]3 _( j) ~31
. q1 C: z8 S. o# \32
, \) c& {* N2 i3 M- u33
6 F9 O0 ?; M, c9 e34
: T1 x  I7 m  a& B$ R% O% H35
) ?$ U) W3 a! `' J. V8 w36
0 t$ ]0 t4 L5 c; b+ |37
" [9 M. \/ l+ h+ w3 k38
. m* }+ U6 R, Q& J39
40
  y! P8 v4 d6 L  p" |41
8 [# @  S8 Q: O' ^' W9 u性能
8 a$ u/ t' \' t) J( q
时间复杂度和空间复杂度
稳定性：不稳定
- W+ \- ]! k. l  i" r2 R. `
3. 选择排序
3.1 简单选择排序
) Y3 p& w6 J" h# \$ H# c图解


基本思想

4 D4 m+ [% C( M在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]进行交换，第一趟排序完成。
4 |3 v5 {9 k" p% ?4 j8 ~在a[1…n-1]中继续进行排序。
+ p3 h( R6 a; `; R代码

#include "stdio.h"
% a/ I; I/ w9 C0 J( z
6 c% Y& _- k2 y6 {+ @3 Btypedef int ElemType;

5 y( F9 m2 o  r( ?, ~8 @void SelectSort(ElemType a[],int n){
) A# ~/ l0 g: ?) Q1 [" p% x0 y    for (int i = 0; i < n-1; ++i) {
1 W3 _4 M! U7 e; W/ ~2 \6 r4 R        int min=i;
        for (int j = i+1; j < n; ++j)
, V2 {; w: Y0 x2 ]$ [: K9 a8 W            if (a[j]<a[min])
: y/ E5 B1 e/ I9 ]6 _  ^1 G( j                min=j;
        if (min!=i){
" t) k  E1 t8 V, P6 D2 ?            int temp=a[min];
            a[min]=a;
# n! g6 [. s# h7 |            a=temp;
        }
, q& R5 q. q  j* ]2 k9 E    }
}

int main(){
: x7 T! \. f9 R3 E4 r    int n;
    ElemType a[n];
6 G5 J  D3 d# I( e/ t! \3 a) a7 Z    printf("一共有多少个数需要排序：");
3 L% l! r  u- \) F) |" W/ a    scanf("%d",&n);
    printf("请输入%d个数：",n);
( V& R# O1 j" q( c% t6 `2 t  w    for (int i = 0; i < n; ++i) {
8 z; W7 X- c0 \+ G/ r/ x" Y; c$ ]        scanf("%d",&a);
    }
6 I' @4 {) P1 a* U3 I1 ~    SelectSort(a,n);
/ P5 x9 K7 Z4 H    printf("排序后为：");
- U- X' x$ ^  A; b, i3 r) A    for (int i = 0; i < n; ++i) {
" S$ f- w; i: B1 ?9 D, H% m        printf("%d  ",a);
    }
}
4 A; u7 x2 m& t* k$ O2 C; t
2 A( v3 ?3 [5 x! k- t: u1
2
) _8 Z' f) |' ^1 }) M1 ?1 G3
* N* x6 G' m  D4
5
" |* N2 R9 r+ K/ G, [# H6
! M6 G  b9 U! M6 q7
: j$ n* [5 h! \" `6 d7 J8
1 A3 E: ?. ^7 V, @& Z/ p9
# i" e) x' A( h: F5 @2 A5 {7 R+ h. H10
' {& ^! Q$ w3 e; a$ h" ]11
+ H( ~) T* k& Z( D# C8 m, V12
: j# w7 c6 C0 U5 f- s13
/ {8 I9 Z9 ~/ ?2 [+ v+ y14
2 W5 {* A3 @# U( T1 \2 d  _9 i15
  l# A9 m+ J) ^- Q6 L16
17
18
19
4 d0 W0 X$ T7 D20
21
# @. [2 b7 ]2 g22
' E1 C8 N: _' V5 ~  B: G23
1 T3 A8 m& k. V) n  U9 a9 _24
! F0 v" ^( e3 d: b4 e25
5 q0 N4 r$ D9 B26
27
28
* ]3 W6 E1 X0 E5 v1 l: ^6 b29
30
31
32
7 B2 V" }7 i* \9 e5 S33
# b, G; `8 `. D, t: Q2 v+ z性能
" r: v) f6 D7 Q1 Z& C3 U
  j0 X9 J, v% ~1 o4 J* {2 d9 Y空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
! B6 k: S- T% }9 F2
' ?" r) i: N1 z: W2 B" M )
稳定性： 不稳定
- J' |, A2 h( Z8 j' @( \/ D
使用性：顺序表和链表都适用。
5 B4 R' i$ x4 r2 f- ]( y
' }& \9 ^2 C8 _! b, D3.2 堆排序
看堆排序的点击这里！！！！

4. 归并排序和基数排序
4.1 归并排序
图解
2路归并排序
  B6 _& X3 o6 ~

基本思想

) o4 Q2 i" D& Q# r6 Y# s% h将待排序列分成长度为1的子表，然后两两归并，形成有序子表

然后将子表再次进行归并，直到子表的长度=待排序表的长度。
代码
7 ^' e) W$ p! M8 u
- Q8 X1 C, h; @( F#include "stdio.h"
#include "stdlib.h"

' W4 Y( U8 ^: ]8 v/ o! Ftypedef int ElemType;

ElemType *b;

4 b4 H$ ~1 @( Z5 Nvoid Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
- z9 M  w2 W  H; R0 K8 F5 x3 r7 E) s    for (int k = low; k <= high; ++k) {
        b[k]=a[k];
* r2 j- ^3 }+ P$ I    }
1 {+ ?: g+ F' j7 z. z, s( i    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++];
    }
+ G% q1 ~3 Z, H" j) D8 g8 q+ Z, V    while (i<=mid) a[k++]=b[i++];
    while (j<=high) a[k++]=b[j++];
}

void MergeSort(ElemType a[],int low,int high){
9 d+ N) m5 _/ u% P- ]7 G    if(low<high){
8 A0 ]$ j; s6 q: ?7 j        int mid=(low+high)/2;
' c5 H' k1 A+ g) B        MergeSort(a,low,mid);
: a; a* K2 M* Q  ?3 d        MergeSort(a,mid+1,high);
( d$ k0 Y7 B' d3 w/ v! O        Merge(a,low,mid,high);
  R! m, o, F: W    }
+ {5 x: t( E. m9 W: c}
: b5 Y& N+ V5 ]. D0 e2 H9 P
) X/ Q0 U8 Y! [. o6 hint main(){
    int n;
    ElemType a[n];
    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
    printf("一共有多少个数需要排序：");
: E* j/ K0 |) t- z/ p2 q    scanf("%d",&n);
5 R! N+ L: L% l: w9 Z    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
. c, {, D: [: s/ a        scanf("%d",&a);
    }
( k( n2 @9 y8 [8 q  X9 q  u    MergeSort(a,0,n-1);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
! k( E! G1 W, S) m" w) v}
1 D' ^2 ^2 @, W3 A0 a% d  J
  C& S3 O2 }: O/ |% C
1
2
0 k8 N2 j# K0 E  K$ }3
! `' a4 o* L* a) D  s4
# I/ ?& v& @1 x& y! ^& r) f9 ]; {5
& j2 S0 K; n1 v8 f  K+ v6
7
2 ~1 r! ^8 W& o; o. c9 S( f) [0 a8
7 c, @% }( S9 V( A9
  a5 u9 ^# l3 \$ _/ t( G10
11
12
13
14
7 x) ?" l! g3 N5 K" @- f( f15
16
17
: a, o& Y+ V: B) N) p4 s18
19
20
21
) ]& b; u, B+ s4 P% |/ W" s/ N22
$ y/ g( s. M$ V0 V1 A6 i4 R23
24
25
26
. O) @$ D* A7 J2 E$ L6 C; {1 l' B) a27
4 k+ z7 P: r( Q: j28
  V2 v7 U3 _! m' i29
6 j8 _: _. p  l30
1 q! F, w/ V5 Q5 H7 }! r$ [31
32
4 m* X6 A  G$ d+ a4 g33
34
( R2 U+ v1 x4 F/ y) t35
36
: {" G3 G6 w6 R; d8 p5 y37
8 S$ U, }0 B. V* H( P7 q38
/ e2 M  C- a% C/ r, Y, w) A39
: P/ b' F, M3 @( l40
7 v" p& @' l: a( o  u# s* d41
42
43
44
4 n$ }  h4 o  c7 A: k' K$ H45
/ t+ f3 s: f; z8 `" {46
性能

空间效率：O ( n ) O(n)O(n)      创建了一个数组b
& @. J; N& c/ Z7 M* J: k时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
  a! s% D+ ^9 z3 Vk
​
n)  k指k路归并排序。
. o  t1 d3 W) `2 t* @( r1 q$ ]稳定性：稳定
( G3 V! Z* f! D9 S& t% a0 z+ f
3 F3 L5 M; c  N; _; H! z4 W4.2 基数排序
- T) m& O5 S& g! |* v% e8 M# r- J图解
% e* ^6 \# @' r* s0 j; [
- K4 l) k8 S+ L8 s% l5 N3 a
基本思想

# d  \" m( V# E& w( P3 ^将各个位数（个位、十位、百位…）进行对比。
- i* l" _/ O: x5 k- Y8 {7 L为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
  ^) |+ x6 W: A! ?4 |$ |
# X) i! r, Z& Q, Q- F性能
2 j, D) `" N: W
空间复杂度

时间复杂度

2 l* T  D0 x, o! ?! z4 `; Q
稳定性：稳定
3 s1 \% }2 S, x; J+ t4 r! _" W- |
: y: u0 J! Y% P% j5. 内部排序算法比较及应用
5.1 整体比较

# Z5 q# G* p$ _7 c* S4 a9 p- `& {: ]
% H, F+ X% u8 c9 R' S5.2 时间、空间和稳定性

: y1 T# Q$ [  _
& E9 U4 U9 ^3 s$ z: l7 m参考资料
《王道：23数据结构考研复习资料》
————————————————
" X+ T, T0 G* |3 ?3 t- w版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678
9 ]0 f% N* D8 X& i& Z

! D3 f7 d2 `+ j