数学建模社区-数学中国

标题: 十大排序算法（Java实现） [打印本页]
作者: 杨利霞    时间: 2021-7-14 15:14
标题: 十大排序算法（Java实现）
) h1 H* J& f- t+ `. K0 P2 Z; I4 X
十大排序算法（Java实现）) ]/ `+ e$ |+ L

" w% l' l/ V5 L3 }( V; u十大排序算法（Java实现）
/ y: f% h. C7 g8 |排序算法框架
' O" K& m* d  [排序算法性质" W1 e" _. `+ U8 f; i3 X9 M
插入排序
- n4 {  \3 l! ~直接插入排序3 d) r% p$ t2 C7 I
希尔排序
8 p( Z; d% i; {' V2 T选择排序
0 `  `. Y  R  \# g- l4 B简单选择排序- H. t7 d- T: l. c. F
堆排序, h4 U& w. O9 C( S2 c. I0 l
交换排序
: k$ {% ]1 m- T/ \# ]冒泡排序# u0 `" v  z) T& I9 X# \6 r
快速排序- Z; e6 s5 j4 R+ J/ t
归并排序6 B; |/ `9 r6 n1 \. n
基数排序! j. k1 ^; V5 ]' x
计数排序
# i- J, i/ }# q4 {' q- Q桶排序
2 g7 P6 F- P! b  v) A6 W$ G& b3 @+ \更多文章点击 >> 这里
4 d, y( u7 D5 B
  M) Z0 O' W. u3 O. X7 y  |# j7 [6 R5 E9 a# [
排序算法框架
2 G/ H% v; [0 ^: c8 k2 `3 H
5 q2 I/ @& M1 Q0 }' w$ \
& U( b' m" v- C7 X" j
! A& C" o3 ], Y- N8 N
1 H0 H. _1 b- s3 I3 k排序算法性质
# ]0 U) Q8 k+ V: ~7 B6 U- {. r. @8 ~; @: ]
) x" c9 a0 A  x0 e5 m  V$ T) W
& P7 T; H, ?1 C8 `9 G  o0 c

/ x+ m1 W$ d; K6 ?插入排序
* X1 K' D0 b! V# K, Z1 }# i直接插入排序5 N) h6 K/ L4 N. Z8 v7 b
从第一个元素开始，认为该元素是已排序的。/ Y; r7 |% `5 q- @; ~7 {; y
取出下一元素，与前面已经排好序的部分进行比较。
9 o* d6 A( {; b, ]0 }% n) T若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
# z* U5 i, z0 m% B. {遍历数组，直至结束。6 f/ ~9 \5 R; l2 y' v
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n 5 W0 H( V8 q: `# o; j
2
* D. N" Z  }$ G, h ) 。
( G  I3 Z$ O4 z! h, k7 E. X& v7 P* y$ ~4 Q* k( c, r3 U

9 M/ l$ ^" i' P" x  ?& o+ ~代码实现
) d/ |1 |: T' ~; T+ t5 E6 w! l, e) l" k
# c" [1 h  c) `$ T
public class Solution {! g, v- R" y7 T0 R
        public static void main(String[] args) {
2 I; X" ~! F0 u                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};! y7 [3 \6 E2 \# f: Y* Z
                insertSort(array);7 v" l4 S  ]* C* E3 Y" ~
                System.out.println(Arrays.toString(array));
, E$ H: F; W. S5 O4 F        }* f6 x; x+ J, x9 A; F5 y+ a( N
$ U. x# E. [2 u

) p9 s% S1 m) }* k5 O        private static void insertSort(int[] array) {
2 x2 I' N7 |- t8 C* y                for (int i = 0; i < array.length - 1; i++) {) d1 B9 x% {! L7 X6 Q* T
                        int data = array[i + 1];1 }- m2 Y2 j( N+ I5 \: p  `
                        int index = i;
9 H: K9 `) Z) U                        while(index >= 0 && array[index] > data) {
& l6 J' k$ M% A; y& {                                array[index + 1] = array[index];6 ?( I8 E3 ]/ }
                                index--;  S  x! ], ?# F( S) w: x
                        }8 m% I4 U, h, J2 F& V
                        array[index + 1] = data;
- z, O) j9 z$ _9 _# n+ S; I1 h                }
- X3 [- W5 `' [        }2 J" X4 E$ X1 S2 b# z' B8 s! o+ S0 ]
}
, f# i3 F- ^# l9 t1
5 d0 x0 Z1 E- m2* G6 D* v9 {1 H( l" }
3
$ ]. W0 v4 b: p( a% w' @4
7 N, L3 m( p6 [+ l, p5 ^) s* u! K5. F% K& \2 q2 K/ Z6 H  _, X/ C, ?4 G
68 i% U; e5 z+ ^& l. [$ P
78 w  s2 Z) e  D
8% }$ g2 K8 ~; p9 l
9+ w& ~0 o' W0 ^/ `
10: J8 h% v" Z+ U# N. [  [1 \* e
11
0 w1 G) h6 x! P5 A5 g7 C12
# z  `9 _/ \+ [) o13
4 @% l1 p5 r; T1 ?14' |* L* @, W  L. s2 F/ p
15/ X! W  b) l8 x" n4 R
165 d# M* S. }3 r3 l$ X6 M; k& H
17
) G( A+ W- `  R% T18- [8 N) `- E: ^% c' z1 x( q3 M' K  J
19
. \: `& s) L  W8 f/ R, f希尔排序2 r  y1 b8 `) g

. P5 g8 S$ S0 C) h% g$ X. @: {; s" u
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。7 V" O* A7 z. t; Y' n" [: F

+ b6 [1 Y; Z+ ~$ x5 f0 S1 Q1 {* b" Q% z. x7 ^3 x& h
代码实现: l1 ]9 @6 v4 G& W( a9 e" C

, G' Z5 Q4 p+ K' S: j2 b
& s3 F9 b: O( G$ `public class Solution {) X4 }1 O' c( Q4 F! c& ~) `  N
        public static void main(String[] args) {0 t6 f4 D/ H7 ]9 Q  v/ y& \
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};5 n: X$ U+ h. f- C
                shellSort(array);
  c3 x- I. f; x! M. ^- m                System.out.println(Arrays.toString(array));
6 U, G8 K) c5 R/ W$ d        }9 w3 j) ^/ p$ J( M/ b

) O; N# U3 y6 }3 s+ q  F; ]9 t. q. z7 p% x  u2 M6 E% L
        private static void shellSort(int[] array) {
" R2 `' q( `# s# ^1 B                int gap = array.length / 2;5 |/ O6 ]# U: f* v5 v1 G9 e7 r
                while (gap > 0) {& t2 i1 M- w2 n0 W. g
                        for (int i = gap; i < array.length; i++) {  k9 L9 m; n3 `' c& h
                                int index = i - gap;
& }0 x* f3 ]% ?0 j$ F$ Z+ l7 O                                int temp = array;' Q1 J+ g% y: n8 [# L
                                while (index >= 0 && array[index] > temp) {$ M& g* `2 X2 Q
                                        swap(array, index, index + gap);; ~2 @5 G/ H8 `& T5 g( _
                                        index -= gap;
" X3 d/ ~) z  K5 ?0 R2 j, g                                }; a; Q/ \6 ?1 }- v4 n; I6 `
//                                array[index + gap] = temp;6 a2 z- [% L5 @/ m, k* ?
                        }  |) K7 w/ G2 _+ T& H
                        gap /= 2;
% b0 P1 z: s1 @6 C                        System.out.println(Arrays.toString(array));: U" q& b0 }. L- x- Q7 A9 {; w
                }/ P# |' ]: e+ e& T% Z% Y3 C
        }
/ m& p/ X7 L3 R2 D0 b6 d' h( |7 J. R( H: X
9 C2 Z& z: f+ d' y
        private static void swap(int[] array, int i, int index) {
, @& D& A9 k: {( T3 N: R                int temp = array;
' n7 U8 w/ A( F0 F- W5 _                array = array[index];
: B9 m( N+ R4 d4 h7 Y; N                array[index] = temp;5 I5 a2 W% C( V' i9 ?. ~
        }
1 b8 n' C; T- c; c}
8 @; z# |6 ?# ]) |# U3 X10 T, x7 t( S( j" N; G9 ~! u/ w
2
% J& y/ E" D/ j- T: C  r- M3
; z1 _) _! S+ V, G" y- B+ A" y# _4! X( }) L# q$ n8 y4 B& l
5
# t7 c$ k+ ?3 Y3 W+ G3 X" g. Z6+ M2 k4 y$ `8 J* H' c! E! l3 ~
7& A" S, F# G# I$ H0 j# d8 S
8) l* H3 ^8 v+ r# `# e
9
4 z( `# q; @1 j: h" ^' Q9 J; o10
6 m2 o! A; x! U11# r, y& k* H! \( R0 t3 h4 L( Y
12" d: ~' D9 y0 G0 k" z
13
( A- r! W3 x% X5 U" h% G: W144 C7 L/ p, c9 _
15
' _) [  u( O# ]9 @9 G. w6 D* e16
  K! \6 [, {' |17; N6 k% \* }6 B0 Y
18& U4 Z* V+ e0 `  ^6 O( F- ]6 {
19* Q; {! }2 q: }; M  k
20
! B7 v1 |4 @( H! G3 E" D! e. ?+ U* N21
" i4 @- X% s) P( D% F22
( H6 H9 l0 q( m) Z* }8 ]" t5 L2 ~23; p. O2 S$ x( x1 {$ m* c
243 _. ^/ D0 N! \
25- _4 r1 O3 X- s( ]% k- w
26
/ T- U  o' F5 ?' H27
7 B2 U2 @. e3 W" V2 c) B  C28/ A0 l! |. P# `' A+ Q
29
9 k* e# R5 r& F2 H: @303 d! G% k9 N" ^3 d1 A% t0 W
选择排序
4 k& v3 l$ z$ L" m+ Z简单选择排序
0 w# _1 D! e% P% d. k从未排序的初始数组中寻找最小元素放置首位。
9 ]8 A1 ~$ p$ w- i从剩余元素中继续寻找最小元素，放到已排序序列的尾部+ d  y" a5 o+ L2 Q. F. C7 @: j% Z
遍历数组，直至结束。6 a( M0 r! {" w. _) B3 E# Y
时间复杂度为 O ( n 2 ) O(n^2)O(n ' @9 a+ q" [5 ]4 z2 n% [
2
9 F3 Q4 |( F. q; j4 ]- a: I ) 。; f1 V& x' n) Z1 \

. a) V1 Y' \, R1 P
7 K4 R% s3 w# c+ D, f代码实现**
$ B1 H1 w9 n: Q5 p% {' K/ A/ b
/ S1 C. E8 N, q  d- M6 [9 e6 ^% D2 i5 Z- @2 F$ N1 E5 i
public class Solution {
6 O) f; I# q5 K# U# q        public static void main(String[] args) {
1 B4 S% D& h. c: w                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
- v' }9 {( m! r                selectionSort(array);6 i3 p' j9 T9 e) f' m6 B
                System.out.println(Arrays.toString(array));  u0 Z9 g2 ^$ r: O3 e
        }
9 C6 B: b7 ~: Q0 E, E( q$ B4 B) s2 l2 J

. i( C& ?. i2 f) D        private static void selectionSort(int[] array) {) d0 M8 U% S4 v. J" H& I
                for (int i = 0; i < array.length; i++) {
3 q7 b1 E( d, M                        int index = i;! D  ?9 C4 P* s* p
                        for (int j = i; j < array.length; j++) {
# u& n: n, l9 J# m0 y                                if (array[j] < array[index]) {
" N9 D$ H8 @, T! u, X6 B  a" @                                        index = j;
. Q. q0 N- O2 x0 O                                }
: d% C+ O% z3 o+ ?2 f                        }
) x4 @1 P) f+ o6 Y( V$ k" M% r                        swap(array, index, i);
! y" v4 K, R! Z' {                }8 A. j# J/ D9 [
        }) W# J4 O1 x* W

* Y2 G/ P6 x5 f4 b( Y: `2 S% w: f- {( X1 ^/ s% p+ K
        private static void swap(int[] array, int index, int i) {9 v3 W5 p% A2 A3 z
                int temp = array[index];+ c& h6 T1 r6 T0 d1 r( `2 |; U
                array[index] = array;" }* b( X1 b* y0 Q6 X# ?8 {. R' k
                array = temp;
2 C0 M% a* W# K6 A  C( W$ Q5 i8 g4 S        }  z" @  b, ~7 L9 p& V6 }3 E6 T. S
}6 h3 H# P4 V7 c  b2 r0 K
1& P; S; C3 z" y1 ~0 A: j
2; P: x' p; \; n
3
6 T* O' {. h1 D6 V4( A! Z( b+ ]1 L, f
5
8 J; S+ A; l( H- d9 B6
9 V( {, s. z, J+ M) q" ^77 i% h) ~% j$ }3 _
8
' k' J* J! d* B! D2 K! x93 S3 C" R" _3 F3 k) D! y
10" N& Z. O+ j/ u
11
: ?# ?' c: T* E+ ~# s$ o+ \/ O2 o12
6 ]6 q0 Q' A  L% x13" s" O; A8 d7 K
14. }, o# l1 U3 I2 e; g2 [
159 f) I% j  k+ b" R3 C% I6 a$ |* {
16
- J3 B, k3 o" d17) ]  c4 N+ ?4 w
18
" _. k) t+ J3 l# ~$ t5 u19+ d9 k8 c. h0 o5 }( l
20
  m6 X6 J* d% O0 v2 P( N, Y& C& X211 Z" h" P1 S6 \! K2 v0 u. E1 a
22+ r# `8 C* Y! I! @
231 B2 C/ M* |5 b  A4 B1 I  t
24+ @) K* j* Z" n
255 o6 |! A  a1 ^# c/ P
堆排序; a7 d0 O& G. q
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。0 Q3 m# f3 U& @; E/ k/ g

9 L% b. Y4 k6 X* e5 u
$ @" i0 d; D  J0 q代码实现**
* q* X% ^7 q* I  m5 Y" F
9 r. h7 f+ s2 [
8 o0 {$ s. B0 p  n$ ^- m% o9 }public class Solution {9 [2 R" t% w" r
        // 建堆
" L9 ^) c& @# Y        public static void creatHeap(int[] arr, int n) {
' g% s6 z+ T6 i/ K( G                // 因为数组是从0开始的  K0 l: _; z5 F" P# V9 x" t
                for (int i = (n - 1) / 2; i >= 0; i--) {" L0 b  e+ ^( t$ `
                        percolateDown(arr, i, n);
" W' K5 J' T4 q% G                }( E4 |$ |' _7 d" I7 D* w8 c
        }
2 s+ Q$ S# `9 g8 L, B        // 插入# I) R& i9 P: V0 l, ^1 F
        private static void insertHeap(int[] array, int data, int n) {% p% q) A% a6 v
                array[n] = data;- z% |( O+ i8 b4 O) z' s) c
                percolatrUp(array, n);/ r5 \5 a) T$ w9 ^
        }/ v4 T, F" Y! z8 j$ h
        // 删除栈顶元素( `/ f0 f6 b% D) \6 Q: O( s
        private static void deleteHeap(int[] arr, int n) {
) W6 S! {+ n  p/ J( Z) k  G2 r                arr[0] = arr[n];1 c4 l5 I' L  \) ]' l2 g
                arr[n] = -1;
* V' T5 \! {% g/ k1 J2 Y9 O/ O                percolateDown(arr, 0, n - 1);
$ t0 \' d8 `4 X4 K- ?& @        }
+ v/ _! ?8 d0 L4 R0 o. Q" X        // 上浮
0 d" c/ h1 @- g# x8 g" S: b6 w% T        private static void percolatrUp(int[] array, int n) {
* @1 D- R" `/ T) J                int data = array[n];
& z, v7 V) R! f$ ~7 X) l                int father = (n - 1) / 2;
7 |/ }4 m$ X$ v$ b5 Z, r                while (data < array[father] && father >= 0) {
  n2 f) \- v& b$ f                        array[n] = array[father];* \4 `: l' ~& S7 s
                        array[father] = data;7 A8 R$ n: b* a' \
                        n = father;
/ Q4 Q& j- ~7 Z  d9 o                        father = (n - 1) / 2;
" n0 X0 n( N5 a4 {) M3 g$ A                }- }6 s. \) E& U8 C2 y6 A  e* k
                array[father] = data;
% V4 a+ `9 e( [) l        }4 P% }6 }( Z2 M5 i
        // 下滤) t3 s; x- F: [3 g7 a  v6 k
        private static void percolateDown(int[] arr, int i, int n) {* `' b- x8 Q: g$ B9 C& T  y
                int father = arr;) M3 l3 }+ E" s: _
                int child = 2 * i + 1;
, n+ K$ S$ [+ w+ A                // 遍历整个该根结点的子树
& v. F5 X+ W/ N7 X7 K) d                while (child <= n) {$ P) p6 ]- S0 m0 F& T1 r
                        // 定位左右结点小的那一个" D& u4 o+ Q, v8 k& F
                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
. p8 C$ s% p! E9 c: l7 E+ a                                child += 1;
% t7 `7 A: L8 `& y( D. V. O+ X                        }; L- G! l4 }5 }8 W
                        // 若根结点比子结点小，说明已经是个小堆
+ _% ~) p1 n: V3 L                        if (father < arr[child]) {
' Y- K7 S9 E" S; j; W1 `/ [" I                                break;: Z$ j  @9 M( s
                        }
3 ?" }- M& V& n                        // 互换根结点和子结点
! p' b8 I5 ~' C7 h* j+ L% a                        arr = arr[child];
; J- m2 h4 z5 z5 t0 @4 r1 k                        arr[child] = father;3 I: q, _  p* M- f
                        // 重新定位根结点和子结点7 |8 _5 T7 l& N
                        i = child;! g* g' z  `. f+ g; q8 }
                        child = i * 2 + 1;
+ G2 ^4 ?8 t! N+ c0 H7 J" @5 y                }+ ^4 r8 h: L2 ?. L
        }
" N* }- _; M4 R    , P% ^% I; E3 e5 r/ u
        public static void main(String[] args) {
5 h+ v6 P8 I, W                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };9 q8 Z  k0 c# N* F
                $ y1 D) D4 k' l' q! A5 i, Y
                creatHeap(array, array.length - 1);3 @% [5 I0 b$ V  p, A
                System.out.println(Arrays.toString(array));
/ |3 Q* Z  c9 N( {" f                6 i+ n* d2 {4 b, z& \
                deleteHeap(array, array.length - 1);
" {! @# m, N5 \  e1 [- V                System.out.println(Arrays.toString(array));8 F. ~0 l& m6 n
               
( ~7 ?* Y- {' Y; }& V  V2 F: G; T8 L                deleteHeap(array, array.length - 2);
/ x9 q% ~0 E# ^                System.out.println(Arrays.toString(array));
' V" D9 S9 v  b2 v               
5 B) K! O' o2 K& i/ y  q' u; ]                insertHeap(array, 3, array.length - 2);
' v! W$ L5 Q1 f3 Q                System.out.println(Arrays.toString(array));/ j1 x& b9 F& P6 g3 V1 l
        }3 S% Y9 T- {; G! |
}
/ x( t  F5 s: d6 X$ T$ D: v1
& A3 @: {& C) B: P' c' I0 y2% C7 ]* I0 ]# ~+ S
3
" U' p  i2 W8 d4 F( i4
8 g6 S% D! ]0 V5
" f# F' c5 O% |9 T3 x0 s6
* ^9 g' z- Q( m( w/ J: G7
% t: \- F3 c* A- a0 @5 L5 ]; N8$ F  V! @9 L; V5 }' y& F
9; j: W' p: }* i
10
6 w& X3 q% o% z. O2 D11
) A# t. I/ S/ E; z5 H12
2 {) J, V9 g! r5 y4 ~9 h139 E) x. I; G9 Y0 u& h* R0 b" R
14
& [1 M0 m5 e" ?: B4 B1 m15
; c$ c: r+ L+ Q165 q& d; a4 q) \6 j
17
8 ~9 R) h. S1 I8 a$ c  Y" |+ m9 u18
3 ?3 s% r! D8 n* S0 D" Q199 c' e# g' u$ c. S
208 F! r) b" `5 [  m: y! |
21
: n4 l& O+ C5 g0 d( g7 I5 d22* h* l: v! \  @4 c+ o3 X
232 Y2 t' y) t3 Y% M) }' J
24+ ?- v, j* ]( Y% O1 q# O
25
4 b3 q7 H- z# p+ L, T26
; a+ f1 P4 q+ E27" h& ~5 O0 W6 J! D+ W! n% R
28$ {, \& U. \5 w3 `) S4 Z
29- x- L% u* w2 k! N* ]7 |
30  r0 J$ d4 ]  Y- z. Z% [2 n
31  H3 v* G% O( O9 X2 q5 L/ J
32( n% }! e' O8 k8 o) L1 T
33. \. H( i) L6 X8 W0 ^$ l( X- u- b
342 f' C5 ~+ \8 Z$ K. h
35, l6 k) W6 j% b7 G& L) X8 G5 X
36
. x5 l: R9 T+ [2 c" R: k; \+ u+ B37
6 W- c7 C8 E8 h: C$ F0 P+ a38# ~7 b4 [- V- e1 B) q. q: q
390 p9 l, r2 f/ g/ ?$ G
40! w, r1 Z6 y% s! T
41
+ U4 y( h6 a2 [) w( ^+ Z/ F' _42
1 G8 U5 x  T+ i- s) o43
0 ^1 M5 I' J9 B44/ ]9 R7 K, V& k7 k5 h% ]( g
45! H! ~# t* u7 ~9 d6 W
463 X1 R, ?& E0 }% ?' W: F8 S
47
' g! o* S6 [$ i48& o8 A+ e3 ]% e
49. P' g! D8 y8 v
50  Z9 Q* E2 q5 x1 O- U
51
. M8 p: t. z1 a0 R- S4 S5 P52
, y3 k( O+ L$ I) S53
7 Y- @+ m- k+ F, v54  z* }# z5 d  M: l
556 B1 n6 l8 O7 X
566 _, q( v  j6 M
57
6 J: {$ ^) M+ h2 Y: u, _581 G! Q: V7 s* d. I4 G
59  X: [& j4 _7 J& Z& c
60
5 o  n! a7 ]! R$ E616 g" _, u' H0 K  ]
62
; \! n$ E! V1 L* ~4 i63
4 n: Y4 X" l# ~- u; V  n644 J9 l' s4 y5 r* M  ~
65" Z8 O- q+ G% }! d% i6 z( T
66% B& e) k; p2 c* i' d
679 d3 }6 O+ C7 f% z7 I8 R* a
68
5 }: d* b+ B! N0 {690 f! V, q/ h( B) N/ `3 Q' z- w; O  r
70( n+ N" v" ?$ ~' I6 D& h' g1 X
交换排序
/ A+ d6 t' X; b, R, g冒泡排序9 {) e: ^5 x. ^+ B# M7 r
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。: I3 [4 Q- ^% G  u1 n
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。3 a" C. j+ B8 r; M0 S' [4 |
遍历数组，直至结束。2 u# R  R5 P7 X8 ]/ a4 H5 y
最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n ) \5 P# _4 V$ q
2
0 B, N8 j& X  {: h$ c8 z" ^. V ) 。
5 a" _" K, o  ?! t5 _+ W6 f) i7 \1 ^/ v: Z6 t/ ~4 }
9 ?4 G% b( ]& h- i
代码实现
, G  s( b' ~# U, E8 P1 d7 O" d8 v+ C' _+ z+ i% H
$ K1 `9 ?# q+ q; e7 ?3 U$ m
import java.util.Arrays;! ~7 ]; L$ N  U7 U0 w+ N7 D
public class Solution {! O& b' x2 \6 w4 E  P
       
# M; R  J. i0 s. L4 `' p+ n* ?! o- j        private static void bubbleSort(int[] nums) {
( t  l( b: r) D                // 循环次数7 g- r; T$ u; }* C) Q
                for (int i = 0; i < nums.length - 1; i++) {
4 _! p! Q6 P# ?3 ]4 d+ `                        // 比较次数3 e' j& C6 _8 i& [! ]
                        for (int j = 0; j < nums.length - 1 - i; j++) {* ?9 F3 s: I6 X) G5 A# N
                                if (nums[j] > nums[j + 1]) {
; I& c: [' r7 {  e3 @% u7 ]9 v                                        swap(nums, j, j + 1);) ?" H; U9 D+ s8 r" \
                                }
& V6 V7 q. N! n5 Y$ L7 t( x' M+ L9 b                        }
6 N! F3 M' V+ U+ z) D5 O" N                }$ }" O8 Y3 f2 N* T% _6 J- j) M2 U
        }
$ W3 G4 L- u4 E
# m5 Q9 ]) O# D& Q9 {; V
6 |  L. [8 Z) O! @& \( l( T- a        private static void swap(int[] nums, int j, int i) {+ }6 |3 N0 a$ ?* G: L; }, Q
                int temp = nums[j];7 C; m( i+ K6 Y! I. z
                nums[j] = nums;
. S: G/ ~; h" k3 L! T$ d, g2 A9 f                nums= temp;
- t5 C" }8 ]& g        }; p7 s# P0 P) c" V& O# R- D

( B& S- h( A" Y, ^" E# b# N( n; p! t2 ]4 o
        public static void main(String[] args) {
1 @& y% T  L9 {# \                int[] nums = { 6, 3, 8, 2, 9, 1 };
- w4 f& N% x5 Z4 z                bubbleSort(nums);; j" O: n; l+ ^- B7 Q* Q) M( }% Q
                System.out.println(Arrays.toString(nums));9 |4 l' P: h% [# G; i# M
        }4 P# C9 k! X) o5 Q
}
, R5 d& t( N1 F* [6 o0 D' M1) s5 A3 F& v' {4 W
2! d2 |. F& D8 B) U+ b, [" M
3
+ Y2 o- u2 ]6 l5 I( Q- h4
' B: ~8 [* T9 k5
% k/ z3 ^* B+ U. Y8 X1 r+ `. A60 J! q& @, V1 r& Q" q+ g9 Z# M) k
7
7 ]. F+ ]0 x, o7 ~2 y6 g8, Y4 ^& d, s8 F( T3 n; l: ?4 x
98 V8 `& ]8 ^# p  d: s
10
3 @6 D9 B5 ?1 |1 _% w11/ E) r) L# L! V) D  G( u
121 H4 v5 ]& a/ r* R0 e% D
13. P# \( C, {( s8 T2 g7 P5 ?
14
5 |* j( s8 |' E# w* w4 Z15
3 J- I6 [$ _% b2 s! d$ R16: C, W0 `8 e$ d+ e6 u# C
17
' T3 j/ r7 |& l  j18
4 y, p$ v5 _0 ?9 G2 B$ y8 P. l) l% x19; n+ O) E5 W) I4 u
20
& @* O; |* K" o2 e- H) q21
4 l, S+ Q+ M" I% I2 O- J22" ~* u- K5 s  v. E2 A7 @2 Y" P
23. F# o$ W: h. O# A5 D6 m
243 ^& E* @( P; y( ~! p  ^- }
25* Q% h2 u1 J) z( B
26
# u4 s0 K9 d4 f  r$ }276 X' {% u8 Q5 c! p. a% N( b
快速排序9 f+ }2 z5 }$ }5 n/ O
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
+ S) y) `2 d' T3 g9 F2 }) n6 r9 F8 G% x
# G* c, p/ x( F% i) U
代码实现* ^9 I+ t+ {; u' K7 s
' r$ V7 L& U; Q  `
( S- `; ^- ~. g& d: s
public class Solution {1 S' o$ q0 B+ `9 g  T6 X
        # f$ C, I( [' c4 Z* C
        // Median-of-Three Partitioning
7 _6 F8 P. O' m% v        public static int selectPivot(int[] array, int left, int right) {' S& N) d$ |7 b2 P7 f9 t
                int middle = (left + right) / 2;
9 h; F. W" f% _, \                & @+ p) Y9 F1 C, D6 Z
                if (array[middle] > array[right])! }9 k3 i' G1 k: M! e4 g7 `
                        swap(array, middle, left);
5 N5 s- [; p3 L% m2 _7 I                if (array[left] > array[right])' P( x7 J2 q+ L+ O. F
                        swap(array, left, right);2 |- m1 P0 B8 K$ \% H' b: ~
                if (array[middle] > array[left])
1 H% |7 w+ f9 k                        swap(array, left, middle);
) T# X* i- x) x  l9 X                ! ], ]" F' w+ n* ^. M
                return array[left];  R: {+ X4 L' N- O' M4 {+ |
        }
7 c+ U" n  R# g+ u3 ]3 C       
  e. ]5 E) v( D5 t" b5 S        public static void sort(int[] array, int left, int right) {
" G6 M! w, P0 q) k( V' b                if (left >= right)3 l" k% b4 J* G4 c4 c+ M* E' g  i
                        return;
4 L7 y; m4 F/ o" s7 @                int index = partition(array, left, right);
6 G+ v9 M2 c' E% B. d( Q                sort(array, left, index - 1);
+ a4 `6 P3 a+ R4 s8 O0 G                sort(array, index + 1, right);
6 O$ L1 x. ], C  l  q    }7 F* O% G6 D' _( I) Z
       
0 f3 g' k! {& z, X5 i  u        public static int partition(int[] array, int left, int right){
7 F0 X3 ~7 J' [9 M        int pivot = selectPivot(array, left, right);
6 F% o# N5 V3 x  t3 Z9 ^' S        while(left < right){1 I) k" \5 J) \+ A/ K  G' G
            while(left < right && array[right] >= pivot){6 v1 G8 c2 }7 `, s' h# P& i5 Y
                right--;
" q; K! j1 Q1 r: r: V5 M            }
" s7 @3 ~' y) Y5 N) A* U            if (left < right) {6 V( T) t- q5 H. [
                array[left++] = array[right];
9 w* r3 B8 p1 E) O3 U            }5 ?9 `! z  v- t, g/ ^
            while(left < right && array[left] < pivot){
6 P* ?/ z. ^% j! p% H) h0 P8 N                left++;
- f8 t# e/ Z. P: h            }
( u0 k7 E9 C; `7 e3 `            if (left < right) {
* s1 a' w. O4 R- ]% m, d                array[right--] = array[left];
3 S& J1 F+ q8 I1 a# G8 s5 e            }
& V7 M) t$ }( Q" r9 s" w        }9 Y: j" w# r% E4 W( G. ^. C  c6 O
            array[right] = pivot;4 j+ z" C; |/ K' i
        return right;
0 N9 C4 w5 p/ z9 H8 X3 I3 L! ]- [    }' o4 W$ N0 w, W4 a6 K& Z
9 g, E" g! \( n  A
" ~# d7 B7 {8 I" ~1 {$ j( p
    public static void swap(int[] array, int left, int right){
) H- `9 ]6 d6 B            int value = array[left];
/ |2 f# u+ _: z3 |- I- G$ K* \            array[left] = array[right];
! [/ o1 T; h& {* o3 ^# D            array[right] = value;* N/ z$ f1 R" i
    }# r% Y/ ^( F: d3 P( W( X

2 a+ L3 C' z; ?% u0 g1 i
+ a" P7 `8 O% J2 u5 S0 }        public static void main(String[] args) {0 W. m8 s8 i( |. M' j
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
9 @5 d/ ^2 V6 Y6 I3 [# c3 v1 H                // System.out.println(Arrays.toString(array));% b9 T1 V* \* A. B& _5 s0 G
                sort(array, 0, array.length - 1);
1 y, V$ A4 \1 r0 B6 n" @                System.out.println(Arrays.toString(array));
+ g  z, r( e7 j" G        }
! A( N4 ^. G2 Y+ l$ f}
- K2 Z) T! v" s; D5 L1
% A/ O. O* V7 E; u( t7 X$ e2* `; c- F, A2 V% T( i
3
" P* i( `8 K1 o2 |42 F1 z+ M) z0 O2 i/ D7 q" N( [
5; J/ x8 u7 S9 ^' u! W* v
6- T! l4 @, q3 e7 W% I& \6 w  b) E
7% ^1 B, [+ M$ \2 A4 y6 d( v6 o
8
; I  o; p6 I4 B/ `9
' ]  g2 G9 S6 x+ P- @' ~10/ \/ R1 K4 d. w. @  v& P% F. _! D( n6 W
110 _( g+ j/ M. Z$ k  H2 y: G
12
/ I5 }( I, s: `) Z) d13
9 H$ m" R5 u5 G& }14
5 ^! }  l7 v5 t$ e2 J" _15+ r3 _" K- m9 P1 c! q# c. g& R( |2 ?
16
1 M# \1 r6 d) }; j1 e1 {172 W' S9 D. J; _
18
9 e0 T7 h* x0 X. V, ^8 K# ]# [# X19; b! O% `3 W& I, n6 m
20
+ V  {' x* S, V( q! |! G! i21) W0 K* x' e$ U7 H
22/ P) d6 E6 O( I5 Y
23
2 j/ Y7 L; l2 b6 w+ n$ Y24- {2 b) O- k3 i% ?1 W$ j
257 H1 ~8 v: B) V
26) [: z7 W/ w1 n
27
9 \+ j" M: Y- G/ i28
7 }: a) O$ i9 e8 \) J: H29
; X7 Z. r4 `2 Q0 C  w. Q' j309 c. |1 E. D3 x9 h6 X
316 C9 ]8 G: ~# I& X
32
1 n4 c! t* n" d6 s33/ z* p: b3 a2 T1 a# a$ ]/ |0 |4 G* a
34
4 O' g0 _+ ]7 J35
% A, n: u, Y3 d! D  X0 C36& @* O3 n! s8 u% w, i2 C  ~
37& u* f5 H& h" i) a2 W3 j
386 t0 Y8 L: _* p( i
39
: x1 o2 P5 _% H+ G) s40
, q& T6 f( e9 H0 G7 Z  v41
+ X% a5 F) @5 ?& F) g42
2 Q( q, s& [! k  I! C: q1 C( N- l43
4 e* q" D% L/ i- N* c9 f; I: J& W44
' |+ R) m) I. x+ j7 h45- ~% D8 B1 Q0 `% `) I
46
: b) A7 i# w# c; y! E& m/ Y47
1 P' E7 F2 g! ^  u, Q& x% ?7 p48( m5 b8 U( i/ M/ o, I8 t" |% V3 R
49
9 @! o: i% i) l; q9 f; l+ t50  E. c& q2 c0 L' N, v
512 X" a) T5 K8 Q- m) [/ X, E
52- L% ~2 Y* Q+ V& P1 t8 R
53
1 {" T- a, _, A8 j. |1 [54
& g! C! c! k0 w0 Y# c; q" n55$ B3 a4 c2 ~+ e
56- {, m8 ^' W; Z/ u: u
57/ d2 n% I2 G4 ~( d- k( X9 {, }' `
归并排序, D$ n8 \! f  {0 c5 X* |" ]) w
将长序列从中间分成两个子序列。
4 r% S* q0 ]1 R, a  x对这两个子序列依次继续执行重复分裂，直至不能再分。: ?' o( _5 `5 B
递归返回两两排好序的子序列。
/ \2 Z, e6 n7 V/ m$ m平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
7 b. R- p! M: {/ j! r  Q
1 @3 k3 A; O1 P# {) i  V; a- L# \) P7 W: g5 V
代码实现**& Q- Q' u% u* T! v( a- L

7 V. S* z2 u7 x" K4 u$ R7 v- Q2 N. d" F0 x4 F
public class Solution {
* Y* [. b. _! h/ Q7 N        public static void main(String[] args) {
, H4 A! J( ^4 C                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};: ?" ?8 R+ I( J# k) `! O. Z" ~
                int[] arr = MergeSort(array);
1 O7 x6 ^3 b8 a5 N' w                System.out.println(Arrays.toString(arr));
6 d- y" V8 O2 _. a, q  Q        }
* W. _6 q  r+ @  D8 c* C% @* L6 I* I$ i2 C
" P  {7 d! r' a0 ^
        private static int[] MergeSort(int[] array) {
; D. h8 @, C5 T! W) N. S                if (array.length < 2)
1 w9 M- ?. i  Q6 O3 |! [" X3 z2 n& y  A$ ?6 p                        return array;7 \$ C( \0 |' F: u, K, P' N- G
                int middle = array.length / 2;
& r; {: F9 T, h7 H4 U# R# h                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
; q& {6 ]; x! r, n' ]                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);$ o4 G. q' O8 v6 m( G
                return merge(MergeSort(leftArray), MergeSort(rightArray));
% H2 x/ o/ T3 I: \4 O        }
2 X4 }9 J7 h* O
+ W, _* Q" m- Y% ?: x% }; p+ p3 k/ C0 H) a
        private static int[] merge(int[] leftArray, int[] rightArray) {
3 X7 ?: q7 L0 m6 a" j8 ^9 U                int[] result = new int[leftArray.length + rightArray.length];
2 O, t2 x: s2 C! Q5 p5 ^                for (int index = 0, i = 0, j = 0; index < result.length; index++) {, x. S6 v& y- Z+ A5 O( a4 K7 \0 N& ?
                        if (i >= leftArray.length) {
+ B" N: Y, X# Q9 g: p# l                                result[index] = rightArray[j++];' c" ~: K, E2 x/ \  g
                        } else if (j >= rightArray.length) {
# b5 \; X# y+ g% P+ O                                result[index] = leftArray[i++];- n5 e0 [- A2 o" ?; n
                        } else if (leftArray > rightArray[j]) {
1 R1 Q! J+ D/ }# _# B1 Z+ L                                result[index] = rightArray[j++];  O4 r6 r  r% I! y$ s2 }
                        } else {, |  q! v$ I, V0 k5 T) M: v
                                result[index] = leftArray[i++];
: d6 X  u8 _8 j; R2 |                        }% d, t0 m$ {. ]
                }
3 k/ F: F! i0 k5 d                return result;$ s3 f6 N9 w) z0 K- V& c# g; Q
        }+ E* p( q: e- x$ q% B
}
) x; _) O7 T! O
* p- \. A9 x, s0 _9 n" G
' i: {: `0 i* L4 q- M1
$ Q2 |+ ?  U8 ]5 M- c9 D2+ X- _; q8 b! H# ^- O* T! T# r  I" G
3& B& P& w) |7 S' I9 `' @
43 A1 `+ }5 U6 _1 y0 y. f4 Z
5
& {% s7 f2 \1 P6: j& A# W6 C/ a) H
76 C+ |6 w0 k$ |) _: b
8
* `- |; ~4 ]9 w0 G! q& t96 v( u% r- a# W$ F/ p
10
8 Q' v- a1 F% R8 S2 `11( |: f9 Q6 r! s" _
12
8 q' h4 Y/ y+ U13
% i& ]  _6 ?( {14% ^& A8 @/ Q6 R5 ^' Y" ~
15% ]" w9 ^5 _6 s/ M- U. d
162 p3 Q2 ]! d6 f6 i
17
4 n* z4 y0 ?4 [% W9 |18% I" U1 `8 ?  S4 X  O$ N
190 Q% |- u$ x* r6 [
20# N/ A# e3 v- e) ?& m9 J
21
9 g. q" m8 T. L. t0 {3 b6 S1 s22. F. C9 m! e4 p4 a9 @
23
$ O2 _- q6 j  O7 D+ R- b' t' t24
5 u7 w; I" W- z3 A25
% b" j# F7 M, ^; P# r260 |" L7 i9 Y: Z5 o
27
3 p9 t9 ^( L2 _: P$ Z285 S2 F9 y! t3 N
29
; ~5 @3 L" Z$ E; u, m# f* F- o30" _# r& V7 H: U2 G4 Q- u. U( d
31  T/ D) O1 _" I; Z3 W9 t/ F
328 Q. ?. I; R+ v' ?
33/ x4 {2 Z" z& H' H/ Y8 v( G; W- [. Q6 M
基数排序3 `3 T9 [2 n5 M: Z( o
找到数组中最大的数，确定最多一共有几位数。
% n" r: a0 y$ n1 R3 m/ O0 u按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。% B# F' F' D& J* c+ S3 e& w
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。2 Q7 f  p' N# p: T
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。  d' a! t( Y* ^: w0 H( {
5 b! w. A/ t$ ?) w0 p0 ~4 W8 ~

: \( f# m. ~0 E8 L/ c代码实现**2 z% \  Y# I4 ]/ b: R, F- ~" z) \; f

. ?$ ^# b2 z  N: s* l( @  t/ r9 O% }' }1 c' B$ V
public class RadixSort {1 R9 D5 C2 M8 [3 U& g4 x

$ r  K, E, V, [9 l5 v: X; |" y3 Y0 |0 y- D- c: H+ T" E
        public static void main(String[] args) {
  o0 b, f. k& s0 M" ?* l) c                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};2 I: o+ c2 ]! Z2 X8 y
                int[] arr = radixSort(array);
( E/ z3 x& |6 j                System.out.println(Arrays.toString(arr));
7 Y0 \) ]5 A  B9 l        }- C6 p& E/ q5 f

* L; c# L% s" P: Y5 k) x+ ]8 Y0 R' F: |  _
        private static int[] radixSort(int[] array) {2 K. I% P  ]/ F9 ^6 C& M
                if (array == null || array.length < 2) {
- i8 y+ K+ N! W+ e  b4 g                        return array;0 K3 K1 w8 m2 w* |# d
                }
% `2 w+ [; `$ e' Q# O% G( H                // 根据最大值找到最大位数
" Q' I; Q7 l; |# Q  ~                int max = 0;
. {5 z, O" D2 ?                for (int i = 0; i < array.length; i++) {1 M6 c7 M9 B, f
                        max = Math.max(max, array);( P9 l+ L& j. P3 W) W, H3 F5 h
                }8 ~1 U+ G- V1 y& z8 h% T
               
$ ]% H$ J! y# G' W2 s                int maxDigit = 0;) V" T1 u0 ^4 P. {6 p! e8 q3 q
                while (max != 0) {
% h! e! ^* h8 ]: H( U, E                        max /= 10;
- d' k" b; o" g1 f                        maxDigit++;
/ b. H  g& u+ t8 e: t                }; c9 V3 m$ }2 Z* [$ n" m" C
                5 L, ]& y/ J$ X% T
                // 第一维: 0~9
- P2 ]- e2 N/ `# j" |                int[][] radix = new int[10][array.length];
( ?" p2 {) S1 ^                // 该位为 i 的元素个数
# u$ w+ R7 n5 k/ b  M0 L                int[] count = new int[10];
* V1 M* C* K: y$ G$ ~               
* h, y. H% H4 P5 B1 N1 S                int m = 1;- N8 u! Z4 n) r# P$ Y- Y; h; B
                int n = 1;
* ]" L# u5 d+ d& `                . c# R5 J! R0 X! W7 u# C; @
                while (m <= maxDigit) {
( S# x# k9 H$ P# T                        for (int i = 0; i < array.length; i++) {- S7 ^$ @$ W8 P+ X7 U: `* Z
                                int lsd = (array / n) % 10;
! R( O* R$ o8 @9 d                                radix[lsd][count[lsd]] = array;
& @6 s1 `/ i& y. o' u                                count[lsd]++;
) R3 z4 `3 J3 o+ N, S; v                        }* Q5 {8 b5 t; s( h+ b: E% I- [6 V& r% W
                        for (int i = 0, k = 0; i < 10; i++) {
& l* C9 ~8 U, a4 U8 C                                if (count != 0) {: H) N) J# e7 I; b
                                        for (int j = 0; j < count; j++) {! G- `& p/ U- b3 r# |  O& m" k
                                                array[k++] = radix[j];
" L* }# l2 D2 D6 y- R                                        }
6 ?- w9 T4 B5 M% N                                }  Z  K* {) D! F
                                count = 0;
+ e* J- m6 H. @  M                        }
, o9 ^. T& U6 T5 Y7 ]2 _# q& f                        n *= 10;3 d6 d5 v1 y6 c
                        m++;( h; ]4 N3 G" ^9 p8 t4 e/ T
                }: L* L2 V8 E! u+ q! a
                return array;. P- w: W) }- `- R, ^0 G: G
        }
: }, q: K# \: Q1 y3 |: J; M( P! _7 ~  |0 F5 m+ s0 g
8 p6 }  V/ r* c3 l
}
6 Z# V6 p+ H2 r; H4 i1
0 u0 G! z) A9 W% {5 E( B2
  D5 k/ H4 j$ \6 s: d$ l37 [1 Y8 _- E1 r6 [
4
+ d% h/ o, w9 ?0 d, g5$ x( S: c* @" B9 H$ a% N
6
( [; f# c$ {9 F! i. ?/ H( H7) Q" @: g. d$ f$ Z
8. R/ k+ j! \7 y/ ~% K+ K( O4 w
9! W7 e* X3 m' ~' g) X- V( _7 S
10) o  l% k* |/ z2 e
11( {( o7 j2 N$ M  j, f2 _
12+ K5 V/ i% t9 _
13
- Q& [3 ^" b& z- [1 o2 J5 k14' K- M, p) v! D5 d" t. @
15
6 H8 e) g3 @; Z/ p16
" V) }6 F& s2 t; w( u! z3 o: l! O17. m+ m9 o; O% e: V4 x- i9 g! e+ t  N) @: o; x
18& I; a! Q. M' c- G0 ?
19  b  F. f3 M( `, v4 w5 j5 [
20" ?+ X0 f  F* \6 b# g5 N: V
21
5 v( t+ Y" W4 l* `9 d2 B229 U" i( H0 M0 E- u4 E: N) z/ _
23
6 V, g9 ^9 [3 [2 \- t  n24: }2 g4 v+ L" @. \
25/ \( \* H7 v* |0 z& d* E/ x
26. }0 @# p' h3 A6 G( Q7 k
27" B9 m6 x/ S# k9 v
28- L3 p# c6 {1 c% c/ L) y" T; b
29  [5 U+ m& g+ S5 S2 S4 k; w$ P5 s3 m8 A3 ?
306 s# d9 V  p3 v2 y- b8 S+ y
31- G8 t) B& F% o- n- L* f7 x# v! |
32
/ g6 d$ X) A( G9 a- `# a33
* }- ?! R: [5 T( P3 e# o4 q341 f' t6 l9 T) W0 a4 ?
354 h: o& }: ?& L; y
36" W& a7 q- {( `8 {# ?' ?
37
) U1 x# S2 s: w& r0 P38) u& b0 W6 @; b  _; K; U+ m
395 v; F$ j! ?7 c8 d$ p
40
) t) t$ I& {! l% `6 ^  z/ M4 p/ W/ f41/ A3 U' r$ _% t+ g
42# R* s0 l! c0 m6 J( j# P0 w+ L
439 ~+ N/ B7 z+ M9 r3 ]. H
44
$ B- N6 ?( w- _. I45
3 T0 i; a2 T- U46) X) d" I3 B" z2 H8 X' G. C; c8 q
479 s$ B$ ^- b; v/ K) j2 O
48
3 D7 q7 y4 ]4 k. y$ F- l/ w49: l: T. w2 g  I) N/ L5 U
506 Q  h2 [: i" ?6 P  Q
51
6 o5 f* E  E) L6 a4 Z; S7 Y52
) N* P: _$ I" R6 B53/ e8 b8 |/ V% I8 R
计数排序
# l5 q3 J0 s. P/ _  J  [找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
- y9 f. P& H0 q) q. V! W# W统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。* H  p) h6 l$ ^  J4 n
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。* @2 D# w3 P$ o# ?/ B( T& C+ s4 x* C
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
9 f3 B9 H0 U& j+ a6 ]) w
% [* n" s4 R3 _" o8 ~
) M( D2 ?/ K# {( s- ?代码实现
+ L4 @0 p5 h; |" A, ^( e7 R* i1 S# t, U* s
2 N1 [8 e- G% S5 k4 Z3 @
public class Solution {7 w/ s% |# F1 g
4 i! C, n" Q. `/ W4 Y
' _( j% a2 t& q6 E* V
        public static void main(String[] args) {) B; r/ s, K3 a1 W% [% I3 I* Z' A
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};7 m4 O' p( D6 E* Z3 S& p0 D
                int[] arr = countSort(array);" H% o- r# w& D, d  ~; M
                System.out.println(Arrays.toString(arr));$ x, v( }  s& p3 H' z3 ?
        }
$ o! U% [' [3 H$ C1 T- \3 x6 M. x$ l7 C& e* `% k8 `5 B! y
+ n7 ]# p- s  [6 |
        private static int[] countSort(int[] array) {, j4 X: l; K+ I8 u' d
                if (array.length == 0)3 z! h0 D1 |/ [/ i
                        return array;; l9 x, v* a# s" N) \$ a$ M1 f
               
# }! b0 f( K3 m/ J( S                int min = array[0], max = array[0];& m& t% }$ }; t- |2 M  w7 j
               
: {+ g, q+ ?% @                for (int i = 0; i < array.length; i++) {
6 C1 f% x  P. {1 `                        if (min > array) {8 {3 T0 |0 i( B' }8 G
                                min = array;
3 F5 Z/ M% H4 V' r* q, P                        }. V) f0 ~% B) d& g2 {6 n: A
                        if (max < array) {3 h4 x8 [& N" R$ f6 a
                                max = array;
* g& o9 ~% f, W& i/ ?& S                        }/ [/ C; j- x' Q0 c' d
                }
. [4 R7 S! D: g* a: g                8 i# G& C( V. k! ~5 d
                int[] count = new int[max - min + 1];
& m8 U$ j- E9 m- i' G, l# z                & U' A6 g5 j0 E: Y8 p  ^
                for (int i = 0; i < array.length; i++) {
) v4 N; B, G7 U                        count[array - min]++;
$ O3 T$ s& Z# Q# u" f; g7 N& O( W                }1 M2 c% i- U9 T) O) [( G
                * ]7 n$ S1 V& w; u" e3 `
                int i = 0;
# H: a$ H  u( [/ n+ ?+ s2 Z                int index = 0;5 K' _! l* [' [4 S0 D& b6 h* y: M
                while (index < array.length) {
5 f* l7 E' u7 a                        if (count != 0) {+ f  v9 `. Q0 |" A* w' y0 H
                                array[index] = i + min;
) h# k: ?8 B1 O# T( z5 Z( w9 i6 M9 A6 w                                count--;  l: n: @7 L# I3 K- R: K
                                index++;; Y' Z3 j/ [; u; ^- [: w5 f$ D
                        } else {$ \6 Y, D/ _* A4 Z4 p8 @
                                i++;4 i. b5 _* O/ _0 ~2 U1 C6 ?& t
                        }
7 h) I5 T" V; ]& V! G# X# i! H                }
8 ~# G5 ^1 D7 u' r" M+ s0 ]& ?& N                return array;( ~4 K- J$ R6 Y1 a3 X
        }9 ?1 X" ~) d2 u! K
       
( O  @' w# H( M. ~# ]: {}2 J( {  f5 F: |7 h9 }9 Z
1
, A* v4 A' B! {- A/ g- F2 P. K* b28 J/ ^9 m- @  V
31 r/ i& K( o. H4 X1 n
4
$ x9 e6 C" ^) f5
. `$ S- B* l0 ^- a6  n( |( d' Y' w( S; u
7
0 B& J$ u/ B, U9 g6 b& n8- o' w& N; k9 b2 Z% s
90 M7 X7 |: B6 {, K( ~
10
4 D) }/ p; |1 s' C, \' T11
: R! c/ a5 }- A# L12
, `9 f6 D  o  j) U% e13
4 z/ w) f9 y1 L- Y14& F! q9 H6 ~+ w4 X- b/ h
15; p& C5 `/ X* |( L3 S  W
16  s4 N# D% L* ?! q" D. D
17
6 X& |* j" y: y, G- s18
* n+ L$ y0 y+ n0 ~7 D5 Y3 S19: e" V7 w9 n- Y. K  ]) Q
20  ^9 R) ^; e$ K; ~+ U" b
21
( O. C: t8 G& t: r" y22
- A0 z% d2 w) A23
0 P* F( u' D$ Z8 L% F. T1 B) X240 E% U# ^8 Q, }* F& y0 w! o# m
252 j6 M# x9 R( m8 W
26
2 ~" E! S' L8 s) Z9 @4 i27
8 I5 {% z" X/ E, b28" v9 X# ]; H9 U
29
8 m  R, J8 V5 c, h5 l6 J307 [4 p; w' z6 `& v- Y
31- F# f5 B0 f; j. d  R1 D  I
32
0 |5 p) F! o; |5 j" D2 [  i33" s/ v1 g5 I7 M3 a* A
34
2 w/ T# E' M2 q35
2 ]1 c% m, [- g36: k* }) }- L' i! {0 g: o
377 Z( A+ I; Z  r0 I. X9 [6 {4 C
38  Q6 q6 m" R  f: i* P1 `
39
. a  W! l3 p6 L7 _. T408 D, C/ K, S( w1 @# \* ~! }
41( m0 L8 I4 S9 Y, V6 F
42
+ q0 Q' D, @) A3 s, p43
2 W7 s+ Z2 C0 O3 V2 s' r1 ?4 `1 v* I8 I44
5 W* ^9 Q9 I/ K8 V" E5 z% m6 a& A' V桶排序9 o+ J% T' @  P! i. P/ |
————————————————" f- h/ R: b% d$ n! N8 F$ T, s
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
/ _, M: Z9 e& O5 \原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
1 F) X: u# Y1 n2 n; q% I& s# A+ d
, P+ h8 K( X2 \- S( H. \  n; `% h, `




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5