十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）
& c, P! z' j! S" w9 F
十大排序算法（Java实现）
排序算法框架
排序算法性质
4 e8 g  b$ R/ l; O( D插入排序
  Q3 g* q8 L7 d直接插入排序
希尔排序
选择排序
2 s2 Y) L+ w3 y' l  W简单选择排序
堆排序
: L% m) t- j3 {- I4 E: l交换排序
冒泡排序
1 N" W# X" g+ a5 F4 \$ U快速排序
2 L) m/ ^/ J! h3 Y归并排序
' {! S) ?9 ^) [' ^基数排序
计数排序
桶排序
更多文章点击 >> 这里

1 R. \* v& {9 w6 T5 a
排序算法框架
5 M2 k* p* B: s7 I

5 o  |1 Y  T2 t
2 H: O2 t; s5 l1 _. W# a
排序算法性质
9 R  E; C9 m' u  u! o


, u! D2 L7 V- `, q. Z+ I* X
插入排序
直接插入排序
* A" m- _. D" W* n$ U从第一个元素开始，认为该元素是已排序的。
) S1 M4 ~* E6 e; X/ X取出下一元素，与前面已经排好序的部分进行比较。
) U- C+ D/ q: V$ d" t若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
% r9 B( K8 }1 C- J3 y0 ^9 W遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2
) 。

2 v( y# N9 j3 F/ \: {% r
: F: J' j( K& o; y1 r, {% h代码实现


public class Solution {
        public static void main(String[] args) {
, t# g! u9 w+ i9 ?  [                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                insertSort(array);
                System.out.println(Arrays.toString(array));
        }
* N; R$ a6 x! A+ G# O

, Z5 L9 k& t$ w" E# O  g        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
$ x7 {, ~5 ?3 a. F* \                        int index = i;
1 ]/ z8 R1 I* g4 t! t( C6 ?2 H) q                        while(index >= 0 && array[index] > data) {
0 ~# U) K0 R" B# ~1 d                                array[index + 1] = array[index];
2 r+ v5 j  P, U                                index--;
; a( p3 ]- n7 P: b# K5 f" [; R                        }
4 @7 q/ ?% l: ]% Y9 q8 m8 B                        array[index + 1] = data;
* B/ H; N/ K: X2 _( Q2 G                }
5 Y! L6 i4 m, q& l! q8 w( H        }
}
" P6 Z  t  O6 y9 y1
+ u% K" ]$ D0 {2
% W. x2 p) F* t4 q% w) R3 [3
4
( A. z5 x' j3 ^- B5
6
# d* A# p6 P2 n; d3 ^( N7
8
9
8 w# Z! U4 @: S, Z  s10
) d1 C' a: r+ G& f- c11
' f, |6 `, f1 v  @6 V12
; E9 [4 B! T  n) O1 o13
! r' ^, d& @, h3 i) {14
15
& \. n# K/ ~. w' f; a16
, h1 E$ K' ^; G17
18
19
希尔排序
# u' S" h, G. |2 x* k. q) E1 Y
% s( P2 V  t% z, T) \  N+ W
6 r5 f) K2 C7 z/ ?: D& u) I3 J7 {' ~2 N时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
1 R: N" \( F, t# ^! S
' C0 b) w' P5 [2 j' ^8 R9 j4 h
代码实现
' B7 O8 J6 ^, @' m) Q$ a5 T0 N

public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
. w2 j8 V/ y3 F9 S7 `# O                shellSort(array);
                System.out.println(Arrays.toString(array));
        }
8 `) i7 S. _& h/ {# g1 Z/ n

        private static void shellSort(int[] array) {
. L( |- ^" n% N" y5 \- P                int gap = array.length / 2;
! M' J. M( n  s8 l8 y" E  @                while (gap > 0) {
# U3 J$ V, o4 }' q                        for (int i = gap; i < array.length; i++) {
5 z: }& Q! u* f3 L: |# {                                int index = i - gap;
                                int temp = array;
                                while (index >= 0 && array[index] > temp) {
  c3 `6 Q8 ?" R! v0 \" p6 V! \                                        swap(array, index, index + gap);
                                        index -= gap;
                                }
//                                array[index + gap] = temp;
# n9 f6 }  M2 y7 F2 k7 e4 c% O9 ?                        }
                        gap /= 2;
                        System.out.println(Arrays.toString(array));
                }
        }

1 W: L/ H* ]1 J( h
3 J0 B  c' y+ T* Z9 m4 c        private static void swap(int[] array, int i, int index) {
9 P+ _- s& j+ l                int temp = array;
                array = array[index];
                array[index] = temp;
7 a0 {  H  ]1 C. m" i% c4 b        }
( x3 E0 M$ J, n& ~}
1
0 _* l5 {3 V8 o5 L: V& M2
3
, e& G  }5 O% \4 K. V4
5
6
: b6 v1 M& c! N; |7 `7
8
9
8 U: u* {$ u; G8 x& e4 h% E10
11
12
/ ~  L+ n: d9 U7 h2 A6 v! u% g13
14
15
16
17
18
19
  g& O* T; b9 u- G& u20
9 i$ u8 W9 a& X! H! p" N( v21
22
23
24
25
26
27
28
29
- @+ M' p& n' j; E: K30
选择排序
简单选择排序
, Q9 ^4 S6 N  {4 ]/ d8 ^0 a0 l从未排序的初始数组中寻找最小元素放置首位。
9 v+ K- w1 c0 r6 \: f7 l8 B从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
8 k1 \- H$ B* q8 |2 x& o$ v2 _时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。
2 Z0 ?8 @# H* \# o$ L5 s( Y' M
6 k4 }$ L6 v) D* h! @+ C% j
' _) O! v2 Y* a, ~代码实现**
: Z5 n3 n5 F7 @$ y

public class Solution {
" P* v( z: X0 Q5 }6 I        public static void main(String[] args) {
/ A' `/ j! T$ h& \" `( i& R                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
; q$ |% Y; T( q) J                System.out.println(Arrays.toString(array));
" x6 L2 f/ N0 t5 H8 {        }


- N5 T  Z. }1 F8 Z/ o+ U        private static void selectionSort(int[] array) {
+ }& v7 U/ G4 O0 {9 J                for (int i = 0; i < array.length; i++) {
& I3 _, P- p; y) S+ ]                        int index = i;
                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
                                        index = j;
1 w  |% }4 ~/ W# b4 n6 _: q                                }
                        }
- i- l* c- Y5 i) @% i                        swap(array, index, i);
                }
, P6 I  i. U+ R& Z        }

. \, X! c8 \4 ~' V- ~' Z, o: O. v
7 ?! j7 X8 Q& I+ c! N        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
                array[index] = array;
% @+ X" ]- x: o+ W) ?. o7 O# y                array = temp;
        }
. i1 a! b2 `2 v+ e}
1
" e6 @& U  h$ a# ^* z  u2
5 P# L' Z$ o7 G! L, X" _3
4
5
0 I' g+ i. r# y$ W% W. ^9 j6
6 J/ v) h4 A0 f# J, Z( w3 ?7
4 y* E, `; g" s* j8
9
; M/ E3 a0 \! F& e# X10
11
12
13
14
" {0 K3 T6 P9 i& R15
- [7 P7 u% ]7 i& f& _+ X16
17
18
  s$ W. G; }$ Q& l% p7 n19
& ^0 @5 I1 }7 [2 U  J' t/ O! a20
21
22
+ d; L" Z8 Y; Z# M! J% d0 j9 `23
24
. g9 c4 `+ J: z25
堆排序
% j) x/ F4 \4 C$ m时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现**


public class Solution {
" B0 a2 T4 H! g$ [" C        // 建堆
2 z6 P8 x4 \4 w* s        public static void creatHeap(int[] arr, int n) {
1 Y& L. r0 ]( A& @) a                // 因为数组是从0开始的
                for (int i = (n - 1) / 2; i >= 0; i--) {
2 [1 n( H7 T3 `) @5 ~$ L+ g                        percolateDown(arr, i, n);
8 C- \6 I. ~: B8 z) ~                }
        }
        // 插入
  F- i+ T0 a/ ?/ j0 Y  }        private static void insertHeap(int[] array, int data, int n) {
0 h1 f! c+ O  f                array[n] = data;
: f; e$ x. L, e; U                percolatrUp(array, n);
        }
        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
3 |$ ~% |) b( a) K                arr[0] = arr[n];
: z' |, p* R8 d; s                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
. K6 F: a. m- P3 j- E' x8 d3 d' K        }
        // 上浮
+ L2 D+ L) O7 E4 p/ e* M1 M        private static void percolatrUp(int[] array, int n) {
                int data = array[n];
6 Q; c+ o2 B0 f6 \2 o4 M. L                int father = (n - 1) / 2;
/ }9 @( A: h6 P                while (data < array[father] && father >= 0) {
/ E. x9 l$ k; F' V3 F                        array[n] = array[father];
( A! z% ~# v  r  l5 U$ C5 E( A                        array[father] = data;
                        n = father;
9 M9 S/ f2 }, y% l1 [' L/ f5 _                        father = (n - 1) / 2;
                }
" ~1 W! m6 O0 d9 I. U                array[father] = data;
        }
        // 下滤
2 y! P. h8 y( M; N) D1 r. U        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
                int child = 2 * i + 1;
                // 遍历整个该根结点的子树
                while (child <= n) {
                        // 定位左右结点小的那一个
                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
; l& h; C# ^7 O' A/ Q/ _9 z, D                                child += 1;
                        }
$ z$ B. f# v2 `7 [0 J                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
( }* r/ g. [9 v0 L( Z5 T1 }1 H, J                                break;
                        }
                        // 互换根结点和子结点
! }. }! x! K, E$ K/ h9 v7 Z: u                        arr = arr[child];
                        arr[child] = father;
                        // 重新定位根结点和子结点
2 E  j8 b* Z1 @: ], j* H                        i = child;
: o4 _! F% E- |7 i" t' g3 {% J                        child = i * 2 + 1;
- J; b) [2 X+ z* P) ~8 R, g                }
        }
   
  l( R. f$ l' e, l. Q$ h- y1 q        public static void main(String[] args) {
9 s, y% M! N1 S7 t% q                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
1 m+ ~, t5 s& ~/ n" e               
( e& Z  X/ a! J! |5 E                creatHeap(array, array.length - 1);
1 y' z9 Y- y2 m, q                System.out.println(Arrays.toString(array));
7 ~. N& i* y& G% z6 L8 f! a, x               
% p2 \+ q' X# |& u                deleteHeap(array, array.length - 1);
  f: ?; z& e) }  q                System.out.println(Arrays.toString(array));
( ^, E" L; q7 a9 A  f               
3 A- j) h( v. m$ y                deleteHeap(array, array.length - 2);
5 ^7 z6 ?; @4 |, R                System.out.println(Arrays.toString(array));
               
                insertHeap(array, 3, array.length - 2);
" Y( ~, f$ M' S$ h3 h+ U                System.out.println(Arrays.toString(array));
, \9 F% \/ v1 Z: Y0 m6 N        }
}
$ l/ j/ l" O! m$ R5 {1
) P+ u' U; F2 U8 Q6 K6 k2
3
4
5
6
0 e: g/ K) W9 J% l3 H2 C7
! c5 A% Y6 I) H" B- c7 S. `7 U8
9 ]4 S* f  x7 n) a9
+ R2 }- g; e9 N10
0 S% H0 u  {, W2 e" Y" [11
12
13
14
15
) E  |$ M( A* ?' `" i5 |8 U! ~2 q16
17
18
19
8 a* S0 z* l( S2 D; q/ y20
21
22
) L% P9 O# q1 }7 u  U23
24
. x2 v/ E) v; w0 t( {7 t25
, S, F$ T9 W9 y5 U26
27
5 h+ N$ O4 F( K0 d& ^3 W7 m* o28
29
30
31
9 P" y! p9 {0 u2 _: }* ^! [32
9 Q( \$ ]' }& q/ h  e$ h9 ]* M( y33
! t1 D1 J! y% ?2 f34
+ l$ J" V0 g/ t$ u& @35
36
37
38
0 s6 B' \4 p7 _; U8 j39
" C1 @1 c$ _; `: ^0 [; k3 D2 M5 B40
41
+ I# X+ E6 t9 g1 A# ?42
" z! w( v& T- J/ w& M43
) @& C7 f* W, j# K44
3 |7 G( s0 \  _- G# d45
2 t5 p  E1 I# n8 [46
47
48
/ g# ?2 u$ g& g  V, Y+ R49
50
+ t/ ~  t( W2 \) o51
) \- j8 Z0 Z3 c52
% V0 L7 J* q, b53
54
; s9 i+ y# y$ c7 l# |55
0 F5 F* P4 X/ J5 b# }! P9 I- Y56
57
3 G+ z% v7 U  c; d* ~: b58
- s6 r) g4 `% a6 r' Q59
; l1 [. K( {8 q' d  t60
( e: L+ u7 t: n- S2 k61
62
) Z9 D- ?4 k4 J' s( k' ]  z63
64
7 `: Z" j1 W( e3 ?$ _! f65
66
% [* ~1 n& V* ^# i, H$ ]0 I67
68
69
70
+ H! J. U( F+ d8 K7 A+ K  W7 c2 q交换排序
9 W! X4 q2 K6 ^( W冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
! K- U/ {+ u- O最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
+ P+ w( @$ p0 ?$ G: p* S2
1 \* p! U; M. x  H4 Z6 _ ) 。
* ~- G: {0 s# g7 d# `+ d" U
7 h3 K/ x) v$ {7 \* J) ?6 d2 }) ^. j
! m8 u# e& F3 J( O代码实现

  u+ o1 ~3 E& ]) p
& f; x  X) y, @/ |+ F2 ?7 zimport java.util.Arrays;
public class Solution {
       
        private static void bubbleSort(int[] nums) {
7 m6 M6 B" P0 W; q) P+ s# w! u                // 循环次数
                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]) {
* {+ J3 M; z3 G& d                                        swap(nums, j, j + 1);
                                }
* |; l0 o" A3 v+ N0 z                        }
- ]$ r2 r, U1 B4 B                }
        }
" v. m  W: Z) F' k
1 I1 K: P. g4 ~2 u7 Y
% M, G+ ?2 C6 k2 S" @/ Y        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
3 q* X; ~" |2 ^. d                nums[j] = nums;
                nums= temp;
  ^/ \& _/ u( _3 D        }


        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
1 U; I/ Y/ Y' \                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
7 }7 i5 m$ Q* j' x1 e/ V        }
) E$ \  L2 H2 |. o}
, o5 Q$ y! N- E$ @: B: N, w1
7 k9 M" \3 W! H: h4 L& h2
3
4
5
4 N' I8 d$ o  x% J) N3 m( t& A6
7
8
9
# W6 ?1 T6 X7 j" v" h/ C10
( m- f  S& o, I, m7 ]6 v! g11
12
9 D! `8 q' j  n' b1 s13
14
15
16
17
18
2 x* Y, o$ q' ~5 t& v! b' ~19
20
21
22
23
24
5 [% `$ o. }, n5 R25
4 X8 q  Z) h) r4 V& `1 y* {26
27
$ a3 d5 g& U7 a& p& |. }4 h2 s快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
1 j0 |* w' z, J6 v4 N6 E7 k

5 ]7 ]1 p; s3 X8 D/ Z0 I- W代码实现
% m6 P! o% t. T% l6 i# f6 }

public class Solution {
       
        // Median-of-Three Partitioning
: Y) w" O& w  f0 O        public static int selectPivot(int[] array, int left, int right) {
/ s) x$ {) l- m& U  ?: q; I                int middle = (left + right) / 2;
               
9 ^9 X! p. [2 c. v3 }                if (array[middle] > array[right])
; e* K) I! f4 T, n) [+ z                        swap(array, middle, left);
% z, P; \" U% A/ {" C! e: k5 l                if (array[left] > array[right])
: \& F9 X% _1 d& u" o& T+ Y* w: Q                        swap(array, left, right);
                if (array[middle] > array[left])
                        swap(array, left, middle);
               
7 U- x: |0 k5 U& i5 u! r  B* E6 G                return array[left];
        }
       
9 r+ L# J: s; N1 X1 B        public static void sort(int[] array, int left, int right) {
                if (left >= right)
8 o' a; P7 N/ {* a5 ~                        return;
                int index = partition(array, left, right);
                sort(array, left, index - 1);
                sort(array, index + 1, right);
/ h1 ^9 x0 `; d2 Z* l2 P" x8 V    }
       
% n$ q% t! y2 `        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){
2 f8 X4 t, b1 O8 u2 A: }( F1 h                right--;
            }
            if (left < right) {
) @" e8 p$ s7 ^, w; A+ i                array[left++] = array[right];
            }
            while(left < right && array[left] < pivot){
' |1 C& m& h7 P! d- H0 ?: s                left++;
& P$ d/ y8 }4 r            }
$ r8 r, ?+ z; V, y" O( U# Q            if (left < right) {
                array[right--] = array[left];
0 c( ~( S2 P0 ^! X' m2 p8 x            }
8 m" \2 Z7 r( T( @  w& |; V+ ?        }
            array[right] = pivot;
        return right;
    }
# q6 {/ R% _1 V- L

! T( u1 K4 c7 \2 |2 t/ l    public static void swap(int[] array, int left, int right){
3 V3 b% s+ x; x, k" P1 W& U            int value = array[left];
) }2 D; Y  j6 k- A            array[left] = array[right];
- L/ \9 l* d8 P$ Z: ?7 w9 Q2 G7 ~            array[right] = value;
    }
+ e5 w- C0 m! t9 ~5 m) \

0 s: w# ]. @  `8 ?$ R        public static void main(String[] args) {
9 \6 v/ }* H! n/ Y) ], e                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
* e0 I$ m0 ?! x# j8 w) y                // System.out.println(Arrays.toString(array));
+ N2 g3 |1 [! W! D( {                sort(array, 0, array.length - 1);
: L$ O; B4 `# \3 ^1 y5 x. v- J                System.out.println(Arrays.toString(array));
        }
}
1
2
5 \" g; C) `& C0 A- `' F2 u3 c3
$ j% `8 H  ?. w7 b8 E  o+ f8 ]4
2 X& E; |5 m5 s6 I$ i* X  f! [5
6
7
8
9
10
11
1 \/ \' K2 J" t4 A12
/ I: s  {1 _4 b* I5 i9 u1 \13
14
15
# L) m- Y2 O8 _/ j9 f8 R$ H16
17
" H7 e8 Z, W; D0 ~9 Z6 b0 y8 d18
19
20
21
3 E: W1 q+ h& }* n7 Q3 b22
23
24
* a" P! J4 B7 l25
' V& p+ _4 e) k; N; C26
27
" P6 O3 O& @0 m28
! ~- X  L4 b6 q! k/ p! f29
30
# {1 F/ }8 p; U& p' K! F2 j4 E) b31
( X& F; X3 M1 ^0 k8 f4 v, g* }. Q32
' l) a; D* [: j33
& i0 m; l% B: o  G34
35
36
37
/ a3 W2 `" U2 {" y3 r3 Z38
39
40
41
+ q# g7 Z; Z* u/ A42
43
, f/ J6 m+ y( ~4 y3 _+ r' F44
7 V7 v& ?6 |2 ~! m45
( ?2 L. z  x. X46
4 _7 Y9 o8 r1 G7 h& Z47
0 y: L0 ?* J- a2 l* s( A48
! W3 r0 ?3 k4 |+ W% |49
) t1 h6 V% B& L6 A2 z4 J- ^' [" y50
0 O6 r. j1 H: M" {5 u! p0 k51
52
0 {9 Z8 E6 A% R, u* m  ?. n! J2 A53
. B! c8 o3 z- X+ X9 E2 |54
7 \5 v& U! g! F! r' I& @! c55
56
% h4 g/ [$ g# ?' a/ h57
归并排序
0 n- V4 h8 [2 V8 w将长序列从中间分成两个子序列。
4 y8 U" J3 J* p! |) M. L! I6 V对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
) }; G* b$ n' ~* J: f  C* c平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现**


public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
+ ]+ g' j* h. K                int[] arr = MergeSort(array);
                System.out.println(Arrays.toString(arr));
" `  j% B2 S$ A; i0 O        }

7 l! m8 I7 z: U7 Z6 I
2 t2 c+ p9 \  S' u! O        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
: V3 ~' ?: |2 P4 z                        return array;
                int middle = array.length / 2;
                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
- B# Q& A1 c9 B+ \4 a7 g( A3 I( H  P                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }
3 D* n2 U5 |6 t

        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) {
                                result[index] = rightArray[j++];
                        } else if (j >= rightArray.length) {
4 u" a3 X. P# K# e                                result[index] = leftArray[i++];
# C5 P4 w$ A! Z8 ^$ L/ M                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
                        } else {
3 l/ n" J& C' }4 s/ [+ F# c, \                                result[index] = leftArray[i++];
, p% T" T, g# }  A% H6 B) {                        }
                }
                return result;
        }
}


1
2
3
4
5
6
7
8
& W  c9 N, L) A; q6 `9
, s+ a) t0 b4 A& N4 K' H0 F( {& L10
! }+ K- X/ n8 k( a& r, T11
12
13
14
15
+ {7 Q: b- J( `$ Q3 C9 H* G16
17
18
, X5 `* f. A' L19
20
21
22
23
24
1 |9 |; w1 E4 @+ ^* V25
26
27
28
29
; k1 M5 c) D1 ^5 \- G7 I30
4 y9 {! t" j  p; E( n, [31
32
$ @" w2 C; c0 A; N33
) s* u# W9 b& ~基数排序
5 Y; L) C: k/ ]0 Y/ c3 R找到数组中最大的数，确定最多一共有几位数。
' \* u  X) Z5 c按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
8 K" J  N+ O0 ^8 _$ A) y! K
5 E# @, z/ c9 E6 O
代码实现**

! p' v  @, d6 y. I
2 a2 O6 ^4 ~/ H+ j& D* m6 x' ~public class RadixSort {
  C5 N, l1 ?/ V, @' ^

        public static void main(String[] args) {
* f1 G- _6 t5 B- j9 y/ h                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
                int[] arr = radixSort(array);
! p& Y5 @& X. l2 L1 x3 {                System.out.println(Arrays.toString(arr));
        }

; q- C' S& s" F
9 H* n* C0 j2 @) V# n0 W! ~        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
, x+ l5 T  J- _4 l9 i                        return array;
$ H% }7 o+ h! m9 ]                }
# p& v* b9 o0 L& K, @: R5 C# _                // 根据最大值找到最大位数
6 b8 n- A& i! N/ L1 @) {                int max = 0;
, G0 u& Y/ J( z# W6 m) H* Y2 U& n                for (int i = 0; i < array.length; i++) {
% v0 V; J+ j& o) _                        max = Math.max(max, array);
                }
               
                int maxDigit = 0;
8 y. J  L* d4 y/ D  N7 i2 M7 z                while (max != 0) {
+ l8 I9 }- W. j3 Q                        max /= 10;
. K9 b! h2 D0 ]( N& P7 e2 z                        maxDigit++;
/ ]; s/ `2 p. j/ l9 J: j' A1 [- M                }
               
                // 第一维: 0~9
# w. j# u1 P3 i( p) p1 x; V( N                int[][] radix = new int[10][array.length];
                // 该位为 i 的元素个数
                int[] count = new int[10];
% J3 u5 o9 F) @+ u               
                int m = 1;
' U3 E5 d1 {# b& M" I6 o                int n = 1;
5 s" Y7 w7 g5 ~3 O7 u% V7 R               
/ }) c  o! F* K# k$ d; t                while (m <= maxDigit) {
) u# s- P& {& P7 c1 C                        for (int i = 0; i < array.length; i++) {
) g3 R5 o% N" o+ P, l                                int lsd = (array / n) % 10;
. C+ k  w1 h, G. k3 U4 o0 b8 a; S, u                                radix[lsd][count[lsd]] = array;
3 V  m0 j& G) U                                count[lsd]++;
                        }
                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
+ j7 h- `4 I# c2 I& i6 T7 D0 ?( M                                        }
                                }
- n7 |# N3 H. T6 x- f+ Q; C                                count = 0;
- X) l" m* e& i# y% w                        }
' D4 e8 I0 D$ o  E                        n *= 10;
2 C# g+ A0 W+ i                        m++;
                }
% d/ ?% `9 F0 D* Z$ v5 V                return array;
# Y! x/ g# W  w3 f" `8 h% O: S        }


5 {( u# y8 F9 s- u( L6 a1 N}
3 h) j0 U5 A2 z- p# @3 s1
2
8 J3 z; e6 k$ i' V% i( c& w3
4
" D! E8 T! J% H7 K9 z1 N2 z; o) P% P" T5
6
7
* g, e! _  O; j3 e9 i8
4 N5 F# P8 y; E9
10
7 x/ q5 J0 q4 }5 z( P( Q11
12
13
8 k9 ?0 T' S- E: _14
15
16
, T4 I# Z- I7 |( C7 Z$ |; d17
: ]6 B7 W+ m# ~/ K  {! w& L1 Z, N18
* N" D$ G2 ~& ?9 j0 i19
20
8 w9 B7 I$ I5 W$ n5 a! {21
22
( l9 R# l3 C, s3 l5 H9 o/ g23
24
25
26
5 P/ H  ~  D2 D- i1 y27
28
  U4 `' S6 a! R8 D29
: Z; [, K- ^' N/ `' U4 k30
2 N" y1 @2 k! ~1 J- ~31
5 X5 k5 v$ Q2 x+ P  N32
33
34
35
, |+ k# ?7 a, F# Q; D& [36
! {: m2 H7 _0 ]! D9 ^37
7 g6 k& M. J4 A1 t7 B8 [38
, y! A- ?3 H/ I; U# ?39
8 i4 f& \- d  D8 w40
) T9 l9 Z9 Y& }41
42
43
4 ?7 b( O  _4 y. I2 g44
45
46
7 p9 p4 J+ v+ J) U7 z& T' \, Y  A47
48
7 `  }9 J3 s% n" P1 H8 n49
- t) B, k' o$ }) F50
. L3 B/ m/ K1 X& Q  B) u51
2 A# H- o2 J, e  l& w" M52
53
计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。


代码实现
; N' r. i. ~. i

public class Solution {
% M* k0 `/ F$ g% @0 ^* J

$ A1 p3 I8 V+ |7 \) h& {) t        public static void main(String[] args) {
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
' Y3 J) t# n4 |1 w9 e" r                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
        }
! H) L6 w6 @! u( p1 o$ j

7 Y- p4 p) E( L4 |! _6 f/ J/ ]        private static int[] countSort(int[] array) {
9 Y! ^) q* Y" a                if (array.length == 0)
                        return array;
" M7 L9 p# H& L               
' g% m$ O& F; a                int min = array[0], max = array[0];
               
                for (int i = 0; i < array.length; i++) {
                        if (min > array) {
                                min = array;
4 w  s" G# V' s. d                        }
                        if (max < array) {
) p  n7 u! Z: {6 o6 a* L3 D# @( C                                max = array;
/ I: [, E0 ~& Q& y! q! F                        }
$ }0 w# I: E+ q$ h0 L                }
) V  s, w! d: S( S0 Y               
                int[] count = new int[max - min + 1];
               
                for (int i = 0; i < array.length; i++) {
                        count[array - min]++;
  |8 C" J  T8 Q8 W1 K                }
% V! b4 ]# T) E' U' ]; P7 e4 d               
                int i = 0;
                int index = 0;
# M( e. S/ t6 ?8 A3 w                while (index < array.length) {
/ h0 U+ N. Q* u4 Z9 f0 |, d+ |                        if (count != 0) {
" y! W# L6 c# t4 ^, j9 G                                array[index] = i + min;
                                count--;
                                index++;
                        } else {
                                i++;
' ^9 Y# g- _, Z& l+ h" J% a) B                        }
% d2 [. U" C7 v, @9 Y2 e                }
6 H6 p% g9 ?' R# c9 {2 ^                return array;
        }
       
}
8 o1 h% i6 }; ]1 [8 D  _1
2
$ J- X) r  D: [3
0 S) Y5 V/ F( _& u* R) M  U2 |4
5
6
3 `' f$ z# }) F9 p- P0 z3 S7
8
# K& J2 Y4 g: w6 i2 i! N" t9
10
11
6 L! w" K6 ~6 z6 U2 J' `% z! J3 `0 I12
% p- `# ^: B8 @13
( b7 f3 i5 l  F) C' d14
) i% M( `. E* h* q9 O3 @* |15
; W4 e3 [2 n5 ]7 n16
17
18
19
20
21
22
23
5 q$ Z6 n; J7 z$ a24
25
$ {$ W7 O. o% p; L26
4 ?8 C; j+ f; j. o- N27
28
. G& z6 W" Q5 M( t0 {( F29
30
31
/ [7 h( E$ J: a' a9 A1 w/ W1 B# n32
8 a9 `6 L+ |* x% v5 S33
5 i5 O3 _6 o0 W34
35
36
& e+ g$ n8 `# d. x: P* X" M37
38
) f$ p6 v3 }7 G39
40
8 ~" u$ |( o6 T2 C41
8 h" Y6 x, I( @3 I$ h( X42
9 I$ N5 e- U9 R4 b8 S$ @43
44
9 K: R9 Q9 B$ J$ [: I. X1 J桶排序
————————————————
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
% P9 l3 y- _; d+ J; D  e: K

# {' m* T1 H9 ?