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

杨利霞

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

排序
* h( e; b# `% Y9 e4 C+ X! f; @1. 插入排序
1.1 直接插入排序
1.2 折半插入排序
( H0 \7 H2 p, D- W# m% [2 s1.3 希尔排序
0 b9 f, d3 s) ?7 R2. 交换排序
$ V7 D2 }% s6 s4 m: h3 p2.1 冒泡排序
2.2 快速排序
3. 选择排序
3.1 简单选择排序
3.2 堆排序
4. 归并排序和基数排序
4.1 归并排序
9 g/ Z: e& v* {, s* A1 b3 a4.2 基数排序
5 H( w. x. O1 M& @% y5. 内部排序算法比较及应用
5.1 整体比较
& I2 I1 d# R$ R5 E5.2 时间、空间和稳定性
6 j& }6 S  Z+ W- F- }. o6 {- k参考资料
1 n6 T8 U$ d" m* V0 z- x& k
内部排序：是指在排序期间 元素全部放在内存中的排序。
, u! ^8 P7 E  g# X1 }  p内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
1. 插入排序
1.1 直接插入排序
; D8 h/ k, @9 c. m' h图解
8 m8 G9 I/ m6 g/ A0 k

$ E6 Z+ X" K" @8 k3 Y基本思想
! K3 Q+ _6 ~# d  E- |( i
9 F" s) G6 e' P! T/ u1. 查找a元素在第1 ~ i-1中的位置k
2. 将k ~ i-1位置上的所有元素向后移动一个位置
5 q0 X3 T; E! ?: v/ G3. 将a复制到a[k]



; X4 o- u6 M) N; w9 p4 t代码
5 l& K: j0 o5 V7 P
. k9 s) P7 q* L0 n! E4 W$ @# n- x$ J方法一：

数组的下标从0开始，如上图。
5 U% ]* y' Y) g2 V
#include "stdio.h"
. ]( _* k' Q, j  n- P! G" G# W% L
typedef int ElemType;

void Insert(ElemType a[],int n){
    ElemType temp;
7 x* G. g! B5 z3 R& }: Z$ p    int j;
0 y" P+ B! ]+ g0 ]6 O6 y    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
        if (a<a[i-1]){
' S0 \- J  w/ U6 r. u6 q            temp=a;                                                               
            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
                a[j+1]=a[j];
            a[j+1]=temp;                                                       
' c0 M" g" S1 e' j0 b0 F, U1 n+ G        }
    }
}
# w) {( G: N, z
' I8 {+ K) q% z9 F% g0 aint main(){
    int n;
    ElemType a[n];
( S9 S& R5 d& h- m5 f( o. _    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
1 B+ ?* a7 q# x- w% I% |    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
/ I: W9 |* n, p% R+ I# ?1 P  H8 a! m        scanf("%d",&a);
7 g1 u! V$ T' [4 O. e# ?* N    }
6 v/ [) H; `' I    Insert(a,n);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
8 l4 p% H* ]* E, r: t        printf("%d\t",a);
3 V0 H2 Z, K* u    }
6 y2 |4 B) q9 U}
( {+ A* R3 f! {1 ]6 j* q3 |
1
2
3
4
/ u9 g: _: S+ m" P5 Q) ]+ }! k5
# v: T% P5 d/ x0 l8 P6
7
" w1 e8 o6 L, d) U8
9
10
7 Q8 S! |& ]  W: r: r7 \11
12
# _) H- ~+ m) O) v4 l- Z13
14
. l) `! V( \* U15
16
17
: C6 P2 M. N# p0 `3 D18
19
20
21
/ y( o) \+ |; B' j1 D9 p22
23
2 F$ N+ C! |0 W4 R: |' D24
25
26
27
28
29
30
31
  `7 D' n; s+ q8 B% c9 k2 M" G32
- X% v# U! t2 o$ k4 i方法二：

9 ?* \! [0 n) ^0 P$ v

#include "stdio.h"

typedef int ElemType;
, Z4 M) z  A! U" c1 P5 ~5 `
! q+ G9 {2 `2 ~% X" B0 I* q7 Pvoid InsertSort(ElemType a[],int n){      
    int i,j;
    for (i = 2; i <=n; i++) {
        if (a<a[i-1]){
            a[0]=a;
$ A+ \/ G2 t, B3 O/ p            for (j = i-1; a[0]<a[j]; --j)
3 N/ i2 y; o$ U                a[j+1]=a[j];
$ m6 t3 y8 Z$ G  u/ S% e            a[j+1]=a[0];
+ L1 Q3 i( _9 z% {6 o        }
; m. ~8 h$ s. u6 T5 [* H    }
& O; ^% h8 O2 Y6 I5 ~}
int main(){
- z  L& T) x. J  Z0 o; H% h/ B6 B) ^    int n;
. f! k0 O' P$ \: T+ G& Y# c    ElemType a[n];
    printf("一共有多少个数需要排序：");
9 \# c2 V# V5 u5 O4 M0 |    scanf("%d",&n);
# v  C- Q8 I/ [# ?    printf("请输入%d个数：",n);
/ e$ b6 L( R! I4 C' i    for (int i = 1; i <= n; ++i) {
) |" }5 E; U) j/ o8 P        scanf("%d",&a);
8 o$ f. n. G' X" T4 P    }
# @) U3 N" \3 L    InsertSort(a,n);
. r4 o0 q, j+ z( f7 P* x  G    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
( ~/ B4 ~* \2 X5 o9 W9 j        printf("%d\t",a);
: m6 p3 T8 i; i: X3 [. D6 c; g    }
1 a6 R3 w' |  y' r, ?}
" w4 _( \: Q+ {
1
& W' @2 Z$ b; p) u2
3
" y; R; ?( {8 n8 R5 \4
* p! d: U! e+ e. H5
6
7
8
9
10
7 o5 Q5 T3 u# L0 K" l: P1 q7 r11
12
13
14
' ]5 c$ c0 W" M15
16
17
18
& N' q" `1 T( z7 E19
- C- b+ z9 C$ a' I& l' V20
21
22
23
" U: q  F1 K$ p7 u9 K24
25
$ F7 l: v7 a+ D9 o, [0 f" w26
27
! \8 H0 ]; ~: U$ g) U9 v28
29
5 Z2 m2 b1 \' V( _30
6 V; w- w' T; X4 q0 D0 c算法性能

空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)
+ h7 a* M! w& K, r
时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
7 f0 q& e6 n+ g$ R0 h9 Q$ C) x2
)
# v5 O1 c3 v; h1 M
# W) ]. T; c2 G3 b6 ^
稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

1.2 折半插入排序
图解
第一趟：

第二趟：


" ]7 \) g8 s5 c% Z6 e1 _2 ~) t第三趟：

第四趟：略
第五趟：略
9 \" Q5 a6 N1 x4 _
& q7 M3 f+ t% g6 d) q基本思想
, y- \3 \/ `4 j8 S) a6 ~3 D
与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
% b" \& i+ \5 h) G* T1 h3 |取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
' C3 j6 P! p: C) U. Q1 A0 U& @代码
0 s4 d1 A+ N0 P) a3 s: V
7 M8 L% Q6 p, e/ a$ ?#include "stdio.h"

: t/ y  ^5 U: W. i% |typedef int ElemType;
9 n- {! ^, X; H5 S# Y
) E! B: P, V! n; w: Ivoid InsertSort(ElemType a[],int n){
9 n/ f& z( |+ W6 i    int low,hight,mid;
    for (int i = 2; i <= n; ++i) {
" E8 e! F, p$ z- Y        a[0]=a;
; ]5 ^, F8 i- b* i& M        low=1;hight=i-1;
1 z* T0 Z) R' Y. K( K* k/ O  H        while (low<=hight){
            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)
1 {* Y# f7 ^2 z            a[j+1]=a[j];
% D3 w$ `4 y9 n  B* q        a[hight+1]=a[0];
    }
4 s( e# m0 H/ Q( o- h- R% |}

- i( e! {9 r; Z* F
int main(){
    int n;
& f- f2 l3 X8 C' H! n    ElemType a[n];
( _1 k, A% M4 R! k    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
' O5 `, q1 k$ [& k$ ~    printf("请输入%d个数：",n);
' v  Y) M  r6 Q% M    for (int i = 1; i <= n; ++i) {
5 G. P9 \4 T( x6 y* w0 R        scanf("%d",&a);
) N0 g8 U5 x3 r1 L( a    }
* e' _; A8 m; p1 q8 H- y* n    printf("排序后为：");
    InsertSort(a,n);
& O# N/ U8 t/ S, ~& j: t
: S1 ^# _9 \1 `" `( |8 R    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
0 M/ M6 Y* r% I5 A& v}
, d  h, W& t* t
1
2
! a# h1 Q2 P6 s  i  k7 v3
0 ?# t# N2 K! W/ I- g8 \4
5
6
7
# o. W' Q0 L) K  h% N) n8
; k( {. L# m/ g) V+ l: J9
10
" _1 s" K7 S( G( T3 A; H11
12
13
2 R# Q! [1 S8 u6 l- v- ?' V" y/ E' C14
6 Q8 a! m8 R; |8 ?: t$ W15
/ g( \) ]5 b" z2 l16
7 f3 |  h; X% a% R- ]8 w17
18
19
20
21
22
23
1 y- a% I" P. A24
5 f" a) j7 c+ H8 c- @2 D25
26
27
! C4 q# v% ~% r" Y28
29
  `& E+ x  T; I7 V30
- j  B9 C0 X7 f3 B31
( l5 M" n% _! V+ X32
; }: H! H2 F1 k9 m33
  B% e4 v2 V* m! p0 r$ n2 i$ J+ F5 z34
35
/ ^5 R/ ?& ?2 {; b9 A) C  y$ t36
37
性能
6 i) ]. z/ f+ Z2 K% I0 C6 m. R. a
空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
2
)
% F4 `8 C: g* J稳定性：稳定
4 w& B" V8 C. R6 ?7 h, m% c; [! k适用性：仅适用于顺序表
6 `4 u- w6 u9 n  H; `9 k6 X; B
1.3 希尔排序
6 c* ~1 {9 B. k' x5 D* g( ^图解(动图)
) i) S6 g, V6 n1 p; u0 k. f1 D; Z

. k7 r' T' B1 j  ~1 s$ s) r4 {1 G$ Q基本思想

0 l' i/ F8 n, \2 \7 U) F6 E先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

代码

#include "stdio.h"

% ?1 I' P( t5 O6 ktypedef int ElemType;
- O, q( g. A; t+ W* I) H
8 ?% j- W( ~7 O. _- R8 Lvoid ShellSort(ElemType a[],int n){
' L% v- y" a2 X/ m8 v. Y! n3 ?2 n    int j;
$ ?$ F; r4 n9 R' p5 Q  G    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
6 ]7 N2 X9 c! u! u7 ?        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
) |; Y" b8 _8 a' S$ S7 v            if (a<a[i-dk]){
: Y1 n& ^" R2 o2 {8 `5 \2 ]& V                a[0]=a;
                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
. J. c' e# x7 ^+ y8 c, C                    a[j+dk]=a[j];
" x6 p5 C' ^5 A7 g6 S                a[j+dk]=a[0];
            }
6 d7 u: ^2 x; M* s        }
    }
}

int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
6 g$ S- `' T8 @- j3 {    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
& I. j( E, F2 S# M    }
    printf("排序后为：");
; o9 ]! I! m% Z" H3 b) d$ x    ShellSort(a,n);

4 C% i9 z2 G& v+ ^/ ?  Y    for (int i = 1; i <= n; ++i) {
' b/ q# h! l3 U; i        printf("%d\t",a);
    }
}

# x8 H; ]( C$ j: G; C2 }7 Q& r0 h1
2
) b9 H2 A# \0 z$ T8 y1 P6 ?3
4
. D9 b  V! {" i- A& s; ~5
6
8 H) C0 E" T! Y, ~; ^4 c% L7
+ h! E* I% W2 K8
9
0 H6 M, ?& P  h* ~/ G10
0 a" i9 X8 f$ Y% e11
12
13
1 ~6 P9 Q* j! X) Q; Z14
0 x4 m. x# }- a& l15
16
' B2 c* Y! z( t. V17
/ w& g9 A+ n( N18
1 ]2 f# `& ^4 C+ V: W. X19
20
21
+ o% u" v4 \. K8 e: f1 U22
23
1 i& r: K; c- n$ [24
25
! c9 @( V/ e& e# Z9 [4 `26
27
28
29
/ t4 q" h4 L, T, D6 H: z30
31
32
33
, `2 I1 L2 F- G8 Q' b4 S% Q34
7 n. ^% A5 A2 i$ J3 r, G性能
8 w0 W, C. H3 r, A/ ?4 K
空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
5 Z% Q( W- w  @# {* N8 d: W. H1.3
)，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
6 G4 S' }: m  I7 U5 B' F* b2
)

稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
7 A3 M6 o3 Q/ |2 k
+ g8 [" u' }( [7 M+ w6 Q* l
: Y7 @% e( z0 l- P* k! q适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。
4 [5 `+ y- x6 I' K) [; H. b
2. 交换排序
2.1 冒泡排序
6 _4 E# P( }' `* l3 j5 t% v+ b" g图解

" a. `  V* @4 v" I
: k6 \1 ?9 ]: J- u7 ^基本思想

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

代码
% |$ w: L3 \3 S/ s' e+ }% i8 a# k
8 X0 K% q5 ]4 l- T1 a( X方法一：将最大元素交换到待排序列的最后一个位置

#include "stdio.h"

typedef int ElemType;
, O+ c  K: |" g% L% I7 C' c
void BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
) ~4 ^9 n  R8 H! Q" |% K; h# G        flag= false;
; d* ]7 b5 Q; w        for (int j = 0; j < n-i-1; ++j) {
            if (a[j]>a[j+1]){
                int temp=a[j];
                a[j]=a[j+1];
# w$ M& A1 R5 \8 t/ M                a[j+1]=temp;
                flag=true;
% J& k8 g0 w% g3 A            }
7 o) g: L8 @* a; b1 v; ]* [4 ]5 E" e        }
- s; W  \8 I& }! |  x        if (!flag)
            return;
/ \5 C6 ?* \0 B6 U* [    }
& O/ @% O2 B, |: z. F}
; [7 I4 q* ~8 {" J

- S1 o5 x( ?2 b) p$ Uint main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
, s. G& {" O' K& c2 K+ o; d. g    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
  T) ]: f8 d1 q& c  ]# n7 g7 O& Y    BubbleSort(a,n);
1 Y8 d7 ]0 C$ |4 S( m! {! Q    for (int i = 0; i < n; ++i) {
  X1 z! Z# M( R- n3 H6 e        printf("%d\t",a);
9 M9 N0 p" `& U( {( R' [    }
}

( @0 ^) |% \5 z1
" U  T7 d2 b# ~! @- k- U' Y9 a2
3
4
$ G. [7 E; q" m+ E) k6 K* ?5
6
7
. J4 D1 D% S7 N3 J5 K; Q$ o8
9
10
2 {  D0 x) @2 [' G11
12
13
14
7 j6 x* s, |+ H4 t/ ~2 o3 L15
16
17
: `! {' A9 L4 ]  \3 E: Z18
9 _+ Z  g, w% [# s) n, Z! E- I19
20
' S) x5 ], ~6 @7 }21
1 f" O( p/ m1 E9 m* V) ^& f0 g22
4 s: O$ ^0 m. j# {# M# c23
24
25
, D, [( }7 p, ]# i1 G+ J26
27
% g4 A3 q$ N8 u$ L/ o8 R28
1 D. V" b3 \0 ~' _" I; C1 ^29
) ~# S4 V) j4 o0 @) e30
31
9 k' o8 ~. {) e# ~# ]+ B! U32
33
34
/ @7 d# m# ]% N$ q6 F* t6 |% k1 R35
36
9 e- H6 y, X1 L% u5 G! A37
运行截图：
; ^9 k! ~1 k% i2 N* d
! I8 y( b( D. z4 P, g# N5 d4 n
方法二：将最小元素交换到待排序列的第一个位置
5 b/ P- C$ \- f& Q
. d, R2 ]" g  z" P0 T6 R#include "stdio.h"

: l0 z/ Z0 V' U( w, Stypedef int ElemType;

void BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
* V/ r! H( I9 X6 u* p& K        flag= false;
$ v! n; W& M) X6 o$ A1 G        for (int j = n-1; j >i; --j) {
. z# X: @3 H' y0 c7 J2 e0 V            if (a[j-1]>a[j]){
                int temp=a[j];
& s# j; U1 z- K+ [7 p* ?: r: f                a[j]=a[j-1];
1 c2 G3 `5 ^% B& s; q                a[j-1]=temp;
& ]  q" H  q( D! \. _! Z4 }6 b                flag=true;
5 ?+ [  P2 k4 a2 {            }
4 X5 d+ r9 k# u        }
        if (!flag)
            return;
    }
3 r# Y; E# z  {7 f5 Q}
/ ?2 @7 h6 @0 C$ v( ?4 r3 ^0 Z

int main(){
: A& Q5 @3 m  j- z7 t    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
  T( ]' v. v- M$ Z4 l    scanf("%d",&n);
& n8 ?# p/ I) P. H1 t$ a# \. k    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
  w1 o+ T# M- L" O! f  ~8 @; P        scanf("%d",&a);
    }
# R# t% ]" `- d% y# m    printf("排序后为：");
7 {1 H8 C0 e' j& v    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
* h' a) K( i0 u( D    }
5 U$ T  V6 @$ r& ?$ v7 B2 J1 H}
5 d+ U4 _( C7 l0 ]. x
1
2
/ x% D  K$ F6 F/ L$ f3
4
5
* ]* |/ W. d+ p+ M/ X6
( {4 P- M. S! K( m7
  y: l+ s+ K) N- `8
9
, G- K1 N0 a) t: w) V6 {) H# J10
11
* ~5 d, D8 I- j/ m& v12
13
14
3 P1 ~, d5 x( z, C8 r5 `' s15
$ D" E4 N* w. o- |16
17
18
19
- H" m! Q: _; F20
& X0 u5 R, Z$ I- [21
2 d) _: P/ c* v22
23
24
1 l6 ?5 y( y4 Z25
26
27
, N' A! o; A6 k# Y! ^' @6 O, Q: r28
29
30
31
32
33
34
4 _8 [: Q7 ?' i; G( }; [* _& L35
' R) O6 {. S" o36
& C7 R% b& D! o/ N5 f5 T37
! T% x3 ^: ^4 a* l运行截图：


! n. w4 N: Y  q9 U% b1 c: s性能

  F; w: z' D& l9 x6 y3 {! q) T空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
/ Z! I6 ~2 B0 T# c5 s5 g2
1 T: ~6 U# N6 t3 D' T% Z )；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
)；

1 J, b& w+ a2 W$ {* |& j稳定性： 稳定
/ x1 ^3 Q1 u- j9 q: J
适用性: 适用于线性表为顺序存储和链式存储。
- Q( H. H3 J2 ?- R, b* U+ q* }+ J
2.2 快速排序
图解（动图以后再补）
; b6 b' W* @( C+ G8 ~' I  p6 Z第一趟的排序：
" X+ |5 `5 @7 P+ p3 i* k
8 f+ y6 x. c: M7 ?第二趟：

* U/ e6 u5 i8 a0 x3 \0 p第三趟：

( [/ x: Y6 d" y  K/ y  u, h
基本思想
% u* v) N+ d5 H9 X' H1 C! O% t
快速排序的基本思想是基于分治法的:
* j- k, ?2 f# J2 s4 r4 B
) w/ A" K5 W, a  r# P. _在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
5 Z' u% T" S/ c5 d( C$ O  X6 d5 t通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
( m9 r  y/ O8 Q7 \# M1 \然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
  R, V9 Q- j+ R" j# Z0 d代码

#include "stdio.h"

typedef int ElemType;
1 e2 |, V' O& ~8 W8 y
) O4 R/ Q7 C& F) k7 Rint Partition(ElemType a[],int low,int high){
    ElemType pivot=a[low];
" w; \- @& A" O$ X7 j    while(low<high){
        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
        while (low<high&&a[low]<=pivot) ++low;
1 x9 B* m1 c- h4 U8 }2 k8 H        a[high]=a[low];
    }
    a[low]=pivot;
4 Q# D8 k' l2 ?% ~/ L* X/ `6 |6 @    return low;
}
9 o, x0 M- \& b0 i' V
void QuickSort(ElemType a[],int low,int high){
    bool flag;
: W. S* ~1 S+ R6 ?1 q/ C/ `    if (low<high){
5 [9 x3 h5 q/ F  Q        int pivotpos=Partition(a,low,high);
  T" d: o# m  a" t5 ^/ H2 O- V        QuickSort(a,low,pivotpos-1);
+ {1 q% g* `  Y6 Z        QuickSort(a,pivotpos+1,high);
8 W: n: v7 G; M4 Y& |. B9 ~    }
/ W, Z1 k; W8 S# H& X) l}
9 i& d$ A4 l  e# g/ }' U# r
8 m4 f, J# _' h3 G; a: oint main(){
$ c3 B) l9 `4 I# L: t) `    int n;
3 V! _2 w0 S; ~1 O3 v    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
2 a' H/ E7 a7 ^& j. f    for (int i = 0; i < n; ++i) {
* [5 b8 Z6 a8 y/ ], t) l* T        scanf("%d",&a);
    }
. ]# {9 p8 V. |( p, p2 _: B    printf("排序后为：");
    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
0 Y* r1 u/ y7 N5 r. d' N. l$ C        printf("%d  ",a);
7 r$ m' w2 Y5 e- `9 N    }
! t2 f1 L6 W5 W5 w}
9 I4 |) ~3 }3 v1 [8 t" [( M

1
7 r, p" Q4 V, q5 o1 [2
3
! u9 ~- j1 f) F( i1 e7 P( [% k9 f, o4
3 v& I) Y5 _8 a+ t8 Q6 \5 O5
6
7 i" v5 E+ P6 O+ r1 u7
7 X5 I4 ?' l2 n. J/ V$ ^8
6 l, Z- E5 @5 b) @. u3 d, N% X9
1 B* U! q) V; d# B3 c10
9 O+ l( x) E/ O; R' N( j- J9 R8 h11
12
' c, ]- J. y9 \$ V5 D13
3 C5 \$ Z" N! k) A9 N1 R, G14
15
  e. w% d# }/ I16
6 H& W6 ~" g$ S# A. w8 y' N) b17
18
- N6 p$ e- R! Z- @19
20
21
* a9 L2 ?; C0 j% p' x22
+ i- k0 O) U# j- x23
24
/ N& }" X7 v1 C, c2 R/ {6 W25
$ F/ b  Z9 U' \26
27
) P2 _: _/ Z2 P. R28
29
" j7 z% \" g0 j1 A6 k" _30
31
32
* D+ O3 @6 H, j9 K, R7 j33
# c5 e# ?$ X$ \/ _34
. ^2 @7 t3 r& M! l3 d35
9 s% W# F- B0 X& O' @. X36
37
38
1 Y) B$ f7 n6 v5 }( M, }+ m39
40
7 L6 j) \& t: h41
/ m, c4 r2 ~8 r. J3 d+ u3 x性能
+ g4 L' C  d" o6 J1 k& [! W
$ Y- @; x% U8 d+ R时间复杂度和空间复杂度
稳定性：不稳定
7 i0 ~" N5 X6 Q7 U( h& v4 C( F
8 g" j, y$ d9 A  M7 ~8 j9 [# a/ n$ e3. 选择排序
3.1 简单选择排序
图解

7 E# {) J' Y" k! y
基本思想

在a[0…n-1]中，将a[0]设为最小元素，设min=0
, t' n; ~( o- O6 ?在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
/ ~- i* E- M# S9 @& _6 _! V若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
在a[1…n-1]中继续进行排序。
' f/ L( I8 o( ~/ v$ `: s代码

' V1 L5 ]+ e+ D) O; U+ @8 U% w5 H#include "stdio.h"

, r+ m! x9 u) Etypedef 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])
5 `- K! t7 o0 E& o2 J                min=j;
- @2 e* }3 t* ^# j        if (min!=i){
            int temp=a[min];
            a[min]=a;
            a=temp;
) m6 Z3 i2 Q! |% A; q: s* E        }
    }
9 _+ X" l8 e, L4 `* G2 |8 ?, Q7 J5 \}

int main(){
9 F7 \8 K+ S0 E: \    int n;
7 ]; z! e1 y9 k+ ~+ r' X+ D9 n    ElemType a[n];
; Z% g4 t# a) ~" }2 |- ^7 B    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
3 R; T4 g5 ?; ]1 h: }6 d    for (int i = 0; i < n; ++i) {
1 T/ X: o( o" r# Y5 o! U  B) j        scanf("%d",&a);
    }
0 y* Y! o( |, @5 M    SelectSort(a,n);
4 H: H! m/ f9 y    printf("排序后为：");
/ I! c0 G3 o# O- X" r    for (int i = 0; i < n; ++i) {
# Y/ C) B3 N6 z# _( Q        printf("%d  ",a);
    }
+ l6 M. B7 s: T9 h}
9 F4 j+ _3 n8 c" z9 E
) C  ?5 l$ h/ N( O1 E7 ^1
# t% |& k7 j+ G" O2
" E. G3 I# k( k% }3
4
5
6
7
+ R: x6 N8 K: }) }8
9
" m$ K$ |: |3 ~  O+ W# `10
# F4 A& Z& ]( F5 v% z6 s0 W11
1 V+ |3 z5 _% |6 ~12
+ e- h) i( ~0 q, ~13
14
15
16
  I6 T' K6 w' J0 @17
18
4 f* @1 d1 I% m5 n3 f. @19
20
21
22
23
24
5 w, t6 R' l: p- e& p8 t' b& p25
7 R" M+ D" U8 R26
+ s3 a& f! \  D. d" O2 o6 T27
, \$ R" s; U$ p0 Y6 M5 V28
29
30
31
32
- v% v) ^. }# y: s, j) }, f33
3 K4 E  F: v6 J% A7 T性能
4 n% f  m1 f- l$ I/ V$ M% e; J
2 [1 ^. S" \2 n: I9 V" i空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
. x. o2 b; I& M$ R7 U" r2 v7 V2
* w* j. f$ Q  m% X+ L" E )
稳定性： 不稳定
) z2 q7 ], j: t# L* f
5 g) e3 r  _% s* i; ~使用性：顺序表和链表都适用。
3 t1 P2 l. y- O! w  _
6 J1 p: w/ p0 l  `; ~  s1 _3.2 堆排序
; U' L+ d0 L; \' r4 H看堆排序的点击这里！！！！

4. 归并排序和基数排序
4.1 归并排序
! p) M9 }, F( G! Q+ p3 o) R图解
2路归并排序
/ }/ v7 u$ l: B

! R& e. _( D. S7 v- x; q基本思想
) d$ ?8 J, h* P- V+ J) M
# z" E; Z+ q4 Z  P& T% q: L将待排序列分成长度为1的子表，然后两两归并，形成有序子表
/ K% J/ F1 J: V6 d' q% ]0 ^/ ^' s) Q+ o
然后将子表再次进行归并，直到子表的长度=待排序表的长度。
代码

  [! W. a5 a: f6 G- `#include "stdio.h"
. D  S% e* V7 C% w#include "stdlib.h"

typedef int ElemType;
* K" O% X- J1 p
3 Z- R- J7 W4 Y7 I3 w4 t) K0 KElemType *b;

2 \. K2 A/ G3 Q: y. _" ~void Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
& G& u" O; \4 P    for (int k = low; k <= high; ++k) {
- p: a" C5 o( F% u! o8 O7 ^        b[k]=a[k];
    }
9 Q- B& C# X9 f. \    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
0 R$ f7 _; ?: @! c        if (b<=b[j])  a[k]=b[i++];
$ M2 a. ^- r1 H4 n1 P        else a[k]=b[j++];
) z% }, F4 e. w7 c/ ~, `    }
    while (i<=mid) a[k++]=b[i++];
    while (j<=high) a[k++]=b[j++];
. `: b- H- Z) Q$ i0 t, ?: A$ g! u}
& v" y$ r: d. B) Q7 d
* g3 g* H2 {% D+ uvoid MergeSort(ElemType a[],int low,int high){
6 p/ w1 `( v& t5 R2 w6 P; Z, e9 C    if(low<high){
% X( i6 o! @9 Z1 `4 e/ h0 E1 _        int mid=(low+high)/2;
/ Y8 o* p/ q6 B& @) V( c7 @        MergeSort(a,low,mid);
: f; W! g2 i  J3 m+ @: l" s4 R        MergeSort(a,mid+1,high);
: |* G$ \: o- j5 y! _0 v( }8 d' {        Merge(a,low,mid,high);
- L. k) {( d7 \7 F    }
}
: u( J* h( i8 v8 B3 z% E4 Z* ]; H2 P
6 i1 m: C# \& Z8 m; v/ t( e0 hint main(){
$ {6 `3 t" J# o6 [    int n;
    ElemType a[n];
    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
    printf("一共有多少个数需要排序：");
" g1 K" o2 j: c    scanf("%d",&n);
& F* |, y- w. w7 }    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
/ L! q7 F& W: y7 ^3 J- E        scanf("%d",&a);
, _( ^5 l" t$ L4 q    }
    MergeSort(a,0,n-1);
    printf("排序后为：");
% g3 g. S8 H1 x  F- N& C1 `    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
: ]; }' o) @" F    }
}
% |$ L0 \: G7 c% f4 V' Y
4 V$ p' q0 x5 |. n
7 \) \& d0 A5 {( o! {( F7 ?1
2
3
9 u2 R) F5 h7 b, Q4
5
6
7
8
9
7 r( r$ N: J0 q5 B& X10
) v: D  o6 G/ I) c" h# I) b11
: a3 r' t  E. Q. O& h. w. x12
. m; O  m+ t9 N7 R13
14
15
% c! J# j7 V% y% A0 \: \16
* _+ n4 W+ t: \3 Y( K0 h0 ]! p# L1 @17
18
' Q/ a, R: q' U2 m19
20
21
22
23
24
0 [/ q" y7 j3 x$ z25
26
& [' u& I2 a. V1 A27
28
29
+ X; W; t8 P8 v  p+ b& h: f! v30
31
" _1 `, k1 T5 Y4 E: L: }32
, {% j7 p$ F! ]+ W6 I7 N! Z33
34
- K, \9 N5 q% S  `6 z5 f, K35
36
37
38
) ~0 X% ~3 g$ J& y  R. y39
' [9 u6 c) s1 S40
' l+ W- @0 i- a* A( n8 E$ h- o, u0 \41
$ t6 Q+ ^5 G6 K$ M- q+ o42
43
4 ~5 z& }; h' \( ]& I) I44
8 z9 t7 X! y, S45
46
性能
0 o% }6 S7 S0 |; L# L  l
空间效率：O ( n ) O(n)O(n)      创建了一个数组b
时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
1 a  @9 q) B* ?  ^. b4 D% G; sk
* B4 f" n/ I/ N# H) I) g* C0 P4 \( Q​
n)  k指k路归并排序。
5 ~8 s* [) T; |+ @0 J& ^稳定性：稳定

& }" C7 r+ Q. d  {4.2 基数排序
图解


基本思想
( G0 T+ a5 F' e2 S' L# C) b  m! k: j8 P
将各个位数（个位、十位、百位…）进行对比。
0 S9 ?3 ~9 j5 I为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。

/ q' I, ^6 ?8 y0 G: S) M' _性能
, Y; M0 y7 c7 V
空间复杂度
$ a% W  Q& A  G- j2 R7 Y
& o% k0 m6 Q/ ]9 E8 z9 X& ]时间复杂度

% X+ h! |( d8 ~5 I
+ A- N) `' L9 E* _, @稳定性：稳定
+ q6 R2 I! E1 n% P6 e0 }9 I
5. 内部排序算法比较及应用
& Y' K; b9 Y  d' J4 \* x& A7 B5.1 整体比较
0 G6 N/ {3 Z2 p/ C/ g

2 f3 D* V2 E. ^4 L3 h. n5.2 时间、空间和稳定性
  p  i# M( r5 x8 m& A  a' c

参考资料
《王道：23数据结构考研复习资料》
————————————————
版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678

! M; e$ M' |( c  j9 `3 ?0 X+ W
3 ^3 f  i8 W3 W" N1 `( ]6 ^4 `