十大排序算法（Java实现）

杨利霞

4 ^. W0 j) t- t十大排序算法（Java实现）
8 Y' S: f  W4 l" B
十大排序算法（Java实现）
排序算法框架
排序算法性质
插入排序
1 S2 g  }) e# A% h直接插入排序
希尔排序
选择排序
简单选择排序
4 o! P- a) U/ y6 k6 k  ]0 ]1 f堆排序
% H* ~$ P( O9 K  R- e6 m% f交换排序
冒泡排序
# y! b0 |, N* ?. q1 E* M9 M) g  K( P# I快速排序
归并排序
9 O3 S, U$ K: s基数排序
计数排序
桶排序
9 B) i9 I) p" X更多文章点击 >> 这里

' `, Y; P* C( x! S, G  p( Y6 v. Y" m
9 @  p; }4 v  ^, ?: O排序算法框架
. \  a7 F- Q9 J5 r
+ w) F( W- U/ Y2 k" H

' d: r- L8 Q$ O4 `& K- x
' Y7 L0 x9 C$ v3 u0 ?6 G9 x排序算法性质

& J) ~9 U4 H" N& R. [

" ]: n, P$ ]: q2 @% K
# m2 h* i% y  c: |) o  I6 h插入排序
直接插入排序
! d6 K+ v. t$ u2 h从第一个元素开始，认为该元素是已排序的。
6 L! E  N/ q6 Y5 `# O. l: T取出下一元素，与前面已经排好序的部分进行比较。
! `4 K! W# a& N% U! P若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2
5 C- K+ q" T9 d8 ^7 V5 i ) 。
5 i, I* Q, \  V0 P( ~% @: @

代码实现

8 i# d. }; N8 K* ~* E
public class Solution {
) t0 B! _! z: i0 `; H        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                insertSort(array);
                System.out.println(Arrays.toString(array));
        }
/ f; Y& A4 c5 a6 ]. ~2 R
; s  ?. e% ]$ O2 A1 L# a& ^1 [
& P& c+ k7 a7 D/ C9 o3 F3 P        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
4 d, q1 p4 S  Z2 O6 _7 F                        int data = array[i + 1];
                        int index = i;
$ x* {7 p( F0 ?% b5 V* h$ g                        while(index >= 0 && array[index] > data) {
                                array[index + 1] = array[index];
                                index--;
                        }
9 l' b3 z8 Q% o                        array[index + 1] = data;
' V4 `$ K, A7 T; j3 A% a0 l                }
        }
5 r- Q( [2 @, Q7 G( S  j6 @$ C}
7 d+ U0 d% P9 {* e1
2
/ X0 |5 |2 R' {6 {/ c3
4
3 H: D' X- e0 n8 u' \& q$ U5
6
7
  ^7 F- y6 d/ W0 C5 S( b6 M8
8 p9 e1 y. H$ }; F" e9
/ T- {( e/ A8 \" _  I4 `; n- W10
4 f0 V2 k# F: {3 |8 a11
12
13
14
! Y- i) j( j& K$ G15
% D+ b5 T* b0 g1 f16
+ x! V; {  j& @- O0 b" @17
3 V6 }  Y8 B% F, J! r18
19
1 ?: z# j, ~& {5 G) V希尔排序

! v) [& |0 s4 a  w7 J  q
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
- s" G* a+ p/ u% W* A
, Y9 j# b+ b+ K0 h. N5 Z
5 a3 c8 ]  @" S7 W" I) j代码实现


% Q: W/ ~6 G' F" y; A# ^public class Solution {
5 v  J) w+ p7 S        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                shellSort(array);
2 I, P( O4 T+ G  N/ W) D                System.out.println(Arrays.toString(array));
        }


/ `6 w* l$ Y, `0 z. `' J        private static void shellSort(int[] array) {
2 q: x' R' A2 a2 q0 g$ A                int gap = array.length / 2;
0 w# w0 u2 x, g" s$ d3 t5 @                while (gap > 0) {
. j, l  K1 U/ ]: w& O9 }                        for (int i = gap; i < array.length; i++) {
- j; b4 ]% A9 H  g* V4 }                                int index = i - gap;
! q  n8 R. E# M; B; b  l) o                                int temp = array;
                                while (index >= 0 && array[index] > temp) {
+ }8 t5 t" _( O8 j$ R                                        swap(array, index, index + gap);
# T5 g9 s8 \$ q% h7 A                                        index -= gap;
                                }
$ h5 g. R5 |* f5 {//                                array[index + gap] = temp;
                        }
& w9 {: w0 O8 r; T# f+ N                        gap /= 2;
                        System.out.println(Arrays.toString(array));
2 z+ ^  b6 t% m! A3 o( _                }
% w6 S& K! R1 i( S, m        }

! e. H2 N( c8 F. W: V
        private static void swap(int[] array, int i, int index) {
( }. m$ V" V" J) v1 c                int temp = array;
* l' U  k, n9 X' K3 P6 E  l2 B                array = array[index];
                array[index] = temp;
& G  N$ Q- a! }! c0 G8 @        }
% ]: O! G( v, ^) L' g) {, k}
1
2
3
4
5 ^+ B% R" O, ?5
6
3 B+ N3 o) O+ C5 j7
8
  m. J3 q4 o( L7 }0 M6 m9
* @4 L8 _0 F" G# T: M, g10
5 k7 O$ z6 C$ V) t6 l% T7 N1 T11
: L8 \+ v4 h# N! K9 L12
# v! M% R* E( ~# K13
14
% {( S% V/ |1 P: \. B15
; n. X2 ~. h8 L. G2 F16
5 |9 `3 \3 Q" M7 @0 W17
1 Q) n3 v1 Z7 Q/ y: M4 Z+ K9 |18
* y! n3 i! c6 D; G! _" t$ x, E19
20
5 Z4 }9 X3 t7 g/ i1 p4 L& g5 m21
/ C% T8 b. u% b; {& E& p22
23
& k3 s9 y$ L/ p& x- }24
25
% W2 C; W3 q6 P1 N2 t, g26
27
5 z0 L; B2 j. h) u' a$ u28
29
6 Z/ q* N8 @: F, Z4 l30
& T9 h( |' Y2 ~: Q选择排序
: [" u( \- }/ R, A# D1 \  G, b简单选择排序
2 i& O# o3 ^" Y/ f$ O从未排序的初始数组中寻找最小元素放置首位。
( i1 o: v0 k9 q  T$ n# ^; `" h从剩余元素中继续寻找最小元素，放到已排序序列的尾部
& K/ k9 y/ J, @8 J1 m+ l% t3 D$ _, R遍历数组，直至结束。
5 Y- P$ i9 E, f时间复杂度为 O ( n 2 ) O(n^2)O(n
; ]1 t# Q& b; Q, c* s* `# v5 |2
6 X' T% b/ U3 R; p ) 。


  ~$ T. Y- L% d! V0 Z代码实现**
0 b: u# U. z" ]3 ~6 s# `/ s* L
7 ^% v& R3 v  {2 p
8 O5 n4 Z# m- K0 @public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
+ P: m) O4 p" i, [8 e) Q1 `                selectionSort(array);
                System.out.println(Arrays.toString(array));
        }
0 ?4 e# k, t3 K3 g
- j& ^# t2 S, ~5 x* L6 L. D
7 j9 a" J8 q( A; `% q" Z" m        private static void selectionSort(int[] array) {
. V& e! Z; h& ^8 a" J; b, q/ [                for (int i = 0; i < array.length; i++) {
% M" L/ {0 q: c+ L9 L  U                        int index = i;
                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
; w5 g* o; I; y# a, B3 r2 Q                                        index = j;
                                }
                        }
* o; x4 m( m+ ]- B3 z                        swap(array, index, i);
                }
& I$ |. p$ k  u, f        }


' t1 G$ t+ B& ~7 \- @# J! f4 J        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
( u" a" o% a2 h8 q" H6 h7 W                array[index] = array;
                array = temp;
        }
& p# R8 u/ a2 M2 S+ u5 ^- c* t# B, Y}
7 k0 ^6 [9 T. U1
2
3
4
. V& a8 y, Y, v1 Y4 ]$ \5
6
$ s6 I! G/ v# C5 X" \7
( l; h. _  Y& v7 V! ~8
9 G- M' L, b3 a9
10
' x- t* k7 u) l  A6 Q11
12
13
14
6 `9 s; U7 b9 ]9 y$ `: N) t15
. k% i; R. L. M  @) k0 \" k16
17
18
+ N8 r: f  W6 a0 P  n19
, Y/ |8 |+ y$ @3 ]20
* |$ X" z& z$ O: O( b21
22
23
8 b! d4 N* j1 X8 r: h24
* H! S' n$ J7 @" B25
9 J# {4 h4 M& d+ A- h堆排序
# }$ S" e  h5 x3 C1 n- A时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
8 l* w6 y1 n. v; P" ~7 B- ?+ ?3 W
0 Y8 K  I" J7 b2 `7 p/ _
6 B+ T5 s' C: s  H) z. J  f代码实现**
  m0 [5 M. h5 K. `) k0 _

0 R$ d" p5 V+ _public class Solution {
        // 建堆
9 w4 e! d7 o/ V" X$ |        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
: B$ G1 G7 c9 `5 I2 E                for (int i = (n - 1) / 2; i >= 0; i--) {
                        percolateDown(arr, i, n);
: G; T: g& y6 A5 z- s  S! [                }
, d2 I  J' |! d4 Z+ e* J9 b        }
; L7 W( m$ S2 F4 J        // 插入
* B) h, ~# `9 C, B, ^# o1 o; f        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
                percolatrUp(array, n);
* W- J, [. \- `: V        }
        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
                arr[0] = arr[n];
                arr[n] = -1;
8 w# C6 _, b- U: {2 c/ g                percolateDown(arr, 0, n - 1);
- m" e8 Y, Q& i# h* W/ t        }
3 y! f  D" f1 B+ B- c& H2 Y& E. g        // 上浮
  M% [9 B) y* H  ]        private static void percolatrUp(int[] array, int n) {
, y1 [6 W1 T. P4 T                int data = array[n];
                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
! O2 n$ O0 D( _( x& x" N                        array[n] = array[father];
2 @2 r; q# `' U  [) H% q                        array[father] = data;
                        n = father;
                        father = (n - 1) / 2;
! @/ _  v' u, L9 [. T0 E( f0 Q! I$ o                }
' S; A# j  {9 {& k: l                array[father] = data;
, Y/ C& Y  o4 ~6 x        }
, i, \' D+ S! Y        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
2 j& D3 v  Y* s. e                int father = arr;
                int child = 2 * i + 1;
                // 遍历整个该根结点的子树
6 r1 _+ H4 m  R4 s. [6 k- m* o                while (child <= n) {
                        // 定位左右结点小的那一个
                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
5 W9 H, y7 z) C0 J. S7 e. A                                child += 1;
; O" b0 M( k# ]* D6 ^* y                        }
+ i/ q1 z0 G0 q( {                        // 若根结点比子结点小，说明已经是个小堆
9 c$ d5 X" I. n/ l8 e2 Q# B                        if (father < arr[child]) {
0 c) C* p& k' X3 h: E4 f8 S$ J& N- \                                break;
7 H) i3 t  T. G- V7 i                        }
                        // 互换根结点和子结点
( n5 ], F8 P5 q% _2 K6 S& x                        arr = arr[child];
                        arr[child] = father;
                        // 重新定位根结点和子结点
                        i = child;
5 F) f8 v1 R8 x4 b" u2 E                        child = i * 2 + 1;
; z7 X# {: \+ i# `, I$ _                }
8 Q, a. c; O  _) F        }
   
4 H* A$ n5 ]2 i! J' U/ j9 ~        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
                creatHeap(array, array.length - 1);
7 i: ~- {  V4 b                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 1);
3 ^% _' j8 R! z" \% `1 D                System.out.println(Arrays.toString(array));
$ l9 ]' z7 s  R( o1 P8 m               
                deleteHeap(array, array.length - 2);
* a& W0 u* H5 j0 o* o/ Y& q5 y                System.out.println(Arrays.toString(array));
9 h& p! R! I; H& v" ?( e' x4 c3 i2 N  N               
                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
        }
}
1
" k7 L. N* ^  a/ R  l2
3
  e1 M" Q' G4 \) Z/ n4
/ w; T% p: b1 [5
$ A. ~) w1 Y- d1 r) }6
7
/ E/ k& o; M7 V' n9 x- t0 H- k3 Z3 t7 a8
9
10
4 s0 O* k8 J6 w; x" H% _11
8 y( p( a5 U! B8 j& }% [- E% {12
7 {4 q5 A3 W# ?$ P" s9 ?13
14
6 d- M5 d' S; h; U' [15
6 x9 ^( R5 X1 r7 U7 I* T16
17
18
  r6 ~) r7 \! y1 u4 j0 h19
* G+ Y, a' d1 H0 j  n3 x20
* ~4 h8 b7 p! s/ q21
22
( \1 P& f8 }/ r5 A" C9 Z, F23
5 {& _7 }% P' T$ b  x, v24
* E5 H, S; W+ |2 g25
8 m- Q) b; t6 w$ p3 {3 ~26
  @. Z* _& h+ c2 @  G/ b27
% Q' m3 R9 M8 g& L! J* E2 d+ L28
29
! h; e0 ~3 ^% |  z" v7 H  A30
. C8 m, {& c4 x" B) U  H31
32
33
" {6 p. q, Y; y6 A4 Y34
" v( T# B7 G+ N5 t35
36
37
! U! |: l- X+ f7 j9 |* c38
$ ^* D( [  t( p& P0 D% Z39
9 Z1 @) N! W* Z40
. ~: X* F( _! M6 x  B41
42
43
44
4 D, i; Z; l$ J+ Q4 r0 x3 h6 i# J45
: ?0 S2 i1 z) ]3 Z46
$ d1 f2 J) `: e0 r9 g47
48
49
50
51
! y- B3 M' a6 R2 k/ l0 @52
  ^% J! Z: T: l9 d- s53
2 p% `8 `# J5 i# F5 r' [# I54
55
, W2 V& x$ Q( U6 a4 e& j% v. x56
1 B+ }) v! P9 ^$ ^) A4 f' |57
% r/ [( ]( F& j- I58
: Y4 v; u% _8 o. `! N, G( b1 s59
  V; Z, Z$ L) j: N0 i60
2 \, n, ]4 z* _1 O61
62
2 j( Q- T1 N3 j0 r0 Y" j: f63
: C. [3 l7 ^& ~, R. p64
65
66
67
( _- M/ v/ o( U  E' ]) M68
69
, i, [. a6 `+ n7 G70
: F" Y$ [/ e5 D- N- [  z% `交换排序
& E% ~5 Z- e: r$ V, c  a+ H冒泡排序
8 E/ q0 o9 w% t2 N# b* V依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
- v: S" |, C3 ?% l9 T在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
2 d( @( d8 }3 ~" X' I( p7 K遍历数组，直至结束。
# v* [( a6 z7 m6 ^4 t最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) ?. ~& l+ o( I7 } ) 。
5 N. i  b4 B& `! A

1 ?+ J; s, |3 M: \/ i6 H代码实现
6 G% a; K' z, G1 c4 ?

# ]& y) A5 Y5 l8 R6 x/ b+ Simport java.util.Arrays;
6 J6 k; S0 I' c/ R; ?  Npublic class Solution {
       
        private static void bubbleSort(int[] nums) {
- n  E* u0 W( G& W1 g                // 循环次数
                for (int i = 0; i < nums.length - 1; i++) {
. S6 L) ], u& X" [/ Z                        // 比较次数
- Y: h6 s+ E5 Q( ^) V                        for (int j = 0; j < nums.length - 1 - i; j++) {
1 L; p& X: V) E" [$ j. p; r                                if (nums[j] > nums[j + 1]) {
                                        swap(nums, j, j + 1);
& Z$ N! M. G+ R& w; o0 |2 b                                }
% }; }8 k$ g. [6 v& R  z                        }
. o  k2 X3 _7 i- c/ G                }
; Y2 H" g( ~( n, A) N        }
1 Q4 N4 i' Y5 X3 h/ i

, A% R, o3 T+ u7 @# F, g        private static void swap(int[] nums, int j, int i) {
* X+ Z4 x, N# E# C2 u9 v                int temp = nums[j];
/ u( B% O- t3 X0 d  F$ R3 E* ]                nums[j] = nums;
                nums= temp;
        }

$ Y6 }( K: B& b" \5 _
        public static void main(String[] args) {
4 N! S3 f/ X8 |1 t7 W                int[] nums = { 6, 3, 8, 2, 9, 1 };
* t; D. q+ h" D8 F                bubbleSort(nums);
! t. ~0 S+ X! U* I3 L( o                System.out.println(Arrays.toString(nums));
        }
7 I- T4 u8 \/ m: b5 w}
1 L9 y) U9 X# ]) n7 X1
7 @$ W8 l, v/ H/ d+ N9 G2
& i& B: o( E1 v2 ^8 H  _3
9 T3 k  s1 W' A0 B. {4
5
5 A' y" l, W+ B' [# L& l" X  A6
3 m4 R( }1 \1 j7
8
9
10
11
12
13
# ?0 ~4 B' S2 S2 n. m6 o14
$ V, ~5 h' A1 Q+ ^* \15
16
" N1 c9 }* N& u- J17
1 i( c' ]5 e+ ~" E18
4 g7 U5 |( s! k  {19
2 ?3 g' e8 w1 ]9 B0 V20
21
- G& C" B) B& W7 A22
23
) [2 |, V7 ?2 H" L, E9 @9 e/ U24
25
26
2 ?& k. B% G6 b% j5 Q% D27
快速排序
9 n- Z0 b1 N& x) B* z& ~% g; P时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

- z+ G$ n0 {# d0 w; Q9 d7 A( A2 Z( y' ^
代码实现
$ {9 |$ _1 Z  v& j, O4 M  G$ U
3 Y7 p- X+ O' P/ u0 p
public class Solution {
       
: T) {, O# o" W; ?* z        // Median-of-Three Partitioning
        public static int selectPivot(int[] array, int left, int right) {
                int middle = (left + right) / 2;
               
                if (array[middle] > array[right])
                        swap(array, middle, left);
                if (array[left] > array[right])
                        swap(array, left, right);
7 q2 I9 m% {0 ?& }                if (array[middle] > array[left])
                        swap(array, left, middle);
, u2 l  N9 {  u               
7 H, N% R5 l' M0 a7 C                return array[left];
        }
0 A; l8 y* r- q. x. u       
- l& e5 s* p! e8 C, s$ ]2 U        public static void sort(int[] array, int left, int right) {
                if (left >= right)
5 h% K% R. y: ~' l% Z                        return;
3 ^' ]: r% F' [                int index = partition(array, left, right);
3 j# T/ q# U' b" y4 M5 ]                sort(array, left, index - 1);
                sort(array, index + 1, right);
    }
       
0 t  ^' B, q2 Z) Q7 ~, N  V; r7 F' J        public static int partition(int[] array, int left, int right){
, n2 q! v4 e! x0 F        int pivot = selectPivot(array, left, right);
( W2 O! ?2 r* ?        while(left < right){
            while(left < right && array[right] >= pivot){
* z7 R& E) ]9 L, m2 @2 s, s, x' t                right--;
! r  x& J/ G- S& W, o3 T* ?            }
' R4 O' X: Z+ n: g6 m! ^            if (left < right) {
& x# u, Q7 L, x+ P+ S/ H! \0 b2 M                array[left++] = array[right];
0 k0 t, o& \9 [& Y3 x; H& p            }
            while(left < right && array[left] < pivot){
                left++;
3 h1 B( r8 c$ M" I8 N+ l( z            }
& @! K4 f# I  S3 U            if (left < right) {
                array[right--] = array[left];
8 L" J3 U2 N  @2 J2 Y+ n1 ]            }
        }
            array[right] = pivot;
4 I9 ~# @. ^0 f  s1 `        return right;
. T% \5 ]1 Q' \: z0 s# d- r    }


    public static void swap(int[] array, int left, int right){
( A8 i) G& R" S: a+ K, P  }5 N            int value = array[left];
& [( @8 D4 l- x9 K* h$ ~6 F            array[left] = array[right];
0 F- a3 G. @3 o' x4 s$ @, P            array[right] = value;
$ J% J3 t  Q+ c$ P0 W# K; L    }
' @6 \2 A8 R: M

$ J" K* g% `5 E# A* T3 X8 ?        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                // System.out.println(Arrays.toString(array));
* Z2 |8 F. Y2 C0 e% q  ~! A8 m9 l                sort(array, 0, array.length - 1);
: ]' |. ^! @% `( _1 J                System.out.println(Arrays.toString(array));
, Q/ L6 K1 a! V- {4 q        }
}
  o% Q+ d* P9 P# ?, v1 T1
( p! E/ l: L1 i2
3
4
2 r; j4 M6 u0 Q- a; j" r4 t5
  S& ?0 p2 \( @4 C! F2 |: l" q# P6
7
  A3 ^  N) D+ Z8
1 R2 E/ E0 L; L" q9
10
11
12
13
14
15
, b6 Y- u! c# l- G& y+ ~3 l16
17
3 K, U9 C, M$ k3 J3 J" V' ^4 k18
19
* A( K" a0 |! P1 ?20
21
) l" [! G  g! ^22
- A7 v; Y9 j* g# m( Q3 B/ i& `0 o* T23
24
+ N7 r$ M8 T( f2 \' T25
26
- I( @* ]; X( y9 f& `27
28
$ @3 {1 _0 P! W& X* e9 m29
30
# i! {7 W0 h% w/ [31
4 u" E/ u% |% {! i32
33
34
35
36
37
38
0 ~  ~$ \2 l( r& C2 R5 @! V39
40
; @4 [4 F6 Q! W/ }) @41
! {; k* H- L6 R/ ^- B42
43
0 a9 g; T) D  Z7 R# \0 N$ i( }44
7 N5 T3 Y/ M2 g& d3 `% A45
# ?/ x4 c! \2 q5 r& D8 }: ^46
47
48
. i  I6 K6 [: Q  M, T6 r  @/ V49
* l  w! J* P9 Q50
) v  s7 V' A5 u9 o& ?' r8 r( P51
52
53
/ r  f5 U+ Q# X$ n54
# i, X8 F5 \( j7 M7 K( m* k$ }9 J55
& k) B4 m: A3 a7 g) R3 {+ [& C3 L* r56
* p3 `; i; w' S8 }* t# y6 j; u57
7 b9 A3 y6 g: z5 @. J+ X8 P归并排序
将长序列从中间分成两个子序列。
对这两个子序列依次继续执行重复分裂，直至不能再分。
' C/ B2 _' F' x( E* O% W递归返回两两排好序的子序列。
% z' N7 M! _- M4 F" u- N# L平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


7 p# D: x+ E+ P  I代码实现**
0 \4 D2 @$ X6 g' f4 d

public class Solution {
4 L' c. b  F/ k. w/ k' @( w        public static void main(String[] args) {
; ?  o1 K+ {! [5 @' `                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
3 @2 X8 F; L6 i+ c, D% C& f                int[] arr = MergeSort(array);
                System.out.println(Arrays.toString(arr));
        }
1 r9 F, \, w) F, z  M

        private static int[] MergeSort(int[] array) {
& @7 H; T6 _6 R  }9 v                if (array.length < 2)
                        return array;
2 T) ^1 z7 e1 G- V                int middle = array.length / 2;
2 W% v- ~- m( m                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
, Z2 P% j+ \0 w. X9 I7 {                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
# P; e8 n! M7 ^+ i, Y1 ^                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }


9 D+ ^. M8 V3 u; y        private static int[] merge(int[] leftArray, int[] rightArray) {
2 S# F. s& a/ T! `4 Q                int[] result = new int[leftArray.length + rightArray.length];
                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
                        if (i >= leftArray.length) {
8 l0 g  o8 N" i                                result[index] = rightArray[j++];
                        } else if (j >= rightArray.length) {
                                result[index] = leftArray[i++];
" t( E% ^6 S7 T4 T                        } else if (leftArray > rightArray[j]) {
$ p$ P0 {( M2 E3 _9 x                                result[index] = rightArray[j++];
" [  u. S' @4 B                        } else {
% d+ j, \9 m$ }1 y                                result[index] = leftArray[i++];
! m4 u$ I0 U- [% ?9 j9 L% Q; Y+ E                        }
                }
                return result;
+ ~  Y% L# j* p1 l0 Q  {# j        }
4 W/ D! X. O3 E9 E8 K* m}


, y& N1 Y, }3 o4 Y. S" {1
2
, b: w) X- o2 v8 K' g6 S' T3
% g. R4 M/ X$ W  R5 q. X4
5
6
7
  j. X) P& w' W8 T' A- h9 x6 a& L8
9
10
11
& ]( T! }  d: H* N7 z$ S5 V12
13
14
2 R" ^/ _7 Y( O1 P8 J15
16
7 F$ _5 @& Z9 s17
18
% |; n$ u3 Q) s* {! @) o" J% ?% J19
20
21
& t9 B; \! a! F9 C0 w6 Q) a22
23
24
25
8 ~9 `9 O) @) [& ~2 l# T/ {+ R26
/ b8 I# j  n3 s, U  B$ q( _27
$ i& x+ D# D7 g% [28
29
8 @# u$ R/ e4 }0 l30
31
5 e. s# t3 ~) Z, X32
  }: T6 t6 M5 O! \8 z& m& h33
/ q9 T/ n. @, X3 K5 t基数排序
! e; m& S, }3 e: j3 D5 C8 P找到数组中最大的数，确定最多一共有几位数。
" U, G; x  j# x! g$ \按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
6 q4 u, `6 x/ g, I& [将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
6 y4 @! d$ B& D6 v9 h$ F时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。

" A: g6 ^: r/ W, L: {; ^; `7 o
3 S6 d- s- P: _7 ^" G# ]0 [代码实现**


$ J- j* i) N2 s* mpublic class RadixSort {
, i5 n5 N6 z2 X4 {) p* Z

0 t' ]4 F9 }, V; ?. ^3 v: m        public static void main(String[] args) {
# z; J/ m' M) |* R; ^( g8 V                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
2 Y5 r, x( b, i' b) N3 g2 D                int[] arr = radixSort(array);
$ }- K& j) @' _( l                System.out.println(Arrays.toString(arr));
        }
5 S& e( G  u7 H/ \% `

        private static int[] radixSort(int[] array) {
2 b8 ~7 k& Q7 k9 D                if (array == null || array.length < 2) {
                        return array;
                }
                // 根据最大值找到最大位数
                int max = 0;
                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
3 c7 m  B: T( G( o/ U                }
  c3 y: @/ j. z: N               
                int maxDigit = 0;
                while (max != 0) {
                        max /= 10;
1 q0 @4 s& t) Y                        maxDigit++;
6 _) N, ]* d" _7 Y                }
               
7 V; h9 M, \4 L9 q0 ~                // 第一维: 0~9
& t+ ]6 A+ c0 E2 X" B8 \                int[][] radix = new int[10][array.length];
( x/ M+ ?  A* f5 W) o                // 该位为 i 的元素个数
                int[] count = new int[10];
               
/ n( V: o3 W0 a# H$ j& I                int m = 1;
                int n = 1;
               
/ u1 ~* X$ f4 G" G) z                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
                                int lsd = (array / n) % 10;
                                radix[lsd][count[lsd]] = array;
2 H' q, W: O; `8 e0 y0 I                                count[lsd]++;
                        }
+ f$ i4 q# ?: d) ~                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
) {8 W- ]3 Q' B6 J( K2 W" `                                        for (int j = 0; j < count; j++) {
5 F( V) |, v8 _                                                array[k++] = radix[j];
                                        }
% T( ~; V% ]. t! F                                }
# F1 M9 g3 N# s, n0 u* F& B                                count = 0;
                        }
                        n *= 10;
                        m++;
                }
                return array;
. I1 |3 p. H# H1 B        }
' R8 N/ j$ m( b5 |
) _7 N0 ^; |; G: L/ g
# V$ e  ~0 t" c$ \, ?1 n- x2 l. m}
1 X& r  N7 @; @1
2
1 b  t% F, ]3 {4 ]( H. @3 Q  X3
4
/ \! c7 U/ l7 i9 E5
6
- H0 \7 a1 r. y/ W7
8
9
10
8 O5 q" }& W% `( P) h5 O1 g4 i11
" P. U; q# l* k+ _* @' ^12
13
, }! S2 {. |- F+ H( k14
15
16
17
) F8 w2 o9 V, O% W$ N# S# N' b18
19
20
4 ~: f% G' T6 d, l' q7 R21
4 Q6 E9 D: U: @1 \, k0 G22
3 L  S1 r- V5 ]& e! h$ a23
24
25
0 m$ P) h9 n. e8 C26
0 a: g( ?; `2 F% }1 m4 x& O27
, ~! }3 Z# r3 _" Z8 Z! q$ w  @# V8 W28
/ u: Z. ^& @, c4 d29
30
! B/ X: t+ ]! v) H+ ~- ]% ]+ t2 L31
32
! G& Z* n6 a+ P5 I% C  U33
: x  l) x# c% g0 f! W0 Y34
35
/ j; V0 q5 w5 }/ w4 s36
37
38
$ n% @% g# S  G39
40
+ q0 x' A+ f1 y9 e3 f6 J41
42
43
- x: Q0 X3 O% a8 B2 R% }44
45
5 v" F% x6 e% R0 y  J! L6 W$ ]3 R46
47
48
- }8 }* R  U5 j* \$ ~7 p: y) s49
2 N! `; J5 S$ a50
+ _) n9 Q+ [  o7 C51
0 a8 P- x2 z7 U* e9 D- x; }52
% l! ?& |' Z9 L0 ^) I2 b: P53
; a- a" X2 O. w6 u计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
5 j. L; _) z. a9 [" F# C) [+ a5 a$ S统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
! f: I. Q- Z: O. b5 N  C9 u+ O: y时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
1 j3 x4 B5 J! A3 h+ d3 g6 c

2 ?! ?; }1 W& h3 `) T8 n代码实现


  ?4 _4 o$ r4 [. Hpublic class Solution {
# {, R/ ?( l$ Z2 w6 m: t! A2 U

        public static void main(String[] args) {
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
- i: V' O% A; l* A3 d+ ]                int[] arr = countSort(array);
) j* _& J0 R) q  G8 ^                System.out.println(Arrays.toString(arr));
# C9 d& N+ O8 E1 k# y& }        }


/ U2 y) J: P& _9 f9 X$ G  }$ L        private static int[] countSort(int[] array) {
. ]. M" e: O4 \+ C; V- |                if (array.length == 0)
* H  A" O8 w% J                        return array;
$ y0 X: b: m. O               
2 r6 ]% J" |  e. E                int min = array[0], max = array[0];
& T+ h  s6 v& p0 `               
8 w0 {0 ?! F: v3 f                for (int i = 0; i < array.length; i++) {
, p* {( P( |' }7 {8 {4 i& `                        if (min > array) {
; n1 o0 A, w! `7 C' p. w                                min = array;
0 M% \9 N- T5 k4 r0 u% ?* r                        }
                        if (max < array) {
7 s8 Y8 M/ C/ h3 D# ?: @) y                                max = array;
  b5 B6 V$ q0 i- @9 b# s0 t: E: O                        }
0 j, |, a- s& Y                }
+ L0 C, l$ k, ?% |* e' X8 q; j               
                int[] count = new int[max - min + 1];
7 v+ W1 O- I. R* W; P5 a& n               
                for (int i = 0; i < array.length; i++) {
3 w# L( x: ?1 X                        count[array - min]++;
                }
               
! j9 V, o7 p9 `! c3 @' t                int i = 0;
' B) \/ X6 z: d* r3 `: E. @7 `3 j                int index = 0;
                while (index < array.length) {
6 _/ x! h5 E" c( _! F% S3 [- f2 k8 f                        if (count != 0) {
                                array[index] = i + min;
& t% L6 U  ]0 D0 Y3 W# D                                count--;
                                index++;
                        } else {
: Y2 s2 v: d6 b5 y                                i++;
                        }
( z7 K' \" [  L0 x1 R  b                }
                return array;
        }
! H. N# o, j% U5 G2 ^% G$ S       
" M0 W7 J% J" ^2 q) j}
1
0 ?: \( F6 L/ `2
3
4
/ \0 H) |" ^# ~1 }5
* I. e% R3 j/ X) Z4 [6
7
8
9
$ Y& y* U* \* R, T: N, F  u) [10
11
12
13
1 ?* n  g& i" v6 H9 Y14
9 g7 J( ]! [# B8 ?$ a9 ~15
$ H' G$ G- J) ]3 d9 I16
17
( h3 _3 c! U% S" N) C6 t/ N  T& D18
, ~: c5 c% A: k3 H$ Q$ U7 E19
20
. X& ^2 n7 p' K4 {" R21
22
23
24
& s) _# Y+ Q2 o/ n3 y# V2 f) z25
' J2 w8 H) F& C; V26
# x4 a  ~- D2 P27
28
29
. r9 }1 Z7 [1 X30
4 |* T  y; d$ n8 }31
6 h% c' U3 x/ k3 E32
33
) C+ q# z" L) h9 s1 d5 H% v9 Q  E5 u34
" W  ?# f1 E" z0 t1 a- ?) ]* J35
5 |4 P5 O7 I- j! p1 r# O! b36
37
38
4 _0 X/ _) a) J. M: g39
40
" @! q# K! P6 L2 c5 F0 @. r4 p41
" _. P6 s$ ^6 t42
/ n6 I  [% ^* y6 n5 A$ R43
, j7 H! Z5 v- ^' e7 O& y44
& E: u$ S6 y. c  r! t) q: z桶排序
; S" x( v$ g4 s& r. U8 G5 K$ i————————————————
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
/ v: T) t8 X* |! v, n原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153


" p6 v* K: ?6 b& U7 ?