数学建模社区-数学中国

标题: 数据结构：九种内部排序（动图+完整代码） [打印本页]

---

作者: 杨利霞    时间: 2022-9-8 10:09
标题: 数据结构：九种内部排序（动图+完整代码）
数据结构：九种内部排序（动图+完整代码）

排序
1 k9 }9 @3 ]6 J: L1. 插入排序
1.1 直接插入排序
1.2 折半插入排序
% r$ r! g1 u( I1.3 希尔排序
9 u- V/ ^; }: d9 q+ `! M3 |5 r5 b2. 交换排序
2.1 冒泡排序
: @6 u1 u0 h* z/ S& D2.2 快速排序
3. 选择排序
/ S( k0 U, e) p' U1 F: Y3.1 简单选择排序
3 J* m# T9 Z; T7 B! i3.2 堆排序
4. 归并排序和基数排序
4.1 归并排序
9 Z( a0 o# ?. [9 r4.2 基数排序
5. 内部排序算法比较及应用
& c. E9 F/ i$ z! C: R5.1 整体比较
5.2 时间、空间和稳定性
参考资料

: Q9 m* ?# _" y2 ^  o0 o内部排序：是指在排序期间 元素全部放在内存中的排序。
内部排序算法的性能取决于算法的时间复杂度和空间复杂度。
) G: s% ~. P/ P" F9 T1. 插入排序
  ?- L3 \5 p5 n* Y0 B1.1 直接插入排序
图解
. n6 \0 Y, A/ j3 H

基本思想

1. 查找a元素在第1 ~ i-1中的位置k
2. 将k ~ i-1位置上的所有元素向后移动一个位置
3. 将a复制到a[k]

; i( E: P, f, V/ d' S; o6 D  q
1 A3 |' ^$ W/ h+ p6 O3 I5 _% D9 L" o
代码
( m- l0 w; u, |3 I$ f+ I% b' i
方法一：

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

#include "stdio.h"

- v& \0 Z/ u, b! ?5 X; t3 U: ?typedef int ElemType;

4 r* |+ K0 Q  I& ?( G8 z) a& Gvoid Insert(ElemType a[],int n){
    ElemType temp;
3 o: P4 P& o! j5 o    int j;
( B6 I, Z. `. F, B# |# y    for (int i = 1; i < n; ++i) {                                        //假设a[0]是有序的数组，从a[1]开始进行插入排序
( B) G& \& H, j% E3 o        if (a<a[i-1]){
# h( t" p. ]" c! q. a" o& g# f( g            temp=a;                                                               
            for (j = i-1; j >= 0&&a[j]>temp ; --j)        //将k ~ i-1位置上的所有元素向后移动一个位置
                a[j+1]=a[j];
            a[j+1]=temp;                                                       
( }1 `+ o$ }5 ]3 B( p1 ^: }; n        }
& Z) R! t* R/ W( k; {: J. s/ @* O  g    }
}

int main(){
    int n;
' j2 Z3 d3 O5 e% D/ w; J$ e    ElemType a[n];
    printf("一共有多少个数需要排序：");
" |# w1 \! p1 h: c( R: N: N$ R    scanf("%d",&n);
1 j3 _5 w2 ~( q/ B    printf("请输入%d个数：",n);
0 k: r: h. ~6 |3 y    for (int i = 0; i < n; ++i) {
  [$ H  x% U* k" q  Y5 `8 B        scanf("%d",&a);
    }
    Insert(a,n);
) |8 Y# ?0 O$ J3 [    printf("排序后为：");
2 ^3 o( E+ h- K5 _1 y; r    for (int i = 0; i < n; ++i) {
+ j! X/ w) E* S( z: ?: k6 U        printf("%d\t",a);
- G3 A; `* S& I    }
}
& |$ \) t3 w6 }
- A, s' l& M5 B) @" t1
2 W4 W  t; d% d0 \" v# _+ M2
$ a' o. Y  P& A7 ^1 R$ P: j3
4 C1 o* x; ?% u" j4
1 N. x4 V) v; O' }) ]$ N5
6
5 H6 D' j6 m" @6 c$ S8 \+ [7
8
9
10
+ R. P) ]5 v& ^( P( ?. M2 h8 x11
, K7 P5 N& |* J+ {# Q' Q+ z12
* A! D  r- }1 c- R13
14
15
" a2 S. J6 y0 w0 I16
7 F3 q  d* Y+ y' U17
18
/ ?6 S, d, N9 I% Y7 a19
20
21
& g+ `; P: }1 b8 I( p+ L22
23
. }& {0 h( H& |) D! H24
0 \' X, C9 t% X( x1 C' t25
26
27
: I6 R1 u, N; V0 h28
$ J1 Y  c/ e& |29
30
) x: n' n4 y8 y# q- w31
32
方法二：

+ L* T/ s$ y3 P. b6 c
  w3 ^# Z& m/ t( }1 }
#include "stdio.h"
, n5 S7 x' W1 P9 e8 {2 Z: `+ `
typedef int ElemType;
! S6 Q  U! t' @" y
void InsertSort(ElemType a[],int n){      
    int i,j;
( \; z; v2 R) v% Y3 j0 }. `    for (i = 2; i <=n; i++) {
4 s; w* @5 z! `        if (a<a[i-1]){
            a[0]=a;
: U! `4 z9 \2 u4 h/ U            for (j = i-1; a[0]<a[j]; --j)
                a[j+1]=a[j];
            a[j+1]=a[0];
        }
    }
}
, s- _0 ~. k1 [: }* d* R1 ~+ v4 D& Lint main(){
    int n;
' U1 n4 r+ ?: v) C* Z5 f6 G- t    ElemType a[n];
+ M1 D) c0 m0 j' a" ~& ^    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
4 w5 w( r( o2 W# C. v% j1 }    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
; P! ]$ F3 `* O1 R( c) H& O4 b        scanf("%d",&a);
    }
- D$ v3 K0 R5 @. v! Y/ u    InsertSort(a,n);
/ u! b* W6 O" y3 w% z    printf("排序后为：");
6 v7 \: h' y5 T- _, ?    for (int i = 1; i <= n; ++i) {
2 E7 e$ X5 a% j" U# z        printf("%d\t",a);
    }
- F7 F( B3 e3 B! U( l}

) M9 e+ J* R4 T: p) u" G9 j1
2
& V* J) C& L+ b1 Q# F% N3
4
+ A4 a' j, g3 O3 o6 U8 |5
6
7
3 H2 ?- V3 d; u3 r& b8
6 E  r1 }+ C% K- l9 b3 t9
10
! T" G9 K! j3 y  L8 ~11
12
+ V  P+ \2 y7 a. A% L5 p13
14
3 N# i! }2 j9 }$ C! B15
16
17
18
, V+ T3 {. W. c1 g) W& }; J, C19
20
21
& m# M$ G6 Y8 W4 l+ j22
23
$ y0 B) j' B4 r5 J. T6 J24
25
3 o* `$ w+ P8 D" Z0 d26
27
28
# v4 `  \* b) [, g- a& }8 `! V" }29
30
' Q1 N! z! q" t! C) \算法性能
9 L8 m' g; A# [% K
空间效率： 仅使用了常数个辅助单元，复杂度为：O ( 1 ) O(1)O(1)
+ ^/ Q! H4 O5 M( S8 l5 b
时间效率： 平均时间复杂度：O ( n 2 ) O(n^2)O(n
: M* I3 d) z0 U2
)
% g* b# S) {, n& \4 Y9 ?

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

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

! C* L$ G1 L" r; ?/ L. x1.2 折半插入排序
: |5 g4 @. l9 z8 z# A) C: q. h图解
第一趟：
$ Q8 B$ j8 F; R. F9 N
第二趟：
- U9 j' O" N% `$ w4 K

6 Z* t$ ]* h9 }/ t) Z1 i+ P; M第三趟：
, i2 H' N. M$ p2 z
0 T( p( }) J; A& K& e2 @. y: ~第四趟：略
$ {7 w5 `# V+ [9 _, v第五趟：略

* P3 X# q: K2 f5 Z: C基本思想
8 m- o+ e1 Q; y0 i
! X4 B- b. e! J7 u: S) e8 ~5 I6 t与直接插入排序相比较，折半插入排序引入了mid，low，high，减少比较次数。
1 {) L" w+ m/ Q( _取将有序子表中间值，若a[mid]>a[0] (待排序元素)，low=mid+1，反则，high=mid-1；
找到比a[0]大的元素，均向后移一位，将a[0]元素插入待排序子表，形成新的子表。
8 m+ _$ g* i! y* B# ^3 Q代码

#include "stdio.h"

  T/ U* O9 ^1 t2 dtypedef int ElemType;

, A- P0 t' Q+ p. K9 X7 L; G; tvoid InsertSort(ElemType a[],int n){
    int low,hight,mid;
- l4 W# M6 e- H- f, X/ B& L0 d" X    for (int i = 2; i <= n; ++i) {
5 E, o  |; }1 e! t! c( a        a[0]=a;
        low=1;hight=i-1;
2 t1 p, l: Q; g, X        while (low<=hight){
- f" _3 b+ N( i# Z$ Z3 I3 O: k            mid=(low+hight)/2;
6 }' r0 |% I' a2 ~- I" g( _8 y2 x            if (a[mid]>a[0])hight=mid-1;
            else low=mid+1;
        }
" X$ S( A, K- G4 ~7 [# y& [6 {5 k        for (int j = i-1; j >= hight+1 ; --j)
            a[j+1]=a[j];
; `7 U& U0 R6 E/ B  z. x9 f; G        a[hight+1]=a[0];
8 a4 c- a+ F7 V1 i    }
$ n( Y+ B* E, \5 |5 ~}
8 u( M: M  N) Q( b3 \  M

. A; W( [" F3 P: ~8 _* e- hint main(){
    int n;
' B+ `( j4 F* a2 V8 F! G3 ?. w    ElemType a[n];
    printf("一共有多少个数需要排序：");
% y! {: b" N! x2 N: ]1 `    scanf("%d",&n);
    printf("请输入%d个数：",n);
# i- Y& e- X( Q% ^2 B) O    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a);
    }
3 ^6 D2 A& G4 ~8 b' C7 h    printf("排序后为：");
# l, x, y: Y0 T' E' w    InsertSort(a,n);

    for (int i = 1; i <= n; ++i) {
3 K7 ~6 k" V- [$ w        printf("%d\t",a);
2 S& U4 ?/ A& r0 c    }
  b5 K1 j4 i' U7 V}

* ~# o& t- r2 v$ [1
: \; [0 s& b; u+ N) Q2
3
: p  q' b5 x4 a6 O. W& R4
5
6
7
4 F5 W& R( f) P* @6 W+ x) v8
0 r7 w! {% N* p* B9
  g- i# l9 K- E) @10
11
12
13
$ ^) A4 U% [2 n2 m14
15
& V0 `+ K9 \# d+ ]$ G7 ]16
) U# O( y" b& d7 \- F' J, Q8 @17
6 F+ B% r8 y, ^18
) r" d: h- n! j: o6 R! j1 J. |) j+ G19
! ^' j. u7 B! f$ Z8 L3 c7 _: E20
21
$ J! R* u9 A9 K+ f& q& W4 U22
23
" X  _- A% `/ f/ d2 Y7 Z24
25
5 D5 L) p6 {/ ~& b8 ^& O26
27
* b3 B1 Y: U0 u, C/ \+ q28
% A; T  W6 `* N1 b29
9 a1 y* T/ [' {' f$ K30
31
32
4 F! f; V! x% A2 m33
34
) s( V& P* I3 l) u/ Y35
1 I8 ?! k( n, L; M36
6 y- y& [( @, @; v& ?37
# x, @- ~* \4 L4 p9 F性能

空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
. N* ^+ z% ?% e0 g& l4 A9 O2
! _0 R+ Q+ D- z8 N- m5 R: T" ~ )
稳定性：稳定
适用性：仅适用于顺序表
+ l2 Z% h& Z# ?* x$ [4 i
7 b' w  i/ A: `  T8 W% Y1.3 希尔排序
$ f9 r* v) }. j" f图解(动图)
4 j0 z* Z! [. k0 o4 V0 T
# h% A. r5 I$ f6 I/ Z5 A
( H/ v7 J& M2 c: @基本思想

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

代码
' m3 m0 t0 t4 a' r
#include "stdio.h"

typedef int ElemType;

void ShellSort(ElemType a[],int n){
& n/ l2 s) w" \3 K" G# p    int j;
    for (int dk = n/2; dk >= 1; dk=dk/2) {                                        //判断每次分成几个序列，只要>=1就排序
6 i' p  x, l6 {+ B; s& C3 o        for (int i = dk+1; i <= n; ++i) {                                        //dk+1：取到小分队的第二个元素（从第一个元素开始）进行直接插入排序
" r: ?$ Z8 j; p8 K' l' A            if (a<a[i-dk]){
" F: z  y) X8 L                a[0]=a;
                for (j = i-dk; j > 0&&a[0]<a[j]; j-=dk)
                    a[j+dk]=a[j];
                a[j+dk]=a[0];
# C& p$ G; P( `* Y7 Z3 g$ Z            }
4 U0 d* Q( h5 o! d4 G& n9 e        }
/ D6 m; Q4 E% |% @    }
/ ?3 E6 w6 |1 J* }: L2 b}
% J/ x7 I4 `& K
int main(){
5 m+ y3 g. j7 o' v. u    int n;
    ElemType a[n];
' D5 a2 D' ~& h' z    printf("一共有多少个数需要排序：");
) q# H8 L5 p$ k    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
  T3 W& a# N- u5 ~; T2 J" J        scanf("%d",&a);
    }
/ n& c9 {2 _# k2 A( V    printf("排序后为：");
& ^. V6 P; s& n& X    ShellSort(a,n);

' z6 i7 R# u& U! t8 s& c: C, `    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a);
0 `. j: p  a$ N1 h/ L: }" h    }
}

9 ~& C/ g- ~3 ?6 M& @) t& r; C- `1
  u% I' h+ s! L; X6 x& o0 v/ o% {( K2
3 S7 m/ N( N9 B5 a) v0 X2 U3
4
5
6
8 C' }! U* D- c- K! |# K, i( T7
  D0 J7 |: ?4 H8
5 r  G" I, S3 A9
4 u/ R% n9 M- ^0 O/ ?10
8 Q8 ~' \- R- Z0 {5 w; K& ~11
12
- C/ }( c' {( E8 W4 I13
14
+ B$ {+ {( L5 X  \/ W1 g' ]15
9 w2 `2 j. X7 d( j' @( |( @16
3 R7 B) ^8 b8 |. v- S17
18
" e  s6 E# W! Y$ [19
  x2 x5 L3 ?+ P8 k' [9 J20
21
' v! ]' B* f+ ~' w22
23
24
( n  s# U. j$ n8 i25
26
8 B! \9 i9 ]# _$ w+ v$ V27
28
6 k- D- C) h* X5 `/ c& [$ j* y29
/ K8 h1 O# o  G2 s2 L" }$ e30
8 D& W: C) N, o7 `( q31
32
33
34
性能
5 h0 f/ O+ B$ t) B( Q5 Q* [6 v
空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)

/ o4 O4 x6 S; {; _+ N, ?- m时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为O ( n 1.3 ) O(n^{1.3})O(n
5 P0 V. ?2 i( X0 t1.3
# Y3 V: I- f) A  g )，在最环情况下希尔排序的时间复杂度为O ( n 2 ) O(n^2)O(n
4 l- j) D. p6 Q! d2
)
  ^1 X- Q! j1 ~  i2 i: d* t; P
' L: U9 U% d, ]  m, f* R+ R稳定性: 当相同关键字的记录被划分到不同的子表时文可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。


适用性: 希尔排序算法仅适用于线性表为顺序存储的情况。
& `" u, T+ H7 L+ ^
8 C4 o9 i9 z  s+ E2. 交换排序
2.1 冒泡排序
4 @4 E6 T' N3 c% C, n: G" `3 A图解


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

; s  q, Z9 Z4 M( S' W8 u代码

方法一：将最大元素交换到待排序列的最后一个位置

#include "stdio.h"

typedef int ElemType;
9 C: C+ h9 \& q: I% [  w
void BubbleSort(ElemType a[],int n){
    bool flag;
% g4 G" s$ w  s/ v0 C! \    for (int i = 0; i < n-1; ++i) {
, Q4 R' D$ y/ q, |3 U2 R2 _3 N9 z9 k/ ~        flag= false;
        for (int j = 0; j < n-i-1; ++j) {
            if (a[j]>a[j+1]){
, R4 L8 i; \* e8 l                int temp=a[j];
% M) {7 G1 n7 N0 h. ?3 M                a[j]=a[j+1];
                a[j+1]=temp;
                flag=true;
            }
# l6 b' l2 R5 P1 h" `        }
        if (!flag)
            return;
    }
) z0 U( S8 J6 _$ V# N}
4 j' Q4 I: J4 ?" P% _* D/ X

+ q6 Y9 ~8 s( t3 x" Wint main(){
    int n;
% G* ]& I" z9 l* ^    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
1 O$ `9 R) e- K4 v$ \; `    for (int i = 0; i < n; ++i) {
( X$ O! o  |; O  r  `  b5 \" y        scanf("%d",&a);
    }
    printf("排序后为：");
$ C# s9 s/ q4 T) f    BubbleSort(a,n);
- J( ^; x: {+ C7 ~    for (int i = 0; i < n; ++i) {
  ~0 e9 h% s; X% Q- F        printf("%d\t",a);
    }
* ^& B  r% V6 @& D1 R! b! [}
7 i6 c7 D: {1 h8 b6 J1 g3 J
& M* x# o& h- }2 S1
2
2 r5 A6 f7 z: {( F: Y$ }& `; G3
4
5
6
+ f9 @5 s# G/ ~2 Z7
4 i5 F5 H( _2 K& n8
9
' D; X* c6 B, {  N0 e) |2 H- J10
11
12
13
14
3 d$ M9 n7 u' F: v/ K  b6 i( j+ G15
0 Y% x. M, k# p3 F16
17
18
- v8 j8 t; L& ~/ s$ }' M19
20
21
22
23
24
+ \' ?9 [2 T- r/ [; G0 ^9 n, Y25
26
27
28
, a3 f* Q" ?) T0 ?( ]29
30
31
32
' K! [' U5 N6 q, u! Y33
' c, q. C  R9 s0 p34
35
) j! `9 G) l) F) w, \( Z% V) G36
: D9 ^  F: ]$ Y, x, ~4 \& I) f37
: }$ R2 u  f+ e运行截图：
, h2 q1 l& C2 Y# F( |; }+ c: ~

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

#include "stdio.h"

typedef int ElemType;

- X. @+ e9 k! B( Mvoid BubbleSort(ElemType a[],int n){
    bool flag;
    for (int i = 0; i < n-1; ++i) {
. ?) i3 o3 O! V3 R1 x, A        flag= false;
: q; S7 E: L5 O# _: Q        for (int j = n-1; j >i; --j) {
! W: M! P  Y, o/ u2 I4 y            if (a[j-1]>a[j]){
                int temp=a[j];
0 C+ K+ r' A* j7 p% f8 a! |                a[j]=a[j-1];
                a[j-1]=temp;
                flag=true;
% y9 M; ]- d( q8 Z" ]            }
# E0 _7 g- I! R        }
* v3 b$ Y+ ~0 c* N! S        if (!flag)
, z  R" V* e/ q3 |, d' [& A            return;
    }
}
4 E0 q' ?2 w3 k4 o2 e7 R+ O
  h# A% `& C5 Q0 X& _' S) {- C
int main(){
    int n;
( ^. l, g: I! D9 K! U! C    ElemType a[n];
    printf("一共有多少个数需要排序：");
  U& j. T! ~* }$ j: I    scanf("%d",&n);
2 o/ I; x$ I# ^! f6 u2 G    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
) n% }  s2 l% \$ m& b# b9 d( x        scanf("%d",&a);
: ?, |; `" n/ o0 E2 ~, L    }
    printf("排序后为：");
. w+ |5 X8 U4 E' h5 y2 v7 v    BubbleSort(a,n);
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a);
  [6 {, m$ j. O* w    }
% j/ Y0 D& E; V& \& J}

1
+ r4 _, P) i' M2
% y, X) }( ^- A( ?7 @& D3
& f/ j( g! J$ C: \3 \4
, \: R. r$ O* I, s5
6
7
8
- u& n7 `  c# z/ H8 I. _' c/ r9
3 D1 d7 l  k7 ~3 N$ h) ]3 s10
: y7 |# y7 r1 R11
3 c, H! b3 D& W; Z! q6 n12
8 K* y* N6 X5 a% R' G2 W0 ~( e13
14
" b8 a( w* H# r: ]" u15
/ ]% x1 A; k# U% c7 A, o1 L16
17
18
19
20
2 |  Y  m- U. j) H21
+ a: ]! ^& R* F% R- @22
23
24
! b5 n5 s$ ~1 R4 L3 D: Y25
26
27
8 G1 j7 E& R+ w3 t9 Q! f& @- e28
29
30
31
32
33
34
35
36
37
运行截图：
9 B& ?4 L9 F1 B$ K+ K. d  P, I
1 X; g5 W, |0 K) F) T
0 h% q% }1 }- k& [' |9 t9 F1 B性能

4 I& w& I; ~/ }7 t空间效率： 仅使用了常数辅助单位，因而空间复杂度为O ( 1 ) O(1)O(1)
7 c! I) |) D9 ]6 o
时间效率： 最坏情况：O ( n 2 ) O(n^2)O(n
2
)；平均时间复杂度：O ( n 2 ) O(n^2)O(n
9 o" a3 Q$ ~! d6 |& S; g0 L2
. y9 E. d, ^- t3 t$ L )；
" u* D1 ]" W) q1 q4 S9 w( \& Y8 P
稳定性： 稳定

适用性: 适用于线性表为顺序存储和链式存储。

: r+ q- T- f2 h. E( `' k! h2.2 快速排序
图解（动图以后再补）
3 h5 l& s1 o2 ~' Y第一趟的排序：

& D' [8 T" y) p第二趟：
2 Z  F8 H) R2 X2 Y# S' {
9 x: _, Q& p0 k9 ^, |6 P6 k7 J, z第三趟：


4 n5 B$ V+ _/ a8 f+ C' V基本思想
; L: Y& z+ r& V/ v+ v0 v
快速排序的基本思想是基于分治法的:

在数组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步骤排序。直至所有元素排序完成。
代码

5 K0 v. O5 U5 U0 p$ B" c#include "stdio.h"

, w$ o0 F% r# Q4 U/ o% G' Ztypedef int ElemType;

int Partition(ElemType a[],int low,int high){
    ElemType pivot=a[low];
3 c6 k' M. F1 `: ^3 C$ T" g    while(low<high){
        while (low<high&&a[high]>=pivot)--high;
) v2 c5 P5 R/ A9 u5 @        a[low]=a[high];
        while (low<high&&a[low]<=pivot) ++low;
        a[high]=a[low];
    }
    a[low]=pivot;
% X" Z. S6 e" e4 r    return low;
}
' c# D/ h- q- a
void QuickSort(ElemType a[],int low,int high){
    bool flag;
    if (low<high){
        int pivotpos=Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
5 M; k  v5 [4 v% L    }
}

int main(){
3 }* ?2 @- M" l% e3 ]" {- B& V5 b  A    int n;
! Q/ y+ r+ \' I  v. c7 Y    ElemType a[n];
    printf("一共有多少个数需要排序：");
/ Z9 n/ j+ k" E' O, q  |8 Z& C    scanf("%d",&n);
    printf("请输入%d个数：",n);
/ l% B# Y* [9 V& V4 C' e9 s5 V    for (int i = 0; i < n; ++i) {
- G" t) j" q: w" F        scanf("%d",&a);
+ q5 C& V) r0 o7 l8 r9 v    }
    printf("排序后为：");
- d/ u/ i4 W7 V- u* o4 A! Y0 `    QuickSort(a,0,n-1);
) M2 U0 p& }6 W* H% y- X% C    for (int i = 0; i < n; ++i) {
( n" {+ F9 z0 I6 _$ ~3 T+ a$ Y! z        printf("%d  ",a);
    }
8 Q& j7 \" U/ l1 V& ]; i8 P8 c6 L}
% d% l: T4 J: O% I2 @

1
2
3
4
+ n; }. U: ?1 R/ T5
6
7
8
% [6 z" g9 `* l  t8 R6 y% M& s9
9 K1 b0 j* O5 I: e: s; ~1 r10
11
9 r) f1 ?3 g3 j12
13
14
0 T8 N4 }8 ?1 V( U" E15
16
, V, }! Z4 H& y$ z2 ^3 y' U: f. B17
6 k, f0 I0 j% A2 R, ?# @18
+ X/ L$ m+ b8 X* v( l19
: ?2 I2 R5 z4 X# o2 |8 e* Z6 w( i20
" x$ k/ V! i( z21
# J5 ^# q' t& L, I5 F2 ~22
: u. V8 _. d) M  S23
24
25
26
27
7 s) w" X4 J  x7 N/ d% _2 Y28
29
30
31
$ B+ \/ ?+ `" `3 e0 |, J32
33
34
35
36
37
: Y; D# _8 Z# o8 f% l) G( I3 d38
39
40
41
; h) }3 N4 F$ p$ A性能
; Z& |7 B" I6 u, c# H
$ @1 \$ q  o3 |6 I时间复杂度和空间复杂度
. g' p; Y% U" E0 x1 b稳定性：不稳定

3. 选择排序
3.1 简单选择排序
9 V! l$ s4 n# A5 m$ }# C0 {5 m图解

; z, \; s' q- \& t# m
基本思想

在a[0…n-1]中，将a[0]设为最小元素，设min=0
9 A  L, v$ [* A  h/ H$ c在a[1…n-1]中找到小于a[0]的最小的元素a[k]，令min=k;
若min=0，则a[0]最小，不用交换；若min!=0，则a[0]和a[k]进行交换，第一趟排序完成。
  h. q/ e/ h, `# G在a[1…n-1]中继续进行排序。
. H0 _, Y1 C% ]8 c3 y代码

#include "stdio.h"
& I6 P/ v- L1 x% w3 M5 {
& U! {" J, ]5 x) Stypedef int ElemType;
1 n9 w& d3 |8 n1 ~+ w
void SelectSort(ElemType a[],int n){
    for (int i = 0; i < n-1; ++i) {
# L4 k. y3 w) D2 u- L& k        int min=i;
. a8 _) o1 c& D! d4 @$ T        for (int j = i+1; j < n; ++j)
+ `4 G( y5 G& e6 _& E7 n1 g3 \            if (a[j]<a[min])
8 }6 ^- y8 |! U  j                min=j;
        if (min!=i){
            int temp=a[min];
  K. ]. ?: z* [5 [% b            a[min]=a;
, D2 j* D% l% b7 A! g! E            a=temp;
        }
    }
}

. ^" q3 ]  H$ f+ N" \- e2 Yint main(){
( O* {& P% ]; ~/ Q4 R; B9 ?    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
5 I8 ]. N% K7 Y6 k    scanf("%d",&n);
! q( Z) f2 c6 D* \    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
0 X. w; ^8 v4 f        scanf("%d",&a);
7 Q+ E5 T  y1 k) A# t3 |. D) S    }
: ~+ l" F& c# |    SelectSort(a,n);
8 y. V2 j. H1 J& q/ c    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
% V9 w( B2 X7 m7 w        printf("%d  ",a);
$ R# T4 `$ d5 N7 q: b/ `: L    }
}

1
4 |" Y3 L6 F1 |6 N% e! @0 @6 ^' Y2
* y% }( Q; o/ x9 v/ C3
+ |8 K% I8 [- m0 L4
1 ^3 ?$ J# U- M' y5 d. E: F5
6
/ v9 k% [8 i3 m9 [5 w7
8
  l) y7 y: U* @# _8 x9
10
  B# r1 A! B, {7 I  ~2 s11
12
: b8 u; {1 T: k# N13
14
  Z8 h9 m' ?4 }  v; p8 J4 J15
16
9 h/ y! w7 Q  h2 I. g9 ^8 A17
18
19
, g+ J) S/ v' r; B! l20
3 Y8 ?  W( {* n" k6 N2 @* F21
+ n  P& H9 y" H9 o  W- k- u22
- w. q2 m! v# l23
24
& D8 [5 n# f1 l. E/ S( h/ l% A25
0 ?3 P2 q* ~: ^& S8 [6 X26
0 @) x/ T; H4 @1 V. H3 x  b) F27
28
29
# Z) s. B4 G) l# B- D1 d' O' s30
$ S0 `6 Y- M7 N* K" j# X& V31
32
3 }1 I9 h; H* G5 }33
性能

5 L6 }* G0 r3 G& B空间复杂度：O ( 1 ) O(1)O(1)
时间复杂度：O ( n 2 ) O(n^2)O(n
2
)
稳定性： 不稳定

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

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

& ?. Z! B/ }; T- t$ Q  I$ K8 M4. 归并排序和基数排序
' z# T! M- b2 m1 i% h4.1 归并排序
图解
  k" h& D/ G- k+ [2路归并排序
  F# e  q2 O# q3 y; O4 p9 B

+ V4 T3 M0 ?0 F- |3 }1 r基本思想

将待排序列分成长度为1的子表，然后两两归并，形成有序子表

然后将子表再次进行归并，直到子表的长度=待排序表的长度。
代码
9 A3 |, ~% H6 z6 p6 r
$ R" _6 q" H/ N% ~' O9 N0 S& i0 j# w#include "stdio.h"
' P: [- \* u- J- N8 P; f: l4 A#include "stdlib.h"

( y4 Z1 P1 Y( G# ?; N% G  `typedef int ElemType;

ElemType *b;

4 i5 k, u$ H" `" p5 m# R; ]+ {9 [void Merge(ElemType a[],int low,int mid,int high){
    int i,j,k;
6 `' n6 [6 i4 a% K- r2 b: ^    for (int k = low; k <= high; ++k) {
# N: K6 j7 F- w9 B* d( h        b[k]=a[k];
    }
    for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) {
+ ]1 ]4 a" b1 Y  {) }: Z, \        if (b<=b[j])  a[k]=b[i++];
; X5 y. n& ~: X; F7 `        else a[k]=b[j++];
) i# O, H  a- ?6 m& c" Y' P0 F7 F    }
    while (i<=mid) a[k++]=b[i++];
# S  n: @7 o2 |" e    while (j<=high) a[k++]=b[j++];
}
3 s9 H! A" I  j) Y1 M; V
8 v: w8 y6 b" d* o+ q1 mvoid MergeSort(ElemType a[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;
! ~: @  q5 ~, f- x        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
' D, Q% J8 G1 m2 O. W( r2 X% u        Merge(a,low,mid,high);
# I) G# K8 X7 f% K# g( |3 L    }
}

4 G9 F3 F: I6 i1 eint main(){
  ]9 e7 R- p4 F; ?7 U- h    int n;
$ X% `3 @9 _5 z$ A" ]$ U    ElemType a[n];
, }, Y  \. @: d* }6 Y0 M: R5 f    b=(ElemType*) malloc((n+1)*sizeof (ElemType));
    printf("一共有多少个数需要排序：");
* ]3 S( m# ?! |  w' q    scanf("%d",&n);
8 ?: l3 _; c5 }# i3 p& e( r  N    printf("请输入%d个数：",n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&a);
- y9 V/ ?4 v, z4 E    }
    MergeSort(a,0,n-1);
+ Y; E9 V4 C( h( K5 D& X6 _/ D    printf("排序后为：");
    for (int i = 0; i < n; ++i) {
        printf("%d  ",a);
8 ]; x% @  M, V- E    }
}
: A  a4 Q! D& r+ p

; E3 }: S2 \! G2 h; f5 C  h2 k: e0 t1
2
3
4
5
6
7
5 {# h. a" z* Z: E' J8 q$ {* n8
9
# R* P: N. E' O2 j! A10
11
12
13
+ s5 o, H! O8 Y) P' J14
5 ^, P( Q5 V& |; I15
& y" w* q- e. i, K  C( K16
" k  f- t1 U! u; f' U17
18
6 n4 K6 E, x# c7 |) x/ B19
1 p* L8 E3 |9 O6 B" w. J6 y5 ~4 w20
' a, B: I" ]& g( i21
22
$ t- \# @% M$ y) m23
# |7 n  M4 q' g6 r9 Z4 Z) p24
25
9 }" J7 j) z. k" W# C26
2 g0 ^* r) X3 u+ X# b27
& h# k4 U2 p7 q$ a% h9 W) _28
29
* o' j* w) m4 O" S30
- r2 `- ^) {7 U- y' X4 P3 {! a/ `/ G31
32
* c4 N, g3 w7 D1 {33
34
6 n, ?3 Z) p- w$ v# U35
( w" Z1 L0 |; X" @9 _) C36
9 E$ q/ C# Y/ r6 [% {37
38
39
40
1 x' {- c& P. E* T6 I41
42
# W! A) p+ ]1 @) g* H( {* A43
44
( ^* {5 }# b8 I7 ^45
46
性能

空间效率：O ( n ) O(n)O(n)      创建了一个数组b
时间效率：O ( n l o g k n ) O(nlog_kn)O(nlog
k
+ j" |& e) b0 f​
# S6 I3 R  d! b" K n)  k指k路归并排序。
2 {2 U( Q7 u; F+ Q. a5 ~2 v2 A稳定性：稳定

3 m! J# E1 V0 P4.2 基数排序
图解
2 E* i" `2 y) u! l  L6 ^% p* K
! Q; ^5 g! v$ }: W( ^* \6 q+ X, x- T
/ i3 S, V3 J1 ]1 m1 n! i. \: M基本思想
' c8 U9 Y2 Z6 N4 K
将各个位数（个位、十位、百位…）进行对比。
为实现多关键字排序，通常有两种方法:第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。
3 ~1 p0 L0 y( U$ {& w
0 N8 l0 Z. U( X0 `. u  Z性能

空间复杂度
' f# }3 Z* j9 _( x6 ?5 L- |7 R
# ]( Z$ u: e/ @3 I% ]8 R时间复杂度


稳定性：稳定

% A3 G  p5 \- x5. 内部排序算法比较及应用
- _% ?. m! J! F- P5.1 整体比较

/ k* Z- V) M5 F7 `( a& ?9 \5 D6 {
( y7 y. C/ T7 \$ c. ]/ j5.2 时间、空间和稳定性
4 v* A/ V' A2 m6 Z7 R: e7 r
/ H+ O. u  T6 f( `( B5 k8 R# K8 A
参考资料
0 b. T7 S+ u4 N" b6 g+ |《王道：23数据结构考研复习资料》
% x, ?2 {% @" ]% U9 U* J————————————————
版权声明：本文为CSDN博主「仔仔木」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_46629453/article/details/126078678
- K, W0 R& P4 U' ~  I& i& ~$ v7 i
8 }. V4 c4 s' C+ ~5 {; R
, B) h  G, v8 n' v1 i1 O

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5