十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）
! ^/ {  P9 s/ x7 v
- i: ~) D- F2 L. z( y& ?十大排序算法（Java实现）
# P* }4 z+ G7 n: D3 m9 ?( z6 q排序算法框架
排序算法性质
插入排序
直接插入排序
希尔排序
选择排序
1 F+ h* @$ Q9 l, N5 j& @简单选择排序
: Z5 ^& K0 U6 A' x) J7 ~% p2 M堆排序
" ?6 Z& @. G7 [8 L: d) ?交换排序
冒泡排序
快速排序
归并排序
( ]. y- d+ R) Z5 ~( n基数排序
% j+ W  U. n8 A$ z计数排序
* ]* Z4 Q& X$ M) j3 \0 e桶排序
$ `# I; ~  {- I+ Q2 l8 t: j更多文章点击 >> 这里


0 o- m/ ~2 E. [; U) I排序算法框架
# Y( y/ S% K- P) j$ s

# I! D. @7 i/ K! q9 b
6 A* o- L+ k8 z! Y& u
' J1 L) o; b3 ?! q' b* c排序算法性质

! P) Y! h6 M" `& K# ~; K
, @/ e& g: b4 ^" i, f0 e- N. m

插入排序
+ P5 b( x/ q1 S2 H2 ?( Y, _直接插入排序
从第一个元素开始，认为该元素是已排序的。
取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
' p; g% C' b6 a3 S$ Y" W最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
, U1 ?$ m$ c6 D2 o6 b2
6 a# ~4 [9 r# k ) 。

9 s0 j+ y0 m, N6 P: _  I
代码实现


public class Solution {
* }, Z5 c# I' a& Y7 g1 c1 N        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
  F' A7 ^0 G! N7 b+ b4 r  H                insertSort(array);
: B& f6 N! h; O4 ?5 N. h8 g                System.out.println(Arrays.toString(array));
        }
3 s4 S$ ]% \- G2 K
: Y6 S6 l# H% J8 K% X) ?
        private static void insertSort(int[] array) {
. c( x$ L. [/ H# D* s, H                for (int i = 0; i < array.length - 1; i++) {
, D0 X% g# q: k: R- {                        int data = array[i + 1];
                        int index = i;
                        while(index >= 0 && array[index] > data) {
2 o, o; v; J) m2 M                                array[index + 1] = array[index];
6 t) ^" |1 f# S8 P5 m: M                                index--;
                        }
                        array[index + 1] = data;
                }
        }
8 A: Q0 `# Z& h0 w2 a) ]  f}
2 u( d7 _4 H4 O" I1
2
6 g0 \9 q& l, p/ Z3
4
: u6 N8 L0 H, E2 b0 e5
6
7
8
9
10
2 v( v2 f, ~" C0 I11
" [( z1 S, {3 E* U5 X1 q3 P. |12
! X; j. h5 O5 s' i9 A4 t0 y" q13
14
15
: |9 C. f3 b, Z: |3 U16
" s& @" O* j' p1 T+ C; I17
8 p& Q4 f& R* {2 |/ ^/ d/ V5 Y18
! a2 I4 x* O$ P9 _* A$ n19
希尔排序

- @/ m" y. n7 T3 V& ?( Q
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


5 F' {: Y/ Q$ {8 z$ e, b2 Z代码实现

5 N1 ~/ t/ s% S% k. X; O
/ I& t+ v2 h/ M. h5 [8 dpublic class Solution {
        public static void main(String[] args) {
1 H" l  J& l% e( ?1 Z. M. N, u                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
$ P0 h9 X( n7 V) c/ P                shellSort(array);
                System.out.println(Arrays.toString(array));
        }
# I! _: K& U- E9 x% g+ ]- O
% _: B6 ?( W0 I) J% c1 R/ x; @
% y' H4 G) o2 W5 b/ Y        private static void shellSort(int[] array) {
8 v- X3 a6 S* W                int gap = array.length / 2;
                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
                                int index = i - gap;
1 }. \% {' N- P5 G                                int temp = array;
6 q# Y0 D8 G9 Q; J$ ]                                while (index >= 0 && array[index] > temp) {
8 d/ V5 [, z$ [) E) i6 N                                        swap(array, index, index + gap);
                                        index -= gap;
                                }
# K6 z4 [. G6 s5 S% D0 O9 q//                                array[index + gap] = temp;
                        }
- b5 h2 G' B- m* B1 l                        gap /= 2;
+ ?2 P' @% P4 C: T                        System.out.println(Arrays.toString(array));
  S9 L9 k9 g. x# v, L( d                }
        }
/ a( k1 r7 ^; N/ d- t! J
, n0 X! u4 @% I% Q
0 G) w. v( Z0 ?/ @- J# T( ~        private static void swap(int[] array, int i, int index) {
                int temp = array;
  W, _2 t) P# |: `* N; ]: G                array = array[index];
                array[index] = temp;
9 F+ V0 P1 T9 N* i5 a3 s4 K        }
" A9 O) V5 q& T/ |6 [# G}
$ [, [/ E- E2 r) w4 e1
8 W! e8 F$ `4 x% J! F9 F% Q. w2
' u/ p1 j+ U/ X$ R5 E' L3
* y4 h9 h1 P! s* Y& v2 M0 x- e& I4
5
7 ?% L: ~5 o3 T; j6 K6
7
& ~3 o' L/ ~8 a8
: d1 ~9 @8 Y" |9 K9
10
11
- W5 N% Y( c5 |1 m6 H12
5 J; `( [% V# ^- K; g13
14
15
6 Z0 C& s: ?3 m- k2 C8 n; ^16
17
18
2 T! J, D$ C9 I9 L" v19
20
21
22
23
+ G& q8 x* x. l3 z- b24
& T; O$ x8 L8 h8 M7 d# e3 P25
# x* e4 V2 e# H0 F7 r26
6 V3 C! X" `& O- s5 R* J5 I27
28
29
30
选择排序
简单选择排序
7 G$ v6 p. B7 K7 |0 T从未排序的初始数组中寻找最小元素放置首位。
; [$ B% m) g: ]( I从剩余元素中继续寻找最小元素，放到已排序序列的尾部
) B+ J- n. a+ E遍历数组，直至结束。
时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。

* u$ U+ {5 ]2 w8 N4 g* I
% O$ F# Q! B) ]' l代码实现**
" M1 M! K" i2 F' N
" J. C" g3 v! D
public class Solution {
. B" _6 u( s# ~! P0 B% L  j        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
* ^) e) l+ R; i3 i3 h                selectionSort(array);
) G* @5 h, s6 {& @. d                System.out.println(Arrays.toString(array));
2 ]+ C3 _8 `3 g. x        }

# |: N' b" ^0 Y2 J$ p, d! j
) v/ z* r: j- B  C, t" |$ `4 y        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
                        int index = i;
1 ^; D, t6 s4 N) q( t: M                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
                                        index = j;
% {# V. ^+ o) a( f7 T                                }
* j/ |! }2 G) r& I+ Z5 |& Q0 C                        }
                        swap(array, index, i);
5 Q6 ?  Q  {, e& l  E                }
2 ~+ e  m1 T% p- x8 y" V        }

. x! \# h& O1 I8 T8 {6 O& z2 G5 p1 a
  Q% H4 D; }9 q( w8 I( n: [        private static void swap(int[] array, int index, int i) {
8 U" `  ?# F6 m$ w                int temp = array[index];
                array[index] = array;
, @. A2 Q" B8 ]                array = temp;
        }
}
" D8 N2 f5 t6 J) ]1
2
0 H1 K3 h' ?" P6 z3
4
" u- ]3 R' d1 Q9 R, |' R5
6
! a: Z# u2 y/ T, f& r7
8
2 b! _7 y: ]# Y. K8 K* \9
10
11
2 }2 d1 E/ V( z/ }7 S: J/ X12
13
- N* K! ^. ?3 L! w14
15
16
17
18
19
5 A4 t% Q0 K4 J* [20
21
5 G7 A- e; Q5 Y+ l% I( T22
23
24
25
堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
5 z/ V* K$ ~" ]
5 T9 c* Z6 C! [" q7 P5 q
: T5 @; v. D/ X& h9 H7 h' C代码实现**

2 L7 |! d" a% [4 k
public class Solution {
        // 建堆
$ z" O& a: K0 T/ R$ Z$ D" l' E        public static void creatHeap(int[] arr, int n) {
0 i! v2 f- w9 W& A& M                // 因为数组是从0开始的
                for (int i = (n - 1) / 2; i >= 0; i--) {
                        percolateDown(arr, i, n);
                }
2 w+ j/ c% V) z) L' E; z        }
        // 插入
' Q' k& \( X" x        private static void insertHeap(int[] array, int data, int n) {
$ y1 V  x. t# o, v                array[n] = data;
: M) l$ s' I# _. Q; b. M/ N                percolatrUp(array, n);
        }
3 z. H8 |0 C% ]# N/ ~* u5 z        // 删除栈顶元素
4 J! U2 ^$ D# V* O3 k5 N        private static void deleteHeap(int[] arr, int n) {
                arr[0] = arr[n];
                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
! S( |) O" @& n6 m        }
        // 上浮
        private static void percolatrUp(int[] array, int n) {
( U( U: A% r; p. D3 v                int data = array[n];
4 f1 ^4 ~9 K1 E$ p; c& o- p+ N" n+ F                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
9 |1 o* {- `1 {9 n  {0 Q/ |                        array[n] = array[father];
                        array[father] = data;
) H7 ]. I% \& `5 T; `. s" Y                        n = father;
$ Z- j9 n3 |8 V! `) R4 p6 W1 k                        father = (n - 1) / 2;
7 |3 w8 ]8 K8 @$ o7 w8 C5 F# _                }
$ J  T! F; p) r; ^                array[father] = data;
( T0 p/ z; W- r# J  {1 O8 @        }
. c- m. r) U  C/ z# ^        // 下滤
. v! a0 d# j/ N, v" B        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
5 R0 ~) W# p, O2 x+ {- X$ b* J% U                int child = 2 * i + 1;
                // 遍历整个该根结点的子树
                while (child <= n) {
) Q; x1 p! l/ q  g, D  g# @9 ~                        // 定位左右结点小的那一个
7 d" y. ~' n% Z* O9 q% H: K) B                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
  k& x! d" [1 n4 v4 x2 Q                                child += 1;
                        }
7 H) o* L7 M* A* q5 F5 W                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
                                break;
                        }
                        // 互换根结点和子结点
                        arr = arr[child];
                        arr[child] = father;
3 _$ r- g/ o* Q( |% T- O$ L2 ^0 y                        // 重新定位根结点和子结点
                        i = child;
; r4 ]6 n2 p2 j4 J3 i6 _' v                        child = i * 2 + 1;
+ U5 c' p" U9 s; N                }
0 `& R8 _9 H4 A        }
   
        public static void main(String[] args) {
- D8 r/ o  E: i# R+ ~: T+ E                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
, C6 s, I" e+ M' i                deleteHeap(array, array.length - 1);
) C, {( T( L) G6 s8 r                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 2);
8 C( ]$ U+ i2 h# i  B: g                System.out.println(Arrays.toString(array));
8 ^& W) \8 x. J  B7 w- r* C               
0 y8 r  a7 b2 j1 e- O                insertHeap(array, 3, array.length - 2);
1 l, K+ w9 }& q! P* ?                System.out.println(Arrays.toString(array));
# G* |: J  m) E        }
}
1
2
3
4
5
& [9 j* S7 Z1 @6
3 c$ c% i( w2 f2 y% [1 [- x1 _; l: X4 s7
6 `9 a; V) C1 h" e8
' \- R8 e2 @4 }# ~0 F9
10
- Z  t3 F2 Y5 ^; C! |( J11
8 g& Y) v5 s4 P" _1 E* F! |12
6 o& B( l% O: {+ p13
/ a3 A" E1 N! _8 k1 G! L1 c8 Y14
15
16
17
  S9 g9 U% [) N2 D5 z18
19
20
21
& }0 d; @2 x) v$ k+ j$ _22
8 ]4 ~0 ^. Y. J+ @' w$ X23
' L& m7 n5 z) x- z% W24
25
26
27
28
29
30
31
32
33
" U" n9 a: f# X$ A8 k7 n& R6 Q9 @34
35
36
37
3 O0 T7 f7 K# b, d( ?& U" N: m8 n* I  u3 Q38
39
6 g$ Y# Q( w6 q40
/ K6 g. Q% R8 Q$ i; [5 N, V+ n41
42
6 D" V' B7 u3 }, S1 \& Z- b43
  _& d* z7 F, r* c44
45
  a8 e6 R% e8 z1 D$ x/ I: O46
  {! m( J2 a2 {  z% y47
+ j2 x! Z# Z( y% B48
49
50
51
52
53
" t% R+ O4 k/ L, Y& Z; M54
55
4 j; W# M  P1 G/ S% A" D* h8 G+ P56
57
58
7 z& P1 s! z" j% A1 @59
60
61
) m1 B& g3 F! j! }$ w9 }# i2 s62
63
# f4 u5 L/ x- F$ ~  z64
! r! ~; ?7 m" ^, S3 c  O65
( P4 ]( k; ^+ B$ Z; m" I0 x% U8 a$ Y66
67
( {" i) y+ l* M  }( i68
- p' Z" b( M6 i69
70
交换排序
冒泡排序
8 I0 D( R* m& U) G& h依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
; f, U, T* ~1 r在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
7 A# ?! p. ?% L$ A% f遍历数组，直至结束。
0 g4 _  ~! m+ a2 g最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
$ g- k6 v# B5 S2 B- X; b  c7 I, | ) 。
# p. D* l' Y) j* F( H0 ?
- V9 u  ~, [2 S: O7 Z# t
代码实现
1 @; }9 n9 f( p" l

* C% d! g# t" u- y8 T! rimport java.util.Arrays;
public class Solution {
. d) Y, b& b0 d" l. d       
3 c! L* O+ d  n$ B! A6 Q        private static void bubbleSort(int[] nums) {
  K4 u& l9 z' ~1 L3 Z                // 循环次数
                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
- S% e, k8 a; k$ c. }- _7 \  c                                if (nums[j] > nums[j + 1]) {
: X5 `" y+ ]$ G$ U. ^1 [& ]                                        swap(nums, j, j + 1);
  @2 O: z3 B/ T" P7 a                                }
                        }
# O7 }. B9 I# I% g4 L* w                }
6 ]' f3 L- k+ u; X        }

+ C. {. b' C5 b7 R4 P2 v9 A. C
        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
, I% o) O9 l* @/ |                nums[j] = nums;
                nums= temp;
        }
1 C% z5 |/ t% x  ?

        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
5 G/ K  h' V% F% Y' e        }
}
1
4 a& C& k5 \) X' I* W' {2
3
4
5
6
7
8
" z3 e) t- J5 i/ h1 S% S9
& {3 ^$ o% K7 y. R3 a10
: e. G% x% s& s4 {% F1 K% h11
' H3 C6 T  A; ?; H; p) Z4 q12
8 C4 p6 a2 u. i( E13
14
15
4 s7 v) u1 S1 {" n& W$ s( l) E16
7 j- X) _3 ]' X1 Y/ l17
18
% x) ]' ^& G! b. T1 o19
. j4 H' ]# d6 E) o20
21
$ Z! v6 V, {. ^22
2 B$ A: W7 N/ o' t. U+ y8 n& [23
24
25
0 m3 `& }. B, ^26
3 ^/ _) Q! k+ f! G$ f$ E27
快速排序
/ U( T  f! E, `4 f. Q时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
9 z9 [* ^' A8 ~* S8 f

7 ?" D2 f' h6 G, m% W" w代码实现


/ g9 {+ e% W6 k8 e1 a- Qpublic class Solution {
' ~8 F5 e4 A; E! u3 i; ?- W6 q, d/ z       
4 o# k% S: ]: l1 x% A* o        // Median-of-Three Partitioning
3 N  c/ D# Z% e% z        public static int selectPivot(int[] array, int left, int right) {
                int middle = (left + right) / 2;
, e/ [% M% T( X               
7 M) ~$ v1 ^7 w& J+ M9 f                if (array[middle] > array[right])
( e9 M/ n5 R- F& t( U" T                        swap(array, middle, left);
                if (array[left] > array[right])
                        swap(array, left, right);
( U8 V( S  X8 u  ]                if (array[middle] > array[left])
! a8 r8 D2 p5 u- s                        swap(array, left, middle);
               
                return array[left];
        }
       
+ r: C9 l: Q3 f" W  ?- Q        public static void sort(int[] array, int left, int right) {
6 _% P* y6 V/ m1 V5 K9 a: ]% J                if (left >= right)
% b8 o% q% R) t' M. ~9 h                        return;
* v( B# q9 W6 g/ j7 _: X                int index = partition(array, left, right);
                sort(array, left, index - 1);
. L3 I) R+ |4 q6 t! K9 P                sort(array, index + 1, right);
    }
       
6 X$ A- s1 m4 ]# q* x; @" }- j        public static int partition(int[] array, int left, int right){
4 M. K/ Z% b1 J3 c/ i        int pivot = selectPivot(array, left, right);
' }8 m( s* c3 T7 e- F        while(left < right){
            while(left < right && array[right] >= pivot){
! `5 Z+ ]. L, a- R                right--;
) P) q; m8 f! R6 O' g# c- N6 _            }
            if (left < right) {
' V8 ]" S& P$ `/ L( @$ k% A0 ]: A0 X1 o0 v                array[left++] = array[right];
7 I8 {: c: }* f6 S- D! U' N            }
0 }' A1 j0 _7 }  e' ^- L  z1 H            while(left < right && array[left] < pivot){
2 C4 t1 q5 Y& ~                left++;
            }
            if (left < right) {
                array[right--] = array[left];
            }
0 @/ x; W$ b/ q) l8 Z        }
' Z+ k- Y5 Y# p3 `/ \" H7 Z            array[right] = pivot;
        return right;
1 k; b/ F' z' x# \) u    }


+ C. H8 [+ k# v4 `    public static void swap(int[] array, int left, int right){
; H/ j4 H# w: ~- `0 X7 @            int value = array[left];
            array[left] = array[right];
            array[right] = value;
! m6 Z( g" J7 t    }

+ i7 Y! P7 i5 Y
8 R3 C3 A$ h5 D9 _        public static void main(String[] args) {
' e$ ~& {" k8 o; D                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));
8 T$ Y7 Z9 Q# h. b. p: y        }
9 y+ c: U" Y% a/ t: o" K7 K}
% f6 y' z$ X$ [  K& n+ y$ O1
$ a5 W% j+ Y3 n3 `7 L" O2
3
4
5
1 |( J/ d6 ~  X' h6
7
8
: |. @# {9 X( R5 J+ F! L6 V7 r9
10
11
12
13
14
) ^. @) c/ f% T0 I15
16
% o! Q, L* ?8 {/ l' s$ ~17
: ?9 H5 {& S0 ?' a1 V6 o" y6 R18
0 d# r! c; i! }19
. T* C; d" S5 u$ O) R% q20
6 {5 `, Y0 }/ x( E" A' S/ V" U21
22
23
) L- `7 O6 n6 E% ^. c9 Z, f24
25
# `+ `' F, s7 Q4 q26
& v$ _! h$ y( @3 c; f27
28
% l  E" F, F3 I9 I1 c4 a29
( u% e8 t: G2 c+ y' k% f% X: g30
31
" ]3 G2 H$ R3 ~: S+ x+ T0 {/ }32
33
34
35
36
( m2 t% i) y7 N7 R& v37
38
  H+ Z5 D8 V& E/ f; w  }39
9 J8 Y; d* W2 c: E40
) d, R+ ?' p6 D7 y41
& M0 c+ c* |% q$ p42
43
44
( H, ?: n' t3 f+ T! c4 p- D* N45
46
47
48
1 `* z2 w2 J- x7 I. S2 _7 ]0 k49
50
2 @  s) N% M8 R/ f0 N8 p0 |51
52
53
/ {$ F( \4 P4 n: C( _" z7 L54
55
56
( d9 b/ @: V3 r8 c: o& b) ]# _8 _& g57
归并排序
将长序列从中间分成两个子序列。
对这两个子序列依次继续执行重复分裂，直至不能再分。
0 h) x! a  ~9 F& A递归返回两两排好序的子序列。
: D# S* Z' ]8 M2 ^4 R( m) F( q平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


) J8 ?' l2 i" a" c$ [代码实现**
7 _; v6 M  x9 e6 a; r
" ]: e. G2 B  F& Z
public class Solution {
        public static void main(String[] args) {
( Y  y2 Y; |5 V. D                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                int[] arr = MergeSort(array);
                System.out.println(Arrays.toString(arr));
        }

8 a% p9 S" y! g
        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
' N: t- ?7 V4 Z9 l( O5 L0 \9 R; y                        return array;
                int middle = array.length / 2;
                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
. {0 N& u5 T3 N5 b                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }


        private static int[] merge(int[] leftArray, int[] rightArray) {
  N9 o. W! S1 t# X7 n# |5 E0 y                int[] result = new int[leftArray.length + rightArray.length];
$ h7 i9 w- s2 j  U" ~+ o                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
                        if (i >= leftArray.length) {
1 X' z' O" n! i. m; Q' {                                result[index] = rightArray[j++];
# @" w* g8 I$ O  Y                        } else if (j >= rightArray.length) {
                                result[index] = leftArray[i++];
+ @, B+ j* n# k( A, _; h' o                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
                        } else {
! Y, H( h' h6 a! r                                result[index] = leftArray[i++];
                        }
                }
                return result;
4 f4 }/ C) R/ W4 z        }
% G: j! \+ N' [5 V  `; ^0 p}
$ O, u7 e, g, Y
+ y  R2 U, s, R+ @, B5 u  k' a
1
2
9 Q3 v4 s1 K1 I  X9 K3
4
: M' F. N2 P& w% Z1 y9 {5
% K1 o; t# W0 \6
7
/ G4 w0 F. G! z  Y8 ~% y# q7 W8
  `3 S" }0 j* o8 V/ l- f. z9
10
11
12
13
14
- E$ B! F6 I) h" b  ~" N15
16
17
  m% h/ |2 r9 Z3 T' u9 i& {18
19
5 ]: R4 S& [! R: L0 x( w) x& Z+ q20
21
22
& X3 m  b. M1 L+ B23
0 ]6 Y1 x( U  M$ W/ K, h24
; t  v0 h, x1 \+ ]( @/ j25
26
27
3 z3 \1 {- r2 t* [28
$ {% E) z7 r  O. P29
30
% e& j* G8 o; _9 S/ d+ a31
: K% n% Z+ R0 n# |: g0 G6 J- h32
33
' p! `' |5 Z1 t6 m9 r* }基数排序
+ Z( A% A- E3 v% _3 ?" T找到数组中最大的数，确定最多一共有几位数。
* q. ]$ c0 z* I$ f7 x按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
) r6 n* L  x8 |2 \0 W8 p8 }/ p将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
; l% f1 N3 |- W
1 ^; N! Z: Q3 i1 G# x, u, ~3 T" E5 c
6 c* @, L% B8 X. W4 `代码实现**


' t- {2 u+ |2 {7 Wpublic class RadixSort {
$ }) m# f$ z! ]/ I* r7 ?

        public static void main(String[] args) {
- S3 Y! T* E+ M  F6 f                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
                int[] arr = radixSort(array);
                System.out.println(Arrays.toString(arr));
        }
. d, d. R* J: X/ Z3 Z: o
4 o# A5 \# I/ T) ~  P
        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
" ^# I$ v9 R& j' f" S* ^8 `- g8 z                        return array;
: X' H7 X  K9 w0 j6 v1 h! `                }
* j& K6 O2 j6 b1 c# T& w" @! G" h                // 根据最大值找到最大位数
( @& O5 Q" R3 g- w! R: R9 j                int max = 0;
1 X6 k1 [, ], a. O% a0 o                for (int i = 0; i < array.length; i++) {
. M+ i' O8 Y/ j/ o                        max = Math.max(max, array);
                }
               
. V7 u* s7 G: U& A; T                int maxDigit = 0;
8 E9 i2 {. ~5 n: Z* P6 @, k                while (max != 0) {
" K3 o- w' R9 X3 |                        max /= 10;
/ o' H9 i3 Y  B. f- s2 L- E6 g                        maxDigit++;
                }
" S+ _) F% w+ f& U6 r# l               
                // 第一维: 0~9
                int[][] radix = new int[10][array.length];
" o! I8 u' D) i* d$ E                // 该位为 i 的元素个数
                int[] count = new int[10];
5 k8 P- p) {$ f! u; H5 }- f               
                int m = 1;
+ a$ a4 x' t1 X3 |                int n = 1;
               
                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
                                int lsd = (array / n) % 10;
                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
% |' p( o- S- y& e                        }
                        for (int i = 0, k = 0; i < 10; i++) {
4 }6 z8 ^7 J( {! |1 O" f                                if (count != 0) {
- l2 k" [8 J9 A. v6 @                                        for (int j = 0; j < count; j++) {
5 I: W; w: ~' z" r$ i8 Z: ]                                                array[k++] = radix[j];
, E7 w5 Q8 D5 f( R                                        }
                                }
                                count = 0;
                        }
                        n *= 10;
                        m++;
                }
1 d; \$ f6 f# s/ r                return array;
( L1 S% l3 G* V0 H2 ^9 y        }
( {. p" T6 _6 K  M: b
, d9 P+ P0 R/ v2 A5 D
) V7 z) p! A2 i}
1
2
' R9 X1 e! u5 g6 _) [7 C9 S3
4
# p3 U2 L( A+ M9 q5
6
! {: ~1 Q: q2 Z1 E+ l6 c7
8
9
10
% L: D9 Z6 f7 }" z" q) b11
12
13
8 L- f  E5 ]* x# J: v14
15
; {2 d* Y, n" j1 K: V16
17
18
" x: e. C" B5 u9 z; O' j19
20
21
22
7 D- a8 d% c% O0 V23
24
25
( Q. R9 d9 f  f+ G* N) `6 h26
8 B7 K2 R8 {: p5 Y' {5 n. k2 w  l27
28
" f1 I" {. P% z0 ?9 J% G+ h: S29
% j; b% _: E: t" w30
# H# I4 ?; b4 @( w$ l! ]31
32
  Y6 |) I3 h$ z4 F& Y9 \0 l2 i1 n33
34
/ _& n- H* ]! Y5 o7 r: `. X35
36
37
38
39
, q$ U; n* {/ W40
0 d3 }6 h$ ?! N! k( E, d6 ^41
, f' G, P" t2 f3 R0 f& D: z8 b42
2 G( x6 f/ f; v43
: ^* M) b+ t7 r44
45
( h- y& p  k) ^, ^; x: ]: s46
47
2 U6 c0 d" T  }& Q. s/ n48
49
50
- q5 Y8 g9 W5 B51
% K% \# S* `8 U7 o% E/ J# e& c) s  n52
9 X  G! v5 n$ G8 b! r53
计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
" L2 R7 v6 F# r0 l统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。


代码实现
0 t6 a  V1 F2 {

public class Solution {


        public static void main(String[] args) {
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
                int[] arr = countSort(array);
7 o# t; q, U' T                System.out.println(Arrays.toString(arr));
! C. E/ H3 v9 i        }
/ N/ j7 j5 Q1 ?* }" F+ w
: U5 g) M2 ]1 w; z: U- r4 m9 ?  H$ b  {
        private static int[] countSort(int[] array) {
1 v3 o& v6 @/ k( H                if (array.length == 0)
% F2 U8 f' P+ t4 C& H                        return array;
5 Z! V, E" h# m+ \. F; D: y               
                int min = array[0], max = array[0];
1 d, G: f9 d" w               
' J* ]) j) M* C4 l3 ^( F5 \                for (int i = 0; i < array.length; i++) {
$ i; |% Y/ D1 [4 s: r) {" T4 w                        if (min > array) {
                                min = array;
                        }
                        if (max < array) {
                                max = array;
% [7 a1 r  J$ F1 w                        }
8 X3 f" @4 N5 ^                }
               
                int[] count = new int[max - min + 1];
               
: n$ b. m7 b  F7 w5 }                for (int i = 0; i < array.length; i++) {
" c3 R. z4 O& i* V+ i  P% w9 R; Q                        count[array - min]++;
' W# [; n9 b7 n7 [3 U                }
               
                int i = 0;
                int index = 0;
; E: U- @' }* _( F: }1 x                while (index < array.length) {
                        if (count != 0) {
                                array[index] = i + min;
                                count--;
                                index++;
9 C# @* z2 B4 Q3 w                        } else {
                                i++;
* i; L7 G! A; p" P                        }
                }
0 r' z- |( l$ K5 K  `                return array;
4 c  P/ x$ D% w5 ]; o% s! B        }
8 o8 }; t* ?' g: g3 W4 I6 x       
}
1
1 j- R9 B) W9 [+ `5 |, _5 p; r0 W2
3
4
5
6
2 u' w1 ?0 p" |7
6 m3 e3 W* _5 g' e, N$ t" [8
& ]4 i  f- G0 Q) N% _9
10
11
' E4 ?* R6 E! Z2 w4 e12
13
14
15
6 i: H0 T) L2 ~: s$ z+ ^' O( D16
+ r% \7 [: V& K17
4 _7 N: D9 f3 E9 b18
19
20
+ T8 h" w9 T  [4 c5 O* V6 X1 x* i21
; M8 }: k- x( l+ ~22
+ o: W. E5 y# ?! u+ [23
4 T8 `/ A  ]5 ?: q9 I1 O24
2 F' T6 U' j: D25
, C! R6 `+ {/ ^1 E6 t" y/ p26
# ^/ [; c7 g1 Q2 |# w3 z  S27
* X: S: Y3 @( H/ B" _4 }28
29
30
  S6 _+ d2 n: I8 |% ?" K# ]3 z% d31
32
0 C/ E, W9 V3 p  E7 n/ b2 S; D33
34
3 W" s: w) A+ w2 x/ H1 W( W' V35
6 O2 \: l0 I- f+ O8 a36
! C" w( y+ h5 y37
8 D7 O+ e  |+ V  B1 _- ^- F38
% ?- g& [! `. @. w/ J39
9 E' u( C1 [: z6 O( `40
) ], p0 J) k6 `) o6 Q; Z. c" H4 L41
( M# ?6 _4 M) H42
43
% v3 k" I' g) Z7 U44
桶排序
————————————————
, ^! V3 i! w" Y' ]! ]; v版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
  L% W- u; g& F4 Y1 K% }' j

+ X/ M+ u0 P; J3 \( I" @