十大排序算法（Java实现）

杨利霞

& {2 J$ Y: L# @  A) m十大排序算法（Java实现）
) `$ E6 J/ f$ h- ^. ?
十大排序算法（Java实现）
  F+ L8 g% t# ^3 V  w+ F: t排序算法框架
排序算法性质
' x% w8 v' _- _: h插入排序
直接插入排序
3 t, @% x6 `7 |0 j' A希尔排序
选择排序
简单选择排序
堆排序
交换排序
/ ^( `7 R! x4 o& y冒泡排序
$ X* H1 D# a& c3 r) @快速排序
归并排序
基数排序
计数排序
桶排序
: g, d6 Y; S% O7 V更多文章点击 >> 这里
, W' J; M7 d, h5 y2 d5 s1 R
1 u) R1 M' _5 p5 }& O- D
8 d& Z3 C. U% C: u排序算法框架

9 K7 T, Q8 |4 F7 _3 P; x+ V7 E4 T
" H( H( o: k- V  m+ b

; z( E1 g( C6 x& Z: M排序算法性质



9 ^& t& Q5 [( a8 ^2 d" e
9 p7 {9 z( p9 \' @! a; D插入排序
+ w) x, i' |. i- p) J直接插入排序
从第一个元素开始，认为该元素是已排序的。
1 O1 V2 A& ^  K8 V" q取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
+ N% F, v- y2 H8 i% Z$ X* |遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2
% o: R- n# \- d$ S! n$ E$ Y ) 。
1 z3 e2 ~1 }# ]4 H. }- R

代码实现
" w, w; a7 _+ o) J

public class Solution {
! U8 s* g) ~6 E& z        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
1 N7 [3 J9 x, q, h( g5 s                insertSort(array);
* h& r$ n% B3 `# C                System.out.println(Arrays.toString(array));
        }
; j) H$ u! A, }4 X

9 K2 _& _- a. m7 |9 k* y5 ^) C- I        private static void insertSort(int[] array) {
- h9 o# m% ~3 d0 j, V# C                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
! |6 i  s6 @6 u. ]1 f; W                        int index = i;
5 C3 w3 L5 }5 A- u8 o                        while(index >= 0 && array[index] > data) {
. g% W5 D1 k" N: X0 l                                array[index + 1] = array[index];
0 T- r( `# n: M8 `3 g" d                                index--;
                        }
                        array[index + 1] = data;
                }
        }
: B8 U5 h3 }5 J* N* D}
1
2
& g( p/ V6 m! G3
4
5
# L7 n4 R- b" h5 K% P4 ^6
7
; I$ D& _8 x, B( v8
: g' }* O. T+ ^  ?3 c9
10
4 r  Y3 k6 u( o- o11
12
' ^! h3 e4 ?$ a13
14
+ r' P  A# u/ f& ~5 S" F15
16
17
18
19
希尔排序
) L5 o# O- k1 M

时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
6 F% |/ U& j2 @' l/ {, r

代码实现
- ~) M6 Z* }' S! i4 E7 @) |

public class Solution {
        public static void main(String[] args) {
" R. N* k5 a. g  N& z+ B                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                shellSort(array);
                System.out.println(Arrays.toString(array));
( j% H! q: W. u        }

- b# L8 m1 _* [" [0 z
4 y6 ~: r8 S3 o$ z        private static void shellSort(int[] array) {
                int gap = array.length / 2;
                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
8 V4 }6 q' v. p; G                                int index = i - gap;
                                int temp = array;
0 V, J0 E* i- `0 y                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
' n6 m" R" o) x, r2 y2 I6 u0 p& L$ k                                        index -= gap;
$ {: n. ^, k" }0 U                                }
//                                array[index + gap] = temp;
                        }
                        gap /= 2;
8 F3 Q( d: r- v" W                        System.out.println(Arrays.toString(array));
9 b% z- |. J, p6 q                }
        }
, X+ @, |& f8 }/ l7 z
" }8 X- E/ \; G3 }" \) u2 x/ t: E
        private static void swap(int[] array, int i, int index) {
                int temp = array;
  h! n" w) o& t- I! {                array = array[index];
$ _5 G, L5 G9 W* o' f; O- O                array[index] = temp;
2 P( p6 F8 d; q' c7 V9 r. W        }
' s5 R+ |9 h% D: {$ m1 p" `}
1
2
3
4
5
6
7
+ w3 ~1 |# i9 k; n' A8 `8
9
7 b' Z. H8 _/ f+ m- X3 p$ V10
11
12
13
( Y2 r1 n& M+ L14
15
16
: }8 L/ P5 r5 v' L/ y, m17
' N5 z1 L0 I' ^: u6 [" B  V18
. Z' w1 R' J  f8 D; \9 U19
20
, c, x. [* P" I& A( R2 O21
22
23
24
) _1 t5 K8 q" U: t/ n( r- ^- d25
26
( A' U! f: @' k27
28
6 |( X$ [2 ~! ^29
8 }6 m7 Q% `* w% m$ [30
选择排序
简单选择排序
% v& {+ W/ t; s从未排序的初始数组中寻找最小元素放置首位。
! F; ~5 s$ A/ z; a从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
时间复杂度为 O ( n 2 ) O(n^2)O(n
2
0 g2 Z8 Z$ ~% T% w: B7 W9 l ) 。


代码实现**

/ B7 p9 {" g* ^
public class Solution {
' X4 l; \) g& N* J$ W3 j) T( W+ P0 j        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
/ w  W$ G/ ~6 O7 y7 z; F% Q6 s: O                System.out.println(Arrays.toString(array));
3 o" G  |6 \0 }/ s( c0 D/ s        }


        private static void selectionSort(int[] array) {
# V: |8 y; v" O7 \                for (int i = 0; i < array.length; i++) {
2 T# _" u6 q' e/ Q2 Z  X+ B' T                        int index = i;
; w: e8 c7 z% N; l1 A                        for (int j = i; j < array.length; j++) {
' b; Q( m% x" d4 y  Y0 a% F                                if (array[j] < array[index]) {
                                        index = j;
$ u  P3 c, `! Q0 |- Z& S/ ]: o. t' X                                }
                        }
                        swap(array, index, i);
                }
        }

* b2 A8 e! t4 u1 Y# d, D7 [" o
        private static void swap(int[] array, int index, int i) {
/ t1 ~( n, c$ @& |% z2 r: m0 p, `5 E                int temp = array[index];
                array[index] = array;
- L! O2 s# H$ U! W( _( L8 j                array = temp;
        }
3 J% Z% M3 R% c}
: O/ x' D; V) O7 e1
2
3
% U( D, @& ?5 s3 l7 K4
+ k! [! w+ l5 t' R( q. a4 {) h5
, s1 A4 F% A& d! R% g6
% g; p! p% P; u) B# }2 ^$ c0 ]7
/ O* O& I7 _- h. R5 \- ?1 y/ J$ a8
9
7 U) L, S& w: ~+ ?4 J: C7 ^% a8 ^& A6 x10
, W# E( E6 B$ V3 c11
12
! t0 @5 D9 Y+ }( y13
1 H: z$ n* O- ^: n14
, a! b% m. W) A3 ~15
# o" s! h& V* [5 A16
17
18
19
* r' }; l2 t7 E+ u8 I20
& k% P! X/ i' Q, P# w21
22
23
24
25
堆排序
7 H7 ~6 v! `9 K, q. f时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
2 l" A/ ?! H5 G6 ]+ o& u
' p* z2 E$ \+ ^* x( t/ b) s) P9 L3 [
代码实现**
( t- H  k  D1 F! {( [

public class Solution {
4 V* p0 k- z1 {, y! B2 t- s* N        // 建堆
        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
- l$ v3 c' {4 ?- W                for (int i = (n - 1) / 2; i >= 0; i--) {
; I$ D2 j/ p# s  e                        percolateDown(arr, i, n);
  p  |% n  u9 j  o5 `* K                }
. r) c9 w& X5 M5 x        }
        // 插入
        private static void insertHeap(int[] array, int data, int n) {
, W  c( Q: ^5 G+ Y( w                array[n] = data;
% g* F4 Z0 B: o* v2 y9 f3 y) I                percolatrUp(array, n);
        }
5 T* E) Y4 Y  G0 W        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
6 D7 y) {# k* m                arr[0] = arr[n];
                arr[n] = -1;
. \; w/ S( O% c4 k- M9 W" W                percolateDown(arr, 0, n - 1);
        }
! O' ~1 ^- A. B5 x2 R        // 上浮
        private static void percolatrUp(int[] array, int n) {
2 K( {5 l$ m; b. _& R% k                int data = array[n];
9 d. g" Q: e9 o7 a/ M+ @8 v                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
1 D5 [/ ?* e6 i/ F3 J7 U& G                        array[n] = array[father];
; e% I# ~5 v9 i                        array[father] = data;
* Q: C9 l# O; f/ f4 {( S! K                        n = father;
                        father = (n - 1) / 2;
* j7 Y" N" m3 t4 j5 j# m                }
                array[father] = data;
        }
+ Y) K7 W( a% x/ o        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
/ P/ [$ k3 C- [- [% @                int father = arr;
; \! k9 \. b3 S- p4 b# T  Q7 Q                int child = 2 * i + 1;
8 w. a* H) @) i, t8 N                // 遍历整个该根结点的子树
1 T, u' j' G0 Z                while (child <= n) {
                        // 定位左右结点小的那一个
  m: z' M( Z) s$ X* a/ k                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
& K6 L$ a; u0 v! s% v/ h0 f$ m' ^' j                                child += 1;
$ o( H$ t8 {+ r2 m* [" o                        }
                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
' D6 O  Z5 C  w- q5 J                                break;
                        }
# u6 t8 e0 T" x                        // 互换根结点和子结点
6 M& n+ m# ~5 ^5 y1 ?5 w8 U+ \                        arr = arr[child];
                        arr[child] = father;
0 \+ D" ]- @7 D                        // 重新定位根结点和子结点
                        i = child;
                        child = i * 2 + 1;
                }
        }
   
        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
; K! ^- j% u5 o, \               
                creatHeap(array, array.length - 1);
) m4 p" A6 d" E; b7 q! x6 Z; n0 z7 \                System.out.println(Arrays.toString(array));
& Z  \3 y2 C& ?  v1 W               
                deleteHeap(array, array.length - 1);
3 m+ d  e3 J( E4 O7 I% j                System.out.println(Arrays.toString(array));
9 j' ~9 i2 n! C/ E4 [               
: J) e& o& \( x( ?4 l                deleteHeap(array, array.length - 2);
0 L' L0 n  o) ]3 v: B! ^+ `+ r                System.out.println(Arrays.toString(array));
               
                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
        }
}
( o9 L' X; T+ N) W1 J- @0 a1
5 O0 A, q! [6 Y2
3
0 s" X3 |9 b% K! P8 [7 t4
  i/ t  J. X5 t5
0 q6 k( x  e5 B7 v6
* F% d! W/ E7 a6 G( U6 n7
8
9 g% v: @1 I- X, F3 g9
7 \" ?, v4 n# ?) o) }6 t10
11
12
13
14
15
16
17
5 H. N4 C& U& A# U4 L" e18
! B# P: w+ L" W" @+ @! ]! M, I19
20
21
$ L2 m' L8 T* d* R+ k22
4 I1 m$ ?; o5 R' e5 u1 |23
24
! M9 j4 j0 p9 `& n( b25
  t& ^, N; S; D# Z) U* L26
  [" L4 C3 x, I27
28
6 ?9 Q9 I0 J) k4 A3 ?29
1 C, B* Z) Z, R9 v2 y. }30
6 X: Z2 M* Q, j$ C% L5 Q" ^, C2 l31
32
7 e& i8 X, p/ Q6 U( x33
0 |! l- H; S0 r. @$ I" g8 A1 i34
* e" [9 W+ t& V# U35
36
37
. ]$ ]& v- }/ k/ I" u4 \; e% e38
) W2 P$ I) B0 `39
9 F( S, R  y' ~/ z1 c40
41
: G1 f$ ^3 y. U' |4 v6 `42
43
44
$ q8 }& T$ `' N45
0 @: B8 a+ r" ]) @/ M: j) H46
  n% c% P; W4 J9 j47
48
49
50
51
52
53
# E) e# q! e" W9 S0 d6 r( O5 x! _. x54
" Q9 K- e' y* Y# T) O0 u7 w& k55
2 s  @$ c+ P, F6 N% s6 e' {0 }56
1 L6 Q$ b, g1 Z) ]' n) p5 ^& Y57
. ~! }/ ?9 B, {' R! H58
59
" d9 ~0 }# k+ {1 y. H% k# D60
61
62
8 |# z& O% u% _/ W& U63
64
8 }/ q# T; a& ~65
. C$ K/ a0 x! c* C8 Q+ `. ]* A' G( E5 V66
67
8 N" U* w- w4 r! I) F. _* r( W68
69
. W% ^  P# G4 x70
交换排序
冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
5 l2 F+ U' |, h3 n3 h/ t/ g/ V在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
8 z. m; w! n, R; M" Y2
) 。
+ |5 i/ x6 V6 o4 d
, |. O9 f8 J# c$ g7 f
' n3 c; z, S% @! K1 u/ \: W代码实现
' o4 N2 w( {2 u4 `/ u3 R

import java.util.Arrays;
4 v1 L7 k0 T- M; U1 hpublic class Solution {
       
        private static void bubbleSort(int[] nums) {
; F" U" l3 a$ t2 j% Q# W                // 循环次数
                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
5 `2 V1 C" C* G6 ]! X" {1 _                                if (nums[j] > nums[j + 1]) {
                                        swap(nums, j, j + 1);
                                }
2 Z! L6 \9 n" R                        }
                }
: G5 X: ]5 ]8 t3 ~9 b+ K- G# j        }


2 W9 j. r2 N- k$ |; y. n$ }        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
- L' x: w/ t/ u5 k                nums[j] = nums;
                nums= temp;
, h0 m: `8 }8 N- m2 d        }
: v4 v2 o; H; x# s4 S% ~5 u' m

6 q5 y/ ^, G+ c! o  ]* [" g        public static void main(String[] args) {
5 H" ]! J. K3 o( T) F/ M                int[] nums = { 6, 3, 8, 2, 9, 1 };
; O7 h. `- S! ^8 ~* q                bubbleSort(nums);
4 o+ x$ |  S6 f                System.out.println(Arrays.toString(nums));
1 V% [& o+ c. D& {% b        }
2 C0 X5 K) o4 P1 k, B' k9 Q/ d}
1
2
0 E9 x& _/ N2 z3
: q% w, z4 ?# V; N! e  }! j4
5
6
1 B5 u% M" P0 l" D5 q! x3 |7
: ~; C+ h8 }0 j& s6 W, I8
9
$ t% u& H; k9 A8 a! f10
  P6 N) @! n! O11
. k* K- e- d( {& M& c& {1 E9 i9 x12
13
14
15
16
0 F- r$ y4 x, V5 K$ X) a3 b1 n17
& V% M0 |6 v8 @8 O9 o18
1 K& B( O: Z* O4 p1 v& o- F19
( e$ o/ [5 O& q- ^# f* [7 k4 F20
$ _  j" t" L/ @2 Q0 V2 E! c! e8 ~21
- L/ ~8 F" O* y4 r- s: ?( M22
3 P' E- |$ @* F+ w23
4 P8 O% {" q( h! z" z. W8 d" F24
: G6 m9 q7 w' I$ r25
+ h( S6 \  J6 ]. J- D/ N. D26
7 i) p0 x1 ^( d5 T. V27
快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
. Q) @7 o) E; v- k/ Z' C

代码实现

; \( y. [: M; }( Q
public class Solution {
2 Y% e8 r4 z0 e       
        // Median-of-Three Partitioning
        public static int selectPivot(int[] array, int left, int right) {
                int middle = (left + right) / 2;
               
/ I* U9 K( E  g; f, e# f                if (array[middle] > array[right])
* n$ N8 I; c) N. i                        swap(array, middle, left);
( N% s) i2 T$ z# S                if (array[left] > array[right])
+ R- T% i4 j+ g7 x, o2 l                        swap(array, left, right);
                if (array[middle] > array[left])
                        swap(array, left, middle);
               
                return array[left];
        }
6 ?8 i  {9 z: V0 V$ T( ]" d       
4 j  a7 k' ~/ x" q: g        public static void sort(int[] array, int left, int right) {
) \" B; |/ _! n$ _5 X                if (left >= right)
                        return;
                int index = partition(array, left, right);
                sort(array, left, index - 1);
! K4 |  O* }8 t% M7 G                sort(array, index + 1, right);
    }
       
) Z0 _1 _4 Z1 ^6 T7 T        public static int partition(int[] array, int left, int right){
* g/ A6 ?  Y' ?" Y* T        int pivot = selectPivot(array, left, right);
        while(left < right){
            while(left < right && array[right] >= pivot){
                right--;
            }
3 M4 q* q) R: J/ ]: u4 V            if (left < right) {
                array[left++] = array[right];
            }
( \. u$ c: S! C# q0 X9 s2 Q            while(left < right && array[left] < pivot){
; K1 s8 m1 h  v. |4 C+ ]                left++;
            }
            if (left < right) {
                array[right--] = array[left];
            }
% G  A3 e, f1 _# m4 r$ v5 {        }
            array[right] = pivot;
        return right;
# |5 c) X+ ~- E: @    }

% ?9 r! W5 L+ N1 V) u% x
    public static void swap(int[] array, int left, int right){
            int value = array[left];
; x$ Q8 A1 X/ h, Y7 c0 ]( M% h/ f            array[left] = array[right];
5 @. n9 Y  ]! h0 q+ _' U& {* S' T            array[right] = value;
3 Y6 N8 Y* t7 k2 B1 B6 s! }6 a    }
' O6 Q# ~2 |8 t4 L! \: Y' F7 L
- K; ~. D' c' y, X
# O. _5 M' I4 `! K        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                // System.out.println(Arrays.toString(array));
* G0 g6 h4 N4 ]2 ^' o8 p8 _" O                sort(array, 0, array.length - 1);
$ n7 F$ V( a0 y* Y7 q( z# E                System.out.println(Arrays.toString(array));
        }
}
1
' q3 ^* c3 p. N* h' j2
3
4
6 V( K* H% H: c3 w( L+ m/ ~5
6
1 a: h5 o( {* n0 M! z7
/ [  t2 C4 \% H- w8
( ~0 \% _2 `& ?, g, a/ y* ?9
10
11
12
13
14
15
2 p+ h3 C' w# T* E" I16
17
: }% U( z, c$ r3 H+ P. c18
19
) R: X6 O! R8 J6 k20
21
: Y* [' Z$ ~2 p, I- e8 f3 M22
23
24
3 q/ }) k7 K- |; n25
26
; _' E1 v+ `/ X8 [" p* {4 L0 t  `27
1 k8 U4 ?( P) n$ e5 v! N# \& W28
/ n6 U# I6 a/ }  ?29
) r2 v( V' M! z30
; B" R- ]1 i2 g; z31
2 y; p' i0 R/ C# v32
. J' b/ E) V% x6 [/ C33
34
35
36
37
# h  B! r6 P5 P+ V, ?38
39
40
- d+ t8 a5 F- m41
42
43
44
45
( Y& N; _) ~( z' ^46
47
48
2 M# |  |6 Q: F3 r( y. b49
50
: C+ @" F* ?7 e, y) ]5 ^& S51
52
3 p, f" o% \" I: Q$ X6 V53
54
- M/ C, n3 z: }! m55
56
57
归并排序
/ \- {7 I( |  C9 H; x' F  f将长序列从中间分成两个子序列。
  o, x. d2 c3 p% v9 c* Q8 z3 W& Y对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现**


/ e! r3 `8 ]1 q/ ?; Cpublic class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
* s4 a9 p3 k( K" b5 Z: {                int[] arr = MergeSort(array);
+ k; P, |! w- L% Q8 R& G                System.out.println(Arrays.toString(arr));
        }

) ?3 I8 c: e- _. x/ p  R
: o( ?( a3 ]$ o+ _4 s% I8 D        private static int[] MergeSort(int[] array) {
                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);
                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }

' @* F. M% a% h2 M
        private static int[] merge(int[] leftArray, int[] rightArray) {
( P5 K! H/ a& I; _8 D$ r                int[] result = new int[leftArray.length + rightArray.length];
* S1 y2 ]8 w/ X+ L                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
                        if (i >= leftArray.length) {
                                result[index] = rightArray[j++];
6 J9 ?4 q9 ?! c$ h* o0 @                        } else if (j >= rightArray.length) {
                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
) {9 M0 Q% Q; \! `                                result[index] = rightArray[j++];
- v- j0 g6 S+ x                        } else {
                                result[index] = leftArray[i++];
! |, s4 }8 `) [% h                        }
                }
                return result;
        }
" a, T$ g& Z5 {) p8 [}
5 r( P) g" U6 f

; s$ e# X  e% w; J3 f3 Y5 J1
3 C  |9 H" h& C$ a8 W9 S2
3
4
5
0 v7 D4 m% x4 @" t; d9 m$ R. x/ o6
$ b9 z/ r: z  X7
) Q4 L& K" v: |# Q. h8
- W+ q4 E# M, M- a7 J) i' M- W9
% T' [4 h: m% K! `# ~& T10
7 u7 p8 c3 f; s9 F11
" z4 J( _% A: n% s12
13
2 W" C3 W9 |  n, f5 l0 L9 x& [14
15
16
; u: H- Y. |& {17
; f) |* R: j( B4 T18
19
8 M7 f" E; ~! j2 G: f7 E20
21
) V6 W  H: \6 W2 b- y5 c/ J' B2 Q22
23
24
) L4 K5 T0 q! x! W25
26
4 p3 U- D2 G7 h9 p  R" k27
+ R7 y% z- l4 `28
29
30
31
32
33
基数排序
- G6 g8 i( a0 ^  F找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
" b& _% B+ _' w8 v1 N将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
0 t0 s2 v1 f. {8 j- R1 p! D时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。


代码实现**

& v! A0 |, q' t5 H! `$ U$ i2 N
public class RadixSort {
) R  \- S3 S& P* {! H* z, _
0 G1 K9 Y9 B& N' T( V1 T  i
        public static void main(String[] args) {
2 m. _8 L) C2 ^. X6 p                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
                int[] arr = radixSort(array);
! X* ?. r  Z, @4 h  _                System.out.println(Arrays.toString(arr));
        }
. G. H) w: H5 ^- I4 p% ], N
: j# O! m; v% o& c6 q, ?4 ]8 X9 {0 m
% j+ I: a# o6 x        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
                        return array;
                }
9 v! k7 e7 v1 k$ ]                // 根据最大值找到最大位数
                int max = 0;
                for (int i = 0; i < array.length; i++) {
1 W! Y5 ?: a9 p' c6 S8 F) F                        max = Math.max(max, array);
- a2 N$ F$ S4 B" @( y                }
               
                int maxDigit = 0;
  \2 S7 f% c# s2 J4 V                while (max != 0) {
7 J: x! R" \' Y* f8 j                        max /= 10;
/ s& i! Z# ]- A" ]- e$ i' c& m5 ]                        maxDigit++;
- r& y6 ]/ d; w4 R4 Z                }
               
% b) j) u9 Q4 {$ l                // 第一维: 0~9
: x5 Y* D4 q. L; F+ C1 w                int[][] radix = new int[10][array.length];
0 |0 x4 m& _( k, l/ e                // 该位为 i 的元素个数
! c% v- @# ~3 U2 [9 p' b                int[] count = new int[10];
               
                int m = 1;
5 G/ r8 ^* S1 |! h" `1 J% X$ t" u                int n = 1;
: W3 Z/ z6 T6 _0 f3 V, n8 G               
                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
                                int lsd = (array / n) % 10;
0 G5 V1 ]' X8 Z% k& i                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
" n6 `# ~' n2 b0 K0 O1 g' {                        }
                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
$ T5 L8 Y) Q+ r* ?9 f                                        for (int j = 0; j < count; j++) {
7 u# |: P( Z; _( X" s                                                array[k++] = radix[j];
  O) [; D2 c2 v1 M2 S9 Y                                        }
: l. d- I0 `+ d+ v3 q/ c                                }
0 h" v; @7 s" B$ t& \9 w( @/ ]                                count = 0;
) U3 V; t$ a8 z/ E1 W  @7 o2 e                        }
                        n *= 10;
                        m++;
                }
" d$ U8 p8 @2 S( k$ s                return array;
        }
# K: ]4 c3 t1 Y& N- A* b7 }/ q
9 c0 u# ^- I0 P) ]4 D) l7 R. x7 U' L
& R0 s- w$ N. L" V( D}
. m, p- {1 F: {6 F2 K. p1
9 D, h* N8 _" X  d6 J! f. ?) W2
3
4
+ |1 i: g+ I, B. |( z4 R* h5
6
7
4 }' t) i& M/ `, d8
9
10
11
1 X- x; u4 V" I12
13
# z7 F$ m+ `. L  D( ?" f14
! w3 l" }3 F1 L8 {( X15
16
17
18
19
20
+ q& E7 ?, ?! I" j21
# B2 }( j+ @, q& K22
( l1 r4 i3 l! X# ^8 i# B& z* s# w23
24
* t: {1 q5 x8 T8 |+ m2 z25
26
27
% d- ^/ v4 ^# P6 S" D! O: g8 L, K. U28
29
30
! h5 }/ p- A) K6 ?4 J/ D+ c! l: j31
) P# {, P1 l; d& e4 S32
33
" p* X, p) ^5 l34
$ C0 [4 Q0 ^/ [35
4 |1 M# m% i0 y" P: C  @, S9 f36
37
38
39
40
4 W5 J' y! m5 y3 Z" e- n41
8 n' h5 \" Q0 f1 c42
. x; G5 a! ^- d1 H: p/ ~: L8 A8 {43
44
0 [3 \' ~4 e5 F# \- d1 l45
) Z" y7 |: p* J' c+ H5 I46
47
48
49
50
51
, z0 h: j' L( T- l' H52
53
计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
7 @( K9 D& n* F( x7 S2 f统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
( v7 Y" }, x* l. p+ t% A) F
8 `* {* F- d$ O% d5 L; P0 `; W
9 F3 P" w0 |. n代码实现
) n* q; H( E. T  H9 d/ N
2 Z! v$ j0 x6 y# W; P1 q2 R6 _
public class Solution {


        public static void main(String[] args) {
3 i2 n: v) Q4 Q' E8 R                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
& a( B  e  L! E. a                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
* @. g0 a, N: X  H2 r# ^# F# n" N0 ~        }


+ h* l6 F9 Y6 W3 ^        private static int[] countSort(int[] array) {
                if (array.length == 0)
                        return array;
               
                int min = array[0], max = array[0];
               
! b% }' d. {! m                for (int i = 0; i < array.length; i++) {
' H2 k/ E2 f  H% h4 }. u  w! z! E# V' \                        if (min > array) {
                                min = array;
                        }
                        if (max < array) {
# I  i- s* q- y$ z2 C. U- n  G                                max = array;
                        }
8 q7 V" K; R! W1 `$ b$ ^+ J, p                }
' v7 K7 F8 k3 {; z$ {               
                int[] count = new int[max - min + 1];
               
" E: c. z/ e' Y% Y                for (int i = 0; i < array.length; i++) {
                        count[array - min]++;
# c6 u+ w* w' M2 R7 O8 |  H& B                }
1 [! z2 ?4 I! E               
. T4 Y. r" B! U                int i = 0;
                int index = 0;
( z+ C2 [4 |+ E; {6 e                while (index < array.length) {
7 R' w) [. z$ ?                        if (count != 0) {
                                array[index] = i + min;
                                count--;
+ n* q' U% L* V* N+ ~( c" D0 ^                                index++;
                        } else {
+ X0 u# h& J5 U* y                                i++;
  A- W. X, _' R2 q, k  W2 O5 X0 x                        }
8 C9 I& i3 \( J# x. k                }
. u4 P  l% ]- o/ i( b3 @+ b                return array;
        }
/ n4 V1 L! S  [' o" Z7 ]       
}
% c- c# W* H$ b+ R1
2
3
4
5
6
9 e; O! T4 r1 q2 o7
- X/ ]" P/ Q( s; R, W" t8
# O" i: [' }+ n  m4 O% q9
10
" X+ _/ ~( C2 h4 ~) c  b; n7 I11
12
13
6 b$ ?+ I( G2 A14
3 f. _- k" @  I8 n  \# ~1 d15
0 }) _$ V/ U" K16
+ X6 O/ Z$ F$ P/ A9 k& W17
) U. r3 p" |3 t, s& s: N2 f! m18
* r, P* |  ?  D5 J4 X19
+ _) m: y0 F- S* `7 H20
21
22
. B7 ]/ b6 m0 M23
24
+ b3 L* U# l9 I9 \- O. m25
- S( V. i8 A4 g8 J, \0 D26
27
! \7 \# }: E) c) h2 \5 @! c) s6 Z* `; Y28
29
/ J9 [5 L: x2 {: m) k30
$ @8 x' h1 U4 R2 X& D31
, \6 k0 K8 i; J9 {32
, @( d7 b" y' F5 [% r+ t" O33
0 I7 Q( `; u7 x# i6 L" z; }$ _34
. a& r' B. k) v3 r0 o35
! Y  o/ e0 D5 {& l  `8 Y7 [4 t- Z36
6 {& |! t6 l5 j, z: U! E6 w+ n37
# C2 s8 {8 w! @; M/ a" Z  x38
0 i5 C$ a4 N3 ?9 R( C4 x0 u3 ^, q39
40
- Q5 R* x' D6 ~4 L/ O# g1 M41
42
43
4 g1 J6 {0 i. R44
桶排序
- a% d% @, W2 w$ I& e: V% A# W# ~2 j————————————————
- o$ ?0 B1 p) t8 ^/ {版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" S: L" X$ n( n9 Y. z% K% d原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
" [$ Z/ f. I( M' N