十大排序算法（Java实现）

杨利霞

  G$ o8 k* k& ?3 l十大排序算法（Java实现）

十大排序算法（Java实现）
3 e6 O6 a4 m+ |4 z5 A8 V" C排序算法框架
9 o. c: }, {" p8 G排序算法性质
插入排序
. n8 U6 `5 V) z% f/ D. G( v; d1 }& }直接插入排序
希尔排序
2 ^$ N/ o3 b  i2 Q4 X( D: S选择排序
简单选择排序
堆排序
交换排序
冒泡排序
* n: [1 `- @( ^1 ^2 x$ B快速排序
* `2 S( V& U. q  c8 Y归并排序
基数排序
) H' `) g: W$ P6 ^# R计数排序
  X1 j* c! [* J' p. U) g" f  M# [% X桶排序
更多文章点击 >> 这里

: g% N& u) O5 I" ?0 b1 c7 F
+ I) Q8 \& y( g9 {! ^; K4 A排序算法框架
: z( A3 W2 M0 }( T+ f; v

* @* `# R5 z: o  Z" _
7 x9 `$ J1 o0 a7 F7 R' A3 P! e) i
排序算法性质
  o( |+ O9 x5 g& \  L
/ m5 d+ X1 G7 y- ~+ c


插入排序
# ^3 _4 `! D1 b直接插入排序
5 `! O) i- |( t+ J( e+ m从第一个元素开始，认为该元素是已排序的。
取出下一元素，与前面已经排好序的部分进行比较。
1 S* h6 T. M$ A! E: Q; P: N若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
8 p7 Q0 Z9 X7 ~# a6 t* h遍历数组，直至结束。
0 V" ]3 a! r! U& q1 d最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
  n# G# \, M; P+ s( y' n2 f( b2
) 。
0 A! [. A+ N+ ?% _
4 Q* B$ S" t% o+ G7 l4 c
) V# H- M8 |. }: N4 I5 O: m0 C代码实现

' w( H; {# I( h
public class Solution {
" @. Q0 p  K4 C- g$ p' y        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
7 F, N% g) H0 M# R; p                insertSort(array);
1 r, Z$ u8 \2 o- u' ^& }  k7 w$ |                System.out.println(Arrays.toString(array));
        }
- C4 |; I4 ^7 F! K

        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
& I$ C/ w' ?! L* g  l" Q1 K" _) w                        int index = i;
                        while(index >= 0 && array[index] > data) {
                                array[index + 1] = array[index];
                                index--;
  ?- Q1 Q7 H/ s5 v1 z$ }                        }
) h* }7 Q# Y; U5 A& B6 B9 {                        array[index + 1] = data;
                }
) m& h' E* a0 K% a% O: q        }
. L: e, q- ^3 |0 I4 Y: e' m}
+ ^+ P# {/ @: _6 M! ?% r& z1
2
2 s& y0 @0 L/ ~' [' ^3
1 z3 f& z/ j2 U  }7 c: j0 N: y4
0 b" f- {4 @7 o" Y2 D5
6
+ U9 x- \# a& a7
3 i5 ], o  B; j2 z. Q0 P3 E7 W- D8
5 D9 Q/ L6 }) e0 g9
10
2 Y  L; u; o, e- O% X11
12
13
14
15
16
17
18
19
9 V. l2 q1 J& H. M$ ^0 {4 E) x% ^4 v# b7 ^希尔排序
4 X, V9 g2 v: Y) R

) T* t9 h& I# n. p7 c$ i* ~时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


, i+ Z+ S: J9 j) R, b# \代码实现

# {: N; f/ U* _" L& b2 s
8 w+ g7 Q: ~* z. M: fpublic class Solution {
$ p/ l; O4 e# K        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
3 J6 Y/ u# i$ c& C: S                shellSort(array);
0 w2 I: W. Y1 R* N                System.out.println(Arrays.toString(array));
6 i% H8 ^- m2 o1 y5 R  p        }


& V+ G4 s5 q8 E5 O9 S7 M6 h9 D  s        private static void shellSort(int[] array) {
. |! O$ [8 m4 l3 x                int gap = array.length / 2;
                while (gap > 0) {
2 i2 \7 P4 C9 n6 k0 t  e  S                        for (int i = gap; i < array.length; i++) {
% U! l# }% N+ S! ]1 I: |( R4 F                                int index = i - gap;
                                int temp = array;
  O$ R! a% \5 h: a) h5 f2 N2 h- o# _                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
+ G1 X- ~! ^" d2 a! f( h6 ?. ]                                        index -= gap;
3 S) e; f0 T% }5 K% x  B, @                                }
//                                array[index + gap] = temp;
                        }
0 w' M4 P! ^9 L                        gap /= 2;
                        System.out.println(Arrays.toString(array));
                }
        }

3 k- @: N8 O. b( A! s+ `# S3 \& P
  T$ l& _, |3 ?8 f$ L) i+ B        private static void swap(int[] array, int i, int index) {
                int temp = array;
                array = array[index];
" r1 j9 W, @9 Y+ N$ ^$ B6 F! T  l                array[index] = temp;
        }
4 p$ S! |# C7 G* d0 V0 X# _}
1
% F1 B5 R. h, r4 [' x. j2
- N6 [2 ~! }3 |  O; R3
4 R- W# F  C' e- U4
( Y4 |  _- X* d" o, y5
2 s+ q2 ?! ~: o8 D4 `6
& R1 O3 M7 x; q  ?4 W9 J7
$ w) b! K  H0 V* h9 y  P5 l- u8
9
- U5 j6 z" a4 M# ]8 h& Q- _0 O10
11
12
13
14
, |7 A4 J9 L3 P15
2 _+ Q! g/ m! Q1 t16
17
18
1 l& {1 b( }- \5 X19
20
2 A4 D! z) C$ {. c! t21
( I7 @, q  M. i" E5 O22
' D0 W1 W4 I8 S1 Y23
24
% W" Z4 }( P2 y" b0 |25
26
27
28
29
" M% g- S$ p) l# N0 q30
选择排序
简单选择排序
9 K, k: ]" o* {从未排序的初始数组中寻找最小元素放置首位。
; m8 f% F  C" E7 q3 X2 d从剩余元素中继续寻找最小元素，放到已排序序列的尾部
) Q% j2 [1 j7 z3 q6 n+ r6 q$ R遍历数组，直至结束。
时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。
' {  Y& D& z( c5 j
5 `, t2 y! N: G! K& b
1 A+ J$ A6 U4 O5 {2 g* h5 c2 I代码实现**
+ a: z3 q# C& f9 U! ]
4 N, I8 E1 i* b) r# ]" ]. t1 U
public class Solution {
# `/ _0 w) n9 j5 ~% G1 \6 M6 b        public static void main(String[] args) {
7 f8 Y! V8 u1 D8 k% {& m1 ]6 z                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
                System.out.println(Arrays.toString(array));
        }

) v% Y8 g' u* a# C$ [
        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
* J% `9 A0 g% z5 W/ m                        int index = i;
1 [0 L3 h9 w; Z9 s% A; g                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
                                        index = j;
/ @. d5 V% M4 F8 H! L5 W                                }
& v; X  H/ L7 m: A& K                        }
. W8 `- v- `2 \7 B( z                        swap(array, index, i);
5 t/ T+ K7 i. }                }
9 w- ?: P. O; [) [6 f0 \1 X        }

: b! A, P3 s! p% o* t4 H4 V
        private static void swap(int[] array, int index, int i) {
7 k/ |! a$ L7 o- D# X+ w                int temp = array[index];
                array[index] = array;
& z8 p/ H# l( v4 D* W+ U                array = temp;
) `% T+ D0 J8 \( ?# L        }
, W2 c+ f4 V) k0 d7 o( l1 R}
1
2
' J* C( l0 @3 e! E. t, |' S9 I+ M5 F3
4
9 H# w5 k, l) J, N, ?6 {& H2 F0 `5
: Q. S$ J% m! I1 i6
( `0 J* k1 F1 g+ ]7
4 v9 G! o! P2 I: O8
9
0 M+ I3 l. _/ Z3 f2 ?! u' s, ?10
  s% {+ d8 y, `, @& n- H. P; f11
% p- `/ ~3 d8 C/ U0 M12
6 Z" g: O3 l% t2 `$ t1 ]13
+ P/ d! L' U" A. s14
15
16
17
+ R9 Y7 t- L8 y3 j. O" F18
19
; a# q9 k/ f7 `/ N20
21
9 U8 r; Q" \7 V& a+ Y3 G- O22
  B  {( o& W2 p9 t2 C23
24
+ \( g& a1 }8 }6 b- b25
& {" ]* A1 m( L- _1 m堆排序
8 p7 s& Q* G8 B) ~时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现**

5 `; a' r3 _. Y, @
public class Solution {
        // 建堆
        public static void creatHeap(int[] arr, int n) {
6 ~  P7 U1 d/ z* f) Q                // 因为数组是从0开始的
& P' ?' b- m, Q$ A) D4 r                for (int i = (n - 1) / 2; i >= 0; i--) {
                        percolateDown(arr, i, n);
1 R/ O; t7 ?! C1 b/ _                }
        }
1 l. `$ U8 J6 U6 _) ?9 t! g        // 插入
        private static void insertHeap(int[] array, int data, int n) {
8 o2 a8 y. K2 d                array[n] = data;
                percolatrUp(array, n);
$ U! q) B( B1 ?/ V0 B& M, c8 y        }
        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
7 E9 f$ \6 W9 a/ P' {5 _                arr[0] = arr[n];
                arr[n] = -1;
$ d+ G' e9 k& ~' c! p                percolateDown(arr, 0, n - 1);
        }
. n* f9 U0 Z2 }0 O8 f7 F2 \        // 上浮
        private static void percolatrUp(int[] array, int n) {
0 l* R% F: S# a  Q- n: ~                int data = array[n];
                int father = (n - 1) / 2;
* D% N% F3 J; d8 ?, D                while (data < array[father] && father >= 0) {
1 L' ^2 [. l) z& E: t0 U/ O! M0 \                        array[n] = array[father];
                        array[father] = data;
                        n = father;
                        father = (n - 1) / 2;
                }
                array[father] = data;
6 ]! `; M# ~8 }2 }; `( F! g5 V        }
' I* J4 g7 H+ A6 F; w) H        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
) E- V/ Z$ v9 R) F                int father = arr;
                int child = 2 * i + 1;
                // 遍历整个该根结点的子树
& |( ~- t8 N. z1 r7 }& p- R/ i                while (child <= n) {
/ F6 V" b: P1 b) k; E! J& F                        // 定位左右结点小的那一个
- P( y/ B( a$ ]' T  l6 n                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
                                child += 1;
                        }
                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
! b1 {0 J+ g7 u                                break;
% Z* R! E- {; e) ^2 z9 Q                        }
' p  P$ q. T; q) Z& U3 j9 x( @                        // 互换根结点和子结点
                        arr = arr[child];
: t' g! Y: }4 ]( p                        arr[child] = father;
" |, g: U- ^9 M: D' q7 f                        // 重新定位根结点和子结点
                        i = child;
                        child = i * 2 + 1;
                }
7 ~3 h+ r: E# {, o6 {2 [        }
   
        public static void main(String[] args) {
: t7 C2 t, U0 m/ t' ]                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
# T" v$ d) K$ n+ O8 L               
                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
1 H9 A$ b5 d! r. t+ Q+ p1 s/ j7 P0 J               
- o* T; S6 F( p! X* o4 _: [6 S! U                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
  }% U$ Q# A) L- O; g$ b* W. u/ }               
6 g, ]9 g6 K. C( b: b                deleteHeap(array, array.length - 2);
                System.out.println(Arrays.toString(array));
; _( F6 o9 a- n1 A               
- }5 d  x3 ^0 F- u- \( l2 \" A, h                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
        }
. R  s# t" n: E, j/ D}
1 i& I3 ]( M# b  d* X' J* g; g1
2
3
4
/ ]9 o8 O" F; Z' p. u5
& e: A9 n8 v4 v9 W# e( f5 E5 Z6
7
/ ~! r) |2 h% s: `" b# [, W8
. E* d. V* {7 l5 s# @  r! }' @4 j9
10
, i! s8 W% s) ?1 Q9 `/ R- z11
2 b+ N: d0 ~" C4 M2 z7 x$ N* t12
" o. W0 X( v5 m5 _# a$ V2 X$ v13
3 \; ?( q" p0 [/ m1 k4 N# ~' R2 N14
15
) v) Z$ |) L- [) b7 O  \16
17
. X7 C2 c- i5 c: K! v( j2 X* b/ q18
$ p+ H7 q: [1 ~% L2 w8 _19
! s: Q. t' n; z( A5 |8 _20
21
22
0 x8 v9 I9 V4 ~( b5 }23
24
25
26
27
28
29
6 @  b1 n. V1 d/ v. t- P/ _4 p5 r30
8 m, {: i0 _) X% b31
32
33
- e0 \6 z5 @5 V& B34
  g  Q$ ^' z& c; L* ^35
9 _& z  E. p. ]3 n. _0 U0 q36
5 @  y$ {: U6 D5 q) n& ]$ x2 s37
7 w3 Q9 O8 ^# W. j5 R38
4 M+ ^, M6 y' `6 p# w  H39
- N% }, I! N# N& N, t5 F) w40
8 o8 p; D, ]7 h7 U41
) u. g# n  W$ [/ u42
$ m% n- ?+ @8 G" @# t( L) h6 t6 r43
& L; P2 b4 U! ]7 Q1 o$ X- ?44
45
/ q* h" g8 F4 O) I4 f1 p) C46
47
48
49
50
51
  K7 U, Z& M6 h" o/ h4 T" v% O/ S52
& L% F( j. E& i$ K53
& y5 W6 t5 c7 b' G6 a4 i1 o$ F54
55
* b& f* r% P% M/ b, G' [  T: N56
57
58
59
# X: `" s5 E, W. k60
  _2 a; U$ n0 [0 m, T4 ?* q61
62
' s8 b4 F& s- o63
64
65
66
, m( @$ a0 n* B9 B# N67
$ P8 `1 ~  R( |6 a% m68
6 n9 P/ z2 E+ _, {& ?! B69
70
6 Y3 T, B% Q8 _$ ~+ z  |% ^交换排序
冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
, L9 n6 k" N$ D' l; H1 `3 w7 \( K! j在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
7 U& d" y/ ^# {2 K- q+ a2
) 。
, P+ a: [5 o. _4 l
9 w1 c6 A8 G6 Z8 b1 x+ u
代码实现


. o( n" o/ E4 Z9 @7 bimport java.util.Arrays;
public class Solution {
       
        private static void bubbleSort(int[] nums) {
( B! F- H, M1 {! w+ l8 l                // 循环次数
                for (int i = 0; i < nums.length - 1; i++) {
/ t2 ^9 C& ]! r                        // 比较次数
) G6 I3 O* c8 D8 r2 v/ }                        for (int j = 0; j < nums.length - 1 - i; j++) {
# Y% Y" Y( N4 @4 v; r+ q! F                                if (nums[j] > nums[j + 1]) {
4 M; l0 W' y  h. \$ s! F' K( j: X8 |                                        swap(nums, j, j + 1);
8 w: B9 d1 b2 A) r# C                                }
                        }
; W/ u4 F+ w" r! \* W0 A                }
; B  \) [% L9 m0 t: x5 n3 M        }

* ?0 f, f- {0 @8 {
        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
                nums[j] = nums;
; T; z1 i: F/ x1 P; b                nums= temp;
        }

5 b! H, T  K! ]0 z1 z+ g* u
0 R, v6 R# P# ^        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
        }
+ N6 f+ \0 ~6 E}
/ l4 ~/ y4 A- T; k# N6 G/ B1
$ r/ N) [( {" C7 t) D4 J2
2 X) ^7 `$ H- M& V9 P+ B4 d3
/ p! b# A& G5 G3 k2 M4
5
6
, F' R; Y9 p, ]0 ~8 g& R7
  W) G8 i9 g8 M$ M% |! L8
* A0 t1 e+ ^) F( E" z  w9
10
11
" ]# n; [, d) q. ~12
13
14
15
16
17
! x* V. W: S8 t4 A18
7 U3 @. k* W7 @19
4 L7 |/ M+ z4 E7 c4 b- I) N# w, e& Y20
& P. r# |, Q4 J9 A2 F8 F* j21
22
23
1 b$ U- ^7 n% i5 M8 ~; t" g! U24
25
5 ~$ g4 z- ^! H8 o/ J6 _8 O26
27
快速排序
7 W6 s4 }2 ~( Z3 j) l% Z! c时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


7 J1 L, S( P: p0 G代码实现
7 ~$ P8 g7 v- g

  Y0 P0 _6 B4 Ipublic class Solution {
       
! n- ~' F) v3 M. n' S% m" A        // Median-of-Three Partitioning
        public static int selectPivot(int[] array, int left, int right) {
) G# o0 g7 \! I1 t4 W                int middle = (left + right) / 2;
               
                if (array[middle] > array[right])
6 P0 a9 _2 U( C. @) S                        swap(array, middle, left);
                if (array[left] > array[right])
; q5 {  i$ [' V7 w/ I# V                        swap(array, left, right);
) }: o/ G3 i* f& J                if (array[middle] > array[left])
4 Z6 a% g; e' e- Z5 _0 n7 ]3 S                        swap(array, left, middle);
               
                return array[left];
1 ?2 K4 n' b; {: t$ \2 R        }
6 ^( @0 i$ O' Y5 w7 M% ~       
        public static void sort(int[] array, int left, int right) {
0 |6 F9 i3 {8 s5 k7 N4 K$ f                if (left >= right)
, N$ i: X& E- B6 s9 t- S                        return;
                int index = partition(array, left, right);
                sort(array, left, index - 1);
                sort(array, index + 1, right);
( Q1 e( Q% i# [2 Q; k3 O- f* M    }
8 l- H- Z6 G. b3 M       
        public static int partition(int[] array, int left, int right){
        int pivot = selectPivot(array, left, right);
; W* d7 \( Z2 T; p4 b) b% S        while(left < right){
            while(left < right && array[right] >= pivot){
                right--;
            }
: H/ |' Z4 \% U; |2 u            if (left < right) {
/ E: J" {, d+ c+ t# g" [$ @                array[left++] = array[right];
            }
            while(left < right && array[left] < pivot){
                left++;
            }
            if (left < right) {
                array[right--] = array[left];
, u) F8 M* L/ h4 Z# v' y, b            }
        }
3 w3 u4 s# o8 f; T( t. r            array[right] = pivot;
        return right;
    }

' G* i2 f3 p  ?
    public static void swap(int[] array, int left, int right){
            int value = array[left];
            array[left] = array[right];
" q- P" e+ @( I/ W- X            array[right] = value;
# s# N/ i9 x% j9 e    }

* x8 k/ F! W9 k; c
        public static void main(String[] args) {
, \& h4 o2 m' b9 m                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
- S/ [( N  {1 W# @7 I$ M4 d* S                // System.out.println(Arrays.toString(array));
$ Q8 J; Y0 j4 J6 z. c" R                sort(array, 0, array.length - 1);
5 L0 L# S4 m' _& T! Z                System.out.println(Arrays.toString(array));
        }
; }- D  [* D( j& U}
1
2
3
' [. F) V, ]3 X6 b" h4
/ q3 W+ {- T# h5 K# V9 h' K2 p+ I! e* H5
6
" p  \- E1 u$ E. U$ @$ r7
) v# a( }; ?1 ?9 o# k: b" S8
9
1 `4 q& C! c" k# v10
2 S" D6 [$ M, F$ }) X11
: ]" K" Q! C, ?* ~# X12
13
# Y) N6 W- t5 b8 s1 f/ e14
15
0 Q4 X( j2 r' o5 P# J7 O16
17
18
8 H; E0 Q' M2 \) Z19
* c8 w4 Z* v1 ~) l$ u/ v3 e20
21
- s, `& V) l- u! f' {8 m' _: z22
8 B  j6 L! V7 m* ^1 o; n23
3 I6 y) K& ?( X8 K& H24
25
26
27
28
29
30
, k& f; Y5 [; l+ O% D31
+ n2 E, s) x, P+ |5 [9 t; z32
33
7 {/ S" h1 }) C2 W: h6 s34
35
/ Z' H: q  @( p" D36
6 z* @2 C1 D. W/ a37
: v) R! j0 v" p, ?' i6 A6 ^2 E38
5 C8 ?2 d) ]: I1 E* B& j1 \. P0 |* O3 s39
  y- v% `6 c+ c40
41
42
( X- s. Y( `2 C5 G% B! ?" @/ i43
44
45
46
47
4 R" w( g1 _1 X. k$ J3 ~3 V48
% i% [6 x; h0 ~: d% m. L) Z* X4 h* g49
; |4 r# B  w4 Y2 t$ f50
$ S5 b2 d$ C5 r4 [1 k8 z7 B9 p7 w51
52
0 P) c) t) g3 i6 J( e" E5 E53
1 q6 M  n7 G3 A0 {- y% Q0 V54
3 G- d5 i8 N0 A9 n55
56
57
7 L2 L& v8 p2 K; d1 _0 r0 E归并排序
将长序列从中间分成两个子序列。
2 E9 r9 Q/ `3 f/ X. [4 n对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
/ g2 V0 h3 S9 ~1 V1 L9 l& j, T) S平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
% ]$ e# P2 m7 J' o1 ?3 ~0 n1 w

& u7 H; V, z% g; R3 t8 }代码实现**
$ ^& _# h, l6 d4 m8 V

  k& g# b( a: {public class Solution {
" }3 L- _: G8 R) B        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));
( k! ?! ]% r% y        }

+ h; L4 O2 K. V5 ^* g
        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
                        return array;
                int middle = array.length / 2;
                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
' V% J9 ^. n$ f1 V; ~; A9 V                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
) Y  r" S' Y& {                return merge(MergeSort(leftArray), MergeSort(rightArray));
1 X: t$ M2 C4 ^: E" y6 ^        }

/ g: F1 p" R' j3 Z
# Y0 H3 N$ Q1 b" ~; ]+ ?) R. I2 h        private static int[] merge(int[] leftArray, int[] rightArray) {
* K8 v/ y* U6 s4 l3 d% d                int[] result = new int[leftArray.length + rightArray.length];
; N8 s' V: m- j0 K1 O$ F5 D* O# s6 t                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
; h% k) G7 k- E+ M3 `                        if (i >= leftArray.length) {
                                result[index] = rightArray[j++];
                        } else if (j >= rightArray.length) {
                                result[index] = leftArray[i++];
, m4 y9 D3 i; {+ c$ a% k1 q                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
                        } else {
0 J& e, f) u3 k( z& K                                result[index] = leftArray[i++];
9 d0 @2 l' z% U$ U# ^, r) l                        }
- K4 X. ?0 ]" v1 M4 B                }
                return result;
! X: d  h* |0 b- L/ J" [4 G) F        }
% a4 m$ |0 Q/ }! u! I" z}
# t5 t5 H" K( B

1
" K; L& _$ h' Z8 g, O( O; A  u2
' v+ Q8 c! h) l  l2 M! c8 m3
7 e1 S7 r7 }& h4
5
" e4 C# \0 s+ }6
* f% k" P( k2 e) ^% q3 I( D, R7
8
" e& T4 D( v% i3 n. R9 \) U& |. P9
% D, t% R( }5 m6 y7 R! Q10
( t5 g* f* F5 L# y: N8 `11
12
9 I  L/ j0 i$ U13
14
0 f$ [7 {9 C- Y& d' ^2 u15
16
17
) ?& w, W* o! C  E18
19
20
7 s0 M3 T8 L0 _- q% q21
22
6 l1 [7 X# p3 ^2 b2 O) d, ]8 n23
24
' t& u+ m4 O5 @) M  O& |% X& ^) k1 X25
26
: d5 Y) l; g; {  v- d$ s27
28
29
30
% r; Z: X/ K# M" |2 c7 @$ ?/ F31
+ f9 w! u# J4 ~7 Q32
: i1 i1 x4 ~  l! A! s" I33
3 P8 K8 p# |* S* H3 E: m* o基数排序
找到数组中最大的数，确定最多一共有几位数。
; H( ^( c. B$ ^6 h: O按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
0 S- r  o$ L, t4 m) g$ Q将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
: Q9 c9 A: ?) a; o3 [2 D时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。


代码实现**


7 Q2 O3 k8 _  C0 y' _! b6 hpublic class RadixSort {


) G; Q; o4 ^( b9 _! ~; q8 d        public static void main(String[] args) {
! H/ ^! N- K9 F7 Q& A- g                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
                int[] arr = radixSort(array);
; P7 r  q9 q* p( R4 F                System.out.println(Arrays.toString(arr));
        }


        private static int[] radixSort(int[] array) {
5 l, x! ?! }% x& U3 a$ R                if (array == null || array.length < 2) {
                        return array;
                }
. m: x  ^9 e5 }" s/ g                // 根据最大值找到最大位数
                int max = 0;
+ x( J' s3 ]) c! U1 N5 I! k! ~                for (int i = 0; i < array.length; i++) {
/ K  _# z# u5 z$ L                        max = Math.max(max, array);
                }
( r! D3 O- q% {3 o6 y" u7 {               
+ i$ |) Z9 N+ l( Y0 d. y4 Y! I                int maxDigit = 0;
- H  |! ?, }8 y9 q                while (max != 0) {
                        max /= 10;
                        maxDigit++;
! ]2 b0 _6 R* v0 {# M/ c                }
8 G+ m0 a/ E6 N               
. Z% j$ R5 P  ~0 A2 g  |% ]) o" s* y                // 第一维: 0~9
2 T/ d$ [' G0 E$ ]* u9 k& p$ V# W8 i                int[][] radix = new int[10][array.length];
                // 该位为 i 的元素个数
                int[] count = new int[10];
               
6 @& ~/ }0 \% m3 ~9 ~                int m = 1;
! D' K( o3 Y" }- a                int n = 1;
2 Z5 ^: }  [( D& S3 r/ p. [               
4 k. T- b) x5 \: L& }( a  f                while (m <= maxDigit) {
1 ~6 }! a- |! D* c6 Z3 f                        for (int i = 0; i < array.length; i++) {
                                int lsd = (array / n) % 10;
  b* ?/ R& ?7 W                                radix[lsd][count[lsd]] = array;
0 k( q7 c3 f7 I, U$ K                                count[lsd]++;
                        }
# A, L3 l6 F  `& |* x) ~                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
  ?, y9 d) h. {8 |' M# o  Z0 B                                                array[k++] = radix[j];
                                        }
9 A. A, a# k2 C4 m; R                                }
                                count = 0;
                        }
5 j1 d7 M& K. D3 P1 J                        n *= 10;
                        m++;
9 ]% s% j/ `9 W( z2 k9 V                }
1 [, Y( [; V: T! E                return array;
        }
) u0 {6 w0 O* |" q' d/ _

}
- X; N' {) l# o) ?$ b8 o' J# {7 l1
7 o: ]  a3 t) l5 s2
4 `) i" I* `4 p1 h5 g; J0 n9 Z5 H& I3
. B7 l* \; f6 V( z4
6 H9 ^- R7 y! D- ?# L5
6
  P. D9 R  R: J' o/ U0 R9 _0 l7
8
% ^5 J) |9 k5 g; D2 ^9
1 j+ K) h4 J) {& `10
11
12
13
14
15
16
17
5 K# i/ [0 _- I18
19
20
21
- w0 P! N1 p% ]) n8 l* v22
4 }& T# s5 L' ~6 s, T. k23
24
25
) i1 `7 U2 X" U! s3 ]& a7 [$ `26
27
" h" ]: Z# `( J$ k" \2 v9 u6 O28
29
30
# x( {! J3 g+ z( |31
32
33
" a) |! s# F) Q3 |- e34
6 R3 ?" u2 y0 I0 ^5 |: j5 C4 @35
36
  J4 H6 }' K! Y2 h4 v, A8 j" b. _37
3 ?; {5 ^& s9 }& I# o+ G38
39
40
41
42
43
1 p+ P7 ]5 y, @& ]$ S' D44
45
7 A, F# ]; v2 P6 N$ |; I+ y46
47
  h3 {- a) v. Z1 y, e" x48
49
50
- U+ B& C8 c0 |- [. z51
52
& G' @) }* w: G# L53
计数排序
- z9 d) I2 m, H) P' l找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
& r5 o5 N. M" ?# H. I! V8 u统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
. k' E; y! L/ n最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
& Y! n" g1 y4 H' i时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
: ]$ K/ y6 N' L5 }1 B' s3 l; R
6 }: Z  Z( r# Q0 m/ d  }
, `5 F- k  i" Z5 p" \/ ~9 I" b2 i, q代码实现

; V" `8 A  k. g2 A6 I
public class Solution {
( g3 u! T- H6 O
3 A3 P' b. _0 S. m
$ ^( Y; H' U0 f3 L# _& v: Q# F/ r        public static void main(String[] args) {
, F& {& ?9 x7 S3 T6 ^6 @6 y                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
4 a, S! d7 s( E; T+ _                int[] arr = countSort(array);
! T# A, C: `+ Y8 j* X                System.out.println(Arrays.toString(arr));
" z' u: R; H+ q+ Y1 S# m- V        }


1 A* q) s3 i+ V6 s        private static int[] countSort(int[] array) {
                if (array.length == 0)
. l5 \) S5 K2 Q: {8 r! t) N                        return array;
4 N! |& W# }/ ~5 Z* I/ L               
3 K6 r* _" A/ a; d- f                int min = array[0], max = array[0];
. [/ g: p6 |9 J% y; Z               
                for (int i = 0; i < array.length; i++) {
                        if (min > array) {
" B2 \: y# o. Z) _! U  X                                min = array;
                        }
                        if (max < array) {
% O( e/ c2 \+ u: Y( L0 V                                max = array;
                        }
4 r+ G: G# e0 n5 g% N% O9 O                }
               
                int[] count = new int[max - min + 1];
5 Z, D) S$ W$ b! l) G- ^5 s$ m               
; l, d4 Y: `/ l( p) D                for (int i = 0; i < array.length; i++) {
! m9 Q" p# p; M                        count[array - min]++;
& r* h0 i% X9 T( Z% x                }
               
0 i2 t( G, A$ Y  E1 m3 {, A5 y                int i = 0;
: o" S5 U0 O2 r9 M" w5 H7 U                int index = 0;
                while (index < array.length) {
+ o. e! Q) U; d/ L0 n& |                        if (count != 0) {
$ M2 n% [6 G6 B2 i                                array[index] = i + min;
                                count--;
2 v0 V7 w  N$ }+ c$ M* b  X2 C0 d: w                                index++;
+ I& I# m+ u6 w5 K# Z                        } else {
3 ]% k! M. I" l0 B2 p4 p                                i++;
                        }
8 F7 w1 P7 C* T$ [                }
                return array;
        }
- ~* X* y# k3 b* F8 i       
' W$ P$ ~, n8 e) a7 Q! l! g}
1
2
3
1 S) {% j9 h( i* E6 i4
/ k1 m* N, c1 {3 m2 L5
3 p$ k, h4 @7 j' A# c6 C, p6
  n- ?- @- p' w7
8
9
% ~/ T* a0 q$ d1 k! P" ?10
11
" C' B# `# s* }: F12
13
14
15
16
5 j/ ^+ F. U  Q9 b+ `9 e1 V17
18
/ Y+ \. r& Q' l+ z3 E/ s. X* e19
20
  \8 _9 p6 {, z1 Y& |1 s21
22
) T! E$ V* S4 @23
6 j( m4 |) u/ N8 u  v0 C, ^24
25
' J& Q1 `  i% V) F- N1 m/ x6 U26
27
28
. {8 n3 P3 ^  e29
30
" {' K6 o) j3 a. V31
32
33
34
35
- i& c% ~! V2 _5 X( R36
; S* [/ M  h, A  F6 [8 F8 H" L37
38
39
40
/ w1 X; T$ n0 |2 Z9 a" b41
- \4 z, x- H) B7 g7 q42
! E, w" S: Z) w0 e) J2 _43
44
桶排序
7 O# q! R/ t; t4 h" k0 L————————————————
6 S6 E. q  {4 j2 B5 Y4 ^* o$ c版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
1 ?  n* W9 I  U/ b