十大排序算法（Java实现）

杨利霞

& @# k+ _  k7 H; ^+ o1 W十大排序算法（Java实现）
  A2 I4 W9 N6 \, @  R$ r. ]
- F8 e: n; w; Y4 O- n十大排序算法（Java实现）
" t" k' z  k! O, q3 `: H0 ^排序算法框架
: v. h& d6 E8 p2 ]排序算法性质
2 L8 s0 |  {& n& u# s6 `插入排序
直接插入排序
希尔排序
1 w0 v% u. {6 n+ C8 q3 V选择排序
简单选择排序
7 y& q% J) t  \/ H堆排序
2 B6 Y' z7 H0 z. p' z& x* T8 E交换排序
冒泡排序
) n( S! N8 z8 N快速排序
归并排序
8 ~1 ~* N; {, d3 W- i基数排序
计数排序
桶排序
更多文章点击 >> 这里


  X8 g( Q1 t! B. R排序算法框架
7 Q' ]' G, l0 r' Q) N
6 R: m' g6 K1 e. ]8 H  f! C  m


排序算法性质
6 w! b- X; ]: f6 M% P. @9 c


$ E- [( P5 k- M
# ]3 @7 x& |* R- V" W7 {& Z/ q插入排序
直接插入排序
# k% o3 w  f$ S7 c: `! q2 [8 z从第一个元素开始，认为该元素是已排序的。
/ A3 @+ C1 |  K) a: H# f7 |取出下一元素，与前面已经排好序的部分进行比较。
. I6 N9 K- v! y+ ^$ A. b& {若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
% B# ~3 U* r! ^遍历数组，直至结束。
+ D# s1 d, a" `7 N$ l. n8 o最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2
) 。
; B; m% r. W; b

& H- P* i# k% a% }代码实现


7 ]0 }- U  I2 w; epublic class Solution {
        public static void main(String[] args) {
8 U5 G$ j0 V( D' H6 G                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                insertSort(array);
$ o' e+ H7 J# [& j- ^' l+ Q                System.out.println(Arrays.toString(array));
        }
/ O5 q' b, T9 B$ O# a5 a1 b8 v
/ J/ I, Q' i, c
1 l' h2 W5 l8 h7 i. q( `& [        private static void insertSort(int[] array) {
+ G  ^6 V8 `3 {                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
                        int index = i;
                        while(index >= 0 && array[index] > data) {
# j) o1 h( M, V$ ~7 p% c% E( N                                array[index + 1] = array[index];
$ z- x" j/ x5 F/ e8 b                                index--;
% r! c* f4 o: l+ S: _9 g' G, |                        }
                        array[index + 1] = data;
                }
        }
}
1
; y) P" y' D3 H* B* l, H  |$ t* |2
3
4
6 R3 Z* m. g, x9 K: k5
4 \* z3 ]1 z, u6
2 ~& f* h9 \, b7
% X3 r  q. \: y$ J) s3 r/ m- |8
9
2 X% P4 A4 ?0 M+ w- M9 X) v10
$ e: K+ P6 f+ ?1 g$ y- b11
12
13
14
1 X; Z% Y  s& [2 t15
16
5 E6 o+ P5 ?$ _( Z! S5 u0 p17
% ?2 y7 U& G% @: @# N3 j- k18
19
希尔排序

) Z' `& p. O3 X6 J6 v6 r: ?" y4 p
! k/ [: ^+ X' a3 a5 B) n) W( Y: T时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
; m/ h5 d( H; V; e, t' ~- ?

( C. b1 q2 p3 e3 H代码实现

/ z( f4 a+ J3 @( X; m# E
  [, G3 L/ [, F) o2 Y- Spublic class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
; F; k: a- b& b                shellSort(array);
* q( M3 a6 G+ H" Q# a, R2 f                System.out.println(Arrays.toString(array));
! y$ N8 s  B  M- y0 c: R+ U        }
- t" D# h7 r" W) f4 y% z7 U

        private static void shellSort(int[] array) {
4 Z. n! I- [9 ^                int gap = array.length / 2;
  h9 F/ P' p# X* E$ B1 b8 l                while (gap > 0) {
% U0 B8 `% L+ ]/ t) U  T                        for (int i = gap; i < array.length; i++) {
# t+ f# J- r' ?# b) H7 F                                int index = i - gap;
% G0 D+ i4 b$ z3 _" L                                int temp = array;
                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
7 q5 E9 M# Z* E( }: G                                        index -= gap;
                                }
0 y7 B, t6 e6 R, a//                                array[index + gap] = temp;
                        }
( _# N1 p0 V% w% \                        gap /= 2;
4 ?* m7 `2 L) P" v; o! J% V2 C4 K3 ^( Q                        System.out.println(Arrays.toString(array));
- R2 p- u/ o; D9 i5 V: m                }
( E- X3 C9 K+ E; K        }
4 x) b$ D4 h( ^, l7 B
  |2 p- Q( R# Q: S
        private static void swap(int[] array, int i, int index) {
                int temp = array;
+ e$ W  r" M8 Y  D                array = array[index];
                array[index] = temp;
* w9 H$ a# u0 `$ c# A        }
5 T/ E0 @) t- @  v  B+ b2 ?}
- g+ H; z( h( @+ }  D1
2
3
& j8 G1 t! Q5 c; W  n; f" M4
$ a: }' l9 B1 x# W4 c+ _5
$ f' @8 Q5 B" D5 t6
7
8
9
10
11
3 M4 r$ _& r  d* j5 Z2 E8 W% ]) N12
13
  `( B& T( i: A8 M: v/ {. \! Y14
15
16
8 Z& ]  c0 h3 y( |/ q17
# [( k1 O1 [/ E# [% d6 q18
  c. h( r0 ^1 o7 i- R& }: O+ ?19
20
21
8 B: S% H' X  M0 }22
3 i5 R1 G6 E% q- n, L23
3 T  F" \' U3 ~7 o- K& [$ ^24
25
26
( a$ m9 v1 T! Q2 w( C27
28
% W  n+ \5 ]7 f, ^9 H$ g$ l) W29
0 W5 _  T# g0 n# b( J! {# y3 x30
; t4 y3 B: T; c. r. N7 K7 F选择排序
9 P8 l! j/ r: N简单选择排序
. ?9 e5 A- r3 z) V  h从未排序的初始数组中寻找最小元素放置首位。
从剩余元素中继续寻找最小元素，放到已排序序列的尾部
3 ^+ g; r$ M9 e0 S+ @+ r+ e3 Z遍历数组，直至结束。
& u; S7 r4 d, [6 r* c$ ~时间复杂度为 O ( n 2 ) O(n^2)O(n
. K) o, U( R  A- A6 O/ W0 ]2
% ^. p7 G0 r5 P+ _' } ) 。

+ _8 a$ A* F. c" ]
5 k8 g+ B+ P- A8 p  t( v  M代码实现**


public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
- U/ G4 M8 f  V) w                System.out.println(Arrays.toString(array));
        }
5 T" h, E# S/ S6 E: C
0 I( ~; h6 Y% |' H/ S6 v7 e/ R; b1 x
        private static void selectionSort(int[] array) {
: [2 Q1 {2 ^5 ^1 b6 K                for (int i = 0; i < array.length; i++) {
                        int index = i;
1 i/ s( T! R. Z% \8 B& q. W8 [3 j                        for (int j = i; j < array.length; j++) {
/ B- ~5 m2 @$ j6 n                                if (array[j] < array[index]) {
8 N+ g1 u5 `" ?" X                                        index = j;
                                }
* J1 v- {8 Y9 o9 A+ P$ e                        }
                        swap(array, index, i);
1 A' {: I! U& U- }$ i                }
  t6 f; ]. w6 Z4 @5 n+ g' E" l        }


        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
                array[index] = array;
                array = temp;
' B* X& l( |( ~        }
0 ~! ?. A6 n5 f# A  i& ^}
1
2
3
4
5
6
" S, t* S8 @) r8 m* e% @( b7
+ N1 n1 ]1 d/ I7 O: Z1 V$ c% i! d8
9
10
11
12
  ]! G8 y4 d$ P1 m( o; R13
3 |5 u8 V2 n; R5 v14
15
16
3 \) l3 M2 `  R- C17
18
19
20
+ K8 p6 }2 e2 o% V21
22
23
5 l7 L1 j2 U6 q24
/ M6 ^5 N5 v3 U) o% O4 D, C25
" ~; l' _' k7 C9 |7 x/ l堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
" @  w* P7 z: b4 R, F" G, m2 I8 m
) ]& f& f% X& ^+ V8 l! x# S
9 u' b4 ?2 J, w/ W2 `9 Y/ I: a. x代码实现**
" s4 P9 ?& [. B5 z/ X

* I5 s3 J  o7 w; b- ^: C$ _public class Solution {
; }+ h+ C; I, x        // 建堆
8 F0 U& V  e% K4 e        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
) Z& {) d! c, l* t, x; D                for (int i = (n - 1) / 2; i >= 0; i--) {
0 W, `# A7 F; R/ S3 j, u$ C1 A                        percolateDown(arr, i, n);
* S' U/ [& s2 ]( F! W- c                }
        }
; p: W6 x$ k% ^: q: A$ D        // 插入
        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
                percolatrUp(array, n);
, j( w/ j8 c2 _8 r' ]        }
1 W9 r) k" f" ^        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
. s$ C; ~- D+ h                arr[0] = arr[n];
                arr[n] = -1;
5 N" g& V; N/ O6 ?                percolateDown(arr, 0, n - 1);
        }
        // 上浮
        private static void percolatrUp(int[] array, int n) {
2 }4 t: N+ e# g! L6 Z                int data = array[n];
! k1 r2 t; [) S' _$ C                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
2 w4 V& o/ G: Q! c                        array[n] = array[father];
: _) T+ B% M8 t2 v  K                        array[father] = data;
                        n = father;
- c# z6 @' v" Y2 Z1 m" w                        father = (n - 1) / 2;
- J: z  V% j. F9 V' L                }
                array[father] = data;
: r. t& A% ]* j( W3 S        }
        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
1 f- f) |1 \& g" ]1 o- F& f" }                int child = 2 * i + 1;
                // 遍历整个该根结点的子树
                while (child <= n) {
                        // 定位左右结点小的那一个
                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
# x  J5 L1 N6 ?3 u: z. B# j& n% K                                child += 1;
$ M: @7 R$ E: B                        }
" ~0 F) y) A" M4 U( W                        // 若根结点比子结点小，说明已经是个小堆
' n1 y  K$ y8 Y                        if (father < arr[child]) {
                                break;
8 j0 w* e) B7 q2 L6 O( r                        }
0 Q8 F' R' }; U# f. X9 T& X                        // 互换根结点和子结点
                        arr = arr[child];
                        arr[child] = father;
                        // 重新定位根结点和子结点
                        i = child;
, w! C6 `0 Z7 {! F1 x2 B8 Z; X                        child = i * 2 + 1;
; M) r) f, l0 W+ O; Q                }
7 r/ P! o0 M; D- T6 A% ]- V        }
- a" A6 X$ E6 r8 l   
  A4 I1 X! X: r        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
% g2 n; m( X+ w               
                creatHeap(array, array.length - 1);
$ r  b; A" `9 z" g9 j                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
2 ]: M& y  f* c2 c                deleteHeap(array, array.length - 2);
                System.out.println(Arrays.toString(array));
4 f7 F7 ]3 d( T9 v- R) u/ y               
                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
+ r# g) l6 a1 \; r( d4 E        }
}
5 G3 z) u1 i7 `1
2
3
4
5
6
7
8
  j0 V* n2 _4 A6 {' t7 n9
( e- P  C8 ~- K- G/ O10
11
) \2 t- ]( W- Y1 p# a  P4 j6 J12
13
14
15
# N" u( I6 `! p; `) a" z+ G16
7 T1 C5 P- m) ?17
18
; _' L! [8 n5 J9 H+ V19
20
! Y6 p$ C' m* B, T, H* _  X21
22
3 A% {3 c) d) y9 _23
24
, F( w/ @/ B8 S5 h25
6 k7 s, [' W  P0 G, i4 {26
, C0 Y& J+ j) R8 E" _27
) V2 j; Q: \$ ^' H28
29
30
# l# I+ t& V9 L" ^31
32
33
7 R0 I' J) F6 f34
35
$ |4 t0 ~# O( o: l36
37
38
  }8 [/ E9 C/ l% T39
40
) p! S4 |3 y8 _41
42
  F1 O" D9 Q0 |7 w! z2 q+ T43
8 M# B0 }; ^2 r# |' W# j! H! t44
! v  t0 v$ N* |6 ^+ O, j45
46
; N+ o9 O- v& @4 o8 m, H47
48
49
' P) V% i: @" `3 ?50
5 E2 y; l+ w- K5 I% \% l6 [2 k0 c51
+ v+ g5 u4 a; s52
' V7 l6 ^# K! }6 R1 U53
% s3 j' g- m& ]' D/ n54
7 R( X# T; ^5 X! H55
56
57
58
5 D+ o, j% t' d* t59
9 _# t' o! |7 ^* O60
61
62
; a! W3 S+ Y3 @' _+ b6 m9 Q63
64
65
! x% d/ L, O' |' Y66
3 X- T6 j- _, S) e9 a67
2 N2 x' f4 k. o& B4 J0 f68
+ O* `) @7 r* T, {3 r; Z69
4 _: _$ H% w- ]70
1 \: A+ a  n$ s/ X) a9 b交换排序
1 V9 W/ @7 Z( ^1 C) H, I冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2 d1 \- B9 A- C$ ?8 N! H) p2
) 。

- ^+ Z( Z7 P, i9 f* k
代码实现
9 ?* C! p* S# e% W' C4 T, x

import java.util.Arrays;
public class Solution {
4 r) [" D% A$ B       
        private static void bubbleSort(int[] nums) {
                // 循环次数
# d  A# E7 [. S. J                for (int i = 0; i < nums.length - 1; i++) {
8 I! Q0 j! n6 R9 N+ c6 O: q- }                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
                                if (nums[j] > nums[j + 1]) {
4 N! o% A' S9 L4 T8 {$ r                                        swap(nums, j, j + 1);
4 @0 M3 ?6 R5 f* L                                }
+ |. z( h7 `, f0 F6 J: V                        }
! M5 n7 }  x- N) o                }
        }
7 Y( O  Y, y# W* a* w
" h" c" ]5 I8 K- ]$ [/ ~
6 c4 ?$ H) y: C# t( B2 W/ j        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
                nums[j] = nums;
. S5 V# M) x/ J4 ?( t; Z                nums= temp;
        }

/ e  H& ?: Z1 i/ r1 s
        public static void main(String[] args) {
, Z& ]7 R1 v8 j' y0 ~( l                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
        }
}
( G( u( N6 ^, M  \1 C- N8 A1
2
$ a: D& s# a' c% }' f8 \) ~3
4
/ B, T' u! }, y, T$ k+ V& ~5
6
7
9 T! K, _. J& F6 h6 x2 }2 p6 }# V8
9
10
11
7 |9 `4 w3 E/ L5 U+ H12
13
( N0 N/ {5 U; q0 v# u% u1 I14
15
- o# P4 I9 d! c- @& J# d- S9 J16
17
18
- c1 N$ o- l- V6 W* O19
20
21
& a+ w) K# ]( v22
& Z$ i* f8 ?2 M* C# r1 ]* z# L% w23
24
# A( @, X% k1 c25
26
6 r+ u5 ]; t; d3 k7 |5 z4 o27
快速排序
3 J$ z4 p: I; c  h! g  h8 ]时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
6 s* L5 t/ x2 u" y& R
) a, a* ?2 ~8 \- D5 C2 A
/ ]( t; H7 g8 q# ~0 E代码实现
: A! u( F6 F) _6 M) c3 b/ s( `
9 ~" X8 S( N) X) \
6 k0 n* e# ]5 Spublic class Solution {
       
* M. F, j3 e* A* t        // Median-of-Three Partitioning
9 Y1 F- Q& D$ u) F( w; k        public static int selectPivot(int[] array, int left, int right) {
* Y& y# T( [7 C8 ^# }1 I9 X3 n                int middle = (left + right) / 2;
" R9 Q2 Z: ~0 a6 Y2 E               
                if (array[middle] > array[right])
* J, Q1 n+ [5 `6 H                        swap(array, middle, left);
( Z! l4 T6 {' A1 D  F                if (array[left] > array[right])
' X" e, `0 Q7 z6 p5 @7 e! n' V                        swap(array, left, right);
- i6 s& E( \1 N6 k/ a* Z& }2 N                if (array[middle] > array[left])
                        swap(array, left, middle);
               
) K) e4 i" e- G/ I' q. p3 v                return array[left];
& v4 n8 }$ G  @' o- l        }
' y6 }$ T4 s9 g# I5 Q$ ]. n0 X+ n       
        public static void sort(int[] array, int left, int right) {
                if (left >= right)
4 o8 Z$ w; K1 n                        return;
                int index = partition(array, left, right);
                sort(array, left, index - 1);
                sort(array, index + 1, right);
8 F+ q4 g& b0 j    }
1 |7 O) o/ [* y/ f5 P9 |5 R6 n  d       
        public static int partition(int[] array, int left, int right){
+ @: S* O- j' v' I: x5 ?/ U        int pivot = selectPivot(array, left, right);
% K) J% c# d' t# t. t/ g$ ?' @        while(left < right){
$ |) H! b- Q5 a            while(left < right && array[right] >= pivot){
, s' {  N7 u( Z# ~% G9 ~                right--;
, D& W. R5 a7 p0 U            }
            if (left < right) {
                array[left++] = array[right];
            }
            while(left < right && array[left] < pivot){
, m4 M" ~3 Y* W4 I5 c                left++;
            }
: |* V' {, }  ?4 w- \            if (left < right) {
* P) i2 R5 m2 c% V5 U& R- e                array[right--] = array[left];
+ I5 Z, j) B% m) i            }
        }
& A/ A) T" K; O5 u: N0 ?) u7 R            array[right] = pivot;
) W$ a' b# o; B        return right;
9 t9 e: f$ C5 d0 f( W; Y    }


; R6 H! O2 j) Z5 S. {2 j9 a    public static void swap(int[] array, int left, int right){
            int value = array[left];
            array[left] = array[right];
/ _& a% G0 v8 n+ M0 W# h4 m            array[right] = value;
( w" X  x$ Z; s# f8 C    }
6 j3 v2 h5 `+ d8 y1 S& `' Z

% q/ q* q4 P* ]. f& J+ P3 ^( a        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
0 J* {- n4 M/ E, k                // System.out.println(Arrays.toString(array));
  |$ s; r0 E% G# l& o: j2 D                sort(array, 0, array.length - 1);
& ?  p  i. R' f2 T5 z                System.out.println(Arrays.toString(array));
( A4 M- h, h, p        }
) ?' A: l7 X! E9 z2 e$ L7 P4 Y}
% r* _9 X( q4 l* B+ k, r% o1
1 X- Q/ \' ?$ ~) O; a2
' K5 x9 o, m4 Y# [. E  K$ k3
4
5
: t" L6 R. E) c; g0 `% r9 V6
7
8
6 R; R2 X( p' q: }. X9
10
8 l) F& X: b7 Q+ q5 R1 M2 p11
% |" n1 v: |' G9 |9 m4 L" \12
13
) l+ k" t( _' g) [& m14
15
& V% |5 \3 \4 f1 x  V" T' n: }: n16
7 x- A. [7 B: z& g17
8 j# h5 ^7 L+ _- x  m7 F18
- b( J# m8 i4 g, P; b$ b# h19
20
21
; v$ q$ E2 o( K7 @+ A- U22
6 i) U2 i; t3 Q* I4 K' y23
24
0 [% L! m. N! m' u3 N25
26
27
28
29
0 X2 S+ q* z3 X0 j30
# w  m+ O' Y4 y" @# c, {31
32
33
8 {. h& Z$ ~: E, p1 e7 E" ]9 t: i34
35
36
37
6 i7 Z5 L. X  v2 n1 B38
8 o5 U4 x# V% B39
40
41
( E+ F# S2 X7 e! {42
43
44
45
46
$ {" S1 Y% ~. N  Q& n47
% @' k3 O4 C1 q- n48
! \9 }8 R1 ]2 S+ C0 x* b! A2 l49
50
51
. F" F  a! f2 L52
8 V9 ?* L+ d, w# O$ l* U7 `53
54
9 M3 K/ [6 i' r/ {2 ?; J: [4 [% u55
56
57
0 y+ q2 E  s# Y4 |) B% R* G归并排序
3 y! X' ^, D' W! t将长序列从中间分成两个子序列。
; _$ a9 ^* {+ u& S( H% ^! u对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
+ q7 F5 X: W3 a1 \平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
# U9 I3 H; U3 w; _4 ]% f9 P9 Q8 y
4 z. w1 I: ?: r$ m" P& Q
代码实现**


- `2 p8 ~' u* p+ X1 apublic class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                int[] arr = MergeSort(array);
: H7 Q8 J" l  E* t5 M. V                System.out.println(Arrays.toString(arr));
        }
" `8 |* g, u# d+ ]) B5 i
$ F9 [, f3 w. Q1 ^" V/ l$ C3 x$ v
        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
                        return array;
, ~( P/ V5 f# i9 K                int middle = array.length / 2;
# _) J. n5 [! W  z! M4 m                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
+ n9 D- F& w- x3 @2 H. x                return merge(MergeSort(leftArray), MergeSort(rightArray));
/ g4 k2 s7 K) e' O. v/ L3 S4 r        }


( G  M. i4 u- E! N( [4 @/ v1 I6 f! ?        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++) {
4 [* E+ D3 A0 c9 l+ a+ ^+ u                        if (i >= leftArray.length) {
                                result[index] = rightArray[j++];
                        } else if (j >= rightArray.length) {
                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
5 \9 n- P* M; e                                result[index] = rightArray[j++];
                        } else {
                                result[index] = leftArray[i++];
                        }
; R. u' M/ [& |, ]3 S- K6 N                }
& W7 ?, M% X, D. |2 A                return result;
  w! e1 P$ x/ A% u' V7 U3 f        }
2 P" a$ m% F& N}


1
1 X5 n) w; Z0 U: c2
7 g7 ]; U  _* K, C2 o3
4
; B+ n0 _5 r5 z1 J* O5
6
! H4 o6 j% l9 k0 C% B  C6 k7
8
- J1 y6 e- K! `, H( O$ `9
10
+ K+ h) a! N2 `% l3 S, ~2 l' l11
) }0 y+ X2 L* j3 h3 M12
13
14
3 w( ]: E  L% \6 E8 G* t" n/ w) |15
16
17
18
9 K  }5 Z5 H$ `- {5 B& K19
: |5 J, q) T- ~+ k* ?20
& Z: r! a9 Z  w% @0 ]21
22
23
5 W6 m2 U+ R7 U24
; }7 c; c* g/ T- c, F/ v( A7 U6 C25
1 y+ E6 F+ u. ^6 z3 c2 s) |  ]" W26
27
# f+ L  o; P. Y28
( v% M2 N7 l; K29
1 W$ A& B5 \) P30
31
& f0 \3 C1 J' G$ V32
$ j; z1 H$ Q+ w; a* s33
: u: P8 w' I. S) p( V3 |基数排序
- I8 O; f2 h: ?找到数组中最大的数，确定最多一共有几位数。
) R( e% N5 ~4 h0 @/ L7 A4 j按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。


代码实现**


public class RadixSort {

# e. {2 h! h; w/ G8 Q* g: a
5 T8 n& H+ l2 T: o6 ^; w6 |1 s: Y        public static void main(String[] args) {
1 N% R, x+ \( A) K$ U/ E3 P                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
7 w9 t9 [8 {( I, W                int[] arr = radixSort(array);
! |# `  e5 e2 ~9 u! b8 V                System.out.println(Arrays.toString(arr));
# H4 J$ K( q  h) [' @/ r! O        }


        private static int[] radixSort(int[] array) {
: W( ^8 t/ H- ~/ p; f                if (array == null || array.length < 2) {
                        return array;
. `6 G! E& D+ Z& F                }
                // 根据最大值找到最大位数
3 P- b! M4 A1 j/ D$ _* ~                int max = 0;
                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
6 L/ c, x! s8 {: h# g& o8 F! E                }
               
                int maxDigit = 0;
+ ~9 L% L" [, D7 k                while (max != 0) {
                        max /= 10;
( O! A6 y- X- P% P' c                        maxDigit++;
0 l8 H; ^8 ~9 B2 k* `                }
               
                // 第一维: 0~9
                int[][] radix = new int[10][array.length];
; W4 q. x- H/ F1 X9 I                // 该位为 i 的元素个数
7 Q% m# W' E) `8 M' E                int[] count = new int[10];
+ O2 T' [3 N7 F; L+ E! H               
                int m = 1;
                int n = 1;
6 A1 V9 ^5 B" N* u6 ]1 v" |# W               
( p) e3 u, D" L, t8 N6 U. I                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
                                int lsd = (array / n) % 10;
                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
                        }
) U/ v0 X* {/ y/ S                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
                                        }
                                }
+ k: k& y+ @0 H/ r: N: D, c                                count = 0;
                        }
2 U5 v8 \  B( f                        n *= 10;
  h, k+ n/ U: L0 w! z                        m++;
, A  _9 [' X* [3 _: e1 _                }
                return array;
        }

/ p& R4 s. w* n8 v8 Z) F
0 @' t8 l! I2 N/ ~}
1
  d# J1 O0 j* A) i4 y. ^7 X2
) [+ ~" @) e5 v. t( \3
$ U+ w9 Y  ]. |4
5
( {5 V' W  `& a4 Y4 l6
7
4 z( T/ `  N- Q, Y! m( L8
9
10
11
12
4 u# p' E1 T$ m" V3 F' k13
14
15
16
17
18
19
8 h/ q0 i" `' a" i20
21
22
* ]( D$ ]1 [) I0 V" w23
24
25
* k! I- j# n2 _2 c& o  w26
27
8 p4 e8 r$ E5 T$ K28
& x/ U% L8 z7 c; ~29
; J* T/ z- L1 M) i% |- K  M" _4 k30
31
) [& z1 B+ r* g32
33
34
35
1 }* h. M! p2 \; M, |2 m36
( j# d+ J7 H9 t% H37
38
39
2 t7 a( e) m  I, |; P4 U$ a40
41
42
43
44
45
46
47
5 V, k2 `+ M0 o48
* d4 c# j3 V' @" a49
50
51
52
5 i" K" Y* m' M! k$ i$ C3 S9 e53
/ ?9 S8 a9 x) c) z; g& {计数排序
7 {, V0 u. B" z+ i  E找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
1 M! ^& B( @: D统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
& r1 W  b, O- X) w" Q% A时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。


代码实现


0 d" r- R8 u; W, D% Kpublic class Solution {


# }+ k( b' a9 n. @        public static void main(String[] args) {
0 b4 _5 X3 R7 q& f! w                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
5 R5 Q# ~* ?( v5 B4 I8 }! ]( }% t                int[] arr = countSort(array);
( f4 h# e% w4 c! B: g) H% Y                System.out.println(Arrays.toString(arr));
0 Q4 a- F1 f/ |3 |% B        }


        private static int[] countSort(int[] array) {
8 D$ F" m5 u& [) }+ G0 b5 x4 P                if (array.length == 0)
                        return array;
& N; s3 W- u; i7 {               
                int min = array[0], max = array[0];
               
2 i! ]( J* {; v5 z                for (int i = 0; i < array.length; i++) {
: \: j8 r9 j6 @( }: a* p' F                        if (min > array) {
! A. X- C' Q! ?! n! d7 u- _9 [/ F0 }                                min = array;
                        }
* d% ~  R7 h* `: C& x' k                        if (max < array) {
  h: C3 l0 p3 X/ g* \                                max = array;
                        }
1 r& M6 I4 Q& f2 y4 w8 l/ H- B                }
               
' ~' h) U; O/ L/ i+ \: J% z                int[] count = new int[max - min + 1];
               
                for (int i = 0; i < array.length; i++) {
                        count[array - min]++;
- |$ }9 @$ ]- [. j+ H/ @% V                }
4 E7 F- T# Z6 T: g" f& `               
                int i = 0;
                int index = 0;
5 M) T; E7 M. M& p3 n6 a4 d                while (index < array.length) {
% J" c# D- L6 }5 T- H# ?                        if (count != 0) {
( Z7 Z6 i# J! I, Y6 J' Z8 ]+ n. p                                array[index] = i + min;
' D) w8 j( N9 z. A                                count--;
                                index++;
                        } else {
# [4 l2 l, E8 `  A6 g6 k                                i++;
2 l! T* f, y! M4 X                        }
0 X5 A* l" K5 t- d- U; W0 U! H! H                }
                return array;
( u5 J8 d) P; N$ {% |        }
1 t) W# N1 g) I) n       
}
1
" J2 }# I- x( R9 F" E$ l2
! b% B1 l. I+ s3
, j9 w5 v+ `' f/ f( s8 b" l" `& N. e4
; e0 d# s7 V* w( w$ u$ f5
# r0 ?, t$ J. R" e6
7
( R  U0 Q. ~. y- s( p8 q5 h) P% y8
9
1 y9 E+ c/ w6 W* a; [4 g10
/ z) g/ z3 I1 u# b( N11
! o7 p) p3 r) y, d3 r# H4 f# u12
13
% f7 z& e5 Y/ |, z) `; `* p14
15
, D6 e" k; A, k9 p% m4 A, ?! a2 b16
17
18
19
! m% M+ h4 \/ I) B; w" ?20
3 r8 t/ F- [+ j& N4 j, x, U! S21
. C7 k# }, Z! n7 W22
6 o9 x# ^7 ~" H# _1 I23
( W5 B& S# O6 L* @# e1 P. e  n! [24
25
26
5 I( K! t3 f& g27
28
! X3 H- _5 }" P$ j  W29
30
31
32
& m( `$ M8 o. Q) y9 a& j33
34
35
36
4 @# q( k% @- R" n" C4 Y37
38
39
/ s" \) T2 ?6 {7 J40
) l! c& D9 @1 z1 E2 K0 P4 I41
42
43
" b4 F' k5 S9 v& }9 m& a44
桶排序
& e7 B1 D4 J5 y+ d————————————————
) X2 d  j+ }2 {! w% I版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
' ?# X4 b6 b: |( I0 c+ |原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153

" f$ p8 g" m1 v/ X8 y0 t