十大排序算法（Java实现）

杨利霞

& |- |7 o3 f! w; l9 J十大排序算法（Java实现）

十大排序算法（Java实现）
6 i6 t$ J- \- m; B5 Y排序算法框架
6 ~" {% q6 W9 f* R" t5 D4 l排序算法性质
0 I  L0 b. J0 [3 B  q3 y插入排序
1 w3 t' z, a  X5 N; t直接插入排序
希尔排序
0 W1 V% ]  O' C: Q+ e; }. R' J选择排序
2 S6 F+ T7 p+ o! Q7 Z简单选择排序
, X  ~8 y3 a8 o- q; s+ N& v3 B9 f堆排序
交换排序
: I+ T0 ?8 F. ]  ?: M: l冒泡排序
5 U, F* j5 K0 B; \+ s快速排序
归并排序
4 w3 G8 U; m! ^% g基数排序
计数排序
' P3 t; ^  D. j1 M. F桶排序
更多文章点击 >> 这里
1 Y: N9 a: X9 }5 h# Z9 Y. S

5 B% q9 z7 v9 D4 ~- B) E1 K% u排序算法框架
' `7 I; J6 J+ ~) W- C: V1 g
$ F, p9 h* ]% r6 v4 w
  D7 F: h" \) N. `& b! O# L

( W1 L/ Y8 h) J3 y+ {3 K* S1 m排序算法性质
1 r0 z  N1 J' @  S3 u% R  T
0 i$ R6 F* O; L2 U5 ]$ d
6 {  W: V6 E. n+ |, U. V

7 c; h! [( N' Y4 j2 C插入排序
# c3 {- \; P' Z直接插入排序
6 H, n* o" ?( n4 e" Y5 z/ A# {( [从第一个元素开始，认为该元素是已排序的。
6 l7 [. c- I% _& `取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
$ Z$ }! Y' |9 V! d! K3 S遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2
) 。
$ f& v: }$ \% y. s( i8 _" S- ~
  t9 |" c. f- E% U+ C
代码实现
, K9 c6 C: y7 Y- C2 ~
# z9 f2 |) T5 a. Y( b, `" s+ u
( Y: B" z1 L9 k; ^public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
7 c: t- f8 P+ W. V- \& u8 {7 w                insertSort(array);
5 `$ v3 D1 G5 y' ~" P- q                System.out.println(Arrays.toString(array));
- n6 V3 ^, z8 o+ x* I1 u( H# `        }

4 U9 X+ O- i3 [1 J% i
        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
                        int index = i;
* `: S' I& @9 @  O                        while(index >= 0 && array[index] > data) {
                                array[index + 1] = array[index];
                                index--;
                        }
                        array[index + 1] = data;
3 \' r/ x1 c: p) Z                }
        }
' ~" s9 D  E# p. G9 q  ~0 q9 j# |* p- D}
1
# h+ P1 y& Q& ?8 H! _; C2
' J$ [% T+ h4 A0 }# c: C. s4 |3
; a, N; h" O+ M8 P0 G' o) ~4
5
6
7
8
9
* X9 Z0 U* K& a$ }10
11
12
13
14
6 h& i7 Y# w- \6 a5 d" M15
" x' ^: F- S1 G( N' j' Z16
17
18
19
" C) z1 R8 V- u# F希尔排序
9 F+ {% g, b# t9 w  L" N3 g) w

时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
9 V5 n1 ]& ?0 t; X( m

代码实现

# k! M+ R' P1 {/ U8 r
' w5 U0 z1 X1 cpublic class Solution {
+ u6 T0 g3 j4 `% y2 q; E8 l; n        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                shellSort(array);
1 M1 L0 T& C. h+ E  t2 N6 x                System.out.println(Arrays.toString(array));
( t6 n( {4 G: P! N        }
/ D+ K' D& K# ?. c
3 i4 P+ m8 j) s& i) h
6 x+ @2 C9 x( e8 c2 B  T3 k1 |7 N        private static void shellSort(int[] array) {
" A! U8 C& r7 X0 F' R; u                int gap = array.length / 2;
                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
  F/ |* R1 F5 A& P* O                                int index = i - gap;
                                int temp = array;
7 h9 a0 e: b  ~; X' s+ ]                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
                                        index -= gap;
4 k+ C8 G* q" f# K4 c                                }
( p8 F2 K$ G/ b) G" F6 x4 b1 ~# i//                                array[index + gap] = temp;
                        }
                        gap /= 2;
                        System.out.println(Arrays.toString(array));
                }
% i, |7 D7 v6 S        }

# V" B0 l/ o! J8 `+ F' y
        private static void swap(int[] array, int i, int index) {
8 m- ~& R0 y1 E6 l6 ?4 j$ `3 _/ S; l5 U                int temp = array;
                array = array[index];
/ ?' K0 z7 E" }. X2 h                array[index] = temp;
        }
; d3 S  q. t3 K2 b/ ]& a}
, o' T* b" i' V5 _1
2
3
4
- T* ?" j# w, h# ?( s7 ]5
6
- ^* g5 _% |+ a- j1 [6 [: ]7
8
9
3 G3 T; }' k, T$ R2 b( D% b/ C# ^10
11
12
# F3 [+ x$ Q+ S% N' y13
% A8 p' |6 M9 M5 ^9 R14
15
- @) X( k- H; D16
17
18
19
( A$ o& G* A& x% Y: `* t$ {20
2 N; T. k8 p# T' b5 e) M* g21
  K# K5 A3 b4 I+ c( V6 k- f. h7 N22
- I4 ]3 ^- |& J4 ]* ], ^7 h23
- q) Z/ i2 F" h0 H8 T0 T  w+ l, p24
25
" t) [- V2 e8 F: y& ^0 I, R26
7 A& w/ v" ~! h: X$ Z27
6 k  S) Y. R1 v; L28
/ Y' S$ {1 L! o# z; D# p1 ?+ P29
30
$ _% u7 p/ i4 K选择排序
9 h" R8 z) Z+ _1 Z" j7 o简单选择排序
( Z- Z. f, l2 e; m5 b% u6 Z从未排序的初始数组中寻找最小元素放置首位。
从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
& o0 _) j$ l- t3 y! {时间复杂度为 O ( n 2 ) O(n^2)O(n
2 S9 J, n8 C/ P2
7 C/ T( M) q/ |8 f( v ) 。
5 n/ {/ {1 A+ q
! o  }1 P* K9 G( Y% b3 n7 @0 X
代码实现**

  \: A& O8 p/ L. n# ^; B/ S* c; `
public class Solution {
% S( O( ^! Y* V/ L        public static void main(String[] args) {
/ N( s! R5 U5 j9 h1 I8 w                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
) L: }1 a- O! m                selectionSort(array);
                System.out.println(Arrays.toString(array));
        }
: q6 w) |" }6 U& y5 g
$ U* \- V- Z' B% N
        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
& L  Q: ?' g9 D! a+ t( o                        int index = i;
# _0 }0 B) p$ |                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
                                        index = j;
5 F7 A: G2 i3 S' v, `* h, y- K                                }
                        }
                        swap(array, index, i);
                }
        }


        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
                array[index] = array;
& B- p% t$ o% b$ v( F, [                array = temp;
" J2 O* b2 s4 n7 G/ @2 k( F  v7 j        }
}
1
2
# }( ^% }! V, `4 I3
2 O; Y+ y' G" t% [  W. M) d- y% {$ k4
5
% G. O+ ?3 `" P7 G6
" U0 [* B/ A3 y" k5 J7
8
' e* @/ d+ D! [# A9
5 C9 E0 n# Q+ ]3 |4 u10
4 v% R" h) I9 J6 d3 _11
. M; d- ]0 S1 i( O7 D# u' O; R7 X12
) j% a, t" w  Q* ]( J) D13
7 B: P9 P5 U' F2 ^1 b14
; j( F; p, _" z, m15
16
( f' }$ q. |* `+ X17
6 A9 t( `( Z# D! n0 B! K/ n18
: P6 h  {7 f9 O/ b5 A. H/ s& U' F! T& W1 F19
; ?5 m, T) L: K- F, x0 n2 s) s20
$ x4 T# e" N' I6 q( G21
' w+ w9 O! u: i( T4 m4 j2 H3 V22
23
24
25
堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现**

1 D' C3 `: H/ N" x5 m
0 P0 m- V( H& apublic class Solution {
        // 建堆
        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
; G1 N8 ]+ q; H! n                for (int i = (n - 1) / 2; i >= 0; i--) {
. a: j* U$ [( o1 I$ U" ^                        percolateDown(arr, i, n);
, E9 C) `- V# }                }
5 ?; ~! b+ X: g2 Y8 [$ Q4 |        }
. H3 b  F- ~3 C! T3 H        // 插入
' G7 f. |8 K8 R+ M        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
                percolatrUp(array, n);
        }
        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
# {' Z% g* I5 G' t: b( D" F                arr[0] = arr[n];
                arr[n] = -1;
& B* h8 }# d5 b' I6 C5 j4 x                percolateDown(arr, 0, n - 1);
* q1 \) S7 y5 N0 O8 l2 h  L        }
* l- ?6 H: K4 N8 h0 T; p& N, j        // 上浮
        private static void percolatrUp(int[] array, int n) {
/ y, f) p) i% b                int data = array[n];
                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
* ]3 u5 \  ?2 P" M                        array[father] = data;
5 ~! d1 J) G) u# ^5 F' i                        n = father;
                        father = (n - 1) / 2;
                }
6 C. Z3 b' P  o5 ]* Z                array[father] = data;
        }
        // 下滤
% H" J6 Y0 m3 f2 A9 O        private static void percolateDown(int[] arr, int i, int n) {
3 p1 A4 H! I) ?                int father = arr;
                int child = 2 * i + 1;
3 {: [; p6 w7 s. p                // 遍历整个该根结点的子树
/ J7 }. M$ m( F+ [" A9 H                while (child <= n) {
                        // 定位左右结点小的那一个
" k5 J7 ]$ v2 s! z                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
2 N! y8 ?" ?9 |# K& Y                                child += 1;
+ ?) U! P' L* ?5 d) E: H- m6 Z                        }
6 z- l2 ~7 e( _$ ~4 @& ?! A5 X                        // 若根结点比子结点小，说明已经是个小堆
. H/ w- n2 \/ u" L                        if (father < arr[child]) {
                                break;
                        }
                        // 互换根结点和子结点
9 g( \, V* q1 u  V& x& Y, Z( }                        arr = arr[child];
  n) ^+ ?9 P! o4 u                        arr[child] = father;
6 Q; ~7 f7 n1 w6 y1 \9 X                        // 重新定位根结点和子结点
& s# m# s* n8 ^' d/ Q6 B* b                        i = child;
                        child = i * 2 + 1;
                }
        }
4 U! `. e/ q2 `1 C   
        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
: x; A# Q7 t1 `$ }4 |( I8 j! e4 c. A               
# P2 r. _  h0 x7 Q/ I9 V6 R9 ?( ~                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 1);
. h2 j* {5 V1 g                System.out.println(Arrays.toString(array));
5 O# m$ E3 b6 L# p  E               
                deleteHeap(array, array.length - 2);
6 D0 o- z4 B$ q$ T                System.out.println(Arrays.toString(array));
) O/ g% {, H) `8 N3 r; v# ^+ Q! t- z               
                insertHeap(array, 3, array.length - 2);
; {+ m, g6 X4 \( u1 }7 B                System.out.println(Arrays.toString(array));
        }
}
1
: Q* y1 ~0 B; T5 b/ h- j/ I2
3
/ Z$ I! f: x3 q; J/ C3 n2 f2 }4
) f' d) O$ X, C5
6
7
" G% g4 [6 N! ~. T$ I/ P8
* ?5 a& P0 I/ B/ X* a9
10
11
4 |0 v4 J4 |1 ^9 D$ Z/ K" J$ g" S; O2 g: b12
& A4 P; m( Q  q/ X; I2 g13
3 r' |' `5 ]8 y& l$ ~8 \2 m14
* {) N* B. f% k" Q$ A; F/ D6 e15
16
17
( l7 f: ~" H) s5 g! o18
, F1 c# }2 P/ X, m1 F" W19
20
21
7 Z! V# R. z% a0 f. _! k2 ~22
$ x( g) S% \% A3 W+ [' N& x$ g. y2 V% q23
& k7 K# d: _/ l24
25
( @" I( w# _+ Q) y; [1 Z3 i9 Q26
27
28
# B  Z. ?  l, l+ E' v5 x; \29
30
* y9 O/ ?& F; P31
32
33
34
  A6 F( G, V: [/ \35
& N6 O: D4 s; Y2 C# {& u; s36
. d+ o$ v+ \7 Q  p. D- u8 @! ]37
38
3 j! G  D0 F5 O$ O39
40
41
. B$ x8 `- Q' A7 U, k6 g7 A42
% A( M( G9 O! W7 j+ m. v9 q43
44
# O6 i! v$ S# M- W( h# y45
) b2 p/ R" ~$ Y, l2 F$ x46
. Q( y/ `. f. ]5 S1 u2 x9 V$ a/ J$ Q47
0 L' ~7 h; D" B: X3 j48
49
50
9 U/ G% l8 G4 @& ?; a51
52
53
54
55
; C& O8 `$ V4 k" _' w# z( b56
& |& H. b4 g2 {9 T57
9 W$ X9 X) k, t2 \+ h5 }58
59
60
61
62
63
64
2 g3 T+ C. Z' B65
1 M2 |& O, f. n- n- k$ V66
( Z' m) D0 b" ?8 ^, L/ y/ j67
4 Q( d# l" x6 x; B- p; b68
69
0 }% Q" F8 {1 P2 O; C) I8 P/ F7 f2 P70
. r) u! l9 j' X$ E  x# @交换排序
6 N: ^- y+ j; c3 m: z, e* M冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
1 m' Y" [) Q- C. s) s3 Y3 i4 W在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
$ c. I* |0 t$ a, [最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
# g; t0 m2 e( Z. `7 E2
& E: c- ~/ P& |( k4 z( A3 ~ ) 。

3 a9 \" H$ a2 ]8 _- e
  k# C. p. R, Z% D( K! ?5 F代码实现
$ `' L" P$ \* s

8 H( r/ m3 i' {2 K" j. p* p& i, uimport java.util.Arrays;
public class Solution {
       
        private static void bubbleSort(int[] nums) {
                // 循环次数
1 V/ a2 j: J$ E+ b( G0 s# A. ?% M9 X                for (int i = 0; i < nums.length - 1; i++) {
6 q8 O. Z: L2 G) T6 N+ B" T7 z                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
                                if (nums[j] > nums[j + 1]) {
0 G: O) d& w8 z8 f                                        swap(nums, j, j + 1);
                                }
                        }
                }
$ m" @3 }; l  }7 l8 d  C9 i" R1 z        }

* j3 y/ Z) N3 s& d4 D; L( p
        private static void swap(int[] nums, int j, int i) {
3 K% H  s7 ^# U5 j6 t                int temp = nums[j];
3 }* v5 i- n8 O4 |. B2 M7 g                nums[j] = nums;
                nums= temp;
        }


/ _$ L8 ?9 D1 ~) g        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
5 A9 q. }$ {& }                bubbleSort(nums);
* V1 l, y* O* v  r. r$ S3 o# a                System.out.println(Arrays.toString(nums));
        }
}
1
2
3
4
* n& P5 H0 o, Y) m( Z5
6
7
8
& @# y2 }, A5 s9
10
11
- b( J2 L+ d* d; F12
/ C) W, f5 M/ e  z+ Z1 j5 F13
14
# ~4 f' S3 e! [5 b8 v15
16
) u" t: P/ k( n/ E17
. A, j) d2 z) G4 V, @, w) }3 T18
1 F" X: ]4 e: l  ]1 S19
2 ^/ e1 A' O2 ?3 r6 n20
21
; Y  O1 N7 d1 `4 u3 r22
23
* W. _+ D# }4 S) J# u4 n/ G$ y3 E( H24
25
! D7 S3 E# z9 ~7 G26
27
: g  @& d# Q5 [快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
# ]% G6 v8 g8 C6 B' ^1 D

# G- T: F1 Y) y2 d  h9 q1 S代码实现
& g' E' s# A4 V! x* i
! a9 p8 h1 l" M4 g3 }' k
, d5 ]' S8 l9 o! @6 Npublic class Solution {
       
        // Median-of-Three Partitioning
        public static int selectPivot(int[] array, int left, int right) {
                int middle = (left + right) / 2;
               
                if (array[middle] > array[right])
                        swap(array, middle, left);
                if (array[left] > array[right])
+ H. w% [3 e1 e2 o                        swap(array, left, right);
/ r& a2 Y8 H  W4 D# ~8 Y0 j+ d                if (array[middle] > array[left])
                        swap(array, left, middle);
: i  L5 y9 K/ W; {) M               
                return array[left];
& K% u: O4 `: u) M        }
$ |- y- T" B8 A0 g# M       
8 L; B4 t9 h" }* h, V8 v        public static void sort(int[] array, int left, int right) {
                if (left >= right)
                        return;
                int index = partition(array, left, right);
                sort(array, left, index - 1);
+ M- M- A4 ^3 a! [  s4 @9 B                sort(array, index + 1, right);
3 B, X! J. f' P6 D+ V& ?    }
- [4 Z) |# d6 v       
        public static int partition(int[] array, int left, int right){
        int pivot = selectPivot(array, left, right);
9 M0 Z1 a7 |6 }+ q5 v) q/ W        while(left < right){
6 ]; K( v4 k" u, y9 v& P            while(left < right && array[right] >= pivot){
                right--;
            }
$ S+ Q: H' a4 v6 J' k            if (left < right) {
                array[left++] = array[right];
, Y0 s/ k0 B! n! f. a: b% e0 a1 C7 W            }
5 V/ x$ W& s# x7 P# S# k) M& {" e            while(left < right && array[left] < pivot){
4 E6 c8 X8 Q0 g                left++;
: x9 r2 z1 o- C' T1 V; s! l) U8 F            }
5 c7 B7 ^% `% E% ~% m" i0 G7 `            if (left < right) {
9 Y  [2 G; x) x( T3 n! m1 G' D- ?5 i8 ?                array[right--] = array[left];
            }
        }
2 S; t) o: }) S            array[right] = pivot;
$ ?; V6 f' P6 D0 d, M5 a( n        return right;
& ^* ~8 x! S* f; Y. \% Y) g    }

1 Q# ?2 K( F' A
    public static void swap(int[] array, int left, int right){
! M7 R% F4 X: u9 g6 D' C            int value = array[left];
1 D6 k$ o6 l7 A% _  V            array[left] = array[right];
            array[right] = value;
3 w& g  `5 K' G' ]    }

& A# g0 M" y" x2 Y% P# b
) Z* j# J4 K) R5 u  h1 x/ J        public static void main(String[] args) {
4 X. k8 F; v0 b" h: t) ?- r                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
. _5 K/ u: o: G                // System.out.println(Arrays.toString(array));
                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
) o7 D* n8 u3 N6 @        }
' D5 E2 D- Y. p5 Q}
' v3 E" z# f  Z  B7 |$ y  s1
2
% M3 D1 g6 p; A" e+ A2 Z4 O5 Q3
4
5
6
# m# \) [: _4 v& m' |0 e; I( d7
  q) N; X: t: Q" ~8
9
10
11
12
13
9 }4 z) E! f+ W14
15
- {4 X) Q0 q- M; [0 H16
( N$ \; N( U. @8 t  }: n( B17
, |: w/ u6 r; g0 k4 @5 N# {( f18
& Q) z+ j0 N5 t( X0 `, C; h6 D19
20
21
22
23
) x  N( o3 D" H+ k) f24
25
26
2 f% ~8 ^" D( M/ d+ M! c27
$ C' k- ?, n, w2 ], e28
29
5 k8 s+ a3 d% _; ^' w' A) p6 m& T- [30
31
32
0 M/ a  U2 z: \33
34
* k: n- d6 p- F$ |( F. t" z35
' V' }3 y! F- v, ^: N36
37
38
! g; j) a* M9 _, p2 s39
* X2 D/ r  ]& A4 o  @3 w40
41
42
43
44
. ]  x9 k* J2 W' V  x3 Z+ f4 Z* d45
: ]' U6 M3 n% c4 N8 l46
47
48
49
  R$ O+ f$ K& I7 y$ v) v50
% w. S" U# ?' u' B* K/ y* N' W" [51
* g5 u" I: Z) i1 G+ w1 F52
) ]1 ^# g! T9 y  Y$ t/ ^53
54
55
56
5 d5 H6 H0 T# j0 X57
归并排序
将长序列从中间分成两个子序列。
% x' b; p  l/ t7 R' q3 a对这两个子序列依次继续执行重复分裂，直至不能再分。
& F& T# Z4 v( A递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
1 o" p& a) ~. u
* f, \1 M* n) f; R
代码实现**
/ x  Y2 q5 V$ |7 n2 E

. l: [" s0 d: I$ W/ I, Cpublic class Solution {
        public static void main(String[] args) {
' V) S2 \# Q! C. H                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                int[] arr = MergeSort(array);
( R/ |" d4 h1 j3 w/ w* G                System.out.println(Arrays.toString(arr));
        }
0 ~! Y. D% J& ]8 T# N  r
0 Y$ U5 @. v. S) U1 B
        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
                        return array;
. }2 w, C  [- i                int middle = array.length / 2;
+ b6 j" N% V0 W" H) q                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
7 m: U( W6 u7 U0 x$ V5 [9 l5 F                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
! o4 N6 Q& V. T% P; X7 A1 i/ q                return merge(MergeSort(leftArray), MergeSort(rightArray));
# @& _2 s, I7 {$ p: [7 j" G1 v: Z        }


6 d- h9 t1 c- K& C/ a        private static int[] merge(int[] leftArray, int[] rightArray) {
+ a. \0 S. x4 g0 x' {$ |; ~                int[] result = new int[leftArray.length + rightArray.length];
                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
' L) u0 _" K5 s2 T* s$ I                        if (i >= leftArray.length) {
                                result[index] = rightArray[j++];
9 [6 l0 q4 u  ?$ H9 M  F, G                        } else if (j >= rightArray.length) {
- Y3 l& w3 t8 |0 f* k5 `                                result[index] = leftArray[i++];
+ x0 P2 M2 a) C, j1 M  ?                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
                        } else {
                                result[index] = leftArray[i++];
                        }
3 M6 X. n: P8 t0 H; p                }
3 l( t- C# U$ `7 E- v                return result;
        }
8 i3 g- _( t$ \+ r) S- _# K$ Q  U}
+ \6 r+ K! F* t0 K" v% P1 l

$ [- E' @/ |/ [& w' q1
2
6 h; _: g! I' }: Q) d8 B$ g5 I# z3
' E% B2 z9 w1 _5 [, r+ y0 |) x: f4
5
6
7
8
" O2 z. ^* [& j7 W9
8 E7 ^6 o# Y7 D2 G10
11
) D- n( L; E3 Q3 U12
" V; C% s  ]5 a" s0 s* s- [% c/ i8 v; u13
14
) m8 r; [6 j4 t+ X5 R# x6 [. @15
16
) Q+ Q( {$ `+ o. K& y17
18
19
20
21
22
23
7 m, _2 F3 x( Z24
; M1 S! L; Y+ g, Y6 ~25
26
- `  S7 J+ k4 g8 g; e5 |27
9 P! t9 G( T  k. }$ C9 s5 F2 H28
29
7 w6 S& M  r5 K4 |% |* M/ d3 s30
31
32
33
基数排序
/ `" Q: W% k2 X找到数组中最大的数，确定最多一共有几位数。
8 @8 k$ z) X" N# z: ^" L9 C" S! }8 B按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。


代码实现**
: z7 u& Y0 ]0 ]/ Q; z$ x2 _

! ?: H$ R1 c! a( epublic class RadixSort {
+ ~4 c3 b7 ^" H4 _
4 N0 L! R4 U. J4 H2 v& o
        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);
                System.out.println(Arrays.toString(arr));
        }

  s- d1 B& H, ~4 j; k- b& A
- @3 u( J+ b6 i* ^9 C        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
- c4 P: Y% q% v                        return array;
                }
& l7 }5 o, Q8 S$ z: R                // 根据最大值找到最大位数
' q2 v& e4 m$ S/ ^% S8 s& E9 J                int max = 0;
0 ~; t7 d% X, w5 F" Z* F                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
" X2 H0 u* r" ?+ k3 y& }8 v7 R                }
               
5 d( q* S0 Y: G/ B: b( t2 j/ n                int maxDigit = 0;
  z9 f. v7 T' D9 I9 q6 ~1 s9 e                while (max != 0) {
& r" T; k" T. U4 t                        max /= 10;
4 M& E; [! @7 T% f+ y" P- [. p/ i" t1 S                        maxDigit++;
; I7 g( b, r/ P# k                }
               
1 l; E" |: }8 z6 S7 K                // 第一维: 0~9
. N) L; v" t& t4 z3 c                int[][] radix = new int[10][array.length];
. A6 `- v) q' W  ?- d: @                // 该位为 i 的元素个数
                int[] count = new int[10];
/ m' R* A6 b' h+ |$ q               
                int m = 1;
                int n = 1;
               
8 h8 G3 [( I9 \/ X7 r6 V. l, s                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
, t* u$ z8 O! M% X' L4 w                                int lsd = (array / n) % 10;
                                radix[lsd][count[lsd]] = array;
9 x8 ?- S" L1 J7 ]/ M, b                                count[lsd]++;
4 \) _4 [. g( s1 T" @                        }
$ q4 H( a% S9 X$ ~                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
+ D4 ~! E' x* ]& @) K2 _                                                array[k++] = radix[j];
. s7 t6 d( W( N$ c+ |. ~                                        }
* t4 ~& x0 X  j+ Y1 }" a                                }
, V0 T0 c6 a! p2 V/ F$ s                                count = 0;
/ |( ~; H6 O! y: x7 o                        }
                        n *= 10;
% d; K9 {( J# D% A9 Y( q2 V                        m++;
                }
( t: h( o7 p3 D                return array;
( ^% J4 v1 q$ b) r        }


% v9 t8 m" Y* h4 S}
1
& I% S0 s. e4 B" A/ {+ S! a3 t% Q; \0 y2
3
3 |, \' c1 s# n4 F& A% f3 o6 T4
5
% ^1 M7 e1 Q* B* g1 A6
7
. l: Q* O5 e; j7 Z* ^+ Z. X* r8
  A9 h( t' f( c9 R, N( ^9
10
11
3 K2 ^. c3 ?( v6 W* g! Y2 s12
9 h! _0 d4 l, o+ Q3 A* O7 z13
% q3 p+ V4 L1 d3 d/ Z14
' I( g. g1 S$ ^9 ]+ ]3 c# w& O15
$ \/ D2 `& l) f& ^: u5 M" F& }16
# @! P2 L/ Z2 n3 ?/ ?9 E5 f17
18
19
2 b! `3 \) k0 K3 f( T20
5 m: k) G9 R7 H  C3 ?21
22
8 C3 K/ S- R) U) |# A4 u& x23
% n' I$ T! \# c% A+ D9 P( l24
( ~! R3 O; h2 h. R3 T25
26
27
( h( x' e8 R, D% T: t; |. L28
, ~- r5 i* i! f  Q5 @% m29
# l5 J# F, Y4 j: B4 h1 e' O2 L30
31
8 }7 L. n6 f& b. X# v% l% T32
33
34
35
1 y* W  l! H* H. K. `; g! n; m36
37
38
8 }4 ~5 y4 M: K. H9 \* K39
* x1 e0 g- B! ]4 r- |# p40
41
* a" i6 C# c' t/ @% a! C, o42
) Y/ |" u3 u7 {. }! A! a43
7 [( N0 E2 n) w  a44
45
% @" v, x: \, Z9 M2 Q2 A3 z: `! b0 c46
47
! [+ F/ g2 g: Z# M6 t9 \48
49
50
51
52
, @6 U5 f3 H4 s3 p- S53
计数排序
; c. y; d! K* x# A# ~3 ?找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
$ s0 S9 E2 o) Y" x- F6 U  j  Z统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。


代码实现


! I" p, E/ t- Q1 [+ g( Npublic class Solution {
& @) m% J# Q5 r
' G$ t  a+ U( \) k3 }5 j
. m5 c" |. D; w5 i  l( n/ P        public static void main(String[] args) {
% L5 c9 F- D% k+ O" x2 w                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
& N4 Z0 S$ k  k5 `/ b5 T( t4 u        }
) j$ h2 c3 z/ r% w

6 U3 ^9 A1 u9 H" O0 e        private static int[] countSort(int[] array) {
3 L" W/ \# z( U8 W- P                if (array.length == 0)
                        return array;
+ W( g. D# ^# E7 w' ^- \               
                int min = array[0], max = array[0];
2 @. N: i9 k( T( S7 W! u               
                for (int i = 0; i < array.length; i++) {
9 k9 l2 q- ?( q. c- p0 X                        if (min > array) {
                                min = array;
                        }
  A: e9 ~9 L# O& [+ z                        if (max < array) {
/ r6 X" H- H7 O                                max = array;
2 M6 h$ i, \1 g6 c* K3 {0 C                        }
8 C( o$ b3 [- X0 v                }
: K1 y5 ]/ U) F) U               
                int[] count = new int[max - min + 1];
               
                for (int i = 0; i < array.length; i++) {
8 c, Z: m! K. b: A2 ?                        count[array - min]++;
7 @- A1 y% S- I: R7 u                }
2 E9 b8 G  {! G6 R( {               
                int i = 0;
                int index = 0;
1 s/ w/ G3 `( ~$ d                while (index < array.length) {
" D+ X. E. z2 i                        if (count != 0) {
                                array[index] = i + min;
                                count--;
                                index++;
                        } else {
                                i++;
1 p: t, O! i2 m5 E3 m3 B5 A; ]4 h                        }
                }
5 Q; R# m8 N0 K9 Y/ ~' Q                return array;
        }
* E5 E8 g+ n& B& s       
}
1
. t! e8 f. a. n* T/ J5 v2
0 I" `7 w9 j) k. \3 E6 ?' x3
$ W: A' d9 j1 M4 l8 G4
5
6
7
9 x6 g! q. [" `! X) }& g8 Y" J8
9
. ]! G: w: U$ W% l8 W10
11
12
6 X/ P+ X! a) E13
, P$ l: M$ ?, A0 s9 H- I9 G2 y" i14
15
! i! c$ c, [! ~16
17
18
% v( Y% q6 S: I3 p  l3 {+ A19
' A' J! Z* h; [( g4 ~4 y: H/ Y; d20
; R+ @; N. G6 _' l6 d5 B21
! V1 p+ c' N. \7 {0 d9 N: u4 A6 P. L22
- b+ r" i$ ^0 t8 M- ?+ K23
24
25
  i" c% n6 a) ]0 |& w6 T5 `26
27
+ v* D% [5 |) t28
" R! E- n  ?/ h( y  B! n29
30
31
  ^7 @9 f& z9 U32
+ W6 R1 H, a' ?0 X) P" R0 Q33
34
7 O) P+ Z. s! b9 \35
36
37
3 C1 j" T- M% j; M9 a4 _38
39
40
8 ]# s5 m. c/ w+ |" f* T9 I7 W, R- f41
42
43
44
. e4 }# O. P5 U) m) p, i桶排序
% T- \  H5 m- M————————————————
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
- O1 @" x$ n1 D0 l
4 b% Y6 j7 e1 \, W5 S- ?