十大排序算法（Java实现）

杨利霞

1 r+ L) @, u* ~& }6 G& i十大排序算法（Java实现）

) q# J3 A! p6 P( }( l' x! \十大排序算法（Java实现）
排序算法框架
排序算法性质
插入排序
0 `$ ~; T& w" q9 n2 s. U: |, {7 O直接插入排序
希尔排序
选择排序
简单选择排序
5 q( E2 q* j& `堆排序
交换排序
- q/ ]& ]& E! ]0 H, d0 W8 E# ?冒泡排序
. I7 n5 ^$ R; O2 w  H& c9 Q9 _快速排序
归并排序
基数排序
计数排序
桶排序
/ q. A, Q1 u% q6 ^6 @- U更多文章点击 >> 这里
: `  z" r( @0 M5 d# i- f! s! d
% v, U  u+ y9 m
排序算法框架




% X) n# T! [  [排序算法性质
, ]! Z% M" J  y& ~2 G5 R' j

: Z# ]- r, S% J; O( S' k
* b* S" ]$ I3 M( O3 r: @+ S
插入排序
直接插入排序
& ~4 y: n6 ~, i从第一个元素开始，认为该元素是已排序的。
$ U+ C) E0 s" \: F取出下一元素，与前面已经排好序的部分进行比较。
) x; e6 I! w9 @/ @" f3 @/ p若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
6 U; Y; \6 b5 b, v# F1 \0 p% {/ R* f遍历数组，直至结束。
# o& r( a2 o" E& B7 U+ k3 S最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
; g" h5 z( _* v% u+ R9 N' i2
) 。
) L# h, p7 i. X! X6 ?9 u2 ~" T

代码实现

. V5 M1 x$ G. i5 G
public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
" \9 t; m0 T; K4 Y5 y, E: g                insertSort(array);
                System.out.println(Arrays.toString(array));
& W/ R& l2 y5 w, k  f! L, Y3 o' F        }


0 t, |, \' g, B. _        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
: `" H/ h- ?. ?; v                        int index = i;
% G% n  Y! b- r+ I1 d4 H                        while(index >= 0 && array[index] > data) {
                                array[index + 1] = array[index];
                                index--;
% g  J; x9 g- U/ `                        }
4 V  y$ P# t3 ]4 ^- l! C                        array[index + 1] = data;
* ~" i- g5 f; R  k5 _                }
        }
}
1
2
3
; c8 i5 _' C+ m1 ~5 H1 p4
5 O, p' K# n/ h' ?1 {1 |" B1 w1 S5
6
7
2 g7 q1 @0 K$ s6 }8
9
10
11
- N( w+ D) L* o$ E12
13
14
15
16
17
: s  J* S, K. {6 z18
; ^( T' S! A3 v( ^' m; f19
希尔排序


时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
. P, x5 q5 u/ r! C" {3 m7 j) X9 k
4 M2 m! h# N( N( _8 O
4 A1 i/ e9 ?5 _5 L4 U代码实现


public class Solution {
' q+ _$ S# ?& j$ y9 ?  b- O$ t        public static void main(String[] args) {
/ _" P" |& O/ f4 r, h, i" }, V) V                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                shellSort(array);
$ A% ~( M2 F, y2 M+ p" y! j                System.out.println(Arrays.toString(array));
        }
$ A! g; V  f; b9 {
2 {; [$ k8 r9 s3 ~% \
        private static void shellSort(int[] array) {
4 ]6 Z% }& `& _4 e+ V2 M                int gap = array.length / 2;
3 g& B0 H) L0 I& q                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
# c( E8 t- G# _# q+ @% A                                int index = i - gap;
/ K9 V* _0 r+ r+ q: h* L2 j                                int temp = array;
                                while (index >= 0 && array[index] > temp) {
" k* f" G+ a0 S$ H: {5 U( U                                        swap(array, index, index + gap);
                                        index -= gap;
0 g; s4 D2 O/ g$ x; L% [                                }
* a& q2 w7 C' q# p" B//                                array[index + gap] = temp;
                        }
                        gap /= 2;
& o/ h* `4 X3 X                        System.out.println(Arrays.toString(array));
' j5 q: b- }! D; [5 Z                }
( h. ^% R* Y6 u, c        }
1 P0 t. r+ X7 |/ ?( _: d8 g

# [8 b- l' X# Y  @6 b        private static void swap(int[] array, int i, int index) {
                int temp = array;
                array = array[index];
* s( Z7 g; o/ S, n0 f6 x                array[index] = temp;
4 ]$ N" b+ ^) n  n        }
}
2 H! W, g1 U, p6 g5 o1
2
6 m6 f  y4 l* E* ^0 V# A3 M7 Y3
' O. x& H% M' v; I8 y1 v3 ~3 R4
5
6
2 ?2 F/ L5 |- {7
8
' l6 z5 y$ z' [4 f9
10
, f. [, @) t7 [  w& t4 q11
12
1 a" S& W% z; Z13
7 b; J( H! j; u' W14
. @$ N+ q" }' L  z15
$ y) U; M- |) J0 O16
17
18
4 i# E- y& G9 R( e/ k19
20
21
4 u6 ~. Y( X- ]8 b- ]22
1 H; M5 b0 F6 z* S' T7 P1 Q4 t$ r23
. |3 i8 [7 t: T# ~& O* R7 K24
" b3 j, s( O9 J; U25
26
27
6 `- K/ \. D5 y; X9 e0 C: \28
29
30
" {3 m. X  ?6 [: [4 `0 U! Y) m. i) h选择排序
简单选择排序
+ o' C7 C  e9 ^) D3 [/ ~% E从未排序的初始数组中寻找最小元素放置首位。
: g" B. ~* P8 g0 J+ ^/ e6 p& h从剩余元素中继续寻找最小元素，放到已排序序列的尾部
; U0 o4 ]; e: }遍历数组，直至结束。
! G4 j& y! |6 {* k) X时间复杂度为 O ( n 2 ) O(n^2)O(n
% R2 R1 i1 n/ z& P2 f2
) 。
4 A( f6 T2 }  d# O# u6 B

; Q  B- v8 g5 u0 }代码实现**
. ]* l! y' u; T
/ M! r( c  e. J! i. Z4 `, K
3 g: a/ u4 R& Npublic class Solution {
        public static void main(String[] args) {
) c1 w" g) J' ?) j7 Q/ U  t                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
                System.out.println(Arrays.toString(array));
        }
: ^2 h! ~: v2 ?* [
4 K3 c' |5 Y  z% Q. A
        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
                        int index = i;
: ]# ]  z+ H4 F# b5 E                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
' E4 C" N1 n* e' j5 P: T1 Q8 v/ G1 j2 d                                        index = j;
$ u9 l9 |# e- x# ]% v9 B                                }
                        }
" d: a- i/ S$ R' H! M7 c                        swap(array, index, i);
& N/ W" J. b- D3 B                }
        }

# _, m& @9 G+ _0 A) q- {# y- u
        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
' \7 E. N; o) t; r1 U                array[index] = array;
                array = temp;
4 V( \3 T, L) g2 t1 O  J& d        }
}
1
2
3
4
1 i: l& S/ x2 Y8 z% B( O6 ^5
6
, J; n; t! {- u) ~* f- U7
+ c! A  }- q4 ^# c' R3 R8
! I! S% S3 D' p9
  X1 ~5 T7 y* z/ C% U$ C10
11
12
* ~2 j6 i( T: y" d7 {2 u13
/ U4 o: g; R% s14
' P; _) u7 P: ?15
$ ^. w$ v+ t0 [  C* B4 ]16
  s; H! g# O  k" M+ B" r- ?17
0 I+ B" p% y1 ]1 J2 T  q0 ^18
19
7 }3 ^  I" n1 ?8 Q4 Z: b* {4 A20
21
, K9 T& F6 ]3 Y8 \" a1 m" F: ]3 }22
3 M. W* x- g4 B$ e) H: ]6 y23
/ J0 R+ S( ]0 G4 }- p7 o/ v' a24
25
堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
3 I! c/ ]; b: N% `2 {/ Y
" V! p, v) ~2 h! T5 V- E& {' ]: N2 D
代码实现**


public class Solution {
* t) b% S, j" s% y        // 建堆
& W* T! P  t0 u+ v( F5 I        public static void creatHeap(int[] arr, int n) {
2 f. l: H+ M! r% h# I7 j                // 因为数组是从0开始的
                for (int i = (n - 1) / 2; i >= 0; i--) {
! Q/ e; d$ h% ~* o  q                        percolateDown(arr, i, n);
. }0 K, E5 i% G0 P                }
/ s4 u) k8 o2 ]- E- o9 Q; H' E        }
        // 插入
8 K" |3 Q+ r. _9 `        private static void insertHeap(int[] array, int data, int n) {
( ^, Y8 H! v  H1 {                array[n] = data;
                percolatrUp(array, n);
        }
9 J% W. m, U2 D  w5 r. J        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
                arr[0] = arr[n];
                arr[n] = -1;
# y2 p- O& g& `                percolateDown(arr, 0, n - 1);
, r' J1 K. d6 `* l        }
        // 上浮
        private static void percolatrUp(int[] array, int n) {
                int data = array[n];
0 m7 k; H# M- l                int father = (n - 1) / 2;
) U1 Q* R$ Q  O                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
                        array[father] = data;
                        n = father;
                        father = (n - 1) / 2;
                }
                array[father] = data;
! B3 y2 |+ r* K% W1 V        }
, `% P- F0 t  B: R$ _4 {# P8 }        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
                int child = 2 * i + 1;
                // 遍历整个该根结点的子树
                while (child <= n) {
2 k* |* u5 w$ s4 d                        // 定位左右结点小的那一个
' l$ i8 x3 g4 E/ N                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
                                child += 1;
9 C+ e: c( G5 y9 g+ |$ t* m0 }' Q8 V                        }
  e0 O+ x6 E; H. q                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
                                break;
                        }
                        // 互换根结点和子结点
                        arr = arr[child];
" f' y, _* D1 h1 U/ J                        arr[child] = father;
) _, P. N! n3 h- |                        // 重新定位根结点和子结点
                        i = child;
                        child = i * 2 + 1;
                }
        }
   
        public static void main(String[] args) {
% N7 w  V6 F1 y  C                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
: U' u0 Z4 e* Z% N: s; e; p/ C# F                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
$ R5 K5 _* f* K) j               
                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
' A8 Y* G# v' M' i               
                deleteHeap(array, array.length - 2);
; H  j9 q& K! a  O, m; ]                System.out.println(Arrays.toString(array));
8 S8 M5 z9 @0 G% [- s9 L               
                insertHeap(array, 3, array.length - 2);
( ?2 Q1 O5 n( j% N) S0 V3 R                System.out.println(Arrays.toString(array));
        }
8 x( K6 Z9 k$ I8 Y% Y" {}
1
2
3
4
5
1 P$ j$ X" |% r7 }  a, a6
, s+ I1 z0 b3 T/ U9 l8 R0 _7 w7
. V6 D4 ?  e0 q4 E  |! Y8
9
10
3 ~+ A( L7 `  P; t11
12
13
14
2 i& d" z  Z% ]4 j15
16
2 B: ^1 E" W: k8 s# I+ b17
18
19
0 S$ H: r1 K4 T9 w, @5 d4 Z+ v20
# D& p& r- O+ C21
22
% x. O* T9 O; e23
. Q9 F% Q' M% o4 U" Y+ Q: h( m: y24
1 w7 B6 n% j( I& P5 w25
& V% y3 s9 u& U4 W7 M2 |( B26
9 m# n8 \5 P1 C! ^  ^4 L; b: C27
& g, G( F( ^/ Q, q. R* c28
& N1 V0 c* d) h% z1 }: _, _29
30
31
32
9 G; [" K  i+ @9 _8 R33
34
35
36
$ z* c; V' q7 ?37
0 c- o: L( v* m7 W' u# d38
39
40
41
+ N8 u5 a7 @. {42
* w$ a. t( l; l$ `! n/ l+ [43
1 N  o* g5 s, B5 Y! m' |3 [44
45
) U3 ~( w- G7 T# l! f. ?/ W46
+ B/ }' g* j* ]47
48
49
' h" U+ h! k. q/ ?9 [: J50
51
9 H9 a8 B. ^( E52
- Z! J1 m" Z# \  ^53
# q7 D$ z( D& G( ~- |$ d54
. I$ _' f9 `( E9 @4 O8 @0 z4 A1 b55
56
57
58
( A: M2 ^/ J: [0 }& f# v59
2 a* n- r$ K. Q1 t5 o3 p60
, u; }0 |3 F. O% f61
62
) \7 U- a: E$ ]$ n$ A4 O/ W, a- D) M: t63
64
! w) l1 d6 T# Q7 b8 j2 k% u7 ~65
  z% o+ z# V4 `* l66
67
% X( D4 m  r! M/ m& V) U2 Z7 s68
69
70
( M- ?2 e; O1 m交换排序
冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
  y' ]3 [" j1 W1 U1 t# B在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
5 i1 G+ h/ y# u/ q: ]' m7 p遍历数组，直至结束。
最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。
/ V( t. \7 @! s# f3 E9 H
7 @2 g8 s& P. ]
代码实现

0 }! \6 E9 B: m( m1 w/ V8 n# ?
import java.util.Arrays;
9 L) X( M. x1 ^% U' V$ _public class Solution {
       
        private static void bubbleSort(int[] nums) {
                // 循环次数
4 Z: N* X$ s7 Z) g6 J" s  U  [/ p                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
. s3 M; T+ D! r: C) k% ~/ F* ^                                if (nums[j] > nums[j + 1]) {
, l/ ~2 `0 G! k9 S2 o$ O: E                                        swap(nums, j, j + 1);
5 A( }* T9 s+ p) A7 E% z                                }
' K2 B! |4 j4 K* y9 j                        }
$ o+ d9 m7 ~% h( \2 H6 z                }
        }


        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
5 S8 u5 R' o- B" O% U. \1 y+ t                nums[j] = nums;
  \, G( [* J0 Y) U                nums= temp;
        }


        public static void main(String[] args) {
. l# l9 t' ?. H+ D7 n# {                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
% @0 Q! Q# C* e2 |0 |/ w        }
}
+ b0 s  A( A9 Q! I2 x1
8 g, p  @1 O' L9 e! p7 u/ z; c: d. m0 A2
2 p( B5 X( O  r+ F; _2 T5 L. w3
4
; }9 G$ a) x) N; z5
$ T& F( @) O% z9 a6
: w0 `1 h2 z& A) g0 K. r2 J4 }7
  s0 H/ Y, x3 q! H: `3 |8
9
10
9 ~9 y# {/ Q  f7 d8 E" |11
, z! T, s0 H2 R% E, y/ I- l  h12
6 z2 I5 m. \: X7 ^/ M% F' V13
% `: {& H7 `( T3 M14
15
16
17
% k7 C" T+ c$ I: |( y) X# G5 M18
3 `3 e! C" Z/ y( t* e19
20
21
% o3 W/ N. b; x22
23
/ j8 P4 A$ D) F' E9 e6 V24
) x: H2 o5 Q  T- R* g25
26
27
快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
; U1 w0 e$ G8 @- i

. Q4 d# D% w0 O, Z  s' [代码实现
- y- f; ]7 E1 Z: ^) y) D2 T! s7 I8 v0 I
( m$ ]. j% o& o5 L4 i& F
0 y& F4 C* e3 o- X+ zpublic class Solution {
. q  x: b0 D; D( ^. i6 o9 X$ M6 ~       
9 a. g3 ]8 v2 M& a- ~        // Median-of-Three Partitioning
3 ~, y# P& l& ], C        public static int selectPivot(int[] array, int left, int right) {
, V! l) h* I1 I! S- E; J                int middle = (left + right) / 2;
               
                if (array[middle] > array[right])
                        swap(array, middle, left);
2 p2 c& a( K+ l5 c  D5 Y                if (array[left] > array[right])
( N, g! D0 W4 y                        swap(array, left, right);
                if (array[middle] > array[left])
3 C, v" B/ x: V, f+ ?                        swap(array, left, middle);
) e. J/ q4 j: C               
                return array[left];
; R6 w1 u3 H9 ?! E: M$ T        }
0 t+ @# O" g8 @  s3 ]# S/ ]1 o. h  ~       
3 z! y* \$ `6 g0 V# O* `' B6 `        public static void sort(int[] array, int left, int right) {
                if (left >= right)
5 b2 G5 _; s; X                        return;
                int index = partition(array, left, right);
                sort(array, left, index - 1);
6 R* D, w5 o$ ]7 A! Q                sort(array, index + 1, right);
& P( c: s# m+ C" h2 E/ i; D    }
% s( H# [% W( Z3 B7 c* u       
        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){
                right--;
            }
% ?* k, J$ S0 d5 ?. e0 {8 u            if (left < right) {
* r* H; c/ t) v( o, r: V                array[left++] = array[right];
            }
            while(left < right && array[left] < pivot){
                left++;
            }
% R+ B4 S* U9 G% A            if (left < right) {
9 I) J$ e) B7 H% }                array[right--] = array[left];
            }
, R/ w3 R' Y3 l: s% Q0 U* _        }
            array[right] = pivot;
" V; Y2 j0 y  Q; }- J2 v5 W5 _        return right;
* Y4 S: |# U' }    }


6 d+ M0 d$ t" v1 g+ q* x. C7 Q    public static void swap(int[] array, int left, int right){
            int value = array[left];
            array[left] = array[right];
% ^& Y1 {9 y! Q/ G7 o! e2 ^8 E            array[right] = value;
( R0 w! q) t/ B+ s( j7 H    }

. f: y" Q( C4 [/ N  I
        public static void main(String[] args) {
* H! ?8 s/ J6 q. p# Z- {                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
5 X+ T) ?) x- Q) t* X9 u2 u                // System.out.println(Arrays.toString(array));
                sort(array, 0, array.length - 1);
! A) v( L9 s# }; s/ C2 W                System.out.println(Arrays.toString(array));
9 _# r( N: `$ C) q. c, P        }
}
1
8 ?8 E' }2 D% W6 P: G2
3
" U9 p& N& d& f, b4
5
) C* U5 e( Z7 W6
7
8
9
10
/ F0 o* ^! @, g6 N! I' @11
12
13
14
, Q3 a( y# C4 A6 a$ ]- r5 h15
6 c! |  P4 r3 N/ |16
/ ^( \/ J, m8 N! R% }0 _17
18
19
6 ?" P% F6 x8 M7 i8 `7 x! ^20
21
22
23
24
25
26
27
28
29
30
) B# ~% }( r. b% ~  E4 g4 q31
& j4 c- z" h* p' B32
33
7 S( `: Z  V" ~  X+ a! ~1 U7 i4 v- E34
3 O4 V1 B* z% z! I4 E9 W' G+ t3 J35
: A( U- A; A  j36
37
! i7 O) C- E- R, z. _- o38
$ [% h: `  d( t' w39
" ?* q* i; q5 m$ h& q4 X6 j40
* `$ J+ P4 u/ g8 f41
42
4 c5 `  i) c  p2 {/ i43
44
45
46
47
48
0 G$ K8 o5 ]2 ~' s8 t49
50
51
52
53
; L# C- w8 J$ c54
& x% S* b8 k" r- G1 V$ K) q+ ?55
56
57
归并排序
将长序列从中间分成两个子序列。
- ?: W! f* V$ D8 J9 c, Q对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
0 H- b7 G- s' o1 M7 I, v) y7 d+ ^: ^平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


5 z4 c5 i9 e, A代码实现**

) y/ g, O$ q- w
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);
                System.out.println(Arrays.toString(arr));
        }
8 w% m  j9 U. B) R3 `0 s) i; ?2 }

& c6 x: O+ m" y% J0 N; g6 P7 O        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
5 g* I$ J/ P9 t2 x( k                        return array;
3 S0 E/ W/ R* w9 \8 ^                int middle = array.length / 2;
/ A1 c, w5 P/ h' {                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
& m: c( O; a8 X& l1 z8 e                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
' }9 \# C7 g9 u1 h0 _                return merge(MergeSort(leftArray), MergeSort(rightArray));
. ~! h& q& X4 L: ^+ j4 A/ _! [        }
+ H; A& K: K! C2 ~4 ?8 q
% Q2 M* ^$ O6 b+ R, d8 |0 b
. E+ L) s7 \# U' H' g& j: R5 ?% [4 ~- a1 \        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) {
' X. Q% Q/ }9 }                                result[index] = rightArray[j++];
) \# S8 ]7 ~+ [, `: x$ I                        } else if (j >= rightArray.length) {
6 u6 F! c. @& ]  t  [, C                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
. S! T9 f$ ]+ Y+ b+ N                                result[index] = rightArray[j++];
                        } else {
                                result[index] = leftArray[i++];
                        }
                }
                return result;
        }
}

- ^/ i* E+ W) Q0 _0 G6 I$ Y( ^
1
- P; l0 e- T  Y" B2 D: v2
3
4
5
6
* P. ~4 {+ i& u& [9 X& l7 @+ }7 w7
8 H; F$ J3 I# }. r9 _9 O& `8
5 k) c) g5 M% C- v4 ^9
10
) [  Q- }$ x& }7 j! m11
; u2 F, C3 ^: k; z$ M, {- [9 D12
" Y5 S. C6 [$ `3 v; }. k13
- ?' [( |; h% P0 j14
15
! d' k1 x; a! J- l: F9 N# x16
17
18
4 w7 a' ]/ d! J& A1 J19
20
21
, E: o/ V$ a2 `22
23
24
5 x9 p4 c2 O# o' q1 D, b9 ]0 b2 |6 l25
26
$ h* t3 v& x1 b: F  [' @& ^7 Q27
28
9 l1 u! X, j% K& d. J( V29
, \# K0 R2 v( t8 a5 X30
/ ~2 L4 h) }( @* y% \# ]31
0 r/ y' N6 o6 @7 a: t32
) }; Z2 Y) T, v% P33
基数排序
. y5 ~2 q0 ~1 [$ m( O找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
( I: _8 n% D: |4 L# H将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
: H. j' Q3 q4 g( R( H5 K/ u

代码实现**


public class RadixSort {


        public static void main(String[] args) {
, ^9 h! ]$ z. @( c8 Y0 ]4 V. g9 l                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
                int[] arr = radixSort(array);
% ~  [0 I% m8 t& O3 f# ~, \. M                System.out.println(Arrays.toString(arr));
        }

9 a! @( e: I& C4 |8 t9 u& U; E
/ I' k, g* i& j# U( e: }* Z2 b        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
                        return array;
. h; ?+ e# c. X( z                }
                // 根据最大值找到最大位数
                int max = 0;
- o" f$ M! p/ D; e( E                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
$ Y3 y6 \  @! \% P                }
               
                int maxDigit = 0;
                while (max != 0) {
                        max /= 10;
6 u, `, ^2 T$ l3 d& m  a' @                        maxDigit++;
/ R0 ?* M; C7 r; c0 j2 A+ ?                }
               
                // 第一维: 0~9
% r9 x& r, `! M, Y* D6 |4 I                int[][] radix = new int[10][array.length];
                // 该位为 i 的元素个数
                int[] count = new int[10];
& P; ]; c5 N5 P; a               
                int m = 1;
& Z, l& g& s- y                int n = 1;
6 o4 D6 s) r  T$ @               
                while (m <= maxDigit) {
' Z6 b* P! d1 w1 ?* `! y                        for (int i = 0; i < array.length; i++) {
. I( i+ o& i, b                                int lsd = (array / n) % 10;
: o! B# A7 n, q. \                                radix[lsd][count[lsd]] = array;
& M: O; k1 p! c0 I                                count[lsd]++;
                        }
                        for (int i = 0, k = 0; i < 10; i++) {
( m! f' o' g& c8 @1 f7 n                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
6 x% h7 L8 G2 _                                        }
( ~+ ~- d; X9 ~& K4 V6 b5 Z                                }
                                count = 0;
                        }
                        n *= 10;
6 A* x" T, P  E2 C& h0 p0 p8 T                        m++;
                }
; h$ @8 i& H: K8 {) H                return array;
        }
4 R7 b/ Y9 V" |* M( l' x3 @; X

7 K8 i% P3 K3 ?& z  n}
$ X3 P8 n  X) r  k; T1
4 d% f2 K/ p8 u2
3 a+ f5 m. w3 L3
4
7 f9 t, o( D8 n+ Z2 {5
3 N+ N6 r1 Q- p1 L2 d6
7
3 B+ U* Z7 {6 [9 ~4 d6 `8
9
$ T: s! O' B- l% ^0 w5 i, X6 D0 U10
$ X. J# u/ h  h# y; l11
6 a5 Z# q( a4 Q* R/ Z12
13
% N& ^' l( K0 q  _- _+ K- s14
, W" X6 J+ s2 V7 x5 `$ O/ W+ O- L# |15
16
17
18
19
20
21
22
' C7 |4 K8 s  _23
: C) j* n1 \$ v# e7 k24
25
26
) V6 C- v$ V9 m: N% D& r27
28
29
$ V- c8 ]' z8 H# K$ K$ o30
3 p. }6 ]- u1 E8 o+ u31
32
33
( [& N( O  A$ S) ?34
35
. m8 w6 h7 _: D! x5 V' {4 N; l! u36
2 O$ E  ]9 x. j+ l: K37
38
39
40
41
42
6 V$ b) ^. T% Q& ?& T) ~3 x2 }43
8 c; J7 u8 z2 i. M% h44
% y' c( S! E" g45
8 [( b, i) Q$ x4 y, a46
47
48
49
50
1 D6 _& U' h$ O( j/ X# ?51
1 ^+ c$ g6 U9 o, u/ ]52
' Q/ {' r, C7 R53
计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
/ }7 S8 D3 L+ U: E& g7 n" \1 G9 C统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
0 D9 r4 u; C0 K0 |2 r6 R最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
, X+ Z2 J& r! a3 r4 G# h时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。

$ t2 N4 ]5 {; J* p. K% [; W
代码实现
# {& g' G! e2 p# M! v( b4 \
% b3 ]) m$ z% u$ Q* k- f$ `8 U  L
public class Solution {
- R3 j0 C1 o; z2 c& ~' {& \

        public static void main(String[] args) {
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
' Y/ Y7 b3 v" `9 k- F) t9 A1 p! ]                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
        }

3 b( s- t- s2 O
        private static int[] countSort(int[] array) {
: Z. [: R. n. |                if (array.length == 0)
1 I3 ]3 F  ?3 z6 X                        return array;
               
                int min = array[0], max = array[0];
               
& r* \( s( |3 k* i0 i3 u                for (int i = 0; i < array.length; i++) {
0 v& W: {- U1 K, ^& I: I( o                        if (min > array) {
9 h) W, G- X# K$ G/ n                                min = array;
' q9 p1 e( O% t2 [2 M                        }
4 N) N2 M+ _+ F2 j7 x1 {2 [; j                        if (max < array) {
                                max = array;
( ^/ v( y8 q. w. d0 _! ^                        }
                }
$ {  c3 I! w4 m" {               
# K, p% W( ?$ j                int[] count = new int[max - min + 1];
- j' [) I& p6 Z% I- o! Z               
8 u$ j" T7 U# A) E& c                for (int i = 0; i < array.length; i++) {
                        count[array - min]++;
  k' O% e: H+ p) w                }
. d3 Q) T0 \: [$ H4 Z# p               
                int i = 0;
                int index = 0;
0 \) |8 H- i* c6 ^$ _1 f                while (index < array.length) {
+ c! t* w# w5 o( }: ~                        if (count != 0) {
( `! `' ^2 O# f5 }9 X                                array[index] = i + min;
                                count--;
                                index++;
                        } else {
& x7 F0 V' u0 ~& ?                                i++;
                        }
# t* ]$ ~1 d. Z1 T                }
                return array;
, J" [: \9 {2 k" v) N6 ~        }
3 c  H, Z/ z8 u* h       
}
) d3 K4 g, z) m0 M9 }+ o! e1
2
3
4
4 v- o& C( C3 C' @- F5
6
7
8
9
* @) w9 l- ^" b+ ?! t' n* W10
" i$ T( v- O) K  I7 S: [11
" x* m! ]: a1 f2 C/ T2 [0 j12
13
# p* R1 k* C4 L& S: i& O14
2 J* x, S* d! P- L- t% [15
9 l0 L3 {: r8 M7 _- ~16
17
* Z- ^/ f. y' {: u" b: ^18
" B8 E, ~% N& i; O2 `19
20
& e6 _( K# f5 i1 ?9 e21
22
1 l: H) {% h' T* Z6 C- p  e/ e; ~23
24
/ ^) e5 i8 F3 c! K25
% D6 P& z/ B, Z( ]9 \9 y; h26
& c4 T, S1 k6 z! U27
! ?0 t4 Z; E' u% ?2 o28
29
30
31
( W6 _# ?5 q% C8 g' @) g  d; K32
33
34
, W8 L: I# i8 ^" N+ G% A# Y4 r35
) M# O1 m9 q* g36
2 D0 c9 i2 E$ w3 _2 ?" w$ p# q( ~37
3 X3 \! c& l0 K  v& a38
, V/ `2 f. a2 \% f# q3 E0 u% L" u39
2 Y4 p0 y" H2 B" h40
2 O( O& S. {1 V8 r41
8 j3 M6 V+ p- Q) |42
3 E. ~( ~& {% u. Q" A( s7 h43
) B0 c, S0 W* ]' i44
8 a7 m) K3 w4 m! x% z/ n& f桶排序
————————————————
5 |! O7 c2 n1 j* v5 D/ U3 m1 ~版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% S. \' I: p2 e; {5 x原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153


8 i/ i% _1 }6 Y+ s! M# k/ @& L- _