十大排序算法（Java实现）

杨利霞

; Z3 q# O( N5 [- a/ A% _, o8 N十大排序算法（Java实现）
+ r( A  d$ q- w. |6 H3 X
, }, F2 T$ l8 y! Q" i8 I十大排序算法（Java实现）
- b) v* d$ ~) ^0 O排序算法框架
排序算法性质
插入排序
9 H3 Y3 s8 }( i0 v) u* }# }直接插入排序
希尔排序
选择排序
简单选择排序
堆排序
交换排序
* H5 s4 ^" B% f( R$ ]' ~! o冒泡排序
快速排序
归并排序
基数排序
计数排序
* @) T: g" K! y2 v/ a: @桶排序
6 q$ A$ L3 Q2 V' ?( M% o3 ?: J% O更多文章点击 >> 这里


排序算法框架
& h6 Q* M5 U4 O
( ]3 k/ \0 J; S" p- M2 F
) X0 t/ E0 r! p1 I! B
9 {* u& E' T/ ]" W; N
排序算法性质

8 K1 u" ^. T. S* O& r  @0 x
( @( k7 j; \% C: f0 f7 V
% v6 V: U% n" \
插入排序
直接插入排序
从第一个元素开始，认为该元素是已排序的。
取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
7 \9 e" L5 V3 n  m2 u& h: A2
4 C" T7 {, N+ n& f* q ) 。
+ Z' _1 F4 j, d1 Q) e1 P' Q
) x, E& w0 d/ h+ t
8 ~; a" [. q) k: R0 Z, L代码实现


& O6 X6 e/ Q. a$ X# d9 G1 _public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
) Q* y' d% E# {0 x2 E$ l! H( ]9 b                insertSort(array);
3 X* S2 i4 s9 K2 _                System.out.println(Arrays.toString(array));
        }


+ o6 V: I4 u# T) @+ w3 [9 M0 Y+ R0 ?( Z        private static void insertSort(int[] array) {
; H, N! G. f* [% H                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
* }+ O( q; Y4 ]4 p! z3 F* q8 F                        int index = i;
                        while(index >= 0 && array[index] > data) {
                                array[index + 1] = array[index];
                                index--;
* K# K" ]! B! H8 \( J2 K4 \                        }
& t) S, H+ v# N3 w: i) u                        array[index + 1] = data;
                }
        }
; u* p9 C5 C4 Q: ?6 V/ ?9 k2 L}
1
5 v) |; _5 j( H/ g2
3
- Z. W0 l$ z0 A( l% z! B* b4
5
6
4 L+ u  B* {. g; n  ?* c7
. R; p- q5 w8 x9 {. a6 ^8
; X  e( n; H: ?( m& V# n9
2 g3 [6 |5 N6 s1 T% v, e* L10
11
. ^' \; q/ n, l* k2 G" Y12
13
7 d* e! N! Q; t/ w. \* m3 k14
15
16
1 ~# V" B/ E/ q8 f) Y. e- U/ {17
18
19
希尔排序


时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
  t5 U1 H" R! v9 j" S4 S3 z/ ^

代码实现
- X: s5 L0 R! ^
; V" a# S5 z4 [3 F5 M) W5 W7 ]
public class Solution {
        public static void main(String[] args) {
; C) D2 u5 x, E* h3 U  K                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                shellSort(array);
                System.out.println(Arrays.toString(array));
# Z# Y- D' G( `, g0 X& Q        }

0 `' a) l6 G1 K9 g- M  I' r
8 h$ }! b5 s- M- e) H9 R        private static void shellSort(int[] array) {
/ t# i3 N) n1 x) D7 C6 j" m8 ?3 v                int gap = array.length / 2;
                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
                                int index = i - gap;
                                int temp = array;
                                while (index >= 0 && array[index] > temp) {
3 |% }2 }/ H8 R" T                                        swap(array, index, index + gap);
                                        index -= gap;
3 L* u( |; E% x6 W& m3 z+ i: x                                }
# \6 q% P# A3 S$ p5 h) [9 \//                                array[index + gap] = temp;
) A4 ?: o& {. Q. @                        }
0 \2 C( [/ u( i/ I0 x% h8 e                        gap /= 2;
                        System.out.println(Arrays.toString(array));
                }
        }
" k' C9 Y5 r9 {  @8 o
0 M, C6 @( r+ D5 a* J7 p( b+ D
        private static void swap(int[] array, int i, int index) {
                int temp = array;
2 R+ M% S% Z( D( w                array = array[index];
7 b, V* g, D' J) Z# k  [                array[index] = temp;
        }
}
' y) W9 o/ Z. P. R: \! ?0 {1
% {4 c/ q! K# F* p1 |2 J2
3
1 L7 f" K! F3 J/ `, p4
5
6
% {" Z9 g; d. }1 Y( `9 T! N( C) m2 c. X7
8
9
$ p" ^( u; j( T10
4 K8 B+ \6 O/ Z8 q( K11
12
13
14
15
; c* ]. M  D! @16
1 U: r  X  c7 q+ P17
18
6 k$ ?" V" X# G% v19
. `: r' b. t% x1 b! q! ?20
21
22
$ [& a6 w9 Q* P+ K" `- ]23
" G2 K: C1 D+ P- g24
7 U3 K/ j( h; u4 C25
26
27
28
& q3 w8 B! S6 n' o: z2 W29
30
选择排序
3 |% a5 B0 b+ J7 _: w: K简单选择排序
从未排序的初始数组中寻找最小元素放置首位。
- k2 x$ `9 u3 f. M( N- ~9 y  m# m从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
7 i$ M4 D2 e1 {# E时间复杂度为 O ( n 2 ) O(n^2)O(n
% O8 }8 ]" @; h% F2 A2
0 A3 n0 E0 y- p2 k# I ) 。

$ g) ~( K4 ?) g! |# H2 H
, X$ W: I! I$ e6 k代码实现**


8 A5 _/ J$ K4 h, V8 Zpublic class Solution {
        public static void main(String[] args) {
" u2 J, I) D  @0 [) w" L+ c                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
                System.out.println(Arrays.toString(array));
        }
6 p5 H4 C- e& z5 P, U  G# I
1 m3 p: t- R! T6 x1 j7 D8 F4 J
# s6 q1 a3 \9 t  z( G        private static void selectionSort(int[] array) {
  i$ d+ S/ v; ]3 E+ s$ V                for (int i = 0; i < array.length; i++) {
                        int index = i;
$ F) l: g! x) f                        for (int j = i; j < array.length; j++) {
' \5 i& X( A  C) o                                if (array[j] < array[index]) {
# s* x7 i3 c: B! n                                        index = j;
* Y2 V/ y9 R+ w+ K& ^( L                                }
                        }
                        swap(array, index, i);
                }
        }


        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
                array[index] = array;
                array = temp;
" p- ]* E7 b! @' o+ V$ j) G, l4 x        }
2 A" j5 N' d- r- X$ u" ?+ q}
1
2
3 I. q2 K0 R# T+ ^. Y3
4 g4 Y; i0 d# m" l4
5
0 a' A7 Z" H# q: g% g' a6 [6
: j7 L8 ^2 f8 Y5 x, c7
8
9
, L/ z% C9 v% T6 T8 W10
& c9 n' y+ e" C0 b8 S# F: V8 Y$ c11
* j' R. b! L" {) N  z12
( B9 E: ]. {8 C9 W13
! F' P. K1 c: m* X% f  U. a1 I14
15
# t, q# L" X# R9 m5 m+ B+ ^$ c16
17
# Y" `2 d8 W5 ^, D18
19
20
21
$ h9 f! t6 ]$ w+ P) }5 H3 ]22
23
24
25
堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
  Q3 z; X) n: R2 Y; j9 q

代码实现**
7 D7 K/ h; p. S

2 e  Y4 m; i8 r5 q# d6 q- t0 Ppublic class Solution {
, ]( u! G  a/ x$ y' X        // 建堆
        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
                for (int i = (n - 1) / 2; i >= 0; i--) {
# C, U5 ?! b$ v9 Z+ ]& a3 L! a                        percolateDown(arr, i, n);
                }
; e) O1 D- A) j" W5 F        }
, y' F; l7 T5 @6 E        // 插入
5 `# n) ~- \& Q+ w0 K        private static void insertHeap(int[] array, int data, int n) {
3 h: C4 _9 }. |                array[n] = data;
                percolatrUp(array, n);
        }
# P  s1 Y$ Q: F( F; Z( [; I        // 删除栈顶元素
& V. G8 f6 h+ y# k1 g        private static void deleteHeap(int[] arr, int n) {
% N8 J5 N7 q2 p: V  k$ c                arr[0] = arr[n];
1 D$ P  M9 V* A8 t                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
        }
1 k' d2 d0 Q: U9 \        // 上浮
        private static void percolatrUp(int[] array, int n) {
" e+ Z  {# c, G# S; E9 G' v: }                int data = array[n];
, K1 x" O" M6 {                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
1 L8 ~* T0 H3 `. K( j1 n                        array[n] = array[father];
                        array[father] = data;
* \1 V, [* b% O2 L4 w% L& m                        n = father;
0 y; ]. R& q( T" A6 @8 C                        father = (n - 1) / 2;
3 v, G' A& h$ I, q- e                }
                array[father] = data;
        }
        // 下滤
  J9 ^' r0 l+ t& {0 O        private static void percolateDown(int[] arr, int i, int n) {
, m7 p4 U$ Z4 B2 J                int father = arr;
                int child = 2 * i + 1;
                // 遍历整个该根结点的子树
1 Z* t( k3 n# x/ b) g                while (child <= n) {
9 m( L7 w9 `8 F8 N$ h                        // 定位左右结点小的那一个
                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
                                child += 1;
                        }
                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
! @$ Y9 g( W  y# J                                break;
                        }
                        // 互换根结点和子结点
, Y% u) c: F; `5 G  n/ G# ?                        arr = arr[child];
                        arr[child] = father;
& d6 A. k4 B+ k: {6 J; m" N                        // 重新定位根结点和子结点
& g7 D- H; {+ y5 x                        i = child;
                        child = i * 2 + 1;
$ J9 ]; H8 t1 D, D3 U& L5 K1 s" E                }
. B) x+ \% R( t- I. S) z7 x        }
6 o0 o+ X- ^( M$ f3 W* @! c   
        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
' F1 @* J$ _  x& [                creatHeap(array, array.length - 1);
5 x$ j: P* ^% P4 r! C9 |9 d; n                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 1);
+ m3 `3 p0 T+ q, c8 M/ c, ?& ?( b                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 2);
                System.out.println(Arrays.toString(array));
- q% u2 I) l  v* G% G               
8 s1 Z6 z1 a3 Z; W+ @7 Y                insertHeap(array, 3, array.length - 2);
, K; K) S0 o0 P. x* N6 N: ^                System.out.println(Arrays.toString(array));
        }
( h8 I! \8 R5 Q" H7 K}
1
2
3
5 ~1 o, F2 S8 ]4
5
0 m3 x0 D( G) a0 ?5 Y6
4 a% t7 G1 ?  \, F! \7
8
4 l+ x. [, f9 x4 g5 q' F, d9
10
11
12
13
14
15
16
17
18
19
) X0 K0 v- r& A8 O20
21
22
23
# R' z2 k0 {, O24
25
9 H8 g* o4 A6 j" ?" m26
27
, G5 v! }% Y: B" f9 o8 r6 v* Q+ s28
29
& r- h% W/ Q8 v4 z8 W2 }30
: m& ]% i( L2 M31
32
33
* n! g2 C$ ^, J2 b34
0 b# F1 }. Y! N35
2 @& F3 i+ w- f! ?) j: B$ z36
37
38
5 z: c, D7 [3 N39
40
41
42
/ S3 G7 \  b+ q# T- u, h43
44
! I# a( c+ t; b45
46
# H; I9 X; M# C* i) w% T; X47
. w$ s/ U0 C  c- ?3 l& K% R$ {48
49
. M3 O) I& p( a1 K$ E1 Z( Z' M  N50
6 E; i) n( M6 c51
6 K( {" v3 e9 L# R- A4 I4 `52
' m- Z- V) o& o53
, Z, Z/ _# i8 B$ ?54
55
3 p- U; _* g/ o' }+ I4 Q56
5 C* z( n! k3 T) Y9 e57
58
59
60
/ B% I9 w+ p' X. u4 W61
, D/ T7 t0 ?, V) j62
63
4 E; p, W# L! q. Y3 H. u0 M64
8 e/ |+ @- {( Q6 P0 O8 {  ~  k# q65
66
# d7 `1 f0 I8 A& W  I67
/ u: w8 W  @4 {- x2 [68
69
6 P: Q* j# V; [9 s" b5 G+ P  A( @70
& [- U, O9 V4 x- T交换排序
6 I* W+ T, R+ ^, ^冒泡排序
6 _) N) d4 ?/ `# s% D3 ~依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
, Y" t) \  z. @& p% F9 X1 F最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
" u  e" f5 s9 F* r. B  {8 O. ^2
, ~1 q, T+ o) @  h5 B' P- b ) 。


/ \  r9 w# I9 H  X代码实现

! j2 G: g+ l; B& _9 V
+ @, K% }! S  s' Q: f1 l( \import java.util.Arrays;
public class Solution {
       
        private static void bubbleSort(int[] nums) {
3 z; i' l- B6 m( T2 c4 ^                // 循环次数
7 T# c9 H9 n+ g4 `                for (int i = 0; i < nums.length - 1; i++) {
2 _: }9 o& E6 T4 S" u                        // 比较次数
8 e# l" Z/ t0 p( b$ p. ~                        for (int j = 0; j < nums.length - 1 - i; j++) {
                                if (nums[j] > nums[j + 1]) {
/ Z' ^8 k: _1 M# M! C2 t; a' q                                        swap(nums, j, j + 1);
                                }
                        }
                }
        }


8 }" N6 S  \7 m, l7 Y5 B4 G        private static void swap(int[] nums, int j, int i) {
% ], i5 Y' x( ]) [# F+ [                int temp = nums[j];
                nums[j] = nums;
                nums= temp;
        }
+ m5 t- m+ \' R% Y* h5 b3 o

        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
% q4 m; y6 ~$ i( {                bubbleSort(nums);
6 y: V! k( {( Y. H! a8 M                System.out.println(Arrays.toString(nums));
        }
}
6 T- W/ p8 i3 f2 T, }; d1
0 Y; r! B3 K  c  ]2
) @0 t& u/ ~, P& M' z3
4
6 g) S. q* Q7 h* O% b5
, ^( h/ r+ H( e6 g) w1 v, U6
# g' Y5 t' Z' \# t+ v6 i, f7
8
# ?% M1 ]1 ~) {/ n5 F9 `9
10
) J2 A5 j( x, z4 B$ E* Y  n11
; P) j; P- ^, F0 w$ o12
13
14
) O8 t+ r& q1 V  h: T8 @15
16
17
7 o7 i5 ~0 R: n$ s& t1 p. }( V18
" V" U" F  R1 P) L- V19
3 U; ]7 k+ J0 x, ^0 A6 W* J20
21
22
23
% J! c- ~! k- O! h3 ?24
25
# f8 S( s1 ?7 Y7 G26
. f" Y) K- S! z5 ~27
3 h2 `$ P0 G2 \( f* ^3 l快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


& Q6 Z# G% s0 ~; s1 j' t" C# o, q代码实现

* p5 B5 g" A* l% n
7 D+ n9 O$ y: l: J3 L, D0 hpublic class Solution {
* t* r2 y+ [9 R$ Q- `+ C( R) G8 n3 |       
% w0 @' Q5 K- l& m/ [1 r$ x* m        // Median-of-Three Partitioning
) O, K* m( s# O6 ?        public static int selectPivot(int[] array, int left, int right) {
                int middle = (left + right) / 2;
3 Z2 n0 E5 S8 v& u9 v: u               
                if (array[middle] > array[right])
                        swap(array, middle, left);
0 h5 G) C+ d5 e0 I4 f! L+ U, a7 o7 ~                if (array[left] > array[right])
                        swap(array, left, right);
; H2 N4 U. y: }- i* x! V+ W( i( D1 t                if (array[middle] > array[left])
# G' X: v3 e7 P# M1 l; ?                        swap(array, left, middle);
7 `6 g, a0 P6 m! _% `               
                return array[left];
6 m' _- v9 _( y# S  C        }
       
+ h2 }  n- Q) ?( [4 l5 ?- E        public static void sort(int[] array, int left, int right) {
                if (left >= right)
  q6 z- a. ~: C1 q- U- Q, n                        return;
                int index = partition(array, left, right);
                sort(array, left, index - 1);
" F4 t7 V  U! |. ?0 X. ]                sort(array, index + 1, right);
    }
       
        public static int partition(int[] array, int left, int right){
* v# {0 A4 A2 M. f/ B8 p        int pivot = selectPivot(array, left, right);
        while(left < right){
7 x) @- H% W9 r. w% Z            while(left < right && array[right] >= pivot){
9 D0 S. D/ U! Z% W$ |" Q                right--;
1 ]5 _! ^$ i4 r: Y6 s7 C7 k            }
! v4 s6 `# p) I- T            if (left < right) {
; G6 C4 C/ ]6 }, D3 M8 Z; `                array[left++] = array[right];
            }
            while(left < right && array[left] < pivot){
                left++;
            }
            if (left < right) {
                array[right--] = array[left];
6 z3 W1 s" L! R. K7 |2 `            }
        }
            array[right] = pivot;
        return right;
% ]+ b& p. V/ s# B' O    }
* C. O/ ~1 G: b4 j! C' j
; _8 I' E$ K* `- l3 @
9 x, I) l) n" m4 m. `. {+ ^" L    public static void swap(int[] array, int left, int right){
% I* m8 v3 C  \* y            int value = array[left];
            array[left] = array[right];
( K/ T" @6 M% g4 m% X            array[right] = value;
! l' E% _2 }6 I4 ?    }


0 @7 N3 ~6 R" r% g        public static void main(String[] args) {
5 n0 t/ z0 p" @5 [7 B5 Y, T                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
7 O5 k+ ]! p) l& p  t  C; \                // System.out.println(Arrays.toString(array));
                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
, C: g7 s' o" W1 E; X) z5 H( R' d        }
}
1
3 L) _6 E  s1 v" C2
+ @5 N& g4 s/ p! T/ f9 M! n3
4 i% {$ n9 w8 t- U; G4
2 L" g$ }  H, |$ @) o5
6
7
8
3 R7 [5 \7 p+ i$ e9
5 X! M; O" h. G6 K10
9 W5 B. A) v' ?( E8 t+ f$ Y4 K7 N11
12
13
14
8 o3 z7 A: m3 `0 O" W8 h% e+ L15
4 r# d  K" x, j$ a/ ~0 l16
17
. C" `8 j6 P5 J( V18
19
5 g0 J' M  T- j8 c! I20
21
22
7 W% g5 O5 O* e- q23
8 g' y/ `( N9 m1 R* L9 g" }9 U9 t24
25
26
- v! t7 D. K0 P3 ]27
% i8 c2 V* G' l+ Z28
29
30
. q  c5 n" U: k6 H3 o1 |8 K31
32
33
* {. c$ N& @% y  r: y34
* I8 N/ A4 d% Z7 P35
36
) g: a, P! D4 [$ }# n' e5 [37
38
- T; ^* L3 L: a4 \39
40
* A) }% h  ^, _1 x& D! V41
' Q- o! o" b3 Y' |! d42
) q! [1 X% f, `6 I0 j& U43
44
45
46
& p4 x7 c& W! {! h47
48
7 h& a/ U1 h. k49
$ ]; c8 X; }" Y* p- E) X6 l% U50
51
52
53
$ D2 E, d" r( }- Y/ @  l54
55
, }% ^& f$ J) p$ F56
57
归并排序
将长序列从中间分成两个子序列。
6 P1 M, j" Q; a+ v& p2 X  E  H! `对这两个子序列依次继续执行重复分裂，直至不能再分。
% ]4 P! z: j7 h# z递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

2 ~( B/ W' I6 u
代码实现**
5 ?- j" k5 G* `5 G6 j( U; B' h
1 L, l4 Q* x/ E0 n# N4 K# P& F& o( y
1 x" A0 g  Q6 x+ R: v! N. apublic class Solution {
  h5 v. [6 t  U' Z! v        public static void main(String[] args) {
; v9 s6 F" U! n" F3 @: e- t                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
4 j  J9 E0 y3 N9 C. n  g                int[] arr = MergeSort(array);
                System.out.println(Arrays.toString(arr));
+ G2 N8 S7 G9 v4 t8 I        }

3 M- l, K6 K. i3 P& w
  N, Y# G- k' }- I1 K0 ~, Q- B        private static int[] MergeSort(int[] array) {
2 R9 v4 U$ o! E" s7 G                if (array.length < 2)
2 g/ c8 H6 {+ A                        return array;
& j  C, g3 {/ P5 U' d- x                int middle = array.length / 2;
                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
; V# _6 ?8 R/ P4 \5 [4 G: p                return merge(MergeSort(leftArray), MergeSort(rightArray));
2 M, @6 Y4 c" Y6 G; q        }
6 w" u/ V! X: d5 Z" p; b
* N" A7 q8 p; u% E# Y, Q
        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++) {
2 Y, _9 L6 M- @/ T8 n& {7 N                        if (i >= leftArray.length) {
- F# {: F+ P* \! X% ^                                result[index] = rightArray[j++];
                        } else if (j >= rightArray.length) {
                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
                        } else {
                                result[index] = leftArray[i++];
                        }
                }
) W) E" v  U: y3 ~% l5 Y                return result;
        }
/ ~  y: g; G4 z8 i$ x3 u6 d}
4 Y, Y5 L: E! t% p; K9 `
$ A3 e. K$ G+ B- X
5 ]7 K/ W/ @5 o" u* L8 Q) w9 Q1
/ y, H0 q" Y$ C# u: i$ t2
3
+ f0 c6 P, ]# C; V7 L7 d4
5
6
7
8 K6 `1 G' ]4 F8
9
10
* ]: K8 ~) G8 T3 E11
12
13
, V9 ^3 T' z. x8 F: w- L9 n14
( c5 l. B3 k9 t2 a15
9 v: G& ~+ E+ v3 _' ?4 x16
17
18
- T& _2 D/ l$ o5 J19
5 c: S* y% G5 K4 g! V20
21
; R: Z6 f3 C8 u2 K: q) y; Q2 V4 M22
23
24
# Y6 }4 ^4 ^9 P# U5 v% |25
26
! d0 a2 _4 t5 h2 ]' j27
9 q0 P: i* N( B, S, o+ R28
2 H8 I, `+ Y! E6 f* q29
% y8 \0 t4 T( I1 B30
- W# y7 o1 Z8 y+ p; i" n31
32
" n6 r7 [& A4 {33
4 b: h; `5 y+ ^& U+ P基数排序
5 H, ?$ r3 B9 R+ P找到数组中最大的数，确定最多一共有几位数。
4 u9 f1 N; A; \* u1 `0 }按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
  ~% I" ?" p( E# c  C# |5 G6 C( ~时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
% `+ p5 q+ M  v/ ]( ?% e
' U2 y. n" r! m; z* s
* T+ X! @$ M5 J+ ]# ?& U5 p代码实现**
) S+ Z- |4 V- J& h3 D

( x0 ?( P! U" \* Hpublic class RadixSort {
: P2 c2 r! R3 J" A9 I
7 c3 d; t6 ~0 w, d4 U
$ O: E: N2 h4 a: M% M  I9 v        public static void main(String[] args) {
6 h5 I; f+ T4 ~' \  A                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
                int[] arr = radixSort(array);
2 C# W; c: C0 ~& j8 @                System.out.println(Arrays.toString(arr));
        }

* Q- Y" A  @6 w5 J, i! n4 I( v' [
. k6 M. H2 y1 M4 I) ?% V/ V        private static int[] radixSort(int[] array) {
6 x' y. c: Z1 x7 O# x1 @; D2 I9 i                if (array == null || array.length < 2) {
  ^5 V. \1 T, ^: z" o2 u                        return array;
                }
                // 根据最大值找到最大位数
                int max = 0;
' Q; o1 R, g6 D! T% j                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
2 X5 H$ m# l/ C$ `6 M, G4 N- q4 ?                }
( g$ K  ^- {. i* Y8 _' I4 W- m; Y; [               
; t9 |/ i$ N1 c% K. y* F                int maxDigit = 0;
                while (max != 0) {
7 y' F+ c6 `& n% Z3 A                        max /= 10;
                        maxDigit++;
# A. q  I) G5 q" D/ g+ ~                }
5 [  X5 y! k8 y" h( A               
                // 第一维: 0~9
                int[][] radix = new int[10][array.length];
/ g2 F) k; E: j' w                // 该位为 i 的元素个数
                int[] count = new int[10];
8 T5 x: A8 B6 H% _7 L8 y               
1 G' f! v" R: C7 s2 ]- V                int m = 1;
                int n = 1;
; k' o5 [) A  T9 G, d3 z) I               
                while (m <= maxDigit) {
' a7 {/ c- ?) M0 c( z5 O                        for (int i = 0; i < array.length; i++) {
( d7 f4 ?( L) G# o. T1 W" J                                int lsd = (array / n) % 10;
0 G0 z3 ^7 w, g" F5 q                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
                        }
: T# s/ x- ^' |                        for (int i = 0, k = 0; i < 10; i++) {
' {4 y5 }: _0 s( |: c( S7 B                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
- G1 m/ z2 o1 l. F  p+ @, h5 j, o                                                array[k++] = radix[j];
5 N6 O" \! k. y                                        }
                                }
( k0 _8 c; `# O% q4 \8 u& x                                count = 0;
                        }
0 l( K, [" ?; W% N% W! {" _) @. P                        n *= 10;
                        m++;
- A2 ^5 f2 r$ R( P* K/ [5 V                }
                return array;
2 M0 O8 i  M$ y; I& J        }

( d5 h+ l3 |8 c+ `6 G
}
1
' W/ U/ B. V& N; H; m# F2
3
4
5
6
5 H, `' @% h2 }% H3 [  g, u7
8
2 O7 N* T+ o7 D- Y9
: s% u# V$ s. R! v6 H/ k* Z10
9 H. }$ t" }& v# N, m- {  s/ J6 w11
12
13
& N/ f+ h0 C6 k9 B  \14
15
: p( M9 |! V: H" @! Q6 _16
! s( o- s. P- F17
18
/ T) G+ X' L, m; g: L0 O/ M19
20
21
22
23
24
25
1 m$ j% S4 d$ j0 T+ i5 e+ ?! A26
27
28
29
' t& b- k) V5 E/ m  M3 Z30
31
32
33
4 g8 u% e$ E" s8 {& R34
" C0 Y/ i" e: d+ `, g' A35
; \8 j- E" @! Z2 M+ [0 Q36
37
38
$ |5 y! }& S5 j$ Q4 l: l39
4 @( L8 i3 _8 o: P. F40
# J  k2 ]( U1 E+ k" T41
42
" X3 W5 V1 R3 a0 ]8 D2 }2 J43
8 P' ?3 A/ R4 Z# y3 W, U0 F44
45
8 f  w. a5 ]0 e" E& P46
& N- a: X5 H+ i% ~. Q' m5 J- y% y47
# y" H9 I$ }2 M1 o! J48
. ]+ s, M% R3 Q49
50
2 }: ]/ B) r: I; ]1 }2 ?8 O51
& M7 K% E6 l- x; d! U% e! L52
9 D; L+ ^- Q2 p6 |53
计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
2 h6 |( |5 m' M, R最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。

7 ]* C# ]  M; w4 \" \5 w3 d
代码实现

, p( d6 [. k1 l" e+ ?: A
2 q( D: F' F$ j5 ~public class Solution {
8 s9 c1 n6 d0 s/ G
1 h1 ~! ?2 X& a! f2 j" Z
        public static void main(String[] args) {
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
# X% C* V7 b. r" g5 l; ~, [/ P- z                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
* }8 h% Q' F3 m/ ]        }
; n9 d" j7 O6 J: R4 u# t8 o
4 }" z0 i- ~# b& @
- P" S. L2 n# Z, l        private static int[] countSort(int[] array) {
1 I5 g  i$ J& i7 l, J' j# N                if (array.length == 0)
6 I% m! O  B" g) ?2 F: K2 ~                        return array;
               
' D% G7 F4 U& D# q                int min = array[0], max = array[0];
               
                for (int i = 0; i < array.length; i++) {
7 J7 y. k/ U9 b+ l/ m0 }, z                        if (min > array) {
3 w9 a- K& Y; h3 ~2 G                                min = array;
0 Z4 z  J% h8 y                        }
% b1 j4 Z% W. p* I, g                        if (max < array) {
                                max = array;
                        }
                }
               
! R% x$ P# N. K4 b                int[] count = new int[max - min + 1];
8 f! d2 b% g, X" X! W2 T7 \               
  ?% g9 L3 t: h  R8 o                for (int i = 0; i < array.length; i++) {
                        count[array - min]++;
) G5 H6 y! J8 \; {7 U. F7 l                }
               
                int i = 0;
                int index = 0;
                while (index < array.length) {
                        if (count != 0) {
                                array[index] = i + min;
                                count--;
                                index++;
                        } else {
$ A* L* c) K% S9 l, h( a+ z$ i3 {                                i++;
                        }
, {- F+ v8 S$ p* \% i8 O                }
3 r8 X8 z. y$ e0 ~0 n9 L+ z                return array;
        }
       
}
1
3 c4 d* n0 A# m  N" T. Y2
) U# c1 c( b/ {' W3
8 {- B/ h7 [: u4
5
6
5 C3 q, J9 P/ b( d7 C; F7
8
) J, w* L" c' C# L- I6 ?, c9
" N7 z% r) L; J. X" Z6 W10
11
12
8 i( r% v/ P7 T" {8 ]$ \13
14
15
16
1 A8 E6 l$ [9 [! ?5 j17
18
' ]- v" g2 ~7 V3 V; \5 J1 X19
20
& p; t4 i3 T! I" D7 _21
, w# ^5 @# C" {5 W22
5 }5 C0 a8 u' m, W$ W23
9 \* Y/ D% r6 s; w. q: _24
25
26
27
- N5 h% [' _4 \+ {  K28
29
30
. d& _$ X& a, s7 x! B& U7 K31
, @8 s1 L( H1 v) D; D: ~6 L& o) t32
+ k  w3 X& {1 K4 ]% c1 A0 @33
34
35
36
37
' V) C, r0 c2 f+ b38
  a# U$ l: t5 M39
6 a5 n; h, f- [0 _40
41
. U( L/ e! K* n$ H3 z! I42
43
+ ~2 w0 b0 `5 o  i* L44
桶排序
————————————————
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
+ e1 E/ C9 X- L) U7 t2 w

& j# M9 T! ]. K; W  V# d