十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）
) M; l% [6 j% P
十大排序算法（Java实现）
: a5 K5 _5 T/ x' a: o排序算法框架
$ [- X5 i0 T/ o$ z& }& A* M' ~排序算法性质
插入排序
+ a0 n' e3 a9 |! F直接插入排序
* v2 r" G% ?3 b8 r+ O希尔排序
选择排序
简单选择排序
堆排序
/ l/ i* T  Z* o交换排序
$ g! e/ U7 e, |/ @; t! N; `  z( g冒泡排序
4 b5 E) F- F6 S) l' ~( \- r快速排序
归并排序
基数排序
5 t! Q. R* e% l- U1 l计数排序
桶排序
更多文章点击 >> 这里
0 Y, b2 B" o1 N1 c2 F
0 L$ [' P* s6 [$ E" H2 C+ u
排序算法框架
4 w; v# \0 \  u, ^/ F  p

2 _' q8 ^" ~% g+ `

# F6 p) U0 y% {" _2 s5 z$ w9 h6 Q排序算法性质

) z# I2 V, X/ o9 m: m+ q* {9 A
) i9 B3 k  O  o
: H$ p! b8 f5 g' f! A4 W
插入排序
: ]# X' R$ b6 k; a. i# }直接插入排序
& o3 A4 v7 z7 N8 c- y; b从第一个元素开始，认为该元素是已排序的。
7 L4 v' P5 r/ G  z取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
5 e# d) @% S; j3 A. G- z" o遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2
  P8 W5 h& P" N- E ) 。
$ P; S, y  ]; y5 x( H: o

% K5 U1 ~& F) u8 a2 V, U代码实现
1 q# G9 L/ _& v  Z  N" i  t# T
, U( S: y* P9 H) {. b" ~0 G
public class Solution {
        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));
# w; I) \" \5 F3 P1 ~  ~        }


6 S$ u5 B  ~/ M* ^* x' h% g        private static void insertSort(int[] array) {
4 A5 ?4 @8 \) F                for (int i = 0; i < array.length - 1; i++) {
1 ^9 t" l- |" s, f. u8 K                        int data = array[i + 1];
# u3 B: I' I4 ?; D/ z2 p                        int index = i;
( c) j9 k+ ~- S) S7 U                        while(index >= 0 && array[index] > data) {
                                array[index + 1] = array[index];
                                index--;
                        }
                        array[index + 1] = data;
( [7 p) p: r, {( b. m8 [/ R                }
        }
5 C( F: C( t" G9 b5 v8 f0 S}
1
5 Y& j6 g- r7 \2
3
7 [% Q: i( F" _! Q& @* z) F4
5
6
8 _2 y4 h( m8 V# u" Y7
$ t' p: s9 ]! N8
8 f; Y( n( ?" r  |7 J, [7 D7 L9
( S' n  w, B, z: j- {4 ^10
4 z& `# T3 B6 z( `* r11
' b+ h7 H6 E% l' S4 P1 |12
13
5 Z) Z9 u+ j6 h2 D14
15
0 @# m& E0 _! M; b, M9 C16
8 O; w7 B! R$ v* Z5 }1 T17
18
& k* k& M; D& e- }& }/ }19
! h' l. q1 J; P# S希尔排序
4 X9 B- ]0 P3 b6 h, b2 V
7 I2 ?! j' W/ p) J( H- ~$ _7 _
2 Z: E8 }$ {; E& i0 \时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现
7 G* s1 ^5 G9 A8 Y* F* f, M3 g

% }5 F; F1 \! A3 epublic class Solution {
. r( t7 J3 O# e        public static void main(String[] args) {
8 ]: u7 P( m) b/ B0 e4 z                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                shellSort(array);
9 n* P* \" a7 z2 }" B/ c                System.out.println(Arrays.toString(array));
        }


        private static void shellSort(int[] array) {
                int gap = array.length / 2;
% x9 Q4 T5 k- b+ j                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
4 x8 d, i" v8 x: r9 M6 }0 g# R                                int index = i - gap;
                                int temp = array;
                                while (index >= 0 && array[index] > temp) {
* {1 u6 M& }' U1 C! W1 W) r                                        swap(array, index, index + gap);
4 H$ x. [- k& }* G) w                                        index -= gap;
/ \2 D; V2 e; W" l# Q; N                                }
//                                array[index + gap] = temp;
) @/ v+ `9 J* a3 @) X* a                        }
                        gap /= 2;
3 k- C% G) V, a# u: a                        System.out.println(Arrays.toString(array));
3 x9 @  _# a4 w/ }& W! c* b0 Q5 \                }
        }
$ N9 ~" A7 T* Y  X4 {' G  O

        private static void swap(int[] array, int i, int index) {
% E: ~( V# E. }: C5 L: |$ @                int temp = array;
                array = array[index];
3 b  ~' \& H% A                array[index] = temp;
        }
( V3 |5 g' O! I  S0 [1 ]2 n& j( b) l}
1
% |0 m& E$ l) C, T& z! j' ~2
: Y. [) Q6 i1 _- I+ V% n' W3
4
% V" J  V/ A: Z- o3 L8 W5
6
7
8
9
10
% p% ]) U) ]) n$ ^5 U2 }/ f+ u9 a, ?11
) S) M  B- s$ P+ Z5 w12
13
% a6 m; p4 U  m; h14
15
16
. J4 g8 I' o8 @* I( Y, H' d17
5 N0 Q+ W2 Y4 s' D18
19
8 R5 V( \* ~, o6 W# c% s' M$ J7 i20
4 x/ T) P5 t& U21
0 ~1 w0 j" b" m. w3 [: p22
, X  D) u4 d9 G7 {23
24
5 J$ W; C; {3 |0 u8 W! B25
2 y- p  `5 r: q3 @- r26
27
1 m, P  }" H! b+ ^4 R5 g28
% i, ]3 Z2 F1 [+ N* R" A( @) N. ~1 M* h29
30
' |$ H+ n/ u( ~7 A9 U选择排序
, _! W! c. z" U$ |5 m: p7 Y简单选择排序
1 |) ~  `; x1 b) O  _从未排序的初始数组中寻找最小元素放置首位。
1 \& e+ j2 V$ B从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
. d  Z' E0 u4 H3 g$ ^8 s1 @时间复杂度为 O ( n 2 ) O(n^2)O(n
6 T; \# g9 ?( Y8 u2
) 。

4 t, v9 ]4 |$ F2 i1 r; J
% m& h$ ^# g8 [' F代码实现**

9 G* e3 O8 K8 i3 A( f
3 q, S+ A7 `* L7 Y; o$ ]% y% T: y/ R  G8 Ypublic class Solution {
2 d1 H. j. s4 Z. ], d0 N! K* }        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
$ X* }) ~, \2 ~7 |                selectionSort(array);
5 p: Z0 ]6 ^. V                System.out.println(Arrays.toString(array));
        }

3 h# r; D6 D( o7 d6 f4 W  G+ q
1 B; _& o2 F7 c  J1 @) }& T# P        private static void selectionSort(int[] array) {
" D' d% t7 Y* S1 ?8 t. f( [                for (int i = 0; i < array.length; i++) {
                        int index = i;
. X% c9 M0 j0 a- k& C                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
7 i# J- J5 [; x* R- r" _                                        index = j;
2 C5 [" T# g# j, I) ^                                }
                        }
$ h' [+ ?( ~3 a- B/ S% N                        swap(array, index, i);
                }
        }


        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
2 g5 p; d( {* W7 I: m                array[index] = array;
                array = temp;
        }
}
1
2
4 J" W* y9 B1 v% l3
4
5
6
7
8
9
! T2 P0 e; S! g0 d' P; n$ [$ a10
11
$ d# O8 H$ ]7 p; N$ w/ [9 A* {: M12
13
+ n2 q, n2 L1 @# \: L( k14
15
16
) K+ J$ V! x: y17
& O$ S" t. X# e2 Y5 i18
$ ?% i: t5 s' A& @8 e! ?, C& [19
20
21
' k7 c* o1 {/ V" X" M22
23
# V( ^8 @$ m% ?3 y24
# j" L& ~1 U; `0 l$ y) u4 F  |25
' @$ r; E$ Y' S! w- I; d堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

0 l& R" t7 W$ n2 M7 Z
1 r# u! g9 [/ b5 S3 `代码实现**
. n: L% Y+ k: k" W/ x4 ^
, l7 `6 k+ I! @  S/ ]6 g
public class Solution {
        // 建堆
        public static void creatHeap(int[] arr, int n) {
* i% y' M8 Y* g. I+ U) c# }8 _                // 因为数组是从0开始的
# Q+ }6 x& s9 m, J4 q, y, I                for (int i = (n - 1) / 2; i >= 0; i--) {
                        percolateDown(arr, i, n);
                }
1 T; [. j0 \  t8 y7 f! T" ^/ B* r        }
        // 插入
6 i2 j+ b/ q+ L/ w, ?3 G- F        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
                percolatrUp(array, n);
$ M. p2 b, }6 J9 l% x( _0 ~        }
        // 删除栈顶元素
9 ]5 U7 d6 y  K0 j        private static void deleteHeap(int[] arr, int n) {
; \/ b9 u# n( O% k( f: |                arr[0] = arr[n];
                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
        }
        // 上浮
        private static void percolatrUp(int[] array, int n) {
; ]" u2 l/ `) f% A. B0 J  P2 D3 e' \                int data = array[n];
- b  d5 e% u  H, D                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
+ U) ?5 [% O) D" g# N; u8 B* W                        array[n] = array[father];
/ V. {* A0 G- B  F  x                        array[father] = data;
' E; h" s+ i* t  L                        n = father;
                        father = (n - 1) / 2;
                }
                array[father] = data;
' d, v% b* f! E" T$ x) t3 B        }
        // 下滤
* i" v/ n1 a0 t        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
: m5 m$ e% N! ]7 C. q' I( G                int child = 2 * i + 1;
                // 遍历整个该根结点的子树
; o: _7 D- h* v1 I$ g                while (child <= n) {
                        // 定位左右结点小的那一个
, G0 W8 U6 V5 y  ?5 A                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
/ W7 ]0 j/ |7 ]% I6 z! ?* c! k                                child += 1;
                        }
6 c1 ?6 X2 I* l# j. ]. W                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
6 i8 J, q3 n1 ?3 M7 ]- H                                break;
- E+ P  D/ ?  `6 e- ]* _' Z, z                        }
                        // 互换根结点和子结点
6 M$ k, d) u- \' F& P! E                        arr = arr[child];
+ x$ L: U) b# c0 j( V  o                        arr[child] = father;
$ c" Q3 I" {4 \                        // 重新定位根结点和子结点
0 u% F" R0 c  l  O& k( m8 Y                        i = child;
                        child = i * 2 + 1;
7 ?5 _: n9 r- Z2 a) U- j1 l& I                }
        }
   
" o& Q. L0 ~- ^        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
$ f# ?2 h1 Z0 l/ }; ~# q                creatHeap(array, array.length - 1);
3 p- `8 S- `& X$ n2 G                System.out.println(Arrays.toString(array));
               
: q2 m0 y8 E3 g/ ~6 e0 }                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
5 k7 J, x1 T5 }0 }# g# ]               
# s$ E3 U1 ]  ~. [                deleteHeap(array, array.length - 2);
# `4 `! Y: N: y0 J5 f) ^                System.out.println(Arrays.toString(array));
" h! D: F- W  j6 D8 K" B               
                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
# ~, U: _, y  }* h7 j. D7 T- L7 G9 J        }
) Y* q  z: s1 r* y9 u}
( a2 X7 o$ F' T6 `* ~4 }* O1
2
3
  y) i+ a5 N; i1 b- M0 `- [4
2 y8 N7 A' `# J" b7 F) I/ a5
, ?3 F" z) L  r+ i$ c0 W6
7
5 R6 E5 H& m. F. w8
9
2 ?) c# v8 a' B7 }/ Q( X. ~6 I10
! ], o* j. V: c0 Z3 w: e11
12
13
$ O7 W" U' f9 u5 s& y14
& o/ I1 h. a8 F- {; l6 W3 l15
/ W8 M4 h& U' {9 v2 |1 z& I2 R16
17
7 F# P$ Y0 U$ n) d- X" h% Y18
& @7 R: c  B8 R/ T19
20
21
22
+ ~0 u9 C0 `- I4 Q7 f5 a23
1 P- N; \( b- e3 C. U24
1 P* d, K2 O  J& Q4 [8 I/ t25
( j* `1 v$ L9 b5 R4 C5 x1 K, u26
' A" S7 J2 A6 Z0 F; q# `27
28
29
5 b( ~' z$ C. s1 T& f$ @30
31
32
- b$ K+ E7 i" v" ^5 \( `! U# A33
! a, m. m! A! ~& a/ l: J, z0 k34
35
! l- Z7 @" e9 H1 b/ s, Y1 h36
, l& ~4 t; j( D( b7 i9 j37
# K: o% ]- C" W; K, M' t& `9 \4 @38
. p# }+ u4 ~; h* S: s" O' W39
# a* m: Y3 ^. }1 Q+ |40
' N+ O$ \  a( v' _41
. X. ?6 n5 A+ @& Q8 B9 r2 Y/ O, Q$ C4 J42
( P/ x; I+ ?: ?0 K43
44
" q' g4 v9 k$ ^: ^8 U' Z45
, m3 ]9 u8 e7 T; f2 E46
47
5 v. Y! M6 t( S; ~$ R( I8 {  c' F- j48
49
/ Z% ~1 }1 Y) k; O3 A: q, r. x50
2 P0 q% L4 M/ M2 i5 @4 h7 U/ d# k51
52
53
54
55
$ i0 [. _7 t8 z/ n: f: a- Y" z  |0 |56
8 s  e! {# A& i6 |* i57
58
& v4 [6 d9 [' q  J2 a8 Y- r59
. r) e5 L1 X& ?) R60
61
62
63
64
) e! Y, d1 F( J' ?" e: H- S* g65
66
0 s' O1 K* n3 |67
68
% t, b5 g8 x' _: m. t0 j6 R1 n/ X2 m% L69
70
6 U  B0 `) x, z$ J3 K" L& F交换排序
冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
, }1 }" x' L( @+ s遍历数组，直至结束。
) ?2 ]; H4 v, ^" o* i4 A' l% e最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
) s) ?1 J  t: ~; r2
) 。

: [( q* ~! O; L9 }
代码实现

+ z1 E6 C8 J& T3 F  ?: b! R
import java.util.Arrays;
! ?( x9 Y2 M! v6 d" }public class Solution {
       
/ u' U* b# V$ b% i3 \3 H        private static void bubbleSort(int[] nums) {
                // 循环次数
- F! T" |2 D& ~                for (int i = 0; i < nums.length - 1; i++) {
3 P" e7 a( D3 z. y6 b  z9 |1 A  o# X- g                        // 比较次数
7 n$ D, n5 S% Y                        for (int j = 0; j < nums.length - 1 - i; j++) {
                                if (nums[j] > nums[j + 1]) {
' \1 o  W% _+ Q$ Y+ L" B0 F- N                                        swap(nums, j, j + 1);
                                }
: X6 E8 t8 R  N4 w% x. ]: |3 V                        }
0 Z* S9 u+ R. v4 h                }
        }
$ |8 {2 }5 [2 c1 k: j4 [

        private static void swap(int[] nums, int j, int i) {
# Z: N4 t. c; x8 ]2 Z' z) ^                int temp = nums[j];
& U+ T* i. u' w/ q- c' i                nums[j] = nums;
                nums= temp;
        }

) A" `  \& o/ m( l
3 o! D- X, m. [, o! m1 v        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
        }
}
4 C! J, U2 @  S6 @3 h! K4 Y" R. H; y1
2
0 E5 t: r0 m: H" O% t7 D3
4
5
6
1 V! ]5 ?' s, n* L/ y7
8
5 z* {% d* S7 O$ U% j% W9
9 l, L! |; s. q  a5 o10
& x5 v* I0 v% C- O11
% M: {1 r- O* b( O. f) `: c* r12
3 v4 {2 u( F1 {3 z$ d  {2 u+ C13
14
$ H$ t. j1 E  m" k15
2 v8 I3 ~& A( Q( Z1 ^2 q! h/ S% o16
. T/ G9 O% x( F5 j# E, @17
18
19
20
21
22
23
24
25
0 h' Z; M# r4 D9 O3 d" m1 K26
27
快速排序
; ]% @. C% Q( u' s时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
& i, @! M3 N3 S& I/ c
( o! x1 Q2 ~! Q( l0 o2 r9 f
代码实现
( A# ], `1 p+ V1 Z9 L2 ~/ ?
# L! i+ S# ~9 o+ Q
2 k3 p  L+ M( `  m! @; _public class Solution {
       
        // Median-of-Three Partitioning
6 Q, v$ f3 W8 Q) `" b        public static int selectPivot(int[] array, int left, int right) {
# e. m7 l7 \& [+ f                int middle = (left + right) / 2;
               
                if (array[middle] > array[right])
                        swap(array, middle, left);
                if (array[left] > array[right])
: ]  k5 i! X" S- h! |2 J+ ^                        swap(array, left, right);
                if (array[middle] > array[left])
4 l; a3 o$ }8 p, W' R2 Y8 I5 B5 l  W                        swap(array, left, middle);
4 E4 f8 }6 r& T! y* d% e. x$ G               
& f+ o' E! {3 f. v/ U3 U5 h1 V0 h4 Y                return array[left];
        }
! K, h+ W4 L3 R/ r5 n       
7 o& \# z' ]/ m1 s7 @& p  i        public static void sort(int[] array, int left, int right) {
                if (left >= right)
! ~$ R! a$ K0 |  V                        return;
; {8 ?- u0 H4 L$ l0 z                int index = partition(array, left, right);
( O5 T, D8 }: ?+ d. [! h% [0 R                sort(array, left, index - 1);
2 {* ?0 g( }5 [                sort(array, index + 1, right);
6 x- J' ~$ }+ m) [; t7 B    }
       
# i. r) i6 L+ _; m. S) Q" N! ]# y# e        public static int partition(int[] array, int left, int right){
        int pivot = selectPivot(array, left, right);
        while(left < right){
' k7 q9 G/ `/ }( u" o$ I  E            while(left < right && array[right] >= pivot){
6 x+ C# m' {. R: n) Z                right--;
            }
            if (left < right) {
                array[left++] = array[right];
            }
& R' V7 o1 V# ]+ _3 [& y! R            while(left < right && array[left] < pivot){
! \5 P% O6 t# `                left++;
6 y' b  \/ k. Q, G" d( G            }
            if (left < right) {
# R. s( V! i3 u+ h                array[right--] = array[left];
            }
        }
& X7 x/ ~0 ~1 b            array[right] = pivot;
8 Y% L3 V1 j: W' D        return right;
    }
' H( j1 w! b& x/ Y0 v
4 L5 o5 Q. j( s- u9 v! ^8 e
    public static void swap(int[] array, int left, int right){
            int value = array[left];
+ z. t! D* K6 J7 O2 y7 y. [            array[left] = array[right];
            array[right] = value;
    }


* x/ }& l; }3 y+ x8 m8 x6 L) _        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
6 |3 ]5 C+ z7 Q$ {, v4 j3 Z# p7 o                // System.out.println(Arrays.toString(array));
+ J* x1 @' X( N& O, z  R                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
: j, s% H5 F+ Q9 [+ s        }
% i/ q, x; y0 s$ ~3 T3 e3 a}
1
2
8 H1 {* c( L" v3
4
# [+ q4 j, m/ b$ c5 e- k5
6
  a" z2 u  u0 Q7
: s2 g( N+ C7 p1 M8
9
" a- a  l/ O& y10
$ n8 _8 }/ r6 ^11
$ ]. |$ A4 _( P9 U12
13
) b, n( J5 @# W: o% _' D' U1 F14
15
16
; B: \( {# Q- A17
! o1 C  X( o4 {' a18
' o; |$ b& Y4 C0 G; X1 x2 a2 S- _19
; j6 w0 X+ ]7 G0 Y/ H# P20
21
22
23
3 M# R7 t- ^. A1 d$ n7 y5 S  H24
) c8 h" E# ~: N25
26
% c% [! h! l* Y27
28
29
# I0 Z- M) R8 s% @1 `9 K8 ?' O# T30
31
32
33
: A) d5 ?6 P3 d  v+ h2 y8 _34
  @5 i4 O& h  ?; S35
36
9 V2 r0 i) }5 `* s37
38
39
+ e. m& @1 {; t/ e8 v7 p0 v9 D40
41
4 {( [. c0 p) s# r) W2 w1 [- i42
! K9 {7 t7 j- N0 k7 U$ i* s1 i43
- k, O1 |' e4 w' r$ ?% W44
45
6 ?& I9 L# O4 {- u46
47
48
4 q6 |& `7 a6 O2 R# I0 Z49
* r0 v9 x7 B5 k50
51
52
# K. V; [/ y- t" K$ D53
54
55
" j7 K' S" i) T$ x, u' V56
57
归并排序
将长序列从中间分成两个子序列。
9 t' S# I+ D: R  Q- h5 }对这两个子序列依次继续执行重复分裂，直至不能再分。
" b) J* j( D6 x$ U递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
3 r6 O4 }/ V$ t" Z' X! u  O' B. ~

代码实现**


public class Solution {
        public static void main(String[] args) {
: j; g) e0 I* S# n                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                int[] arr = MergeSort(array);
2 Z7 K. y7 f( ~- k                System.out.println(Arrays.toString(arr));
7 D2 C0 C5 \1 L$ X( J' y        }
" ?4 D( R! Q8 O7 V$ v

        private static int[] MergeSort(int[] array) {
$ ^  w/ q; L8 {6 t& K                if (array.length < 2)
                        return array;
                int middle = array.length / 2;
                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
8 C+ F( y# {- C% R                return merge(MergeSort(leftArray), MergeSort(rightArray));
- Q' ~1 \) G+ Y' u        }

' ?8 @2 G2 i" W1 T+ A' `. n1 k1 `
        private static int[] merge(int[] leftArray, int[] rightArray) {
                int[] result = new int[leftArray.length + rightArray.length];
                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
, m& l" e* q- K2 A& q( s  N                        if (i >= leftArray.length) {
                                result[index] = rightArray[j++];
% \9 C# N$ [/ b5 A- H( L! j                        } else if (j >= rightArray.length) {
1 D! q% S3 l  q0 D1 p                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
5 v' @4 M3 |! F+ d: Q                        } else {
                                result[index] = leftArray[i++];
6 S2 u1 H- S+ D% `; g. M0 s3 p, Z                        }
                }
) C+ X6 q1 O7 n8 e                return result;
        }
}


1
2
# _9 Z& i: k& q) R! E3
" x: q& ^- |7 F; b" j& h+ x4
5
9 ]% H3 ^% B4 z& x6
7
$ R, R5 v6 X! @; {* g8
4 K7 W8 Z' p# j7 _0 _1 u9
10
! ^7 M; T) U0 g& _& U* p$ v  z11
12
13
14
15
16
17
18
19
& ?6 Y: d; g3 I20
21
22
23
! o( p! l, G  \- u. d6 `  k24
25
+ x5 H9 n* n6 O$ _8 h26
27
28
+ [" t* V/ d  R9 o0 x5 @( B* n4 h6 _29
30
31
: V8 Y; l" j2 P: ~32
3 X3 |: C- V3 [- N- [1 N33
基数排序
找到数组中最大的数，确定最多一共有几位数。
- N  a1 C+ c0 x& H. P& E+ y% {按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。


代码实现**
1 B6 \- S* m/ ]+ J& f# h# `. o
* B8 V6 [* K+ W" s
# v9 y2 i7 V9 h- a. lpublic class RadixSort {
- s  t& O' m" x; ]" N2 ?& ]- V
1 |, s5 u7 I6 y
        public static void main(String[] args) {
% \( n4 C& c* }8 [1 X& J! T1 I9 p; |                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
3 G, W2 l3 a! }: h6 O                int[] arr = radixSort(array);
                System.out.println(Arrays.toString(arr));
5 t, o# c! n5 b! O" b7 _6 {9 _        }

. R; s1 |. \  }5 N
9 z2 Y( D" l: }1 [0 @, f! ]: ]        private static int[] radixSort(int[] array) {
, l$ \% N7 C1 N6 a                if (array == null || array.length < 2) {
1 J! k* Z% F5 g2 {& `                        return array;
1 [3 p4 M2 k' `' [% u6 _/ |$ O                }
' w1 B+ g+ y1 q/ |! i                // 根据最大值找到最大位数
8 ~! u$ J9 n* W* v  ~                int max = 0;
                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
                }
  y% ]0 i: Y- B7 Y) i8 Q" e, e7 m# T               
4 j/ A. t/ [, K7 U# d                int maxDigit = 0;
+ s/ a1 a6 X  Y                while (max != 0) {
& C* k' Z: z" d" J4 y: Z+ x* z                        max /= 10;
                        maxDigit++;
                }
, l% ?  s- A: Y, K; @               
) M2 G- w  M, z3 y* S. A* s/ V                // 第一维: 0~9
) j8 I4 P7 s: ]6 z) v' N/ l8 V                int[][] radix = new int[10][array.length];
! q6 V' N0 g2 W8 n0 m* }. ^/ c! t3 T; o                // 该位为 i 的元素个数
                int[] count = new int[10];
' h: k. \& u5 y; J               
                int m = 1;
3 H9 n: ~1 K5 G                int n = 1;
9 s" l: x$ N/ F( m' O6 Z7 p               
                while (m <= maxDigit) {
* V& U1 F. [  |1 a3 \                        for (int i = 0; i < array.length; i++) {
8 Q& n* N+ U- \6 o9 c7 f% @                                int lsd = (array / n) % 10;
                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
                        }
                        for (int i = 0, k = 0; i < 10; i++) {
3 x4 K; p$ d. g7 G* `! U' z                                if (count != 0) {
! ?: F) D9 e- {                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
                                        }
                                }
! Y4 Z. H3 L7 z, _7 s, E3 E" `7 C                                count = 0;
' \2 V( H4 ~: I9 i- b                        }
9 ]2 i" a* Y  q" H: v$ K                        n *= 10;
                        m++;
                }
                return array;
        }

+ A( z1 b# E" D( N5 |8 O) B
}
1
2
$ t# `, c1 k$ o: g3
4
! G* Z$ X3 e) W. }, z% B+ M5
6
7
0 T& U; q' z5 V- Q# M5 i3 e: `+ m; U8
9
10
11
0 S' M( M' i$ l2 X) ]# T12
; [$ J! I5 Q( G) A13
14
/ H* |( n7 V' |- ^8 k+ f) }15
0 t) q8 v' Q; |& ~16
$ V- A. W; _1 }2 `1 v4 R5 w$ k17
& C/ w- a' U9 _1 F* I$ T8 v  G18
$ d) o' k& O* Z9 h! {" ~4 O! d19
( l' ]+ K1 A' U# ~8 J  }20
7 N( K' W1 m' P21
22
23
24
25
$ X- F; V* `& F; d& a# X  F26
  k7 k$ K3 X5 g& ?27
28
5 _+ ]6 T4 w" }, K8 }" @# F29
/ S; \1 C8 a2 Z30
31
32
; Y0 M+ k% p: ^6 A33
9 m' t, I, r1 m# e$ b& a34
35
# S  M1 Y; h% h$ @  k4 R3 ?- H; x! D36
( X) m: z, G; o7 e9 r% Q37
38
) V, P, f% H+ T; H7 V39
# B0 b& e) y1 T2 h) V/ R40
. X( Y% Y1 d4 _8 r41
42
1 e$ `' u3 p6 H' r- U) E' x# M43
2 H" E- n5 `% }# z& m44
45
46
47
48
$ D& g! u4 _0 f  J  s6 D0 e49
50
51
52
- ]5 V: v2 k3 g& B' D- u53
计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
! ~/ g" W; t) _3 l最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
1 e; A) ^. R% e) A- d时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
. \6 r8 b0 @  S% q* X, e& n

9 k: u5 Y- H4 \/ r; I代码实现


+ l: Q: W5 E7 K0 L4 M" K- R" G9 ^" Wpublic class Solution {


        public static void main(String[] args) {
( ^" N. n+ }! U8 G1 }+ [                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
                int[] arr = countSort(array);
! b! m& V7 k- i3 D                System.out.println(Arrays.toString(arr));
        }
5 h7 Z) d: L$ s( }

        private static int[] countSort(int[] array) {
8 P1 l& ~+ p# T% O+ q3 b+ T                if (array.length == 0)
* |- i) w% C, @$ q7 `                        return array;
               
                int min = array[0], max = array[0];
1 s% `- g) u& B5 }$ W               
# ?% j  _6 B5 z+ `9 Q                for (int i = 0; i < array.length; i++) {
" |. V5 z$ [  _                        if (min > array) {
7 B  y. L' t) U/ A5 ]( w                                min = array;
8 a1 F5 i& d7 E: Y! Z3 J0 c                        }
                        if (max < array) {
                                max = array;
! f* a5 u! q" a5 [6 u) k                        }
% ]& [1 ^* \2 @( x# Y/ E                }
2 y# ^6 x4 C% O5 P' q8 c               
                int[] count = new int[max - min + 1];
               
                for (int i = 0; i < array.length; i++) {
0 _8 D2 b! F& L6 t9 L/ K8 ~* g3 L( U/ I0 B                        count[array - min]++;
9 t1 p1 E+ ^) t4 f9 l                }
& J4 C' ^2 d' R               
6 V( T1 ], Q0 q9 W' r5 e3 T! c5 S6 C                int i = 0;
! U* d( w( c0 B7 m                int index = 0;
( i5 S+ A' f# t# q( k# L# L                while (index < array.length) {
                        if (count != 0) {
7 E% Y& Q( |9 z                                array[index] = i + min;
( q! S& w% {8 E  Y4 n* z: c, M4 m                                count--;
                                index++;
9 m$ m" H# R8 T5 H( m2 }8 C                        } else {
                                i++;
) P/ A9 N+ d; K3 Z                        }
                }
( O/ Z2 C$ c" o: S- |                return array;
1 d; I5 y" ~6 d$ w% U6 }  p        }
       
- ~! P! p% |6 p0 Y}
. {7 y6 j6 p3 X. z; j2 a6 }1
2
& @: Y. j0 l, {* ~; k3
4
5
) r: w( x9 r9 K0 x: V% ~2 K5 {6
7
8
9
10
11
3 C8 O9 l& z# J* V. x12
13
% W" E3 Z6 s, K- D; u  x0 M+ N; ^14
15
16
17
18
' w7 G4 [+ _- I4 W19
- J- k- t' O3 x3 i20
21
22
23
) N; l: r9 O2 `( G; ?5 v24
25
26
27
28
29
3 g" @+ k# t/ @5 M! V1 p4 s30
31
+ h/ u/ u0 s2 j" j32
33
34
2 [7 {1 ?; L$ l) S+ W* ~35
36
37
* `5 w- N$ C( E' p  @/ N5 s( o9 ~38
7 D& N; K* T0 I& S( X39
40
41
42
% V- t7 H5 X0 r7 a  s# R$ a: R* f43
% I; C% h' L( [9 b# B) x7 [44
桶排序
# X3 F* h- G9 {  Z# R4 C9 ^7 b————————————————
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
: L' ^, T9 V* V7 }原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153

. z4 J8 I5 E) O8 x. |, F1 U9 j- r: R4 S