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

杨利霞

数据结构：九种内部排序（动图+完整代码）
+ B0 X0 ~0 Y& X* }5 O: I
排序
) D# E' k. V, ~) ^3 @1. 插入排序
1.1 直接插入排序
' q2 g0 {/ T2 |+ ^9 J- q- J1.2 折半插入排序
0 V, k% |7 ?1 U3 p4 |- i5 A$ N6 x1.3 希尔排序
- k* i8 ]/ \! p' P( q2. 交换排序
2.1 冒泡排序
2.2 快速排序
8 q" r. C7 r! v0 Y- |: b; ~5 R3. 选择排序
3.1 简单选择排序
) k, T$ n- Y4 E' [  y3.2 堆排序
4. 归并排序和基数排序
/ f! F) R/ j* p4 x  x7 w4 |, }4.1 归并排序
4.2 基数排序
- m% f0 Q& r/ X4 O0 Z& @) G5. 内部排序算法比较及应用
5.1 整体比较
5.2 时间、空间和稳定性
参考资料

内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
1. 插入排序
# |$ `* C( q; a" F9 \# @" W1.1 直接插入排序
图解
  D" O$ N5 T9 Z/ ~# a& ?

基本思想

1. 查找a元素在第1 ~ i-1中的位置k
# K7 m# M0 ?0 p3 Z2 b6 h2. 将k ~ i-1位置上的所有元素向后移动一个位置
5 _: l# _  r& B: [0 H0 }4 P. `7 P3. 将a复制到a[k]
" P" e: ]3 V& L
3 M( C- P6 t0 q. I( u$ _  P
% I- }  {. k0 D: O% f; V9 A
代码

方法一：

数组的下标从0开始，如上图。
! Q" f# _# w6 \: t, o- r$ i
% F1 H/ }. r% S& {, w#include "stdio.h"

typedef int ElemType;

void Insert(ElemType a[],int n){
    ElemType temp;
- ^, s2 X6 A1 x, Q: q1 V    int j;
' s, E2 e( F7 ~    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
9 w' m( ]! ^5 T* E4 s- v! v        if (a<a[i-1]){
9 Y5 h7 Y2 r6 Q4 j& u  h            temp=a;                                                               
1 m- ~' a) i7 U$ i/ h& I! p            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
8 \& Z4 J2 e" I0 m# u7 s                a[j+1]=a[j];
; Y3 Q6 ]4 f* q6 z: s$ _8 \6 @            a[j+1]=temp;                                                       
        }
    }
}

; V  X4 {' X& \' o) Uint main(){
    int n;
. c& S4 A+ i' S; H: t    ElemType a[n];
: ?" a/ {/ s( r' s# M! k, w2 e6 t    printf("一共有多少个数需要排序：");
' @: r6 T' Q# [    scanf("%d",&n);
    printf("请输入%d个数：",n);
" k  z3 B  m" A! g' D1 h    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
! I3 P  i- U! m2 r+ _; }    Insert(a,n);
4 b- Y$ D" f$ K- c' {8 u    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
- h3 e+ n% ~' u5 \6 m, X/ J7 Z8 i    }
}

8 v/ F& \( @8 P( J3 O: c3 j; l* W0 t1
& k/ f9 x- i8 \2
1 D; B; h* v7 G% D7 A" d# Z3
  x* A' x: m  }2 k' \4
5
6
  l% e( g1 }4 g2 N7
; x! \. B/ W2 Y2 m: ]2 E8
: G* e* c3 B2 m4 u' q- X9
* B& l9 d* }5 l8 O3 T' o10
11
, F3 i% }" B) ]3 W0 W* H" O; ?+ n7 p12
. k9 O# j5 _& c5 C+ C7 X. W) p13
) N( b8 B4 b8 r# F2 d8 ?" O( W) ?2 U14
15
8 I: ~3 g  A, X: z16
17
5 i% U" f  f1 c5 h18
19
20
+ u% |# ]) r% z5 l& j7 @0 @21
22
, X0 n/ J# D! ^% W23
) R2 {+ t: X+ F24
; C7 @4 b! G7 u$ n4 U: g3 K25
26
0 y: j7 k2 d6 Y  L27
7 R/ h9 {2 e7 I28
/ a' a% q, s( v7 x1 c29
# j0 s# i& @* f6 ~0 O/ I30
5 d) @3 a' C0 w31
32
方法二：
* ?, h& Z2 T/ H2 g
) Q2 I. z7 {% ?: k4 \9 [5 t
2 Q1 }7 u; r/ H7 i3 `4 B( c! W/ _
#include "stdio.h"
3 a4 E0 F' z! D' ]! f- m( G
typedef int ElemType;

: W- D8 _0 o5 Wvoid InsertSort(ElemType a[],int n){      
    int i,j;
/ s" f4 k, u  Z4 m7 Q    for (i = 2; i <=n; i++) {
) y; ^$ C  u% K' s        if (a<a[i-1]){
            a[0]=a;
  [( ?. m) U6 X+ M1 Q            for (j = i-1; a[0]<a[j]; --j)
% }3 w  ^2 u8 o2 P' b) O. D                a[j+1]=a[j];
            a[j+1]=a[0];
        }
    }
+ T' J5 d0 R8 c& F9 Y- A}
" N2 @# n# [) \int main(){
4 G5 f# b6 _- ~# I0 N    int n;
& F( a+ [5 Q; B% e% L* l    ElemType a[n];
4 ?8 E) \8 w" @& t1 c' s    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
# Q2 x/ K  G2 q, |* k1 A    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
* ~7 X2 r1 r1 y0 K$ n$ [    }
    InsertSort(a,n);
7 k) ~/ s2 u/ ]7 e1 I8 T    printf("排序后为：");
1 K$ |0 T9 [/ E' V) J" Q: R- p/ Z    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
! l3 ~# k4 _7 J* h, Y% Y* t! a}
& ]. L7 A" Q3 p* n( p# t7 Y
1
2
3
9 G% x4 m3 V, Y$ Z4
5
! f( g) `, |6 A4 T6 b" D9 l! Y6
& o8 Z. {& s, V. p6 w7
8
9
) s2 z2 |1 \" _7 e1 q  Q10
11
, i+ h" n1 C- w12
5 H$ Z8 X* Q% ^8 e13
14
  t' c$ f/ k& U: t4 y15
9 z- @1 @1 R0 a3 h8 y" A7 }# I16
17
18
4 ?1 F! r7 H- B19
+ @( z. F0 `# h( h20
) g& f8 P6 s$ m4 ^5 L, {21
/ M( X& A9 l# M22
23
24
3 v5 ^; i5 q" |25
26
8 ]) R/ |; j1 }3 n27
/ r& _  b, x/ g* H* ^28
29
30
* {  I* z( U7 U算法性能

! j1 e! n& d. c6 G6 R: W% a# |空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)

6 D  a3 u: r) ~! ]时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
+ R7 A1 P3 H0 O' l* u )

' s. Y3 t  [) k/ q2 R  ^! t
9 u( S$ u: Z# w稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
( C" R+ X, H. ^1 O4 ~$ j" @" e
5 R/ {7 q" U+ t- K9 S9 p适用性： 适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

/ h" t/ u8 R; m$ A% M3 Q1.2 折半插入排序
, |# V8 L- v. J2 K' c3 n/ x; E- f图解
第一趟：

, W. T4 i4 _$ c5 }2 m: I9 h第二趟：

) Y5 z* K: R2 P
第三趟：
9 n2 [6 y% q2 w/ R2 s: q3 f4 t
3 z" H. T2 l4 _  m  ~第四趟：略
; o: I+ N1 J! D' q6 x7 C' d9 J& x第五趟：略
7 |, Z* U) \3 J* \, d" [4 q4 ]
( V2 S- g6 |1 {& h' H3 b8 \基本思想
1 V3 [: r) S. Y% N- ?
与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
+ @% w9 ]) y) k9 o; E取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
1 H; \9 t* L, d$ l; m* D找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
9 c( D: f* s" h. M+ a4 ^代码

: \, V0 ~/ r6 @$ B2 X: y3 g#include "stdio.h"

8 [' I+ |% {& k( H: ]; z& Jtypedef int ElemType;
( `8 X; V) y3 b# f0 @& k& S8 _: E
* U5 u& S/ m, q; U* _2 |void InsertSort(ElemType a[],int n){
    int low,hight,mid;
    for (int i = 2; i <= n; ++i) {
        a[0]=a;
3 C" y* G; T' {* h, O        low=1;hight=i-1;
        while (low<=hight){
8 }7 x' z' Z  F9 l: |# T            mid=(low+hight)/2;
; j6 ?8 b. `4 n            if (a[mid]>a[0])hight=mid-1;
/ `9 f# {* [: S: O* f            else low=mid+1;
        }
        for (int j = i-1; j >= hight+1 ; --j)
5 r, V/ }' \0 Z3 x            a[j+1]=a[j];
        a[hight+1]=a[0];
    }
}

8 x6 W' q8 n& V/ h9 p
" z2 m9 i) R5 X: Q2 k7 n* E8 i" A* cint main(){
    int n;
4 K' V' x0 \# @: y' Q" y/ S1 L8 `    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
  _$ b) u8 |3 a/ p$ m    for (int i = 1; i <= n; ++i) {
. i  O1 c* t- ]8 c% q6 b. {        scanf("%d",&a);
9 C2 Z8 Y7 o$ a! {/ {) i% ~- g) y    }
7 [7 V2 U6 @% X+ j- h; N    printf("排序后为：");
6 R/ y+ \3 k, L& o    InsertSort(a,n);
4 }% r- d, x, ~, }
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
0 r$ a% A. M( u5 N* @, c  D    }
}
7 j# w! Z0 J9 }$ G8 V/ V# k$ x9 b
1
2
3
1 f2 g# L" }6 h( J! `1 ~4
9 @# t+ N3 o5 D. @' H- S5
6
7
- d8 {! }1 L4 m/ Q# ^8
' g! N: A; t" r7 W9
' e  w4 ?9 m! _# t" @) s1 W& _10
: \. {8 f1 @4 x0 [: c11
6 c/ x2 D9 K1 ^+ D12
13
( V- a" i3 {4 X4 o; p# a8 q( P14
8 U0 G6 ^* F2 }$ m$ H15
0 i5 `8 D  Q- C16
17
18
19
20
21
22
2 a; M$ M' p* A2 b8 A23
4 W$ N4 _9 u, j" f4 ^24
$ W9 W- f  l5 \9 D1 ^. d- c5 D; y  J25
9 M. n/ ?% c; P! E& A26
27
! @' |- w8 h4 D: i! X, ]28
29
$ Y1 Q, @# t- z- @# V30
31
9 f9 i1 e* j/ u1 Y/ A32
33
34
35
: }+ L6 E9 e! |0 r% |# @36
37
+ J: b% V, _9 z性能

  x/ A% l* Y4 Z空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
2
)
; d; L" q* @# O& u8 O) i: @稳定性：稳定
, r  S3 F5 i9 D4 N7 q; N) N适用性：仅适用于顺序表

. K5 w+ Z" a5 Y- H, c& Y% k7 j1.3 希尔排序
* w+ s* x. Y8 e& l9 Q+ |+ q图解(动图)

4 V$ S/ e* L; k+ j
2 B4 H$ C$ c5 Q( F+ c, K' }基本思想

先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
5 s" S, m# Z, D9 V) b, h/ [/ u$ Z. b; F0 g
( y! T% M! k+ ~8 f6 w1 q代码

: v8 b; X% w" Q* \! _#include "stdio.h"
9 p3 q1 V5 i" w8 ^
typedef int ElemType;
3 B3 u  H) U8 w  Y
void ShellSort(ElemType a[],int n){
    int j;
    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
            if (a<a[i-dk]){
                a[0]=a;
                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
8 d2 w$ p% y) O- A6 R+ X+ e                    a[j+dk]=a[j];
                a[j+dk]=a[0];
" x( ?1 G$ D; J            }
! B: l9 T) g8 |+ O        }
    }
7 L" P& w  X4 [( K3 \! Z}

, l/ b0 Z- }+ g+ l8 u1 k4 M9 G5 Bint main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
! S: B4 M5 V# t, l1 C( |7 V; U    scanf("%d",&n);
( u7 u' h9 U+ I( E0 U    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
) d: B/ d. R  w% y        scanf("%d",&a);
+ w& Z7 M- w% |" ?1 b4 O    }
    printf("排序后为：");
    ShellSort(a,n);
3 i7 d/ H! x0 _8 I" s
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
    }
6 I  H" {) R, ~. x$ G" ?0 Z}

1
: i& u. ?) b9 p8 J2
3
4
1 a2 F9 k, o) c: _5
6
7
8
* T9 V0 ?* p" U9 |9
10
11
0 T' r: P+ C3 t% A4 @  A& j12
13
  E2 W& c$ j8 G# }( s: d7 D6 C/ b# s14
! b* I0 F7 a4 \15
16
17
18
* I, a( \0 Y& }: W! C8 P- b19
2 b& n* z" ~& @% X& W20
- G" W4 P' b7 x2 _. }6 M6 {21
22
23
: |* l% P2 }  R' y1 l0 R24
1 ?1 _: v" `) N1 b3 h! o7 `25
26
27
9 v3 K; z3 I- @, `5 m28
29
30
9 @8 n& n% w7 N2 s! F8 M31
8 s% Z& d# \; O' B6 F2 V( z$ K32
3 N9 u" i# c5 c33
- O( L: {5 M  f7 r' s! K3 _34
- x% G+ ]( L" Q4 G4 i+ h' l性能

$ F! g7 z4 {0 V- V( A9 J0 E空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
0 H6 i" {8 B! o) T; x7 |1.3
8 j1 ^2 ]3 b8 u- g1 e  J5 m8 \# K' ^ )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
2
)
9 E; ^  }; w* }- f) p; K6 d! N
稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
5 T  A8 V4 ^6 d$ W! {' b9 s
: i9 v7 n; w4 ?# g% W' u+ _  M
适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。

2. 交换排序
* ]; Y! p0 _& a+ T2.1 冒泡排序
图解
) d7 t4 T6 @. ]4 j

0 p1 [/ `1 L3 ?3 m; i' {基本思想

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

+ C3 k" M! k$ A4 E, q2 ]) F$ Z9 z代码
7 }3 b& B: t% t6 q2 g9 M# a) {
方法一：将最大元素交换到待排序列的最后一个位置

#include "stdio.h"
2 X0 E8 {9 L' {
9 ]: S6 D5 w$ U) k8 Utypedef int ElemType;

# S& t! |  B) e9 Qvoid BubbleSort(ElemType a[],int n){
    bool flag;
8 _7 K% V' s8 E7 `2 U4 C    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]){
* }# C) l( e" m  p                int temp=a[j];
. z6 c4 b: B5 @& s( B* r                a[j]=a[j+1];
# B6 V* S" }% d7 y                a[j+1]=temp;
: s5 R' V" t% U6 Q3 p                flag=true;
. X: D% U  P( h! @# G2 p7 H            }
# C& d4 y$ A, t) F( j! i        }
! \- _2 E% k: s. S, d" c! g        if (!flag)
+ I! o1 K, }& f- b2 ]$ a$ ~            return;
    }
}


int main(){
" R7 m7 T9 h6 m3 D4 e( H    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
3 s1 b7 J, F4 @2 G, D8 `( u    printf("请输入%d个数：",n);
; Y( j, @4 n; o; r    for (int i = 0; i < n; ++i) {
3 L/ `3 @9 ]! ^1 }( z( k; ]        scanf("%d",&a);
1 g6 H7 L- k" V# P    }
. i9 s6 G, ^/ X1 r    printf("排序后为：");
    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
+ n* W" J1 r% b/ ?2 e        printf("%d\t",a);
    }
}
1 e% x3 ?! Z0 I$ v) l( M. q# c
1
2
) u8 u6 n3 N$ l: P- d3
4
2 u# [/ R7 W2 R2 r  R4 @5
% f1 Q) y9 w. V) E, c6
7
8
0 e- b' q& K2 [' w( m! a9
5 S# k8 l2 w; B) l+ Y* V+ k3 l; @10
9 t+ U- d) n/ |$ l6 [11
  I& P& P  H5 c/ B6 o% U4 p12
13
14
% v8 X3 X2 n9 W: U, F& r15
4 m5 N) L: |& t0 n4 ^' j16
17
1 J# D& x/ \, T$ H/ l) U18
19
3 ~$ b" N5 ?& A7 f. m, \. T20
+ }; K8 \+ m5 U7 c21
22
- }! E1 O0 C* _8 b/ z23
24
3 X# D2 S2 \' n% H# r" I25
26
27
( T: r8 R5 {! W# T28
29
30
4 |. m* M" T" J8 g( v" X! F31
2 U8 |/ ~6 Z6 H5 z/ e  |/ F, U32
33
  {, A& H" x& c& T- v) I1 B8 }" e34
35
36
37
运行截图：


! p+ H& ]  n. K方法二：将最小元素交换到待排序列的第一个位置
! n8 y8 L4 n' o6 ~6 ~7 _
1 C3 p' O* L5 j* s& g7 H2 @# l#include "stdio.h"
$ Z4 a" Z( g, p' }1 I
* d; T7 b3 o" |& K1 }& d; x0 _* z0 Vtypedef int ElemType;
% [% H. K) g; l# ~/ _8 ?; C
void BubbleSort(ElemType a[],int n){
/ @9 U0 D* r8 f% j    bool flag;
) H. p+ D" E$ \' p- T0 u    for (int i = 0; i < n-1; ++i) {
        flag= false;
        for (int j = n-1; j >i; --j) {
            if (a[j-1]>a[j]){
( T* E( ~* l! Y' @! u- k2 \9 X                int temp=a[j];
1 o( Y, \7 ?0 W8 h# k                a[j]=a[j-1];
                a[j-1]=temp;
                flag=true;
            }
        }
; k5 Q4 ~9 D" A- j5 \        if (!flag)
& j( q) x' E- n; a. R! }            return;
    }
- C4 t* T/ V  H2 x3 s}

. Z) }! M. D( T' O+ b5 |, C
int main(){
% }! s. Q5 L0 O0 k9 B: d    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
* U. |" ~! g% o5 I7 [9 r    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
1 Z. {* E0 z0 F. W* F1 H        scanf("%d",&a);
& Q! T8 D9 B1 C/ H1 Q, z    }
# {/ Z( @  M4 S3 B7 X7 ~/ G    printf("排序后为：");
    BubbleSort(a,n);
# A* B/ n9 |1 H7 V* g/ a    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
    }
& c* d' ~" D) @4 j- L$ w* I/ V9 U}

1
2
3
! L& l& L7 {& @: ^4
5
6
% Y+ j1 o$ o) @8 M7 v9 j7
8
9
10
11
9 K7 E2 q6 c, n9 X12
+ N* A9 J% V$ V# K! K4 l13
14
  [4 X; [$ D9 o' R4 u+ c1 \3 z6 }15
16
6 q, Q6 h# j* P7 C  m. d17
18
19
$ c3 @' x- g3 ?7 Y5 |' Q20
21
22
! o8 [% m8 ^" T$ v2 S, P23
24
25
( q# N! ]7 y' B* ^& x  L26
27
28
29
30
3 m( T# p" M2 Z, j) ]$ ^31
32
6 i! S2 v( ~: y6 s33
34
& c. I! Y& W$ x2 ?4 {& n# t35
/ r$ _0 _$ z9 P+ i! h$ P  X36
5 f7 d7 O5 a7 B5 y37
1 p8 i$ F; y5 y( Y运行截图：

- `4 j& ^; i1 c
7 M$ p' x) g/ [  s性能

8 w! Q/ V/ I& `空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
2
) u2 ]0 h9 A+ Z$ C$ Z* T) ^) Q )；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2 i* O6 N/ L: u' T" Y# n9 _6 f2
)；

稳定性： 稳定
# e$ p( D! a0 b1 ]% m
适用性: 适用于线性表为顺序存储和链式存储。

2 g3 B# q# y6 C! ]& x2.2 快速排序
( Z) Z( O$ v9 `+ }图解（动图以后再补）
第一趟的排序：

8 ~: B' D/ ]$ x  ?( C# W第二趟：

( U. F6 c5 Z1 x+ g第三趟：
, m* I' O3 L' `
, A2 t! D) N5 ~6 |
基本思想

快速排序的基本思想是基于分治法的:

在数组a[0…n-1]中选取pivot：a[0] 作为枢轴（或基准，通常取首元素)
' O' i# D8 j' m; b: x; X通过对比排序，将pivot元素放置在k位置上，a[0…k-1]<pivot<a[k+1…n-1]，完成第一趟排序。
' f' _# y) b# i" p然后分别递归，将a[0…k-1]、a[k+1…n-1]子表按照1、2步骤排序。直至所有元素排序完成。
代码

#include "stdio.h"

- J: {1 B6 C9 ktypedef int ElemType;

int Partition(ElemType a[],int low,int high){
    ElemType pivot=a[low];
7 u' I& x/ P8 e0 c: S" m, w6 P    while(low<high){
! N9 C6 ]4 k; e: T        while (low<high&&a[high]>=pivot)--high;
        a[low]=a[high];
$ o* D  x- H/ ?2 I5 \5 K        while (low<high&&a[low]<=pivot) ++low;
        a[high]=a[low];
    }
2 F+ z; B) U- f2 s' h    a[low]=pivot;
, `3 U6 D% L0 H2 n) \: I5 H+ C    return low;
}

( T- G& X+ Z0 _( V4 j% A) lvoid QuickSort(ElemType a[],int low,int high){
    bool flag;
8 s1 S) ^+ M0 f1 C9 o4 J  _    if (low<high){
        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
! z2 F) u, h! M    }
}
6 F! q7 r  Y! ?. [  G' _+ Q& t% W
, A8 Y) k6 m1 {1 gint main(){
    int n;
% l8 \! W, K4 {    ElemType a[n];
$ `8 Z( z5 n  K/ t& J/ ~    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
6 E3 |9 M+ A$ ~& t  S6 E    }
6 j9 v/ S1 q8 p" `. O3 }    printf("排序后为：");
3 A. s$ j8 [% p- m    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
+ x0 v* Q& l) ^# b& k9 s        printf("%d  ",a);
# {1 g- Z5 c  a7 h1 c2 {! |, W" N. q8 M    }
; l% z7 g# M; \( W. Y}

0 f9 S4 y6 d) T# V' t" m
9 w0 y: L" b$ P3 M( S" q, Q4 T1
+ W/ L' a6 u% }) x' A( c6 R2 h2
3
4
5
6
: a; l7 R: g+ |7
8
9
$ y5 X& i; X1 Z4 x8 G0 {# \10
- z5 Z" Z2 ]  R( q8 x, q3 x11
12
13
14
15
16
+ n! H: `( s! \5 W. W17
, x# b1 h1 l" N! V6 e  z3 A18
19
20
5 C6 P! k6 l6 D" `0 l- x. X! h21
! ~- g4 ?3 I; [8 {5 Q22
23
' |  {5 h5 F9 m5 P6 [- j- M24
25
26
$ i% h- C" n6 `: ]' C7 j27
28
, \" Q) N3 L/ m; E29
30
31
32
5 |; R% X: e- g% S& f: Z' W4 U33
; |1 X# a+ e# A! P3 K& A34
35
36
* n7 A5 F# ]3 I7 q5 W37
38
39
40
41
性能
8 Z5 L( r0 u0 ~0 F% b8 e
时间复杂度和空间复杂度
* n8 V: l# u$ n7 e稳定性：不稳定

3. 选择排序
2 s% n1 h5 v; c3 z- d4 z, E/ w3.1 简单选择排序
图解
/ f) l6 [9 h+ x# S; i5 F$ T

  Q% o) M7 r+ G. A9 H基本思想
& y7 \8 q* P, Q  `: N
在a[0…n-1]中，将a[0]设为最小元素，设min=0
/ N) v0 h6 @8 P8 z. h在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
在a[1…n-1]中继续进行排序。
% X3 `' c. ]) N) w3 l代码

#include "stdio.h"
; ~) F5 z& \) n) @1 k3 e
typedef int ElemType;
$ b) n0 K* _3 M- H
void SelectSort(ElemType a[],int n){
6 `# k* h( X% ]3 \  s* h    for (int i = 0; i < n-1; ++i) {
4 F% b) k# f. P8 g. w        int min=i;
        for (int j = i+1; j < n; ++j)
            if (a[j]<a[min])
                min=j;
3 n* K; q7 i" ]  A) m! d7 D        if (min!=i){
7 }  T' a  Z( R4 M# O2 Y            int temp=a[min];
            a[min]=a;
9 j4 F. A. `, l4 C4 M            a=temp;
& Q6 [& G$ O$ e& e4 W" L3 z        }
/ Y, [) x% ~( Q; y$ b0 {    }
5 |8 P- N8 E5 e5 B/ G8 V. C  C}
) _) v' I% ]( R5 s1 H; k
int main(){
    int n;
  f+ r+ v. [  Q4 i2 A, M0 A    ElemType a[n];
: }9 `7 f' A  o( u% R3 Y+ J    printf("一共有多少个数需要排序：");
  v  J5 a# g  {: k    scanf("%d",&n);
" o! A) l! Z0 B3 O( b% o. J    printf("请输入%d个数：",n);
7 u! {( m% D# k! v    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
3 x3 V5 [  S0 |, k) q6 ~8 {' B    }
  z6 r$ g8 K  j    SelectSort(a,n);
    printf("排序后为：");
* ?/ J+ T2 Q' e( R, V    for (int i = 0; i < n; ++i) {
1 v' u4 s+ n; j# v, g4 n7 m* a: r        printf("%d  ",a);
    }
}

* Q/ v6 K; l* S! h. `1
' V' F& x# \, Z0 B% f# y2
3
) g5 D" n8 G' {$ J+ }+ `* l4
5
6
  ^. }1 b8 o1 T7
/ l. R% c4 F' U. G0 S8
# ]* i8 K( }6 o( g5 D8 U9
10
) y- V, p3 k) L( p11
12
13
+ x5 G( A. V& R( H) Q14
( Q9 _5 W  n/ ^/ X% T; Y/ T15
# R2 o5 B1 k% B. s" f9 ?; o16
17
; ]) e( T$ }& c; E1 Q5 x  F! R18
19
20
# a! x$ [' s6 I5 Y7 y3 o7 a3 }21
22
0 y5 a& I* Z1 e. m3 y- X2 z. L+ D4 ^23
24
! F; h$ u5 A5 a) h7 e; U* G/ l- W# l( q25
# P9 q0 U9 v( d* {" {' w; k26
27
28
29
" Z4 x! W0 \* {) @! Z30
) S1 {$ [% c) n  ^/ d% M31
32
7 Z+ G# W0 f) a6 `& O& H6 j) [33
性能
8 |' M: G0 q! s# b
空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
8 R5 r# q3 ^* X) L% |2
5 j$ ~( ~! S- \% q6 U; z )
1 r, a% e" s5 {稳定性： 不稳定

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

3.2 堆排序
看堆排序的点击这里！！！！

4. 归并排序和基数排序
, _7 M! @6 q+ F4.1 归并排序
图解
2路归并排序
7 h# _- f0 M% n: t: d

$ d) o1 S: j1 ^0 O% }& T基本思想

  N0 k6 f. Q! G6 V% w- {' O! C2 q( i! ~将待排序列分成长度为1的子表，然后两两归并，形成有序子表
4 l  V! z: X  O1 U, [
然后将子表再次进行归并，直到子表的长度=待排序表的长度。
代码

#include "stdio.h"
, s0 o' i0 x7 z0 B#include "stdlib.h"
3 e) L9 `7 O8 r
typedef int ElemType;
. I5 s% d* t  G. u2 `
" A% {. B5 }: b/ j2 p8 P- H/ xElemType *b;

void Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
$ W* q0 ]5 S+ p+ k6 R+ i+ G, p    for (int k = low; k <= high; ++k) {
        b[k]=a[k];
    }
    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
+ ]$ I6 \! V" e/ A9 [7 B        if (b<=b[j])  a[k]=b[i++];
        else a[k]=b[j++];
" h# M2 K1 B& o; \+ x% d    }
    while (i<=mid) a[k++]=b[i++];
; O8 R3 M0 [! h, N    while (j<=high) a[k++]=b[j++];
9 I3 f$ I- e: H  V}
" y3 S# M2 Q. N) {8 x, R- {
/ C, U, l9 P. K$ h5 E3 Gvoid MergeSort(ElemType a[],int low,int high){
* h- {/ Q0 @  v    if(low<high){
        int mid=(low+high)/2;
        MergeSort(a,low,mid);
1 T) a+ w( W+ U        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
2 h+ @; O: }' D" h3 Y# T    }
}

int main(){
& G) G3 ~4 R/ q    int n;
% N) ~/ [! c/ b. N' x    ElemType a[n];
6 h$ ~2 N6 j* H* y$ W    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
$ ~( w/ ~5 ^( ^) N1 ?: L    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
5 a9 ~, {' d2 L; Y4 d; \+ l( ^    }
- ]: W$ g" \* A0 F/ |. k- n, n    MergeSort(a,0,n-1);
    printf("排序后为：");
6 w+ u) c, P& T( \    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
$ t$ b) o0 T; c}


1
" O- e! q0 A6 l- i4 P* X/ F2
3
0 ^' ~. W8 Q. @9 |) X4
' b. @* ?) K* r# d1 g3 i9 T( r5
6
1 _4 N; X) l: G6 `7
8
& D% J/ ~' p% Z+ B1 s9
- y4 `) ^4 Q4 H; [# a10
11
12
13
5 E' l  M9 [1 }; M9 O14
* [2 t  U" y2 m8 m8 Q15
16
2 b5 w4 a  y/ }& T& r17
18
19
20
# Y0 U& B( N( d" I+ i3 S21
22
* J. ~2 ]7 G" e. f23
' Z& H9 r& J, q9 ~24
25
26
2 R; M- M+ C5 M! m7 k27
, G5 m8 c9 `$ t, \) Q28
3 l& f5 v' {  `; e3 p29
* I  Z4 {# j1 _30
0 ~* z- f3 W  S* p* m, K1 D  ?! L31
32
33
34
35
9 z; s- s  u' U$ W/ `36
: U4 K$ ]6 u) T0 D. u7 ~+ p) Y37
1 C; G# M  E4 D9 U3 g8 d" I# L38
39
40
41
5 g, q! f8 `: K% T! Q42
43
0 r4 n; N/ j5 |44
/ q+ h2 O7 u% d, H' u& H: i45
, L  C3 Y5 f4 A. v" v' ?8 y; Q46
性能

空间效率：O ( n ) O(n)O(n)      创建了一个数组b
时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
; {4 ~. N3 k5 ?; \) s, Q​
n)  k指k路归并排序。
! _+ N# q# \5 |( u, f' H8 e7 P稳定性：稳定

5 l# X0 t5 d9 B4.2 基数排序
$ {; W0 N6 M; V图解
( Z' U; ]5 V% O  m9 L

* ]) _" ?, ^- u- |基本思想
' c* o: a# S- O# G0 a  u4 k
将各个位数（个位、十位、百位…）进行对比。
9 s! E1 K3 k  P) L8 y# b) ]为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
+ I. [! l) U$ L* p) G" ^& G
" i3 @$ i& j4 b性能

8 }! x; G0 L9 R2 s8 H5 L0 d" z空间复杂度

时间复杂度
: J+ {" I  o' T, P+ |

稳定性：稳定

5 i1 X+ P/ p, L: g) V5. 内部排序算法比较及应用
5.1 整体比较
- S' _7 T1 p* Q* j

0 T1 I- F3 m' N+ S1 K5.2 时间、空间和稳定性

. f, {& \# D* E
4 z& F  d. Z% D+ E6 Z, x# [3 c参考资料
《王道：23数据结构考研复习资料》
# |4 h! ~/ M' C) _- Q: b5 m————————————————
版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! ]8 T) w* [& L9 I6 c/ h原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678
5 _4 x1 f: ^0 z4 K8 Z. z

& I" }; a1 n8 O( H3 E* W* N2 n) L