十大排序算法（Java实现）

杨利霞

: ^4 Q" S4 l9 I1 c% e十大排序算法（Java实现）

& t, V  _" _3 x% A1 D  b十大排序算法（Java实现）
5 \3 V3 R+ R" M: \排序算法框架
排序算法性质
插入排序
! @+ u4 Q+ o4 W% H/ K5 T直接插入排序
希尔排序
, H7 M& r+ U8 v8 R2 j' ?5 g! _# m选择排序
简单选择排序
堆排序
交换排序
# F+ X* \. C/ v6 g; P2 M6 J冒泡排序
8 D+ P/ O( @5 H) P3 |快速排序
7 W6 {7 Y+ G! ~% a/ @归并排序
; U% U3 k: q- W基数排序
计数排序
桶排序
6 b/ i9 e8 X, O4 ~2 C. ]3 P$ x, b- o更多文章点击 >> 这里
  [" |: @0 ^' @6 [' Q. L
/ m4 D3 Z: U) ^
7 \/ E  J- D9 _) _排序算法框架
6 K9 t: w* c0 O1 E

7 Q! o7 [) `, t1 ?4 R
6 @7 K% _) i5 B- p3 i
排序算法性质



' m8 _3 P% R% R' {: T1 l& \
插入排序
, Z+ K4 z) B/ s% \+ r! r' L3 H直接插入排序
4 J5 A6 r( N% H4 R* h; B  H! d+ w6 J从第一个元素开始，认为该元素是已排序的。
3 f1 ^/ P( s( A取出下一元素，与前面已经排好序的部分进行比较。
: f7 W) ^. \. N) }, p若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
, C" p* t* [  P0 Y5 z6 c遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
4 ]0 B. p* j  Y( g6 C9 ^" Q2
; r# A  ?" M8 o) n: S0 n- ^ ) 。


代码实现
) w3 C( Y1 k/ Q( U. a$ v

! p7 N7 H+ s+ f7 @, `public class Solution {
% R% G. S! N) M        public static void main(String[] args) {
# w0 y% ^. z0 f                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                insertSort(array);
                System.out.println(Arrays.toString(array));
        }

9 e5 r  j1 s6 H2 e+ w8 n+ c3 u& W
, D2 r; Y0 \# r. `        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
                        int index = i;
* Q5 T( w- s+ _4 g1 t- z3 \                        while(index >= 0 && array[index] > data) {
6 f) I7 [! Q/ t4 |                                array[index + 1] = array[index];
+ P4 z! @( Q: ?2 u                                index--;
                        }
! ]- N& \. B7 p- \$ f                        array[index + 1] = data;
# H# |: }* J! O# R2 h; W                }
8 k  k# {7 _: j' X) q1 o$ L" [5 g        }
}
1
2
3
4
, x% a% H5 L- A( a' j  j5
6
7
+ J5 I* y9 @; ~8
4 d  N8 Q) _/ ]) c9
2 Z! M6 q4 h7 S) X6 E5 J* u; X) `, p10
2 x5 f8 _0 b, Y: J11
12
: z5 h5 `* i2 j2 S% t13
14
$ v5 |6 E" t, S9 [7 Q! f# h% v15
16
6 ?" m# |6 r9 q: o* j. T( i17
18
) t) o& f: Y# z* z19
希尔排序


时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


4 [1 g7 i$ A; ?$ T9 r代码实现
0 ]& u7 B( n- ~# V  D( i$ ^& Q

3 t" S' [# y, _1 o+ i2 z# |public class Solution {
$ J  S4 P1 u1 F        public static void main(String[] args) {
& y7 h$ K# F: {" S- S                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
/ t# I* ^4 ~; s9 F2 T; O$ K                shellSort(array);
5 L8 B6 x5 n6 Z                System.out.println(Arrays.toString(array));
        }
# D% L1 d1 [  W/ ~8 f7 S: D

- {. u, T7 W: e% w1 @9 [        private static void shellSort(int[] array) {
                int gap = array.length / 2;
6 Y6 _5 v/ r( m  w6 m6 y6 k$ z                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
  U/ s# q* \& l1 v                                int index = i - gap;
                                int temp = array;
                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
                                        index -= gap;
7 D( L. J- d: Q( }/ {                                }
. n8 R+ C7 S4 u2 g$ y: P//                                array[index + gap] = temp;
                        }
* Y$ F! Q! u6 Y" D4 D9 b9 J7 {; Y                        gap /= 2;
                        System.out.println(Arrays.toString(array));
                }
        }
% Q5 `4 x5 w4 ^8 d. A7 C

        private static void swap(int[] array, int i, int index) {
0 I% ?; B. Z/ f4 D& N6 G8 X: V2 a                int temp = array;
( A* i& q1 }; b8 A                array = array[index];
                array[index] = temp;
        }
}
1
% Q# k7 Z" w3 d3 r- s) Y6 X$ t# j2
3
) Q) A& A4 N$ B8 u$ P4
  a3 e$ N% m/ z5
6
7
8
9
10
11
12
0 R) M+ g& C* R! M$ a9 T13
) S6 m1 O4 Q2 N) L) R& c- v14
15
; k$ l, ]2 h- N% E7 {16
: N/ [2 t  {6 N6 ]17
18
19
0 i8 I8 s  \" j20
! k9 c  Y2 N' v21
; X& z( y, h- o' j5 }( ?# S22
23
' [5 z* K; u$ d- \! m24
25
26
27
: V, L% O$ w4 S& j, i1 g/ N9 S28
29
30
' y5 d( J% Y& F! P- w) [选择排序
简单选择排序
从未排序的初始数组中寻找最小元素放置首位。
6 E% P  ]* T5 o' J' z从剩余元素中继续寻找最小元素，放到已排序序列的尾部
$ G9 z( g0 I! B遍历数组，直至结束。
' K6 d# d4 g' W+ B! T6 r5 {时间复杂度为 O ( n 2 ) O(n^2)O(n
. M) p: R( _, ^% p$ x5 H/ n7 m# V2
) 。
7 Z/ f2 d3 u) \, Q, M
. E3 g$ C& j: a7 S
& s$ k" c+ B$ u5 a$ u9 `1 s代码实现**
6 F% V" \- g4 C

public class Solution {
$ b6 n4 y3 c7 ^% J. [        public static void main(String[] args) {
4 W6 R+ t: d; h  J1 K$ q# V9 d                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
8 @8 `8 O7 s7 ~1 R                System.out.println(Arrays.toString(array));
0 H: |5 f2 ?9 @' A1 ^9 R, M% J        }

  N/ |. b4 O3 a; b( m- W, {
3 q" o$ e6 J6 L7 `& x9 o/ r        private static void selectionSort(int[] array) {
2 m* i8 K& R, c' D( e7 V. H" v                for (int i = 0; i < array.length; i++) {
2 m! W" q1 V  P  d' M/ Z' |7 G                        int index = i;
- ~4 B' N( a$ |1 {- B6 n- j                        for (int j = i; j < array.length; j++) {
- g  o1 M' [' o: O; k8 q6 P1 r                                if (array[j] < array[index]) {
2 w" x# S  Y4 f                                        index = j;
% y! B1 q8 P8 Y7 }                                }
                        }
                        swap(array, index, i);
                }
! M' N* Q% C- }; v& Z! L9 D        }
" J! V: |) y; [8 r

4 x8 o, K4 K# M% ^' n        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
% [' L8 O- H/ Q/ W& W  u6 z4 A                array[index] = array;
& S; w, x, S3 f                array = temp;
0 J3 c; u9 G) B5 K  ?9 y- [' r) c        }
}
1
2
$ d2 M& B1 q2 r0 e3
4
5
+ O: R# Q- F: L% d6
7
, f# [, A( X$ T$ Y* E1 ?  J8
" d  b5 Q# T# H9
10
3 e# [2 F  c" G( C2 |' ?11
12
13
6 |5 x3 E, D5 \. ]% H' A5 Q14
# R* S* U' h/ i, Y" ~) A15
16
+ |3 Z+ B( V5 F$ S( I. Q$ h17
2 d, {0 F1 N+ H# W5 C4 H18
19
20
5 G- T% L- Z4 D2 v9 L( C, F9 e1 N1 J0 C21
& k% @0 O" y+ H* U! Q3 ^+ ~7 `* N  N) g22
23
) M: V& f2 q+ ?1 _# O24
25
堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现**
# G! d' U3 G/ i

( L+ |  \: J- ?% i8 @5 d2 Ppublic class Solution {
* ^/ o8 E5 z- J6 P1 |0 y  v' ~        // 建堆
        public static void creatHeap(int[] arr, int n) {
4 \) `& u4 ?' Z( n2 i" e8 b                // 因为数组是从0开始的
5 f( l/ ?, C' H% u$ a! Y0 n                for (int i = (n - 1) / 2; i >= 0; i--) {
. Y9 x6 H+ G2 ^/ R3 k* r                        percolateDown(arr, i, n);
( C; M: |5 G# N9 O                }
        }
, k+ @1 f6 n2 U7 s% R5 G. m        // 插入
        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
$ j1 [1 m" M9 `- a) ]( D( {                percolatrUp(array, n);
        }
% c0 }. b- |2 p! A' o        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
& c1 Q) z. o5 k% w( m                arr[0] = arr[n];
- D9 _% L% r9 n+ f: S& _1 I9 Q                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
        }
9 e! i0 X9 ?1 e        // 上浮
4 m% `4 Z: U( c+ S9 Y; Y        private static void percolatrUp(int[] array, int n) {
                int data = array[n];
; W+ V, b, q. \" o* ^" W4 V                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
7 ?2 ^4 @4 q- P# n/ N, i' Z: m                        array[father] = data;
) g$ _- f) _. F' F) {                        n = father;
' y8 S) M# T8 u! ~' X                        father = (n - 1) / 2;
' L5 ^# i9 V" B) V# Y+ [4 P                }
                array[father] = data;
        }
        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
  f; l& l$ y( m+ P                int child = 2 * i + 1;
/ B2 F, a* w) e# I4 f* q& B+ N                // 遍历整个该根结点的子树
                while (child <= n) {
                        // 定位左右结点小的那一个
                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
$ {4 {& e" N. \+ ?$ W( [                                child += 1;
                        }
                        // 若根结点比子结点小，说明已经是个小堆
9 i4 D& c5 F, F% t8 }7 D2 Y                        if (father < arr[child]) {
2 h  z! a8 _$ V* _* K                                break;
5 i0 R" Y. c( E/ s2 C9 _  y3 J                        }
. v( x4 n* r* ^                        // 互换根结点和子结点
. g5 F0 l- w3 M7 z9 Y                        arr = arr[child];
                        arr[child] = father;
                        // 重新定位根结点和子结点
                        i = child;
                        child = i * 2 + 1;
6 Y# C' ]/ i9 `# J* D$ J                }
' e6 O! D" U, n' T8 U0 H! g        }
  @6 U0 `$ f" L0 v   
7 A! F" j' X  D; F6 F4 P* E2 }        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
) [4 ~5 Q$ I4 j" z% m0 n               
3 O: b  j; [% {% Y' Q% a2 p/ S. \8 o                creatHeap(array, array.length - 1);
6 F; I& b4 I0 ]: P                System.out.println(Arrays.toString(array));
$ ~- q- p6 r7 Y               
" l/ {: a% p" k3 o; R( h: K. }+ L                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
+ h& Y/ v0 F) j' x, D4 r                deleteHeap(array, array.length - 2);
                System.out.println(Arrays.toString(array));
               
                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
7 N# R( ]7 D* v3 S* l, z5 |4 @/ \        }
}
! r* [) X/ U; q1
7 e) E  M" i* R9 [. u2
" [% i. e+ X1 F* n3
4
5
! d, L7 Y" S: m! [# e. f2 }3 x2 a& p! _$ _6
# p0 o+ j2 G% s9 N1 ^% X7
0 ?- |' I. D" h- @7 ~8
9
10
11
12
13
14
. o! E. i/ z8 ~. y$ \+ P15
16
0 A) I" L* \) i* S17
18
* y& z/ [- ^: O% O5 i7 a19
7 B3 Y# ~3 @4 l* n3 }20
21
' m8 W, i  r; x22
23
0 v5 E5 x, ]' }$ r% M4 y24
25
! l2 e; p0 }" F$ z2 E26
9 W9 N8 @- z) t' h9 c27
28
8 P, J7 p7 k  n) j& [- B29
30
' L: D4 z' j# |1 x! d; F; p) D( ]31
" }* j1 z+ S; U& p' Q9 s32
33
34
8 N0 J. R2 y  K35
36
37
38
1 w1 r: o1 V& r/ Y39
$ r0 K- N$ {8 s7 M4 R40
41
42
43
44
5 h# q5 u$ H% V9 i& L* J  s6 X% b& F7 T45
46
47
# [/ ~" S) C. Y; r/ J48
49
50
  @/ j3 i' H4 s8 w4 Y. N" |, _51
52
53
54
55
) x( d, i* N3 l' G" ~9 g0 k56
57
# v) b7 y* ]0 M7 e/ D% O' K) q1 k58
59
60
61
8 I9 G& k/ k( s/ h# T62
63
64
( }# ^; b& D; o, J, B; i+ g65
* s* i# [* n" q66
67
68
69
70
% k$ W1 u$ {/ {0 r交换排序
冒泡排序
& l6 o; d, E2 A( o依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。
( h+ y# B. f) q2 o' ~) j& B

代码实现


import java.util.Arrays;
public class Solution {
% N9 I8 x6 A1 J+ v) ]       
4 i5 T* R! e! ^6 n/ u4 S- |% f3 X: n        private static void bubbleSort(int[] nums) {
                // 循环次数
                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
                                if (nums[j] > nums[j + 1]) {
                                        swap(nums, j, j + 1);
( A0 ?% O! ~1 {5 j                                }
6 ]3 i5 u. ?0 `& t9 I" ^0 Y                        }
! P8 ~6 |  I) ~, ^                }
4 K8 ?7 ~3 i' N3 E        }


        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
! {% C$ S5 R( }' \) N6 l2 q                nums[j] = nums;
                nums= temp;
1 I/ f. P- U9 U: c" O- k        }
( s3 s/ b7 P; t. w0 h
9 i7 V; g' u9 @% k; V
% }; `5 K2 g2 s  m; Y' U        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
$ Y* \/ B# P0 w4 l1 q8 A5 O9 u5 X! V' H6 V                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
, w; G9 [: d( P+ E9 A" Z- i        }
}
1 j$ [2 Q( r: k* ^) K4 X; d9 O1
2
  W) X: F$ T: F- l! J3
8 N& {$ n2 K+ r% z: w9 W5 l4
; f2 D* y) @9 Y7 G6 x6 |5 q5 z5
, u- {( ~  |; F4 [3 }6
, x7 k' b; s) V% a2 H* |7
8
9
& B7 h7 W9 ~( X% w0 b' v) g10
11
12
13
14
) D& F9 F* ]0 d6 ^. Z+ O/ U15
16
0 e) ^' k/ u' [: g17
18
19
- e. H! `4 x3 g8 x7 ^20
21
5 s$ [: h# t9 S22
; i6 Q5 F, S" W9 u: ]23
24
25
$ X6 h9 P# v0 C/ T. c26
3 j  J4 l9 Y( i! o) Y4 V27
快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


  Z! p% ~$ z/ p0 x! z' S# b代码实现
( O( C6 U2 F! a7 t$ k4 f2 [3 }

public class Solution {
       
        // Median-of-Three Partitioning
/ f" m" J+ a- J, D        public static int selectPivot(int[] array, int left, int right) {
                int middle = (left + right) / 2;
2 Z7 q* w/ v. g1 Y               
+ i( _: \% w2 b9 u- p                if (array[middle] > array[right])
                        swap(array, middle, left);
                if (array[left] > array[right])
$ }2 j# J5 t  i1 @6 z                        swap(array, left, right);
                if (array[middle] > array[left])
% m  V9 y( [9 O7 g& L                        swap(array, left, middle);
7 ?6 }5 Z0 I6 L+ D  m6 }               
                return array[left];
        }
       
        public static void sort(int[] array, int left, int right) {
                if (left >= right)
+ W  u+ w* a' m) U: M+ ?2 G/ P                        return;
                int index = partition(array, left, right);
                sort(array, left, index - 1);
, S4 Z2 h& \& F                sort(array, index + 1, right);
0 j% ]: B. j) Q3 i    }
       
0 Z6 V+ l' }; N8 _; S        public static int partition(int[] array, int left, int right){
        int pivot = selectPivot(array, left, right);
/ K) j; n9 z" ~7 N        while(left < right){
            while(left < right && array[right] >= pivot){
4 Z9 O0 l  |9 W& V- l                right--;
: \6 A+ @) K) g% v! R0 j9 l, I* d! A            }
            if (left < right) {
8 g0 l8 n' U2 d% t( s                array[left++] = array[right];
7 [' |5 H( v# J; V: E            }
            while(left < right && array[left] < pivot){
; {  g; D# ^% h6 u( X4 z                left++;
5 A. r: S5 B; B; A' r            }
/ M2 \" D7 U( i" S  R, T& T            if (left < right) {
                array[right--] = array[left];
' c2 W; c1 P  ?2 _& ^            }
        }
            array[right] = pivot;
        return right;
) W+ i- p6 q2 d0 o3 G6 Q% Y3 w    }


    public static void swap(int[] array, int left, int right){
            int value = array[left];
            array[left] = array[right];
* d* l% p- v  q% p" ~            array[right] = value;
    }
0 O. Q( v) n1 o2 P6 @6 j/ R
! `: D# n6 p1 `/ y6 R7 n
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
4 s* R5 L5 u9 Q                // System.out.println(Arrays.toString(array));
                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
, n2 i5 ~# J; J& Q$ u1 j+ n& _; X        }
}
/ V! @: H# `8 _6 b) a% S1
. T) l" k3 D2 C( x0 x$ o, z( D2
5 ?% c1 m* o8 C3
% Q+ ^3 x! ~' _. s( `: V4
) {4 ^6 p1 S2 K& G( E6 Z5
6
7
8
9
10
11
12
13
5 c/ H/ Q! p0 r, b, ?14
. |; {& a/ y7 C15
16
7 R( {" s6 |- M2 f6 s% _" w0 d17
2 O( L6 ^" Z5 G18
19
: n; ~) o! f& u20
21
2 S% a$ H8 e9 @6 Z9 i22
  }  P5 t5 y/ T/ t! K3 G23
24
25
$ C3 T! P4 Z) c& G7 Z& ~26
27
28
0 `% \- K/ O9 b" O29
30
31
32
33
34
/ |. ?! T: k8 \! w1 [7 O35
4 a4 y9 S# A8 H36
. Q. X* ?3 m* o6 m' I* T/ \: V37
  {/ q  L; B9 t# ~38
0 p, C6 k2 f8 S9 ^  e39
40
8 {  r0 {& R/ w* ~! ^% y/ ?& b41
42
+ n1 i4 u7 n) L/ \43
% Y/ g/ w4 w/ D7 ?/ l- [44
45
. ?8 F% c+ F! [- U46
# M9 ^2 X3 G2 F47
48
49
& r; z" _; }3 o( E" t  S% r  x" ?50
51
1 d* y/ ^# [3 t52
7 X& f! Q1 E9 {( I. x53
54
55
) M" F4 T/ g$ A8 h, C7 l56
57
归并排序
  t  v* S" D) |! B2 `4 @+ W& x) A9 F将长序列从中间分成两个子序列。
对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

) ^1 I  b' U4 c6 D0 \. V) X
代码实现**

1 Z- G8 D6 u8 a5 f
  ~, ^1 r+ H  D8 o% a0 bpublic class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
, H- Q7 Y4 ~2 d  S% r5 s                int[] arr = MergeSort(array);
                System.out.println(Arrays.toString(arr));
3 @. F& q% K+ `$ T' ^* W        }
0 E- L, f9 i5 l) [8 ~* Z" p* v

        private static int[] MergeSort(int[] array) {
1 x2 m! e2 s" F  v" N6 w                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);
9 v' k% J9 o0 c* d) d# m. d% S6 x9 \                return merge(MergeSort(leftArray), MergeSort(rightArray));
2 w6 l5 _' u+ _: S' E! i        }

2 y( P! A( o2 K- y" s' c, h8 H
        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++) {
                        if (i >= leftArray.length) {
0 W5 [& C# P( U' z                                result[index] = rightArray[j++];
                        } else if (j >= rightArray.length) {
  [7 L* r  w. E) v4 L                                result[index] = leftArray[i++];
. ~# a8 `, ]& k3 |# h0 I                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
6 [/ u0 X, @: f9 ~# n+ q                        } else {
                                result[index] = leftArray[i++];
                        }
" N% R  n$ F% [: T' ^& P                }
                return result;
/ c, t) A  ^0 A' s8 b* O+ c2 J1 l        }
: x: n" a3 A# E5 U) D! y}
' c: M" D$ j4 U2 W

1 A$ R2 y$ U  V- f1 @4 o: w1
0 R6 j7 B( i2 E6 B, }+ h8 j: P! |2
3
/ s# o" E' \) i0 g4
5
6
: c7 D$ \; r' |( l7
0 w. a; D/ s# p, u; _! p4 ~8
' P) G6 N" I; w: b1 J9 U" z9
3 V' b8 s0 g& t! {10
11
4 H3 ~" X, k' Y0 W; m12
1 U1 {9 P0 e7 N13
14
15
16
) b; P" N1 r( L$ }% T6 d17
18
$ w0 }! C# s" F9 l. f19
0 z: a* V' E+ M20
21
22
# z+ `9 w- ~, R5 H& i8 s23
/ J1 m' }6 _" a$ B+ [# C7 i# A24
6 v4 \% d2 u7 J7 H25
26
6 ?+ L+ p9 Y+ J4 M; Q) n27
28
29
6 ], E3 {" I+ A+ V8 w; l30
31
) A8 m- s- H' R  B5 K32
33
" P; I. ?1 ^: k. d基数排序
% P3 h( I( O: r, U: [1 _9 l找到数组中最大的数，确定最多一共有几位数。
6 y4 ?; d7 B  R按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
! D+ J3 q: @9 a* q( s1 A. W. c9 F
9 x& H" \! J/ e# R5 I/ o; P! D1 K& ?
代码实现**

7 A" C8 V+ [( l, ~: c% z7 q2 P
/ t! k5 t3 Q* E: r3 Q: ^public class RadixSort {

& }. P2 q3 Z4 w8 j9 i
        public static void main(String[] args) {
5 o! y! K) c* D  V( m9 ~                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
3 a, ^( N8 {6 y                int[] arr = radixSort(array);
                System.out.println(Arrays.toString(arr));
        }


        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
! p" Y# V; g  Z/ z; y8 @( @                        return array;
                }
9 T" ^- L# }' x( V0 V: w                // 根据最大值找到最大位数
) r* ~1 `: M2 c2 B                int max = 0;
2 s+ @2 @+ f0 ^$ i4 z& V                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
                }
) f) s2 h) y6 `* P0 e3 T               
                int maxDigit = 0;
                while (max != 0) {
4 a+ y# x/ M6 R2 h2 C                        max /= 10;
                        maxDigit++;
                }
, y! R  j& B% l8 `, J; Y) m               
                // 第一维: 0~9
& F9 p# ?' ?! r. ~' M' E2 F                int[][] radix = new int[10][array.length];
2 v; d/ F# i+ B9 l1 F" v, ~9 |                // 该位为 i 的元素个数
                int[] count = new int[10];
4 r( `( K1 T" C: W! V$ |               
- F" c0 f7 L9 z                int m = 1;
, I2 j' e( ^: a# z5 g                int n = 1;
% b# U5 r/ q. x               
; N: B3 [2 E7 ?" J6 p7 W" ]$ @& Y                while (m <= maxDigit) {
  L7 H& P8 d% `7 ]) k; t) {/ x- u                        for (int i = 0; i < array.length; i++) {
' ^1 s) F6 P& L4 I                                int lsd = (array / n) % 10;
" Q# ~6 [2 a4 {) T5 B                                radix[lsd][count[lsd]] = array;
6 m! g0 b# V$ K2 I+ s; j                                count[lsd]++;
# o* r  U* @6 x& ~# a5 l                        }
                        for (int i = 0, k = 0; i < 10; i++) {
2 o/ D1 x+ F  {                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
4 x! m$ S) w) w0 w                                        }
                                }
                                count = 0;
# R) V1 ^8 ]/ ^. Q+ F                        }
( F; I6 W: Z6 G4 z. Z) z, r                        n *= 10;
                        m++;
5 C( e  [$ G  a4 q9 z! u                }
                return array;
$ z) b6 A# L$ `4 V( q        }

7 n! w0 m* d) v; X0 Z
5 Q+ G/ t! e' k1 g  u0 U4 T% S+ T}
1
2 G" f, w, C% Z* l* j; n7 ~2
! l2 I, C' D# u8 G  q: J# t, J& W3 a3
4
$ k$ H+ K; j6 a6 V5
6
7
9 g: ?) \3 t5 d8
9
& t7 O" J2 {: Q: Y: `9 b$ `10
11
$ c, x3 t& V) c1 Y12
13
14
15
16
17
18
  ~$ }. e, [9 u4 U19
20
+ N) N; \9 Y+ k21
22
0 h! W9 u: y. A23
24
- o( E  S$ u4 F" X/ a# Z4 {$ x25
3 c# k3 l$ x% _: L9 E3 N26
27
: _$ \* s) }6 N28
3 e& j# ?1 i( D; d' v29
& M( L) u; O, P* J4 y1 u30
31
32
$ Z1 F6 V+ f/ L, ?% |6 `6 z33
34
" U: n3 D# b, a/ ^35
7 N1 E( e$ c9 L4 X  r36
37
* k; `+ ]" w- V5 v0 y38
39
40
41
8 h* x. V7 q: s5 M5 d( ^42
43
44
45
2 A3 s5 h6 h0 ]+ }, P- }. X0 a46
47
48
. K0 ?5 @1 F( T) x* w49
50
. b) ?$ {8 w2 p3 N5 d' s51
52
& W4 I3 e7 j  ?( M' H53
计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
. h9 @/ x4 E" _时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
& H; q! k) @. ~

# z% r- x& g$ K( U- s; d+ U4 Y# V代码实现

- B3 Z6 ]% G) v
public class Solution {
9 F( L2 y/ H- b# a2 _( p8 C- o
3 z) S- b8 V7 F# ~2 V
        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));
9 f5 x' C6 l$ g, L  A$ H  r        }

: W" C# N! b7 l# f2 T
        private static int[] countSort(int[] array) {
                if (array.length == 0)
% M9 K  l! ~; k# S3 F                        return array;
5 R7 ~" f* E, X2 A5 A7 p- A               
9 e; c5 U. N# v! J3 z' Q                int min = array[0], max = array[0];
               
                for (int i = 0; i < array.length; i++) {
                        if (min > array) {
                                min = array;
0 w/ b- q0 C6 T  P' I5 @3 J                        }
                        if (max < array) {
                                max = array;
                        }
/ V, E7 I2 G4 S) U' `# l9 a+ o                }
               
                int[] count = new int[max - min + 1];
               
                for (int i = 0; i < array.length; i++) {
9 g" ?6 [5 U) ~( E                        count[array - min]++;
                }
               
                int i = 0;
                int index = 0;
                while (index < array.length) {
$ s' R0 @9 t% ~3 }" ?                        if (count != 0) {
: A! ~. ~! d4 c" `' t4 \' M                                array[index] = i + min;
                                count--;
                                index++;
/ _$ L6 [7 T% _  L$ Y" Y: K5 k' l                        } else {
                                i++;
- n) }: j  S, d3 k2 U8 ~                        }
. ]% K* t/ J8 E8 Q9 l                }
* h9 _0 J: n) \0 U' U" N& \& I                return array;
        }
4 S$ H. |( q/ X9 u- v  F       
}
+ p5 J$ \0 D& G, k8 @1 K1
7 O9 i# J. z! S$ X$ F4 I2
3
+ z- W$ j  g  N, i8 h9 j0 L" o4
7 s, ?2 W. H$ Y0 K5
; g3 P4 r. i! q  f: S6
7
8
9
10
. S. U+ ]) h9 N8 H11
4 _, I. |% b# g" J& m1 n+ O12
13
14
, z1 z8 r% l' S15
: P- A) B0 n+ Q, P  U* F16
17
8 z3 Y8 N+ V* t18
& @" q8 t3 x) v. {/ ~: `2 }) c( e19
/ Y7 [9 F+ e- ?% f) @20
. F, o; _4 g+ B( g8 {21
8 k3 H" v. m; z. M22
23
24
25
26
27
1 V% W; p& R1 y6 D4 X28
/ C, f% g0 l# e29
9 b1 r1 S, H& y) I0 B# b5 Y30
! a( k% |+ N8 T% q# x$ J( p' _31
32
; V4 L4 N6 l, I1 m8 K33
# j. k/ z6 S& f: |4 Z* z& ]34
( ]% i4 @2 L$ K  f& D0 p6 H35
36
37
38
; y% f) L' m: r) J+ N8 a4 p" p39
40
41
42
43
' J, ^. D1 B- m+ i# l7 W, E44
: ?5 f; b  I! O( Q5 H7 J4 R桶排序
; ~+ w% A7 R- t' w————————————————
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 S8 r3 V6 Q$ n- |原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
: W6 c/ W9 u  s% T
) q& P% t4 p" v' Q' J! z5 u  C: h/ e