十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）
  _# }% \- f7 l1 [
" Y# y. C; r( G$ y( }十大排序算法（Java实现）
排序算法框架
2 b" ^- M+ I1 \" |排序算法性质
插入排序
直接插入排序
希尔排序
+ `2 C  c( y0 l2 w( M选择排序
简单选择排序
/ ?' [! c# C' H2 p0 A4 F堆排序
交换排序
& _" [3 g1 M3 @$ k! t: R& D冒泡排序
快速排序
归并排序
基数排序
计数排序
8 X, U4 T! m+ V( a: A桶排序
更多文章点击 >> 这里

) n  ^0 B' p9 `9 S  a
排序算法框架
! o  w$ Y; e% Q9 z& `0 S
6 f) R2 }4 h/ ]! m$ c/ {' U3 f

0 b" A$ M. \4 b9 ]  i% J: W
5 \+ _& ~# p# @9 q/ ^* J排序算法性质

3 o1 r1 n% a- G

: }* W1 L% s/ a6 z, ^5 i
4 d) N8 r( r1 a0 v! R$ F% p$ g插入排序
直接插入排序
4 d2 V. b: U1 W! L- S( W3 |从第一个元素开始，认为该元素是已排序的。
  I5 E- b2 O- l# n: Y0 D取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
& ~7 M/ E- O. ^最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
/ ]8 T% A6 s# S: Y9 g- E% K9 q/ g2
) 。

2 b; n0 ~- F/ x5 @4 s
/ O; Y$ A( J; l* H: M, W& p) q# |代码实现


public class Solution {
        public static void main(String[] args) {
) K  ]$ v4 ], D, t0 q. I                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
  y) W- Z6 E% B2 V                insertSort(array);
                System.out.println(Arrays.toString(array));
        }
1 K5 d1 J) S" D  u1 U& |4 _
: u" a( y( t" Q; i8 s" Q8 p
8 Q! @$ N- X* D" I* I$ L        private static void insertSort(int[] array) {
) @# [1 S( k& t7 m0 v                for (int i = 0; i < array.length - 1; i++) {
& o' j" G1 \& c+ |0 Q; Q* }& h                        int data = array[i + 1];
7 X  h, x( S$ t( r                        int index = i;
! H. u# h# x% S0 \; v                        while(index >= 0 && array[index] > data) {
; \" r9 T) Y" B8 q( z( E                                array[index + 1] = array[index];
                                index--;
0 p; z1 r) E: E                        }
                        array[index + 1] = data;
                }
        }
}
$ x1 Z+ B7 `2 Q* f0 w% d1
2
0 k. e" m. P( b# D3
4
; N% z; f, P: Y5
/ j5 C  }: K+ Q3 ]/ \1 E4 s( {6
7
0 d/ f& w6 r' E' o. _0 |% j8 O8
5 y) q& M0 d1 m/ @- J: E9
10
11
0 l' @, C8 {* I3 P12
13
% b7 J! e( p7 O14
15
16
17
18
* ~" B6 l- I" g19
希尔排序
7 y6 c& M0 G3 r9 i
% j3 q( _( @, M* M* h
! c! W' N6 e- K1 E% m时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

) |9 {& V+ i& L- j% ]
代码实现
" }2 d5 u' |1 [* d
7 m) t0 [* j; k# O8 V7 h
public class Solution {
, e6 K. d2 j- A6 w        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
# J* v8 x1 ~# Q2 |& [                shellSort(array);
( w% B2 u, i% }9 O( a+ c$ x                System.out.println(Arrays.toString(array));
        }

. v8 P! r, k, I  V
        private static void shellSort(int[] array) {
                int gap = array.length / 2;
                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
                                int index = i - gap;
                                int temp = array;
# g& P) v0 V0 i0 a% I                                while (index >= 0 && array[index] > temp) {
  H6 q2 N3 n2 I2 e% ]- d" u! Z* V                                        swap(array, index, index + gap);
- X- O& V6 O4 k% x/ K% f                                        index -= gap;
7 n" `% K. o. n* K1 B                                }
/ U' Z/ A4 ~4 ]( R//                                array[index + gap] = temp;
3 \6 U+ v* H9 z5 J. n0 d                        }
' N' j6 `" T+ A3 }4 W0 R                        gap /= 2;
                        System.out.println(Arrays.toString(array));
" t% x4 T# H8 P# F) _" y                }
/ G$ I7 b. l8 ]        }
5 v) Y1 ^: z" g; @' u, V
% Y- ^$ `1 ?& d4 U$ ^9 T& u
        private static void swap(int[] array, int i, int index) {
                int temp = array;
                array = array[index];
2 b2 v- f/ b" U, C  l+ X# D" V                array[index] = temp;
) k* e% R% i( k& o% ?& o& X. C        }
}
  U: C* ~$ ]+ K5 m5 J2 o1
4 C/ N3 F9 B( @2 T2
3
4
" H. M! ]5 a+ F& {4 w4 ^  q$ p5
& }- S: \& C3 c; l6
7
8
9
10
( u" C: g% l) g+ p& e3 x11
, o% I" ~4 M, _5 N12
# |5 V) o4 `6 W' Y# Q3 g13
0 E1 n1 O$ I. i" N5 B0 F8 H7 l14
+ E: ~. N$ u) @) x- f8 k8 W15
16
3 r/ X( F% n4 i# g  I17
8 A* \8 L! o6 U5 P18
' f0 m! W  R& K% t19
, l3 i# A6 N  s! t. r) R20
21
22
3 \9 @& K9 s6 T  Q23
7 B7 n& b5 q2 X6 H24
25
26
27
28
# u" t2 [, Z8 m3 l" `29
" H) C3 p7 r8 j. _/ y30
: b* ?) q% s- J) R+ Y! D0 E9 B. J选择排序
, Y6 c/ x6 F# T: T/ B3 i简单选择排序
从未排序的初始数组中寻找最小元素放置首位。
" J4 B# F# C$ H4 ]+ l( w3 v从剩余元素中继续寻找最小元素，放到已排序序列的尾部
, W/ r. a6 J' x1 K遍历数组，直至结束。
3 }$ b% S  c. Y6 ]6 ~% Z时间复杂度为 O ( n 2 ) O(n^2)O(n
( c9 }5 w7 w$ x+ v# y* a2 V6 w% }2
& @6 h( I8 y5 ]& C% n$ x ) 。
* Y! F) A: b! ]/ `
4 m' v* D) C/ D" t9 b( r3 }! `! ^: d
代码实现**

( S% ^9 J2 B9 y( f4 s3 }7 K( E9 @
public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
  R! `7 n' [. H$ s2 k                selectionSort(array);
. ~& J* W9 {& J/ l2 ^" \                System.out.println(Arrays.toString(array));
4 C( U7 A& r. j; w. `        }

. K0 a& `+ z. X
        private static void selectionSort(int[] array) {
3 A" K$ \2 _1 e                for (int i = 0; i < array.length; i++) {
7 L& y: y. J5 y                        int index = i;
                        for (int j = i; j < array.length; j++) {
8 I3 A! N, _# @; d- G% D* `5 V) h                                if (array[j] < array[index]) {
. i7 }2 h. u# }& X' Y7 ?2 F                                        index = j;
                                }
                        }
                        swap(array, index, i);
                }
0 d: @* B; L8 V0 y' ~        }
: s  G: Z- B8 d& A

        private static void swap(int[] array, int index, int i) {
, m+ s6 v( u4 |- J                int temp = array[index];
: T* S" ^7 L9 e0 J' P6 N                array[index] = array;
8 ~& t8 U$ @# ^. d! _                array = temp;
- a* t8 k* m9 N9 _0 Y# E- [# n        }
" b/ D4 S3 s- q" p}
5 R9 u9 y' F. c; C! K1
2 J6 ^% [$ o$ W2
3
( W" W  I4 E, D, T4
# t6 e* f9 T; k8 u& Y8 \7 |7 P5
8 z, z5 C' r$ b  F5 e& v6
3 P: e6 [. Y2 \5 q  m7
8
9
10
11
12
13
* U  i4 @3 n) p& \9 |+ @7 R14
5 Z% w  ^$ L' r0 ]' r15
16
3 _; @+ E% x8 B% ]17
18
( g9 t) N$ w8 `' H19
20
21
22
23
24
25
堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
# U* H0 L, u, j3 m
! F  J" U& b; `9 P4 a- F2 Z
; Z# j) t0 _. A; k; V代码实现**
4 J- [3 i0 v/ ^8 i( O9 e' l

public class Solution {
2 ^5 O6 Z" D, j3 O4 p0 @! p        // 建堆
        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
5 v% q  h% U% ^0 x6 V                for (int i = (n - 1) / 2; i >= 0; i--) {
3 |" G/ X) [* \% u/ n                        percolateDown(arr, i, n);
                }
        }
& l, n$ J8 }9 ^4 G        // 插入
        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
- c! ~2 }9 k; e                percolatrUp(array, n);
5 A, q1 ^8 D1 b        }
        // 删除栈顶元素
/ h- A0 h# ]& h6 C3 m) j  C# |: C        private static void deleteHeap(int[] arr, int n) {
- r- H1 M3 d2 A$ B                arr[0] = arr[n];
" O5 j2 R: [9 r; l& q. y" [' E. p# M                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
        }
        // 上浮
        private static void percolatrUp(int[] array, int n) {
! g; p5 S! w4 g- S                int data = array[n];
0 S4 z) w5 Y" ]7 J) Y                int father = (n - 1) / 2;
' [; J, o$ O( A- g# ?5 i( ?                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
                        array[father] = data;
7 |2 M1 w9 E- s+ A* n! t# H                        n = father;
" y- U' s4 ?1 c  _6 z                        father = (n - 1) / 2;
& l& F6 q& F( x0 y& X. a                }
                array[father] = data;
" y! e  w6 X% b5 }+ R6 D        }
        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
                int child = 2 * i + 1;
5 j" a/ ^8 Q! P( I: d                // 遍历整个该根结点的子树
                while (child <= n) {
                        // 定位左右结点小的那一个
                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
                                child += 1;
4 f- t; `/ d0 H                        }
                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
% ]0 O: ~! L) N& V5 \" s                                break;
) n& d$ `8 g. T1 s                        }
3 O. f0 K" ?7 v% d0 Z; F                        // 互换根结点和子结点
                        arr = arr[child];
                        arr[child] = father;
) \* H- A7 _( _7 {                        // 重新定位根结点和子结点
                        i = child;
                        child = i * 2 + 1;
                }
! w  U" m( i  e- s* K6 w        }
   
        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
2 A: G5 i* F* t  s               
                creatHeap(array, array.length - 1);
7 O$ x% H# _7 j5 S                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 1);
; F* @# ~" n6 b. a. r4 a  c) J% g6 V8 ^                System.out.println(Arrays.toString(array));
% O7 y2 S2 N( s9 X8 U; L; x               
+ y7 k. f; E- M7 Y& r                deleteHeap(array, array.length - 2);
9 L* @7 o& p& y/ c( T6 R4 z                System.out.println(Arrays.toString(array));
               
                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
        }
- V; t1 h8 {# ?0 R4 P}
: o, D. r  |8 B, b! |1
2
3
8 W+ k7 U' n/ h9 I3 r4
5
6
: F; ~5 }3 e: j0 ^  n: e5 E/ i4 q7
6 Q( h' G. _- [: ?  C5 b: J8
1 S% ^) `; g% p5 U9
, t' C, P9 Q2 e" H6 U' [10
11
12
4 ?9 |; b, Y3 P13
: V1 A; M; J+ \8 N14
15
2 `4 n  Q5 [$ R- S# v" t! l16
17
18
19
20
6 o# P; p, O2 t( o' t3 n3 Z3 a21
  ?: ]- D; }9 V3 m9 P- ^5 ~22
) i3 [: X: i5 ?% j; N23
24
25
- t5 J6 A$ J8 F% Z. j2 ~26
1 O  F9 q$ y, A  w% N27
4 K) ?6 Z) x: L28
29
30
31
32
33
6 L# j9 n$ S3 n  p' v6 u4 v# ^( w34
+ t( v2 {  }5 k7 t& U4 D35
: y, k* h5 `7 g- {6 j+ K( C; |8 f36
7 l' r( Z6 E, Q4 f8 M4 [37
# s, W! U, }2 ]" r+ N38
39
40
41
42
1 g( {  V% J' F# D- l43
44
$ @; e! A  H3 q45
46
& u; i9 e# K- t$ Y3 D47
48
7 X/ T2 s/ U% Y) J% }3 E49
50
1 f$ t) Y0 U% {& {; ]0 A51
3 x) s# a! {( ~( V: R1 ]% u52
53
; X6 F6 `7 }' j5 U9 O# F0 A54
55
3 N! s# c8 B4 h9 z8 l: F56
57
, r5 C7 \& S, Y* I$ D' b! x58
59
60
/ R: I7 G# L( z61
62
( l# O9 A# |- [2 i) h7 S; P63
64
65
66
67
- Q, y0 j/ y5 }! ~  o; C* Z- `68
69
1 ~  M" O6 q, F+ n70
交换排序
冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
, W. C& M0 ~2 z/ h在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
, m2 `* G/ p8 r最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
+ _9 ]8 E( {# |( d' X5 k+ s ) 。
1 r! w6 e1 X. n

. u7 U5 l0 y; n( e代码实现


$ w; M% |/ {- t: e. T2 Dimport java.util.Arrays;
! x/ L9 Z% w3 t: C+ Xpublic class Solution {
       
        private static void bubbleSort(int[] nums) {
                // 循环次数
# t3 Z3 C: d8 B7 {! `0 O0 x                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
; z# Q  m7 |% |7 p1 p% V) X                        for (int j = 0; j < nums.length - 1 - i; j++) {
, k4 Q4 P) s& i7 i                                if (nums[j] > nums[j + 1]) {
5 e) ?2 W3 V$ B! r                                        swap(nums, j, j + 1);
                                }
                        }
                }
        }

4 V4 N3 L5 W# U
0 Q) Y9 N3 {; N; r; _  X- o        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
6 a+ L9 o! B  {, G                nums[j] = nums;
                nums= temp;
        }
, [1 G( H+ ~4 H$ o& J" ^6 c

" x! G4 C, A: o" u0 C* D% e        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
" `, H! S+ z5 b/ a                System.out.println(Arrays.toString(nums));
        }
}
1
2 e+ |; }2 [6 ~' ^. i0 D% ~. A5 r2
3
4
0 f( P  E9 b/ V5
6
& ?+ R- @& M; F' F7
8
, r! |9 i$ e: u1 m0 ?9
10
11
12
$ a6 A: q" h1 K' z13
14
  Z5 n& `( w) k8 n! {* D- O15
2 |2 T! h0 u9 }7 K16
2 z2 P3 r. M! J) V17
5 G8 l* X1 h* T& r5 J18
! i5 F2 E0 K6 {# @* M19
20
21
22
23
7 e. g/ }; v& I8 p8 Q  }# b  g5 M: G24
6 [, \" a3 u/ t: n25
- o/ V3 w6 i( u4 e6 [& ]26
5 p: C  Q' }1 y27
% {: Z3 B3 A& h& l快速排序
; N( S( c2 F% N时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


1 N. X" b# M9 q9 ^, ?代码实现
  @' D! S3 l( E: y$ E# Q
1 _  h8 [* f$ ^) t5 r. ]
; ?5 o1 V4 X+ \! Y% r" H4 lpublic class Solution {
. f6 R5 }  b: u0 \: {2 I$ ?7 b( R/ Q       
        // Median-of-Three Partitioning
        public static int selectPivot(int[] array, int left, int right) {
8 \6 Z+ `/ `7 [( m4 U/ V6 V2 e                int middle = (left + right) / 2;
               
                if (array[middle] > array[right])
) w% {5 u/ \$ ]+ t5 [                        swap(array, middle, left);
. O. \' j- d& n$ |5 _0 W7 K                if (array[left] > array[right])
                        swap(array, left, right);
# }9 n+ `& ~* K! }" h( a# l                if (array[middle] > array[left])
" G1 O4 s* {% S0 T! U1 N. M                        swap(array, left, middle);
) @2 r6 E& f% Q  Y6 n8 b               
7 h2 l: ?" m; M/ T+ \                return array[left];
        }
       
        public static void sort(int[] array, int left, int right) {
! b" g2 L; G4 u" S* d' L+ h! }                if (left >= right)
                        return;
- h9 f4 D0 B# q" T. B: N                int index = partition(array, left, right);
* F$ k3 N) }' C1 Z2 [1 x/ l+ p& n                sort(array, left, index - 1);
; @# }$ {7 e  e* Z* L                sort(array, index + 1, right);
    }
       
        public static int partition(int[] array, int left, int right){
, ^5 H  h$ J  f  `/ ^2 Q# s        int pivot = selectPivot(array, left, right);
        while(left < right){
7 Y( {9 h6 _9 X5 @) _4 |+ V. w0 _0 r            while(left < right && array[right] >= pivot){
                right--;
            }
6 r+ e2 [4 c6 o            if (left < right) {
                array[left++] = array[right];
9 s% u/ B" q) t5 {            }
            while(left < right && array[left] < pivot){
                left++;
            }
: n! q" D$ [3 p            if (left < right) {
                array[right--] = array[left];
3 `& s9 r) a/ G! f  r0 Y, e            }
; F+ s2 M# P) M/ M9 |5 v        }
            array[right] = pivot;
2 M" z8 I5 ?( ^& J1 n+ t        return right;
    }
: ~+ h% s, ^1 H" _! s3 L

    public static void swap(int[] array, int left, int right){
            int value = array[left];
            array[left] = array[right];
            array[right] = value;
. G- t' c9 W  O* u( g: P- Y+ S    }

+ X# j2 T: X7 Q1 M5 X7 ~  a
# X- u& O; `& e, T        public static void main(String[] args) {
+ v' |- c+ U( d7 n% F                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
, P0 \) A# ^" i0 j. Y" [! a                // System.out.println(Arrays.toString(array));
1 R! z$ L% K1 f% q                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
        }
, C" [- ]+ W& D6 u0 ?9 n}
1
2
# Y) S, K/ m7 C8 H$ ~3
4
5
6
7
8
# Z6 N+ K0 I6 K+ I6 ?+ k% l  R' v( n9
" \" I; d; T# \1 f: v2 j6 _9 i! R10
* Y* L, h8 d# W- v# r# {11
12
13
+ `' B5 n; `" P: F( w& k14
15
16
  E: d  P8 a9 }) _) T3 Z; Z8 l17
- U; \9 ^% s6 f18
19
; ]! m; t' z% y- B) ]20
, s' o* O8 Y- U7 M/ `' y3 ~, z7 M9 t21
7 o* J- K3 }" S+ l; n% P# W' o7 u22
& ^2 C; L+ e) h3 u0 Z8 `$ G! R  m23
24
25
26
27
28
29
30
- l' R: e) N' Y& ^31
32
33
- O& @- w. x$ r2 {0 N" ]6 y34
) I9 P- j5 p* Y: Q% g% z8 ^% C35
36
( V- C/ B. p: d1 l6 W37
38
39
; B7 r0 G) \. g( }40
41
2 _. O3 {& m# W0 M42
- c) S+ S; [) \' _4 x% J43
% ~, g+ n, q4 n+ O* R; C. \44
45
* i% q7 W, f1 v1 F& m46
47
7 Y+ C3 D; O4 W# i  i- c& K! }48
. c# ^4 d% [; Q49
* W. D% Y0 I+ ?2 I8 N  q- S50
. u1 K  Y: p3 ?' V2 h* T$ [5 R51
& N: v/ ~2 S- L& Y52
- Q6 a% L2 [  r, b- ?2 s53
2 _# [8 }% E4 z54
) G# y# U% Q2 s55
6 _8 [8 o0 @* |2 D& y% u1 ]4 @56
: P5 H) @* m& w5 M9 X57
归并排序
将长序列从中间分成两个子序列。
对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
' n! ]6 j3 X6 f: E. i

6 ]; U( l9 h2 L4 b8 I/ _3 A, H代码实现**


public class Solution {
( m% T' |4 F% n8 U& b) Q+ z' r        public static void main(String[] args) {
5 C6 A& e0 [0 g                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
, R2 @2 p, W3 R+ @                int[] arr = MergeSort(array);
                System.out.println(Arrays.toString(arr));
        }


. i; T5 d9 L2 X1 F1 ]5 d        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
( C- I4 H# x1 n4 J! _                        return array;
                int middle = array.length / 2;
% g- O# `( E: D4 o* ]& I3 m                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
% z3 h: Z4 o2 F                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }
, n. I8 d# p; _! r5 K  i
; ]3 r  T) i9 i7 m
% S  B  o& T/ \* E. m( V! [        private static int[] merge(int[] leftArray, int[] rightArray) {
6 n8 R5 J+ R$ f8 w2 z$ K                int[] result = new int[leftArray.length + rightArray.length];
5 l' l4 N8 w6 n                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
                        if (i >= leftArray.length) {
% _7 k4 Y( N/ y8 {/ k; W) L                                result[index] = rightArray[j++];
& g5 i3 F3 E* W/ r1 R6 d* R                        } else if (j >= rightArray.length) {
                                result[index] = leftArray[i++];
( |, [: c  U5 R  }3 ?6 P* G7 r                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
                        } else {
2 J: ]" [- G& p2 i1 W                                result[index] = leftArray[i++];
7 ^* E6 N* W0 h9 a0 I4 Y/ K, G                        }
, L  N6 L3 a  n8 [                }
                return result;
        }
! |: I1 o1 x. N* s! L" s; h& e; m}
, {4 m; n( B2 U3 {  s# H

& g. b: G- W0 J5 q7 |4 ]( H1
" Y9 |$ O9 L9 f. y* z" }3 C2
3
- n  X0 t) M3 x3 V4
5 r7 ~& g1 o6 h5 n+ n5
6
: C# G3 }, R( b# v7
8
/ x# a4 G+ t8 F' X1 x3 L- d9
10
. ~1 s7 O. a: N11
9 Q* Q# R) H% b: H( N5 q. F12
13
' V7 e' p' Y5 z5 M0 z  N14
15
$ q* a% y+ j, v! E2 E; \16
17
! \4 n0 i+ Q) ^" v18
19
  M( T& Y) D8 z/ c1 s20
0 U8 G! @# e$ J4 J21
5 D7 S  o# B- d+ L5 n9 T22
23
24
* Y9 a- d- y7 B' M7 S25
2 h0 }$ L7 S/ ^2 C' C4 J  q26
27
28
+ x- K3 C! Y8 s& K5 P  w29
2 o" o% x: ~# q5 g30
31
32
33
基数排序
+ J" A9 [. m5 m9 ~% O! h. a5 l找到数组中最大的数，确定最多一共有几位数。
' [$ D# M. Y: i' W( Q! {! z  ?0 ]按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
9 e! c, q/ _) X# I0 P, j将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
- p* A0 N: e6 l% N4 U7 T! a

代码实现**


public class RadixSort {


, O3 ?6 I5 f( V# c* x* I. O& p        public static void main(String[] args) {
                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
# e. \0 g' b7 t  S' m! v% d                int[] arr = radixSort(array);
  k0 F$ q* Q! n5 |) W/ d6 K& F                System.out.println(Arrays.toString(arr));
        }
; J% S: t7 D; }1 j. d, V* H9 q4 @7 c
- q, z( |, D( h, ~
& K4 w& S& Q7 y( B/ P" p, {; Q        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
                        return array;
                }
4 o0 S$ c7 ]. \4 _& x, e3 ?! N                // 根据最大值找到最大位数
! i) _! Q" [$ b                int max = 0;
, L( N9 l" c  V; s3 H                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
! W/ `5 I4 r6 \( B% W                }
8 o( A' M6 C* A$ j& J8 @: u               
( }4 b- C0 B/ ^: @: X, {& Y5 f7 ?                int maxDigit = 0;
                while (max != 0) {
/ E& d* T' r' t( r+ u$ u& p                        max /= 10;
; i3 S" P( s. I8 N8 w! ~0 p                        maxDigit++;
                }
               
                // 第一维: 0~9
8 P$ [5 s9 c2 K8 }6 e2 O3 P                int[][] radix = new int[10][array.length];
& E+ [( J' t1 B( w. y                // 该位为 i 的元素个数
  A) }  m  _- b, K' `" ]: N5 F                int[] count = new int[10];
               
% H* D- \9 \: j  |' v4 t                int m = 1;
  H; U. m# W" r* T: H9 l' \, Q                int n = 1;
               
                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
8 H$ J+ C* Z' U3 J7 c/ {                                int lsd = (array / n) % 10;
; m) n3 r- V/ B$ I( y8 \                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
                        }
- I( R# n3 \, m) G& R+ P5 y                        for (int i = 0, k = 0; i < 10; i++) {
8 `1 ?9 h% K" r% h% f+ I                                if (count != 0) {
* g& R$ ?/ y% Q2 L                                        for (int j = 0; j < count; j++) {
+ l& e: R7 Q# J& S# t. l9 I* `7 N                                                array[k++] = radix[j];
) p* p- s. U. X0 h2 {1 f                                        }
                                }
                                count = 0;
                        }
                        n *= 10;
. u4 `0 v$ C1 K4 Y! ~                        m++;
" d3 {7 ]! O' @' s. c/ y$ a$ o8 J                }
+ G; Q9 g+ G) ?* c1 E% r9 [                return array;
        }

" A' Z/ Y4 ~/ ]7 }
9 L1 F- b1 M- Q1 E}
1
# b1 z& B! v" N2
3
8 j9 s3 M* k# X6 }2 V/ z  u1 P4
5
3 l+ K& }" [: F, T. c6
7
( v7 z+ U6 j% ]6 n# \! `- C% i8
9
10
: Y1 D( g( Z+ d11
' Y8 W) w+ W2 c* r6 l$ i/ S12
* ~  f, l$ v, K( I13
14
& y* D- g# U) I1 w# s$ h! g15
16
/ i3 T+ p- [1 S* d, K; W17
  o8 D7 C9 L* r) F+ o18
19
20
& \/ }: J4 M! J1 b1 U% x21
22
, `' K7 n. _# s  ]& k- k. c: w23
24
5 i. y& H" s! {25
26
27
) A$ L, U7 V% h6 `6 z28
29
30
  s/ ~1 f- L$ w2 U# `: }31
: l4 V2 G: L4 n+ t' w32
33
34
35
36
37
3 t& t$ l! M4 l38
+ a/ W3 t4 D+ l" y# R. V# T39
40
4 A% Y0 e# U* S( k# U( r4 W41
42
. Q- U9 b& [5 @; W% a4 r6 y% R) r43
: z) O8 I7 s1 d44
45
/ w/ n) y( G0 [' K: q- @3 O3 Y46
5 b) q# N  V" J* t47
8 j" P; u7 L- h6 q8 ^; p48
. D% w! S: Q4 F" h$ W+ _49
50
; z7 ^; b$ E% ^/ z51
- l2 H% T3 n' G# h( l, m, x, g! j52
53
5 G; ?" L2 X- `0 b, j: A计数排序
: A# t- v) @* \: S) v0 u' _) F  r0 v7 D  U找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
: U4 _; D/ ^7 @, {- R统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
5 A1 [0 d3 Z4 x& C最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。


代码实现
  n0 p8 y; e! G) v) H% G3 A; l
1 y" D0 j! e  w$ U' y
public class Solution {
8 M. T' _2 Q6 \5 `) l( w
7 m! k; j) S" s0 I1 G6 t# _- [
, V+ c' z# C# y. B3 M4 O3 ]6 e        public static void main(String[] args) {
3 j) T$ V7 u  [2 P3 u$ l' j; S& Q                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
( Z! Y, I. D* E                int[] arr = countSort(array);
$ B; k1 U: D4 _7 @                System.out.println(Arrays.toString(arr));
& U3 j9 {% {/ S8 Z: W! j. ^- R        }
. C* I7 `. r% `/ d; V. M9 l: b/ h
. O0 s9 O& A( v, D) R4 X
        private static int[] countSort(int[] array) {
                if (array.length == 0)
                        return array;
               
  r; S  o7 m  `! t0 e  M& V2 s                int min = array[0], max = array[0];
3 a5 R% K4 X( Y( P3 d4 D               
                for (int i = 0; i < array.length; i++) {
: Q. _3 l( X$ B+ u5 I; K/ X                        if (min > array) {
+ T) D% _- b) V# H+ V6 M                                min = array;
0 W- N6 `+ X+ i                        }
                        if (max < array) {
                                max = array;
                        }
                }
               
2 A% }6 _8 b; T6 k0 F8 K3 y" v' o; |                int[] count = new int[max - min + 1];
               
                for (int i = 0; i < array.length; i++) {
' ?$ U( I4 N$ H6 o2 L/ M6 c                        count[array - min]++;
                }
               
  Q$ I  Q/ `, v1 z& p+ ~: L3 \( o                int i = 0;
% ~  I' {2 K# [  x; r% T                int index = 0;
/ I) b# p; v2 n% Y& _1 B                while (index < array.length) {
                        if (count != 0) {
                                array[index] = i + min;
                                count--;
1 C* f8 O/ E4 ?& a, J0 p, N+ M& w9 s                                index++;
                        } else {
                                i++;
                        }
                }
                return array;
6 I# p$ G; j* }5 u  B7 A) |        }
# |1 {( P2 S: ^$ Y       
' w9 \  T( L( Q* t1 s! n! A}
1
2
3
4
9 ^$ r+ _, e+ `  X5 y5
+ `# z: L6 g2 Q: c  W1 s1 ?6
7
% l& @4 F' r% k9 a% c, K4 w8
2 N- t' M: v; m5 {. i! f9
10
2 a, @+ g8 b: X* o" ^/ p, W  B11
12
13
14
15
16
17
; X8 D/ X5 @/ y3 o8 Y18
19
8 ^7 r( C+ ]# |/ F- U20
# v& H: m: _6 |: z( s% |+ W; {21
22
( J" H8 r8 D! e2 z; ]# @( p23
24
25
* p7 v9 \) L  C26
+ C8 M6 }5 F! f6 W! L27
28
29
' l4 {; a+ u) U( g) I( X8 U# |30
* U/ u; y+ q; m31
6 J8 q( O9 P. O# j+ A' ^32
33
34
35
% H* m+ `+ t$ C4 b/ m: j36
/ K" y0 t) X7 Y7 Q37
38
% H1 U. g% w" L39
% B* k  u4 @0 T, A40
) n. @2 |1 ~; f/ W7 u% e& W41
% j2 n6 Y. B. T- E7 O42
43
44
' E, E& `1 P" n; K桶排序
6 z7 L( m: p3 ~————————————————
! Z- w. Y/ A4 e( i; r7 z版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153

$ ^: n  q% X- Y6 A- X