十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）

& M3 H2 u* V9 X& ]7 A& W2 T, Q十大排序算法（Java实现）
0 j( b, n( q2 K排序算法框架
2 x# M& V$ I: D- z排序算法性质
插入排序
直接插入排序
8 |) K; X# Y- K希尔排序
3 r. S1 ~- k$ @& a; Q选择排序
简单选择排序
& D5 w5 b$ U. ~8 f2 U( i. H" F, H" L# [  d堆排序
交换排序
" P+ S+ ^, c3 P# D, t8 n冒泡排序
快速排序
. X9 p3 n; l% w# C/ V归并排序
2 z' j# D( e% a* u; `基数排序
计数排序
  L; k$ T  Q, A桶排序
更多文章点击 >> 这里

3 f' N9 J  l! e' b2 y
, i7 v: M; R' ?% P- N, r% ^排序算法框架


8 ~! n1 C  ~8 y2 {$ o
8 ?0 ^/ l: m& Z4 T  N! \9 U
" x: k6 f- T! }  b. l4 h( T排序算法性质
6 w" q5 o8 c7 j8 u- C  ]


/ \7 m: O4 {- x
# s' o8 D- G" |插入排序
直接插入排序
; V$ x- |. y! M  O- ~- _从第一个元素开始，认为该元素是已排序的。
取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
3 `2 _4 k- L6 X- y) l遍历数组，直至结束。
5 F7 j) V! B1 V; t4 c! i3 T6 o# g& l6 k最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
) e6 F" D; O. P& K2
" N8 n" }1 l# q$ \ ) 。
3 g, [; @4 u2 |* c0 {+ [* Y$ y: w; c
: A- r7 k: |2 j1 |- P
  z  D% ~! f/ _" b( U代码实现


2 X# f  G( `* u- hpublic class Solution {
+ T+ c7 q+ D2 k- r6 p& E5 ], V        public static void main(String[] args) {
4 z3 h" d5 ], C) }' y                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                insertSort(array);
                System.out.println(Arrays.toString(array));
2 r1 b) x& U2 W" f        }

% R: f( t# R9 n2 f% E7 ^. T
        private static void insertSort(int[] array) {
6 g! r; G4 t. I0 h$ J, a& U% y                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
# K) J1 ?' z3 B/ T7 T& H                        int index = i;
                        while(index >= 0 && array[index] > data) {
                                array[index + 1] = array[index];
                                index--;
; a0 s7 C: L" M* h                        }
                        array[index + 1] = data;
9 Q- b3 @! i# a2 G5 F# ~% _3 x                }
* v  u  S" A% T0 N2 t        }
8 _+ p; S1 ]2 R8 c+ P# L0 n' G7 {}
1
2
3
4
" X( e6 s( `$ }# G! M! M( F5
: o: B/ C6 B5 ^3 n1 c8 j6
7
" _, C3 `- W0 n% y9 Q0 l8
4 R( H, d& v+ h# ^, w$ j9
" O( u! R5 u' D: B) w/ ~10
11
- v3 _" g8 S, g  ]0 |% i0 n12
, L7 F! Y8 _: D, m& `( {13
14
15
3 E" C! F+ G& \/ R, L3 z16
% p' V( S# S+ p$ b17
18
19
5 a2 D3 D" P5 k$ F希尔排序


时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
0 H8 I2 U' {$ G8 O9 }6 m

代码实现

6 u$ E  E* L* {1 u
public class Solution {
        public static void main(String[] args) {
1 C' O* D' T7 d+ J8 z                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                shellSort(array);
$ Q2 O& C  b5 t3 g5 E; T                System.out.println(Arrays.toString(array));
        }

  j" f) L+ h8 y# C- q9 ~# u
" k! S0 K% K$ Q% Z7 z  `" h        private static void shellSort(int[] array) {
                int gap = array.length / 2;
                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
5 g5 ]+ ?) {& y- K9 S9 d                                int index = i - gap;
                                int temp = array;
9 o. z4 y, b9 k9 n- ]  H                                while (index >= 0 && array[index] > temp) {
5 Z/ ~6 P2 x1 O" r+ k3 \6 U: L                                        swap(array, index, index + gap);
                                        index -= gap;
% x; ?  R3 z- s6 ^3 y' \6 m                                }
//                                array[index + gap] = temp;
$ N5 T8 k  S  y7 p6 v                        }
                        gap /= 2;
                        System.out.println(Arrays.toString(array));
0 d( F, E2 w( c3 J  U                }
0 Q' {. \2 w  I* W        }


& z, b$ ^/ K" b5 C8 I. f2 {2 a        private static void swap(int[] array, int i, int index) {
$ K; x) ?7 C6 `& o3 r; Y9 R8 e; U                int temp = array;
; s+ N  U8 F: q1 k6 d9 X' ~: J* }                array = array[index];
/ [! Q& f9 F2 d: o) d, x0 a& f3 T                array[index] = temp;
6 E4 t9 b" F+ M! W$ }  S4 ]        }
/ J; [5 J: }- F# _, }' M0 }, R- [: q}
1
2
3
5 d: S% w; E3 j3 {$ d4
5
6
" I& ]! h9 F! `* R7
2 v. I2 |" O* g1 |$ \% j$ K8
* ?" K4 [, u2 }% f9
10
11
12
7 P6 M- n( n$ S& U# ?$ U" t! G13
, b( T' v+ P- b/ x14
! W4 c( _7 r) f  t# l2 W# X( N15
9 g- l- `1 Y5 {$ t! ^) [16
17
18
19
20
5 h7 a* {0 y- W3 a; T* @% v21
22
23
4 R6 E' `( Q+ I  a: q7 u1 |4 P. Y$ o24
% z# J0 y/ M" E3 O25
+ k: B3 x9 a( h2 Y  Q7 s' j26
27
28
29
30
选择排序
简单选择排序
# ]2 ^* ~3 d# G9 ]从未排序的初始数组中寻找最小元素放置首位。
8 Q7 Y, M$ N6 {0 D2 [从剩余元素中继续寻找最小元素，放到已排序序列的尾部
0 F6 I2 l  Z  [" N; S遍历数组，直至结束。
' P1 J! F- V; F# k3 S+ O) k0 O时间复杂度为 O ( n 2 ) O(n^2)O(n
2
( N) C1 T. J/ |5 h3 o* \ ) 。


代码实现**

0 z  l, \9 @9 d
public class Solution {
        public static void main(String[] args) {
) G- y" O$ N* j0 v9 s                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
. z6 l6 ?1 `. |/ m% p9 z                System.out.println(Arrays.toString(array));
        }
* K( u) b+ P4 q# z

        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
7 s% c9 C* ?% v, g                        int index = i;
* {( G3 ]/ O# I: c, h4 |                        for (int j = i; j < array.length; j++) {
2 w+ f' x" \1 I% `' P/ t. v0 s" f                                if (array[j] < array[index]) {
                                        index = j;
- `9 P$ q. [) f8 d8 M1 o. E+ N                                }
                        }
# s, a3 A  O" ]# R2 N) u                        swap(array, index, i);
; F/ `, O0 u$ Z+ F3 _                }
        }


        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
9 O3 S" D) D/ X, l- [                array[index] = array;
                array = temp;
0 f. {0 e. B7 t0 d& V" x        }
}
) `1 S+ a7 t2 ~9 t6 N7 J8 `1
6 j. P  e9 P6 Y3 U; O, R2
7 Y6 T  Q# g1 j- t; j* M3
4
. i* e3 K6 G. k) Y6 m5 Y$ K5
6
7
8
9
: D$ G0 G& w( B* [10
11
9 O" ^7 R# g* V12
13
14
( F- i# c* q% t9 D( \15
! {: Q5 [8 J- t/ P, `16
17
18
6 ~  I9 e; I; R' v8 H19
, g& F9 ^: b  G  ?8 T20
2 y* G) e0 h0 r4 `21
4 j/ o# g2 d. ?! }$ T; Q. D* q' \, p22
23
" i5 D; D& k2 C) d% R& M) q24
25
1 I# T. Y' }- D- i3 a3 O& K堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现**

; A7 d$ `9 a, p4 d0 W+ V( ?* H
public class Solution {
5 A# D/ o& ^$ J& P( R; P        // 建堆
: [. u( \8 p' o  y        public static void creatHeap(int[] arr, int n) {
& J  @) t2 F0 `5 [9 R                // 因为数组是从0开始的
                for (int i = (n - 1) / 2; i >= 0; i--) {
                        percolateDown(arr, i, n);
                }
        }
7 t  e! @8 Q5 Z! [7 P6 ~        // 插入
        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
                percolatrUp(array, n);
9 f  |1 {8 g" I+ {# _& v        }
        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
                arr[0] = arr[n];
                arr[n] = -1;
& K' T: m& o/ {: a$ o                percolateDown(arr, 0, n - 1);
. O9 [7 C, T6 A, @* I        }
5 p3 i5 |9 c0 [, v4 ], @& R        // 上浮
: m9 u" r& I! M0 N        private static void percolatrUp(int[] array, int n) {
                int data = array[n];
6 J& V. W: V. a# Q9 d/ y* A/ u                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
# p% f, n9 J" P% l7 A( L                        array[n] = array[father];
                        array[father] = data;
                        n = father;
3 v6 J8 P" v, Y8 s" R! x+ ^' x                        father = (n - 1) / 2;
                }
                array[father] = data;
        }
2 v6 ^( c# P7 R5 }2 P2 i6 M( C        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
                int child = 2 * i + 1;
                // 遍历整个该根结点的子树
                while (child <= n) {
  v- G  ]- \' ]% E, W                        // 定位左右结点小的那一个
+ P7 p; \$ `8 W0 E3 g                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
1 {: @5 J. u( G+ ], |                                child += 1;
4 `, r  T" H" {% C                        }
                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
                                break;
                        }
3 T+ S5 d  m- a) S. s                        // 互换根结点和子结点
                        arr = arr[child];
                        arr[child] = father;
                        // 重新定位根结点和子结点
) E5 [7 W+ q0 y# A# l9 j' D! D                        i = child;
9 l4 Y6 p  |9 V5 f* v                        child = i * 2 + 1;
/ V3 _$ M% W5 z) s9 E7 _* G  Q3 W) w                }
) @" X' E8 n4 c6 m        }
: T; L& I1 n9 z) ]# {' u   
        public static void main(String[] args) {
; V0 t& v- g- e7 a: F                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
& _' U2 C, O9 e, j1 a               
" V2 [% ?+ y, u) H                creatHeap(array, array.length - 1);
  m; }1 x; a& J3 A  S, L, i                System.out.println(Arrays.toString(array));
3 F* w4 G: F2 N- h6 r               
                deleteHeap(array, array.length - 1);
+ k, v0 C) }& c! N7 p; w) E9 G                System.out.println(Arrays.toString(array));
               
0 w4 k# B3 F  Y                deleteHeap(array, array.length - 2);
                System.out.println(Arrays.toString(array));
* K8 {" M& B0 `( U  Z, x( x               
                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
        }
& p1 g5 a8 K$ X9 i}
1
2
3
4
& V  K- Y' Q6 q& f3 V5
$ k' Z+ \4 }; A& Q- m7 v7 K$ c6
- l8 A# d) H% J" i. M, W7
* k! i: ~5 O9 k5 ?8
9
10
: a, P; m, q+ ]+ i+ {$ ]11
12
13
& @+ k5 ]7 p. V0 _. C" D& y- G14
+ H" @5 Z% E- B( w5 S7 ?: a15
16
17
18
2 O, N6 K/ y8 L7 \19
& `; \+ K) d: p. w0 Q, O20
21
1 `$ g! w7 q1 G% K5 i! f8 A( O22
7 O; g- v& [4 B( V7 J23
: U: G. \7 e5 E) Q& |# K  `* M24
% }2 X: K. L$ C2 n25
26
+ g+ R( U) a, p$ D# q27
28
29
30
: ?; F' b1 X, ]4 d31
! I2 }6 E9 w' ~. ~! Q32
% g1 E( E1 K$ E) n33
" B$ k, R/ A* Z$ b* o6 A; ]/ [2 ^34
35
36
37
' I  u0 a# v: X; R$ i38
$ A+ i- {6 ~1 H) n39
  a% ?1 u  s! b40
41
1 n& t1 x" {0 q9 X$ @/ _42
3 T; J' s  {9 Z: B( R! R+ Q43
. t* b4 A! T' s. {$ m( D, _( \( S1 Y44
1 `! h3 t# F! E8 \- z45
46
47
48
7 \; N% j& b1 h3 A7 C0 T49
50
1 f  B% V, t- B/ O% Z51
% j( F; d9 a7 H: N2 t0 w7 N" `52
53
1 ?1 i. V. W! i54
+ h8 f- `1 }- R$ [; j55
56
' |% {% \( Y% K, K' p5 [. I4 g1 m57
58
, D1 r2 {3 u! G2 @1 b, Y8 T/ q0 p59
60
61
' Z" k6 o0 E: [5 I62
# f  @2 t+ J1 U63
64
1 O. l( \: i5 s. {+ `# g65
* v9 ^; j2 n" G$ U* S66
67
0 k+ P) l) j& M, u68
; [& R% P% }4 ^/ F- E69
/ N  V6 ?0 T  x6 ]70
交换排序
冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
3 r; a0 |; p- M6 _9 c9 D在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
* k* R! ]; @  _& L最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
6 B5 F7 ~* g, v, C2
; D& @1 i6 T- o ) 。


代码实现
: v& b+ n8 F& |: g3 h; H1 [9 w. B  m% m
9 v! O* C9 A" X- F+ r
- ]" f1 h4 w/ q+ m0 n: b& ?; O( Gimport java.util.Arrays;
: M" x2 ]; N* F) O; j- Epublic class Solution {
: |2 n, e; P9 A) V: C4 e  M       
0 |/ r. x4 O9 c  f9 x5 ~  y        private static void bubbleSort(int[] nums) {
                // 循环次数
/ e- Z' H3 o9 \, c3 d0 _                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
                                if (nums[j] > nums[j + 1]) {
                                        swap(nums, j, j + 1);
9 }* ~( `/ E* J! }  I; Y                                }
/ C7 _1 z; x: N: D1 z  J                        }
                }
        }
8 t/ l9 p7 ]4 a, i$ z# P6 {

) z9 K; Y2 C' i" j/ A5 @        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
- E) U0 b8 K; |6 L& d8 ]) e                nums[j] = nums;
, D1 N+ z  Z9 l: J                nums= temp;
) `. M6 y/ Q7 K2 o8 C/ p% s2 z9 }        }


        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
$ H) G" c  R2 f! \; S4 K                bubbleSort(nums);
$ e  r, m- c* j3 u                System.out.println(Arrays.toString(nums));
        }
}
6 x6 g: _4 m% R& W1
" W& [6 P+ {! O0 @( ~$ }2
/ k/ F. c: ^, @! b3
4
+ a" Z$ e2 A5 o5
. `$ i" Y( s' |4 q6
7
8
9
" p1 }. P* V; k+ X8 i10
; ]. U  u$ i) o" Q! p11
5 n" D. x: i2 |# j12
13
4 R' \  g8 G7 m# I14
1 X, T, a+ V9 h9 I: ~15
* _$ j. X9 j3 N% g! \, ]16
17
8 }4 Y- L" n; ^" |18
) @6 N) |( P0 [" C' r" |, p19
20
21
22
1 \& d0 ~6 Y! s23
9 I% k: \; Y8 e+ v5 R! P  O# }& k- ]24
25
26
! d: i: B  l8 V% m% A27
快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


2 X4 a( F. b: k. `代码实现
% v. j" M/ a0 M% K
$ B, `( z8 S: P% g4 u
public class Solution {
       
        // Median-of-Three Partitioning
5 E  k9 g$ c' H% `) \  {* {        public static int selectPivot(int[] array, int left, int right) {
; }0 |! j. z! f2 c: C! x0 q, y                int middle = (left + right) / 2;
               
' J. Z/ g% ~8 g                if (array[middle] > array[right])
9 a4 Y1 B9 _5 T+ x. A8 G: a                        swap(array, middle, left);
- D! Z9 c( e( T9 E5 M8 l% d! Z* k/ |                if (array[left] > array[right])
                        swap(array, left, right);
                if (array[middle] > array[left])
+ K9 u4 M* {4 R: _; `; q2 u                        swap(array, left, middle);
               
                return array[left];
6 k6 S5 d4 x# _+ Z/ ~; `3 H6 j        }
       
5 x3 R5 G: U$ Z# G% C  N; R6 U        public static void sort(int[] array, int left, int right) {
- k2 V; O  {% x1 h% X                if (left >= right)
                        return;
                int index = partition(array, left, right);
                sort(array, left, index - 1);
. s8 e6 R9 ~+ D% m! _% C3 k; S                sort(array, index + 1, right);
, m$ }4 i) O, D# F4 z9 z: `    }
       
        public static int partition(int[] array, int left, int right){
; o6 S/ v8 j, x- D6 U4 f; o        int pivot = selectPivot(array, left, right);
        while(left < right){
            while(left < right && array[right] >= pivot){
                right--;
            }
            if (left < right) {
                array[left++] = array[right];
8 [4 F" B  {; ]* @            }
) [1 f& W+ l( y+ O            while(left < right && array[left] < pivot){
                left++;
. `- q& `  u- f8 S& E            }
            if (left < right) {
) T$ s0 i1 O4 A$ u7 w( ~$ l' i                array[right--] = array[left];
            }
        }
- m/ @. ?6 p8 E1 u, N            array[right] = pivot;
        return right;
/ }( _7 u' g/ Z4 ]2 M% M6 Q; H* M    }
6 t. ^- D5 J2 m  x" z+ F3 H& {
! T' |7 t! D$ \4 F! a7 b
( ~6 n& J9 ^8 E7 @- ], t) Z' H    public static void swap(int[] array, int left, int right){
1 K8 y& ^7 t3 d; l# a& ~! h            int value = array[left];
            array[left] = array[right];
9 l' g2 b1 ?: v4 p, z0 g: J            array[right] = value;
7 P* m* K) Z& v8 r1 l1 W5 n+ b. F    }


7 ]7 P7 ?9 `$ n        public static void main(String[] args) {
* P% O0 u8 v  F9 O, H. l                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                // System.out.println(Arrays.toString(array));
                sort(array, 0, array.length - 1);
  j: C# @# r5 s1 h4 w2 J                System.out.println(Arrays.toString(array));
        }
0 R) O' B' c2 e& S# v1 U( ?}
+ H8 l# _, o/ k( B( L1
2
3
4
5
) j  w( X6 H$ |) K& @4 Q6
7
8
9
10
# c1 j! }1 Q: y" Y! t2 c8 K11
12
13
) g/ e+ H$ T% u7 y/ ?! ~: S14
7 u3 c2 B! j+ `' B9 Q1 h15
( j3 L5 Y- o+ c9 W+ d  l8 D+ q16
# b6 B( t7 o3 S" G: _+ f6 R17
18
19
2 r" N+ c" [4 G8 c6 _3 l" [20
21
: K7 J- E% r% T( q0 I22
23
24
6 E9 n0 L2 L! D4 Q) G1 ?25
26
27
28
8 K  @/ x6 H+ u* \  V29
30
* F: r. \0 S% n9 F8 K1 o# n" Z31
32
33
34
35
% E: ^# T9 V9 d% ^7 V% A36
: A. R4 Y8 @* I7 M3 V37
38
  n* Z+ s/ O& p& t39
8 X# m6 V+ y) l7 W  ]3 k1 }40
41
42
6 @7 H( p; o7 Q9 b4 p: r. ]7 q* Y! ]43
44
! A8 w5 B% X7 x45
  ]# a- Q; x5 ~$ M  I5 p46
- a8 k3 _3 k2 j  ^9 s% Q% }47
& {6 u( L; h7 {2 _48
  @, z7 P4 g* o49
8 ^, p2 {- N4 B' Z8 K; |2 f: {50
51
% A0 o2 G  f+ L2 D# {52
53
54
55
2 i9 Y& W/ M# W/ f2 N56
57
归并排序
, F& w$ W( Z" k3 ?1 l* B+ \* d- Q将长序列从中间分成两个子序列。
/ S# [7 L# f4 ]# g0 T对这两个子序列依次继续执行重复分裂，直至不能再分。
, C- E4 `1 S( Q  w递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
  [7 V+ k% k5 _9 _% w
: l$ U$ C/ ]( C+ h
代码实现**
- o  e5 g. s# K7 r3 o* A6 s
% ~0 z* J7 n1 m/ B  w
2 K# _1 V" Z; p) `public class Solution {
) m4 M5 ~, S& j/ n! Y/ v        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
' k, F4 l! i2 q                int[] arr = MergeSort(array);
                System.out.println(Arrays.toString(arr));
9 }' F( e7 b$ D; i7 V! H$ Q        }
" A! k, ?7 z+ ^, d2 L

        private static int[] MergeSort(int[] array) {
- b* h" l% z8 l; k                if (array.length < 2)
                        return array;
3 P9 g$ H, G% {5 O0 t# H                int middle = array.length / 2;
                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
& p4 y. w2 R9 l; k) v* {                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
9 f2 Y* X6 e( `+ V4 B0 C                return merge(MergeSort(leftArray), MergeSort(rightArray));
  g# `* l* S2 N; H( j% @        }
, _! ]2 V  \2 n; V9 C8 y3 I4 B
, k$ _: I& M5 q, k3 j
        private static int[] merge(int[] leftArray, int[] rightArray) {
                int[] result = new int[leftArray.length + rightArray.length];
) m/ ?  m) w, _! V1 A                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
                        if (i >= leftArray.length) {
                                result[index] = rightArray[j++];
. ~" Z- t& S! N7 s  ?                        } else if (j >= rightArray.length) {
* a& X/ D/ x7 @. ]% F- m                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
9 ~0 ~* @& }  C% b$ s                                result[index] = rightArray[j++];
                        } else {
                                result[index] = leftArray[i++];
                        }
1 j' D6 C, t0 ]5 g/ f! N3 }                }
; P9 f; Y# H# r+ n+ Q                return result;
        }
5 S. {5 Y: d4 D+ H3 l2 W) Y}
6 l2 h; _) ]9 l5 \- v9 M5 |

. u4 I  i+ X( }$ V4 q& d6 J: W1
2
3
  F3 E4 W( q5 ~4
( \$ {' K1 v' q! F5 w& e9 c5
" o# V6 l( x& j. t# x6
0 g' {7 B" @  \1 k4 N  q" U5 U( p7
6 O/ K. K: @& d6 i8
9
10
+ \% \4 ?$ P( Z- V2 C% q11
12
13
14
15
16
3 k( n5 |8 N# K! _2 R2 ~4 n. F17
18
19
& k( D6 [( H% }9 x20
21
, c6 c: ^2 K4 F- f& E2 p2 w+ g22
23
- x3 M2 s' C) H/ D2 g9 S$ F24
25
26
5 b# R! M+ N. j6 W27
3 H5 T. B9 l; Y# u' k28
6 R& M" O6 O! {, v5 a6 }4 B, w29
& m" N% C! z* i5 i2 o2 B0 e+ z30
31
32
, {, Y6 d% q2 _- |4 Q! p0 e" w33
: Z, [3 h) @) `, s. K: V. B. E基数排序
/ C2 z( L; P3 S. i( S( F' _找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
7 _8 U" E: ~1 \6 \7 s4 o) t/ Q- f
& v* N# V4 X* u/ i
0 A- B* u4 c5 @" T, {代码实现**
8 F$ z  q1 ~1 @& Z) j

+ D% Q/ U. @! p+ e+ Zpublic class RadixSort {

, j- U& w" i' P. J. r3 F
        public static void main(String[] args) {
/ v! y3 n* d* B. ?  R                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
) ^$ R* u& G3 d' N1 t. X& {                int[] arr = radixSort(array);
& I) b" p( m% l. h: t8 ]                System.out.println(Arrays.toString(arr));
        }


        private static int[] radixSort(int[] array) {
4 r5 S  U1 @" a- E* Z7 _; o                if (array == null || array.length < 2) {
+ }& i0 v$ S  k3 d+ j                        return array;
3 p6 u7 f" U( k$ P( y$ @) t  i                }
; g, s, h( x# o* L! r                // 根据最大值找到最大位数
                int max = 0;
                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
( q/ M3 L6 U! G- o- C6 @+ S5 P                }
  [5 ]. x! d  @7 n9 i! {5 ]               
3 b) E( r: B8 V* D8 U  H                int maxDigit = 0;
5 b  R- `. G# \  j/ G' m                while (max != 0) {
% q( E7 ^  k5 L4 v9 F# u. A                        max /= 10;
, Y, ~5 E6 Q, m! l6 W/ \8 q1 E                        maxDigit++;
2 B) `1 \7 _1 m9 C0 Q' \: b4 y                }
8 c. `/ u7 _3 U2 K  \               
                // 第一维: 0~9
                int[][] radix = new int[10][array.length];
                // 该位为 i 的元素个数
                int[] count = new int[10];
- ^7 k% s/ P5 ~( G- |+ E+ S               
                int m = 1;
                int n = 1;
               
* }/ y' Y0 L# f+ S                while (m <= maxDigit) {
7 Q6 a5 `% f3 {& k' N7 B$ b+ w                        for (int i = 0; i < array.length; i++) {
6 G3 S1 m6 m: ~/ \* Z: r6 P                                int lsd = (array / n) % 10;
- ?. N1 l* g1 S                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
                        }
. C, `) b3 H: z' l8 W3 o8 e                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
( U4 j/ ~7 o2 J+ z9 q8 }1 y                                                array[k++] = radix[j];
                                        }
                                }
# C2 w! J% l8 L- I* ?3 w$ y                                count = 0;
                        }
                        n *= 10;
                        m++;
                }
                return array;
$ ?9 ?5 N( K6 [7 J        }


3 |7 L" }* x4 J0 W}
1
/ x9 g" B" }4 Q% l$ j. \- z2
; b+ [+ E! b/ P) N  `/ A; n$ }3
4
5
6
" X$ y* b. I0 ^/ k) W& z  L( q7
8
9
10
3 n" P+ E) e* r1 e. E  s- g  s11
12
13
14
15
16
0 i- F: I7 g" c; ?6 V17
18
19
, [/ _3 ?" M2 E0 x5 m20
21
5 F+ k+ F+ I- X8 k5 Q- g22
23
24
25
# I# n2 m8 E0 }8 ~, i' T$ b3 Y6 z' t26
27
2 ~% ?' W3 I$ M28
29
30
7 ?5 \' p& P: _) [31
32
33
: Q- y& A$ ^, j% B2 C34
35
4 {. `9 G4 D5 R$ z3 r6 C8 U36
: B8 v7 o: `! ~; K$ Y37
38
. J! C6 w3 m: q0 C* U& ^8 [- E& d39
40
1 s; M; R1 O, r) y- b% S41
42
( g# y# T* ]- r2 ~# I43
" z/ @; z6 g8 L! R9 k2 _. X44
. I6 i! y" i2 ^) W7 D45
+ h! S) y/ }( F$ f5 f" `46
; L, t% v4 k0 j2 G2 U2 ^47
# \6 u2 o( ~% b48
49
50
51
0 u  V8 L6 \6 K2 ^1 V52
! B# l( D5 [0 u: i" x53
; o/ F6 R7 R: O" F5 H$ G计数排序
% _: [, d& x8 H, |) P  `1 e; T# v- W找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。

: t7 C$ J7 \' M- W$ W* \# z
代码实现

' P# I! c7 b, G6 ^# X
' H8 E; F2 h, h# B7 ~public class Solution {
( m  k( T2 q1 S

" E" {" m$ f) `, F7 D/ S        public static void main(String[] args) {
! ~. q" E" V6 v& S7 u                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
        }


6 F- m  w6 ^9 \' j6 o        private static int[] countSort(int[] array) {
. }$ W5 [+ Y: F% q4 K                if (array.length == 0)
                        return array;
               
                int min = array[0], max = array[0];
& f. c  D! ^* S0 f8 v: H3 r               
                for (int i = 0; i < array.length; i++) {
- G2 _* V0 b' X' X/ `                        if (min > array) {
                                min = array;
0 x& Z( S4 A$ @1 X+ j( {' g$ E# H                        }
                        if (max < array) {
- A( b$ B4 q" }4 k/ u                                max = array;
$ s+ Q% x6 i  A! K                        }
& N7 V0 ~- [  B8 R8 W+ k' B( z                }
9 ^( `, w/ A; H" `6 d* f               
                int[] count = new int[max - min + 1];
6 |  T- N! I  P9 n               
8 c8 S1 s$ r: a2 Z9 M                for (int i = 0; i < array.length; i++) {
6 h2 W/ D+ D; z                        count[array - min]++;
                }
               
                int i = 0;
" Z- q, E  Y  {$ Q                int index = 0;
, B+ E# z' k% y; @                while (index < array.length) {
; Z4 v3 O: |: s0 x2 N# v; m                        if (count != 0) {
# y6 q5 q! Q7 x% W                                array[index] = i + min;
0 y4 o) z$ L# u; E/ Z6 m                                count--;
                                index++;
                        } else {
                                i++;
+ d- n( Z, c0 t: I* h* z+ g                        }
+ T8 y2 I0 n! Y& n# f" z1 K* G                }
                return array;
        }
       
}
! j" _$ u: n2 T% s1
2
3
0 c& p8 u% u) c% w+ ^% y4
5
6
7
8 i  B  \* d0 t" N8
9
10
11
: |/ m0 u+ ]5 A/ Z12
9 Q( @5 g3 J9 x9 f/ T. m13
14
15
/ q* E* U: S+ C* `' s' D* Q16
17
18
9 g/ d3 P9 ^9 V19
0 p. v* N3 Y2 Z7 X" u- i20
21
22
" Z- e* y( U$ D: f' j* A23
24
5 w1 p( C6 P& R; d. }25
3 Y, J' A, _( N* W26
: f" y2 H0 Q% b! t8 m27
* ^& l& ^( B+ p' ^/ o( O9 b  o28
29
$ y: |( w# @9 L; L3 R( k7 B% ?% C30
. \3 |$ c  `3 E3 x+ r+ E31
32
. y1 r5 D& X9 F33
34
35
+ s/ V/ k, U) e/ {0 m7 N36
37
) K3 e7 }$ Y6 j% P+ ?! w38
39
; |& G2 U8 G! u# x6 N40
41
42
43
! h4 D: V/ b! q& F& i44
桶排序
————————————————
& n" X( }! Q3 c3 n) k6 t- m% ~版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. c5 V  g0 Q. T0 t; `原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153

" G7 k) s& E4 u: S1 E' K" {