十大排序算法（Java实现）

杨利霞

. H% I7 f$ w' F2 M; x十大排序算法（Java实现）
1 N% m/ _0 r4 Z; U+ A6 }% s
2 f4 T3 p( s6 @3 C$ o! S9 J十大排序算法（Java实现）
排序算法框架
: X$ X) p% C% ?. |% r# Z- ]" L排序算法性质
插入排序
直接插入排序
希尔排序
( ~) w. r. T( Z' r4 o* o& g选择排序
简单选择排序
堆排序
; \% Z  x$ P; r# F/ f: ]8 J交换排序
冒泡排序
0 `! X. @6 a! G/ Y, H$ t1 f快速排序
+ M8 l3 W& `4 p- p+ z) q$ P9 s归并排序
基数排序
计数排序
桶排序
更多文章点击 >> 这里
5 U3 \( x' c' K7 }, o- ?/ h# [. ]

排序算法框架
" c  A8 ^( L7 O1 F3 C
4 [5 m( b& L: B5 l( }
. }4 ?" A2 d; ?6 l5 ]! h3 l

排序算法性质



+ |$ w7 i2 r% \- ~( g3 C+ [' S
' m( h2 P9 @6 o% H插入排序
直接插入排序
) N5 a8 g& o6 N5 q' u! q从第一个元素开始，认为该元素是已排序的。
取出下一元素，与前面已经排好序的部分进行比较。
6 i- ]4 a! O" W% i若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2
  Z+ ~* H( r+ O7 s+ p& ]' U/ j, `' g ) 。
" a  y0 c$ c6 \3 k+ |% p3 v* |
( `' d* t, ]; Q9 R- K$ j
代码实现

7 S( F# b* C" F8 y
# M5 T2 a- J! g$ l7 m: F  L4 \* _/ w. }public class Solution {
$ o' x- h, K) q7 U9 K! o( `        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                insertSort(array);
                System.out.println(Arrays.toString(array));
* z6 ~6 q* X0 ]        }


6 e" J. l# c' {" F1 Z, A        private static void insertSort(int[] array) {
6 A5 D9 `" f. L7 }) r/ S                for (int i = 0; i < array.length - 1; i++) {
+ k1 }8 m  r6 {" M( o- |                        int data = array[i + 1];
0 v9 b/ g! x% e2 z: ?                        int index = i;
4 K$ ]& E2 U; [" q                        while(index >= 0 && array[index] > data) {
                                array[index + 1] = array[index];
1 |1 ~$ U+ Q/ P8 O  m                                index--;
4 p' S+ j6 P) d/ I+ y2 [6 h& y( B                        }
                        array[index + 1] = data;
+ S( k3 E( {0 d4 H$ Y' r$ h1 G4 Y                }
& y, u  E8 @- |5 h; G        }
}
1
2
2 n1 C  K1 l' [4 Z7 E# t2 m, B$ K3
. T! p  K0 F, Y  J2 a# E7 o4
; H/ D& \- Y3 p1 v0 O5
3 F7 q7 w  R2 b+ x6
* x: y; c/ O8 ]* h8 \* C- I7
8
9
10
2 W- S0 P* D0 r3 C$ O# p! n5 n4 f11
12
+ g) C5 q5 K. Y/ T- a8 t/ C13
14
8 e# r% |% q, j& h( O2 \$ a+ ]15
8 e/ g4 C# V/ Q! g8 a- _16
7 w- @( U8 _, [, W6 S# S3 M2 g5 g9 V0 T17
18
19
希尔排序


/ G: o6 ^) H5 r时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
+ g! o' W. D/ c( L0 _8 d0 v

; f# X$ x" b4 z$ S" I代码实现

/ j8 k$ L9 B3 i! X! F
; D$ I5 c2 t, ~8 o  Fpublic class Solution {
( e# w  m3 K, u* X! x; W6 R        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
( l: v( L5 i+ w& j) E5 K: ?; g                shellSort(array);
                System.out.println(Arrays.toString(array));
        }

: _' V9 }" M) e8 o4 n# L
        private static void shellSort(int[] array) {
' o* \# I% M& ~$ w                int gap = array.length / 2;
- v- V& c0 j, D+ s+ Y                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
- R7 S* U- W* o+ ~# @                                int index = i - gap;
                                int temp = array;
. [: G; e' P8 E# T& D                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
                                        index -= gap;
! b; m: v0 z9 E3 _8 W% G                                }
//                                array[index + gap] = temp;
                        }
9 @6 }8 n" \5 s, M  V0 y3 N8 r, I                        gap /= 2;
                        System.out.println(Arrays.toString(array));
                }
! A9 q2 v# x) p. z1 u0 A        }
; v3 k9 r+ v; M0 o' {' O+ D
+ V) k/ n9 `' Q3 P$ Y$ z6 b
3 e' d+ g0 }5 M% t, s0 \6 k9 S! \3 v        private static void swap(int[] array, int i, int index) {
; q1 @$ F. e% F3 d1 k- j                int temp = array;
4 K& R- Z9 T1 a' }. l9 a1 R                array = array[index];
                array[index] = temp;
: T# c6 t5 n. E( `* t& E& r9 i, @        }
}
1 p3 ~9 g) c6 f# V3 o. I) [3 K1
' ~: d# N+ n2 t# g2
9 [9 j) O" Y3 |- W# {; B7 O- J3
4
5
1 P" r. i6 J6 N; `( E! T  Y$ u, _9 a6
7
& g3 R- z" x' M5 g8
9
10
6 I7 C6 G) l, D% |/ M9 g# {9 C11
# J. x$ |$ u6 S( K% l8 x- x( z12
13
8 K7 ]) t& B$ ]5 \8 X6 j6 {14
0 K8 I' n, @7 N& M  }8 J15
16
17
18
19
( \9 T- ?: N' y' K9 g* o+ S& p20
21
8 K( A' [' }$ \22
. y( T. Q9 ]5 B$ V2 V& W+ }23
& ~) S& N; x5 A6 ?7 }24
25
26
- Q6 ^/ `0 ?5 f27
4 |; W7 q7 x: k1 L9 C+ ?7 x28
29
30
选择排序
/ m  s4 g5 z& P$ J( j3 R6 i7 [7 z简单选择排序
# g+ B! m2 ~: D$ ]- _- o1 g$ ]! e* J从未排序的初始数组中寻找最小元素放置首位。
从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
时间复杂度为 O ( n 2 ) O(n^2)O(n
" v+ P/ _8 A& c! H/ Q2
) 。
. ?6 t9 X2 }& o$ f, r
% d2 P1 N1 t5 _/ b) Q- u# d- L
代码实现**

0 {* `) X# z- n' D7 o3 t6 q  T7 `
public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
3 n+ W: L! h5 ^  ^1 G                System.out.println(Arrays.toString(array));
- U; B7 H' c0 }        }

- g: P1 p" e; J2 k" n# t* M
        private static void selectionSort(int[] array) {
: ~, x1 j) D1 E/ G0 e0 k9 s                for (int i = 0; i < array.length; i++) {
                        int index = i;
                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
( S; B$ ?- m! N/ G+ v$ J$ P                                        index = j;
                                }
                        }
                        swap(array, index, i);
                }
/ q( L$ V- ^% L: a! k/ F; M. E        }
9 l1 Q! D( P* F; Q
$ _7 v6 c/ i& s% D$ }
        private static void swap(int[] array, int index, int i) {
8 T! m" o9 [; `. U2 }3 G5 r  h# L8 P                int temp = array[index];
$ m' C5 @5 O- E: m. |7 j                array[index] = array;
                array = temp;
        }
& L; X! {" ?; P( A}
  ]6 x, s( F8 V8 W% n1
7 n8 r) c! x3 V2
3
4
( B. U3 X  z0 U( I- Z0 X5
$ Q) Y7 [' f0 S) ^7 x6
& s+ _5 k) l  a* r7
8
9
/ {3 k$ F" A' D* i, v: f# ]10
6 j0 X( Q2 m3 E& T11
12
& Q/ Q5 m) l0 @  }$ g13
9 E( [  @" i) B' B" R14
15
3 p, w% p5 x1 h. f6 T+ s2 M% p16
- d; I0 L# s9 Q( ]17
18
* g# @$ ^5 ?/ q$ A+ ^# ]& B+ w19
20
21
22
9 F& S, z) Z/ i- A23
$ {/ K9 {8 p. Z24
25
堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
  [6 Q; M$ Y3 `* R9 g0 v

代码实现**
4 q: P6 C, K+ A. e1 A& e
8 h( c; t2 M, u( p! R9 {
6 m4 v* P6 N8 _1 J( _9 dpublic class Solution {
        // 建堆
        public static void creatHeap(int[] arr, int n) {
( E. l+ k. U( J+ {; \) ]0 O) }                // 因为数组是从0开始的
                for (int i = (n - 1) / 2; i >= 0; i--) {
                        percolateDown(arr, i, n);
# f8 J" z( f! h% ?0 h                }
% c8 J5 t1 D: b7 T7 t3 }4 U* a        }
        // 插入
        private static void insertHeap(int[] array, int data, int n) {
* _( w8 _6 J# T                array[n] = data;
/ f2 u8 f! i7 g! ]                percolatrUp(array, n);
        }
. ]8 _0 K+ `& R7 B% V# j        // 删除栈顶元素
' @/ s+ c; z1 I' S        private static void deleteHeap(int[] arr, int n) {
3 l* ~$ r, \" m$ P                arr[0] = arr[n];
. H& i) V. w8 d6 Z                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
4 y8 V' w# B6 `  C6 [! ?        }
        // 上浮
2 p4 x2 F8 f9 D. d  B' a/ e9 Z        private static void percolatrUp(int[] array, int n) {
                int data = array[n];
& k& Z8 ?" x; @- B( X, ~9 Z                int father = (n - 1) / 2;
$ K5 n8 p9 K6 E! ^$ u6 o                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
* o( ^- E* V0 k" c; u8 n2 l                        array[father] = data;
                        n = father;
                        father = (n - 1) / 2;
                }
/ C1 \2 i. ^6 |' L                array[father] = data;
* v8 A# G3 D1 B) l        }
        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
                int child = 2 * i + 1;
5 V: e* b- y- X1 c9 k/ K                // 遍历整个该根结点的子树
' [* O( J; g1 T; A% h/ o$ k                while (child <= n) {
                        // 定位左右结点小的那一个
                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
                                child += 1;
                        }
! e# }7 W1 x0 a) j, G+ J                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
                                break;
                        }
$ f3 r* V, j$ Q' }                        // 互换根结点和子结点
/ G) M" k* X. F8 `/ y& Z                        arr = arr[child];
                        arr[child] = father;
                        // 重新定位根结点和子结点
& M+ x) V$ G: q2 G* g                        i = child;
                        child = i * 2 + 1;
/ x4 Z! J: c) {' m, ^( q' ~                }
7 x" N8 C* s- A, T! r) Q        }
& \* v5 {5 u4 y1 v7 D" P3 A4 I) p   
        public static void main(String[] args) {
. C6 U" y# y$ ~. ^' F+ u! X                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
: T1 X) p7 N0 q4 h: i6 R7 m  r                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 1);
$ P9 ]4 P; q# ]" T                System.out.println(Arrays.toString(array));
- T& Z! k, o; w5 h7 P, d* O               
                deleteHeap(array, array.length - 2);
8 }1 f4 Q$ ~8 r4 ?                System.out.println(Arrays.toString(array));
               
                insertHeap(array, 3, array.length - 2);
2 N  `1 H6 ?% [$ ]: t9 J/ r                System.out.println(Arrays.toString(array));
* \$ W- [8 i) Y0 V+ f        }
7 i, `% F' Z2 r5 I" l- u& _}
: J+ m4 G0 t' B9 f1
2
' t# q* F5 W& ^/ @0 k1 k3
0 s% u* F# D. `; G* q4
5
( |% e/ a7 E( z/ C! ?9 u! g6
+ h! |$ r5 _/ C7
9 q& s& g0 G4 p' p( }! i6 K, {/ U8
9
10
11
12
7 J3 ]& e- u( @3 G8 R! A8 y0 w$ ^13
14
4 i% S/ ^4 v( j# q1 h& v15
16
17
7 F9 P, G- o! S18
$ a) c, @2 M0 O# u( x19
20
# }. q0 j* ^/ R, r2 P8 P21
& b7 k8 r8 r: Q9 L22
23
24
25
26
& |2 X. X" U+ X8 e! S+ w4 b' Y2 D27
28
29
5 d. L$ U3 i: g! b' I( x/ q30
31
32
" y8 J* J/ D8 O5 q33
34
35
36
37
38
39
40
41
42
43
8 b9 P4 o- O  P9 `44
45
- a! l0 B- Z/ |/ ^8 U; s46
47
' Z; E5 ^) f. O, D+ m48
+ Y3 o8 w4 d* [: G4 k49
/ }  V$ o( P% ~# W1 h& t# O50
3 h( ]/ V; D5 v0 E9 f5 a1 E51
. @( E$ N2 p$ E0 b3 d" R8 b52
53
54
55
2 L6 N8 q8 h8 O# X56
' ?& \' d0 B5 c7 @57
( G0 V! P$ W# m9 P58
59
60
! G& ]) `* q0 m' x# i61
" L# X' O- |2 I4 y5 L: i. V3 ^6 W62
; p3 g1 w/ r! Q" I' Y  j. o) k& _* H& {63
4 R( w; B1 J; W. x9 {1 v9 k  s64
65
66
, W* C0 T+ m$ p2 {# B67
68
/ B' `! T$ J% V3 b$ x69
70
交换排序
冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
$ m2 x% S' O' H  V! `遍历数组，直至结束。
+ z  I% [* H& x$ ]' Y3 B0 u最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。


代码实现

1 j# [% M; y# U5 j% Q
import java.util.Arrays;
/ W% N( l  ~+ y: z- I: Upublic class Solution {
       
        private static void bubbleSort(int[] nums) {
                // 循环次数
5 G2 h* g9 u6 p8 P! L8 ?; _5 w                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
; J6 Q5 `+ q5 f. W; z( v& [                        for (int j = 0; j < nums.length - 1 - i; j++) {
( `( Y# ^! E# F                                if (nums[j] > nums[j + 1]) {
                                        swap(nums, j, j + 1);
! Y, l9 F. x, J9 X+ R* ~                                }
                        }
' P8 {6 w  l, Y# ]                }
( T/ s, }9 J4 ]1 }4 {0 v* z* h        }
/ B& d( c! x4 h0 F, C5 }
# d3 Q9 b; }7 |$ o& u" l! L
        private static void swap(int[] nums, int j, int i) {
* w2 }0 ]; I) s2 t6 k" |                int temp = nums[j];
( J$ p- G$ A# b2 v                nums[j] = nums;
                nums= temp;
        }

9 U. d  b! K  \( [
& @6 c, k% p6 d+ v1 k% G        public static void main(String[] args) {
# X  o0 ?0 s$ p( s! Z                int[] nums = { 6, 3, 8, 2, 9, 1 };
' K* J9 b# N; X/ A                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
        }
3 [" Q1 p+ @$ Z2 S+ d}
1
2
3
( |. O+ H5 ~* [* p7 v; Y7 t1 L4
" A: N  T' \! f4 `  q5
, k# A2 S0 L7 X6 _& Z  D- |6
( ^2 ^+ T# p9 Z3 h! V2 l. e- s7
8
9
1 g( z3 B9 C' L. V10
; x% k& U2 O4 O) V9 W- u11
12
3 A) q* v& |4 Z; w7 b2 k. p9 \13
14
7 f: i; A* D) J15
7 n2 M: ~+ u. m- ]4 \/ O( f  I16
  i5 t  R9 z% D, W6 Q4 K17
# M3 c6 P3 K# q! l18
19
1 j4 p  U/ m4 \( D20
# _, |2 f: w+ _4 {' Y. B3 O21
7 H+ U( }0 M+ z22
23
2 v$ ~, |4 \  d* x- _24
) `; U1 t. m0 L/ N! o9 l25
26
! Y' Q( x: [5 m" u& M7 B27
3 m6 t, o' J3 b; B6 A快速排序
0 X; x5 ~9 M  G# L5 N  H' n& \时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

$ U. ^8 Z. H5 D. R
代码实现


public class Solution {
4 N9 |! {1 {+ G+ y# i4 r. {       
        // Median-of-Three Partitioning
$ o1 x, Q  R& x( W- n1 e! E* C        public static int selectPivot(int[] array, int left, int right) {
4 h( B" v; X7 r: H1 e- `1 u1 |                int middle = (left + right) / 2;
2 U# U1 K2 O/ {8 a6 s3 y               
                if (array[middle] > array[right])
* ~: Z0 W1 A2 ^# c6 S0 Y$ [                        swap(array, middle, left);
                if (array[left] > array[right])
                        swap(array, left, right);
                if (array[middle] > array[left])
8 }+ N) A6 R7 V* `/ f1 G+ b                        swap(array, left, middle);
               
4 e+ x" [/ e- H, T4 `                return array[left];
4 w+ G8 w6 T/ b8 h0 Y% e        }
       
        public static void sort(int[] array, int left, int right) {
. [% k2 C- B, |3 t                if (left >= right)
                        return;
5 B! e2 F9 Z+ G2 p                int index = partition(array, left, right);
/ H& ?2 x, K# I' X                sort(array, left, index - 1);
                sort(array, index + 1, right);
4 ?# c7 c  k. m0 T" p    }
       
" z1 B3 H0 \  d! T+ f        public static int partition(int[] array, int left, int right){
0 v8 I: a# s) ]9 w* {& v' n        int pivot = selectPivot(array, left, right);
        while(left < right){
            while(left < right && array[right] >= pivot){
                right--;
7 p' y! V# ]% B            }
1 `, ~5 _! ?0 {4 B$ n! V: B+ {            if (left < right) {
                array[left++] = array[right];
8 ]1 H1 f' f0 i            }
( y4 Z* P) G6 b8 K# H7 p            while(left < right && array[left] < pivot){
                left++;
3 ]0 _0 [5 v& f  p4 M            }
            if (left < right) {
                array[right--] = array[left];
            }
        }
) i4 U6 l) s/ w0 i* p            array[right] = pivot;
        return right;
    }

; x" w' J1 m+ G7 F6 o# A- N( h
8 A$ r6 O2 f' {1 z/ x( s    public static void swap(int[] array, int left, int right){
& X* b$ M- L2 x% @            int value = array[left];
            array[left] = array[right];
1 @* P6 U+ y% k: x+ {4 F  l# D; X0 Z" p            array[right] = value;
  |3 o) L. B8 O9 K, c, v: R' v    }


7 e  Y/ b0 G- M) S$ w% @7 p        public static void main(String[] args) {
5 U5 R2 Z. E* N& G+ C6 P) d                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
. p$ Q' u) ^. G5 s! R7 q5 T. q                // System.out.println(Arrays.toString(array));
- ?% x0 y2 z1 K3 h8 [% l$ z$ E% o                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
        }
: ]/ ]6 Z( B  G* r+ Z}
: t) y( I: G+ ]. Z- {1
2
3
4
5
6
7
8
9
10
7 i7 x/ x3 A# d9 m8 Q11
6 ~9 Q! a) ]8 W& j4 Z! d! x" ?12
; u' r7 ?: s! K! S13
9 k! R; J5 P+ M3 x) h7 y) W14
15
. r8 D' q4 @6 E2 B. U7 Y$ b* I8 D5 e& ?16
17
18
/ Z; J; w: X; L2 ], M19
- J2 D# ]" i* N2 s& M20
+ z5 n0 f2 r) v8 q21
& T: Y/ Y4 r$ J; }) s. F22
23
24
1 F# k' E5 C# e- g+ M25
! w" I4 |* [" I8 \4 y6 [26
- j# F* G1 ]' Y9 Q. |, G2 g27
+ {5 B, J4 C) h& `$ q2 l% W28
29
# h! J" M3 t# |% j30
8 \1 @. v' r1 E8 r31
1 z$ g+ t' H2 `: k  _/ k32
+ g# d, F; |" B" y33
# m/ h  G3 ]3 U) \34
! J; ~, ?5 M: Y9 z4 g- q35
3 Z8 V6 ?# g2 X0 j4 \36
37
38
$ J, ]8 z# X5 M- o- e39
& {: o9 ^( K- H/ L) F# g/ m40
: s- n9 U9 _' L- L" K4 D41
42
4 ?) S9 R4 n; r! s- Q+ |; e  p43
44
45
46
: M8 ^+ \6 I# g7 u47
4 `# P  Q! Q2 C48
49
50
51
52
* x4 x, i9 ?: O' Q/ L3 M3 z5 N( u53
3 f4 @% E9 N! |3 o54
6 m, n: v$ C; m$ _55
56
57
归并排序
将长序列从中间分成两个子序列。
对这两个子序列依次继续执行重复分裂，直至不能再分。
/ @6 Q" W( s/ z/ l9 z7 N% E" l递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

2 ^( C6 U, G; s/ A0 G; {! V2 ~- _
' ~* y, _" q) [0 ]* b代码实现**


. i+ K$ |4 |- x% m' C1 |9 e, ^0 Upublic class Solution {
; e$ F8 Z9 S! M) B6 a1 y' C        public static void main(String[] args) {
9 V7 q6 M" r9 ~4 }                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
. Y* u- V' Z% F8 a$ l. x) ?8 w                int[] arr = MergeSort(array);
! |" B; W! c3 [7 A$ z+ R( Y. S; D                System.out.println(Arrays.toString(arr));
- U+ s9 U% }) G  [) R6 h' Q, G4 J6 L        }
/ a/ F1 T8 l! ^8 V
! {' j" D% B$ [$ C* C' X% r# Z+ i
3 T. Q% j+ M1 \: @9 j! }& s        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
  |! _! u$ K# L6 z% x                        return array;
                int middle = array.length / 2;
$ o& @" u) I% H  V! r                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
* X5 V2 w" E; q6 x& a, e                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
/ b+ W& p$ b" m2 L3 u( R                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }
, G# o  }3 X" _- {4 Z1 c' T, T3 Q. X3 n& L

        private static int[] merge(int[] leftArray, int[] rightArray) {
                int[] result = new int[leftArray.length + rightArray.length];
: [- \  t- H* u$ N                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
/ t* p/ M$ i8 S- @                        if (i >= leftArray.length) {
5 H" D, j! Y3 W4 c1 o3 E' Y                                result[index] = rightArray[j++];
  Z5 d- u: N/ h$ Y                        } else if (j >= rightArray.length) {
$ H# _' O& W  K! h                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
: @) g1 L) m* B1 g  p2 D                                result[index] = rightArray[j++];
- r3 ?; B; b8 |( M' v9 b+ w                        } else {
: M0 U4 e- b$ n8 f0 S/ W. H/ B                                result[index] = leftArray[i++];
                        }
                }
                return result;
        }
2 }* k' h$ b% m$ H5 f+ L' l# U}
6 ^& V* g. d! C& `" M- R) S
7 i0 m3 }4 M! ?% L
' i1 Q$ d3 U8 Z) |; ]1
2
3
4
. G6 b. n6 o8 C5
# Z" x! H! N$ A8 H/ N: X4 r+ c2 M6
7
8
9
  s# _" Q% j. d' B  E+ @! S4 N10
11
) A/ P# Q6 S9 S. f* l12
: @+ c; ]+ X- a. f3 c13
1 |/ O. Z7 S4 c% g2 E, n14
15
9 X. ]" ~, C, ]8 y  j3 E( s$ q16
17
4 P. `# k4 `( t1 p. u+ A; k  E18
19
20
21
" a* ?% M1 I. q" R2 g* ~22
23
24
25
26
27
28
& i- s1 t  a6 w29
/ l2 K; p5 ~4 N  z$ G! L$ O' z/ T8 O6 a30
. z, Z  N' O9 [/ x0 k, H0 ]; ~31
: y: H; z; O# {$ H( i32
33
% q* A% L; x* Q0 n) M& D* n基数排序
9 n- J% x/ y; A找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
9 ^- M* x3 B) s4 A: f" j将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
2 j- @1 [6 [4 @6 K; A时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。

* E7 x6 ~! ?* i. y( ~
, ^! Z; |6 O7 e/ G代码实现**


public class RadixSort {

. v; S1 N% V) G4 [
        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);
0 e6 y* {: Z; F2 \8 e8 k0 p& A                System.out.println(Arrays.toString(arr));
5 R5 v6 ?) {# M/ J7 K        }
4 |% h. E2 Z) p' _

        private static int[] radixSort(int[] array) {
; ?# d- u) r/ u+ ?                if (array == null || array.length < 2) {
                        return array;
                }
                // 根据最大值找到最大位数
" h0 ]$ [2 a7 D: ^4 j: Q                int max = 0;
                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
                }
               
8 Q7 U, y& Q1 Y7 n, K; K% Q7 t                int maxDigit = 0;
2 a: i: q6 Q' q0 J( @8 H5 h# L1 Q: c                while (max != 0) {
                        max /= 10;
                        maxDigit++;
                }
               
                // 第一维: 0~9
9 |9 M8 [- |( C; X- P2 H                int[][] radix = new int[10][array.length];
: P& j( f# E  n# D' l/ F                // 该位为 i 的元素个数
                int[] count = new int[10];
' O4 }/ F* W5 @9 t2 X% D               
                int m = 1;
+ K5 I+ o2 u$ W0 a: U2 E( T5 P& L4 `6 |                int n = 1;
6 V2 y0 b! u7 D' N               
                while (m <= maxDigit) {
' d; ]3 ^; i% K0 y' u% k                        for (int i = 0; i < array.length; i++) {
                                int lsd = (array / n) % 10;
: A" y" S( L/ M) D' x. Q; C                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
* }# a6 T) ]$ f( Z/ {- l5 a4 t% S                        }
) |' E" n; h* e& A' t                        for (int i = 0, k = 0; i < 10; i++) {
+ _0 }' z' v  \' G                                if (count != 0) {
9 a. Q# {. F6 ~# z; S1 N                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
                                        }
# q. `" M/ M- ?$ c                                }
7 i  t/ k1 t4 t0 I9 [2 |% H                                count = 0;
: o/ @! n: i5 j, Q* M! v" R, f2 v                        }
$ G6 e3 i8 m  |9 D# j                        n *= 10;
                        m++;
                }
                return array;
! R4 }6 g3 N! j3 [2 h        }


}
1
2
3
/ U" v+ C/ X9 O! v4
& W" F. c, b0 @5
6 ]: x4 n$ f4 U) w" \: @- |' k6
! u& u9 v& j$ x( A+ A9 }8 S7 {7
: t9 F1 ^) s. \7 s8
" f& u$ U7 c- G  |5 }# |9
' h: n$ c- ~1 q* R5 k) A10
11
7 l/ K/ i9 f! F8 ^12
13
8 H! r8 }+ p2 I14
15
16
# B+ F/ F9 q2 U3 ?. d; Q17
9 J/ d8 x( u* h18
; w' O! `# n5 N& t7 p4 e* Y- D) [19
20
, R4 y  t. E* ?5 p21
! L! m7 i' Y, [+ d* U22
2 |. x1 M! g  N0 t23
24
( H, J9 w. i) d0 l0 X0 @* a25
26
, k  F# m7 J  Q* f, Y27
% x1 ~/ t' M- L28
; c. P2 K% \0 A8 t) n: C1 [+ K. @1 z29
30
& {/ g" c2 N$ M; `9 C: x31
32
33
34
4 ~0 p2 K# A9 j4 s35
" k5 W: R! f7 p: u# l" s" d36
37
38
0 Q+ l5 P" |4 ^39
40
& u% o* |! V+ `0 z& D/ W* F# i41
& G6 ?+ P( R, x. |0 K+ @) {7 P42
43
7 w2 |! b; g4 `6 I3 A44
5 ~) b! a) ^$ K6 s4 B( H45
+ V" ]) J, g7 f4 t% d46
5 V5 ]! x1 d: C  v+ x47
48
49
$ a$ i6 F2 p' w5 g8 k( j# D  o50
51
52
53
; w% l, q% b+ Y$ ^9 a7 d! \& z计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
  Y6 [/ e) a; F! B4 m' s最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
' h2 [0 h. n+ P/ I2 |8 F

9 M1 _) E" i0 }代码实现


& C, z) |  o# g- a' ?1 L0 T6 Jpublic class Solution {

; `$ [; A. [( g
        public static void main(String[] args) {
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
                int[] arr = countSort(array);
# R2 b; T  X, P9 c2 P, ^: O                System.out.println(Arrays.toString(arr));
        }

+ g# u3 F" z; P% B
2 p8 V3 [0 G# H$ m. @: y: ?5 R        private static int[] countSort(int[] array) {
/ w) d* E2 Z+ S2 w                if (array.length == 0)
                        return array;
               
                int min = array[0], max = array[0];
               
  Z4 |2 O1 p$ g) `' K% U                for (int i = 0; i < array.length; i++) {
" a* `7 b3 x- y4 q/ T$ N4 J                        if (min > array) {
  r4 l+ F5 p5 v3 e. e/ `                                min = array;
" W( @8 ]; U1 p                        }
1 C4 l( J! L1 w, u8 P                        if (max < array) {
                                max = array;
                        }
, l1 d6 z. Q9 P/ E5 X, t; d                }
7 C9 j# ?# p# L/ p+ \# U5 b! W/ J               
                int[] count = new int[max - min + 1];
0 _* u6 V/ j9 g5 C               
                for (int i = 0; i < array.length; i++) {
                        count[array - min]++;
                }
               
                int i = 0;
                int index = 0;
7 {1 X& f8 I0 O9 j7 O5 R- N                while (index < array.length) {
                        if (count != 0) {
                                array[index] = i + min;
                                count--;
0 Q5 Y; O- d2 C7 A2 F- J+ a, Y                                index++;
, b# V3 P0 K& w                        } else {
3 a; ^5 c1 \6 x  U( I3 q. [9 |  A                                i++;
                        }
                }
                return array;
5 t/ d: ~7 X% k4 \* V& f        }
% l2 e& r8 l) Y4 |       
( z# }7 X3 b1 k% J2 z}
1
' ^! q  a6 H# ~( }: H" x2 s0 q% ]! S2
' {: ^! j1 t; E8 w1 ?; \, C6 b3
4
) F8 }8 ^0 H% B. y; I& g5
' D# M& Y1 M0 Z, i* s6
. Y. V) C) @% J9 v7
9 a9 Y, X# R3 w1 p- H- @' N8
9
  e9 ^# d: u& u6 I4 Q4 j10
' g" u/ z3 r5 s3 P, M2 H& Q11
12
13
14
5 G4 k4 I* l/ a15
16
17
18
19
$ w! D4 n5 ?$ B0 D% F( F20
21
2 [, p  _/ r0 J* S1 {& R& H% o  @& B22
23
24
25
8 Z% [" N6 f5 D3 t' k, q26
. H& ]4 }( x9 Q* Z- K8 \* }27
! ~1 y/ a6 Z; K3 K1 P- U28
29
- Z* B  e: U7 ]8 L8 W" i+ {30
  {& l. I3 }3 @" q) l31
3 X5 n- O3 o9 i# S2 b3 _6 ^0 @32
33
34
35
36
37
8 l/ u9 M6 L8 w0 x& t: g$ Q3 Q: i+ S38
39
  ~" I* r" G. f8 ~! b/ i0 q40
41
7 z; y' b4 f, z3 i" f% Z42
43
44
8 F3 I+ o- z0 k' H3 Q+ [( t桶排序
" i: t7 t: q# r4 z# U3 S5 j! z————————————————
4 v9 C9 ^" E+ A' M  \9 F版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153


: R5 Y8 a; D  p( J$ W( C