十大排序算法（Java实现）

杨利霞

% x' u5 h6 n- b4 s十大排序算法（Java实现）
; v5 e$ z- J7 ]" l% |
- X( C8 I9 f  s3 @2 u5 Z十大排序算法（Java实现）
2 a# ]! R# ^/ G  S+ r排序算法框架
: p% w/ D" P; ~& K! v排序算法性质
插入排序
/ h# k# s2 q: T6 J0 d直接插入排序
/ ^) o0 D8 r& l4 M" w1 S0 U希尔排序
选择排序
简单选择排序
* [2 H  g/ }( T+ y+ D+ o+ c8 B. K堆排序
" D: `  Y0 R# d6 i/ r) a2 W交换排序
冒泡排序
" S# }7 q! ?+ M' g, v0 l) \快速排序
归并排序
  {6 j- Y1 W# A) g) ^' }/ r基数排序
8 N; _& [+ B2 T8 n+ p计数排序
9 ~( a5 @$ X& j2 F* V" F桶排序
+ r2 B8 A2 z3 Y5 M3 R8 h7 S* V0 B更多文章点击 >> 这里
1 {' L" v2 |) T6 Z
5 @& x4 t0 ]3 l  P1 [7 S8 p
) g( V1 J' q$ W- V, X. A! J排序算法框架
/ h# F" N9 N  [
, b; N" u0 x3 h! o/ w


2 Y* m5 ?, e2 d) s0 e排序算法性质

) K2 ?! \3 _- ?  L
* t, H7 X7 A: B
& r% d% @- f, f: g+ }6 f" q; X
插入排序
直接插入排序
从第一个元素开始，认为该元素是已排序的。
' r/ d+ V- M, z取出下一元素，与前面已经排好序的部分进行比较。
( S5 g, y. d5 ~" J! b& s; _2 B若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
! R2 C6 g6 c9 s; q最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2
) 。

; `, E% _6 t$ m* u- H2 Z
+ r( o. W( Q$ H/ e% z% z/ a# q代码实现
- H& Q4 f4 |# j; Z9 ^& m
) }- v. T  ^# z' v1 `
9 k4 m3 _) e; Tpublic class Solution {
. t; n; P, l& e$ h        public static void main(String[] args) {
- @1 F" k' i  C& y7 N$ Z5 r" k6 O                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                insertSort(array);
                System.out.println(Arrays.toString(array));
        }
; H6 c2 c( R' W& B/ v

$ C! _0 `* R1 ?$ j( b( ], f        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
5 l' h- Z' h/ A- U1 A3 \                        int data = array[i + 1];
                        int index = i;
                        while(index >= 0 && array[index] > data) {
8 T6 x  _3 U( D0 c, k                                array[index + 1] = array[index];
% q9 n) H/ ]  `                                index--;
0 m& S6 S' O) N4 H                        }
7 k% m4 m2 W" Q" t  z- n                        array[index + 1] = data;
                }
+ [  s/ a4 f, U: v6 `, N        }
}
# Y* ~' d2 U4 P1 ^1
2
3
( `; k5 R' i- j) h8 j  ~" a9 L4
5
7 R% J  u5 E. N6
7
, r( Q4 D, [" I$ ^+ I7 q% u8
9
10
11
7 X  l/ k! `/ @9 i, |12
13
5 }& b  E# m* b: M6 ^14
15
/ d0 T/ {# f, W; L16
17
6 }  L* l* B0 k( t2 T18
7 C+ O! C* t0 k; |6 [, \19
& O9 ^" J' z6 {- I/ z/ _希尔排序


时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
6 t' k' o6 i0 T! v, R3 S
/ [/ r0 r7 j# [/ H' N- J! c" O5 X
代码实现


. G& f) _, Y8 ]  f* Qpublic class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
% c" u4 |9 c2 x+ b; ]0 q                shellSort(array);
. J' ~9 g* u" y' J* ~0 I                System.out.println(Arrays.toString(array));
# C1 m* n/ Z' ~9 [3 G% P( I        }

+ v2 \0 F$ N, A8 e+ `4 C
        private static void shellSort(int[] array) {
6 r; q9 v/ M# I! @& s- K' {0 I                int gap = array.length / 2;
                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
                                int index = i - gap;
                                int temp = array;
                                while (index >= 0 && array[index] > temp) {
; Q2 G! j" G% K& a9 I                                        swap(array, index, index + gap);
: ?$ w; n! T% c                                        index -= gap;
! P# q2 d" q4 w: G                                }
//                                array[index + gap] = temp;
9 D9 `% v  U: Z9 Y/ Q4 j2 u6 H                        }
5 I9 S9 b& A7 m: _6 r                        gap /= 2;
' z; D" _: Q* N# l8 ]: l                        System.out.println(Arrays.toString(array));
                }
/ P9 Z9 n% x) f        }

( ?' i6 a4 M$ x* |' k: @7 A$ b
6 j1 t% A- q6 c+ k        private static void swap(int[] array, int i, int index) {
5 l, Z: J0 c$ r& @$ j                int temp = array;
                array = array[index];
                array[index] = temp;
        }
}
1 u) D5 P: }4 `6 {5 o. |1
2
3
4
1 O% J2 W* {1 p. H1 x5
6
7
# _5 J' n- ^* {8 l8
9
& I4 ^* @: {# @0 q10
: l6 ?# C& u0 T11
12
6 W+ I3 S5 O8 C' h- ?13
% c  F5 u3 f, P; C4 E6 F4 U; g4 M14
15
9 r& U# j/ ~, X: n- ?16
17
18
3 z/ _) N/ Y, V- Z9 e5 N19
5 L  X9 X  |- C20
; v( w9 l; y/ u3 l) F* ]21
22
23
5 K* v$ ^" ?9 }24
: ^: W8 @, q: P2 D/ Z25
6 P6 b- x! I" H  \* r! R26
27
5 W  s) ^! d% R28
* p! A! z. M1 N& j$ i" f29
30
% ^" `2 t9 j+ r; V7 Y选择排序
& l% _+ D& e: M: }6 O' w. M, J简单选择排序
+ ^4 ]& v5 Q+ X9 j1 Q$ C从未排序的初始数组中寻找最小元素放置首位。
0 ]9 ], G0 j$ N) {- j0 E从剩余元素中继续寻找最小元素，放到已排序序列的尾部
3 r4 M3 L; N3 q* ?1 ]遍历数组，直至结束。
9 t/ |9 e. T8 w4 N3 X) B时间复杂度为 O ( n 2 ) O(n^2)O(n
3 W. U. M2 p. @8 [* ]2
; w9 T, v, S4 x1 m9 B- N ) 。

/ e; R; D$ b+ u9 P
代码实现**
5 N5 F% I7 A' K; k" O: b

( |  P" b0 Q+ C* Z  r: zpublic class Solution {
        public static void main(String[] args) {
2 k0 U$ R+ G: C                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
8 o4 P' N( n; W" j% |, ^( D1 |                System.out.println(Arrays.toString(array));
: l. X, u- k+ S        }

( c# H, ~7 }8 t2 K4 J2 j' U7 j. r
        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
. W& a# A, _; ?5 z# Z                        int index = i;
                        for (int j = i; j < array.length; j++) {
2 \. B3 _) o0 Q0 T2 T" E, C! l                                if (array[j] < array[index]) {
                                        index = j;
                                }
                        }
                        swap(array, index, i);
) ^; U! |' T* `/ _! r3 u                }
        }
, e7 T6 G1 e( u! Q2 M" `

        private static void swap(int[] array, int index, int i) {
1 `: l! ~4 g0 r7 W6 d- S$ J  `# @; H                int temp = array[index];
                array[index] = array;
# N; U( Q/ r% z2 v. X                array = temp;
1 \9 ?5 z. N8 m. D/ x" X        }
  V0 s- b6 J& S5 }6 y6 d}
1
2
9 Q8 T! \+ r, C) L4 \- U' D3
4
5
* l5 l- S7 ]) G4 `8 c6
* ]) `: q, Y: F) Y6 T/ J3 }, U) ^  W7
+ M3 |, `. U* `* S$ A8
9
10
11
12
" T8 Z1 E. w  d, k, E13
14
15
* s+ U1 {6 h( h* l2 c# w. h16
' c; z* G$ U$ F9 Q17
) c6 |" j) p0 k; {18
6 S$ i+ g# r! N0 f- U19
" i" P6 y0 j8 i* k5 b20
1 F* h: X+ f/ N& Q* A% u) t21
1 Q  i# n! V: O0 p22
23
' _) n" f# G2 L* C" u24
25
6 o3 P' W  t2 E6 b' V5 @& l堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

+ y1 h. z: B8 g! C% M
& K4 v; K& b0 m! u代码实现**


9 F) t6 }* Y. X. ]0 epublic class Solution {
, Y+ k# E2 c" j: y        // 建堆
5 |0 _! }; K7 T- i        public static void creatHeap(int[] arr, int n) {
  U4 o; m7 O9 ?                // 因为数组是从0开始的
                for (int i = (n - 1) / 2; i >= 0; i--) {
                        percolateDown(arr, i, n);
  M) ~+ L) S' M! y                }
        }
        // 插入
        private static void insertHeap(int[] array, int data, int n) {
1 ^7 W  w" m4 D( Q                array[n] = data;
1 [4 X; H4 Y: j* b* w                percolatrUp(array, n);
        }
        // 删除栈顶元素
. _8 j, u* B8 l2 Q8 \; ]$ ^1 E        private static void deleteHeap(int[] arr, int n) {
                arr[0] = arr[n];
, |8 W4 Q9 W6 O& \                arr[n] = -1;
: Y& D5 j- S$ T  Q& W                percolateDown(arr, 0, n - 1);
* t6 Q2 O1 V; H1 h, u        }
; {4 z# w: Z/ J' ^9 H( @7 _        // 上浮
5 F8 @0 ~- O1 @& D+ Y1 K) K        private static void percolatrUp(int[] array, int n) {
, l( Z1 m8 I  `: c0 o" _; b                int data = array[n];
                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
% |) m. _$ }# k5 Q- |' E                        array[father] = data;
                        n = father;
3 H$ ^; S4 J0 y6 Z  G4 \                        father = (n - 1) / 2;
                }
                array[father] = data;
7 ], V0 N2 }6 Y& T/ j3 @  Z' r4 [        }
        // 下滤
  O- t' I1 Y/ u  E8 o8 A5 f. h        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
1 C4 b! N; i7 L2 U) P6 t                int child = 2 * i + 1;
( s( O. V: E+ u4 e                // 遍历整个该根结点的子树
                while (child <= n) {
0 f4 g6 U: N8 ^$ V" w/ X& p3 f                        // 定位左右结点小的那一个
                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
                                child += 1;
                        }
' R2 i: D( C5 I3 t. e                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
; }4 _* b. a/ f# I                                break;
                        }
                        // 互换根结点和子结点
7 \- v0 |2 q5 H/ F, q                        arr = arr[child];
0 Q. a) R# m0 U; `& Z                        arr[child] = father;
& _1 a1 H  J/ F4 ]                        // 重新定位根结点和子结点
                        i = child;
3 c7 `6 o$ r- S% l- V9 ^) v                        child = i * 2 + 1;
% c/ N8 S% V$ J                }
        }
$ U( s7 ~! y2 @   
        public static void main(String[] args) {
$ W5 N- D) z+ M) R                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
                creatHeap(array, array.length - 1);
0 f9 _2 W* y, a  X6 J/ ?                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
3 y% ?7 U1 T7 o" m& J               
( \. ~/ v. p% [* _) i; d& f2 O7 f                deleteHeap(array, array.length - 2);
8 E7 J8 I, `7 P                System.out.println(Arrays.toString(array));
               
                insertHeap(array, 3, array.length - 2);
2 `! |- P7 E6 U1 a                System.out.println(Arrays.toString(array));
        }
}
; z6 F3 J, f/ }+ |; \+ ~1
2
. N' {( B5 U. v; |0 T8 Y+ b: s3
9 Q; ^8 t* [' B9 t4
5
6
# D+ K; u$ |" S9 `: ?7
8
9 S3 C" Z" U* ^2 O- D8 b9
' A' Q3 `6 P8 }9 `5 N* [! [2 f10
& [3 W' X; X: q  \) @9 \11
12
13
14
15
6 H/ t/ j, p* P+ x' Z" L1 k' m$ m16
17
18
19
20
0 J6 o' Q8 Z! A21
# D$ L3 Y# y7 e9 p9 t  q) Q22
23
8 y, B  p# P$ G6 R) A" D24
25
$ _7 G7 C9 a: _" U26
27
28
29
+ N- {# v6 H8 b6 S- A0 B30
& S! ~2 ~8 R) s! Y/ y0 {31
32
33
. T. B* h- q0 [4 n, T5 R34
35
" }, w  M, H, u, F36
37
% `% t4 g* a: a) h) Z38
39
  m. W5 U; c# X4 [40
& K) t; l8 g' z" I9 b$ _41
42
43
44
45
46
47
' n( h! p( t- E2 Z) a48
2 j1 \5 K5 f* F) w( Q5 R. ~49
$ y, V) K- g- J. f* z50
% C: r8 P3 s) o3 H51
52
8 p0 O) \" L/ m# g; M' l1 A. X53
54
55
0 {# R4 k) g& ?- v: }: j56
57
2 n: S5 K7 n! h4 i& h3 N58
59
9 c1 d; C8 t* Z8 R" s' G$ y. t60
61
62
63
: D0 O1 E' E/ B4 R- p64
" `! g  k4 L& @& s- y% O0 ~65
66
67
( }+ c" v, ?( u4 Y& H) s0 H- Y9 ^6 A68
69
70
交换排序
3 z* U  l* V& U/ {  S/ }冒泡排序
2 ^+ r% B6 _& c依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
9 ~8 H& l) y: _, D6 y9 m在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
% R9 N2 {: ?+ Q4 T9 [) e' c9 r遍历数组，直至结束。
, [7 u& t1 R$ W) b最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
- ]) V! ?1 Y3 l ) 。


$ B, P" S) o5 u" k$ z3 w代码实现


0 p1 g% s+ Q& F$ }. j0 ?& h* o" V: \import java.util.Arrays;
0 B1 o) i/ g4 m2 s5 ^public class Solution {
       
        private static void bubbleSort(int[] nums) {
0 P, m+ Z: ]9 ?  o& p3 w9 u                // 循环次数
9 S# |( N" q4 b% A- @! q$ `% I5 [                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
5 `' o9 U- T' T+ C/ a1 K                                if (nums[j] > nums[j + 1]) {
/ J+ C7 }' c9 |- K                                        swap(nums, j, j + 1);
8 O; [3 E! D) I) ^4 N% d                                }
                        }
7 n5 u, t' g% f4 ]" g. h" g                }
        }

1 A. ?4 r: h1 E4 k
        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
                nums[j] = nums;
                nums= temp;
        }


* `0 c) J1 o' G1 o7 `1 Q  O        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
3 t6 C# n( ?- T" t5 W7 T" i        }
/ I$ k7 ]  O- |' |2 M}
& ]; E3 W2 r( H' S- f, @/ V1
- i; i7 j% [4 D. P, l2
' M2 ^) j) h2 A$ Y3
1 j6 d& z! W; B3 a4
5 O! \. p6 @7 y4 s* Q2 p& A5
" h2 p% ?9 `4 _! ~6
7
8 [- Y& T) s# Q  Q: H8
9
7 R: X9 M, `9 Y10
11
* Q5 F# C, L7 X/ S! f; @$ u) N  O12
; Y% a$ V1 W8 H0 E" C13
9 ~( l1 w" X  G7 @# v14
/ o. y5 A9 q! g15
16
17
' P7 |8 A7 g) O7 ~% ~$ Y5 l3 R18
19
( I& o% ?+ o7 L9 r7 ]6 Q1 b20
21
22
23
24
1 F, V- V; S: X$ A! u0 f25
26
" V% e) G- l; i2 j8 F% z- ~27
. k8 i5 y( @" ^0 ?- J5 M6 `9 N- |快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

* B& e* S4 A1 `5 ^- Y( H% S2 M
代码实现
* B7 \- g, E9 c& a1 Z, ^) r0 r

  ?. Q0 U* g1 B, @  Kpublic class Solution {
4 T% F- ]6 c1 p4 o. c       
- O; d1 n: X& A( i+ P5 p6 [        // Median-of-Three Partitioning
        public static int selectPivot(int[] array, int left, int right) {
' [0 L- e% {5 l4 E; T                int middle = (left + right) / 2;
               
                if (array[middle] > array[right])
0 J# L: t; U8 |6 W                        swap(array, middle, left);
; l! q) h* v7 f4 p& X+ r) s% R                if (array[left] > array[right])
                        swap(array, left, right);
+ t0 ]; F0 w8 c6 k6 I& Z: t: @! m                if (array[middle] > array[left])
                        swap(array, left, middle);
# e# w. x: B, S4 M3 T               
% o) D8 t$ j8 N                return array[left];
& K- E2 x2 u+ U- Z6 |. [        }
' k0 C, x9 Y, }$ L: q       
1 }8 E# L3 p; A5 C6 c- {        public static void sort(int[] array, int left, int right) {
                if (left >= right)
; @8 U1 N1 i4 s; Q, o* l                        return;
                int index = partition(array, left, right);
& p. e: ?- W6 l2 z5 O                sort(array, left, index - 1);
6 J1 o& l5 n" T! c7 K                sort(array, index + 1, right);
$ z' G' u; [/ \# ^    }
2 O* \* {7 p8 M" z: K* Q+ X% I       
        public static int partition(int[] array, int left, int right){
        int pivot = selectPivot(array, left, right);
        while(left < right){
0 p) t! ]' z5 z! |4 M8 q            while(left < right && array[right] >= pivot){
6 Q# Q1 M8 c; x1 Q                right--;
$ a  {% o3 @$ k- t8 ^            }
) H4 g& m4 I$ d' ]1 Y4 G            if (left < right) {
6 O9 C, ]0 |7 P) l/ b                array[left++] = array[right];
            }
            while(left < right && array[left] < pivot){
                left++;
            }
8 S8 A6 X1 u2 A" _            if (left < right) {
                array[right--] = array[left];
- P  e5 C: @6 B2 j            }
* s. Q5 k+ r+ `! |' R2 d$ A( X! T) Z        }
            array[right] = pivot;
        return right;
    }
1 q% d' k" [8 p, g/ P
7 R8 v& @( S* |; K
( s; P  m5 K- M4 I! [0 ^: F    public static void swap(int[] array, int left, int right){
            int value = array[left];
$ w/ W' \* [/ E% A/ `7 q            array[left] = array[right];
/ P+ o8 S! Z4 r( U7 h% \            array[right] = value;
/ ?% P( }3 u3 S( v    }
" a8 l0 K! \" x0 |) t+ q
8 X1 h2 q+ r2 q' J
/ W; y" N, t2 O7 U( Q, @/ P  Z        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
% J% [  I$ q0 a* d* }                // System.out.println(Arrays.toString(array));
                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
& `0 L: q$ K3 W6 }        }
}
1
2
3
4
7 G8 y2 c  I& Z5
6
7
# A* M3 F+ @( @, r8
1 _& U/ R! \) s  }9
- x; a, A0 ?8 [; D0 @$ Z10
11
3 M4 @. x; H) N/ D% N$ F2 k* V% q12
13
4 A9 `, r1 @$ U# z14
15
7 h# H. Q1 b' r8 O: Q% {16
17
18
5 h2 m0 ]7 J( p19
; w" t( Q+ C0 F+ a20
5 r8 {1 y( e) u21
9 p$ O0 N. V8 A" F/ r5 _22
& y5 A+ @. W. L  @* \23
3 K. }% Z% Y. q1 h- q2 D* p" F0 Z" l24
, R7 X5 Z: d, R% @2 V# g" F25
26
( Z0 o# T% n  l% O8 W27
+ c' w) w, A  Q, J8 o' M# E  {28
* O+ \0 `7 J% K& J29
30
0 m- `4 l& y/ l1 K; ]31
* u% l* n/ c6 Y; J3 H/ W32
: h0 j! }1 h$ [0 F8 s$ q33
8 C6 F) z/ X0 j9 \7 M: N& @34
35
36
: I+ m  P( ]& P# M( `! q37
+ P" b- X8 s- E( ~, x8 P38
39
+ j& h7 n4 e# g& t40
41
42
9 Q) S" w, @- Q+ s! C43
  T3 X* P. F0 Y44
45
46
) H" }8 \$ j4 l) |47
48
49
5 F( `' o  b9 v/ n( M  w0 G7 a2 m50
& \% ^3 L1 A/ c1 _* @51
52
53
54
+ H9 ?6 Q0 c# ^% z7 p+ F- V55
56
57
0 S" |4 |2 h4 x归并排序
将长序列从中间分成两个子序列。
6 B0 B0 l' g! [9 C" L+ P! L( v对这两个子序列依次继续执行重复分裂，直至不能再分。
0 k7 i( y& T5 |. `3 }5 ^4 l递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现**
) D+ F* r3 D& \$ F3 @6 ~
7 s4 `* ?8 F5 E# n: z3 K/ w
0 P2 [- l4 D; z1 R. npublic class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
; O0 g( G, h2 v: s( I                int[] arr = MergeSort(array);
& T; f9 S4 p. x8 |/ F% ^) t0 y                System.out.println(Arrays.toString(arr));
        }

7 B5 v% @& h! ]% Q
2 X! ^4 c; q7 V& U        private static int[] MergeSort(int[] array) {
% {) M$ o. P! x+ {! J) L* Y                if (array.length < 2)
; q; `! _, ^* Z, [; {0 t% j3 r: `                        return array;
                int middle = array.length / 2;
                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
0 ], J; L' [2 P( X, L4 m                return merge(MergeSort(leftArray), MergeSort(rightArray));
; t9 V; ]) C$ E& L7 h* d+ G        }
# @* c; C9 _! G0 ]% c

        private static int[] merge(int[] leftArray, int[] rightArray) {
) ?: z7 O) U" C7 g) f( P/ a/ O                int[] result = new int[leftArray.length + rightArray.length];
                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
6 Q* I! k7 a, n  O2 o. a                        if (i >= leftArray.length) {
, I5 F& S, H% U. ?1 @                                result[index] = rightArray[j++];
: f, ]4 g$ J1 @( V' Z3 q                        } else if (j >= rightArray.length) {
& o# G5 \/ ~- ^1 |  r" S3 D                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
- ^' n5 `8 S+ ~2 [) {1 L5 D5 q" N! {                        } else {
2 v0 V/ @% u9 C; X& W( O                                result[index] = leftArray[i++];
                        }
                }
, M* y  Q9 Y. d                return result;
        }
}


1
2
" F% L3 s8 I7 K' ]! r' J3
  _3 S6 \* r6 M- W8 K7 s9 `) U4
5
6
& S+ t( [* ~8 a/ C5 p& z0 }7
" [9 M( u  `7 F$ V+ a0 Q6 v# s* l8
9 g% f9 b! a1 f! I& q9
; P8 n% M9 `# _3 }/ P6 _5 E10
11
12
$ M8 e& G0 @. e! A- M13
14
, C8 k) i$ b2 W3 j4 J15
" O5 `1 l9 E5 a16
17
18
19
20
6 Y# ?4 r- x$ Y21
22
23
( u) \3 ^8 N  A24
9 w! U4 d9 [6 I% \6 L5 {1 d& L  M25
26
27
# o$ C3 s& _* P/ C% `28
29
30
31
4 b3 ~5 m) b# M32
* F. j1 ]0 @5 ?33
基数排序
, s8 R, e9 C- F8 A- M4 r3 |5 `找到数组中最大的数，确定最多一共有几位数。
! K: [. B1 c# |# d/ {& y按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
) P" B9 D4 L# Y) s; f" d- d将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。


# f+ l+ c4 R! V9 f/ \1 D代码实现**
6 t0 y9 r0 H2 ]

public class RadixSort {
0 L% |% y* i+ v( q7 o
" Z* e- F9 l/ O8 N1 A; W3 o
4 e: A- y9 y5 F8 t+ m- Y        public static void main(String[] args) {
' X8 K- W; f! y( [. r+ y& `                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
                int[] arr = radixSort(array);
                System.out.println(Arrays.toString(arr));
, [% R, s# B/ c" i9 E        }

4 f' k* h/ ?/ s. s) ]: B9 R. F& s
$ M( U2 N5 t0 C) a7 }1 T7 B        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
7 U+ h$ P# x1 e2 D! E5 t0 w                        return array;
                }
/ V: F4 ]( A8 `' K+ A                // 根据最大值找到最大位数
                int max = 0;
# Z4 Q9 J( M: b4 |                for (int i = 0; i < array.length; i++) {
0 T( Q6 ?0 m  z" `4 r- b. Q& Q0 K                        max = Math.max(max, array);
                }
               
! O5 z# K7 N5 c% z! V) m  p                int maxDigit = 0;
/ j% W; K( B3 `. |5 S                while (max != 0) {
+ c" h4 t4 S, Z* s) T2 v. P) V3 |+ n                        max /= 10;
3 X' ?8 J5 \3 X7 ^                        maxDigit++;
) Y% K( P' n$ v. m4 D% ^                }
+ c. u" w- [- q# b# c7 m( \1 z4 f1 r1 {               
" V& B1 @: t$ D0 D9 P                // 第一维: 0~9
                int[][] radix = new int[10][array.length];
# t: e  [# b; S5 I                // 该位为 i 的元素个数
                int[] count = new int[10];
               
                int m = 1;
3 I! E; a5 r" P& c0 h                int n = 1;
               
                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
. a( }4 D7 [% S; f& c5 }                                int lsd = (array / n) % 10;
                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
$ A1 m) M5 G3 \8 y# ]: a* ?                        }
                        for (int i = 0, k = 0; i < 10; i++) {
7 R: K% S$ Z% X" n, Z, F                                if (count != 0) {
( b# A% }# ~  ?                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
, {% j% K" Z4 r) l* z; p                                        }
                                }
                                count = 0;
                        }
' u! ?+ [/ h' U9 k" _+ ~, i                        n *= 10;
  o# \5 Y# {: U9 I                        m++;
                }
                return array;
% J" k9 a5 c1 E8 L, c  A        }
, U% t# h: ]* J7 z4 m9 c" R
0 s9 H; E; _) W5 u" T
}
1
, J6 V6 t$ r) S' `2
3
8 K7 ?5 k# U2 g) k8 z1 N4
5
' I9 {4 q8 h# R. C: a- A6
7
8
6 p) v) \7 c( h3 I; }  }9
, X2 b6 y2 z/ i4 p% b6 ?+ v% d10
11
5 M1 Y# j4 s& E12
13
14
15
* T2 G% c0 H) x2 g16
17
7 b, F* N' E) f9 i( m% L; Q18
19
20
. U1 W! j5 t& [: B, o21
- f$ G) \$ D8 g. a6 ~- J0 t22
+ @  c" i2 t- H+ }% f8 i23
$ Q" y+ E1 d; j+ [% H& f# Q# p& }; j24
25
26
4 _2 W* }0 N& g6 D7 c( J& r27
4 l" s1 @9 q" v2 N5 q. K28
1 n6 G3 E5 r% Z3 _( N7 W. T29
* _# A7 o* c9 J+ }5 |) S& q) u30
31
* L7 f; `# l' s7 M6 `$ `; _32
33
: b8 Q; a; u5 A0 c( n* r34
35
36
9 Z& D4 _+ [! U( |$ [4 f& V) ]37
. k) _' y, w% G- j' n$ M+ d( F7 K38
: d/ J3 C, n6 w39
' t- _6 I# g. C  O1 J40
7 L8 ^$ v! \+ }: Z/ |41
42
43
2 v6 x( s! z0 o- ~9 Y+ R' L, r44
45
: G3 [  v# p1 u5 r; G* p46
47
7 b4 G! v7 q: o48
/ A, t0 M8 r' L9 Y+ B8 {49
$ K# b( k$ X/ p1 @7 e% S* d  N50
. s3 W% w) T, Y) r3 n51
# h9 v( [" T$ N. ?6 D; V52
53
5 K3 y3 N. T2 K7 G计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
) I- |5 Y: i# d! m; C, |  u- g统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
6 }7 L% R+ `) [7 E! {! Q时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
' J# ^3 J% `: q$ B% j3 u2 j
6 H5 b# a9 H) j2 s7 Q/ b- B0 W
3 o- Z4 g0 z( J. ~4 s2 k代码实现
% H# o) m. }2 ?0 q2 Q

# A  }' ~$ Y" k1 U: }/ Tpublic class Solution {

6 B  p! i/ @8 Q; Z2 L# @
        public static void main(String[] args) {
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
: X3 ]: X# O% n( O                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
- j9 e2 R( k7 Y( z0 A% U        }
9 [9 J& }! p! ~/ |, y  M. Q7 i# ~
. O& X/ h# ?; z5 ?
        private static int[] countSort(int[] array) {
                if (array.length == 0)
+ }, a, V: ~, N/ z0 C% ]7 \0 W                        return array;
* h% I- E* {& W5 \$ p               
# J+ L* X4 _  ~$ l- Y                int min = array[0], max = array[0];
               
                for (int i = 0; i < array.length; i++) {
) U  I+ Z- K3 R8 J* \                        if (min > array) {
                                min = array;
                        }
" O4 b7 P/ i' @8 U* U5 M0 n# I                        if (max < array) {
                                max = array;
8 P2 i/ ~( [% A! x4 g                        }
                }
7 f( I% c* X3 I: I4 N               
                int[] count = new int[max - min + 1];
               
                for (int i = 0; i < array.length; i++) {
                        count[array - min]++;
                }
0 H: Y. S" n& Q- R, m- v2 S2 A               
                int i = 0;
                int index = 0;
3 w) w% l$ {) C1 i& k1 W                while (index < array.length) {
% v, U( ^, l% T6 Q                        if (count != 0) {
) r7 M4 d3 s) ^$ Q6 v+ O) G                                array[index] = i + min;
                                count--;
                                index++;
                        } else {
                                i++;
                        }
                }
+ h8 L! C" D4 P9 r                return array;
        }
       
}
  @' n4 n% L2 ~1
2
' l. t$ o) t* s% `/ f3
8 B  _% B9 p2 X( D& U4
5
5 l! p# l1 Q# C; Z4 U. H6
9 z# E$ ~7 E- c+ l2 |5 Z& G) E. J3 G$ ^7
& Q8 M( Y9 [/ J7 \+ Q3 G. T6 d  F4 u8
) k+ i6 v) m6 V5 d7 Z9
, ~- v3 u- d: U, U/ B10
11
3 _2 N  e  m) `; W' l/ U: q& V' f12
13
( ^1 x& h) r* {% T1 b14
2 g& S9 i, T8 P15
) c$ t2 i1 c- j" L: b; W16
17
9 r+ V7 `- V) s1 ^) F: @0 L18
7 I* T3 Q$ N3 \" }, d# E- S19
0 e- o. b* J- @1 _20
21
22
23
24
! b. l* N& K( ^* B* j5 C25
- r9 Y/ N! ?; g+ p! S26
0 z  e8 M) ^  y# h4 d27
28
29
9 ?2 m( C. A# k2 u! A- k& w# u" ?30
: [$ i4 C# t% ?0 y; J- d31
32
33
34
, I# m  r3 |) r, R35
36
37
38
# ?9 h6 Y8 l7 u. n+ H5 N. {39
40
41
42
43
; f# m; t4 {& u7 W44
桶排序
( c& Q, A+ X+ G$ J————————————————
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153

8 Z. @. T5 V4 Y7 Q
- X+ p* D! W0 e) m" l2 c! s1 ^