十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）

十大排序算法（Java实现）
排序算法框架
+ Q$ T) n0 c- F, A. S排序算法性质
插入排序
- D6 a+ q( E1 _! e7 {/ h直接插入排序
' i& s3 {  @  l- D希尔排序
8 V4 J/ h9 V/ c# s* e, _选择排序
3 R5 p- x2 T, g% A! R8 [, Y简单选择排序
堆排序
交换排序
冒泡排序
快速排序
7 R2 R" E4 W6 k8 N  j归并排序
基数排序
计数排序
桶排序
更多文章点击 >> 这里


排序算法框架



- y! ?3 h" S4 r2 N" K$ \  \
2 z- p) D3 p  s排序算法性质

' l! @  h. o/ }  R; b9 H- R
9 p7 o- b' w& @/ w% u5 L; i$ k
) q* K8 e3 V" I# C* O. g
3 V4 M' b8 {$ e& |" T) h. o6 S  B2 ~插入排序
5 q8 C2 s3 z1 ^- `* h5 }9 ?直接插入排序
从第一个元素开始，认为该元素是已排序的。
7 M7 F5 r$ t0 c5 D& I# v取出下一元素，与前面已经排好序的部分进行比较。
# {( G, e; c- p9 d1 ?5 |$ r3 n若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
. N% r8 k; ~( g& p$ Q遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
& i8 Y! I2 u2 ^( G2
7 v$ E5 G+ N2 N: Y ) 。
/ M5 Q& p, O3 ]3 ]1 w: P$ |
0 I3 N; c, F! X
- X% K4 L, q  C& @+ G代码实现
& U8 Z/ r( p9 u1 m
3 |" |0 Z+ X! t7 O- \& _9 |
public class Solution {
  d' o8 n4 l& k, X" v8 {& H- s7 I        public static void main(String[] args) {
; a, V6 G' a( F  A( Y                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                insertSort(array);
                System.out.println(Arrays.toString(array));
+ b- }4 X# `- H5 o% G        }

( v9 R, y/ c7 h0 f: ~
* o1 D0 u3 s% s& J        private static void insertSort(int[] array) {
4 Y4 N2 J: z' `! M: f! x" ~: k                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
                        int index = i;
                        while(index >= 0 && array[index] > data) {
1 o# b9 W" @+ m4 m- e  i- T                                array[index + 1] = array[index];
# d0 e, T) d1 j' X( n  k- D                                index--;
                        }
                        array[index + 1] = data;
                }
        }
8 c7 l" ]! y7 |. Y& L" O}
1
# _& G% X; {+ E: q; u" t, }6 c& E: {2
3
  r! i9 h3 D3 |) n4 g  g, u4
5
! x( {$ c; p  K, j6
7
; `+ {8 o* w+ w; v9 b! N+ W& f8
+ i4 \& R3 h" G0 _" @) o# P% Z$ T9
3 u' W. n3 b6 o4 l! c10
) c! k! n- T5 Z( m5 X# m11
6 R- L$ K" Q6 p' R- _6 t1 H" m12
& ]2 S9 s4 P" F4 I# _5 p) W/ D13
% j& J$ g; `* S( d- X& l14
15
16
1 Y. ]7 U7 s, G) m, W& g/ p- j17
18
19
希尔排序
  Q0 ~3 f+ a/ Y& _- C- K

5 K$ K, \* Q9 u" z! c  {; c时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

& D% x/ K  N* H0 o
& P  [$ Y% P1 B4 i代码实现
3 \+ g. p& M* {* ~' [, @

public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
2 t# ^4 V0 K% \8 I; z9 u                shellSort(array);
( b7 X8 z; A9 v                System.out.println(Arrays.toString(array));
        }
! J$ d  M7 v8 S0 ?5 t( u

        private static void shellSort(int[] array) {
  h& D  G: g! A/ I* J                int gap = array.length / 2;
                while (gap > 0) {
" x! V" W7 g8 L+ N2 k. n                        for (int i = gap; i < array.length; i++) {
; e8 B8 T1 o, F$ k/ `6 J                                int index = i - gap;
# V' q  N; |# {' u* N: q9 g+ ^8 V( P                                int temp = array;
( l5 _- s- H6 \# G; @                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
3 s4 Q. B: w) q# H3 P                                        index -= gap;
                                }
* O' h! v7 c; r* r( ^//                                array[index + gap] = temp;
                        }
& K9 J& _5 k  E                        gap /= 2;
. \2 F% ?/ ~: `* t! _                        System.out.println(Arrays.toString(array));
9 x0 }$ b  K9 f                }
        }
/ {" A* ?  w" M8 p0 h

        private static void swap(int[] array, int i, int index) {
                int temp = array;
+ I: s( N8 u! Q  Q8 e! G                array = array[index];
6 w/ r  E) F6 S                array[index] = temp;
        }
9 ^; ^  y1 p- a- c8 j8 K, R}
1
8 u" @$ u1 J; H: `; \2
  v! V4 a$ ?& N! K( Q& ^4 U2 t. \3
4
5
# a& n' r0 g2 ?4 ~; v  S6
7
5 z( P4 }% }. E8
9
2 _, @0 t2 L) ?10
11
12
: Q0 h2 `! y" o" q6 N13
. u! C0 q" G( y1 L! B  `$ ]% r14
. D* d2 m3 F4 G) u* v15
16
! C" ^6 S  t& S, ]! y17
18
, ~1 C1 i7 B% ?% y! Q# D19
3 E" v, X/ b2 H- `  d20
21
, Z/ D! ^1 u3 P( }22
4 g% j7 l- H9 ~$ ]' Y23
6 \% u9 S  S0 S/ i8 c: A. A24
25
26
' R' y2 U4 P# N& t/ B27
0 c" j; F  ~4 N5 }# m28
29
30
选择排序
9 Z. o! u) Q2 |  J* g, Q+ ?简单选择排序
# l- T4 W& J! S" ^从未排序的初始数组中寻找最小元素放置首位。
从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
+ I5 o; h1 S4 `' K& o( r1 L9 c2 r" S时间复杂度为 O ( n 2 ) O(n^2)O(n
3 v+ E, L0 _8 J6 U0 f2
) 。
% o7 @  j* i. m9 @5 d6 n5 |6 C  Y  \& N
' Y0 O' W, _  n( `- {3 _
& C! g7 b: _6 k5 s代码实现**


3 }: G* v% p& d4 P( L* @public class Solution {
        public static void main(String[] args) {
, X4 f, S: \7 j8 T; b& b                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
1 ?# B1 i& r: u) O8 J                System.out.println(Arrays.toString(array));
        }


  p& P: H, }% P4 W2 K% q" d        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
                        int index = i;
: J9 ?# b4 ]& x$ x) n. j1 w% i, `                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
! g$ G2 U: d0 L- E) `- P                                        index = j;
7 ]3 z1 j! {, Q# b3 ^6 g$ R                                }
                        }
. B$ p- ]" v" `( B4 x/ S                        swap(array, index, i);
8 l! `) e3 _' v4 Y! ?                }
1 n  Z- S8 j2 u/ H        }


        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
- e  l8 \5 j1 `* l6 n$ V& `. N                array[index] = array;
                array = temp;
0 Q) N8 m8 [: h- i        }
}
1
9 j9 }  W1 a" g2
! \9 N3 T- F  r3
4
5
  r. [+ H0 s6 Y/ P  b/ D6
7
, s) l" B8 _4 I. g- W, }- e. X( ]8
! |' N( D. X4 h, d# ]! X/ [- G9
6 t# \  U9 J" K* ]% W10
( l7 t$ x4 j* G$ m' r% d* M11
6 n" B2 X; z! S1 _  T* T2 N) R12
. }+ t1 p& p6 {: m13
$ r# z' }/ S0 c$ {4 P14
! s# V6 \* A4 u3 [15
. S( U7 o. G6 d16
+ f2 p# {4 S4 c; G1 i( z; c/ }17
: i5 L& j0 ^2 A  X18
: ]/ {8 q9 Z3 `  t. ^* L( i5 O19
8 ~3 p; @3 @, \, m* L% S20
- S$ X* j& T% i. f21
22
  d8 l. K/ X4 ]% p23
! w) g0 ^+ }2 N& S6 H; G# a. z24
25
7 z) f: K: [- W* N1 J4 g堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
4 |4 G* w6 {, q

9 F- w: L, {, `8 F, t代码实现**
; U# v0 d6 P9 f/ |* V- \! ?
. _3 c1 v3 W9 u+ T$ T" M: {
5 H1 s- y! I3 @' B. z$ Lpublic class Solution {
        // 建堆
/ n2 a% x8 A9 s        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
                for (int i = (n - 1) / 2; i >= 0; i--) {
                        percolateDown(arr, i, n);
                }
        }
        // 插入
        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
" V6 H7 [2 C7 Y7 i. B. P                percolatrUp(array, n);
6 e6 j& v+ f$ Q' u        }
) V5 Q1 A9 ^$ c" `2 D8 v        // 删除栈顶元素
. ?' D1 T7 M) D/ Q! j        private static void deleteHeap(int[] arr, int n) {
                arr[0] = arr[n];
                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
) E6 t' L6 F1 |* ^! d. N$ D* L2 Z; E7 J        }
        // 上浮
        private static void percolatrUp(int[] array, int n) {
0 q6 I$ Q& K7 Y* `) m9 ^                int data = array[n];
                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
' A0 ]3 W2 I, _' c. r                        array[n] = array[father];
                        array[father] = data;
- \; M" ]/ I+ m' j+ W9 Y                        n = father;
                        father = (n - 1) / 2;
) R+ Q, s7 L" E0 `                }
                array[father] = data;
. b" z1 {5 ~0 l3 C9 t        }
0 K" j1 N5 l5 B        // 下滤
4 u6 o0 f4 B' \        private static void percolateDown(int[] arr, int i, int n) {
8 c3 F# Q" f# G7 ~9 U, T6 c! J                int father = arr;
                int child = 2 * i + 1;
: x* P4 i; p' _                // 遍历整个该根结点的子树
- G0 a* P0 d6 g: t8 S                while (child <= n) {
$ i3 K0 d% D1 K; V$ G  o                        // 定位左右结点小的那一个
                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
, Z. ?$ {- |0 X, S1 a                                child += 1;
                        }
                        // 若根结点比子结点小，说明已经是个小堆
+ E+ W) Q0 Q- u                        if (father < arr[child]) {
                                break;
. E9 _! W' u% p% f  x7 V$ `                        }
                        // 互换根结点和子结点
                        arr = arr[child];
                        arr[child] = father;
" ~) b" P+ l( M3 o. Q# x# p                        // 重新定位根结点和子结点
                        i = child;
( i' a9 ?0 E& \; d. W# B                        child = i * 2 + 1;
                }
        }
( F- T4 H+ l, `6 `# ^# ]   
! G* g% P4 o5 c3 X4 `4 [        public static void main(String[] args) {
, r3 x" p" K6 l  [$ I                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
3 X. w* p/ [% t               
5 z9 A% b* z* j; q( \7 j# J                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
4 B5 }3 G0 F+ e5 i. r& G% U) R$ S: v               
                deleteHeap(array, array.length - 1);
- Y! L& o3 P. S" I                System.out.println(Arrays.toString(array));
' f! Q: U7 F, z7 Q0 X! {! r9 K$ T               
                deleteHeap(array, array.length - 2);
                System.out.println(Arrays.toString(array));
5 L& ^$ k7 w+ }+ Q5 }3 l9 I               
                insertHeap(array, 3, array.length - 2);
. h& `$ c/ p& H. E( g                System.out.println(Arrays.toString(array));
1 p' }: K$ \( j* C2 e        }
! I2 k/ H, f6 O! _. t}
1
! W& j0 s" r! D4 u3 O8 [7 F, I2
4 |: j0 v4 M. E) W/ T0 h3
4
5
2 _. {+ G/ n! T5 Z6
/ c# e3 M' Y; r# w: r. H& A8 D3 X5 N7
8
9
/ j/ j& f* A9 m, `+ o4 \7 @" h10
, M" s+ ^( z/ ?& \' g# l; a+ X- x11
12
9 V5 j! z. M8 E2 E6 \6 _13
/ ~' V( [( v( h7 D6 g/ a" U14
/ w3 C; `* r. \2 u15
16
% N. O8 u" ^, p6 g& _8 n4 W4 l" W17
5 ]: Z% m3 L, M' r" S/ G18
7 @1 T: W2 q3 i8 i0 Q# y19
$ T$ V- X- @6 y0 R  O1 K) r20
2 I" N" ]$ N" J+ ~3 `5 v6 i21
22
23
% U2 @0 Z" f4 ?2 S+ O- x, g* S24
25
: `: r' R$ w1 Q2 h. P7 }: F. N26
% [: Z# r* K. A/ n& z3 ?: R. u27
$ h$ j  D2 r9 n# h+ {( {# X- w28
) ]3 X) T5 ^: [: J2 l29
30
! z' i8 g* [  P31
. P: y4 p, ?& ]32
33
34
35
  P, I% o' P& [( ^7 K36
37
38
39
40
41
9 G1 }! i8 Q. H* ?42
2 l, u' f4 |% j43
9 y* t" M+ ?& k, ^44
1 c" b% l) }! _8 }* y5 Q45
2 D7 h2 b5 ?+ m46
% @- M& N) T! a& A/ P47
' S# X" s/ E( {) x48
49
50
51
1 V# l- R9 h4 {0 a* k52
& v+ h% u/ z- T/ I; N  |53
54
$ [! `1 S( E- V# d0 e! y! I55
  T- m$ g5 J, _. e56
5 j" q6 K1 p( `" ~8 f' S" z57
5 ?' Y* |8 B% Z2 n58
59
, v2 L1 \- x6 f4 @60
61
; w2 B& G( D" C. d) w62
63
1 B& \, n6 q5 U+ U5 W; H9 @64
* [' q& \: `3 i8 J9 q" H65
  ~. W, l; a2 g: D, h66
$ E; _1 u) O% S: N* N67
68
69
1 }) t+ y, i+ C70
交换排序
, }7 Z6 r; A) r/ g0 K* Z冒泡排序
$ J" y6 E! c- H3 t5 |& R依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
* ]5 o/ z6 M2 z3 ~6 w: l0 j遍历数组，直至结束。
# T: J1 J3 S! s$ q最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
8 p/ \+ E# `1 a9 x2
) 。

5 U( }0 ^( H2 B( p
代码实现
5 U7 D7 @6 W  t  v% Y
9 u, {3 q7 Y3 W8 B
1 E) R! N# [% Vimport java.util.Arrays;
# \0 J# R$ v0 C; k2 k' S$ Zpublic class Solution {
       
        private static void bubbleSort(int[] nums) {
8 U2 ~! y$ h4 F$ m) l. ^                // 循环次数
                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
9 \, S: L+ ~: z& l                                if (nums[j] > nums[j + 1]) {
                                        swap(nums, j, j + 1);
                                }
                        }
6 w( G$ h5 V7 L/ E5 Y& [                }
        }


        private static void swap(int[] nums, int j, int i) {
8 o  L. D, N: _/ Z                int temp = nums[j];
                nums[j] = nums;
                nums= temp;
        }

8 f  V5 T; Y9 v
7 R" e6 a8 }+ Z+ `6 T        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
- O4 P& A* \/ l6 h                bubbleSort(nums);
+ ^# Y/ t; Y6 i8 g8 w/ B                System.out.println(Arrays.toString(nums));
! x3 j3 t7 u" I; s2 Z8 L        }
2 Q& Q4 X( R5 C5 P+ D}
/ n0 x9 M" m1 \, H9 B* E- S1
; l3 ?& K; r/ g. V$ t" U8 a2
3
4
4 d! H2 {6 v- ^5
% K( A; U- Q% j$ B  d! I& A6
' {0 q( q5 T# r$ R& S6 L7
* P* d% ]! O8 u! j* m8 d8
3 `4 w/ z2 F" X- P9
# V2 I) p4 g6 s$ X# r. Z10
3 Q  y& e% U$ R7 I$ U4 M11
12
6 @+ s- M2 J& g4 m& X13
) i, b5 v! O) j9 j14
15
16
8 e4 s, Y( \% |; [: }17
18
: w% k' }5 @, g; k5 }1 V& E- K19
20
0 G$ C( J$ @  c21
22
( Y+ K6 h' {% P$ X4 e23
5 V: @* C" u, s7 N24
25
/ `& }" x( U, C# q' B! K+ ^% P26
+ G0 R5 b! a% I% V% j- h27
快速排序
% M+ K; H5 p/ r& n时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
! V5 s: h* {* \$ T+ u4 u7 r. @
% b7 L6 \3 s7 n0 w4 m: S3 d4 F
! U( W2 E6 E+ U, h4 \代码实现
& A. N9 O& z1 I
2 m, N9 f  {+ d( i+ v$ N$ C; {
public class Solution {
       
1 T- ^/ w' k" h" F. I8 }) Z        // Median-of-Three Partitioning
        public static int selectPivot(int[] array, int left, int right) {
' U1 G% E/ a* F+ E, k& g                int middle = (left + right) / 2;
- F* M% ~; {1 W8 S+ P               
                if (array[middle] > array[right])
                        swap(array, middle, left);
$ K- P0 C" Y" x; U                if (array[left] > array[right])
                        swap(array, left, right);
                if (array[middle] > array[left])
                        swap(array, left, middle);
               
                return array[left];
- h5 n) Q% g, L' t$ }7 I- i        }
       
8 L$ W* F# p4 k& {7 l        public static void sort(int[] array, int left, int right) {
                if (left >= right)
3 b2 C) l! I' e& E( D; Z                        return;
                int index = partition(array, left, right);
3 }& U% e" K* |9 n, i! w$ g                sort(array, left, index - 1);
- Y( h, Q  N1 M" O# n7 Q4 ^! @1 _                sort(array, index + 1, right);
    }
       
        public static int partition(int[] array, int left, int right){
. Y' f* r% U1 P& ^& x7 P; M        int pivot = selectPivot(array, left, right);
+ ]' |9 _7 T9 R% G1 w, c        while(left < right){
4 h% C1 W5 Y0 F3 K2 l            while(left < right && array[right] >= pivot){
                right--;
            }
, G; C3 }9 Y* O. E            if (left < right) {
                array[left++] = array[right];
" w( o  S) @9 v# M            }
4 c, ~/ y& A3 E$ R( X. J9 u            while(left < right && array[left] < pivot){
                left++;
7 V( A) P0 j6 P            }
* n+ F& S2 R9 o; m% r            if (left < right) {
                array[right--] = array[left];
4 J2 d6 k( L: J2 ]6 o. o            }
" ]9 i: G9 f5 m( M( U+ `, r3 ]7 Z: h        }
( C3 p0 T4 n+ D; e+ S5 Y            array[right] = pivot;
4 @. G2 l2 |* p: D) Q1 p* L2 N8 p' p+ x        return right;
" D8 e# u- \: y" q' }/ |    }


    public static void swap(int[] array, int left, int right){
4 y( A  j% E" g: U; O& {9 `  ~! p0 ^            int value = array[left];
  g5 ]8 z: C! N5 k            array[left] = array[right];
7 Y) W& H5 Y( x% v# i8 ]0 M* J            array[right] = value;
    }
7 c% \( k3 X' E. F

        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
# L$ s9 s) q- C' z                // System.out.println(Arrays.toString(array));
                sort(array, 0, array.length - 1);
# @" q1 ^/ Z+ z9 G, h                System.out.println(Arrays.toString(array));
        }
}
2 J' S/ Z% {/ q% p1
7 K, h3 `4 L$ s1 x! ~2
3 K) C$ e& Q9 y! U3
# _3 M# \$ @) z  t1 \" y4
+ p8 O# K3 _) ~5
6
7
$ x; e* J6 w9 F" F! J8
. d6 w: d* y1 U( z9
0 J- h& i9 ?0 Y5 W. M) D! K10
# Y' R1 }: ^% j11
: D  \6 q- D$ N: [12
8 r7 v; O) \* e! |13
5 @+ t: a; V* t- ]& l14
8 A) J# o9 \5 b* T- G: |/ M3 H15
16
17
18
19
20
21
, c$ r4 W( z' Z7 o6 S' V0 P22
23
2 H" ~0 d9 n1 ~. s, U4 c& F0 [24
3 N1 q6 E& E" S25
) W# U* O' X/ s+ w26
27
28
. M( h1 b+ s. P. l29
30
% [3 m/ q6 }; C31
32
33
34
35
! n% f0 Z. V0 @! v& \& ]( V& d" s4 k36
7 B) w" S' \, e7 F& g37
1 P2 t% t( T8 Q/ y5 }" J38
9 G# N5 R0 d; Y! h39
! F% r: p$ y6 W- m& G; c9 @+ v40
$ {. O% M0 s( q* Y. C0 g7 J41
/ N/ O3 }0 u! l42
9 x% N! X( m* ~, D43
44
) g! O6 b' m: Z) y% y0 {0 w45
46
- I* A6 V. @+ \3 W' P. Q& e: L47
48
49
50
5 b% |" A1 u3 F/ N& e51
* K! u7 \0 L' [9 k0 Q7 [52
53
- t2 x, [3 @' R54
55
56
* t: x1 o5 I: J( E! \57
归并排序
将长序列从中间分成两个子序列。
$ N1 j6 i, ^; ?+ k( F: \" `) H( u对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
9 j8 f, a# |0 }
4 `4 k$ S! W, ^  T3 \
代码实现**


public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
' s2 }6 m" x9 `7 X1 D                int[] arr = MergeSort(array);
                System.out.println(Arrays.toString(arr));
        }


        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
/ ~' O+ ~! K: X1 ]" _, ]: v                        return array;
                int middle = array.length / 2;
3 i: b3 `3 _$ e: X$ d                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
3 x6 r) _- W" Y; p+ S6 ?7 N                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }
8 Y# [% P! S/ M0 O

        private static int[] merge(int[] leftArray, int[] rightArray) {
4 @) P4 t8 Z- J: L" Z6 }' ~                int[] result = new int[leftArray.length + rightArray.length];
                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
                        if (i >= leftArray.length) {
                                result[index] = rightArray[j++];
                        } else if (j >= rightArray.length) {
: ^- f4 @; b1 l# z$ G, K6 Z  ], a                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
9 N# i/ @7 q% A5 z: [" N( @                        } else {
                                result[index] = leftArray[i++];
                        }
                }
4 ]5 F2 P1 m% }' W$ w, m                return result;
        }
}
( A: Q$ y, g" Y( }

' j9 l3 J1 A$ f. h/ U: f1
2
& I3 M# t4 N! ]: E1 a9 v3
4
6 E/ [+ Q: i8 }2 q6 S( \6 Y4 E, q; A; Q5
' D3 |: P5 j; H: h6
/ I7 z/ E, ]6 o. L! f7
9 d. M8 Y, Z. d. e2 `8
  \* p8 \# A. M/ j$ e% e8 T9
2 {# z2 N& G2 F% ^$ j10
$ q7 f  d& x& S; R11
12
13
$ t' \' d% h' _8 B0 \# E14
15
8 p  [' ~8 l2 Z+ G, V) z) S& K16
17
  F9 [: \& g/ H" Q9 G% J18
19
( H( F6 v* B4 k2 _- A20
5 ^) T5 B3 i7 H  V21
" p  f& i' G4 t' A- b22
' p4 B' W0 V1 [3 A6 n! J/ I- Y23
, Z8 K5 u4 u2 c9 T2 [4 Z, u, x24
0 Q5 W4 q* [( M% O25
26
27
28
29
. h/ i! ?& b' b; Y3 _" e30
; ~2 j% m  }- K31
0 S( v8 A$ ~! t32
, r3 @+ E- q4 G: q5 t7 a33
: J' h3 u2 M/ j, x基数排序
找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
7 |2 M4 k: c# a$ F将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
/ n, i7 p: o* M时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
7 `4 O, n% y9 A) m. w

3 g, t2 O: t9 j4 X- p代码实现**


public class RadixSort {
' o6 g' ^8 X! X7 z7 f* o) D* J. Q0 Y
- m9 m" J! A/ ^3 i0 v. _9 g
# K9 c9 I/ @; T, y        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);
8 o  u! |( V$ N                System.out.println(Arrays.toString(arr));
, C* M) `; d% j+ r6 A  F! e4 w- W% O        }
$ g3 K! ]" m" U2 j, \/ H( p9 f
4 u4 x/ m- `4 ^0 s+ A3 i! w
1 S# g( }6 H" o9 A5 p; w        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
5 B7 J- R; E1 h- K( e9 z  m7 l7 ]                        return array;
1 W3 A- s: w: _/ p/ @" s8 a' S                }
                // 根据最大值找到最大位数
' m. d2 K+ C3 m: o7 a                int max = 0;
) m4 i: ~/ d2 G& t; w                for (int i = 0; i < array.length; i++) {
1 V* e9 K7 X9 f. P                        max = Math.max(max, array);
                }
1 Q) m3 {  O# `* k$ r               
& Z' o$ _, d8 ]2 W. ^                int maxDigit = 0;
! [4 c7 M# t5 P/ }5 ]- X' K: S. F                while (max != 0) {
                        max /= 10;
                        maxDigit++;
                }
               
- f$ k6 O$ n* q( x                // 第一维: 0~9
( E7 d6 Q" Q: w6 o/ l1 l' @                int[][] radix = new int[10][array.length];
5 h: W1 g7 d9 u  s# ~                // 该位为 i 的元素个数
! W5 s2 {) Z2 T  |4 }                int[] count = new int[10];
/ a4 ^  ?& g! j4 X; @3 X1 L7 y6 s               
5 H; q: w" d% j' u2 \, W                int m = 1;
                int n = 1;
) j% }- L; S5 K9 U( ^               
                while (m <= maxDigit) {
* ?+ M0 D) Q; r: m& B/ I5 U                        for (int i = 0; i < array.length; i++) {
                                int lsd = (array / n) % 10;
8 j+ l+ n. U/ J' |. T( I: ^# R                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
1 r: \$ E- I9 X                        }
                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
: o; G1 k( [! w* l1 Q# H% n                                                array[k++] = radix[j];
                                        }
                                }
                                count = 0;
* u1 u: q; o6 T( g3 _6 t                        }
. ~& @- p5 b* G) H+ I: J( _; t                        n *= 10;
                        m++;
                }
                return array;
4 ^4 U7 c( J( S) S/ x5 r0 E        }
/ i( i7 ^- \8 Q

}
1
2
/ j% f0 j1 ^# v3
4
& R8 d6 A+ b7 I( w5 R5
6
7
! G( N( c& P7 f5 E8
( k# C/ q3 O7 S7 H: l# }9
10
11
12
13
14
15
16
17
  ?2 P  i0 b1 \1 D/ t18
19
0 a1 U! x) v* C20
21
' s7 v/ b- n4 ~6 [! k$ f22
1 c% m4 \$ _6 Y& U2 L; R! L23
24
8 g( ^' H  J! P, Q: F1 I25
' W) k( n  w' p8 N' q26
27
6 `' U; y3 M+ W/ c28
6 ^! `1 ?+ H; X- B- i4 J29
30
31
$ h; \* t& }- V6 E' v: r32
33
% }+ k. Z( G, y1 d34
35
36
37
38
39
0 U5 L: X$ m8 h( Q  M40
41
  S3 {1 b8 p% A4 x! l42
! A0 m& h" _  t43
' s1 f! Y8 q$ }9 x44
45
46
3 L) }7 s0 s1 B8 U+ Y" Y2 \0 T47
48
( E) m5 G$ t4 i+ O7 o/ j4 E+ Z' L49
50
51
52
; J; s" Y7 c5 s53
计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
) l& K7 w# w5 W0 p时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
) Z0 d, e) u0 m5 D4 V7 \+ d+ X- W

代码实现

+ C2 I. s: Q: Q" d( Y! J+ \* h1 J- g8 h7 P
public class Solution {
! U7 w; _+ n8 j# E
* `, j- V2 F  q* E! _; P
        public static void main(String[] args) {
4 }. e$ y2 m( V, @2 Z" b                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
3 e8 e( h- M1 }/ e# R# w, I% R1 F        }
4 H6 G: F7 c! k( T/ |

        private static int[] countSort(int[] array) {
                if (array.length == 0)
                        return array;
" n4 W$ e6 t. H$ |4 v9 e/ L               
                int min = array[0], max = array[0];
               
                for (int i = 0; i < array.length; i++) {
0 \/ ~) R+ Q  Y2 `8 ~; {9 K                        if (min > array) {
                                min = array;
                        }
4 d0 p+ O8 K4 I5 @# ?0 b; r                        if (max < array) {
                                max = array;
                        }
                }
               
                int[] count = new int[max - min + 1];
               
                for (int i = 0; i < array.length; i++) {
                        count[array - min]++;
% Q% O! K& _3 e                }
               
                int i = 0;
                int index = 0;
2 o& b, m+ I0 m3 ]$ t" X; v                while (index < array.length) {
9 |; i! H& ^0 D( t                        if (count != 0) {
2 e4 {; A, v& e- E8 p% Z  o* S, Q                                array[index] = i + min;
8 z6 R3 `3 e/ x7 e$ t. [* Z                                count--;
                                index++;
8 n' L2 H. s' F! N. u3 B                        } else {
% K5 j* a* J9 e4 y# o2 Q# h4 a4 N                                i++;
4 @0 A8 c2 q  S, c" W# [2 S                        }
                }
9 R  F& _, @/ m) s: b& G                return array;
4 N9 }+ J8 ?, ?        }
/ p2 j- ]% v: {; |0 r% d% K       
}
1
  i" z6 ~0 _/ `% f2
3
4
5
- R3 w; E, j/ P% b/ P( ~: F9 J( I6
7
8
9
9 ^- S4 O3 k4 H0 z5 [3 T/ q8 U10
11
. ]5 g- ~& A. D  g& \; O6 K: O" q12
13
14
15
# B, x" Z4 s9 Q16
17
18
2 T; ^* B- `# B5 q19
4 I0 R1 r- l( C) c$ Q$ @20
21
# o2 A( d$ l/ U22
23
24
2 s! T8 e6 m( J( U  y- `25
26
. h1 K& Q3 x+ t9 v/ ~5 [* o27
6 u: }  o+ J. k9 P  y. X1 N( {28
29
) X8 ]' g0 D. E% M' X, E* M& r30
31
32
33
34
) E/ b8 P! c6 D( }35
36
0 J4 c/ G) x: n1 C0 h) a37
, M; ]$ [3 w% o9 L38
39
40
41
42
. y  j% W/ u  u3 z# x2 i2 B6 ?43
44
& U4 ]3 N0 Z6 ]8 L) o: D桶排序
" e. F' e$ \3 c————————————————
  ?" O3 }& c/ Z& D  [/ R$ N$ U* M版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153

( h) e1 t: I3 D3 @3 l