十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）
- s4 h7 K: R& ]7 L. g" s9 e
: ~9 G5 l. ], r: K4 k& c十大排序算法（Java实现）
2 n/ L3 B3 c  }排序算法框架
8 L) q* o1 Y; k8 J/ V排序算法性质
0 w& M" ^  l5 I* l插入排序
直接插入排序
希尔排序
$ ]1 z/ a- m9 h% R选择排序
: S& O8 t0 f: y2 @* d6 x简单选择排序
堆排序
交换排序
8 u  n% V3 x- G! A冒泡排序
快速排序
归并排序
& z4 o4 U+ V2 Q; ~# o基数排序
3 y: P" J* E  K$ \# }, O计数排序
4 w" b3 Z6 W7 Y, Z. Y桶排序
更多文章点击 >> 这里
0 p: R* h# `; y

$ }. f4 s* \: p+ F) {! F排序算法框架


3 x+ c) g1 V- P& w
/ k( U3 I( ?3 b
* t' @6 g" c) w4 H% M5 Z排序算法性质

, v' _3 j; o( e
% \- v$ r7 X( D2 F
' s) n0 W$ ?6 Y7 {6 O( i
+ U! e5 Z. G$ C' _7 k插入排序
直接插入排序
5 W2 e0 Z% e: L! f) f0 K从第一个元素开始，认为该元素是已排序的。
4 D  p5 C+ [; [- a9 k取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
; p1 ~5 H+ A9 x" F最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2
) 。
) E" z* `  x: M! B

代码实现
0 l" |  a+ x" u  M5 d  `+ g
) @0 x. M+ B' w* d: I- j( o. M
$ o; Z! p) G: M4 L$ z% P7 X' A8 mpublic class Solution {
        public static void main(String[] args) {
5 u/ |. P% F5 |8 J1 Z3 Q                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
5 Q. B# O6 e( D/ _                insertSort(array);
                System.out.println(Arrays.toString(array));
        }
9 |, k3 R' M" F- J* G

6 u+ E* Q6 l" P2 C  V        private static void insertSort(int[] array) {
( ?. _0 `! ]9 n) B7 T                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
                        int index = i;
; Z6 Q# p1 L# h& j2 t                        while(index >= 0 && array[index] > data) {
) A" Y8 r6 e3 @# F                                array[index + 1] = array[index];
                                index--;
                        }
# m& c' n$ R; N0 X                        array[index + 1] = data;
                }
; s. [3 l$ P( n        }
7 w1 {: |$ E, @. H2 k% S) |& x}
1
9 P5 e8 ], D- ]+ @2 c2
- |/ r' a! }0 S6 @& j3
# m+ t# ~/ {  M0 I4
+ S+ {: v! ?- Z( J8 G  Q& A5
' |9 _  D' o/ |* L6
7
) B( N* _  s( `, F) n9 D) H) H8 f) w8
9
5 b: b0 P& w) D10
11
4 M) z7 v# h: y9 n+ H/ ?0 H% b12
8 p- P. ]8 F2 C) K5 w* K13
) G- ~2 @0 l6 _8 p5 K14
4 }' G5 \. v3 o6 N4 X0 w15
16
17
: k# K7 C- l# w2 N, l' l$ H# A18
: u* I0 \, u$ l9 J' X% S19
8 ~' N- N8 w8 R! a- B希尔排序


时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

7 Y6 S- V$ G! C9 u4 q1 ~
+ ]0 V7 M8 o4 E( I; k8 R; _$ O代码实现
$ k  f- ~* ^* ]3 m6 M; k( F. y
$ z1 C0 N: j. i5 p2 j6 p
0 ]3 n3 l2 N7 o/ h* g6 z% lpublic class Solution {
- b5 A6 P1 a( W$ A& _        public static void main(String[] args) {
  e% ~4 B3 Q! ]                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
5 b& |+ w1 m' d8 b                shellSort(array);
                System.out.println(Arrays.toString(array));
; h' O) ?2 S; o0 A% J        }
4 p" g. B* k/ |. b+ j2 D
' A) h; x0 C& Q. P. L
# \1 M+ ^, g/ M. F' f- T, |        private static void shellSort(int[] array) {
; c) W6 l7 b7 V                int gap = array.length / 2;
! \5 c' |  K1 e) i" n% U                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
                                int index = i - gap;
) r6 {! M8 Y$ [4 S                                int temp = array;
& k4 Y; `! N5 Q+ b4 x/ e$ E                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
                                        index -= gap;
- k$ `% o7 Z# Y) j                                }
//                                array[index + gap] = temp;
                        }
                        gap /= 2;
; S# p6 g! g7 `                        System.out.println(Arrays.toString(array));
. D+ v3 x" S& X+ F! e* h6 P1 V                }
        }
) C% t* k+ u, j, O5 j9 b

        private static void swap(int[] array, int i, int index) {
                int temp = array;
                array = array[index];
+ L$ F8 X2 V# Z4 ?9 K                array[index] = temp;
        }
}
$ ^  r3 W" M4 |2 r# \- d2 @1
2
( ~6 i/ ~& X; g5 V' `5 }2 F& e3
7 _7 _$ H0 q; Z3 y) i+ P4 \& }2 e4
% X4 v+ C% W' n5 {( v5
7 I$ ?: k; N+ B4 H2 c" P6
7
8
9
7 k+ O' t% m/ A10
11
4 o  V) O; D8 i. T2 H+ ^8 B12
13
" J. K* ]; E, r/ Q. G9 r! ^& _14
15
9 j2 H( [( ?& I2 T9 L- i4 I% s16
% q8 Y1 A* t9 J2 {- ^17
18
0 F8 e3 n6 f) {! Z2 E: f19
20
21
22
23
9 U" x' A5 M* i! J8 ^24
25
0 ^8 Z1 D4 E5 c( a" k26
27
; K/ S3 o* s6 G& @$ e' H, f28
29
3 J- p# g# w3 U. t5 ~" S7 e9 y30
选择排序
简单选择排序
4 B* w' h- V# l% v% n) m从未排序的初始数组中寻找最小元素放置首位。
4 i$ t' G$ J; [从剩余元素中继续寻找最小元素，放到已排序序列的尾部
( \  ]* t! `; _1 V2 R遍历数组，直至结束。
1 M/ h0 x3 `' k) |) P5 ^4 N时间复杂度为 O ( n 2 ) O(n^2)O(n
' T1 h7 F9 J4 d$ L8 V  D2
) 。
. n% n4 n& n# [! v4 a' U! C

3 t6 @! p7 i* I: q5 k代码实现**
3 ~) z* R5 \: \% I, ]: g
) C3 Y- L, [9 f9 A: x
public class Solution {
+ h( S1 ~  Q; c* F        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
5 \$ K( r* I' i6 k                System.out.println(Arrays.toString(array));
* c: D" O" W. c( C( b& j. f( t4 v        }


5 I6 Y6 o3 |' P4 p7 }        private static void selectionSort(int[] array) {
) o! M: l- h7 K: h7 f                for (int i = 0; i < array.length; i++) {
                        int index = i;
                        for (int j = i; j < array.length; j++) {
0 g  G+ C8 M9 b- M                                if (array[j] < array[index]) {
% s1 ]: K+ }1 m* Y8 J                                        index = j;
6 [) \5 }/ {$ [                                }
                        }
1 |, S! x" d' Z6 V; g                        swap(array, index, i);
                }
' M/ q: o; I* L$ s, d  N0 H( S& c+ e        }


% s' a- ~6 w; H. U5 t4 Z        private static void swap(int[] array, int index, int i) {
! W- ^( F3 s. d0 j* E$ z* D1 p                int temp = array[index];
                array[index] = array;
                array = temp;
( Y# E/ M: K. w8 \( Q+ q        }
  H3 Z: `$ Y3 X) V( M}
1
2
3
+ b+ w% S& l$ ]4
% `% {4 N$ [- C2 C8 }5
6
& t7 N0 |0 L! r) g) s' T3 r7 `7
- ?# z' Q) E8 }2 y# L! j* r8
9
/ ]8 E7 N; V5 a7 L6 D+ A( k10
! n0 B+ r' G2 c% A1 O6 P7 C8 U. u11
12
! j  l  W' P# K( S: u% Q13
: `+ i$ q+ x4 l* g14
15
" F" w" v( ^- Z8 _$ i8 H6 c' Y# N( s16
17
18
19
20
21
22
' A! c1 ~4 v  Q8 {# w( h- ?* C23
$ v" f6 b1 [1 ~# K& E: |- Z24
25
+ N( _1 }0 i( L0 w3 u; ^( ~堆排序
+ n" `: A4 \9 A) c时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
* V: u& s0 m5 o# B  A* V& z

: z, P& l4 S6 X7 L代码实现**
/ |: b% Y8 `& F* }' t
0 |4 v; h8 G0 k
* q2 S9 ~! K! I* C, Jpublic class Solution {
: s! ]: b9 X+ h2 C+ k: Q5 N/ q        // 建堆
5 o$ S: s7 W& K" V4 v. n/ C) O        public static void creatHeap(int[] arr, int n) {
" W& Z# ]9 V5 ]: M8 Q. g3 A! p                // 因为数组是从0开始的
% ^6 [; ]9 F2 D; }1 a# o) {                for (int i = (n - 1) / 2; i >= 0; i--) {
5 P" f8 k$ K( u( r. _7 e8 W                        percolateDown(arr, i, n);
8 t; N8 X5 h# n/ ^# W                }
        }
        // 插入
3 D, ~3 F) T" i, d- D! j        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
                percolatrUp(array, n);
        }
/ V& l) P' D( [8 r9 s  S! c        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
                arr[0] = arr[n];
# t- u( o' S! m  }. a$ U                arr[n] = -1;
8 D( O7 l3 F; H5 K" a                percolateDown(arr, 0, n - 1);
        }
        // 上浮
# v5 r% H" [, w, r        private static void percolatrUp(int[] array, int n) {
. @2 T# h  r5 m; \+ Q0 F4 _; `                int data = array[n];
% ~4 q4 d4 Q; h# j' W                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
! Y/ L# a& {; l% X! I1 o5 j                        array[father] = data;
                        n = father;
                        father = (n - 1) / 2;
                }
                array[father] = data;
        }
8 n& G+ ?% ?! W. F        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
  u% f6 U9 L* g8 B. u2 m                int child = 2 * i + 1;
% b, q8 V: p( z  J) C' E                // 遍历整个该根结点的子树
                while (child <= n) {
                        // 定位左右结点小的那一个
! m. P8 U1 n$ _8 [& ~                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
' c# H7 Y" y, v7 T                                child += 1;
2 G! L7 x/ T6 R$ Y% w) j+ }                        }
; T& k* a, o0 [" K9 s5 l                        // 若根结点比子结点小，说明已经是个小堆
& o0 E& b* [! R5 B& a( l7 \                        if (father < arr[child]) {
/ i6 x7 M2 R& o/ a' D/ ?. I                                break;
                        }
                        // 互换根结点和子结点
  ]4 v& T1 A7 W3 e$ y/ b; C                        arr = arr[child];
* _5 w6 V) r3 A: I% l+ m1 T! W                        arr[child] = father;
7 h' R" x+ h% ^- c                        // 重新定位根结点和子结点
, s  ]0 W- q, F" n" D# o                        i = child;
                        child = i * 2 + 1;
" y3 F) |+ a3 E6 a                }
; ?' {0 o2 _- q! U$ Z        }
/ t% Y1 E! G/ b) {5 P( l  g5 A( q* N   
        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
) O( h8 V* X% ]6 Q/ `7 g$ H               
: Z& k: M  }$ f( E! P# b9 N                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
9 `$ ^  T1 l. e: m5 y                deleteHeap(array, array.length - 1);
7 M3 _0 A! ^5 f: Y" C- y                System.out.println(Arrays.toString(array));
0 K' ^4 ?' k5 W; r0 y2 |# o               
                deleteHeap(array, array.length - 2);
5 ~6 @1 N' }& H* |  b                System.out.println(Arrays.toString(array));
               
3 y- W7 R* }# H                insertHeap(array, 3, array.length - 2);
6 z* L2 I# ^2 d7 t% c. M1 t                System.out.println(Arrays.toString(array));
        }
}
1 e# l  g* E2 s$ _( J1
2
3
4
5
1 G3 n/ R! B- l: [  f  _6
) \2 c4 _) `! ^* q/ o* y" r( u5 {7
, }  X, @5 s; q3 V! n' X8 x8
9
10
11
12
3 Y5 _0 H2 c& T4 U8 H' J8 q  e13
, i8 j# p- ?1 B7 I( \& X# c/ d14
15
: e& s( A2 {- Y7 l' X8 t: [16
" L& f! I6 m3 m17
18
19
20
  V$ s  f$ V$ _( P8 T21
22
3 o! s; s, T: _$ j9 l& H; l0 N8 ]23
# R1 S6 T% `* w" R24
5 P6 I' ^5 [; l; E" w, a25
26
" H, B& S0 `& g! U2 n  h7 h# ~8 Q& v27
28
29
  V" Q% p) @3 Z+ U30
" d1 j, G8 [* A& r31
+ v4 d% m5 }3 ^32
33
34
35
5 e. n$ U0 Q2 l4 L, m7 K# o$ F$ c36
, Q" j7 z5 R1 K" o37
38
39
1 o! d: ]# ?/ U, e40
41
4 R" A4 ]& I; Q42
43
# \/ e: V- ?6 n$ y8 N0 u1 E5 k/ D4 @  {8 Q44
45
46
8 W6 s1 [) x3 c7 A. F4 p47
* O2 \5 [8 u, u3 A3 ^48
49
- n: ~1 j: M) L: [8 a& d" G& F50
51
* x" r+ M: T  R+ C& R8 F52
$ ^/ m& c$ j6 {+ }9 ?53
54
. `/ z2 k. m2 Y4 Y" Z1 Z3 ^55
56
/ M/ a+ d! u+ [: u1 f9 W57
58
59
60
61
62
4 _# ~4 `( X) a63
64
65
66
67
68
69
. z# c8 J3 \8 P0 H8 ~70
交换排序
: b5 k( a& z6 J; \+ R- m冒泡排序
6 z, ^. `: o/ y) U依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
& G: [  w1 n: @( T( D$ p" h3 a' p遍历数组，直至结束。
4 @2 u, C" A/ N( w# l- x* b# d# X最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。

5 S! Z6 ~0 P' V  r+ n
0 w( @# `8 R+ j3 t; @! w2 y2 b. K代码实现
, e- g- q8 k. f

import java.util.Arrays;
- Z9 w6 E: ?/ l* e7 ~1 Upublic class Solution {
# J5 s* c: c( q& {6 I       
% j8 @0 j  X% a, E" d" V0 s        private static void bubbleSort(int[] nums) {
                // 循环次数
6 l0 v4 |5 P* t+ N8 M, L3 i                for (int i = 0; i < nums.length - 1; i++) {
- `, j+ v+ U& M" e: E: ]                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
                                if (nums[j] > nums[j + 1]) {
: w$ j  P$ d/ [; F0 m2 k, I0 }                                        swap(nums, j, j + 1);
3 `7 s6 d& |- ^/ b+ J' a$ A                                }
                        }
1 L. v5 _5 Q" x' T                }
2 k: v2 E+ L0 W5 f! I% S1 z        }


        private static void swap(int[] nums, int j, int i) {
; `) A/ ~+ p! f                int temp = nums[j];
. q" E; \3 u9 s  a! |8 R3 M0 K+ J- ?                nums[j] = nums;
                nums= temp;
        }
' F9 v/ F; f* x) O7 R- m6 K" H0 u& P
% \0 e$ b; a# {% ?5 R, K9 g, b
        public static void main(String[] args) {
7 k/ L, C1 r! }5 F6 s' ^                int[] nums = { 6, 3, 8, 2, 9, 1 };
$ m8 I2 b3 g" @- G4 J; H                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
) ^- f& o6 {2 H% h, E2 y9 b" C$ E& }        }
( T% M# F  E" O* h8 b' Y/ H* j. E}
* L; f. T5 s0 ~  J+ ]1
  R, J8 @. @' f$ [4 h% P9 R2
- H" K9 k$ Q3 A: b' D% p: `3
4
5
( m" r' S( k. o& s/ Y* t. O6
1 i, o5 M; G6 d& Y; M7
8
9
0 y+ i! L2 E$ R; w. |& f10
& T4 X: T! P+ b+ @11
12
13
- o/ B, l3 e; U3 c4 c14
15
16
  K1 u* i" C# H17
) H- h* \6 n1 Q2 e( t18
19
# d( w. P2 P5 j2 |20
21
22
! z' l7 {2 o6 P7 T8 ~/ ^23
+ P2 z' m' d) J$ r, d+ r24
25
26
27
快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
" H# U/ W# x9 C9 K3 g
: e4 {5 S* k. g* j" l0 A
- k6 t# E1 X( x' q, o$ u代码实现
2 h* x* D6 \( D3 j) l

3 a! m* R& [0 u! a' ?7 K/ I9 ?public class Solution {
       
        // Median-of-Three Partitioning
* G  q) Y5 [8 P* t        public static int selectPivot(int[] array, int left, int right) {
: {2 X# t; L$ T* J" x2 {8 v                int middle = (left + right) / 2;
               
( v/ S4 w+ n  ~3 P                if (array[middle] > array[right])
. S: `% w% J' g+ _8 B+ y& X                        swap(array, middle, left);
+ W7 A! Q7 S& a( E4 V7 n* b6 `7 r  X                if (array[left] > array[right])
8 x& Q" r+ [; ^9 W3 F4 F( x1 Q' `                        swap(array, left, right);
                if (array[middle] > array[left])
( B# _6 R! y6 j7 t% w* J3 Q  ?, l                        swap(array, left, middle);
               
$ c8 u0 }- r. s8 w8 |$ D                return array[left];
        }
       
9 a3 f3 ^7 g( S9 }- o& X        public static void sort(int[] array, int left, int right) {
5 ?, K7 [$ `9 s) w$ ^: z                if (left >= right)
                        return;
/ y) Y5 g; f' |! d                int index = partition(array, left, right);
                sort(array, left, index - 1);
/ z5 ~7 C- }0 {' r# a                sort(array, index + 1, right);
    }
       
4 N% h. \' z% X        public static int partition(int[] array, int left, int right){
: F* K$ Z  \$ z6 H2 W. B2 T        int pivot = selectPivot(array, left, right);
        while(left < right){
) D6 [- t3 T( ~5 K' t9 q  W+ W            while(left < right && array[right] >= pivot){
1 b; a7 ~: L1 _; i! }                right--;
- I- L& t2 P+ Q9 s            }
% j! A/ R  R( B0 ~! g            if (left < right) {
                array[left++] = array[right];
( w: w3 g3 _" x( g8 o. _            }
% d8 e; H" i; v5 }0 {! G" L1 g            while(left < right && array[left] < pivot){
+ r+ Q" {1 ]8 m9 u7 S4 f2 x0 K' z                left++;
4 c' G6 g* a9 c            }
: y3 M# U2 I; H4 R7 M            if (left < right) {
                array[right--] = array[left];
            }
2 a# }7 O1 X( S2 X. Z4 ]+ E        }
            array[right] = pivot;
6 E! ?4 Q+ {( X        return right;
+ W, p3 e: W$ e/ _$ v1 w    }
* G* L) |+ b9 ?. s& H9 |
# u, D8 \, n* M0 V' g9 P! d
; c5 I, m& d3 @! Q8 ~* S7 R+ m+ n    public static void swap(int[] array, int left, int right){
            int value = array[left];
            array[left] = array[right];
            array[right] = value;
    }

8 t" J9 [  S* B* y  |- F! i; c2 m" t/ W
        public static void main(String[] args) {
8 O+ h) T" J$ [' j                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                // System.out.println(Arrays.toString(array));
5 E0 Y1 z0 A4 \, ]2 J                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
        }
0 ^8 W7 H' \6 t# x% V- d}
# b: l: T4 r8 m* q8 Y' Q$ @1
2
7 {& Z+ X; u& t) L4 D. _5 a3
% H' z* Y9 |+ s4 D# c9 ~2 N  Z4
7 j* v+ F. z0 G8 D1 ]5
6
" s; d6 ^8 J, B: D% m; z7
8
( U/ a7 \7 v6 v* ^) H9
10
6 u+ m: `0 t* ~; |; l11
12
13
4 }5 z$ z' j! V: _: I3 z; y1 Q% ^14
15
& ]4 N, Q: g: {# e! ~16
17
18
19
20
21
22
23
5 C! W/ P( }5 q- {- r0 w24
25
  p+ |6 g: G  O: v5 Q3 w26
27
28
; v; q) G' t2 p# J: E% ~29
30
$ u1 z* G7 {2 q# x  I6 j% I: ?31
$ N0 z% j( v: g9 G32
33
34
35
36
5 G# {  W* V/ D0 T3 F37
+ {4 Z3 H4 P8 M38
3 u& l# M. r: a! E/ v1 H( r39
0 Q0 o6 P4 A0 _1 t! U  Y' z40
41
42
43
44
7 X- s# D, }* C8 L45
46
47
- _6 g. R, U( F3 b: Z' }48
' n; [6 F6 z& A+ [/ J) v$ t49
50
51
* y" v  f6 N! ^" ^; m+ V2 f52
2 D. s( b! n2 ~53
54
3 \' K1 }: Z& t9 w55
, h7 z! v) k4 z' c1 D/ Q56
; I& ], c! \3 V# x) U' {57
归并排序
* G9 X8 U5 X( x7 c! n3 N将长序列从中间分成两个子序列。
( I5 N7 }  p$ b+ [6 q, O6 g对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
- ~2 R5 d7 Y) m) U# C平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

$ c* U5 _0 v; w2 Q. O+ U" }( o- l
代码实现**


public class Solution {
        public static void main(String[] args) {
+ `7 \! v5 u4 T; _; L, S                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
1 {- |9 T7 P2 k; G+ x' {                int[] arr = MergeSort(array);
$ w" k# {9 w  ?9 e                System.out.println(Arrays.toString(arr));
        }
5 ^7 q# x. D, _, I
6 x2 r& X5 E: E$ e
$ S6 o" [) ^6 t! V+ N+ B+ |        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
                        return array;
6 Z2 q/ N, z, {6 l, U! w, E4 ^5 A5 ?% [                int middle = array.length / 2;
$ V/ t2 z9 A( ]                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
0 n4 V$ K3 p  ^' E                return merge(MergeSort(leftArray), MergeSort(rightArray));
& I$ j4 I) v$ i7 O' _        }
" b( B! c6 e5 e$ |" r, O. b7 v

        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++) {
. @6 F3 O6 A  A, z2 k& Q  S- m                        if (i >= leftArray.length) {
                                result[index] = rightArray[j++];
                        } else if (j >= rightArray.length) {
; [3 C. w* l4 t# l% w                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
                        } else {
                                result[index] = leftArray[i++];
' s& ?, x+ g. j8 {5 ?: O6 g                        }
, X, j1 N- S. x                }
                return result;
$ E9 s4 h& N- r. D, r8 W        }
}
! |) {4 O6 O8 a9 h6 k/ u1 s3 F

- G+ X) q1 z* F/ V1
2
" w% b- N% l1 H5 K3
4
5
6
7
7 Q/ r" p( `; |4 R8
# K7 s& E' ~& s9
; s$ _6 [2 M' ~10
2 V" K6 n- N; M7 a2 Z7 R11
, R/ i0 ~: C3 G12
5 w3 R% _1 [7 P2 E6 J7 U13
' I/ D, V  o/ g/ v8 Q' R0 y7 F14
15
, J( d4 w, e0 y6 J9 e; O16
7 S: h1 m" e& A& G( Q, X# ?; L17
8 u. ^0 A* v6 G- L( A: I18
& {1 y& {# Z7 f7 S; v19
* s3 l: h- M: O20
! Y5 |$ A6 Z. z" a/ x21
22
23
2 J& m4 Z7 R8 _24
25
26
27
: D! Z4 u8 I) O  x/ A: [28
29
/ _7 G( g6 H9 \5 o: S" I8 Z30
31
32
/ Z4 \) G, T0 _( k2 Y2 ^5 \: G) R33
7 H8 H, ~. a  d+ q! {+ f基数排序
, @2 @' M& I! ^( D) D) O( s- G找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
$ E2 O" Z6 E) M* n, q时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。


* k( y4 O4 j1 |/ s8 O# o! [0 I代码实现**

& F% z1 {) {2 C$ B% E' ^
public class RadixSort {


  l1 F/ @5 n' E; g* ?" [: @$ Z) J        public static void main(String[] args) {
                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
  m5 Z$ b9 Q& `& Y$ @                int[] arr = radixSort(array);
  J! n6 ]( f# s/ v/ _" ]( s                System.out.println(Arrays.toString(arr));
  @/ P! s+ _+ J        }


        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
                        return array;
5 z0 Y  U& d9 O  o& s) y8 S                }
                // 根据最大值找到最大位数
7 e5 {. o1 ^  I+ A- C* E                int max = 0;
+ Q, a: g' K) t9 b3 V) {                for (int i = 0; i < array.length; i++) {
+ X! D& K# v& j9 g                        max = Math.max(max, array);
" {0 }5 }1 B0 P8 g* G9 K                }
% z5 w" h4 p9 E+ w3 `" |               
( L/ R+ K+ n- t8 P! l4 T5 D                int maxDigit = 0;
. L7 E+ w' ]1 v$ U  k2 e                while (max != 0) {
                        max /= 10;
                        maxDigit++;
/ {$ ~5 {6 w- X+ i                }
0 p& m  [9 d" Q2 C) j, x               
' x3 h) N/ S" s                // 第一维: 0~9
- g. ^) x6 H, q) M& x1 |: G" @                int[][] radix = new int[10][array.length];
. y! C. n9 u& X                // 该位为 i 的元素个数
                int[] count = new int[10];
               
                int m = 1;
: p; U% I" P0 L4 o                int n = 1;
* G; j) y2 X+ M& t               
% `( h7 J2 Y4 h                while (m <= maxDigit) {
% n& G; I; f. |5 P! B! l9 e) m                        for (int i = 0; i < array.length; i++) {
* H  j; y# G3 V1 p1 C" L& ~0 y                                int lsd = (array / n) % 10;
% e% U) [$ u( N, p" q5 k: C( g! Z                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
                        }
                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
                                        }
+ V* Q+ A3 l% o% y6 f8 T                                }
                                count = 0;
& c. R8 M/ K% R! `0 I; K& E                        }
3 t6 u* f( z3 T6 h  ?5 P1 B* Y                        n *= 10;
                        m++;
* q* m( G8 o0 r7 T+ e3 L  {, c                }
                return array;
        }


}
1
2
3
$ `8 o; b) w: T* b  _0 y4
5
6
7
  K- L4 d# g9 T9 r' F8
- b5 i1 A; u) v# @9
* t. x+ E1 `( A. H* ~1 I10
9 r. i' D( s5 d1 X* f1 G/ n" c, d11
2 |. s. \% R% v1 _, ?' A12
8 B3 g- _0 p0 W$ ~6 n' W& U" g13
14
. J$ Z; j( X- w; U15
16
! \! T$ f! V: Q4 `, b17
) O3 }. R, O* d8 l$ f18
( K- q0 M0 i# h8 q8 w# y19
  U' H) |7 E! r2 e$ _( ]! B5 q6 G20
21
/ Z( _( Z, c1 }/ i0 O. a* E22
23
2 N3 D% `8 [- d# [. d24
6 C, O) y- I3 k, p5 b, d5 p" u. e25
26
% {( |8 m8 H- U. g27
( v9 x0 h5 `! A5 l3 i% o28
29
& R) z$ A2 i# @/ K: T( e" ^# V. H- F30
0 X3 l- |9 M9 [+ i6 e8 p- U31
32
33
/ a; I% Z0 I9 Q/ Z) k7 ]7 @34
35
36
3 G7 u$ o2 w# u( B. R% t37
# V0 d! L- U1 K" V. @, o38
39
$ \8 {- ^+ E$ @40
41
/ d. s! ?' Q4 ~2 X1 q42
9 C% U" b( O7 h3 y! C# j8 B43
44
45
/ R/ F( Z  D/ Z+ M46
& G. b, j) t' I- W; \! V5 z47
48
( b- H% ?) H2 j! ~& Z2 K; e49
# r5 H6 O) j7 B. h5 F50
, t# d) P" J+ k( ~+ q7 B) I* Z, c51
52
! R; V: B# d) t: Q6 a4 ~1 `+ w8 x53
计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。


! d! X" C# d0 p; N$ ?2 c+ Q代码实现
" s% }3 a5 U7 p$ a9 {% B: b/ p. z- S/ f8 b
: E7 }" w* X9 L. S
public class Solution {
$ i" Y8 F. v8 n

8 ?2 A' _/ d+ Y! R6 _" V2 `        public static void main(String[] args) {
; I! t( g/ z- Z5 @                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
& `; |3 v! P5 J' s6 I        }


' H9 Q4 ~3 o% B- |0 H0 r        private static int[] countSort(int[] array) {
                if (array.length == 0)
5 ?7 @6 g+ l& I% {' f9 l                        return array;
               
& l+ o9 Z% j, i  @* E2 i/ s                int min = array[0], max = array[0];
               
                for (int i = 0; i < array.length; i++) {
                        if (min > array) {
                                min = array;
5 [: _0 T: X4 l3 x5 P2 B                        }
8 [; P: O' |7 O2 }. T1 O                        if (max < array) {
                                max = array;
4 t& l5 ^$ W0 j7 F: m5 w- p                        }
                }
               
                int[] count = new int[max - min + 1];
               
                for (int i = 0; i < array.length; i++) {
                        count[array - min]++;
                }
- z0 y3 d* S2 M5 Q% _. J( _               
                int i = 0;
                int index = 0;
                while (index < array.length) {
& _! Z* t' j) r2 ~# W/ {. I                        if (count != 0) {
                                array[index] = i + min;
                                count--;
                                index++;
9 v6 f$ r$ w- \6 E5 M+ `& l                        } else {
9 N- H7 H/ V. z# u4 o& }                                i++;
                        }
; y6 A; G5 K0 I& P. G6 r5 a                }
' s* M, [" a4 A3 O                return array;
6 q# P/ g( m; k  p# F        }
) a0 K) O8 V  G       
$ F& z) C$ a2 u, J  `- G9 [4 g}
( l. ^$ Q. z" n- W* F1
% ^) l3 d. Q* Y( `( V% t: n$ C2
1 @3 R  j8 w6 l* _3
# @! W5 T& q6 w7 r  O4
" F- {# z  H3 o* W7 J5
6
: {$ `9 S& t- O( S1 {+ z2 U& l7
2 L0 R7 o& W3 E1 O+ ?6 T% `8
) T& Q: J! j7 p) z7 L% r9
: h+ U% J. s& Y7 b, [7 I9 ?& i10
11
. G- Y* D1 H; C/ E8 Y12
13
9 r, F+ f+ ?/ }5 P; o& V, u14
15
$ M# ?6 m% q0 V4 _16
/ O. C! I( a' E" N, a7 K17
' N9 o* k  p) ]% q6 q. O3 {18
* x) l' A4 M. S6 T; q% N7 \+ `19
20
21
  L" m  @& U9 Z- J5 N% g' v- z22
23
2 H5 U# F* z# D9 d* _" O24
25
26
1 B, r% }4 v0 K$ C27
28
29
2 k8 \3 Z' s! R; o6 u* r! F9 x30
31
32
33
34
$ i, J2 @) k+ n35
36
( _4 B! u2 f1 b$ l  r8 U37
38
  V) i' W- }3 @, G" t39
40
41
  O- R0 u$ i) Q8 I2 g42
43
44
1 d7 G* e# M; U; s7 K/ Y9 s; ^0 @桶排序
& ]+ i& Y; ]5 f2 W————————————————
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153


0 a6 F9 W% c; M+ p9 o# Y4 h