十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）

% x/ K% U3 f$ i  C十大排序算法（Java实现）
排序算法框架
6 }4 G- b5 E. t) X9 s排序算法性质
/ N* n. [5 L# o插入排序
" X( T) S. A7 f直接插入排序
希尔排序
选择排序
; H0 D& Z0 U5 _) M) k. c简单选择排序
堆排序
交换排序
冒泡排序
7 G9 o: F" t! X/ m  x! y快速排序
归并排序
基数排序
( U. G6 W* k  a$ D计数排序
桶排序
( J3 \5 Y2 W% k% C! @0 o更多文章点击 >> 这里
7 N3 |$ R: q7 X( ]! G
) n) C" A  R1 y1 P1 P
0 V, F# I7 }+ r5 P& }0 D排序算法框架
% j; C6 S& O; Q7 O( q  i

+ {- N! {* `3 D) |3 Y
: ?& i; y; b" D
% r1 b! s. x9 H$ H  P  I排序算法性质
' S; S% j3 Q0 H) a  Y# |# ^
+ g2 M. j& l0 I9 U' s# G$ U- L5 c! f
7 j; u& i# f( Q* M

插入排序
: c' N. O$ {4 K- W! C1 r直接插入排序
从第一个元素开始，认为该元素是已排序的。
; }8 c/ L3 l' I7 n' m% h/ d5 o取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
5 }0 b% \5 x5 a% i& P最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
  m" d# i8 q. ^" ~- E4 a9 K2
( v! W4 P. h# E* W ) 。
! U4 v: e/ K6 R
. j! N# Q, w! i: a$ h
代码实现
9 Z! }; M5 y+ c* y  C5 U

: ]( r5 W' H# f3 O, Epublic class Solution {
        public static void main(String[] args) {
% ?" F! _) H& c- \" ~. l- j3 R                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
  m- s3 W% r& w" g  J* \+ Y5 u8 i                insertSort(array);
/ Z2 B# j+ g7 A( V, u& g, @- H                System.out.println(Arrays.toString(array));
        }
8 j& H  b' w3 R% a1 n

        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
( I6 ]4 N* r' M/ o0 V% N( M                        int index = i;
2 ]) W, d& `4 Q" X5 Q* V1 I                        while(index >= 0 && array[index] > data) {
                                array[index + 1] = array[index];
" c: I" r: ]3 C& S% I2 X                                index--;
                        }
                        array[index + 1] = data;
                }
        }
5 q( A5 o2 n& Y/ |5 f}
- y; b4 c' v  ?4 r! I2 N9 t  p: j5 Q9 c1 n1
/ r: F, J1 n( m8 \$ O5 e2
3
4
5
6
" A* s4 j% n. n  A4 ?6 b7
8
9
10
11
; k' R& ?6 Y' }/ H' v12
13
' C/ a" d% X7 w" v# s5 q14
' r; \  o- k+ h2 |15
' u! l8 {! B' h+ t2 Y16
# \4 K* V+ F: B, p% t17
18
8 X9 r. F1 G" A0 e6 D3 H; R9 V19
: E( M! _' |; _; X* e  Y# s! F希尔排序
% b* _0 \/ T0 H; p2 m' S5 t

3 `0 v% O" O6 ?, `# {" g8 m时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


* t6 L7 v5 e6 r# l7 [代码实现


public class Solution {
) v9 J+ J' }9 P. d4 D# u. J        public static void main(String[] args) {
$ \6 J( B8 t. d                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
" I) w  Q2 Y3 s% D* l* _                shellSort(array);
                System.out.println(Arrays.toString(array));
$ u. B% J+ i2 u        }
# ~; F5 W/ @) A' O% I

        private static void shellSort(int[] array) {
- R6 h" r7 d- f! o                int gap = array.length / 2;
! a/ B, P1 n% ]& _- o; {                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
% c7 |3 F) A3 x3 H                                int index = i - gap;
                                int temp = array;
& _, T  ^1 _/ V1 ~  M9 U- x6 z3 E                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
" r$ V8 w! x  A8 c8 k. h3 N                                        index -= gap;
                                }
//                                array[index + gap] = temp;
6 F& R7 A6 I- L, x! k) @, U                        }
                        gap /= 2;
                        System.out.println(Arrays.toString(array));
                }
* C' R* K7 m2 L$ y# Y2 m7 t! M        }
  e/ r5 Z- C  Q, A/ `
8 y6 E9 G+ g  `0 {7 X
# t" N# |; k: Y+ v( M2 J: M        private static void swap(int[] array, int i, int index) {
                int temp = array;
                array = array[index];
                array[index] = temp;
        }
. Z6 j; A+ Y8 F9 O* F* q, V- {. f}
1
2
/ y: l4 w7 M! s: n3
4
5
6
7
8
$ u) u: H3 J6 S9
10
" ^4 y- [4 h# K& f$ }11
12
13
14
15
16
! p1 s% v) `0 \7 [6 @+ z% i7 @& r17
18
19
# c0 j4 Z+ t& X+ i  v8 }+ H* h20
& g6 g& G5 h! h) }3 c/ B3 ]. U+ ?/ D8 R21
; t. C( P$ q  C  L. k1 P9 E22
23
5 W6 _# t, L; g+ t- x0 u- \3 v1 Q* l24
25
9 t5 \8 S+ L$ P: R) R3 R( o8 V26
27
28
* R& D8 r& r3 _3 z. m' ?29
& ^5 e0 E. ~" Q% \1 s30
7 P2 W7 i! A+ l选择排序
简单选择排序
从未排序的初始数组中寻找最小元素放置首位。
9 Y4 D! ]! {, m8 m从剩余元素中继续寻找最小元素，放到已排序序列的尾部
: i1 _2 X2 O; `2 @7 C; a: e遍历数组，直至结束。
时间复杂度为 O ( n 2 ) O(n^2)O(n
2
3 Y% }& P1 |/ O6 P7 q$ z ) 。


0 U% s$ T; w+ Y; u! {2 R代码实现**
- H# R9 @$ k+ n7 Y8 h

public class Solution {
2 s. k# G3 D: F/ S. c9 G9 [+ C        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
                System.out.println(Arrays.toString(array));
        }
- C* U8 j9 ~6 i6 d* c; G5 B; v0 V

% ?) m' W# r, o+ Z3 m        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
                        int index = i;
                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
                                        index = j;
                                }
' m! v) I/ Y$ ]; y* F$ e  [                        }
                        swap(array, index, i);
                }
        }
$ S$ ~- h' ~5 v% I9 {& k( q
0 ]' A- Q3 f+ ~+ o/ d6 o
        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
                array[index] = array;
9 ~8 w1 r7 `  O, R2 l4 f2 C                array = temp;
" W8 b( a$ S6 z% p/ r        }
}
& _, y/ M! ~# N& y7 e  C1
3 I& k3 Q# Z. u3 w2
3
4
5
- l# I+ E  _2 _2 M; K9 B6
/ Q- R; O, Z$ @1 S" U' j- \7
! |) b4 b) a. B* X9 w8
  }* M$ }' X/ w) w# C4 }# Q9
7 p) E. r1 k! d1 V, U4 s10
1 r* }' {9 k6 c( G3 `$ }11
! O0 L  a, Z$ G6 s; m( _9 P) m12
  U9 {& a0 P: w. m5 K13
4 U/ F: H3 ~, _+ a9 ]! S- L14
15
16
17
3 ^1 t1 q+ M) t18
! ~2 T# i) r2 e+ P- ^) f19
! R, g/ C/ D$ h5 o  T! z/ x20
" Y5 ?9 y& `& s4 Z$ A) Y21
) d6 _3 ?( a3 f; X/ D$ U/ C' e22
23
24
25
堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现**

. t+ B1 p# p; ^3 F2 O: [
public class Solution {
        // 建堆
        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
                for (int i = (n - 1) / 2; i >= 0; i--) {
5 `% b7 G% p0 [. ]  S6 f                        percolateDown(arr, i, n);
. L- q, \" x' h1 x( B                }
/ Z" X+ q: t; D# s6 W( h. O( P* Y        }
        // 插入
        private static void insertHeap(int[] array, int data, int n) {
2 B  q, B3 y/ z- r3 l6 ~                array[n] = data;
                percolatrUp(array, n);
2 l/ |. i: D, ~2 Y        }
        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
6 y7 \+ D! ?6 Q; b9 N                arr[0] = arr[n];
                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
% x' T0 ^5 p" s9 l6 k, Z        }
        // 上浮
/ m; k' j, Y5 @        private static void percolatrUp(int[] array, int n) {
0 h- J" Q& P! O! O: E. s4 Q                int data = array[n];
                int father = (n - 1) / 2;
% K, X" f8 [/ l/ y) J& J                while (data < array[father] && father >= 0) {
( B! s& K* g7 ?, @5 d; t                        array[n] = array[father];
                        array[father] = data;
                        n = father;
                        father = (n - 1) / 2;
                }
                array[father] = data;
        }
        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
4 U' W6 e% T$ ?1 Z6 c                int father = arr;
                int child = 2 * i + 1;
! `8 P+ Q* D. d, T& C) m# Y                // 遍历整个该根结点的子树
# W8 X! A( W; i7 R9 }1 B5 M                while (child <= n) {
                        // 定位左右结点小的那一个
8 |. f, ]5 R% c, c3 T2 K                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
                                child += 1;
                        }
; D" R2 V" h, Z7 B                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
                                break;
7 k& A. ?2 K8 R) G% A* H4 @                        }
4 h" z: T5 ?% J& `; |! j5 Z# a                        // 互换根结点和子结点
                        arr = arr[child];
                        arr[child] = father;
                        // 重新定位根结点和子结点
                        i = child;
# }, @# Q! @& B/ ?+ `. J                        child = i * 2 + 1;
  `" O8 I8 }- [7 ~  d                }
        }
   
        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
1 d9 T4 j0 B" X! u4 e               
6 \  }- K9 q9 Q, T                creatHeap(array, array.length - 1);
; o6 \6 J: i' w2 n7 H- M2 M                System.out.println(Arrays.toString(array));
5 \1 ?+ Z# Q- d2 R5 S               
# p" i8 Z4 V* n* g+ A( G                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
4 |1 {" H5 p1 [) b- i               
9 T* M3 z7 p! B: @9 g2 f! R                deleteHeap(array, array.length - 2);
                System.out.println(Arrays.toString(array));
               
, ~7 ~0 c' |2 C, F                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
. V0 }3 Y5 H5 j% ?0 I' g        }
}
" F8 Q% Q8 C6 |6 d. n1
3 y; f3 S5 @4 ~% X5 ^( K. \1 |9 K2
4 R( S& P5 y) t" j: F' x1 V3
4
5
6
7
3 D& N+ x* h0 d: v, F. E8
9
6 i9 A7 B7 }0 K10
11
) h8 p3 [7 m+ a' Q! L3 M9 [12
13
; z* n0 J2 H) p8 w14
- C- e" x0 H5 G; p* {3 T15
16
17
( Q8 e) E2 [( b1 `* n# D+ F18
19
, ]6 d$ }$ S4 U6 T( W20
2 T3 ~" n" l/ U, F21
% L* O! [; @: w; ?+ v, B- w$ z  f22
23
0 F1 r3 }. J1 h! Z; b24
7 [/ r) \0 C# T8 K1 L8 _4 N25
. b2 T- H' A- T& E; P26
27
28
# G: _  t5 h1 ~, w29
30
5 C) T' b+ E3 a- d: |31
32
$ m/ G5 G8 o# S! @' c. e6 |33
/ [. w1 k6 \+ b* ]4 V34
35
8 Q' `: @% N( l" `- h2 ?. z36
; d- c5 I+ i6 M8 J# i& Z9 S37
3 c( e0 l2 O, }8 X# y- c38
, R6 q  L8 R3 d4 X39
2 u, a6 G' I  Q7 a( [40
, \) H4 A4 n1 L0 b, [0 n* Z41
42
43
0 B% F' U( Z; ]44
; \' N6 w/ Q" O7 j$ \9 J$ W45
46
47
% x# j8 S) r' i( ?( {! W3 J* X48
+ \9 r- i9 @. V" F& Z49
; P+ N3 P% [3 |7 E50
51
$ z% ?" ]/ y9 e( k5 m* H52
53
54
55
56
57
58
59
! T# ]* S* i7 U: T& @$ _60
61
# Z& ^2 ?1 a: C- y  z2 P; Z0 A62
63
64
# g7 c4 z! N7 g& l7 W; z. @65
3 r) g" _- R& q8 z66
67
1 Y% X9 w' j& q+ D: H3 f68
" R, c( [, u0 S6 ]6 v1 ?8 M69
70
* z' o4 l" M- h8 [/ F" N交换排序
冒泡排序
4 ]3 L7 i7 X' t, j; b5 B( h% E依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
0 J" G" T" D) W- S3 c$ X ) 。
6 u3 |6 ?9 Z4 n; \1 H% Y

: B8 L: _( I) i2 t代码实现

$ |8 t9 z" ?" X& G! q$ A
import java.util.Arrays;
public class Solution {
- a* S0 q# q, {       
        private static void bubbleSort(int[] nums) {
5 s3 P( V3 L" C* Z0 t                // 循环次数
) g9 t" u" k; ^( T                for (int i = 0; i < nums.length - 1; i++) {
1 H- y# k+ j2 [. I7 w! k2 d                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
& E0 g1 v8 w1 z4 R" H                                if (nums[j] > nums[j + 1]) {
                                        swap(nums, j, j + 1);
# Q/ F* q9 V! G2 p* t+ E                                }
; I- B; _- \3 e5 a, D                        }
                }
, L0 l2 X: j1 t( J4 ]  T        }

5 r% k) b( @' g8 Z0 n9 ^; N
        private static void swap(int[] nums, int j, int i) {
0 @, ]9 h6 O' J                int temp = nums[j];
                nums[j] = nums;
# Q1 @6 k  C% N* ?* s  X% R2 O                nums= temp;
; q  s) F. Z, T$ C4 {  y7 u        }
  Z, i3 |% f6 W' _8 z

# ^& z' F+ |" I4 {5 h# u        public static void main(String[] args) {
* B9 p  f! x3 p0 t" b: A" g                int[] nums = { 6, 3, 8, 2, 9, 1 };
8 e2 `2 m3 }6 @5 x0 c                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
        }
}
, }' L3 U0 D4 L# V1
2
3
4
* W  L1 T: P. L/ M: D, a% x8 v5
6
7
8
9
10
: y' ?7 h% h: z; \7 a4 Y11
12
- f0 V% I$ l' w5 z0 n13
14
15
! E' X+ m3 J9 S1 v16
17
18
19
20
- l  _* f* g0 ]7 W# ~8 X" l$ }8 ]21
22
23
2 l/ {! D; O$ i- I; ^3 L24
25
% l; d6 ^6 O8 o26
27
5 X2 d) S+ a3 t) d2 ?, s快速排序
3 D$ A4 r: w  J% X+ t时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
2 p; M* K& V0 u( N9 h' e
% T, ]5 H3 j/ e, }
代码实现
# }, C) ^. x$ Q

public class Solution {
       
        // Median-of-Three Partitioning
+ C2 r  I- O' ]$ c$ F        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])
                        swap(array, left, right);
                if (array[middle] > array[left])
: Z# w! d& K2 @5 l' `* \, v8 f                        swap(array, left, middle);
               
                return array[left];
4 M! f+ @7 }; w4 I# T6 w6 }7 ?        }
* T) `. U7 n, W& b$ D/ h       
* ~, W1 ?1 f3 ~! P; f' x        public static void sort(int[] array, int left, int right) {
3 C. R' A3 Q/ A3 a% a5 ^                if (left >= right)
                        return;
% m5 o  J8 j) @  g4 X* d                int index = partition(array, left, right);
                sort(array, left, index - 1);
                sort(array, index + 1, right);
    }
       
        public static int partition(int[] array, int left, int right){
        int pivot = selectPivot(array, left, right);
        while(left < right){
            while(left < right && array[right] >= pivot){
" r8 F7 E' q6 x+ t                right--;
, Z; C' k% u; |  S            }
            if (left < right) {
                array[left++] = array[right];
            }
            while(left < right && array[left] < pivot){
                left++;
6 G0 ~- Z+ f, A7 J: c            }
            if (left < right) {
                array[right--] = array[left];
            }
% }2 ?" Q+ j2 k* s        }
4 b: [- u; ?* B; K8 @$ E            array[right] = pivot;
: d3 O+ o! F/ a: ^: `) e+ e; t        return right;
    }
6 ^) u# h. M4 r  o% C0 B) w) \

    public static void swap(int[] array, int left, int right){
9 X, C$ A9 y% X5 o  {9 |, S            int value = array[left];
            array[left] = array[right];
/ S8 ]% w2 e/ _            array[right] = value;
    }
9 y# C( R0 s- n- Y
* P. Z. j" p% o; ], [
3 L: ^( \9 ~0 P% }        public static void main(String[] args) {
- ^2 \" ?( y9 B4 }0 {* U+ O. y                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                // System.out.println(Arrays.toString(array));
                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
1 Q7 w. A0 ^5 `! H* `        }
' i1 i0 t7 e7 ?5 P9 m" A7 D}
1
2
3
4
5
- O6 e! Q+ Y+ N2 {6
7
8
9
10
11
12
7 W+ Z/ X; v5 ]; C  d. m2 z& w% a13
$ s; o0 o. E6 G6 {$ `. C6 L14
15
16
17
$ T, ?1 S% N1 ^5 d- r18
, a$ N0 n( A& o$ D3 s! ]6 b1 l19
20
4 _! m' w- {: R6 O7 T0 R+ [21
22
23
# Q/ s/ j0 X2 L; C24
25
+ i9 ^# m0 D! k5 K: r7 Z26
  p7 F0 ~5 m- b27
( `( v. ?3 E3 K) a28
29
30
31
32
33
34
35
36
& V- D, N7 O9 _' S" G/ A37
38
5 S# A* r4 t* z% r7 Q39
8 @& [* q7 X, l3 o' V+ r/ g# K40
41
42
* f' w& N% E" C2 l5 t3 A% c43
6 b. q. Q9 E9 I2 M: e! j0 s44
) X9 d2 W0 w- z- ?2 n  B, i45
46
4 ?9 ^. C4 Y% e0 h47
48
& `+ J" J+ O. Y/ _3 z! m49
50
& A, u7 o4 W: v9 l- u51
* X/ {) f' U. a52
53
( v6 t5 R; `) I54
55
56
57
归并排序
3 X) v3 |; h' U) C' u8 i) B& Y( U' x将长序列从中间分成两个子序列。
! U' w! D7 ^3 Y对这两个子序列依次继续执行重复分裂，直至不能再分。
: D) x% C; w8 P; s: O. |递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
+ }. b/ B) `, w# L; b; c

( ]0 @4 h- l* W代码实现**


public class Solution {
1 Q$ B, S+ r+ g4 }5 c) _        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
: ?, @8 ?0 V" W0 ^# r( E9 f& O4 _                int[] arr = MergeSort(array);
6 w0 H5 _& J( V; J' r                System.out.println(Arrays.toString(arr));
        }
2 ]* k% ^$ m7 H: u: v  _
' i4 U; Z3 g' `$ D1 B& S& P8 C
        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
* R# x9 v  H6 x& `                        return array;
# g" @$ {  O9 ~9 R4 j                int middle = array.length / 2;
2 v; f  l3 F& j; ^8 X, p4 y                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
, q) v# ]8 A( G4 `( T; h                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }

; K& g( Q+ V& @. i6 @, w8 Y
. e& ~9 j+ l" b2 _3 j+ h; s0 v8 }        private static int[] merge(int[] leftArray, int[] rightArray) {
- s0 b/ i8 `2 k' I: f                int[] result = new int[leftArray.length + rightArray.length];
7 N7 O' X0 O2 V. i' ?& b8 j                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
                        if (i >= leftArray.length) {
& O; x7 ]' @! J% o                                result[index] = rightArray[j++];
8 O- N: n6 ]/ [" L& [9 E                        } else if (j >= rightArray.length) {
                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
                        } else {
                                result[index] = leftArray[i++];
                        }
                }
                return result;
1 O3 N( G& t4 ?) r8 R" h) N6 K7 m        }
% K0 r2 Y% |/ t. ^$ N: P# K# ^}

( ]/ P$ f2 G( h/ a
1
2
: r/ j, m/ m  P. L" `: @3
4
) J# g1 `* `; o! g# n# @, F. w5
6
! p3 t4 b3 X% w* o0 O; ~1 Y7
4 G! h. T3 v+ X2 }. t. j- l: b; ~8
9
9 z: r8 _# ?( J/ J10
11
12
13
14
+ K3 v7 H6 Y; o) r" X15
: J: ~# f, A. T( j4 b7 x( b0 E2 ?16
17
0 K9 ?) b4 K: W; s  X3 {. ?6 K18
19
20
21
* }, [+ D9 W9 B3 K7 Q7 B22
23
24
25
, ^7 ]) g" h# s, d& E26
27
28
29
30
31
32
33
基数排序
: {, a8 y) I* B+ I; ^- _: S  }# d找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
8 g$ C/ k/ O2 s) v; F" e7 r) J时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。


代码实现**
# q5 D  a& i7 O9 c$ {* m/ F; b

2 Y' W, m9 D9 b5 ]% Z! ?. Bpublic class RadixSort {


, m1 I2 \" f% Q7 X9 P% T; J        public static void main(String[] args) {
                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
$ o. |5 V6 ^9 c9 T; {5 D# L                int[] arr = radixSort(array);
                System.out.println(Arrays.toString(arr));
        }
9 b6 y5 ]* E, S( U6 |
2 f- J8 a$ F: E
        private static int[] radixSort(int[] array) {
; x2 t+ i! i! @* `' O' J                if (array == null || array.length < 2) {
                        return array;
  i) `3 }: K  b8 \                }
                // 根据最大值找到最大位数
9 J# _4 U" y2 ~. k. s( D" I                int max = 0;
                for (int i = 0; i < array.length; i++) {
% G- _* G$ c" `                        max = Math.max(max, array);
                }
               
) r3 j6 X. P9 l2 \: N5 i% `( G                int maxDigit = 0;
                while (max != 0) {
                        max /= 10;
4 z$ u1 W) f" H1 G4 L$ E                        maxDigit++;
                }
4 X* ?7 B) p3 W  C0 _               
                // 第一维: 0~9
/ c7 @& b( W4 r8 Y) A5 A: a                int[][] radix = new int[10][array.length];
: a: D( o& G+ R                // 该位为 i 的元素个数
                int[] count = new int[10];
               
  H, x. j* h; s0 F: P2 ?6 @9 K( n                int m = 1;
! ^9 N2 x5 r0 C# S                int n = 1;
               
7 D3 @# h& ~7 `                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
; `' M+ V9 H  z6 H9 f                                int lsd = (array / n) % 10;
* A4 K5 X, q# H                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
                        }
7 d2 C. m7 F6 g0 z& s# u2 D                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
3 y& |$ Y4 x; J, q* l6 U                                                array[k++] = radix[j];
                                        }
% C; E6 v5 R: |& f# c0 a                                }
# a5 `9 f9 Y" j0 x' d                                count = 0;
% X1 N( Q6 q( H. r                        }
% z/ Y6 e+ a! C                        n *= 10;
                        m++;
4 O. z5 a% Q! n; g% G& c' ~                }
( z' Q/ C" K* I. m# [                return array;
        }
4 q; ]& z  b* I+ a- a! t* v
5 ^9 G* f& B- n, t, E2 _& e# i
}
1
2
$ _1 H) q6 t1 S- e( M' F4 Y3
4
' c3 H. E# t% t5
6
2 ?3 ^: ~/ a# M; N7 F7
: Z  h1 c* ?  Z* ^2 F* l: O0 _7 y  D8
9
, |  J+ ^6 h2 n10
; U4 W& q) {7 R& Q11
) j, k( y* T* d% |9 x& ?9 N. b12
13
5 K2 k) e! _" [8 e5 J6 ]14
15
16
3 ^* p1 t) P# M5 u9 y  I17
18
19
20
5 P# E& \  n6 C1 j21
22
8 ^. o& |3 q, ]( t7 J$ M23
24
6 n' B* B% k# u* W. z# i! _25
26
+ I- A$ @) I8 K) _- y9 q4 J27
28
29
30
31
7 E- \: e5 g2 R* V! F) h32
% F* \, y5 l% Y, T# r33
34
0 h; x8 t% T+ J) ^, Q  s35
36
; {" z3 }, E' x& X37
' a) z, [$ d) \( [! w$ k38
8 O- d" i  N& B# U39
40
41
2 L  V* ~* o, C9 i: ~" Y: D+ V2 `! g" |42
43
) h5 c+ n- J1 X44
% z) O$ I1 o! v9 p" V; r45
46
0 `) S  z1 \% j- Q& f47
1 ^& @  P9 o" a! J9 T+ Y1 q48
0 p7 X* t6 H/ N$ f% F* B6 K! K" I49
/ `- h' w3 ~( r( j* U# F; t' b50
51
$ F4 Q" i( H- G1 t3 g8 [52
53
& f, I. [7 F6 j. P5 }0 v0 Q7 z计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
* s% q2 P! w4 @# v1 U+ Q% R$ d* \统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
9 M8 A! }. f8 V( y最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。


代码实现


$ U5 o( a, u5 v# E9 `public class Solution {
+ ?/ z6 [$ C8 p2 `8 {& I( a
; p; P9 n0 s5 z! ?. h" W2 X3 ]
        public static void main(String[] args) {
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
        }
, C* G+ D( M# Z1 j6 g1 d

        private static int[] countSort(int[] array) {
                if (array.length == 0)
                        return array;
. W3 d" A( ?4 p( M               
! b' V9 s7 B  X$ ]9 P$ h                int min = array[0], max = array[0];
               
                for (int i = 0; i < array.length; i++) {
                        if (min > array) {
                                min = array;
. E; M* ~$ Z+ [, S2 k. I4 k                        }
3 c2 ]' }& Z/ ?! @" M6 y5 b                        if (max < array) {
, Z4 O3 t( N  l9 }5 X5 h8 D* I; b                                max = array;
5 G) V0 A  p2 i0 X0 @+ t0 Z                        }
1 D8 Z/ [" z4 W# o% ^6 Z/ V                }
               
; q- P) v. e6 G/ c* Z                int[] count = new int[max - min + 1];
4 g8 g+ G# b' d- I. @               
5 d- W9 X0 `$ E8 y                for (int i = 0; i < array.length; i++) {
- u* q4 O( p! g3 z" _                        count[array - min]++;
                }
               
  x0 F! F' N1 L# \$ d                int i = 0;
                int index = 0;
. {! X, P, w- E# a! t& U                while (index < array.length) {
                        if (count != 0) {
$ L. H$ d- p  B2 D  X                                array[index] = i + min;
                                count--;
                                index++;
5 F  P1 _# M0 |1 t/ z4 ^! \& k                        } else {
                                i++;
                        }
                }
6 p2 F* U  V) {! s. {                return array;
        }
! S; _; y( Y4 I7 ?1 x) ?  Z' Z       
}
1
$ T, B* W5 f+ @0 A$ p8 o0 ~, C) ~2
+ T& m% m' R2 f3
4
8 f% S+ c6 d  W5
6
3 X8 G5 v, [0 p8 K9 E/ l9 q8 t: [! D7
4 L  `: `' m  J: F8
9
10
11
" h* @" |( k. m% V5 u9 [: R, }& C12
13
14
15
$ k  T% m  H7 Y16
17
' o5 ~* P$ Y0 q+ a5 ?# B/ Y18
19
20
' ~# W" T' A; S! G0 U1 K21
22
. i# [; s/ ?) k$ a2 B, [+ b* g23
24
25
. P. t6 S5 H% ~5 E' X26
27
% ?6 ^+ E' R" h2 I# L( E0 ?% N28
- V7 N% t4 t7 c29
# h) Y1 Z6 Y4 R% K- O* L0 q3 w30
31
' P+ \0 P3 Q. |; ]) V32
9 T* l7 u- y4 v* r$ g; n  T% g. _33
34
35
$ O+ n% x! W4 o7 J$ c( J, _36
37
38
39
40
41
42
/ P" L) I& t; q# ~/ G4 ?43
44
, Y, \1 L% F7 \/ ~# c! M* X) s  k# B桶排序
————————————————
8 H9 g! O3 _3 n! H% @: m版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% S8 o& I0 G5 l; f  C7 P原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
+ B7 b$ P7 H. b' R1 O; y& Q) v