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

杨利霞

数据结构：九种内部排序（动图+完整代码）
$ B8 R2 h" A  T* @2 A  {
排序
- O0 A$ k$ N- l9 n1. 插入排序
) V9 j1 p- j" T. r8 k* Q8 r& l5 ?# \1.1 直接插入排序
9 N, L3 Y$ a2 A. @, r% Y1 }1.2 折半插入排序
1.3 希尔排序
2. 交换排序
! C$ G- E) x# b  s( @2.1 冒泡排序
2.2 快速排序
9 s5 S/ y. J* l3. 选择排序
3.1 简单选择排序
5 ^# a' _$ C; r" T# w& Z3.2 堆排序
' n' G0 o3 ?) s6 i4 _/ B4 R4. 归并排序和基数排序
4.1 归并排序
4.2 基数排序
1 {' z, y+ B* I3 n& v+ v/ g5 T% ?5. 内部排序算法比较及应用
5.1 整体比较
3 `3 R4 R% a$ v' h( Z' t, U* E5.2 时间、空间和稳定性
参考资料
3 c! ?2 T0 H2 r( ?( `
内部排序：是指在排序期间 元素全部放在内存中的排序。
$ L5 R4 H; }, f内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
1. 插入排序
/ s6 H- M% f/ f+ R1 b/ U8 Y1.1 直接插入排序
0 Y/ R+ L0 |; Z1 w8 o9 E; l. z$ u图解
. ~* a, o" j, r# o

基本思想

1. 查找a元素在第1 ~ i-1中的位置k
0 f  K. T7 M" f) D" N; n8 L2. 将k ~ i-1位置上的所有元素向后移动一个位置
3. 将a复制到a[k]
: @* c' }% A" o
2 ^$ Y5 O3 j8 k9 j0 i  n5 W- t

3 ?+ v5 U! N/ G5 g! D5 K代码

" ?" e$ ?9 Z; @4 X方法一：
  K% g2 k4 C, X
数组的下标从0开始，如上图。
. ^: F3 A3 ~1 Y
3 D6 R7 W8 t$ O3 T8 i% n6 R#include "stdio.h"
* w- ]9 D( H  {) ^. B
typedef int ElemType;
  \7 c" U% n2 E5 ~
9 G& _# A" \: `( Gvoid Insert(ElemType a[],int n){
    ElemType temp;
! B& e7 I0 ?8 Z  a    int j;
$ f/ W0 Y% l6 I  L    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
$ D/ O# D! U5 c1 a; U0 a        if (a<a[i-1]){
            temp=a;                                                               
            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
8 g* L8 [& u9 {: W                a[j+1]=a[j];
  V/ c7 D5 J% P! |, w9 \            a[j+1]=temp;                                                       
        }
) b  G+ {9 W/ l- d  v    }
: H. w" g$ k/ i- H) w}
6 a8 i& a* g1 j8 i; n
int main(){
    int n;
. y$ U. A, X: z1 x  B; p2 B5 w    ElemType a[n];
& @3 v' J( l" g$ E. [% d1 b. H    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
: ~" [$ Q% d' S1 G) b3 h    printf("请输入%d个数：",n);
9 S+ N, S# I+ r# z& H" Q    for (int i = 0; i < n; ++i) {
' s3 e) M" I7 b3 o2 \3 x+ t2 m        scanf("%d",&a);
) v* M- u# x% A# g, \    }
    Insert(a,n);
    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
! U2 ^! {4 M3 Y        printf("%d\t",a);
1 v# U# o  @$ i: n0 Q) O    }
}
7 n9 g% d* ]5 t* C6 n! Y( e9 z
0 w& m4 z; @2 a1
+ y/ x9 T) R% x; E, d& l2
3
4
5
6
7
8
- T6 j  u5 d6 v* d1 y6 v) h9
10
, m" ~9 f, F% Z. b) W11
' }, B5 v& W2 ]+ B5 ?12
13
1 l9 E- Y: v* X8 {7 ~& [14
15
16
17
# s" N5 S4 V" z18
( W, z$ z$ k- k$ [* S19
20
21
22
23
24
% c: m. A/ G$ ?6 q1 @- l. g- P25
26
27
28
29
30
31
32
9 ^, s8 u4 q/ j' C' j1 C0 x方法二：
& g& I) P; s1 |9 m6 F

: E" u& [4 O% k
#include "stdio.h"

* c6 L4 R' y  r. w5 utypedef int ElemType;

8 c& i0 g; B( K. G3 M  E, Kvoid InsertSort(ElemType a[],int n){      
- m+ p7 J( k& I" N# g    int i,j;
- E. K4 Q2 Y' M+ v9 }) J    for (i = 2; i <=n; i++) {
$ K  ]( B$ R+ r  i- R2 {        if (a<a[i-1]){
# _/ m: m  W) I: w# m  f            a[0]=a;
            for (j = i-1; a[0]<a[j]; --j)
8 R4 U6 j: z. Q6 z$ O( Z                a[j+1]=a[j];
            a[j+1]=a[0];
        }
0 V4 a1 f6 x, s( `* `3 `    }
}
int main(){
* u* u; L) V. H; {5 f9 H    int n;
) Y6 Z# [0 S. m  Q3 K1 n    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
, M, @# A3 Q( H    printf("请输入%d个数：",n);
2 @- Q9 L0 Y" X4 U: q/ g+ A    for (int i = 1; i <= n; ++i) {
0 ^) G) g3 i3 D2 g        scanf("%d",&a);
    }
; b" n# K3 Y$ F/ }    InsertSort(a,n);
/ s' P2 Q! K( X$ V    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
# h" F; i  U- p& t    }
' p* s! n: e( R- c& M) N* g}

1
0 L0 M- d' y8 I3 P5 ]( f* V# @- w2
3
4
2 j+ g- L+ b- \- u( ]2 w; W( E5
! y. |! N2 {) T3 ^$ ~3 I% l% D6
1 B: v: L" n7 F7
( U+ Q* k, h; `- O" i0 }8
- W2 t9 r  ^& G( Q  H. c7 ]6 n9
10
# w" F- ]1 Y7 z/ e+ }7 c11
12
& |( `$ ~9 a: B, I* S9 E13
14
$ I9 L  x" A% T% m# K  \  ~15
8 r9 ?$ B& P0 R  c9 A* @) ~  R* S16
/ H/ w3 v; a0 h8 V- W7 Q4 }  T17
18
19
  X9 q* E/ D& n6 v- v9 d20
21
: z9 u% E# ^$ K6 C+ C  w) W' J22
23
24
) I9 n7 _$ ~! ^5 t; z25
26
27
3 M) ?% h6 l7 `28
29
30
8 H1 J# ^: H; E; w( w7 W4 y算法性能

$ W% @% v0 n3 n, _空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)

时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
)
6 {$ a) h8 l" F; a( d

% v4 Y; i1 J  {! J稳定性： 由于每次插入元素时总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

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

( \2 |: Q1 c! V1.2 折半插入排序
图解
第一趟：
- R/ \6 J( i, }8 ~9 u0 r5 k  A
& L/ U2 Q6 e$ j第二趟：


4 [  F, G6 K1 v) ]% N第三趟：
# ^( i: ]4 e5 D4 g" u
第四趟：略
0 M6 m5 u: R( D8 n, x第五趟：略
/ t" X1 u. Y8 @" y. q; w5 _# t
  X/ X7 J/ p% ~, v1 J基本思想
( J8 Q; ]: F3 C6 q2 L
: a4 U- u1 ?, I1 R0 K( j, K与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
8 B) S- n2 |3 I$ [; w3 Z找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
8 s# g& v4 ~  b/ ?9 @; I代码
/ \7 `% u* t& L
#include "stdio.h"
' }% z/ @; t9 R9 U9 u. K
; A1 y9 b5 a' Y& B- K( j# btypedef int ElemType;
8 q+ f8 W5 P9 C) `4 m
void InsertSort(ElemType a[],int n){
! n( ~+ J# f* j* J1 L) @: m    int low,hight,mid;
% @4 Q  ]; g2 E. U' K: l+ k8 V# Q    for (int i = 2; i <= n; ++i) {
' Q' g; @/ x: W        a[0]=a;
; Z+ X6 S# d8 k) t1 {' D        low=1;hight=i-1;
% [: F6 z0 o$ t6 j) `        while (low<=hight){
            mid=(low+hight)/2;
            if (a[mid]>a[0])hight=mid-1;
            else low=mid+1;
+ g3 c2 h5 i9 d" R3 \        }
        for (int j = i-1; j >= hight+1 ; --j)
            a[j+1]=a[j];
        a[hight+1]=a[0];
' S# ?8 b# O! M% Y5 Y, _: x    }
}
9 Q$ s8 n# C3 g' f" U3 u) {; A

int main(){
    int n;
    ElemType a[n];
; C, l- j0 ~! ~' L! c$ ^2 ^    printf("一共有多少个数需要排序：");
& X0 A. m5 I- f  |2 y# l6 S    scanf("%d",&n);
6 g* S6 P" S5 D$ g; @; M5 S    printf("请输入%d个数：",n);
( l. L0 p- z( z1 J- x    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
6 |! d5 u; ~! }1 `9 F    }
    printf("排序后为：");
    InsertSort(a,n);

    for (int i = 1; i <= n; ++i) {
& o" d* \4 e. ?! m3 R        printf("%d\t",a);
    }
; x$ Q! k! [7 Y- P8 }}
8 q* I  @6 q3 f. C; N
/ E* Y/ g! W0 d1
2
3
4
5
% w4 A/ P' Y0 l: Z8 V- @0 p7 {6
8 T8 o8 y( k( N, g7
8
5 n' w" R' X0 M, D9
7 d0 M' S0 F. [( }' z# k% o10
+ O  z" M! d2 j" g" V9 i  N" D11
12
13
14
15
16
2 s% b2 f2 t- [0 p7 X5 E2 S! w17
18
19
7 l+ U5 j% p' o, x20
21
+ u6 E. ~/ b4 ~5 ^4 x* ?; L' ?22
8 s6 A2 v3 B1 F& _( t! b23
24
25
, a7 s+ i' V7 ?  K( b26
27
' S5 u% M; R3 N  c: U  K; E" m28
29
30
31
; [6 H( @8 q4 p) y5 `32
5 _: a4 m' F4 [7 R; Y33
34
, c0 ^& ~& X1 H* a0 R0 j! D# f35
36
37
+ b* \0 d+ |" x: S+ L- \7 O! j性能

空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
2
9 m# K& i1 P8 F! n) F( @$ U )
稳定性：稳定
适用性：仅适用于顺序表
9 n- u2 P5 F/ p5 {) ^0 y
1.3 希尔排序
. I* c; L& @( ]- h2 u" Y图解(动图)
( k& H' T8 Q, j; I) ?+ k
4 @  ?( ]9 t1 {* f, H
! {; u+ J2 m, v. M, n) `3 N% A基本思想
" I0 d: |6 A) A, U3 p: e- ~9 ?
( x' D7 _: i! [, v- }9 S先将待排序表分割成若千形如L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

代码
; X/ n4 Y: }3 H% R
#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就排序
6 H% m3 ^! V' s        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
            if (a<a[i-dk]){
                a[0]=a;
3 O9 a. [( ^5 F# G: D" s                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
+ m9 L8 b9 Y; B; N3 k! X                    a[j+dk]=a[j];
; \. b9 ^/ i$ B3 n                a[j+dk]=a[0];
            }
3 H( Q1 k8 a) C! f- _) L        }
    }
}

5 i! B3 _' Z, j& A8 Wint main(){
, i! ~6 f5 c5 ~% I. G9 r9 t. m    int n;
# c  |: D( n: R" A5 |' L0 e# d# v    ElemType a[n];
    printf("一共有多少个数需要排序：");
# m% K9 F; U0 X7 m( }& ?    scanf("%d",&n);
    printf("请输入%d个数：",n);
) D4 x: N" v+ L. A# X9 R    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
    ShellSort(a,n);

    for (int i = 1; i <= n; ++i) {
0 @9 F' m: M7 e: I5 D        printf("%d\t",a);
    }
}
$ P; ^# F: `3 P. R
1
2
3
4
/ r- U1 p. s9 y$ \/ b4 k5
6
7
8
+ R: K" V, O8 ]- C* c9
- E+ {) j2 H# J2 Z2 V* L6 {10
11
3 j% t" P. R2 b; r5 |) |12
# ?3 Z% T; b& M; n+ t  P13
14
15
9 V: m0 c* F& _! ^5 u) N2 ?16
1 i* L* A3 M) i6 i17
- g# v1 P8 p  x( D  j$ N18
6 w3 W+ r+ V: i) U( D; C4 c6 l( ~19
5 B, T8 M7 t( X  r; Q! }20
$ H% K) Y5 O3 S& Q0 ~: `21
22
" \" e5 _8 s% U! l1 _/ ]6 c23
( {* p# @7 Q5 R24
25
9 n0 I$ W' u: J3 W9 N2 x- V" I26
" }; \4 X: M& L3 O27
28
- @0 ?/ ?1 s; H; u29
. @1 W1 i$ b0 g, G& I- ]30
31
32
33
& \  K! M) N" s2 H  q34
性能
& `' Y7 n1 r: n, A1 |  b
. {6 X( d( u3 s空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
* a3 |3 D6 E; X  Z+ r8 ?$ O7 n
" |9 F) B8 f' L' ]时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
! o' s% i' E; k& p1.3
- ^3 k1 _6 D. W1 I5 n )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
2
)

稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
  n' _* s* S' ~! @& U! j
. O( ?) o3 A2 P5 @$ u3 ]# R
适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。
8 _1 G- E/ |$ K8 o
2. 交换排序
0 S8 V4 ?- _5 ^' ?4 ]: }2.1 冒泡排序
: n+ D  p6 q. U1 {; x3 u0 c图解


基本思想

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

( O1 k) j' d4 y# E% n, G* Q代码

! M: j$ n9 M: K! B3 D方法一：将最大元素交换到待排序列的最后一个位置

#include "stdio.h"
6 P, K% B# G6 v& k& q. m
typedef int ElemType;
8 o! x2 {% H$ F" z
void BubbleSort(ElemType a[],int n){
    bool flag;
, w: W0 X( H3 w. w6 ]- B    for (int i = 0; i < n-1; ++i) {
- _$ o% Y# U2 B* L. \+ K        flag= false;
        for (int j = 0; j < n-i-1; ++j) {
( @, |1 S" H) T  M5 D; t. L0 ]            if (a[j]>a[j+1]){
7 e$ C% a. W: Y( U                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                flag=true;
            }
4 @/ C1 e$ {( ]$ m8 z4 y        }
        if (!flag)
            return;
' j. z. U* [  t    }
}


int main(){
* ^/ g7 ?0 F3 u& f    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
# _* H) c, Q( p4 ?  j: f    scanf("%d",&n);
8 C. b$ _& f8 V" o/ y( |    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
2 E$ E5 o, p( z0 e5 |    printf("排序后为：");
    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
4 v5 T* q) H5 W( W" W! K' j( z        printf("%d\t",a);
& d  q% u. _* H( g- j9 ~* ?$ Q6 K    }
}

6 C& q) H. k4 m2 y5 I! {, y: o% N1
( g  g% e5 X1 r2
) m- a+ F7 d  b' [0 a0 L3
6 C' m) O* @7 V- Q5 |, N  Z4
2 e+ S1 a& U8 N: P  c- O" o5
6
/ U& K+ u( \5 Q( \+ ^( q$ K5 i& i& t7
% ?! ^% T- U% {8
$ y* L6 A1 p& z/ M9
5 d' r% c" y7 {5 N+ k  T- }$ D! V10
9 E; \0 N: R$ k11
12
13
14
- P& i( |( e  f, R0 m6 o1 V. {' ^2 D15
16
17
# B; f" z" ~. R3 `18
8 W7 N5 _: P0 ~, M1 N7 I( z19
! V7 k2 n  P) I  d7 a" R! E+ k20
$ j+ T& _+ x* r: s" |21
22
23
9 m1 e2 ^  E' n- m8 l/ L24
25
1 ^* M6 ]: @8 H. T26
0 H. E4 {! v1 I+ ?27
28
) v1 X/ H2 S' M& z" p29
( R5 }) M; ]0 `) P' R) g& m5 A8 K8 E30
. q7 d1 r7 K/ \9 ^: L/ |$ K31
32
) Y( e: U: B# H* d( G/ n33
34
35
, R+ U3 k! w4 R1 J" K36
37
; |  Y9 d) a) M$ ?: ?6 P运行截图：
. c! z- i0 u  o: A

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

* Z% B$ Q; ~, Q4 Z0 h- B0 n#include "stdio.h"
: G8 R, c5 {8 S- S" M( a
typedef int ElemType;
: R1 [, g9 F1 h1 f- k
void BubbleSort(ElemType a[],int n){
/ o! M" \/ A. a7 E" u: p    bool flag;
    for (int i = 0; i < n-1; ++i) {
        flag= false;
        for (int j = n-1; j >i; --j) {
            if (a[j-1]>a[j]){
                int temp=a[j];
2 e* @' k; N' [8 a                a[j]=a[j-1];
* `* i% H0 t/ m% s                a[j-1]=temp;
                flag=true;
- q) C/ }- S5 U# ?. {            }
5 [; J8 P& G, f+ F- K        }
, `+ _) E8 m, |        if (!flag)
% ^" @/ M9 b# u# Y% i; n$ _0 i            return;
' h& P" V$ k$ c5 h    }
2 ?0 \8 R& Q* P% b}

5 w5 w; f0 L8 A
* e, f; [! o1 t  _+ m; Lint main(){
" {5 l; s/ v3 Q. c& h    int n;
( B; J1 a: `7 n) S; N# b* [4 e9 s    ElemType a[n];
: c! Q4 r, s8 n4 f3 W3 o    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
4 m2 l( W) N% H    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
  B; |8 e1 [+ {, }        printf("%d\t",a);
    }
3 v8 T: d) H, i6 i) w& ]7 i}

6 d* q9 ~3 J6 G3 W. N1
5 P( E; o" R3 I$ l2
- U  q, q( C/ L; l( p6 w3
# f* a/ e' B7 a2 V+ U( @1 a4
* v" e2 l- H: s% \5
- A# ^# T' U% {' S% |# {* }6
7
- d* v. g, i. n) o7 `3 F8
  B. T) D6 j# d& }. i( N/ M9
) k+ B4 r; s6 w+ _- k- a10
9 d% j7 Y0 p: Q) s8 m11
0 n" \3 R9 c7 q9 Z1 \12
13
14
' r8 G# g) V: Z) r, p8 r% T15
' b" \$ I$ Z8 T  H; h0 |& n16
17
/ k( h9 k- ^: V18
19
20
. o' r3 Q' J) ]: l1 H' y5 `$ b21
22
23
24
9 t3 d: {- ^1 q2 I& |- d25
7 {+ c7 L+ P% k8 D, s# m; i26
27
! y) R' `% ^% y7 v28
29
30
31
32
33
5 {4 k' j) s& P% {- Q! C2 n34
35
- t  [# g; |7 d8 D8 V36
37
, w1 \8 e: B+ j: F, V* j5 g+ Y运行截图：

2 Y% u3 n, V! l; |0 j2 |$ P
性能
2 g& Y8 x+ k1 L7 I* Q
空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
5 p  a& w! O0 Y0 K( k3 x
$ U* m) s" J7 l' d4 |时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
2
1 i9 N2 F, V: { )；平均时间复杂度：O ( n 2 ) O(n^2)O(n
2
, O1 K5 p# |* C5 s )；

( b% p! l/ i) o& J2 T! A稳定性： 稳定

6 x& ?0 S5 Q% E$ s适用性: 适用于线性表为顺序存储和链式存储。

! a" J( Y7 ~6 G( L2.2 快速排序
1 ?; U4 }9 ?! @$ }2 v* S图解（动图以后再补）
第一趟的排序：
9 R& x! S" [# r. d' `* ]
第二趟：
3 w: Y! T9 Q7 u! F
第三趟：
! D. e* P: P6 X+ s1 Z' T+ z
+ k/ k9 ^' |. R! d3 {+ ]3 ?
基本思想
% N8 g+ H& m- x1 s
快速排序的基本思想是基于分治法的:
- v& X4 ~" @2 f: L$ K- h' c
在数组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步骤排序。直至所有元素排序完成。
' ~) J' f/ f& @& O" o% W代码
/ ^! k+ c8 y' c8 Q( |0 j& y
#include "stdio.h"
' w. [) O  I& H  t& o8 }
typedef int ElemType;

: N. p* p' ]: N  ?: o# v. f' p' `int Partition(ElemType a[],int low,int high){
$ @0 `. Q' Z" S/ v7 p    ElemType pivot=a[low];
/ s3 k/ E4 ~( y/ K2 a* S7 y    while(low<high){
        while (low<high&&a[high]>=pivot)--high;
, {. B9 z: Z6 G! y# z. Y        a[low]=a[high];
        while (low<high&&a[low]<=pivot) ++low;
) `8 L( c3 f7 W; Q! r        a[high]=a[low];
8 X! {3 ?5 t8 r, w7 K( z    }
8 X1 }  W; q- r    a[low]=pivot;
( c* x" q7 l7 x; C. a/ g    return low;
}

) j6 e7 B$ o, l# v4 xvoid QuickSort(ElemType a[],int low,int high){
    bool flag;
7 c- ]  ?: x/ R0 {" @" U2 ^    if (low<high){
. U( t+ d- p8 n% I& L        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
    }
6 J: m+ b  P3 M3 Z7 q( a5 g}

int main(){
    int n;
    ElemType a[n];
2 k0 O& x" x) ^    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
    }
    printf("排序后为：");
4 z" y9 I! m) W5 P. `    QuickSort(a,0,n-1);
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
    }
1 A# j( ]0 G, d}


1
2
, H7 J6 S$ C, m3
4
: \! Z$ _2 P9 q. M1 p1 l/ A5
  F3 Z2 }& O9 l% Y) T6
' Q! r2 D* E0 T) i6 N' A: S7
3 i8 J9 D: H6 ?6 ?5 o0 Z! t8
' W6 H: `% j( j2 r9
& g# `$ D% v9 {0 F5 X( D8 [10
6 {3 ~0 A2 x5 t7 ~# \, U0 n11
12
13
: y0 A6 r  ~* g/ ^* ~& v14
15
* N/ D9 L: |0 d5 i7 T- H) @16
- c# x* b( N8 G9 F' z7 u) O) d17
% @5 n( y6 u4 E" t18
+ G8 S" {7 U& n* O3 b: m8 @7 t19
+ ^! g* y* }+ _& P4 w1 y- b. R20
7 Y2 p; h" s+ H$ m6 U21
22
23
2 t: D) \* D: f5 v24
$ G$ g  h% |6 p5 z( u/ P25
; F+ C0 S' f/ I# a4 m) _26
27
28
& P$ |7 `; x& @29
0 x- o0 J* A6 i) i30
7 V% E  T( n3 K) f' b& J3 l31
32
. E: o# b9 o% O33
34
: D# F6 u( d  Q/ g  @$ s$ t35
9 X) f5 Y; G/ k% p3 N9 R$ Z0 v7 J. c36
37
8 j% }- Z; s9 u% c, w  a38
39
40
0 c5 W6 Z2 `5 J! f1 V41
3 k& x! W& {( f# g, o性能
* p6 P. A( _2 p* p, c# \) o# X1 r+ M
时间复杂度和空间复杂度
7 P3 W1 [- A2 E. @+ \  U稳定性：不稳定
. n6 Y! ?2 M5 s; J6 P
3. 选择排序
: t/ E1 d. _9 B. w9 }( s, u% [3.1 简单选择排序
图解
+ x3 B9 b, M& R, V
1 l$ x# g/ L% ^- }8 U
) Z2 m( E! }4 z# A! c3 ~基本思想
2 I6 c+ x6 s0 h5 w
( @( p. U, j' K8 h在a[0…n-1]中，将a[0]设为最小元素，设min=0
& R- _2 H8 L$ T) n在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
在a[1…n-1]中继续进行排序。
/ c! t$ S) s% G$ t. f* U  s, l代码
$ E) J" v% [: D
- k1 P% s( t2 d' T#include "stdio.h"
" W0 n: l( J- z. q$ A& |! O
typedef int ElemType;

void SelectSort(ElemType a[],int n){
    for (int i = 0; i < n-1; ++i) {
        int min=i;
1 P; z8 {: T( m8 `        for (int j = i+1; j < n; ++j)
            if (a[j]<a[min])
                min=j;
        if (min!=i){
            int temp=a[min];
            a[min]=a;
            a=temp;
, A; I; T' z3 J* [& L9 D        }
& [0 P& @/ I1 q( o- H  ]2 g    }
: s- }( x0 K4 c4 O) q}

int main(){
    int n;
. o5 J5 V, v" _1 o0 a$ G. e    ElemType a[n];
    printf("一共有多少个数需要排序：");
* t. i! |% s1 L0 _4 ^6 x    scanf("%d",&n);
  @# q0 I- I2 z    printf("请输入%d个数：",n);
' m. w4 L3 L5 f# C! [7 E  x    for (int i = 0; i < n; ++i) {
% S2 g% c' b) X- v$ I! |        scanf("%d",&a);
    }
0 q1 _# \5 F3 N+ E  F    SelectSort(a,n);
    printf("排序后为：");
" Z! I& l% o' K2 s& p7 g    for (int i = 0; i < n; ++i) {
9 O2 s: m! u+ D7 H0 m        printf("%d  ",a);
" u1 v" o1 P' `; o2 A    }
% J6 R6 _7 b0 H# b: C}

1
6 b( l0 c+ k  ?3 X% H- E' @! M4 [2
2 W; S) x% m$ t# J3
5 M' w& G( {- T4
5
" C$ A& a+ V: N  S6
  A8 u/ K* w! t; t  F7
8
3 e# i/ o5 `* N/ h9
8 T% x  W/ O3 ^, n! P2 J9 g10
11
12
13
14
15
16
0 p" D/ j/ x; C2 P, w17
6 ]4 S( ~0 \. Z& }: u& g# E% t- L# S18
19
20
) o8 h( W4 ^  p! [21
22
$ u& K- C; o5 F0 D  r7 d. C0 p23
& E8 K# |; [& A1 [' ^24
$ j; v' H) l( o- o9 \/ h& K25
- P, T) A& M0 F& y26
9 e* Y& U+ G5 w* i) @# k) D27
) X4 T3 B! {7 z7 q8 w0 n2 k% I28
29
30
31
32
33
4 ~5 i7 s( o" [性能

' F5 ~( T! q, f空间复杂度：O ( 1 ) O(1)O(1)
* }/ Y$ |( v( _$ T时间复杂度：O ( n 2 ) O(n^2)O(n
2
* T5 K- e% _$ w1 \ )
) F9 U6 c5 P. V+ R  o稳定性： 不稳定
. e2 K4 }$ n' O8 K5 O
: s6 D1 ]( ~7 ^& n2 _% g  v5 l使用性：顺序表和链表都适用。

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

9 o! h/ S) `, p" w, P! J& ]4. 归并排序和基数排序
* [9 `7 c+ H' b( F. T4.1 归并排序
) }' K, i+ m- e8 W1 L6 _" `" {图解
9 X# z: b% G1 m" r% @5 m2路归并排序
: m+ K! B! h5 U* j- g0 y
" s, x; w5 W: h' X. g
) s8 P% z% Y  ^/ m/ H+ N; m; b! ]基本思想
; j1 Q% P  ~5 h1 q- D% D
1 U  L4 x% P6 u& w将待排序列分成长度为1的子表，然后两两归并，形成有序子表

3 h( `8 f5 F8 |5 @然后将子表再次进行归并，直到子表的长度=待排序表的长度。
代码

#include "stdio.h"
#include "stdlib.h"
$ J$ R  y  f( l
typedef int ElemType;

: X+ a, x- b/ Y/ x& MElemType *b;
" {/ M! M' j! F, q
void Merge(ElemType a[],int low,int mid,int high){
9 y. {1 |8 E& {  X: c/ p; q* v1 b* Y    int i,j,k;
- \1 Q2 Z1 [, a- v! H9 t    for (int k = low; k <= high; ++k) {
        b[k]=a[k];
- E# E. a) I  x" u7 a1 ?    }
6 E  J+ J# H0 t- Z: N    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
: \, u2 u* d2 n! q0 q/ F  f& r        if (b<=b[j])  a[k]=b[i++];
        else a[k]=b[j++];
    }
5 p; S1 S% _# r7 c2 V2 k/ I6 S9 y/ X8 L    while (i<=mid) a[k++]=b[i++];
: S* f$ o4 k& j( y& }& G: l- m7 }' d$ }+ l    while (j<=high) a[k++]=b[j++];
& U- e% N, O* e$ i' T+ `! f}
9 j8 Z" V* u4 N7 M2 V* C  ?" S# J0 N
void MergeSort(ElemType a[],int low,int high){
    if(low<high){
0 p5 [' b9 ]) s! c. f        int mid=(low+high)/2;
- ?# a. n0 l4 ]& O' e        MergeSort(a,low,mid);
/ T& X; H1 ]; L$ X        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
5 S/ o7 k5 d0 r1 K  d$ h    }
5 \$ F8 s- t: [5 Z9 z% d9 y" I}
3 B" h0 Y" F6 G4 l4 s( p% j
: ]9 M$ U: k: d  Q) r# t/ N1 x- s! iint main(){
( R! t0 f( p* \+ j# B    int n;
    ElemType a[n];
$ s. J/ P" T9 d2 y, n0 r% F! N    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
    printf("一共有多少个数需要排序：");
$ C' R' E0 X8 U    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
* M- V# i0 `* ?( W. K" r. k        scanf("%d",&a);
. y% J) Y' T: ]4 ^: u    }
, h, K' t$ h+ c    MergeSort(a,0,n-1);
% x6 p, V5 b7 i' D( [5 ^- r5 }    printf("排序后为：");
2 ^* @# }! \- g- ^. ]    for (int i = 0; i < n; ++i) {
4 X* H( k7 A) ~6 |3 R* U. s: a2 t- y        printf("%d  ",a);
    }
  U) T' `( ]9 {}
9 N0 l. w% E4 k1 U0 ^

1
2
" x7 X4 o1 v) `8 d* ?9 o+ Y  F3
4
5
: {. l4 Q+ L) X3 n& y6
7
# T1 I4 A$ t) y3 `* m2 V8
- i2 `- @& F0 G; O  d8 A. `' l9
10
( J7 v, h5 [1 o: A' R7 z8 ^0 U! C11
& B5 [5 l0 z) A12
( c! t0 _% E, m. |3 j; C( b% Y# G* L13
14
15
; j4 n: F- L1 y8 y3 p" E% g16
# R) N$ F  s; N5 z17
18
0 u* }0 j. N1 W19
; T6 ?% c$ a5 X' Z20
21
8 H+ H8 N6 e/ P5 T22
23
24
( H0 F* H* b+ q25
" H2 ^( O7 z! m8 x1 Z( A4 w26
27
28
5 W  @8 j9 O* Q* Y29
30
31
5 P; v8 y* }% u4 D/ F32
33
34
0 [: {# M- ^5 C5 g5 n35
0 T& [, o4 Z$ E$ e2 M& T' M36
37
38
39
( ]: |1 X4 R+ A& V40
2 Z1 K: `0 ~# q0 n- [" _/ T* Y4 U41
6 o* i# J3 z5 T* [: ]42
! s/ Q: ^; p* j( j1 ?. S43
9 A0 u" L5 T& r$ [1 a1 O44
45
7 w- D* T% T' Z# k7 g" H) C- k46
性能

9 |5 L( X6 d0 [4 W# N1 m( [空间效率：O ( n ) O(n)O(n)      创建了一个数组b
* f- g, F* m8 \( j2 [# d时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
​
: \0 Q. B$ \5 N* D n)  k指k路归并排序。
稳定性：稳定
8 a1 p2 w( N; S( F% k- _# k8 q( z
4.2 基数排序
图解

8 u# v9 ~6 h) L
基本思想
* u- q1 n; w/ |4 g
! P0 J+ Q) ^+ c3 e2 {- e9 c将各个位数（个位、十位、百位…）进行对比。
9 [: |. r: H+ X3 Q/ q+ {6 a5 ]为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。

( l; t. Z6 t8 Q, k性能
3 z5 k- b( U: I4 e* M1 {; p* v
) t% H: l" Y: b空间复杂度

8 @) p+ [5 H, s, @时间复杂度


" W3 y$ ?, ^) F$ i! ^; A2 S稳定性：稳定

; @+ A% O  p! }0 P+ s: N( M3 e8 n5 @5. 内部排序算法比较及应用
6 v$ H3 s" |& E2 E+ w5.1 整体比较
& o% F9 N4 ~5 w
6 Z1 B' m2 e% `
5.2 时间、空间和稳定性


参考资料
1 l$ ~9 ^: d% N# R! ^+ x9 }+ X! Q《王道：23数据结构考研复习资料》
4 o4 \1 A) b/ w7 `————————————————
版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678
* [- P" j8 t1 N( e* x
3 T3 ^7 g" ?- d% O: z$ h  b
% O, Y  T$ E" e6 N, m5 B