十大排序算法（Java实现）

杨利霞

; Z* ^2 N, X. C9 w5 c% ^) U十大排序算法（Java实现）
- I% g$ o% p) ?' F
十大排序算法（Java实现）
排序算法框架
排序算法性质
插入排序
& q4 `- Q# E6 x. F3 L! j直接插入排序
希尔排序
选择排序
( F3 i# X( G/ B简单选择排序
# @8 w2 H; C8 Z# o& X2 F堆排序
2 C7 t% i+ V) s4 j8 C0 ]. u9 {交换排序
) r; Q0 W) y! V4 T冒泡排序
; Z; A. d4 E/ \( i快速排序
. l% Q* j' S9 ]: w; b( q! i归并排序
( p2 B3 ]  H) k4 G5 @6 N基数排序
计数排序
桶排序
& T3 e) q7 v% n1 H9 i2 J. I, h( }1 o更多文章点击 >> 这里
/ l& v  y2 b, C% U* C
1 M) H* i, [9 A. D  G' k  P
* W8 y$ h- A2 f+ K- Y9 d" T排序算法框架



- Y4 g# V& ~0 l* v
# B! ~$ r/ ?+ G4 w" j+ C8 [; p排序算法性质



8 L. I0 t: {$ c. e- R  v
插入排序
直接插入排序
/ i* M" t1 K9 t+ w) P从第一个元素开始，认为该元素是已排序的。
( q; _. K& S* _- n' z2 @取出下一元素，与前面已经排好序的部分进行比较。
4 N2 T4 K# M3 W若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
- Q6 x6 \% {" q- t2
) 。


$ d  b2 e% r, n0 J, }& }3 B! t代码实现

2 n- _( D  r: C# C5 G8 |
public class Solution {
        public static void main(String[] args) {
( J* F% G' _2 V0 [4 q% a5 E; n                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                insertSort(array);
  [3 ]' E% S6 f8 W- ]( |6 ]( j                System.out.println(Arrays.toString(array));
- S8 s$ P: ^  j8 a" i        }


        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
* Y5 f1 U, }: e* j2 d! x/ p                        int data = array[i + 1];
' ]" \! B2 V3 l: y1 R; j0 H                        int index = i;
9 B1 p1 M( B5 ?' R                        while(index >= 0 && array[index] > data) {
+ ^8 j1 {3 }7 j* ]# h                                array[index + 1] = array[index];
7 P. u, M1 O; @                                index--;
. ?0 T" T2 j: L: A, n; _                        }
                        array[index + 1] = data;
1 y0 _( |2 L  w; w/ H( V) h+ d6 W                }
        }
}
1
2
3
4
$ c2 h2 Z7 K1 v( f1 c5 c  S5
& B1 |7 S# S9 Z$ P1 N  f/ Q6
7
8
/ m$ \; g# b, V6 n/ R# e. v9
10
5 E' ?- G) v7 {11
; m# P1 d- x$ \' q* K9 x7 c12
13
8 X' Y% \6 X7 h& U" S' K14
6 k0 S6 p, |( Q, q15
16
17
18
5 N) s$ {5 ~, {/ u5 o; B19
5 g4 T  l: O$ D* j- c希尔排序
0 |' O  f, c5 u3 I+ Z1 r

' l8 h4 Y! b7 D! d7 ^- \时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

* o' j# \; l5 L; T1 J
5 O0 x2 ?/ Z% s( r/ b代码实现

! D5 B, X4 F1 V/ V6 ~
6 e! M. g; O' `+ S) Z0 \* Zpublic class Solution {
7 i+ D+ a# C8 U* F- S0 s9 j. J        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                shellSort(array);
1 ~% U5 c+ a, F. _( \3 A; K- d                System.out.println(Arrays.toString(array));
        }
. X; |2 C% ]% U9 Q# \0 J7 Y/ g
/ q% a( x# t8 {9 s4 e1 ~
' F" K! Q5 x; ?. v: W! D: S( B& f        private static void shellSort(int[] array) {
" {- [& z4 n7 U, I  x! H                int gap = array.length / 2;
                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
                                int index = i - gap;
$ ~  C4 }) \1 N+ g- m                                int temp = array;
                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
) |  w, B  F! J/ t3 i4 _                                        index -= gap;
$ T5 Z0 \# X( c' i                                }
" G& ]/ z4 y' M' A. q//                                array[index + gap] = temp;
                        }
; H- ]- P& U* [                        gap /= 2;
                        System.out.println(Arrays.toString(array));
                }
        }
7 F4 a5 r# @7 u

        private static void swap(int[] array, int i, int index) {
                int temp = array;
) R# T5 `3 I* ~                array = array[index];
: b# P; B6 b* v- H                array[index] = temp;
        }
}
1
) g, L  _4 S$ L& E! `2
2 n0 j3 i- E+ ~+ X3
+ g0 C% f7 K* A8 u1 }4
. p& H) I' w5 k( h9 u  Y# P( V0 @5
% K* }2 \: q1 [+ v4 E6
7
8
2 R  @8 |; H2 r! L+ p# p9
, t! @9 Z  b6 |: x; t- L10
1 m- \0 K, c) E3 H) a11
12
13
# i6 S1 m; P6 G* ?: D) P, L14
15
) r; }9 F8 q  W1 b16
# K4 O' r. L; e) p* Q* Q6 X+ ?17
18
) \7 H) H$ v% R- X% f/ b& D19
20
21
22
/ @% Q; @8 A0 i) r9 O' M. X23
$ c5 e% J) d8 U0 P: m  H1 i24
* ~* d  _7 J. U/ @2 j4 p25
26
27
28
29
30
  y' L, ~( n5 M# A选择排序
- V1 Z. ~# p( D& D$ F; [简单选择排序
从未排序的初始数组中寻找最小元素放置首位。
从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
时间复杂度为 O ( n 2 ) O(n^2)O(n
! [8 S- v' p+ \7 v2
; C2 l$ ^$ v0 M  y& C% O1 r) e ) 。

+ U: a2 y/ B* S7 A/ j* r
- V5 G: ]4 D- b( C4 g& ~: z' r代码实现**


0 N8 W% V+ U5 D9 o" Fpublic class Solution {
        public static void main(String[] args) {
, b$ x: G+ p4 a" k" G                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
                System.out.println(Arrays.toString(array));
        }
# E1 e& y6 ]( b2 i7 A
  z( @. t5 r: W3 W9 G" M9 R
        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
                        int index = i;
% o# K* C3 p+ L                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
                                        index = j;
                                }
3 M9 w5 {: Y7 f, e0 w8 v' A8 p                        }
8 u0 m5 n, c5 g' H0 a* z3 D! j                        swap(array, index, i);
                }
        }


        private static void swap(int[] array, int index, int i) {
6 P  Z8 `  }5 i$ C2 u  C                int temp = array[index];
                array[index] = array;
0 B' b# ?- T+ c& U$ M+ m                array = temp;
        }
}
! _" H; o; K# s- o9 k1
  F, @! d( u- a: B2
9 t) C% e  I" h5 [& _- j% O3
4
: L( c' T, H  L. Q9 z, P' m; r5
" y5 d) x# R8 w3 J  g, X8 _6
) o$ j, Y  P0 ^8 u  C7
8
9
10
$ X, C% g: f' y11
$ H" \, C. ]8 n! l. G, G12
* c8 D5 O+ K- U. l  j2 p13
; }- w1 w$ M. S& t9 q14
15
% Q8 [) f; u2 T# V3 o9 m: E16
17
18
19
" i+ Y5 U3 U7 J% [' x1 O/ G* L$ `. }* K20
21
* J9 Q; X% p# K% l, y# W2 v22
3 F3 o( d  K& B4 C0 h23
24
25
堆排序
% @) [+ _& j4 ]$ h! n时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


9 O( ]" i' V( d8 j1 {* e. m代码实现**
" n- q+ ~; d. H0 E) b3 O7 O0 q
; }3 u0 Z! F* o, K3 l: m* x3 P
/ b) L# r( R; {; U% E+ Gpublic class Solution {
0 f* g/ w6 N/ D1 T& k4 e0 a        // 建堆
        public static void creatHeap(int[] arr, int n) {
% |3 x" p. u1 x: u, i                // 因为数组是从0开始的
  D' o9 B% q# {; }. a3 J6 t0 r0 h                for (int i = (n - 1) / 2; i >= 0; i--) {
                        percolateDown(arr, i, n);
                }
        }
        // 插入
4 W8 u6 H4 Y- _2 m6 D, X" G        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
& @6 R- S6 Y! V$ R% W: ]                percolatrUp(array, n);
        }
        // 删除栈顶元素
3 M, N* E8 O: L7 Y% x  |        private static void deleteHeap(int[] arr, int n) {
" y, L( ?; |; ~; r. Z                arr[0] = arr[n];
1 k7 e5 U  q2 S! g- ~3 f/ K4 m( |                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
        }
        // 上浮
* ]( [, t6 j/ o; V, W        private static void percolatrUp(int[] array, int n) {
' s0 L6 `2 G! v5 e' O                int data = array[n];
                int father = (n - 1) / 2;
5 \, _5 B$ c$ q. E% y8 V, c                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
8 e$ D, [- C" q! |) I; _- }0 {+ A                        array[father] = data;
4 X3 f. R( `+ E$ o7 {* k$ y* X+ y: Q6 z                        n = father;
                        father = (n - 1) / 2;
' d: T0 d3 }# t) C) V& c! ]                }
                array[father] = data;
        }
        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
- t# j) M/ c% [                int father = arr;
                int child = 2 * i + 1;
: k1 u& S) U& {1 s+ a                // 遍历整个该根结点的子树
" v% s9 q/ H6 J: N                while (child <= n) {
                        // 定位左右结点小的那一个
, Z! T( i# D% M                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
! P. X) _( {0 I* f6 N+ v' }                                child += 1;
                        }
                        // 若根结点比子结点小，说明已经是个小堆
; F0 m' V1 v2 c+ i+ h- H) Z                        if (father < arr[child]) {
' u' n8 z& I# b* j6 c5 i2 P                                break;
6 }7 @8 Y  Y* b' s  c/ T6 X! Q) e                        }
/ r% J) z: ~! V$ D7 b                        // 互换根结点和子结点
* K6 ~) @/ v4 p+ ~  _                        arr = arr[child];
                        arr[child] = father;
                        // 重新定位根结点和子结点
                        i = child;
                        child = i * 2 + 1;
8 P% a# x1 ~/ a                }
        }
   
        public static void main(String[] args) {
* l- `" s2 l+ A2 `                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
1 \: D; e& j( a3 ~. B, L               
                creatHeap(array, array.length - 1);
% R+ j2 R3 E, B4 s, q                System.out.println(Arrays.toString(array));
9 r  L0 e' ]2 H4 q8 M               
                deleteHeap(array, array.length - 1);
, J0 A% u' \/ C% }) N                System.out.println(Arrays.toString(array));
9 E9 H2 A3 ~: z8 t' Z6 ^+ C: d3 n               
+ ?# v/ M3 a1 B2 T& |' y                deleteHeap(array, array.length - 2);
                System.out.println(Arrays.toString(array));
               
                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
/ A- B9 ^9 j% t( J$ a        }
}
. A& q* q8 F, X* X3 C- w1
2
, S1 p& p# R# u# N3 O3
% |: a5 e+ F8 ~4
5
) \2 e2 T4 K) n5 A0 L6
$ [5 Z  k2 Z" H7
8
9
$ c5 a! Y, ]0 o/ v10
11
% S& m6 [4 F' i12
13
14
15
16
17
) T# D3 t1 w" v5 N6 W18
19
, p5 ?, ^% t7 O4 C: g% n1 v! `8 `0 Q20
21
0 I/ k0 ~7 h' U5 T( _22
: i  s; v3 c* R23
% |/ W# t0 j1 m/ @1 t* a24
25
26
9 p8 k. F, _& ]9 j; k7 O27
; x) B: R" ?! x5 H( g  d; _2 s28
+ A% P* B* C" x29
30
: t. j0 A- f8 V31
32
% c* N0 X/ q* e; S33
34
8 B1 c/ R" v+ g35
36
37
  P, `- W5 g2 k, }38
39
/ ~2 T- d7 ]5 S: \" m) h9 G1 r40
41
" t2 _+ {1 Y' |- @& u4 o9 F9 @1 s42
( m( I3 {! |# D6 B43
44
1 s5 [& ^* y/ c0 u. l45
2 M7 g6 x7 [4 r+ c1 ~. n/ O! z/ S46
( R; m9 u" M* y: P& f) _0 h47
48
49
50
4 z. P1 N+ p. y7 R& B51
52
53
8 \3 p: Z0 V+ W3 Q) f  B54
4 D2 J3 J% l0 l* A/ X55
56
: b5 |8 }( r* h7 F& A# q6 _% Q% u57
58
59
60
61
62
/ ?+ K, V% p( \- O! g/ U+ X" `63
6 e! V' x( q# {+ X! {) e64
2 D4 U! n7 Z- n$ p' _1 m% K65
66
' H( q, b0 R6 Z* Q* d67
68
6 f2 N0 M. F! I6 K2 y69
70
交换排序
冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
, v+ |# M: O/ d: |9 q+ E- A) V在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
5 k- x$ _% J7 x8 B最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
7 B" H% ]( x- h) I0 Y1 T ) 。


代码实现

! H2 j. f7 Q' a2 u8 \$ [
import java.util.Arrays;
public class Solution {
       
2 J6 \; L& W* R& J, ]$ _        private static void bubbleSort(int[] nums) {
1 a' R6 D, S; V                // 循环次数
( G; t, D$ W# ]" ?3 Y4 C8 P                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]) {
5 D9 e; L' @3 a                                        swap(nums, j, j + 1);
                                }
                        }
                }
        }
1 P! Q* _- A! s6 S% A0 ]

        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
9 d, A8 W: N& C                nums[j] = nums;
                nums= temp;
. e% p1 t, D  w7 R: K" ?. @- h        }

, T% f5 ~9 P7 _7 S
7 |! g7 R' V9 [4 h1 a: z' J        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
4 O6 P' N* X/ B$ c                bubbleSort(nums);
6 x1 t2 S' ]: N5 g2 E( }                System.out.println(Arrays.toString(nums));
        }
0 r8 Q  B8 k  w/ F2 }4 c}
0 J- c0 v4 ^' L! M. L1
2
) @  a: C9 y' g1 w3
4
% n) `) m7 J' G# m5
6
# G( Q9 |1 ?1 U# g7
8
7 ?5 V- [) Z9 d* b, P, A6 g6 w# `3 V9
( w- m+ U  S9 h5 ]3 ^/ J  X10
11
12
13
+ o5 B6 Q: E3 {1 z0 N14
9 Q" y: Q1 O) `* O15
16
$ o0 |. q2 _* P( H17
18
19
; H; c' y+ j8 j: A6 O9 ?20
21
  Z  L2 h) E5 V! U. z: i22
23
0 }% }; Y2 E9 a: z: g24
! {3 @; y9 T- e$ B# q" A  g25
" V; p2 E8 {, C5 f/ q* ~- b26
27
快速排序
- o: t1 @) ^/ S! K* _, Y9 ~. i, D时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
( _. c0 H+ ^6 H0 m8 c" p
- m& }4 C4 c$ F% D
0 }- Z( }# `& W0 f9 `1 V代码实现
5 P0 a" b, F2 g8 ?" R1 `/ t
% C6 d' e; M6 i4 h
public class Solution {
       
7 k, p* A  A# `4 r        // Median-of-Three Partitioning
        public static int selectPivot(int[] array, int left, int right) {
; O8 o7 [2 g' `                int middle = (left + right) / 2;
               
- n5 k' k0 a8 a  ?- y/ ^& o                if (array[middle] > array[right])
                        swap(array, middle, left);
% ~/ Y0 m7 F3 K( G6 \                if (array[left] > array[right])
1 N! T& L# s! b                        swap(array, left, right);
) a9 E3 _: \1 w; V6 E- c$ o                if (array[middle] > array[left])
# J8 h0 E& b  S: l/ j: }) d+ M9 p                        swap(array, left, middle);
               
7 A8 f( V( _- m: J; r8 _! Q  m                return array[left];
        }
       
& v+ z  T& \4 r1 r! H7 u        public static void sort(int[] array, int left, int right) {
! K! J& ]4 i. O4 ^( j                if (left >= right)
                        return;
& J* ~8 |* [+ i  U# e$ b                int index = partition(array, left, right);
                sort(array, left, index - 1);
                sort(array, index + 1, right);
    }
; ?  J7 J' \2 d( ]' i7 N       
        public static int partition(int[] array, int left, int right){
. I2 c0 T7 X( @& O% X1 `; o+ a        int pivot = selectPivot(array, left, right);
        while(left < right){
            while(left < right && array[right] >= pivot){
. u$ L- A6 h8 X' _* T2 h2 P                right--;
/ S' l, S, @: I            }
. D& f( L8 E3 a) }  y            if (left < right) {
                array[left++] = array[right];
            }
" X  Z0 O2 w9 b            while(left < right && array[left] < pivot){
8 V# M4 ?/ A5 b, b* G( ~                left++;
            }
+ ], s! B, g+ Z9 p+ N            if (left < right) {
/ N; w  r; n# g/ P* Q/ W                array[right--] = array[left];
6 M& o+ B4 ^# Y# ^- z/ ~! E            }
  g; b8 p- O; R% K7 w' u( R        }
            array[right] = pivot;
        return right;
6 J7 F/ J( r4 H0 f2 @, y& {    }
% _/ h1 k) i0 S+ r" ~; e" L+ n5 ~- D

9 C/ L- C, ?& A& P3 m# J    public static void swap(int[] array, int left, int right){
  B) b* P; }7 [9 \  w            int value = array[left];
6 ^0 F2 v9 a6 K' M& A- Y            array[left] = array[right];
' h0 H3 r7 ?# Y: `3 g8 u& P* |# [            array[right] = value;
    }

2 W8 Y# Y4 |" h" e$ U" [1 n
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
, a* r- |1 _% |                // System.out.println(Arrays.toString(array));
6 i: R. p3 W! l& s& w. w                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
        }
}
1
2
0 D3 U. v/ J5 k6 m' d3 Z3
9 ^, W4 @6 a/ J0 e+ y4
5
+ C( Y( U* m4 m! _& p9 Z6
5 z2 [& N- Q& _. B* x0 j% V7
8
9
10
11
; W4 G$ B/ v6 J8 Z+ y; W6 x  u& j12
13
14
1 W3 h, j- r; |# @# f' Q" t15
16
! P  B  R, W8 H& t17
18
19
" V8 ]; v/ [' \, t) t% C20
21
. ^! @% N$ @$ s  i, x22
! j. L( K/ \3 N1 D- n% u. F7 J  p23
7 M9 `. L9 b5 \% U" B4 l24
25
2 }* ], r1 K( v$ J3 w% `26
1 ]' O% I. }3 P$ ?% i+ d27
28
8 Z; F% h8 y3 g29
4 S0 Q. Q. l2 w, G30
! _; ~- {2 W2 @. c1 }& X31
* \! T9 Z5 l( k% O# J32
! c% }( P5 U% C33
0 e3 m/ A, W! Q/ ~34
$ e0 }) Z0 f- v& o, f35
0 H, @. w3 C# f8 {# [) u2 {# ?( P36
' c- x. g' w6 ?# x37
, v$ @( ^) y- b" f& C6 ?0 O38
) t3 i6 T; s" y$ {; t& t- c2 Z39
1 Z$ x0 i0 j% g4 k- P' a40
3 Q+ U& U4 ]- p0 G41
42
43
9 |8 |4 ~9 V" L. E, z5 r. K44
3 H: Q6 _5 x- f& c, r( ~1 z& z45
& ?' W7 j1 F; U: o( n& L. t* Q$ S0 C46
0 i2 w' N, ?& T# {7 g7 Y) l) e47
48
7 @3 {3 B5 D* A8 z& O+ m; k% ?& o  v49
50
51
52
53
/ m0 m$ l7 k- K  E, o+ E+ _, ]+ x54
55
56
57
归并排序
将长序列从中间分成两个子序列。
+ ?- b4 g/ c6 L  ~对这两个子序列依次继续执行重复分裂，直至不能再分。
* R. j5 ^) C" O: ]) L* S+ C递归返回两两排好序的子序列。
7 S+ g# Y: [$ G; F# S' I平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
) V. F3 B1 e4 n. v* R. V+ Y+ B

! |" R$ e4 A* e! K7 j代码实现**
1 D' Z* v! ?0 l
6 u8 B& d' d& P& T! t' {$ V
; U4 r1 ~9 o8 t8 gpublic class Solution {
        public static void main(String[] args) {
" L" A1 ]) H3 S. \5 ?% R                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
" U" q* y$ d1 M% [                int[] arr = MergeSort(array);
6 _2 E5 c/ l' Y: K$ ]                System.out.println(Arrays.toString(arr));
1 D. ]' b  J) Q! _: g        }
2 u+ T# _& d3 Z8 k4 Q7 }$ E+ R$ }

, a8 c" e! G: ?( ^0 T/ t        private static int[] MergeSort(int[] array) {
$ M, d3 _' F: F9 c9 F                if (array.length < 2)
2 R( J8 [( g( O# y6 G7 x* n                        return array;
- T  O" z7 C7 d3 O  B                int middle = array.length / 2;
                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
0 M" o0 S" ]9 }                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }
/ H" g+ I8 A  W4 J

! o- b& o4 B8 p        private static int[] merge(int[] leftArray, int[] rightArray) {
9 k4 h' H# e7 _0 ~                int[] result = new int[leftArray.length + rightArray.length];
                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
- g9 i6 i. X+ P$ i2 k% w                        if (i >= leftArray.length) {
                                result[index] = rightArray[j++];
9 ~! a: I; h  K" G7 I* P( e. c) W                        } else if (j >= rightArray.length) {
                                result[index] = leftArray[i++];
: D, S/ U- s/ x' K: L6 ]                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
" U3 `8 W. P3 V( J) K2 e                        } else {
                                result[index] = leftArray[i++];
                        }
# d4 L# w9 c% I6 S/ d( J9 [8 X                }
* M7 k: M- g7 x, W4 n5 `% y" [6 ^                return result;
- R1 f; ^; p! }4 D6 S" G! t        }
. I) p5 i. x1 s, X/ g( ~* w}
, e! J; N2 w+ x# a( c4 g8 l
" e1 h$ @( _$ }6 x  N$ l" @
1
8 K! N8 ~. L. O. d9 M3 l2
3
- l8 v) U- x1 Y+ [6 O; A+ U4
5
6
7
8
2 d) O% T5 n& ^1 e$ S$ n9
3 P5 E* O' R! L# V) S10
11
/ n* q7 N$ J5 f- r/ X; a$ W- ~12
# E4 s" r8 v( c4 m13
3 J* d2 O5 W. y0 g8 j  P3 H14
15
16
+ W& ?9 Q  m) ^" B2 f# }17
* ^: y: M6 @3 L% f! K7 Z18
+ F% g, {/ p) K# B& [: z' K19
20
: E, P! t; l( t& R0 [1 D  t21
22
8 e2 ?. l, C0 N: {3 t1 ^- F23
24
! f$ t% h2 {+ h3 h  [; Z0 j25
! |3 y, s. O, U. J' h26
% Y* m2 F0 H7 [1 B0 ~* ^1 r27
28
29
; w, |+ i4 n: C30
6 ?! O" B4 l* c3 K31
32
1 a& @& b* K. Z8 Q33
基数排序
7 s% v* m1 k8 j# e找到数组中最大的数，确定最多一共有几位数。
' i* k  i3 l: X  P按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
# q7 i- q) Q2 V8 M将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。

8 V& ?  ?. {* e1 U
( L! p6 R/ j7 \: z代码实现**


public class RadixSort {

5 ^( I- J( n3 e( F/ i; Y
        public static void main(String[] args) {
5 ?$ ?1 p. [  l( {9 u  C                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
                int[] arr = radixSort(array);
                System.out.println(Arrays.toString(arr));
& R" g2 B, p2 c/ s/ ]        }

3 {# c& T/ ^; L& @. X; U
! e( O: c2 L& X1 c* x0 S; ?5 z  U        private static int[] radixSort(int[] array) {
( j1 |. j& ?: r* z& t, w& P- f2 H                if (array == null || array.length < 2) {
, x: X$ R" f' \" _                        return array;
% g7 V% u1 f" x! ?4 c: W$ O                }
                // 根据最大值找到最大位数
5 Q- W" F7 }/ L( E5 @$ H                int max = 0;
                for (int i = 0; i < array.length; i++) {
# u6 h+ [# {/ S" T0 w2 \                        max = Math.max(max, array);
                }
               
9 W! d6 K$ [5 T9 ^+ R8 o                int maxDigit = 0;
                while (max != 0) {
                        max /= 10;
                        maxDigit++;
                }
- E3 _! s# y2 A0 c               
. u# F2 J5 A  L# a9 _9 A) i9 V; u                // 第一维: 0~9
                int[][] radix = new int[10][array.length];
                // 该位为 i 的元素个数
                int[] count = new int[10];
               
6 ~$ _+ O' Z' h                int m = 1;
                int n = 1;
6 S6 H4 M) }. [* \               
                while (m <= maxDigit) {
* G$ @- E9 o, Y5 L* f; P5 Z; H  \                        for (int i = 0; i < array.length; i++) {
                                int lsd = (array / n) % 10;
                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
: B6 O2 F# u8 d                        }
. H' u. ]1 L' C3 h6 v" V                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
9 ^8 w: T' c5 O3 b& E  z$ G                                                array[k++] = radix[j];
- [1 N* w( ~, O                                        }
# W' G0 O3 g4 I& X! e3 w0 ^& }                                }
- T# S9 r2 }6 e8 k$ w& I) f                                count = 0;
                        }
9 W, x7 l. H" k+ E% \; b% P6 F: x  s                        n *= 10;
- N5 J" \& a% s1 b                        m++;
                }
) i- ^# ?) _: F6 t                return array;
        }
5 r) C$ C7 Q% |0 t0 P7 W& d  h* Z
: G+ f6 W9 o( [5 S4 K" E0 |
; M" g9 H$ S( O/ G) W% Q% g}
  W  ~5 t0 v1 X/ J& `1
  e5 V/ {/ u8 e& }' @) E2
7 A9 V) j3 D6 j+ d  j, ?/ R3
4
4 T2 |3 W5 t, N, t  ^& Q' f+ r5
% S4 S8 A, A! Y  x3 k- l6
7
8
4 i0 \. B% d+ K. W8 d$ ?% q9
8 i# U. c* T) [1 @* ~10
11
12
- C- c* Q; x1 |" A13
# x, }4 w+ ^; |( I& L( m7 Q14
& }& E! k! H' L9 C4 C# O3 s15
16
: n/ M6 I4 z8 T4 F$ e& Z* X17
18
- u- k1 f; H$ ~19
0 {% ~% b. O: H6 x9 g$ D% R20
# H/ M1 w% M9 W8 t2 N9 \21
22
- [+ j3 p$ t+ g* B6 Z* n8 D+ W23
24
4 M/ D7 W2 A! T" d25
26
( a9 b5 `9 P* Y* [! w7 i3 j0 M27
" o4 j4 O( k7 K. Q% s7 k28
% f7 S% _# I# Q% m% c29
/ v' S: S' u' e8 Q% w& w30
4 s  }* Q2 g, U0 @31
3 Y2 v6 A8 E6 M8 D  j4 z2 L32
33
34
35
36
1 F* p/ g( K9 Z0 ]+ P6 O( B( J37
* V' G0 X9 f1 x9 S7 T5 ^# \2 `38
$ h( G) B, ?& E7 h  E8 ]39
40
41
, n  ]4 q  Y& y% G' v) N  k+ Z42
43
44
; c- k, d  [7 C& q& f+ b1 A; x45
/ k- Q* f- G; F3 k( T! P46
  t+ }' d. ]6 Y" R  ?3 ~3 m4 Z9 J8 s47
48
; q# X- g/ T% z  X+ K7 Q49
50
  z% B& {. j; z. G. d) P' e8 H51
4 k7 o) h5 B* U) }2 O. R52
" ]9 B+ n- E4 \0 M( {53
计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
0 J) y5 N+ R# c' H/ l统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
, A: R: D6 D0 H# n8 P. _2 K时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
) m3 k. Y! K' h; m$ M* J

& @$ @4 L; s5 \+ ?6 T% Y代码实现

/ ^) ?0 T. P& D* m8 u0 T
public class Solution {
! Y( C9 e6 S1 |# L, b
- E3 }8 P. ^) k
( F. S: ~0 Q/ ]4 o        public static void main(String[] args) {
$ M+ H! g/ W& ], l                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
        }
6 x. H: g/ m" W

4 Q. f- m9 P: F        private static int[] countSort(int[] array) {
                if (array.length == 0)
- v8 _& Z+ B' M0 V: k                        return array;
               
                int min = array[0], max = array[0];
               
) _3 q* x& B& `                for (int i = 0; i < array.length; i++) {
" ]5 K) r5 ~3 X( T4 n& P! c                        if (min > array) {
: i& F: o2 D! ~/ t. M* n0 [. q                                min = array;
                        }
% T0 U: n; K; V5 p) C- J5 S. {: ^' g                        if (max < array) {
# d( H5 O# v* V                                max = array;
0 a7 M) D9 l' S( }9 Z3 D                        }
                }
0 u, R- \' [8 f5 b# o4 X               
                int[] count = new int[max - min + 1];
3 X/ a- s. l8 _& R, w               
1 G7 }4 F! m* X9 ~+ {                for (int i = 0; i < array.length; i++) {
4 l7 W! |- ?" A3 ~1 _: B& w                        count[array - min]++;
                }
               
                int i = 0;
$ S7 P" J' z5 e' h8 e                int index = 0;
7 T( B- W" k& l! X. `                while (index < array.length) {
( h5 I7 `6 m7 g4 Y! T                        if (count != 0) {
                                array[index] = i + min;
                                count--;
                                index++;
& T' G7 x! J  Y6 o                        } else {
) i! h3 y9 q, V' w                                i++;
' `) D" U! P  i7 }, T                        }
8 o% C# t1 \7 u7 C& _/ s                }
                return array;
        }
( _3 R) y9 d0 Y1 d3 ^8 {# k9 O       
}
2 U2 {2 d( _- m1
& U8 e: b+ C" _2 \7 @0 W2
3
" {, I" h1 W6 |* v  m/ i0 T! r4
- p% M0 m7 d$ X" b, o7 t9 C2 r5
6
7
8
' |# c: q2 r" T* T& h6 x2 @/ L9
, R  b0 u9 J0 a3 W( c9 g10
! p$ W2 Q# x: b$ r11
+ B! ?$ V. j% H12
13
14
15
16
; ~+ q+ \5 V' Y, h7 U8 F17
' M6 K  R8 G. ]" o% M: q3 u9 S4 M& c18
: u+ r! k. c5 w, R' W4 ~19
- v( X2 ?) ?& _& d20
/ {5 x# l* L! d$ n21
22
4 H  P& ?5 R$ D( L/ [4 d23
+ D3 Z1 S) x  S. N+ u& F24
25
" [: b6 `5 O( M) h2 Z% ~26
3 a6 o: d- K. v" U27
28
29
30
31
32
33
34
35
& `  X9 y& U/ S' ~2 W& p36
37
38
0 ~0 r8 s& X* T0 p+ s39
" a0 w' o, ~7 V% H9 P: Y# K/ r# V40
41
* a4 T5 `( w$ b& A7 r) d" l6 r! K42
43
# Z1 c/ `& }, E' D( {44
桶排序
————————————————
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
4 O/ {. ?- M/ G
1 e1 |1 q# U$ m( K
) h4 @" r2 k1 y3 k3 ?