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

杨利霞

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

排序
1. 插入排序
1.1 直接插入排序
1 |, H3 q: M0 @# L7 c1.2 折半插入排序
4 ^: y( K. G; v$ G1.3 希尔排序
2. 交换排序
5 w3 a9 }7 L& T; n% T2.1 冒泡排序
2.2 快速排序
3. 选择排序
6 C% c, y: S0 P$ k+ g3.1 简单选择排序
3.2 堆排序
8 _+ b9 V, u, i  K. t" `4. 归并排序和基数排序
% `9 e. k7 M2 O" A4.1 归并排序
$ ~( B+ |$ B9 t7 }4.2 基数排序
, ]" D* l- K" y5. 内部排序算法比较及应用
5.1 整体比较
/ S6 K2 v4 N- ^8 i2 K  d: B0 j( f5.2 时间、空间和稳定性
" q0 Q4 V$ ^! r# l! o# A参考资料
- q7 S3 \+ g$ W
内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
' a( C( ]0 |5 Q, x8 @1. 插入排序
7 J) W  u: O4 ~: Q1.1 直接插入排序
+ }; o. @( {  D* G2 H- v2 q图解

/ g& N3 @& ]# q! U' p7 u
基本思想

3 n/ q6 w- a: Z# i% ]1. 查找a元素在第1 ~ i-1中的位置k
* z% L9 o9 I( B3 ~# f2. 将k ~ i-1位置上的所有元素向后移动一个位置
3. 将a复制到a[k]



2 b7 a7 I5 P* L; {代码
! d4 ~% e+ d( N  L6 [: Z
方法一：

. i9 t6 \0 y- k数组的下标从0开始，如上图。

; x) t4 H: B! X4 H7 [( w5 U9 ~* o+ ~#include "stdio.h"
) {* Y7 ?3 n7 {& G- c. G
. f1 R& h- W1 itypedef int ElemType;
& i! Q, J4 q3 Y6 F1 Q
% b4 J1 B0 |7 m8 M2 I& evoid Insert(ElemType a[],int n){
5 L# @2 y$ h/ J+ R. r9 y$ A- k    ElemType temp;
0 o* z7 _$ l* Q9 A! y    int j;
    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];
7 x2 g, g4 V2 k% O6 n) ]! ^            a[j+1]=temp;                                                       
        }
4 T7 T$ `5 M& v5 E1 p6 Z  |+ O" e    }
5 S7 Q: o$ a" j) l; W% w1 V}

) `( D2 J6 r0 J0 [int main(){
    int n;
    ElemType a[n];
! L% o6 X6 ?. g0 G; a% I6 F    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
8 w! g* o6 Z5 l4 R/ ^* O; [0 c$ f    for (int i = 0; i < n; ++i) {
. r$ o4 T, O! O- [6 }; Z9 _) ]2 \        scanf("%d",&a);
2 N! O( ^: U# h    }
    Insert(a,n);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
% E/ X, d+ V; _4 w4 a        printf("%d\t",a);
; P+ Y0 f7 D3 K: ~1 s    }
" w) h" B* z. ~6 ?6 F& j}
( }8 _6 q) g5 X) r: F0 r
1
0 l8 W) [9 ?( Y5 \; j. }2
3
4
- `0 a* I, d  ?1 v! @0 R* t9 k5
# l5 u1 Z  ^4 ?* }" c6
* |8 Q+ D* l! w% h+ D7
8
9
0 V& S6 T% C4 M, I$ Z' \: K# t' d10
. {+ Y! b+ i# {. Q& Q11
12
! w* b0 g$ c4 V/ k3 b& Q( a13
14
15
16
17
18
% ^6 j. |, ^  L+ A19
# F3 G% ~; ?) F3 `, K6 h20
$ z+ x& b8 j+ I; f! M/ |+ l1 a21
5 ]/ _) Q: K  g% o4 a" i9 {22
. v) T# }' h/ W23
24
& v$ B: U& J1 a* V; A25
26
27
2 f0 v6 E1 E9 \  h* _' r28
29
. X. t9 v0 S3 o( ~, @' o' e# e30
" F# k2 H3 C8 c  }/ R" Z31
32
# r& S4 p5 ~1 C( e/ m1 k2 M2 u方法二：
; V; F. ~. c; r* b. g

5 H$ [6 \2 q) ?7 G
4 e0 Y* M9 Q1 T5 ?#include "stdio.h"
) E+ B) G6 |# g/ V1 R
typedef int ElemType;
  o; D6 ^; N/ Y; r" m7 T: w9 ]4 V
5 b1 s7 L/ h) Y7 O' w% f, L+ _: ?- xvoid InsertSort(ElemType a[],int n){      
    int i,j;
    for (i = 2; i <=n; i++) {
        if (a<a[i-1]){
8 f4 B/ }: F$ b4 ~* L            a[0]=a;
1 [% }0 y+ z. `$ s) r/ t) E- s            for (j = i-1; a[0]<a[j]; --j)
" Z+ W0 V  u, E2 ]8 A3 G                a[j+1]=a[j];
$ h* Z( t' _9 z: I            a[j+1]=a[0];
        }
    }
4 D6 @3 v, O. X4 m1 t$ g}
int main(){
    int n;
  r4 h# ^/ Q/ s& x6 [8 a8 E    ElemType a[n];
    printf("一共有多少个数需要排序：");
( |+ R! w$ M( p2 E( n: P    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
7 ~; l5 J8 y7 w: c+ d8 M    InsertSort(a,n);
. o" k; U  a( C; p- }2 }    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
7 l" o& j1 [2 W8 R* z. q  a( V    }
6 V4 }" l& m) m1 _$ C7 `$ |) L" f: {}

1
2 k& o; j/ I! D* L8 A) C2
: K# O2 s5 n0 Y. R: K3
4
+ o+ {( _4 U+ ~5 M# A8 o/ R9 i) T5
6
2 ]2 |. u! e3 O, I1 @# s' [2 C7
' g% g* k; ~/ S! D% U9 M8
$ k8 A/ ^/ c: q4 E: T9
6 M% ]: `  s1 p! U7 O( l10
11
% I8 {$ N6 R+ S6 D) G: \" t12
13
) S* q3 R. A. x0 S& V14
  X% M- {( m% v- x$ O, @15
$ r2 N! H0 Z  U) N) h8 Y0 o: L$ F2 g16
/ P" S3 _. Z+ a' O" I* x+ ^17
18
) v: ~' D- F7 B" F0 N$ W19
20
21
22
3 U! }. C! R& k- C6 B" o) S23
' _7 t& @3 V, f7 J7 |* ^4 h% k24
2 _  \: ?& p- W& f3 Q25
26
) W8 N; I$ r9 L$ B6 z* O( F27
( p: l, D/ m! Q' ^( K2 ?28
! S- t" u% r2 a7 W5 O- m29
- d9 V# n/ a0 _4 x6 P% y30
算法性能

; J$ g) \/ ^; @6 {, D. p' w. i空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)

时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
' B! c- ?8 h8 W. A+ ~, Y2
)


" u' O) R# B( U: ]6 a* v3 A稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

( W  \' j, X: T, [, S适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。
! i; k+ X8 y7 l) `( \! {3 o" Z
1.2 折半插入排序
图解
第一趟：
% O; w6 l" o& G# t( A* ^
第二趟：
' z3 e4 O# B; a: J+ j2 B' T0 D

第三趟：
# x: j) Y! r4 H% W+ O6 S: R
第四趟：略
$ S" \' L: \$ |4 ^; U( @1 q" I第五趟：略

: C) N. a9 R4 R% C( m7 w+ r基本思想

& @7 F4 Z( M5 I  z与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
9 S- W, S% |# t! e取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
# a$ O7 T0 V' U% E代码
! p& B/ K* K* H9 l* N* k5 T; O
#include "stdio.h"

typedef int ElemType;

5 D7 z1 F0 Q0 b  R7 C1 U3 zvoid InsertSort(ElemType a[],int n){
0 H6 `0 }* H8 d% ~; n1 y: V7 b    int low,hight,mid;
    for (int i = 2; i <= n; ++i) {
; S- ?- Y4 V9 E0 |        a[0]=a;
        low=1;hight=i-1;
, I0 Y: H8 _' j& l' l9 i        while (low<=hight){
3 ~; L  \- ]$ h" r/ ?. F            mid=(low+hight)/2;
3 T0 `) ?- |5 D" g# x            if (a[mid]>a[0])hight=mid-1;
% h, Q6 V" n; ~) F4 z            else low=mid+1;
8 S0 b) ]/ L( P; ^        }
        for (int j = i-1; j >= hight+1 ; --j)
            a[j+1]=a[j];
        a[hight+1]=a[0];
) \+ _. v  R7 ~    }
( ]5 `( W/ v2 Q}
8 u7 {; F& e5 J! `

int main(){
    int n;
% G4 t/ K2 N) U1 L* c( k9 l# Z    ElemType a[n];
; u8 s* C1 w; a1 n- Y  H0 b    printf("一共有多少个数需要排序：");
0 |9 f* d1 T7 A$ x: p; B* }    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
' l1 ]/ d' N* s5 d4 @+ Z$ F7 V        scanf("%d",&a);
/ |# Q, d# m9 L    }
    printf("排序后为：");
    InsertSort(a,n);
  n# a! q3 p, h' Y" W4 ~0 m# q
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
. H) ~) X( d  l}
) b( w1 D9 W( v" H6 x
1
2
2 j: Z( L( B3 |1 ~9 J# [3
8 \0 S! F& K; O- [8 v* z4
5
* c  b$ F) @9 }$ ?- x& O8 i) G' o6
/ @+ D, P: y+ v5 m$ d6 P7
8
. D$ O: E+ G, |2 |2 {* p. |9
10
7 J! o/ B2 A  s. g  L11
6 j* O: `' U- r  c12
4 N% H+ T8 d# p13
14
7 X3 D1 v' H. n8 D; T2 ?7 s15
. ?5 [+ o6 z4 @  l, @0 f0 k; ~5 i16
17
8 q% d* O. j  R3 w0 e0 ]18
3 \0 \7 H2 R% Q; n% |/ U- E  D19
0 X- w- w/ E' t# G% W; w20
21
1 v% ?3 ]3 K  `, d- G5 m" q) b6 M22
23
  R- z3 g) z; ~" B24
# K1 p& r6 v8 e1 S4 \/ [25
4 {9 ?8 h7 P8 }  {- Z" A26
* }8 H! h7 |9 a; k27
' o- K1 a8 D; J28
) w4 m2 |! x! P( c29
30
31
32
33
34
$ v" a+ Z5 y, M: ^5 |& r$ K35
36
37
& Z) J, P4 s4 P4 q& w) d# g" o" {6 ^$ f性能

空间复杂度：O ( 1 ) O(1)O(1)
# o3 j  @6 o4 T8 v$ `3 }7 o时间复杂度：O ( n 2 ) O(n^2)O(n
3 d# U9 Q- N3 X( d. c! _8 [2
# v* }8 Y3 p! z+ a )
' Q8 g" C) M& ]7 _! E) ]稳定性：稳定
适用性：仅适用于顺序表
$ {( d% k+ q/ e% E- A
' C7 o9 p- r  A7 s- s/ T1.3 希尔排序
8 W# Q/ `2 ?# `图解(动图)


1 E- e* O/ W1 P9 ?基本思想
& g8 A0 H5 a" w) Q; E" F/ q
& L; P/ B# f& s1 |- Z8 R- D先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
! r: I' j) }5 X3 [
代码

1 _1 G/ Q- G2 ^4 _# U) `; l4 p- p#include "stdio.h"
2 y$ x7 C# a& Y7 T, T
typedef int ElemType;

void ShellSort(ElemType a[],int n){
    int j;
$ i( Y6 S* V: t* Y- j    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
" H3 G) J2 j- V2 r        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
8 f* ~9 Y+ `9 v5 z* i3 q            if (a<a[i-dk]){
6 s& B+ t+ D$ N% d6 Z* p# ]                a[0]=a;
. K9 D7 [' y$ v                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
                    a[j+dk]=a[j];
                a[j+dk]=a[0];
4 W, @( C3 s# u            }
        }
    }
}
  i/ }: k" I4 q$ z  h1 q& s) y  k
9 t( P6 ^( z  [int main(){
+ `# ^5 r# {$ C( e& s    int n;
: L  U9 n9 L8 l$ q6 L4 x9 [    ElemType a[n];
    printf("一共有多少个数需要排序：");
7 w& u: a! d+ d5 L3 N! m! V    scanf("%d",&n);
4 B& k# n1 U& ~# v1 I/ q8 w    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
: I6 B3 `( K; v4 y7 o) \        scanf("%d",&a);
    }
    printf("排序后为：");
    ShellSort(a,n);

    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
9 [" `, c  N4 U, ?+ |7 @3 n}
* \- c; P- O( d0 j
1
) [. [; b. Y, b! j3 M4 ]8 [2
3
, Z$ \  E* r. w; h! ]4
5
6
7
, l5 _2 p* t; N$ ?8 T8
9
. x$ u* w  f) ^* h! r10
11
12
( v  j) ]9 F; B: S13
! ?4 f; M0 V' m& T14
% d4 T- |- s' N3 @, e; e15
16
17
' Q4 h, v  i2 z& Q0 R& {# d18
& A, b$ h; i* w  k+ C- e19
20
21
% M. g' t5 f# s; [2 Z1 U8 R22
23
( G, c4 u+ x! |) |' X3 B24
25
  L$ Q5 \2 ^" r, S/ v26
5 \: ]: X% m- |( f' Q27
9 [$ C% E8 ?; I) B) Z/ u3 O28
29
30
% q9 m9 i& Q" A7 m( p31
6 M& g7 D& p) V1 T1 R$ q, ?% C  F32
33
34
  V+ J  M* e( L1 P性能
" V* [  x  {( U5 x$ k
  O# y; m0 e$ U空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
6 c, k$ O8 f! ?) L  c5 E
时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
  M' h6 @7 p% v- x+ `8 e1.3
)，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
2
)

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


/ D; R( J0 P, d! ]: O4 q: I$ w& P适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。

) L; U6 Z4 K/ b8 M- i2. 交换排序
% R8 X% B8 N, r9 W+ }2.1 冒泡排序
$ ?- s4 o5 O/ ^& `4 X  z6 G/ y: C图解

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

代码
0 T& c+ z3 t( R9 t# s' N
9 ?5 f! e7 l9 f9 E: G) e方法一：将最大元素交换到待排序列的最后一个位置
. H# G) I- z5 X% O/ j
#include "stdio.h"
- A! J0 O& a% N. m
typedef int ElemType;
' p2 O- E3 e8 x( m) n2 c4 o/ f4 {
8 m, j1 i9 V* ivoid BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
        flag= false;
        for (int j = 0; j < n-i-1; ++j) {
            if (a[j]>a[j+1]){
( E) I! c; M( g1 w                int temp=a[j];
* Y( P5 }1 u* i6 T3 h( S; a. U- o                a[j]=a[j+1];
                a[j+1]=temp;
                flag=true;
% q& X& V0 Y$ @# Q            }
        }
        if (!flag)
( U) |$ H4 k1 x1 \! b7 [            return;
    }
}
  |4 z2 c, K$ M+ |0 E

6 K3 B4 U6 g7 L5 Pint main(){
    int n;
    ElemType a[n];
4 {  `. G" r. e    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
& W# v8 {+ e! L    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
    BubbleSort(a,n);
. g  R9 [1 f; l2 x5 c    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
}

1
# ?* a, X2 R+ H, ~1 s+ R) f1 s2
3
3 ?" d4 v+ o' C3 [4
5
2 p1 h2 B4 r! E$ t  S* A8 T6
2 D7 ^7 S0 n8 B9 `; ~* P7
8
* z4 u; H& r  o/ D! v% B5 U; u2 V4 G9
6 Y; @& V% M8 F) t10
# h$ I6 J  S* [% o11
12
13
14
1 q; ~/ V7 Q: f  M5 ~/ o' k% {15
; |; H" m: ^2 w1 F& \( ^/ j- j6 I; ?16
7 Y- C+ F- i+ ~17
18
19
20
21
22
, D$ r" L$ ^  M6 p" @+ R% a" ?23
$ D# n! X+ b5 ~5 F24
6 K2 r( Q6 ^* W% [5 k25
; s0 k1 M4 ~( f5 I26
27
; j! j- F. t" F# @& S28
29
30
31
. c, Q. W+ P- B( u32
33
; h3 S  j9 v/ G  N34
+ n1 V4 a' R% u3 k- \35
36
- R4 U. P) h! f9 ]5 A  Q37
, ~" y- R$ M  y6 Y. m' s" k' ?运行截图：
0 l$ G( L  P0 O
$ L% F: c# ~6 _, E: U7 B: ~
2 n+ w( A: f% U1 I8 N方法二：将最小元素交换到待排序列的第一个位置
$ t% k# n+ \5 a
#include "stdio.h"
' N  u$ V) T2 b/ J2 A0 G7 C3 }. Y; ^
typedef int ElemType;
4 F: E; Y+ R- d9 D' G9 F; k+ K
( `5 W: Q; k  K8 R9 nvoid BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
        flag= false;
        for (int j = n-1; j >i; --j) {
- \! I! T  K6 u$ i& C6 z9 W, ?$ J            if (a[j-1]>a[j]){
! x0 P5 [' K& B1 }1 A2 D2 D! |                int temp=a[j];
                a[j]=a[j-1];
' O% J$ ?6 p2 @# b. L                a[j-1]=temp;
$ P6 x2 r: \9 b                flag=true;
8 o$ Z" b4 Q! e( M            }
        }
& s9 w, m+ v! t6 W7 Z% u/ k8 c: \        if (!flag)
, e" A* m, S/ F            return;
    }
* f5 Z3 y7 d: `4 `9 e' Z}

5 R3 F5 g6 _" T# _* v
. x" E* B( ~) K- }8 kint main(){
9 ?  j$ X0 V5 U9 ?' q- [7 w    int n;
& G6 z5 A  v. _, N4 G" ^    ElemType a[n];
5 o$ S5 r; o, t5 j7 {8 X' j8 l7 n    printf("一共有多少个数需要排序：");
2 V5 p" L) U7 U5 z    scanf("%d",&n);
' }! s! h  j7 j8 t7 s    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
; q- b+ l5 a2 M- N3 `4 S        scanf("%d",&a);
    }
: w& [6 e, @0 I" n. l1 E% v    printf("排序后为：");
) j; I) \7 s/ h8 W$ n    BubbleSort(a,n);
- i  l& X" i5 ]7 i& M    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
) ^. i6 L8 t8 x% Y  P$ R" {}

& A4 c: r) V. @; g9 ?, ~. h1
0 P' s0 W1 ?8 I  _7 ^% x2
3
4
5
9 i) E* q" N& c1 n5 R6
7
8
9
10
11
12
+ `6 V/ |' ~7 x; V! ~3 L13
" K7 ^: o4 }/ |! `14
15
16
* ^) c) Z& ]' i9 A2 q& d5 `; {17
18
19
20
21
0 K5 I# ]3 V- @22
* L! S+ y& e) p, f/ a23
24
. g  P( _* ^( m0 Q25
( }4 u. S7 F4 ^4 c+ d# K26
1 d3 D. \* ]/ J# m# _% e27
/ H! s3 X- M- {% f28
29
30
' m5 Q6 X4 Y4 {+ _31
32
33
8 ?  R& P  T5 O  N2 @, D; |34
35
36
37
: Y/ F+ a& x: E2 i, V4 U+ \) V运行截图：

6 m3 E- f$ o& Z  ^
6 Z. }# J! d& V( l* g% Q性能

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

时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
2
)；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
)；
( ~3 }" H) L4 V) @' _7 o
+ h, g( S) X8 H稳定性： 稳定
1 Z" A: M- C. B# f( a) P
适用性: 适用于线性表为顺序存储和链式存储。

1 R* t1 w6 N& X6 X2.2 快速排序
图解（动图以后再补）
第一趟的排序：
. l) u7 j1 k: N2 R6 m1 R
/ \2 X+ i( Z" {6 ]& u4 t第二趟：

* L" C. j8 O; V" e4 h/ G& @% _第三趟：


基本思想
* _" T- I$ M, G4 F" u
# M: t6 Z6 P0 I快速排序的基本思想是基于分治法的:
' j& o8 u' Z* S" `4 A& B; f
在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
; d: B5 m" d! t8 F( |4 i  b通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
代码

# U$ j4 R) a% {, @2 p$ J9 x6 m#include "stdio.h"

typedef int ElemType;
5 q6 `/ M5 w* s) ?) f
6 L: \/ @7 v4 i' y# p4 X0 k2 M" Wint Partition(ElemType a[],int low,int high){
    ElemType pivot=a[low];
2 v3 d6 ?% S$ F1 H' b. H. k- @( W% B    while(low<high){
        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
        while (low<high&&a[low]<=pivot) ++low;
        a[high]=a[low];
5 O5 o* }* a  D# d& A8 Y7 J; u    }
, ]8 m. W$ @2 B4 P    a[low]=pivot;
    return low;
1 \, L7 y$ {+ p, ^8 _}

void QuickSort(ElemType a[],int low,int high){
" n% Q* N8 y! V; a  L& W    bool flag;
    if (low<high){
        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
4 s2 \5 D" p# b/ @7 Y        QuickSort(a,pivotpos+1,high);
    }
}
5 I; c. p% c( s8 Z, E
int main(){
    int n;
: c+ \0 d/ J; G8 ?7 B( \2 h    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
3 q0 h# [8 F/ u5 R    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
7 Y" d9 [: ~9 U: u1 n: ]& E* E) v8 m$ o4 W        printf("%d  ",a);
    }
1 j4 y7 H/ ?' J}
# Y9 y3 R' O" g" b5 h8 H
5 a. Q( b7 y' s" j
& M) i$ @% |$ s# ^7 L1
: o6 j, D) r7 I8 [3 j2
3
0 v3 c+ C1 b5 s" @* G4
5
4 S' K; {' @1 u/ Q. u, l/ V6
, J0 ?: N4 c' O; L+ H7
* _$ T5 O2 c2 I& ]# P9 \8
$ f2 U0 h; q2 ^( z8 F+ _* r9
10
11
12
13
14
0 {4 Y9 X6 i2 E( `$ @7 @15
& z) I  a4 Y) U! V16
1 f" S8 W- {8 Z17
18
$ T% D7 F( l( J2 ]; C19
8 n  i0 X+ f- u8 U% i  j. G* ?/ S' y20
' W; e) |8 ?0 }; e' R0 U! F21
22
23
; T+ D, ?: E# s3 w24
25
5 h2 }4 X# Y; @& Z8 ^26
' ~' V0 E4 ]3 O27
8 |" F, }6 u% N# A5 q* B28
29
30
( T5 ?( p  I* A+ G! C, g1 z31
/ q' b( [7 h5 u4 t' @* ]8 H32
33
34
35
36
37
! o1 U* n2 F) K" j38
39
40
41
性能
2 g* p0 Q9 F; F! ]5 B. v$ M
时间复杂度和空间复杂度
稳定性：不稳定
7 t+ B8 [- K" x8 N; ~1 d' o
) k9 Q( v: e  [  Q! H; j, l/ u! y3. 选择排序
4 m3 D( v7 k; `6 e) r' p; ^3.1 简单选择排序
图解

9 R7 o  @1 s) y7 a0 ]8 n
基本思想
; q/ u3 b# c# K2 ~
在a[0…n-1]中，将a[0]设为最小元素，设min=0
在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
6 L( j4 n- }0 P若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
在a[1…n-1]中继续进行排序。
代码
' g( E2 W9 A2 l/ {0 @
* X+ ~. m% c0 P0 Q0 O#include "stdio.h"

' |6 N7 y6 S$ G* u7 t* ctypedef int ElemType;
1 {' m. r; |8 B" B( E0 A, S
! s# P# F* s: B/ N3 W8 ~& ~$ `$ u+ }! avoid SelectSort(ElemType a[],int n){
    for (int i = 0; i < n-1; ++i) {
        int min=i;
        for (int j = i+1; j < n; ++j)
+ H) u# `# R: O5 h7 a            if (a[j]<a[min])
3 P. ^9 c: D% n                min=j;
3 i: y: \+ a- {        if (min!=i){
4 E$ w3 T* r/ {  O& T2 v1 `            int temp=a[min];
            a[min]=a;
            a=temp;
# A/ _4 O6 L9 E. n2 l; {' {        }
    }
}
( B3 H" J% U5 N# n* r# S
int main(){
    int n;
& F  d0 t. p/ b5 a    ElemType a[n];
: ?9 N' T. T9 q* e: @    printf("一共有多少个数需要排序：");
, X7 M% ^$ @4 u* x* b8 r    scanf("%d",&n);
    printf("请输入%d个数：",n);
8 k3 q5 S9 ^  E/ Q    for (int i = 0; i < n; ++i) {
: {) E: z% W6 l7 ]' F! X6 K        scanf("%d",&a);
    }
    SelectSort(a,n);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
( w( y! j: v# O* }7 g7 p6 H    }
  a. h% K, p9 m. d# P( c}

5 I: _' {5 z5 }1
$ R& J8 ?$ q0 [2
- r1 Z  p' G9 a4 Q3
4
' }$ w3 ~0 B6 C+ P6 X5
$ r+ g2 e/ |5 a: A$ d6
) l2 E$ w, M/ `. B7
8
9
1 J- J. r# {% ~9 H5 h# N4 t/ y10
- k; d7 _2 t. h7 q; r$ e' m11
12
' H% y9 `; d, w: x% o7 u13
14
15
16
17
: @% @0 ~! C" A; v2 Q18
19
20
21
22
" F# u/ H! ^8 m3 W& B% F23
24
25
26
( b9 J6 ]7 E2 m2 S. _0 v0 t27
28
" q' l1 {4 d, c6 _9 c0 `29
30
$ m. B5 M: ]: l7 `1 Z3 `4 t31
  r& s9 `2 ^7 Q' p- h; b32
/ v* J5 B* A3 U2 o33
性能

3 z6 p. @8 q0 a3 |6 {$ ]; E* n  }空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
) v3 Z  q% j* @2
)
- I5 u; x0 s6 Q0 W* Y! _稳定性： 不稳定
6 ^- q: w- X+ F7 f& A& x( l
" a3 ~3 D6 V1 k0 V! s使用性：顺序表和链表都适用。

7 n( F* X: `, T2 g' }% J9 I7 }/ }$ M% H: ~3.2 堆排序
7 N  W# }/ d- j( J& b# K2 U1 Y看堆排序的点击这里！！！！
- L1 {- i& L8 }3 X2 P# j5 t
4. 归并排序和基数排序
4.1 归并排序
' A3 J1 ^1 E  C2 x/ y+ Z图解
- G) z3 h4 e* B# N  W! i9 W) N  B2路归并排序

, f. C6 p4 t! @( `/ b& n6 Q
基本思想
6 m; R8 d2 U+ e/ j5 X& u' @
将待排序列分成长度为1的子表，然后两两归并，形成有序子表

然后将子表再次进行归并，直到子表的长度=待排序表的长度。
代码
) l/ J2 A+ n  T8 I+ `, a
0 n" S! F# r: S! f# a; B#include "stdio.h"
  A/ W  Q0 T; v. I#include "stdlib.h"

1 ~8 z4 I8 K& V6 itypedef int ElemType;
' F0 a# o9 \# N5 M) C7 p7 _
ElemType *b;
! f$ g& D& q1 ]9 m( a# h# v5 k
void Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
: K0 ]! {8 \# }) ~) y( R5 K    for (int k = low; k <= high; ++k) {
        b[k]=a[k];
- Z2 p% P5 y4 n1 r    }
8 }: w# r" o+ h" m    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
' ?" T5 ?, f/ ^        if (b<=b[j])  a[k]=b[i++];
        else a[k]=b[j++];
    }
1 u. r  V" P% R  J# \) ?! Z& }1 }9 P* s    while (i<=mid) a[k++]=b[i++];
0 r6 f* c4 H; z7 e# D: N, D7 c    while (j<=high) a[k++]=b[j++];
}

' H3 C/ ^: c/ C. I1 Z$ \void MergeSort(ElemType a[],int low,int high){
    if(low<high){
/ m( W# [6 [/ \9 M2 c1 E5 l( n        int mid=(low+high)/2;
" ?( i4 q0 i, k: E        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
}
, c4 P2 b5 \. Q4 m! e( h2 @& W
! U0 v. q7 d- l* C7 [- Tint main(){
4 G, w7 S' Y6 h/ e3 h  G    int n;
    ElemType a[n];
    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
# ?; y( _( o; J# K$ `1 \! X7 u    printf("请输入%d个数：",n);
* f7 U3 |1 ?$ P( J  }% P2 v: F    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
# h$ T8 [4 }9 L( j. ~* E, k# D    }
    MergeSort(a,0,n-1);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
" A  B9 T* f+ b    }
}
- H- b/ m4 o) |) }- d
' N" T( m! }. Q5 x/ ]
& X; E; W1 G6 V2 j/ F& C6 V# [  V1
  I* Q  \  E) L2
3
4
2 d' _, ^3 _) b9 q6 _5
6
6 V" ~/ [, W  F" d0 n5 c' V( y, D7
8
0 d/ ?& H7 [7 ]4 y$ v, ~% @1 @9
6 M! S9 c3 J+ W8 R' g( Y10
' U9 a% \- {& N6 P3 _2 n8 ~11
12
( q! n1 R3 m2 j  \1 P2 r2 k1 i13
14
5 s: b' u. r1 o% b" h$ _; c15
16
# i- x( ?. y( e1 X4 h+ z9 s, p: z17
18
( U; `: K. [+ y9 {19
3 n! w; v) {3 y8 P, L& i20
! }% u4 ?7 i: Z( p0 J1 o21
22
23
24
& o) N' c' X0 ?- d25
26
/ ?$ B8 ]7 s  t" |) P6 ]9 c27
  y7 I& y- t% z( c1 P0 d# M" }28
29
30
2 @6 O/ W  {4 w31
* }  `. s4 m. F7 U32
- F  U6 p- y6 I& h; D1 `33
34
7 ]  @9 ^1 p8 Q8 m( ?# U35
36
37
38
8 C6 s' x. T2 P2 v& g1 f! a% M2 l8 Y; n39
* k/ a4 G0 ?" w$ b. C40
41
; D# E) x3 L' g' q) Z( y42
; ~+ ~& j) F# e. L43
3 J! K' O/ I5 ^! }5 n) _3 a44
9 i/ c& @$ n# x( E3 M45
$ T# M( M% Z" \; R6 G0 G46
性能

5 W- x/ b4 s1 Z+ v3 ?空间效率：O ( n ) O(n)O(n)      创建了一个数组b
1 P0 d) o, ?$ S$ G6 Z* d时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
  L3 A: h$ ^# `# p. v0 O+ c# p​
6 u, C: f$ A3 i; E0 H+ h n)  k指k路归并排序。
稳定性：稳定

4.2 基数排序
图解
2 p! J+ g9 q. W

* U4 L% e7 U1 k6 q' n基本思想
- d" C" l) Y( X" X7 E
1 b+ Q3 }3 F2 Y  \将各个位数（个位、十位、百位…）进行对比。
为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
8 k+ W; ]0 l9 a' t( J) J
性能
( ]* X5 W. Z4 x" v! [- w7 n5 q
& ~/ ?1 S9 t- g: t  A+ e空间复杂度

时间复杂度

# Q. H& \  k0 }; t9 z& x2 L- h
稳定性：稳定

, i* g8 y* z+ Z6 {2 l; u6 ~$ b, K5. 内部排序算法比较及应用
5.1 整体比较

4 z% t5 A! u9 F
5.2 时间、空间和稳定性


, L4 \. ?" z9 y$ L  M参考资料
《王道：23数据结构考研复习资料》
* E  {5 x3 _& X) R3 ^' \9 R————————————————
版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" {) |/ \, q. c/ Q4 y% U# G原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678


# W0 Q+ ~; ^0 E. t1 y) [6 D" i