十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）

# V! i" c4 X( u1 ^& D5 K十大排序算法（Java实现）
排序算法框架
排序算法性质
/ k& `( u) j& P8 q2 Q+ p  R插入排序
直接插入排序
希尔排序
选择排序
简单选择排序
堆排序
4 d( {6 _7 v# {- x3 q交换排序
冒泡排序
7 a- U. P5 T  @$ }快速排序
归并排序
基数排序
计数排序
桶排序
更多文章点击 >> 这里
# }9 Z# N+ e3 N

* u& a7 V: g. T& P& c  n! G排序算法框架




排序算法性质
" J$ @! V9 H8 t- ]

1 F, T+ W* d# S' i  V

插入排序
: G0 F2 G* m7 U' Z1 B  @& ?- c直接插入排序
/ B8 W. \* [8 I$ }4 ?* n从第一个元素开始，认为该元素是已排序的。
1 N, |' k; B' o2 k+ P取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
! B; e1 k  Y' \" a遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2
9 a/ i7 P; K' t# o ) 。


代码实现
8 E. n$ d8 n, @, \* R- c2 S

public class Solution {
7 ?9 Q& Z- e2 o) J5 F/ u; Y        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
. Z# U! n+ M6 y' \" d                insertSort(array);
" n% s2 ~" i0 I                System.out.println(Arrays.toString(array));
0 U3 D1 j9 y6 q% X        }


        private static void insertSort(int[] array) {
1 ~7 ?6 _5 y. ?8 l$ r. }7 h                for (int i = 0; i < array.length - 1; i++) {
& V! i* x6 q/ X5 X0 n                        int data = array[i + 1];
                        int index = i;
7 X7 l9 m" T1 p% o                        while(index >= 0 && array[index] > data) {
5 F9 H  o4 I0 |* O7 l- z                                array[index + 1] = array[index];
" k6 D2 W4 h/ D$ }4 V                                index--;
4 T. B( T/ s5 k3 X$ R                        }
7 N& X% R2 ^1 T" j1 z                        array[index + 1] = data;
                }
        }
}
2 L/ L/ E3 M6 ~3 _9 i1
2
3 O8 T/ L: y# P) E3
4
; ~+ _5 N! E" h$ W; n! a5
6
7
3 W. }1 ]8 C# r4 n8
- t8 U+ I. ?( `9
2 j7 z! f+ q. S2 f10
11
12
13
+ p  i: A: }) E14
15
* }2 m- Q: X8 _( c. X4 W16
17
& x- m: v, Y: m" W; L( c* Z18
# F, R; y# Z% u! m! p& O19
希尔排序


3 C1 |9 u' A% O8 a" [9 v7 s* r时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
" l1 ?4 J3 k. v( j

代码实现


+ G4 [4 W; i1 n' R1 Ppublic class Solution {
        public static void main(String[] args) {
; C* h+ X1 U) a! h! k% ^' s                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                shellSort(array);
% \! C3 h2 P3 |6 o9 ?                System.out.println(Arrays.toString(array));
6 R+ t( y  ^2 ~' ~+ X. L+ t* S        }

7 k  {4 M% a/ U# L* W/ n6 D6 ^# C
' p) h8 z3 [1 u+ |7 G        private static void shellSort(int[] array) {
                int gap = array.length / 2;
                while (gap > 0) {
  |9 z% o# r1 r0 }                        for (int i = gap; i < array.length; i++) {
0 L# T! Y0 B* v; [$ P9 h0 c6 @% m                                int index = i - gap;
                                int temp = array;
6 W, D/ X+ H& ~                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
6 Y/ {& M3 s0 d: f                                        index -= gap;
. n4 E' p# B8 k; J: X                                }
/ j' w" q1 U' q- I" U//                                array[index + gap] = temp;
3 Z4 F) N; j! ^, R. a! F" q0 s( W' d                        }
# u9 ^9 D; o& H* O1 M) L3 x+ o  O                        gap /= 2;
                        System.out.println(Arrays.toString(array));
$ O( Y* G! p8 ~' }* d+ \+ z6 B2 y                }
- j& D7 `1 @) ?        }


1 z1 t% J0 Z2 ~: |4 P- |        private static void swap(int[] array, int i, int index) {
                int temp = array;
                array = array[index];
& U7 G+ d% c6 i  N                array[index] = temp;
9 }0 y( K4 H4 r4 V# v% m        }
}
1
/ }2 N6 T7 z, E8 F6 {2
3
4
& D# ?  w' @+ a- ^5
6
7
7 H; f& {" C1 v; j5 M* n8
% }5 i/ Q$ S( k9 u: Z, l% t5 _. z' E9
10
2 a" @% d5 R$ b0 k4 t7 Z11
, \" F( U0 l' c, A12
  [1 E0 X' K* t9 A" D7 [1 `13
14
$ t' d. x6 @( Y) q' j0 n# {15
# Y) `" o. ^, E  T6 z1 y" `16
17
18
19
# l$ L+ K0 `/ p20
21
1 G) C! d! F7 H  \( M: u5 ~22
23
24
3 Z4 C* d' d) U/ X( n3 u' F25
( H* J/ j) z0 u  s' w26
! a2 i5 Q3 x) y  Z/ }. {% W2 g27
28
29
30
* D7 O0 w" B* k2 k0 {# K- f8 f选择排序
简单选择排序
" W4 w" ]5 B: D4 H从未排序的初始数组中寻找最小元素放置首位。
从剩余元素中继续寻找最小元素，放到已排序序列的尾部
/ j, A+ C$ [" O. U% _( V" V" S遍历数组，直至结束。
时间复杂度为 O ( n 2 ) O(n^2)O(n
+ a$ r5 K- r+ K$ I0 T# V# n( f% e2
) 。
6 M* K" F- W" a; J* @

代码实现**
  c" Y0 W. S' J, ?: i

public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
. O: @+ ^! G+ ]$ y& E( j                selectionSort(array);
                System.out.println(Arrays.toString(array));
        }


        private static void selectionSort(int[] array) {
" ?6 t, s2 X; m+ b3 t0 t1 i                for (int i = 0; i < array.length; i++) {
                        int index = i;
- q- z+ }( {$ u( M% ~3 L7 k                        for (int j = i; j < array.length; j++) {
% @- U+ U8 S) d2 N4 W  Z3 x/ s5 U                                if (array[j] < array[index]) {
                                        index = j;
, x. B; H( v% @* J6 d& V                                }
3 `5 r7 c/ v+ G, t4 l; B# |                        }
                        swap(array, index, i);
( c8 Y$ Y* F$ C                }
        }


        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
9 k' T8 \+ b# t+ |, p9 p                array[index] = array;
                array = temp;
        }
/ `' p/ _5 l- m) I( X3 s; N& K}
1
, P( I! p+ ^5 Q. O% l' T2
3
4
# L4 g, g4 R2 L7 i; r5
: q# j  m& P9 b3 I% ?6
* |5 K3 @/ T# e3 O' P) h8 d7
8
( x" w% J) B3 G9
10
$ O  P6 T/ t6 ]4 @& O% R11
: E  v% m  E" v! [. e12
13
14
15
16
9 R& {6 b5 W! C17
* k8 S2 `+ j! R18
19
$ V8 Y. M# p0 E; a% s) ]20
21
22
/ c% Y+ n: i6 }# ]1 C% r, z' W23
" x. p5 H) m  z. {. p4 E24
& q# u0 e( j2 I25
( r, C# F" i4 f堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
4 Q7 j( d- a4 ]: R% x% @

代码实现**

0 o6 p; t; [: T# v. Q) ]9 X9 X8 Z
4 T  ^- `: j6 q  q, C- Fpublic class Solution {
        // 建堆
0 `5 ^$ u) J) v        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
                for (int i = (n - 1) / 2; i >= 0; i--) {
                        percolateDown(arr, i, n);
: G8 Q0 n0 r- P4 Q0 a- h0 y8 R                }
, Z9 j7 t0 ^0 ^& o/ a$ L* e        }
' Z7 `' z, s* t  C" ^/ T        // 插入
        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
- I' K/ u" H! ?: F  B- Q, s1 ?6 u/ A                percolatrUp(array, n);
        }
        // 删除栈顶元素
0 V1 Q5 }5 `& P. \. I        private static void deleteHeap(int[] arr, int n) {
& I! u4 H8 h/ v5 d                arr[0] = arr[n];
                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
        }
- M6 t/ [% n/ M  Z        // 上浮
        private static void percolatrUp(int[] array, int n) {
                int data = array[n];
                int father = (n - 1) / 2;
- v- Y6 @" z1 [+ z( f6 c                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
                        array[father] = data;
                        n = father;
                        father = (n - 1) / 2;
                }
: d+ i! e( A4 a- g$ |                array[father] = data;
        }
5 V; m+ [) U' P7 e$ Y6 Q6 z        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
. ^7 }  R4 }0 x" g  h2 m                int father = arr;
6 D* M' I' R# A+ T1 m# T& u# U                int child = 2 * i + 1;
# B) N8 [5 L" [, c& t                // 遍历整个该根结点的子树
) a  P% x: n( h8 E                while (child <= n) {
                        // 定位左右结点小的那一个
/ N) S# o1 ~! b8 V                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
- @" {7 T1 L% j( r( t, S                                child += 1;
! P" V$ u% [: r$ p( W' T3 S$ R                        }
8 M( e' l6 P: @! P! ]0 s( {) F. v                        // 若根结点比子结点小，说明已经是个小堆
! H  P: j* k( T  B$ Q8 @5 e                        if (father < arr[child]) {
                                break;
+ Y& J. }( [- g' v/ W2 T/ o                        }
                        // 互换根结点和子结点
                        arr = arr[child];
1 M% x7 ~( c5 v0 e' p; b  s5 |                        arr[child] = father;
( h7 O+ m1 {' {4 ^( D# d' p                        // 重新定位根结点和子结点
2 m& Y# T4 C9 D7 c) e! D- p  ]                        i = child;
, M8 A  v" a$ u* T) u' x                        child = i * 2 + 1;
. z3 a" z. d5 y                }
        }
   
8 s- z" ^* `! ?- [; f2 q        public static void main(String[] args) {
: I% i( `. I* d4 e                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
2 V. @) U% z* ]% h! Q! |               
                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
6 K& i/ |  @4 U+ G( D                deleteHeap(array, array.length - 1);
' J! d$ I) B4 ]                System.out.println(Arrays.toString(array));
$ F" j0 C# Y9 c6 Y               
                deleteHeap(array, array.length - 2);
+ @; n2 s1 p$ c                System.out.println(Arrays.toString(array));
4 a, ?8 _# k3 n/ \0 P. _7 m               
- @2 h, p! @* a/ D/ }) f# x, ?                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
8 ]; P8 k! @6 ?0 \- t        }
}
6 x" R5 Z) O. S7 N' F1
2
3
4
$ x# o" X) t& I: _) P* S! N  i3 @5
, q( v# g' E; V$ A3 i6
8 G3 N, o  S$ \4 o8 n; L- f7
, \- S/ A& V4 p- N8
9
& y% v0 C8 y' U! F* m7 g9 _! M10
$ C6 b  a2 ?; \/ F11
) D9 M0 |3 j' o! p12
13
4 U4 l0 N2 |$ |. F0 e6 `14
7 s/ M2 R' {) I% R15
16
  q4 ?* x' M# D. Y17
18
19
, h4 e9 |( e% M: U4 a20
2 ^) M( c8 t5 a/ A; S6 a21
) ?2 l. r1 \" ]) K: P* a22
# g5 d2 H1 E0 y/ p9 S( E; A23
) v% g8 o# C1 b24
25
26
27
28
29
5 x3 Q' U/ K/ F2 X- B' Y; F. |: ~+ K6 ]30
7 I3 }6 T$ L7 L& Y0 O0 f7 \! [31
0 z$ r4 A+ x! ~2 R4 l0 {32
: ^4 |( \1 w0 j! g: f/ X6 m33
34
35
! N$ ^% U. J$ T5 ~% a* d) x5 e$ N+ @36
3 H) s( d/ w/ A: v37
4 k7 _  V2 z: A  e8 I4 f) `; e* U2 I38
1 {( R) v8 e- f3 U5 A" K. p  v39
40
/ o: ]$ B8 h% n/ I: S9 y41
9 r; n* l$ G6 e2 o" l! |. b) P42
43
8 I* `+ _0 f) Y6 c2 m) f8 O44
45
% V+ q/ w; H2 }6 N7 n% u. G8 f46
47
6 [$ [" d! r. f1 X1 J7 g+ r$ D3 _7 C48
49
& x# l+ E% [+ Q8 v/ J50
8 ~7 n/ p& |( F6 u51
! ~! S* }! L7 f1 J6 t/ E/ q, ?52
53
/ v9 P5 I% p, a/ S6 A2 c8 z7 |54
6 ?* Y* s! w3 z2 A4 ~55
% w0 k4 L# o5 j# P+ ], Y* r56
; |, }# Y# e+ t7 h; o* _57
58
59
60
61
62
63
- W+ i& |( }3 n3 Q' @# m% ~) w64
65
66
67
68
69
0 ^! H' J' ~8 A5 @70
" z) v* Z$ Q1 v4 b. z+ P交换排序
冒泡排序
- C- B& A/ q2 ]) a: }  k$ c& Q6 e" \依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2 t) ^, X- H/ ?9 c' z2
) 。


2 p" w# {& a" _- Z代码实现


. g( ^  b$ C* C% W2 Cimport java.util.Arrays;
public class Solution {
       
5 h5 Q& V4 L6 ~3 J8 e& J        private static void bubbleSort(int[] nums) {
# k* @+ Y' m  V3 j- u3 c  W                // 循环次数
2 {7 T9 z8 ~; [0 `& l; s                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);
                                }
                        }
                }
: O0 R! F3 t4 u        }


        private static void swap(int[] nums, int j, int i) {
, C2 f) {/ w4 V! y& e5 Z" C                int temp = nums[j];
8 ~" ?9 \3 M* y                nums[j] = nums;
                nums= temp;
        }


        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
6 E; m: p  ]" M2 K                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
. e, I* W- G) X2 e: Q  I% {7 G        }
}
1
2
0 t& o! J  \, K+ w: P" J3
' s( k9 w4 z4 [7 a4
5
6
7
& d0 \; J: f# m- g; I6 G4 @8 H8
, S$ I* }4 A/ }9 O8 X2 j9
: R7 y) M, u! s  R10
1 \3 A* ?# [2 I7 i' p- v; h/ e11
! \: m! w: P5 x4 r  S12
13
( w+ W, K0 C' p% B- O- d14
# a, }0 ]0 K) I3 P1 _15
) r9 `; e& Y0 Z+ ?7 C16
17
" R. t. X: r, r* `18
$ U! v2 {/ D- Q. A8 _% m2 w* Z19
6 H3 w& w! ]( j9 D" ~  z9 ?20
21
( b3 ?' r/ ~. |8 ~22
+ w' w$ |$ ~: K$ s* b$ O' d5 `4 m- D23
: E* |/ k0 }4 I7 a2 M24
25
26
/ U& `9 \- G7 h- n0 G5 m: v* z27
  F$ t/ z/ ~3 e8 V快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
, {! I8 n0 z9 A4 r) M& a

6 q* Z+ C; P" r代码实现
! ^& T/ {4 K: E- `) {$ ]6 C
  ~/ ~: ?5 ?& b; t# p
# s  _' d2 }  Y: p3 W' P. wpublic class Solution {
$ i8 O( G& K4 a0 [1 [8 ~       
        // Median-of-Three Partitioning
' @' H4 m9 f! f+ I        public static int selectPivot(int[] array, int left, int right) {
  z" u( l* X9 x% o% ^$ q$ u                int middle = (left + right) / 2;
               
                if (array[middle] > array[right])
                        swap(array, middle, left);
; B5 e4 y# o8 K% l( K! G1 n                if (array[left] > array[right])
                        swap(array, left, right);
" @* A5 g2 R9 J6 b6 }" V                if (array[middle] > array[left])
                        swap(array, left, middle);
               
                return array[left];
' t4 X+ `% ~) p) z  ~* H! ^        }
       
% A6 l' f3 S1 T$ N        public static void sort(int[] array, int left, int right) {
                if (left >= right)
                        return;
                int index = partition(array, left, right);
                sort(array, left, index - 1);
) p2 U/ i! J9 s% b                sort(array, index + 1, right);
* o+ I4 B# s/ t1 p    }
       
; q: _0 z; [0 G: l9 A        public static int partition(int[] array, int left, int right){
! o$ {6 I; @8 r: R8 U6 p        int pivot = selectPivot(array, left, right);
        while(left < right){
9 k& p0 D- S4 |7 A: Z+ t/ K) X            while(left < right && array[right] >= pivot){
                right--;
            }
            if (left < right) {
2 q4 U. ^& r6 M4 H                array[left++] = array[right];
3 r7 F8 n( H" ]$ P, ^9 D* g            }
            while(left < right && array[left] < pivot){
) g, y) ~! o/ i                left++;
            }
7 f! B9 u4 K6 M6 Z, r            if (left < right) {
+ d& B$ [7 K$ V                array[right--] = array[left];
3 O8 M( w& U. a1 E: S4 o. ?            }
        }
! B* \0 u6 Y- c& i! A* V            array[right] = pivot;
& g6 [! p( n) s; C        return right;
    }

/ z" g9 O& D( a
    public static void swap(int[] array, int left, int right){
            int value = array[left];
' W$ |7 L4 j. T            array[left] = array[right];
2 a% ~' h, I  i# J, a            array[right] = value;
    }
( u" r7 b" T5 j5 R7 _" V: ^
5 X+ o$ \# N" 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));
$ p- o- m8 S4 F2 D8 C; G8 ]* m                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
/ S: W5 ]# ?8 L' F- v        }
0 ?2 S! h) z' j& _1 `. Y}
. Z+ g8 R% c( {6 G* F( [( A, Z8 _9 V1
; A2 h2 s& l* \- Q. g$ t0 F3 _2
3
4
- I. \( J) Z- P( |6 F! c5
6
7
8
9
8 _7 _: c. o0 f+ I( v: G10
11
12
13
7 n4 U# p) f! f4 `" j7 e1 [14
( }) n$ y# l6 u( v7 a15
16
17
, N( `' W0 Q3 H2 K3 S( @1 A" B% A18
19
7 i2 D1 w7 M! W  w7 P3 o. b20
$ @2 D9 D- O4 n6 P8 }' b( M/ L21
; {% c0 [. j8 u" B5 T6 U22
9 z, K- a$ q: J( J3 D23
24
: V" L/ c9 Q2 s/ v* U8 T) P25
5 o5 w, O$ i0 U/ k' P26
27
28
8 S& M& I5 R4 q* a/ q+ x7 x+ C5 H( w29
+ L1 P- H/ ]1 o1 K" g; n1 q  D30
+ Y6 t9 E  i" c% M- T31
32
1 J; L% r4 A6 B2 M33
34
35
36
' T0 ]/ [2 x) n' @, }$ x37
38
39
40
9 g1 C$ Q  G4 w, F& c# E% }41
' ?4 W% y: `! i, w  z8 m42
43
0 `' C4 o5 p/ j* t7 e7 C3 o44
9 `0 L" O) _1 ?: E0 T45
  ?0 p5 e, W4 M* b2 d$ T, k46
47
9 C! O# `/ J1 j  T- R$ H48
49
; J: Y6 h0 P$ L50
51
52
, u+ G# _) S. u  M" G' ?) [3 s53
$ v- i$ r/ i. H. F) t- [8 c54
/ U. l0 N9 G& R55
$ R, [+ a. X9 b9 C+ ?56
57
$ c% ], l) O* u0 k' }归并排序
, H- ~6 o" M1 y% a( i将长序列从中间分成两个子序列。
; w5 G, k4 A4 S6 x9 U对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

5 D, \3 P$ k8 ~& M; U
: l0 N8 _  h  z% G) R+ C代码实现**

) r# \2 \; B' n4 |
- W2 w" G4 y6 R& B, c  [  w- Spublic class Solution {
        public static void main(String[] args) {
8 t  u* k- |$ i! y( d7 W                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                int[] arr = MergeSort(array);
4 J8 i: }, @. }  a                System.out.println(Arrays.toString(arr));
        }
1 {6 g' x+ [& c+ [& c
4 X  K0 {$ u) R+ h% r9 c
        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
                        return array;
; H9 C  v1 W# A1 H0 I                int middle = array.length / 2;
0 g9 T  i8 Q" ~+ U, }. P3 E                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
                return merge(MergeSort(leftArray), MergeSort(rightArray));
  v' q7 g. ?) N* V- a5 u        }
" F2 {$ q! ^8 X! M/ Q9 k! r. Q
7 T( C3 Q# f5 o$ T: e
7 ?1 x) H5 h! ]+ q# D/ [: R5 @        private static int[] merge(int[] leftArray, int[] rightArray) {
2 Q; ~+ q' G" f& I; M+ H                int[] result = new int[leftArray.length + rightArray.length];
4 u& o+ G' l4 C! l                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) {
* ^) L4 g( y/ h8 y                                result[index] = leftArray[i++];
' [8 |! `- C% N' H8 \$ m                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
9 u( h9 H9 [7 ^* q; x; U4 J) m. `, {                        } else {
                                result[index] = leftArray[i++];
                        }
                }
9 {# G) o* H( ^' m2 Q* j0 l                return result;
; ~/ |1 Y8 K* X) u        }
2 J5 n+ J5 k1 l6 [& c. P}


# I% B; ?9 p* ?5 ~7 _2 m1
2
. r. [/ V. J; `- g5 R! \3
8 v4 ?$ Z) [! m( |" H4
5
, H0 {$ P! ?! M6
7
! K- B+ ~4 f* \8 V# k1 q! t) `8
1 L/ E" M0 e$ R7 l8 I0 ]  S9
10
+ d) a! M# y9 M2 E9 {/ b11
12
! Z" ^" R! u$ S9 r0 m6 G13
3 |" f) g* H1 j. @6 }14
8 Y0 r+ t4 J3 Q15
1 G4 [+ D4 D9 }: f2 }) ~16
0 T, l8 s0 H! P8 J% S& |5 H, O+ ]17
18
19
, Q* }' X1 u! c7 f20
% f$ n$ W. j# J# T& P9 t4 n- P1 I21
22
23
24
25
26
27
28
3 N9 S8 r+ S3 s. l0 R# v6 `6 l. A  F29
" O, T# u9 l. C* g7 p9 W4 W30
31
* s2 B1 e' @* T/ L. }8 M7 {) x8 `32
& L3 g. k3 z: t* q$ e8 E9 H33
0 D: F0 ~4 ^3 t% h9 V3 U* i% T6 J基数排序
9 V2 Z+ l0 f/ |% ~6 Z找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
1 L- B1 W, |: e9 C时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
  o- k. a  c$ Y& h
0 Y5 x! s* j' {+ S3 z. B. R
代码实现**
- s) y' G  z  A% H# r$ m

4 e3 J, v" j  i) Z( F2 P& G5 ^) Zpublic class RadixSort {

" ^1 S' h) @# Q
        public static void main(String[] args) {
+ X' l: _  B8 U' O4 H$ e) J                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));
3 f; s) i8 ?& N- u$ Z4 @        }


0 }' ~- j; ^  \7 `8 L1 {- `1 z5 a8 B        private static int[] radixSort(int[] array) {
: I7 W4 h  ^# ^3 F3 L5 X) H                if (array == null || array.length < 2) {
4 i: o( Q- T7 j) i- o5 T                        return array;
3 Y: q  R) C% Z0 U' k                }
2 }# }' j# f. [& U0 Q2 J* X                // 根据最大值找到最大位数
                int max = 0;
                for (int i = 0; i < array.length; i++) {
9 L1 _- z/ J4 W( u: r, ~                        max = Math.max(max, array);
% I. L- q7 Q& t$ ~* u                }
/ t- x. ^6 f0 b5 a* [+ \+ R6 s               
" F6 N4 p  }; @( A. ]                int maxDigit = 0;
                while (max != 0) {
                        max /= 10;
                        maxDigit++;
                }
  U9 `& ?9 n1 X) r& }2 C1 Y# m               
                // 第一维: 0~9
4 g  K7 A1 j- X( S# C                int[][] radix = new int[10][array.length];
0 l- E6 v" @5 X. v, o1 `                // 该位为 i 的元素个数
, y- K& m+ K5 B! w                int[] count = new int[10];
               
" w" q; H: F' _1 M, F8 N                int m = 1;
                int n = 1;
               
                while (m <= maxDigit) {
% T8 h  A4 s# L) D. {9 z- O                        for (int i = 0; i < array.length; i++) {
2 f) Q: t( N1 r7 j9 o) W. p                                int lsd = (array / n) % 10;
- v1 K  y( n  M0 z2 q                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
4 R- N' T' \2 \+ ]/ Y( r                        }
                        for (int i = 0, k = 0; i < 10; i++) {
1 \" j- a( B) o' r# I% c% w                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
                                        }
                                }
% P. A2 u* z! f# J5 W! `                                count = 0;
                        }
2 u' `% }2 r4 |; _                        n *= 10;
                        m++;
                }
                return array;
        }


: s+ Q: E  N. E" f( ?, w/ }}
1
2
3
; _4 v1 V- a! c2 b( ?$ z7 K4
5
6
1 U8 [4 K$ `. N8 v1 B7
8
9
10
9 d3 a2 o3 A6 X* `! n  F* D11
; C% \. V& Y. {- J, d$ M% H" d8 P12
13
14
15
16
7 r( x( N7 C& M% |5 z- U17
18
* i9 j0 n+ O& q3 \* E19
: o. s9 {( [- k) @* L20
# Q+ b7 M. N* X: _1 [- e21
! B5 q% c& Q4 {( ^22
23
0 M8 @: L5 i3 e" f) V! \24
( s, X) `3 c6 b# @& S4 W! S. B25
. F. C* n6 B& B, k26
27
28
29
) D; ]5 T# D% l% w30
31
  G1 h0 W' q0 x  u32
33
4 ]* @+ V! s. S# @1 W3 C34
2 B, S$ e) D0 y# Y; S35
36
37
' W& G9 g0 y- Z, ~' N38
; O$ m  t" K- g5 N9 j/ E. I( N( P% w39
40
) d  k( v9 o  @! z8 a& k41
- L9 a& s0 }- F( m42
43
44
0 }7 S( Y' x* }. \45
46
9 R; V7 [3 I1 r- a4 n- ~47
48
49
* W  }, O5 ?& R/ U- [4 g50
1 L  h4 P7 Y% U9 ?* i7 `: |51
52
53
! Y' B" d) j! F5 j; C9 H( U计数排序
2 D3 A6 w) j) Y) D$ I9 p! R找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
7 ^9 B8 Z' V4 z7 @' n# ]; k时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。

' w; V7 N0 \# u% A. a3 X
代码实现
4 `$ W$ G, N0 w/ C* w' j, K0 \
* H* f+ I( ~" D% D0 [3 E
, i* e" O; K& k1 o$ m, W( T) }$ X# }public class Solution {
% s9 r* A3 E% h" }
/ f  t; h# ~4 w" \6 b; u$ r& u
        public static void main(String[] args) {
( E, }$ W3 f7 e                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
" V  c  G) Y- k+ I                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
( Q: Z/ r2 I; V3 b        }
' ^& E& W. P+ a+ Y' h1 ~" K

        private static int[] countSort(int[] array) {
                if (array.length == 0)
0 ?* B! m! U' d: f" U1 }                        return array;
, u- ^- o: _9 ~6 q. u" V1 w               
                int min = array[0], max = array[0];
               
$ y" J) Y$ k- G2 g( H; {2 ?                for (int i = 0; i < array.length; i++) {
                        if (min > array) {
                                min = array;
                        }
                        if (max < array) {
& X* Z% V; I9 C4 C) Z. {2 ?                                max = array;
                        }
; f$ E& r! I$ X2 D1 ^  z) J# v                }
! i# b/ y& n( \" e4 L9 e5 x. {" \               
                int[] count = new int[max - min + 1];
' B7 I: o, s' u% F1 g. @               
                for (int i = 0; i < array.length; i++) {
1 a" h( z3 `- J+ r: W                        count[array - min]++;
                }
               
9 W- |8 E" E8 u6 ?" ~                int i = 0;
                int index = 0;
9 P* k1 Z; p8 ^3 f$ y                while (index < array.length) {
2 S0 ]' M4 j9 y: L; l6 z                        if (count != 0) {
                                array[index] = i + min;
; d  D. v6 e  u: }/ o5 z# D: O; Z                                count--;
                                index++;
                        } else {
                                i++;
' D6 ^9 I7 S0 }: X                        }
4 K5 e) w* f6 Q! v                }
$ @$ z, t3 s4 i) W                return array;
% R  v9 C, v9 r) W$ m* p6 l+ o        }
+ z* q: @. v. O. J       
}
1
2
9 c  \# n5 c- n& N3
4
+ Q- p9 t6 J( W, s" B$ R( a5
/ S2 q4 l  b: R9 |6
: E' v7 ]/ Y7 w7
8
9
- U# {1 ^4 k5 h* k$ n& C$ W" _10
11
4 k3 W) t& X, J* j6 w12
9 g* e4 F+ j, y* e13
2 X; @& n; ^* r14
+ y3 v2 d' P" h9 m/ S  P15
16
17
18
, f& @4 Y/ M5 z19
20
9 d/ [/ i) X9 h& r1 y; G) a% T21
" X; a! E- o' e0 k8 ~, b22
! Z: @; I$ l$ X0 Y23
24
25
7 Q/ g) \! X* M3 f26
27
28
' ?/ X6 W; h- X3 \29
30
31
32
33
34
35
36
37
38
; h1 l* y, I( Z7 m$ @8 j39
: {; ]9 `1 o+ B( z0 Z( N4 W40
41
42
" U6 |1 }  e- @! g# N8 R7 v1 w8 B43
  D6 C& I' u- q, D44
桶排序
4 U5 {# N$ `: b————————————————
" D1 Q6 p/ W9 g/ C; p版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
6 ]  L' j& E% U9 l, I4 k. B5 e0 F

1 ^$ \# D. A, [$ [/ s. S9 z