十大排序算法（Java实现）

杨利霞

+ o# O$ t; ^' [2 i. {& m$ H; I' k十大排序算法（Java实现）

  B8 |, ~$ L. d6 E8 i十大排序算法（Java实现）
9 I* s' P$ Y/ X7 x5 Y排序算法框架
8 [, u' Z$ C: t! ^! n2 z* n排序算法性质
( @* d/ U7 [9 n" g' B: M8 [' U) J/ Y插入排序
! ^% B& r- i8 H7 v! _/ e直接插入排序
) I/ s8 p/ X7 r3 [. E$ d# G2 A/ k希尔排序
( ?9 x; j7 X- ~4 c选择排序
简单选择排序
堆排序
+ F6 d3 ]! x  L+ w6 p1 {0 C# J$ n交换排序
+ w1 ]' R9 P3 Q3 c. I冒泡排序
快速排序
归并排序
5 c* t" z2 k9 E; r4 J7 S基数排序
' Z) R6 R) Y+ I计数排序
桶排序
更多文章点击 >> 这里
! ?( P9 w9 _, c7 d

9 i% B8 h5 }5 v6 v9 e  X排序算法框架

- D- R. w5 H1 J- y/ F
  z$ b8 N; V5 Q, g; o$ n
1 P3 r0 F. Q6 I) F' Q! h
排序算法性质
: @6 s4 b$ d) Q# }
' A! k5 T0 i9 |* M' g- R6 z
4 N& j# `  q0 k3 }! |* W' p5 j
% q, d$ X0 y! }0 ?
插入排序
直接插入排序
从第一个元素开始，认为该元素是已排序的。
取出下一元素，与前面已经排好序的部分进行比较。
# f/ l( r  t& L% r0 y( J1 F若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2
) 。
. c' c  }2 b1 y( d/ l
$ h! p. h; O) u" b, k7 a# D
代码实现

4 }9 y+ F( U; C
public class Solution {
& \1 `& k0 \; }" l        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
1 E9 Z) V- V" A: o" H                insertSort(array);
                System.out.println(Arrays.toString(array));
        }
3 X) Y* V+ m3 G0 y

        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
                        int index = i;
6 y% l! M) `( ^: Z                        while(index >= 0 && array[index] > data) {
# x& W3 D) @' n, l0 O5 [6 A                                array[index + 1] = array[index];
! Q1 I8 A9 z" K! b, e  p' T, K                                index--;
  f. b& B; c  z! _( {1 f                        }
                        array[index + 1] = data;
4 l9 L- i& o" B. }; w                }
        }
}
* r- \: V5 Z% Q; X/ j3 u9 a1
/ Z0 U# u2 Q2 r6 f- _2
, M2 F3 P9 O+ [1 h! ]3
4
- p( o0 O! [6 B/ l5
6
. j5 Z2 W! v- y7
8
+ e5 K3 J2 Q* ^- G6 ^  ?; H9
10
/ M. ]4 K) b+ u7 V6 K) L11
, S) k4 S, L2 w# B9 a12
13
14
15
16
17
2 s3 a, `4 I+ E2 K  ~3 j5 f2 P! ]18
19
& i6 [% l9 J( G) G7 m希尔排序
/ }$ {' h; e, \0 \6 g- H

( O  W8 p6 n% P时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
. j6 ~& y0 V* g& o
  z  r' f) E* m: Q* v, F7 ]8 R
代码实现


public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
" C+ X6 V( L# J                shellSort(array);
7 K" |1 Y6 A! f: y$ n( x% Q                System.out.println(Arrays.toString(array));
        }
3 }  P+ B  J+ _2 L

& w( i8 ^2 d9 z8 o* ?, k. \        private static void shellSort(int[] array) {
; B! h6 W2 H4 o3 a/ F4 ?7 u                int gap = array.length / 2;
1 \3 M6 e/ U/ A1 ~/ v                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
                                int index = i - gap;
8 ~: i$ w- R( U& H                                int temp = array;
+ e% E' V9 i# _                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
                                        index -= gap;
' B  r1 ?/ u9 f; q! D                                }
. B7 H" j) }  e' J7 V& n6 W; a5 t/ T- t; M//                                array[index + gap] = temp;
# J6 P7 |* L4 `5 J                        }
                        gap /= 2;
" w- ]$ u) e% T5 M. T5 u                        System.out.println(Arrays.toString(array));
                }
& r/ t* i% M' ^6 L        }
3 R5 a" w! N0 z" q9 }

" [6 Q- t, p: a        private static void swap(int[] array, int i, int index) {
                int temp = array;
                array = array[index];
% {" J" R/ F: H8 C# r5 T  z                array[index] = temp;
( b, B& m* ]( X/ ?        }
}
1
/ ]9 m3 J/ t( _# S3 b& m1 ^' i2
* r8 {% _! A5 p  W/ W3
. E9 x- s/ J4 M  E& k4
5
2 b- }( J( m- H7 n5 B) O6 ~, q2 {6
7
, P7 I$ s, ?9 |, I8 J2 k9 A8
9
10
11
12
& U" H5 `: r9 S) o, X( |13
14
/ Q' K3 n+ x" z0 R4 Z8 s15
1 p- Y+ c. @5 m16
17
; x  E7 _1 B3 i2 O! F! q18
; k: z# g3 q4 n& r1 C19
2 j4 ~3 e- y4 U& E4 @20
# c) \  u$ }7 T* B& d$ f21
22
2 C* L3 z8 W; i6 M$ n5 u  y5 G23
24
25
9 ]) `7 M" g+ T26
27
" a7 E, P6 z% [28
29
30
选择排序
简单选择排序
从未排序的初始数组中寻找最小元素放置首位。
- i7 j8 X* m' t( T从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
+ {6 D7 t4 z* C* Q6 [- \时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。


代码实现**
; U- @# W6 I7 j. P

public class Solution {
3 |1 R: U0 z1 O; g* p# z1 y        public static void main(String[] args) {
8 A+ h( T& x$ Y4 W8 P9 k6 Z                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
" |7 b7 A0 ^' n) N/ U3 c* M                selectionSort(array);
. N1 |& ^2 ~: S6 L& w# |                System.out.println(Arrays.toString(array));
6 @9 `" w) ^% q7 x9 t9 w        }


        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
" P* {- X/ u) C/ @( O                        int index = i;
2 A* J7 }% \+ B4 J. }+ V+ [/ _0 t                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
* A( p3 B( I+ d1 b9 O% A& E% M                                        index = j;
0 j( N7 H; }6 R+ v. Y                                }
                        }
2 H4 Q7 Q' i! |# L% V) G5 ~                        swap(array, index, i);
( i' F5 G" W# g( a  T7 z                }
        }


1 j* }) o! l) g% t8 D) c1 H        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
                array[index] = array;
                array = temp;
        }
: j+ o7 C* h, l3 O}
, R7 S' k8 ^9 ?0 f! v! \1
3 k+ q9 s7 X2 M  b1 f! c7 f+ q2
3
4
5
6
7
; k; W0 \# s. J; P5 |1 o8
& d5 x/ o# j% Y+ R, G# p. W: @  s* Q: V) m9
# v6 a+ U5 D% I" S/ L10
6 U3 h' c$ u8 T8 X, r: E11
12
13
9 ?( [& O* M9 @, q" X14
: K6 e% P3 y) t) I& b9 K( w15
6 v, a: y2 O' F7 c# L9 {1 H16
17
4 ?) i; _6 q5 [5 ~$ d18
9 |+ f9 {" H$ h) _8 D19
20
21
22
23
24
" ?2 ?' V' G2 K" l0 E1 \/ `% D25
7 M- y: q% {. `1 S. @0 K堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
/ ~! y5 \- l9 }3 F
6 k! {  p6 m) m( m/ L
代码实现**


0 ?* Y4 k) t$ s+ r9 @public class Solution {
1 o7 g3 T1 y& F" g2 m+ H' ]        // 建堆
6 H' C  G7 y! l3 h7 A( E        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
) T" s5 S# N6 |4 v( m/ [4 F                for (int i = (n - 1) / 2; i >= 0; i--) {
) ?3 E) j/ a; r+ g                        percolateDown(arr, i, n);
                }
* `) j. R0 m6 R! @# _  z        }
        // 插入
8 m6 h. p' _( i4 F/ K4 u        private static void insertHeap(int[] array, int data, int n) {
& X3 d* w( J( e7 R4 L! ~                array[n] = data;
/ x% V' a2 |% T6 {1 J8 p2 b+ {                percolatrUp(array, n);
        }
7 K! s6 c" W7 |# ?4 p5 r        // 删除栈顶元素
4 ^5 K6 e, \1 a' C        private static void deleteHeap(int[] arr, int n) {
5 D* E& d) |) K3 e' \9 p- n3 a                arr[0] = arr[n];
                arr[n] = -1;
% Q) N/ j( b' A0 s, ?. A, d1 }0 |                percolateDown(arr, 0, n - 1);
        }
; v0 X$ c9 x2 W, J) ]) b        // 上浮
        private static void percolatrUp(int[] array, int n) {
, a6 O! Y6 s( x0 Q7 J- G/ S. L                int data = array[n];
: s- E: g% Z2 f7 W$ x/ ~                int father = (n - 1) / 2;
) a" K$ }6 K9 v                while (data < array[father] && father >= 0) {
' V' ~7 j. Z8 i( Z: P                        array[n] = array[father];
                        array[father] = data;
" Y8 k# T% \4 c; x0 I" O9 w                        n = father;
1 |6 [* I$ z4 v8 E; z/ R0 F                        father = (n - 1) / 2;
# e* _$ t& O2 }' b- a+ k                }
( h, m; _- I. y/ m6 O                array[father] = data;
+ i; p6 Q4 h% m0 {; I        }
        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
  [$ L- `( W7 U                int father = arr;
                int child = 2 * i + 1;
                // 遍历整个该根结点的子树
( J. a4 `7 s4 o( ]+ H                while (child <= n) {
                        // 定位左右结点小的那一个
; p. D% l1 A  U8 j                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
7 E1 F0 b( @$ o4 F% G                                child += 1;
1 u, Y* y. B9 z                        }
                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
                                break;
& x7 D" O# [7 e& q! G& V( w                        }
# _: T3 X& R& b% ]$ [0 t$ _                        // 互换根结点和子结点
                        arr = arr[child];
% N+ b& D; {* T7 \                        arr[child] = father;
" J5 w- L" h' h                        // 重新定位根结点和子结点
                        i = child;
; O7 Q  d3 z. c; m6 q                        child = i * 2 + 1;
% }4 n1 U2 x, P' k0 e3 n, s, k) Q; ~                }
7 L* n/ e% s) r8 x* B( S        }
/ a" o& Y5 ^/ B# b# r8 @   
/ o- e9 W( t8 s2 v& A        public static void main(String[] args) {
+ H# \4 a7 ~, d# a" V                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
                creatHeap(array, array.length - 1);
5 Q- c" ]. [  b, c1 G7 l, k                System.out.println(Arrays.toString(array));
               
. P% b5 L0 Y" f' J* @                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 2);
7 n2 e1 {+ |) J8 }* O; v                System.out.println(Arrays.toString(array));
6 {5 s. [3 M9 x$ a; |9 v               
                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
        }
}
1
2
3
6 z* }' q' z: F8 S# o. K4
5
5 H  s  g, F5 ?( d6
7
8
9
10
  T8 R7 W0 I, _' Y8 _11
12
+ D# h$ s5 K) s2 \# b! i. f# V13
. j1 O+ \4 q1 B" X( m9 I9 w# Y. {4 M14
/ a" ~2 T# ?; M& P15
9 M7 p" B+ A9 i& G1 O6 T- d6 D16
+ O: }& e) }; i17
18
+ |% L5 r7 Z3 M19
: f. R5 E7 y9 b5 B5 t& C20
" B5 l* n5 b, ?6 u$ Q1 Q21
* c8 X$ S/ x7 l22
, h8 R$ u3 x2 Q1 L# O23
6 `' k" r9 z. u0 ?" O# P2 K- v24
25
26
27
) g$ [. ]8 i( j) i2 ~28
29
5 V% ~  a0 `: R+ s, ?( I30
31
3 n6 P8 @( E' G32
33
% o/ V* X. c* Q34
35
- S" |9 x6 `7 L6 _9 u6 C; H: U; e36
  [& V! `* w. I4 O37
! j% T2 h" r  e* I2 K38
39
* S2 X* J$ Q/ l40
' S/ M1 a" H& F; M# b2 X# d* J6 j41
' Y) t2 y- E7 G4 L9 M+ p( u42
43
44
45
46
47
48
/ S/ X5 N, H0 u4 H. B49
3 d: g+ @7 H2 G2 R, M, y. S50
$ L! b1 s9 B' J8 w# v" @51
6 ~* @/ j& g2 B; v& j, @4 X2 Y- t52
  u  }+ [- e4 V0 P53
; b* B4 D3 s2 {) l3 g54
55
56
57
58
59
60
) \& B% I- X/ X9 H61
62
63
7 r8 z5 r8 f3 t& L64
65
66
67
68
0 Y" u7 B8 Q) E69
70
交换排序
  z4 T% q) k( p+ x) h' ~冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
" Y2 d$ v/ q9 [2 D! i* E在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
8 S- L" I$ D1 X  |最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
' h. b& t. ~" b1 v- V+ \2
! J' Z/ S" J5 b7 k  V/ j ) 。
% h8 i5 Q* q: o% J3 ?3 C

代码实现
: j8 [0 Y; ~! A" Q; ]( `
/ U8 P& ~" Q8 K8 k9 w4 z
import java.util.Arrays;
public class Solution {
/ Z  i: O+ E5 M4 O4 t; Z# i' a       
        private static void bubbleSort(int[] nums) {
1 E$ R$ U) [9 P$ }- a                // 循环次数
4 S4 B7 N+ A" ^                for (int i = 0; i < nums.length - 1; i++) {
8 L4 W- g& ]3 N/ K# ]$ e! }' w                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
# ?3 l! @9 O9 C6 C                                if (nums[j] > nums[j + 1]) {
3 `( B; V% y  V$ g1 e4 p                                        swap(nums, j, j + 1);
( y6 S7 B1 R/ d) d                                }
  a* ]0 j2 e% J3 K/ h& I9 u8 G. x                        }
                }
        }


" r, t  q7 O+ P        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
                nums[j] = nums;
                nums= temp;
( m2 A1 n9 v% t- {6 P6 m# S, U: W% Q        }


        public static void main(String[] args) {
3 s; t% T# g/ P8 F# O! j                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
        }
}
/ ~9 @( ~( T4 b1 J  O1 _1
2 T: @0 Y6 f! \; [8 T2
* n+ I" u: g( R3
4
5
# \6 l  u- F  k# t6 M6 i6
7
  @( }0 i. l" `  c0 j, e% d8
9
( b* j. Z& Q% s10
11
( O9 F5 u) f& @5 e. h( Z12
13
" F5 m+ x' Y$ _1 |6 Q9 k2 \+ w14
15
16
17
* c' K$ h  |+ y! }% G# j1 h$ X18
19
" Y! P! _5 u( M; Q20
21
3 f. |0 W7 X2 v22
3 y7 x1 k# d6 B- w! Y1 ]  l& ^23
: `$ U% }" r; t2 ?: B% t' f24
25
26
27
- E4 X2 G$ }+ a, ?. N2 X  ]# j* A快速排序
6 {$ V; o" r. _4 p# U5 b时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
1 a& E9 q+ p. a1 C
2 J- b; `- f" \- F2 V
2 j2 r5 q! j. @- G代码实现
7 ]- j3 x" h2 t/ R: I$ T0 A) V3 t
/ `, u8 J3 D5 _  c6 d
4 ?; W: ~# Y4 }( }( Bpublic class Solution {
       
        // Median-of-Three Partitioning
        public static int selectPivot(int[] array, int left, int right) {
( h: _+ Z+ ~8 x5 q0 v$ U2 }                int middle = (left + right) / 2;
               
5 e& [! ^& Q* r% O9 h                if (array[middle] > array[right])
                        swap(array, middle, left);
                if (array[left] > array[right])
- ]; x9 P6 y: f8 P" ^9 b, u8 `, ?                        swap(array, left, right);
% B% _( S  k4 e% O, ?6 q8 X                if (array[middle] > array[left])
1 a; D$ [  Q4 s                        swap(array, left, middle);
               
" j0 J8 V' Y3 {3 S+ e  I0 r                return array[left];
        }
       
        public static void sort(int[] array, int left, int right) {
/ p6 P9 a0 W9 Z# l  F8 F/ H. ~                if (left >= right)
- [3 I' b& {* T' Q, |8 W                        return;
2 i9 n/ m/ w9 C                int index = partition(array, left, right);
                sort(array, left, index - 1);
                sort(array, index + 1, right);
/ S( y9 h5 t& n/ H$ c% d: h    }
       
        public static int partition(int[] array, int left, int right){
        int pivot = selectPivot(array, left, right);
$ b0 C( T; m) v5 h7 m7 G        while(left < right){
2 W# L. s# P+ a. l            while(left < right && array[right] >= pivot){
: d9 B( }6 U& l: _2 F0 D( B& e: ^                right--;
            }
            if (left < right) {
                array[left++] = array[right];
            }
5 n, u, p5 q$ _7 @6 y            while(left < right && array[left] < pivot){
' _0 |8 I7 h9 S- {( W                left++;
            }
            if (left < right) {
6 f+ l7 I) U8 @, h* y                array[right--] = array[left];
% F  P$ F* D3 r+ X8 ]            }
. N( H/ ]. }7 {" r1 y  ?$ J        }
            array[right] = pivot;
) W* w* H) q+ q. d( S0 R( @) m        return right;
    }

8 b6 k9 V8 b) j6 u2 w, H% I8 e( s( S
* j# t: F, }* _7 D    public static void swap(int[] array, int left, int right){
            int value = array[left];
9 M! X- Z4 o1 q. s% u# O: L" s            array[left] = array[right];
            array[right] = value;
    }
5 r  Z% m/ J2 N, P
1 P, m4 r1 o. T; y
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                // System.out.println(Arrays.toString(array));
0 V* o( z3 N+ u4 _9 F* B                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
        }
. D3 M" j# X) _- @0 M4 P! G}
/ X8 ~. m/ P5 O& F8 I- V1
% E9 ~: J+ }: d  _; M2
3
4
5
  H/ S8 `8 J9 H, Q6
7
% _: m% K, f8 y8
* s% d  K% d; C, X9
10
5 \9 t4 p! R$ f11
0 A8 I5 I6 P& x' `6 w- K12
13
& G& q" l- S; d" C. V) ]6 {14
15
8 I& r! v9 m$ p4 S' v' E16
17
18
% x; A7 T' L7 m; ^. A19
0 w+ E5 d; l' t: e. v! m20
1 C. Q6 c% j/ z, O) K21
22
23
. ^' W- k/ S! m  W, U4 x24
25
26
0 N% P3 z. D# E: z27
28
29
30
( T6 z- k3 s* p, `3 }: ?31
# y, z& l0 ?9 S/ a32
$ ?. }+ \  E5 V. }  z33
34
: |& l. {- r% q+ N/ @35
36
* A: Z/ u- }* |4 [* c37
! H! B$ \. v; q* n+ z* X38
. S! f. o4 P& ~1 S% z) a4 a39
40
41
42
- h+ ^# L' r7 a: Q2 R1 H9 v43
44
. P+ G* O" j& @4 O( _45
$ z4 s: J9 X! h$ m9 X( B" M" K46
0 k2 Z8 h5 Z( r! q47
7 J% i' i9 e8 Y% \48
/ f- z& m1 Y2 U3 y3 e- p% n49
" M- d& a) [0 Q4 I2 H50
9 K& d8 V: C% n. ]9 `51
52
53
9 Y9 I, \7 s( C54
$ c" `& _  x( m( u7 q55
56
3 s7 ?1 U2 l4 G5 |' N57
6 J% ]9 I  R- ~4 g归并排序
" Q6 e) W7 i; l- x$ x" t; L+ d- i将长序列从中间分成两个子序列。
对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

/ y* }5 }& }. A5 [9 [2 d2 \8 b* b
代码实现**
9 W& X4 Z& G2 l4 J' ~7 H
; V! r  c2 @/ \8 ]- v+ t
, c9 k8 m; @# @# K5 l% dpublic class Solution {
- N& Z" ^: U) l        public static void main(String[] args) {
2 {) g4 u+ R6 y8 [2 b0 u                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                int[] arr = MergeSort(array);
* l1 j, f$ U! x. i) X& }                System.out.println(Arrays.toString(arr));
7 S+ k: h1 ?; E, w' y* w! k* O        }
  Z0 V, n& Q5 D% j$ [( P
: _0 z% n% {" E% R
        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
                        return array;
+ F& ?& N, g: q: d" T& O                int middle = array.length / 2;
" B# ?  Y) C3 n) j3 s+ }                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
* s& j$ `; D3 K' U5 }                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }

" I* S* H1 D! w
        private static int[] merge(int[] leftArray, int[] rightArray) {
2 V9 R0 r! ]' E5 M: v                int[] result = new int[leftArray.length + rightArray.length];
                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
                        if (i >= leftArray.length) {
2 d5 C0 F1 b2 K) t5 E: ^2 l                                result[index] = rightArray[j++];
                        } else if (j >= rightArray.length) {
                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
; X! [3 y& B$ C) z                                result[index] = rightArray[j++];
                        } else {
; p! e( Y1 A! a                                result[index] = leftArray[i++];
$ O3 A1 Z* h0 P1 W# ^0 D& L                        }
( d. ?7 o/ Q2 I7 }: S+ G- L: I+ I: X                }
                return result;
2 C5 a2 H. j  O: ?9 P/ y8 j        }
}

! s. H6 @3 |  f+ [& D
1
/ |8 D* _, K6 Y/ V6 ~2
& d) ~4 q; ?; h8 i3
  }1 ~- s/ m1 i4
5
0 M+ n* _) K! Z  b3 b6
% u+ A7 D' b6 k0 |7
7 Z( I) a/ i) P: x7 E  J8
9
2 H" s- p# r2 v" u10
11
5 r( V/ ?0 j- U. e( p12
13
14
6 B* N4 v+ @3 p  ]( j2 ~8 n4 M% g15
9 @( }2 w6 h+ `; s0 B/ A16
17
7 j0 c/ h( U9 L! i  F* G, H4 A18
; _6 g/ ~) d5 O3 @19
3 u8 u  U4 ?' q8 U: u20
" ?3 i4 x- E( D7 h! B2 U  c* t' \21
( J) z! `4 R# q" w22
23
& z8 C- B7 ]" N24
8 q; I* Y6 ]' |( S25
26
27
3 r9 S' Q0 X* w" D0 [28
& w: U2 `2 M+ Z0 `0 u6 H, e29
8 Y% ?, N/ C" i  G9 @7 H, k30
4 p  r0 ~. Q- `* s2 K# e: F- d) [31
32
33
! g. c, H6 f" d3 l# R基数排序
7 F8 t' }9 ]0 j# C找到数组中最大的数，确定最多一共有几位数。
/ \6 d5 R6 b& r/ }! @; \按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
; \8 A7 @0 m! ^2 ]5 a% ^将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
& q( F$ p7 w2 r时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
1 m2 \- p' L- ^# P8 }
5 @: ?# X; F: ]2 B- b: r( |
/ ]. o7 S' v* y代码实现**
( q/ _2 }. L( F& g1 o0 B% O6 \1 O

& x3 s3 J1 J$ w( }" F* Zpublic class RadixSort {

6 |4 T: R. {' [: i' Z$ v
        public static void main(String[] args) {
                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
                int[] arr = radixSort(array);
. {# g- M$ Z4 N                System.out.println(Arrays.toString(arr));
, h8 m4 {$ b2 C+ I! ^+ ?1 ^        }
1 `' x  b# n4 r" p  @
- \4 L/ m3 H6 p$ w' G4 b# u7 e
/ p+ c5 u, b/ K9 _        private static int[] radixSort(int[] array) {
& A# N8 g, f6 |6 A                if (array == null || array.length < 2) {
                        return array;
                }
6 I- P* t" T* e) ^4 j  M7 T! ^                // 根据最大值找到最大位数
                int max = 0;
                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
                }
               
                int maxDigit = 0;
                while (max != 0) {
                        max /= 10;
                        maxDigit++;
- ?4 |9 X4 v' r9 w$ x. O) j                }
, F5 M4 L# a8 Z3 I3 k7 X& f               
                // 第一维: 0~9
1 y7 g# w, a9 ?                int[][] radix = new int[10][array.length];
6 g* h( R) k. I* o' U1 S2 h1 S# b                // 该位为 i 的元素个数
                int[] count = new int[10];
/ q0 }8 M, B* S! Q6 J* V, i/ r: I               
& g) @5 h5 s( Q- v4 w0 z                int m = 1;
- m5 o* D% }: j, G                int n = 1;
               
% Z1 [  H' o) ?8 Z! @                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
                                int lsd = (array / n) % 10;
: L; I$ h, `  m6 Y                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
) G$ L1 {7 \5 j( K. K/ ]                        }
                        for (int i = 0, k = 0; i < 10; i++) {
% f( j& _. f& R8 v                                if (count != 0) {
1 X. {, F4 j: O- f" P                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
                                        }
: ~0 R2 r6 L% {! |  Z* Q                                }
                                count = 0;
                        }
' j0 ]0 o) G: s4 f                        n *= 10;
! H) S2 C% V4 E5 S# ?                        m++;
9 f* ~+ J/ w4 K# \1 L! G7 I0 t' Z                }
2 s3 Q, C# [- }4 z                return array;
        }

, R& p- {! j3 e1 P0 I* a' r4 C
}
9 c# u- u. W' |$ A  n) |" ~1 ]% v1
2
3
3 j5 t* i; J# L6 d1 ]- a1 I4
5
6
7
6 L3 z1 x  ^3 A% P, d- G4 c8
, e9 |% I  X: G9 b5 V1 L9 Q9
* @( F% @( B0 `7 I10
11
# x$ ?3 p% k! ^) A12
7 X. I2 c  L; g2 `13
" y4 P) O! U! o7 ?9 @. E/ B14
( ^( J4 N7 d. y4 _9 E2 t. i15
& y" Q# ]8 L- `! f' E16
17
18
19
20
; V! ?: N. @: ^0 ?21
7 r: e  U% v  D' @. S0 N22
23
) n* Q, ]3 v8 X$ T# j7 d) U! M3 C2 J24
1 E: [3 R  Y) x25
26
27
! b$ R  H' |9 Z! L3 x, l; [28
1 e! a) k. u- j1 z29
( |& G( J; f' S( [: S6 g: k9 w30
31
32
33
" R7 d" C  }2 o! O4 K. T; g! M34
35
) m' e7 b1 {8 F/ Q, b' X5 z36
' v9 _" d  ^3 I) e37
2 |' s- C9 E1 K& b. O$ |38
39
40
41
42
43
44
45
1 K7 Y1 C1 [  C# U7 d# p46
47
) q0 f3 P" F0 P. l% s6 s! {48
49
& H1 U& k1 k3 M) N50
51
9 f* ]7 L" o, n, B52
1 e  Q& N  t4 i+ m& I: J53
+ f: W. m( U, D6 ~! n2 J4 N计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
% p/ s, [( k: W7 L$ i统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
% B! ~% l5 h6 V# A9 _最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
0 O6 s+ ^! L& h/ Y

* _- s) s% `) f0 \$ a$ D代码实现


public class Solution {
# {5 `6 u7 q3 i$ {, i
( b3 T) d! @7 X/ j2 r9 g
6 d( `3 y1 K  Z- z' {        public static void main(String[] args) {
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
                int[] arr = countSort(array);
8 Z' B  q7 h% H1 l1 q4 R! M# `                System.out.println(Arrays.toString(arr));
" F& N+ M; u# H! O2 U4 W        }
7 i: ]3 r* Y5 d& {0 ~9 k& \" ~

. k4 E: j, D. a0 ?        private static int[] countSort(int[] array) {
$ G5 m* i  X2 p0 k) ^6 P, c                if (array.length == 0)
                        return array;
+ O, N% d/ D' G# `+ w& V! X               
                int min = array[0], max = array[0];
) S) S  q# M9 z, X5 n) C               
                for (int i = 0; i < array.length; i++) {
* O5 H0 v! E+ K# X# t                        if (min > array) {
2 X; g. v8 Y: D  @3 J) ]3 I                                min = array;
/ ~3 q3 o" \; u. Y; V4 Y2 ]                        }
6 Q! e3 \9 j1 d# V' B5 D                        if (max < array) {
; c  G2 K3 z6 r                                max = array;
. G; z3 k* z! }+ i" l. \                        }
                }
5 ~7 }4 c  U2 p5 r* H               
5 ?1 H) u( k1 f, G5 K+ h8 s' ?- j                int[] count = new int[max - min + 1];
8 }$ v& r2 i2 `1 O               
                for (int i = 0; i < array.length; i++) {
, k1 R# e/ o  ~) @- z                        count[array - min]++;
                }
               
                int i = 0;
                int index = 0;
3 k5 b2 `  L! A: P; u6 ~2 {                while (index < array.length) {
                        if (count != 0) {
                                array[index] = i + min;
                                count--;
                                index++;
                        } else {
, x5 V; I6 s. v! \) T* f+ ~$ _/ e                                i++;
                        }
! q. Q, `" n' `: v$ }* N                }
- Z3 g+ A. [" F9 L                return array;
        }
: }- |" o- W# V0 o' I       
; n) f  I' g! x}
2 M2 a# R+ K6 y/ ]- j9 v( ^1
2
3
6 z" a3 g( K- }: c4
7 Y% P+ A! F8 d0 ]/ N0 J. g5
6
7
0 Z: h/ ^# g% g( Q' _5 j8
9
10
11
, u% {  X3 E) U  C8 l12
0 i/ ~) g4 e# t2 }: @! z13
% D* T0 M6 i6 @0 U& K2 U- _14
15
16
/ \7 a6 ~: \* o! K3 [; H# M$ y17
! y+ g" x/ K: t% m0 U4 J$ p$ V18
19
20
21
3 V2 q9 x4 Z+ G+ ]/ }" Q# B6 M22
0 M' Y* ~# @* U' C23
) I6 Z) L. Q3 H% h24
25
26
27
/ `/ [1 z; Q) w" R28
29
30
6 f- @, U" s( r31
32
! A) {5 J) J, i2 h8 D( V33
34
& @& R4 ?5 U) t8 f& L% M- p35
, l4 Y! G. A& t: k+ G36
37
& h7 F) P/ M8 Z* @' H" }38
( x: Y2 i9 V) t5 E39
40
41
7 A+ ?& f+ X5 ?$ ]4 ?42
43
7 p* c0 w  B3 R! T) j/ ?, @( F44
桶排序
————————————————
; O# ~2 X5 A: X" f版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
: D3 ~) T: S3 I* T5 P, d, T原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
- r7 T, W  r2 z' u0 i/ v8 E$ g
$ ^! _1 L5 @0 N