十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）

十大排序算法（Java实现）
  T6 i+ G1 O" u排序算法框架
排序算法性质
插入排序
; ?2 `8 G" @! N' s( L5 }9 @直接插入排序
希尔排序
选择排序
简单选择排序
堆排序
交换排序
0 O, e; O0 R* ?  U6 K1 p: h冒泡排序
快速排序
; R' s! _4 C9 B" t; ^8 R3 `归并排序
基数排序
' e4 a# z9 c' b- Q2 ?2 \# A" d计数排序
桶排序
! _5 `2 X- O# |4 {  ^更多文章点击 >> 这里
1 q; X! [" ~' n. Q

排序算法框架
( O% q+ T- h5 S$ r1 z

# b! v, c. f+ |( S2 ^
8 ?! d' Q( I* R* r3 f+ r
# o% a8 N% Y1 j3 H排序算法性质
0 T. c9 g0 r# w4 h: e6 g  ]0 t& i
/ p6 n9 ?: l0 b- q1 Z


插入排序
直接插入排序
从第一个元素开始，认为该元素是已排序的。
取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
  B. {! l+ Y3 z1 ^% w' T5 o2
5 \" `8 b) N; ?# y1 c5 \1 L9 \ ) 。


* @* v, F( U) [: K代码实现
9 j9 Q: T! `$ P" p1 v

# a! G) `# }' m9 W; R5 u7 xpublic class Solution {
        public static void main(String[] args) {
5 r6 P! @; j7 ]+ ^' O* R                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
! s9 L9 B8 Y. e+ H; q. D+ E                insertSort(array);
9 _9 n. O; ?% H+ v( O' m) t                System.out.println(Arrays.toString(array));
7 m8 E& w. [# U* k1 M        }


        private static void insertSort(int[] array) {
$ @( s4 a" i, G                for (int i = 0; i < array.length - 1; i++) {
- J4 h. Y, m" k2 s! W# b) o# A                        int data = array[i + 1];
                        int index = i;
  x8 J! I' ^( o1 z) A                        while(index >= 0 && array[index] > data) {
                                array[index + 1] = array[index];
                                index--;
                        }
* t0 W3 m5 O5 b% i                        array[index + 1] = data;
& g9 ]  w+ X( Z2 x6 A6 }" d. n1 l                }
; M/ ~' Y3 U7 ]9 X5 x        }
3 r0 D+ L1 e; p, Y8 C  m, [$ |4 |}
9 u( O9 T6 C1 W/ K: Z6 N1
+ W7 z* i4 f1 v- N/ @3 }2
3
+ Q/ m) ~# N0 R7 ~  }9 \0 b$ T4
( W; k& X! Z8 j' ]5
6
7
8
5 q  |! E& A  ^3 R7 q5 g9
10
/ ~5 h5 [  _/ T* D11
12
1 i( S0 W  o5 S% H7 `5 K4 b. U$ W13
14
15
. E/ ~7 W6 n$ \" X3 P0 u16
/ N$ D6 f) A. b, N3 ~17
. Z' v! \! S' t4 x6 W' ~18
19
希尔排序


# h: Y7 P1 ^% N( d/ t- {  f时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

1 K. a4 ?7 I9 W4 }. R
3 G7 C% h) p4 V  e) C2 b代码实现


public class Solution {
        public static void main(String[] args) {
; \; c$ ]/ K4 F9 b& X                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
4 N& t! p/ R6 r% c) y                shellSort(array);
( i2 s( ?* j. |1 T5 x8 k1 S+ \/ l4 T                System.out.println(Arrays.toString(array));
  n9 C4 \$ O$ X" h2 v        }


  r$ y" ?9 r  y! ]2 B  V! d        private static void shellSort(int[] array) {
                int gap = array.length / 2;
: R+ c: F9 w0 I+ y+ Y+ v8 U                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
3 L) {5 e! X% g- G* j) e( A, K                                int index = i - gap;
4 h+ S& U7 S+ {                                int temp = array;
                                while (index >= 0 && array[index] > temp) {
' S- c" f3 d& F! D/ M                                        swap(array, index, index + gap);
. S( ]) Y$ V+ R' ]2 J                                        index -= gap;
* [/ Y& M, E2 I% S* h( I! o  }                                }
//                                array[index + gap] = temp;
                        }
' |3 K/ `- u/ u- y" g0 N' A" N                        gap /= 2;
! A2 A7 E+ k9 ~0 E2 S9 A                        System.out.println(Arrays.toString(array));
                }
        }
! U1 g, _! l) y' d: O- n5 |

        private static void swap(int[] array, int i, int index) {
                int temp = array;
1 y, O8 |- f% N) c5 {                array = array[index];
                array[index] = temp;
% P: z; y/ B/ n0 B        }
}
1
, @4 F& J) l8 p" m  V2
4 ]8 c9 Z* y/ u4 Z, g/ b' E3
4
5
5 b) F0 |: X5 L3 ?6
3 V+ w6 w, @4 ]7
% S6 ^: B" k! T3 I0 {9 m/ m$ @+ n8
9
10
11
/ N% v+ D* p+ m: i4 W12
13
14
15
16
& d0 u4 q# [' ^& j17
% P# n; q0 n/ m# y# Y. n18
19
20
5 h1 ^7 z4 o7 Z21
22
5 n: l5 a$ ?( E, D8 h23
$ ^, Q$ o# x* ]- o9 P# J4 q# C24
25
26
9 N* s. x& W" y27
28
29
30
) _5 ~+ `" O2 v7 |  z3 \, n5 t! C选择排序
! G( X5 Q# Z4 {# }& h简单选择排序
5 R. ?9 U& y% v2 ?7 V# F从未排序的初始数组中寻找最小元素放置首位。
) m( m7 i5 Z2 w从剩余元素中继续寻找最小元素，放到已排序序列的尾部
6 w6 F+ |% i" v: j3 a( F  U& n0 J遍历数组，直至结束。
1 A  a# ?( w. |, q% S, Y时间复杂度为 O ( n 2 ) O(n^2)O(n
1 v2 a* L% B8 W8 q2 z& R9 ]2
( f4 s- L8 J4 P ) 。
6 [/ n8 g  A" V; ^, }- z2 \4 S

4 b. u/ H$ Q2 M1 t- w5 o代码实现**
( Z: A! p; _" m+ ?* u& L  O+ y

public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
8 I% S1 k% D( _$ Z3 P                selectionSort(array);
                System.out.println(Arrays.toString(array));
3 U- x/ ]7 j2 T, t        }
8 R) [1 n2 K; ]; r+ R

        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
                        int index = i;
5 X; T8 E: T+ ]( g% [                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
                                        index = j;
                                }
$ T: u* M* w, @7 @7 h9 D                        }
+ s2 T2 n  z# N6 e                        swap(array, index, i);
* Z3 Q; D# @" K5 m                }
        }
' n- q) A" C, A/ H  C8 |

8 s( }6 T0 c3 d        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
& e  f, }1 z% M4 F2 f4 j& j                array[index] = array;
                array = temp;
        }
}
1
2
3
4
5
' o+ {, A, A3 x+ w# ^6
- H4 m2 m$ }( Y' e' M% Y7
) r- s9 a  U6 o7 D: n1 }8
3 f; d5 i8 o" V& j+ V' W4 e9
10
11
12
13
14
$ w  ~: @8 {4 G  D15
16
9 C0 U6 A" x2 o4 y2 _4 U8 b17
1 `# Z" ^2 L3 n, g# }18
5 |# c5 Y& Y; ?7 q2 Z- B8 o, i19
  P, s. K2 p6 [8 g20
21
22
23
2 U! g# }8 i  B7 _5 J24
25
堆排序
; C/ C3 y0 t/ e2 n- V" o, u" U时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
' F' [& ]" e  [$ `+ ]  C0 F2 g- {/ e

代码实现**
- L8 |/ h0 R" k& \/ H" f
9 U* r8 V* L! l) Y* v5 i
* f) }( m0 u: T6 d; P9 Vpublic class Solution {
' k+ C( l: T! M* i! z        // 建堆
+ N! o; ]/ ~, `! n6 T        public static void creatHeap(int[] arr, int n) {
/ ^: z$ V2 a. a1 e                // 因为数组是从0开始的
                for (int i = (n - 1) / 2; i >= 0; i--) {
' D# K. @6 f5 x) b                        percolateDown(arr, i, n);
$ J& G2 p- k/ l6 U- I% G                }
        }
        // 插入
        private static void insertHeap(int[] array, int data, int n) {
- H  X! ^% F5 v  O  c                array[n] = data;
                percolatrUp(array, n);
% X) P4 Y$ O  X  j/ j6 g        }
        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
                arr[0] = arr[n];
# H. n1 B1 h' N2 E+ v2 m                arr[n] = -1;
. H: F) H1 |5 E* N/ O                percolateDown(arr, 0, n - 1);
        }
        // 上浮
) k' @# o: {3 w1 W; x* t        private static void percolatrUp(int[] array, int n) {
                int data = array[n];
) ~  O; {7 u- O                int father = (n - 1) / 2;
$ r- w9 S0 d% c8 F6 ~# o' T: \                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
                        array[father] = data;
; P3 e6 d  I% o) I# c% q7 c) H9 i- l7 t3 G                        n = father;
                        father = (n - 1) / 2;
                }
                array[father] = data;
        }
- w* P4 e8 D# V: Q7 G& n  ?! A, p        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
% h. b" l1 a5 r9 e7 _                int father = arr;
/ j- |0 Q; U4 T7 O# J+ H$ {                int child = 2 * i + 1;
7 l! P* u, G7 M7 F% [6 t# L3 K                // 遍历整个该根结点的子树
                while (child <= n) {
                        // 定位左右结点小的那一个
                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
/ W# ~7 m" B: Z# ^                                child += 1;
2 o9 W! f; j2 M) K* |( X, l7 I                        }
& h7 l' E+ z) {& }                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
; X" h7 Z2 f5 C1 k7 K                                break;
1 x* J2 L8 I+ g7 u7 F. l! Z- _9 N                        }
7 L1 \& q  W! I& m& _# c3 n                        // 互换根结点和子结点
                        arr = arr[child];
                        arr[child] = father;
* ]1 H; U/ b/ O$ Z/ V* b1 r& J; D                        // 重新定位根结点和子结点
                        i = child;
                        child = i * 2 + 1;
: n6 e: m3 O1 j7 A                }
        }
   
        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
$ s, ?' e! h+ b+ R) a                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
9 m7 f! c, ?* x6 C+ k  d* v- y                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
2 }7 N) A% _  H4 H/ l5 Q               
& [% D! {* |+ \8 f                deleteHeap(array, array.length - 2);
: {) c$ E& \; r. i1 U                System.out.println(Arrays.toString(array));
% ?, |% H$ A# O1 D# G               
4 B$ d2 j' @* @$ v, z3 }8 x                insertHeap(array, 3, array.length - 2);
% ?3 n+ P' J+ D  R. ^                System.out.println(Arrays.toString(array));
& K" f* W8 y* v        }
" ~& G$ b- R# @9 O& U5 ^}
! `& r/ }9 h( r1 X1
2
3
4
  ]- y  k3 c8 ^8 Q' y/ Z! T1 F5
; `: G5 j8 [$ k# I% r( L  |5 W( e6
7
$ h* h$ U5 Q5 R8 A0 W8
9
10
# U8 T" p& _4 I! ^) a  ~) c11
; c2 }+ n6 b' f1 h+ j12
13
! z# m8 \" P5 B! ?& t* a14
15
16
& o+ |1 {, h) r17
18
! x7 c' Y$ F9 x' v: t- O19
- g5 q# h% W( P8 e5 [2 j7 Q20
21
22
23
24
+ ^# O* {) @. H8 r25
26
27
28
7 h" M6 E- a% c9 v0 `29
30
: D& p6 R& R  Y  v- V/ [3 R% `31
2 `( k/ `: _  ]& J32
. r$ W0 J7 `$ ~, @& a$ H$ f33
1 `% W% x/ N1 R+ C% s- s34
35
36
9 O9 s& }5 K3 x9 K0 e6 O8 t37
1 u9 Y' K( M4 v2 J2 i38
39
  t+ R) x' R( m+ V8 V  Y4 O40
+ B; _' z4 w2 g; R, L; g41
0 O2 T$ g9 o) n7 H3 ?) d2 L" D42
% U2 K7 l4 c  X7 J5 L/ e43
44
45
' q1 A. Y4 A& @9 R" R7 K6 @46
47
48
6 p2 D7 C: e* A, d49
! {5 b# I" _2 g1 l) E1 M50
3 n7 D- @/ Q- {( J! s# K: y51
52
7 M# J$ l! W- {$ H" H+ X53
54
55
2 \, o8 n* V2 r  i- S6 }, E56
8 r/ O: n. v% {1 @57
. R$ ?' ~5 f1 Z' s6 x58
! Y7 I( m$ U3 n3 R8 e) n4 A59
. v% @/ j* @2 f! l6 V60
61
62
63
64
65
$ i6 ^+ [# G# y0 i- C66
67
68
5 p5 `  \' @! ^4 I. v- n+ `  v: j) ?69
70
# q* R0 o8 F/ ?' J, Q/ y交换排序
0 N: L: m7 h# M" v冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
0 W% x- V( W% ]* G6 J5 O遍历数组，直至结束。
$ I- P% R" q6 u: D. B4 x) `最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
6 S0 y8 ~0 i4 d4 } ) 。
- [9 g- z3 b" Z

2 G4 o% Y' _/ d) N4 s6 p代码实现
* i: R0 F8 Y+ S5 R* L1 J' ?4 e
- M; W3 S9 R: S; |( Z1 I/ Q1 f
import java.util.Arrays;
% r( B# H# Z  hpublic class Solution {
+ M- E! r) m  b2 n* B       
' \& W3 G' ^/ y% f8 C/ ^        private static void bubbleSort(int[] nums) {
                // 循环次数
                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
1 b5 h4 v) }8 T* S4 W+ p" v! u                        for (int j = 0; j < nums.length - 1 - i; j++) {
                                if (nums[j] > nums[j + 1]) {
                                        swap(nums, j, j + 1);
- s, {( |) a, K2 n5 N, w, {                                }
                        }
1 [* s  K1 q9 |& V" h0 I                }
% b/ N# ]7 M/ ^4 c0 Z" Q5 T& E/ S        }


/ [8 V! w" r1 O' h& y        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
" ^2 m( o4 v& U  m3 a' R  A" T                nums[j] = nums;
/ ^/ ?) E, b3 N* _                nums= temp;
! I3 ^! K' P3 |0 O  z( i& X. C        }

4 M$ y$ R  p: p; Z1 v" T7 |
2 V: P1 @$ Q7 T1 I. t: \        public static void main(String[] args) {
; a7 S* P" P; _2 A$ i1 b% ^                int[] nums = { 6, 3, 8, 2, 9, 1 };
1 B- f3 _7 @7 _2 s- P                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
        }
}
1
2
/ p* P3 {; Q' w' e# ^1 M0 ?3
: L! |2 u/ o: A4
5
3 r( M3 Z5 ^4 s+ w6
# T; z3 a. j1 N: w# h7
8
& @  c6 `& r3 I9
10
11
, `4 ^5 o/ S1 q, _12
13
14
15
: d1 T5 P; _5 o16
5 d+ r2 t9 H4 }( E9 u17
  A' c2 N( d6 |( E( F18
& {0 Y% P) n3 R8 ]" L19
* x$ p0 O- d, _3 s20
/ _6 y# l, ?: f( O# q21
22
2 _; B& ]: i$ Q: Y; I3 R  m23
24
25
; t- R! y0 F& F% G# r; x26
) o4 f, |3 ?" N( {) k" T4 ~1 K27
快速排序
) C' T/ \; f0 i2 e6 `2 [时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
4 t1 T: c0 ]; o% b2 P$ e

代码实现

( w: B: W5 A1 M
public class Solution {
       
        // Median-of-Three Partitioning
        public static int selectPivot(int[] array, int left, int right) {
                int middle = (left + right) / 2;
, u! E. W7 n3 G' B) i: Y0 t$ K7 {               
                if (array[middle] > array[right])
                        swap(array, middle, left);
                if (array[left] > array[right])
                        swap(array, left, right);
; G1 @  m7 `+ O! \: J( y                if (array[middle] > array[left])
' O7 W  h- J3 _- \5 v0 e                        swap(array, left, middle);
               
                return array[left];
        }
0 B% ~1 M* ^/ x: F$ L. ~9 J       
        public static void sort(int[] array, int left, int right) {
0 A1 i6 ], e% ]8 S6 o: B* f                if (left >= right)
8 [8 E+ O; E1 X7 G/ f                        return;
                int index = partition(array, left, right);
                sort(array, left, index - 1);
                sort(array, index + 1, right);
    }
. n1 b1 a. r% P2 h8 r* K       
' k  m- Z: b  C; `! ?( ]        public static int partition(int[] array, int left, int right){
        int pivot = selectPivot(array, left, right);
4 e3 V1 A' W! ]; L. Q* g6 M2 {6 J        while(left < right){
. t+ Z5 S5 S# p( b3 [" [8 C            while(left < right && array[right] >= pivot){
                right--;
            }
% T6 X( c5 Q' L            if (left < right) {
                array[left++] = array[right];
            }
            while(left < right && array[left] < pivot){
3 I' }; j8 m( z! l                left++;
" J6 N) v) \3 W$ g+ H& G6 U* @            }
" N0 s, S3 _. P$ d% ~4 V  H            if (left < right) {
/ d8 O/ p, ]1 z3 h6 X* U4 X                array[right--] = array[left];
            }
# f5 E; \& {) Q, a4 x# i        }
& d* z6 q7 V, ^6 q, x" B            array[right] = pivot;
        return right;
' P9 D, T4 S$ ~/ ]: c    }
( g" c' r$ d- J  X9 {. g# }1 Y

    public static void swap(int[] array, int left, int right){
            int value = array[left];
            array[left] = array[right];
            array[right] = value;
    }
' Z) Q4 U+ n7 i

6 [4 {7 e" Q; t5 J5 F$ O0 e        public static void main(String[] args) {
                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));
) m6 K+ C' z" r        }
}
1
2
3
" s5 c+ s) f" ~4 k) U6 `4
; ^: ^' \3 l/ y# R3 p) v' P5
2 g. W8 y+ S( a3 m' Y6
7
8
6 w  U0 K, z! x3 l( E& J9
: x  i; p( I. _3 ?! Q0 t# i10
$ E* ]1 `8 ~! b7 T11
/ M/ @5 |7 R0 t2 o3 r3 p; N7 y. t" K, \12
13
6 t6 k; ?1 D0 D, f" X. N+ T14
) n9 o( T; I, k1 b1 `! A15
8 I/ \5 |) o$ w; ^( Z2 m16
17
18
19
4 u6 i8 V1 B" X! P" ^0 z20
21
3 f& j  f" k# O3 F: g22
+ c$ c- g) Q: m/ U6 R23
4 x3 W( N& P" [, i  @24
25
26
0 K1 ]! s! M& b& `( F1 c27
28
29
30
31
32
$ {! l8 j" J4 U; o6 \) c* E33
34
) \4 G4 |' Y% ^" a( T9 l4 P2 b" P7 @35
36
2 G/ `6 I2 P9 \) g37
38
39
- Y0 L( W/ X5 v& d40
7 m& e# n7 |2 S4 C# w2 T41
42
43
5 j0 J2 z$ g1 P  m7 a* s: v44
$ s* c$ C5 Q" V* B) G45
46
47
7 L0 {% T* p! S9 O7 C! W  ?48
# e8 [. t/ t% T6 C$ N. N- J' u49
; u2 P9 Y: N" D6 j7 k8 h50
51
52
  P2 B, J2 @6 i/ D5 H3 ]53
54
# T% g- h% |) O55
56
57
归并排序
将长序列从中间分成两个子序列。
对这两个子序列依次继续执行重复分裂，直至不能再分。
3 `( }  y( G& h& W递归返回两两排好序的子序列。
$ \; ]+ Q: V& C; E; s平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
- ~, ]& u! x2 h

2 v6 g+ o2 m2 K2 X代码实现**


public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                int[] arr = MergeSort(array);
/ H* ^4 x# b9 [- N: I0 o8 t                System.out.println(Arrays.toString(arr));
        }

4 J3 B8 Y# V0 B. i' e
% G4 n) y, G- E  V        private static int[] MergeSort(int[] array) {
6 M0 ~3 f( Y+ W1 ^* k" X! u: D$ \                if (array.length < 2)
                        return array;
3 x$ c- r. V* z                int middle = array.length / 2;
% k4 [3 Q) o5 [9 g; j1 a- f                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
# H4 ^% w. L, u1 [4 f& n7 b7 ?0 U                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }


% h) m: b+ J. C- c/ R- H        private static int[] merge(int[] leftArray, int[] rightArray) {
                int[] result = new int[leftArray.length + rightArray.length];
& Y4 V7 k8 g4 Y2 F0 W7 w                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
# m( ]- f! z8 F9 D                        if (i >= leftArray.length) {
# e6 H, m3 M: L% F. c                                result[index] = rightArray[j++];
9 Y- l$ Y7 K+ g! n: T                        } else if (j >= rightArray.length) {
) W' M2 V  L$ r2 Y                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
: R" W/ U* Q4 a6 v6 \. }) p                                result[index] = rightArray[j++];
                        } else {
                                result[index] = leftArray[i++];
0 {0 S. t; w- @! f  ?$ z                        }
                }
( R$ j) |8 E4 ^# Y" B/ N1 z                return result;
' ~5 C* Z8 V, J2 ]3 Z        }
) v: y0 H8 w* O  u7 T}
" \" {$ [+ C0 n

1
2
8 V2 ?- T7 S" ?* k5 L3
" e# e( w. ]+ F  E: J; t4
5
6
7
8
9
4 Y' v" F' F4 R10
) m4 a  _- r# j+ ]- x  r! g11
6 o0 N3 ~" Y& R9 @& t12
13
1 U8 [- p. D  c  r' i  M! @% Q14
7 n6 ]3 o& {- }' O6 Y& u1 F15
16
4 A6 p% c8 U( ?( V4 D, u: P9 C1 w17
18
19
) c7 U6 Q6 f$ f+ U20
21
22
23
- B8 c: t2 f8 |0 |5 h5 ^24
25
26
27
28
" c3 K. F8 S! Z) a29
3 D# q# i6 g3 J0 _/ H& C) n" T30
, W- b4 G7 j; n+ R; X% {31
32
33
& d- F0 g% o2 V基数排序
/ `- @: \6 p' \! Y0 i- Q4 I找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
* u: B5 i$ V6 ]/ Q# Z# u; s时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
6 m8 C8 l& _0 ^- @% O% X$ c$ ~9 x

代码实现**
% @6 V: {* K  }7 a0 m& r

public class RadixSort {


0 P) d- B- S4 A0 T/ b9 W) @        public static void main(String[] args) {
                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
) d- K1 N, O6 |/ n. z& G                int[] arr = radixSort(array);
                System.out.println(Arrays.toString(arr));
        }
) Y9 N. V( |* U

        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
" t" E) ~  A! Y. o& d4 \                        return array;
                }
. T' d9 j: z* \. U5 l9 L$ R# Y                // 根据最大值找到最大位数
6 |) q7 i. v7 R* J  ?                int max = 0;
                for (int i = 0; i < array.length; i++) {
$ d6 x/ {7 E5 ^2 f+ B: {! h                        max = Math.max(max, array);
* Q3 u. X) ?7 O7 n2 D1 |8 @                }
               
                int maxDigit = 0;
                while (max != 0) {
                        max /= 10;
                        maxDigit++;
4 z# j0 _4 H* A4 D$ Z" v4 d6 I                }
               
2 v" c# v" V  k8 K" t                // 第一维: 0~9
* z4 Y% c% f5 S" E( \, f$ O  w" o                int[][] radix = new int[10][array.length];
- q& O) U  ?- ^( x$ E. b                // 该位为 i 的元素个数
5 V% k8 W9 W9 |, z$ ~* L9 D% |0 ~                int[] count = new int[10];
               
' v8 m2 o+ T) F8 T: ~0 W8 [" \                int m = 1;
                int n = 1;
               
) e$ t# t, k$ T- o3 P& m  u1 {; n                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
( M& ^$ J3 O! U" t* m                                int lsd = (array / n) % 10;
                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
                        }
                        for (int i = 0, k = 0; i < 10; i++) {
/ N1 ?, z3 o) L0 v                                if (count != 0) {
; w- s  t5 I7 R9 e                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
                                        }
                                }
( g) y# Z  _" I                                count = 0;
                        }
                        n *= 10;
                        m++;
                }
                return array;
        }
) E3 C6 ~1 v/ C3 }2 P

8 |5 V  j$ J5 y' ]! b}
) H1 e# o2 N4 I# w, \1
4 w# @" Q$ q: ?( s1 o& r% O2
+ r3 v7 R9 V* X4 G2 O* {& j3
4
" b3 E5 X5 P( _# r; H5
9 o0 N' C. Q6 w5 _+ e+ M6 c6
7
+ M4 o: ^  E  ?+ b" }' T9 t8
9
& Y# A9 v3 ~% m3 D/ x* k9 L( m10
11
  ?6 k! {7 ~! e+ d12
13
14
15
16
17
18
19
20
/ `- z+ b0 _7 C. c* Z) C21
) y* U1 H+ E. ^, U22
+ N- `: {: {0 g' }23
' D. k6 w- G/ T24
/ a) q& X+ X8 M9 l" J" B5 y25
. S0 M& L% o+ T! @26
27
28
29
30
31
32
- {1 \3 W* o) u5 h7 U33
* I: \4 B% y5 u% A3 z5 C$ q8 n- p34
35
36
, B2 ?, i7 F$ d) ]; U$ z0 q37
- \% f2 R6 }  E+ A38
2 f3 E8 G0 h$ c8 H( v0 |2 s, B/ E39
40
5 c' ^- ^! Q5 d8 K% C  w7 f; h41
) Z: L9 j# P" G+ B42
: _/ x4 [2 f; j% o43
/ ^) E- @" m+ D0 D- r44
" q9 w( G' ]$ v, Q0 B4 g45
46
47
2 w% C& o2 O. y, U# B  t48
49
9 T( ]: c, l; P8 C4 i4 C6 v" u5 ?50
51
52
3 @- F' P0 t& d9 [# w53
* @/ [4 q+ I+ g( `! G计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
/ S$ F7 f$ m. r7 h: L4 k6 q9 |统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
: T; {: e# z+ g, r+ Q$ ?时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。


9 k7 ]; q8 [( j. _/ y0 T6 @代码实现
. j: o# X- V" R! w+ D0 F

) ]* S& x# Q1 A; f7 n- vpublic class Solution {
+ U( U/ r# R0 v0 i( Z

        public static void main(String[] args) {
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
  k3 e" F* d# X* b                int[] arr = countSort(array);
# \1 {7 X' ?  J, ~6 n5 S) g7 a( S7 @                System.out.println(Arrays.toString(arr));
        }
$ Z2 W4 y+ q; R, X7 A9 b0 v$ b* C
3 V6 r* t% w* ~
        private static int[] countSort(int[] array) {
                if (array.length == 0)
                        return array;
               
/ J. |$ _. p6 N; b5 N. V                int min = array[0], max = array[0];
               
                for (int i = 0; i < array.length; i++) {
1 g$ }5 w0 {  B  d! q& ~' P$ R9 V                        if (min > array) {
& }/ Y+ [2 q! v+ J7 c9 j                                min = array;
                        }
: J! o. `  q+ U' O8 Z+ N5 a# S                        if (max < array) {
                                max = array;
                        }
- I: t+ \& E5 a4 j" ?9 X" Y8 \+ S+ A                }
               
                int[] count = new int[max - min + 1];
* d( j; e" n1 o# k% V               
                for (int i = 0; i < array.length; i++) {
                        count[array - min]++;
                }
               
  g' r' _, k/ x                int i = 0;
                int index = 0;
7 t% \0 Z8 U" X3 p; f5 E/ u& J. M+ G                while (index < array.length) {
                        if (count != 0) {
                                array[index] = i + min;
                                count--;
                                index++;
                        } else {
. X+ y" |" W" S                                i++;
* C, H  k1 y$ t6 r- T                        }
4 F6 `+ m" ~$ h2 u$ Y                }
! }: [: ?- \) Z8 T* P* z6 A" j# Q/ q0 e                return array;
: a# N* z+ u- \; L+ X7 [6 c        }
9 K+ J& o  G4 ^" ~       
4 b4 T( l  D: x* r* t+ U7 \6 y6 y) k}
( {. S, C3 m8 V; P+ M" z5 J. A1
  D, ?7 h) z8 V2
3
3 I. e& @0 ^( K+ D# g4
: d+ M# R9 j( _0 i5
7 G# l# r3 N/ B) f- r( `  _; f) F6
7
8
9
; F% _0 t' t; B# c  z10
, t$ L: c( M# M) S! {. S6 g11
, e( g# i: n7 x' |$ Y- t) k, z# V12
13
: L, u6 S3 _) G7 y/ m8 v14
' F: N& o4 u5 d, `15
/ O$ m2 n, {# H  g2 d16
/ G7 H  W) N6 R17
18
19
20
! V8 V# o3 {. z, ~4 w1 [21
22
% u) x  b9 U$ l23
8 c) P# @6 ~! |/ K- g24
25
- t. u' b) y7 U, s0 T26
27
0 P" p+ S* u" X2 f5 x28
0 ?$ o* I- d0 {* @; `; D29
4 X- |* o# k; e* f: Q" Y! [30
% }) D2 Z2 a3 n) l2 W8 ]31
2 p8 l9 Z) p1 @& |) \& ?; \32
33
34
/ s8 m6 J: o" _35
0 o4 Q" @: L, M$ E2 g; Q36
37
. n$ K8 g. j( `3 s2 [+ y1 I38
$ ]) O3 f9 ]4 J0 d) P# b  m8 p6 U# l39
7 @* W  M# {8 z% O! A- R$ q40
41
4 v  ~6 z" j! g9 k5 S  R: q42
! T+ R5 U& i' [6 {! j43
44
桶排序
2 D. w. r4 T" s9 P( x8 b8 a4 v————————————————
. x5 ]% W1 A3 J8 ?版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153