十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）

0 M2 l+ ?$ J  S十大排序算法（Java实现）
: v% _) J. l6 m! S" \排序算法框架
. O1 s+ {! o3 z1 |# o) S排序算法性质
插入排序
8 D9 J% \# G5 _5 J6 U: L2 v直接插入排序
希尔排序
  g6 }& ^1 R: q' n: A选择排序
. Z  I6 d* N0 t简单选择排序
5 Q, R; F; V  p- p) ]* X堆排序
交换排序
冒泡排序
+ n6 A# Y& c; Z1 n% M% A$ k+ ?9 \快速排序
归并排序
" x# B. O' {. t# Y& R. E基数排序
- u2 p: Q2 O7 C计数排序
桶排序
' Z# j2 y3 t$ U: P) R2 N$ m更多文章点击 >> 这里

) F# P- ~4 x8 A3 P) j/ [3 T- q
; i7 {& _# V- b& V排序算法框架
9 B$ s. ^3 C5 ?

4 N2 h) E  b# x+ C: \3 F! r* ^' k) B
& M& \' H% p; t- z0 h# z1 k: R
4 z& C/ y* F% I- ^* }- o0 Y排序算法性质

3 Z  t2 p' e3 t  q& N3 y, b# \


% Z  b% g- ^' W: x6 b7 C) P插入排序
% n! d% j  t; M5 I$ k, _6 y, w直接插入排序
4 F( z2 c' ?+ K9 V' {7 L从第一个元素开始，认为该元素是已排序的。
* q8 i8 I, p3 Q, X" v取出下一元素，与前面已经排好序的部分进行比较。
, E- i  y! H& I! T9 v* l! X若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
- F) ^$ W( {0 G8 n. l0 O9 W最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
+ l* k4 \7 L+ l: ~4 h" @' e2
) 。
; K$ E% |% n+ L

; ]0 Z7 ]: b7 u' G# `, z代码实现


public class Solution {
        public static void main(String[] args) {
) |4 U$ _7 X& f                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                insertSort(array);
. u7 [9 ?: l# ~9 m# S" w                System.out.println(Arrays.toString(array));
  \( L8 d9 F0 C        }
1 _& w) Z0 v+ j! g$ B* a  c$ i6 ~
3 c# Z3 ?  @" a! H7 o! ]3 X/ M
/ V4 F. D6 z2 J* Z: _        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
                        int index = i;
                        while(index >= 0 && array[index] > data) {
9 `% P+ `7 q7 S* V: s                                array[index + 1] = array[index];
                                index--;
                        }
                        array[index + 1] = data;
                }
3 Q6 U# B8 r  M; k        }
}
1
; N: \. C* C5 E2
  t. u8 u( C0 o& E2 I  T" z3
2 s; O! u) @- g5 [  l3 j9 P# q# h4
5
6
8 w1 m( n* b; ~* E, \* w& ^- q$ H7
8
9
10
11
* w! }" M; N' H8 {12
13
14
, N$ L0 Q* u, j1 r8 A% m; f( @15
# j2 Z8 u! q7 o6 L- w16
2 t( n9 L! T! }2 e17
18
19
/ ]. w& @' _& ?9 H3 N希尔排序

, Y, x% p$ u6 j( O8 S# n' o* ?/ q" E
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

5 D$ H1 Q. e$ M2 m
: ~* p; O2 u$ J0 V  r' v9 A: n代码实现
+ U& H. d5 K( |: J" X

public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
% n5 Q! p  q4 Z$ i) V, k                shellSort(array);
                System.out.println(Arrays.toString(array));
) u8 p3 d3 ?7 E" {  S! Z; Z        }


        private static void shellSort(int[] array) {
                int gap = array.length / 2;
                while (gap > 0) {
5 k- h1 x( X7 y/ N& `) L8 n                        for (int i = gap; i < array.length; i++) {
1 s% Y8 U& U4 \, E                                int index = i - gap;
# l1 ?  l2 T) a5 J                                int temp = array;
: A5 b& o, S7 @# A" W8 ~- z+ L  b                                while (index >= 0 && array[index] > temp) {
) x6 h4 W9 i" R% g  c% A2 _                                        swap(array, index, index + gap);
                                        index -= gap;
                                }
+ t; ?6 c" t, `& f//                                array[index + gap] = temp;
7 a4 S& u" E/ \% [' _/ l; ~                        }
                        gap /= 2;
5 W! k+ C6 \4 @) v" C                        System.out.println(Arrays.toString(array));
                }
+ \5 z1 Y5 Q6 a        }


; q+ E+ t* G5 N        private static void swap(int[] array, int i, int index) {
$ {! ?/ ~' F: f7 U7 x  r                int temp = array;
                array = array[index];
                array[index] = temp;
, F) g2 B0 o. f. L3 {        }
& U! Y9 @( E+ d! P}
1
; X) c! q7 Y) l! A( n2
! e. l/ a/ L$ u; _. c3
4
5
( Q, e9 L  n2 K; D6
7
8
9
10
2 x' ~; u, u+ b$ W' l$ u( _% p11
7 k. t$ S% }5 G7 q. `% t12
13
1 F4 S5 q! k# S' V  {3 t+ r/ m: O14
15
2 M: V+ n5 x( [$ p6 ^8 x16
% d; |8 `- b6 ?+ G5 Q  z17
: d+ r- g, d9 o" J2 O0 N+ q: ~, b18
19
20
21
22
23
24
25
26
  e% M, I! {& s# m27
28
29
30
' ^+ Q. _6 v- S" e选择排序
1 P, ^, M, b1 |简单选择排序
8 W% F+ c7 ~9 F4 q7 r, U$ k* V从未排序的初始数组中寻找最小元素放置首位。
- [5 g# A1 w% v从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
5 k6 @. R# d" v2 e# L4 b时间复杂度为 O ( n 2 ) O(n^2)O(n
, B) a4 B- b5 W# d9 O6 q" |# {2
) 。
2 G7 U# ]2 b  B2 H

代码实现**


public class Solution {
- n+ V$ H5 N/ Y6 r/ s9 V        public static void main(String[] args) {
# W0 i% e2 e9 d; D, W( t* b" C                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
                System.out.println(Arrays.toString(array));
        }


        private static void selectionSort(int[] array) {
: P& Y/ M& m5 j/ ~2 I7 t; S                for (int i = 0; i < array.length; i++) {
" s( c# U. s" f! v; T) ~                        int index = i;
8 I$ ]+ w' c5 h% i' a! o9 {+ |4 b) \                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
; q' F3 ]( [1 l" X6 M; w                                        index = j;
+ U1 J, v1 u! L. r+ f9 b; o  S4 L                                }
& ~/ G+ @, Y5 H  f2 B                        }
                        swap(array, index, i);
0 q; ~5 X5 b* W0 V                }
: j; b' [- Q; Z4 \6 F        }


        private static void swap(int[] array, int index, int i) {
: a1 R- \/ ^$ ]  L8 m- b                int temp = array[index];
% M9 E! c* `$ o! O) t' Q7 h) H                array[index] = array;
                array = temp;
        }
}
# j/ [$ B2 z! O7 j) h+ P. V2 [1
2
3
. w  t: D8 N1 R0 d, u, k4
5
6
7
8
5 m& I$ A: T! m' Q5 h9
10
) Q0 @: D3 d1 X& e11
! Z7 i2 Z: u  [% G/ N, |5 {( Z12
13
14
15
16
17
18
3 b! G3 C. L  \% {( g/ w: I$ B* a19
20
: l4 `& F# B8 H9 Y2 ]  v* h21
* l: d  a, T8 g% ~, @$ e22
4 \2 M4 B' l, V* \$ K$ _+ f5 V23
1 d1 v1 e7 \1 p; V; x( J# c& @24
/ N3 t6 W9 ~8 u" l6 H25
& G% L1 A! C: R% ^1 A堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
" m6 C) C/ X( x2 B
  v% M3 f1 B* N, [3 u
9 m1 s; h, {! V  V5 r代码实现**
9 Z& h" I, g8 `; [8 o4 b
* {/ F: v! F  x
9 h$ |3 [: S1 R  l- k% v5 h+ ^public class Solution {
& l* G% |! L& r        // 建堆
        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
2 h2 \: C. Q, s5 h3 p* u                for (int i = (n - 1) / 2; i >= 0; i--) {
. T" B/ X: G+ w( f1 }" Y                        percolateDown(arr, i, n);
                }
        }
" r* l1 W* r1 W$ e( V        // 插入
        private static void insertHeap(int[] array, int data, int n) {
" L& B8 `; T1 ~' N- J                array[n] = data;
                percolatrUp(array, n);
1 W' h, y9 {1 O* ?4 U8 H        }
1 I$ z: u0 j4 `8 s+ e  ]        // 删除栈顶元素
; D+ }. {0 N- k$ r7 k        private static void deleteHeap(int[] arr, int n) {
" u3 a: ]! e" Y- Y" P8 m. [2 L( K, C- |                arr[0] = arr[n];
                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
, W" J+ G# R. V2 j: [        }
        // 上浮
' F9 p9 B+ p8 z) v& ?8 S        private static void percolatrUp(int[] array, int n) {
                int data = array[n];
                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
( A! r6 c& z2 q                        array[n] = array[father];
                        array[father] = data;
. U( [6 p9 p. j9 ~                        n = father;
6 H' D3 K8 N4 q. O$ X1 m+ p                        father = (n - 1) / 2;
, p# K& B2 ?! _; B2 {                }
, e& {: v% K8 l7 Y+ T( w, g                array[father] = data;
: S! ]) V- B5 Z) V/ h        }
( `. }3 A* [: I0 i        // 下滤
( S8 n# P* v+ ~1 x        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
                int child = 2 * i + 1;
7 x$ W& W+ ^% f. ^) q7 y+ d                // 遍历整个该根结点的子树
                while (child <= n) {
: H- R, x' F% D                        // 定位左右结点小的那一个
, v3 O7 D, z" J+ e+ P                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
                                child += 1;
                        }
                        // 若根结点比子结点小，说明已经是个小堆
! d! x. `; h* p1 R# d8 h                        if (father < arr[child]) {
                                break;
                        }
                        // 互换根结点和子结点
' ?4 t9 L  |" S+ P4 O7 G+ k                        arr = arr[child];
' f- T: c4 G& \                        arr[child] = father;
5 r9 B0 q- Z4 `; q/ I: U                        // 重新定位根结点和子结点
2 }8 F# {6 W5 x2 N4 J8 Z                        i = child;
                        child = i * 2 + 1;
# V. N' S+ C& C9 y2 z$ ?4 `# L2 p                }
6 E: O6 o% m3 m( H5 q/ J7 I        }
1 N; H" d0 m. q$ {   
/ i- {+ d& s5 E5 g) S        public static void main(String[] args) {
$ y7 c  }: }4 k2 h                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
9 U$ ~9 A$ n0 U) o6 E: ?0 K               
                creatHeap(array, array.length - 1);
: v! n7 p# ]* \; f$ u# R+ X                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 2);
                System.out.println(Arrays.toString(array));
               
                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
        }
' w/ Y* q2 w$ b! q; q}
  B! p! F1 |( b2 p; u1
& D1 e7 l2 M8 k8 }3 G# P& A2
8 R# [6 Y7 ^% X; g; W( g& X/ W0 c8 n) P3
4
: S* c1 f8 y& m7 C5
! Y8 H3 S" Q7 ?5 c. u6
4 _8 V: d) g* K, l. A/ v7
: b2 O- Y$ m2 P0 p* h8
9
10
11
12
2 K6 H5 O+ O8 k" Z13
7 Q9 v- ]5 F5 e14
15
+ {5 Q' v4 x4 _16
; Z1 n# i. C9 }, q) K1 `' A- `17
/ P8 X: k, s! `$ t+ t& U! K1 Z) I18
19
20
4 Y3 j$ v: @8 o21
  l$ H2 ~8 P2 ?22
+ c9 J+ ~# k3 `0 D3 F$ S4 y6 G1 k# r23
; g$ ~! S; Z! d' \  K* a: K; s+ Y24
25
* [* j! d. r/ v; T# Q+ d26
4 m# J! y7 T. W) G' D27
28
& i! E9 |) T; ?$ K% q# D% F29
' W6 o* K& D2 P0 Q1 @30
31
32
& c4 G: H& f2 h; T- o33
- r+ z$ F) t' [34
. R* _( H) C* P9 }/ t35
4 A# Y( Q# T# ^- G5 i36
37
* ]  G6 |% a( |! R! Y) _& ~38
7 V8 ^) z+ d1 b39
! u2 q5 t1 W& s3 l6 `" G) @2 B40
0 A" s. j7 i5 w3 l% [$ V2 l7 W41
42
! g+ o7 e6 y; _! V43
44
45
5 `, K% q, X9 C, ]; u46
6 _3 F, j! R2 o. t1 Q- h1 \47
  b$ v& S+ l% N48
/ c# _! i4 h: C3 m49
50
/ Y# U4 n: s) F; C51
52
53
7 j% l+ h% H0 L& K, G0 b$ h54
55
56
57
58
. D+ ~3 P8 g- P' J- u! \; B: h3 h59
60
% x4 t& v! }& _) D1 A' ]+ j* b61
62
, K  K4 d3 H% e- |) N! W' \63
/ P/ f5 ^6 {# i64
, h! l% U. t# i3 {6 C) P65
: |9 Q$ p) T6 y5 f: N0 ]66
+ B# \1 ]; R9 r# V67
+ S% \# E8 x6 E1 w/ [1 M68
7 u$ G* d2 J3 d69
+ s' d: ], x* E0 W7 _! ^70
交换排序
冒泡排序
. r# W$ @& ^5 b  o& O( o1 ]0 C$ t依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
0 W+ X6 \* E- {, Y8 Q在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
+ h; d2 n. H, Z" P) F$ D, N* |最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
3 x+ p% u4 F6 _" e8 s) o7 \3 M ) 。

5 H( ?* L6 ]5 W0 U& a1 N+ o
代码实现
- o+ Z5 }3 y6 Y6 [5 V  y

import java.util.Arrays;
public class Solution {
5 M  I, u; W: b6 K7 J& d       
        private static void bubbleSort(int[] nums) {
+ [+ B2 H, v: ~- C- `- ~% ^                // 循环次数
                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
- g2 f( p- H1 T                                if (nums[j] > nums[j + 1]) {
                                        swap(nums, j, j + 1);
                                }
4 Y2 P/ l; w( _- ^- R7 T/ \                        }
) P* i5 e- i# V; J2 _2 Y                }
7 k1 Y) ]* I6 P- p# c4 l        }

4 w" r: m. J7 z1 }6 E
        private static void swap(int[] nums, int j, int i) {
9 R4 X7 J$ a' ?0 e/ X5 W9 @) s                int temp = nums[j];
                nums[j] = nums;
9 r: y  d, {' S! D                nums= temp;
        }


        public static void main(String[] args) {
- h2 j/ d' q# J                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
# ]  K3 T" z, k1 W4 `' ~2 ?                System.out.println(Arrays.toString(nums));
        }
! `, \5 R: c- S" _}
& l2 s& K0 ^' ]1
2 P% m9 T* v9 d& @* i. k2
8 R" `' U% Q! J3 a, ?3
$ P5 {' M8 D" m2 Z  r- \; a2 y6 p! K4
5
# R! @" t" f% ?/ p6
7
8
9
10
+ v* f- O7 u) \! d( A11
12
0 v+ m+ _9 p3 g8 W! u; }5 |* A13
" m4 x! B8 L  \/ S/ e& t: G14
15
  T6 b7 V; ?2 r3 w16
17
7 s6 h5 W1 D2 o- L18
19
7 H& u& ~" e( V/ }9 m0 t# t! A20
21
22
# ]* |+ [: V" C8 X, Z23
, l1 J- f6 W9 @24
1 R4 K, M2 S1 ?  W" q8 e25
26
& W' Z; C/ ]! @2 Q: p' j27
/ x. M" |9 k, |' ]0 ?, D9 _1 ~快速排序
7 k7 H! h* E; x6 g. p1 y0 I& i, v时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

9 v2 I/ k( N6 x4 c" Z2 w. t
代码实现
- @( j; H; d9 T
/ T1 x5 g) B0 E# z  @
  f' M& {. u; n  ?5 T0 X0 z: spublic class Solution {
( u7 y! J; V; ~& ^5 i$ X/ R/ _       
9 _/ L1 Y+ f. r) o& e        // Median-of-Three Partitioning
) m6 E" I0 O2 X3 J5 N5 i' c% G5 X3 `        public static int selectPivot(int[] array, int left, int right) {
2 L! P. ]( v, t* r2 }8 O, V8 ]                int middle = (left + right) / 2;
( d* I/ h9 w+ Z- m2 I) U0 i5 R( a               
                if (array[middle] > array[right])
, d6 f, ?; v/ @                        swap(array, middle, left);
; Y% ?( z, Z. e                if (array[left] > array[right])
                        swap(array, left, right);
                if (array[middle] > array[left])
                        swap(array, left, middle);
. J/ L$ @4 c2 @2 c               
  ~1 g; w& U& X2 S( Y1 H                return array[left];
        }
       
        public static void sort(int[] array, int left, int right) {
6 i5 K: v1 ~5 w! f# R                if (left >= right)
2 R0 Z: R# I+ f                        return;
                int index = partition(array, left, right);
                sort(array, left, index - 1);
                sort(array, index + 1, right);
    }
       
        public static int partition(int[] array, int left, int right){
$ G2 ?* s, U( G8 i. O        int pivot = selectPivot(array, left, right);
        while(left < right){
; k% G+ {6 X( t6 f1 p            while(left < right && array[right] >= pivot){
2 j( t5 U1 v; |$ A                right--;
) ^/ y% H. T  T3 Y: B: k            }
" Z. C' E* u+ K, g0 T            if (left < right) {
3 q2 Z; d/ A5 I0 s' A! V/ d                array[left++] = array[right];
            }
            while(left < right && array[left] < pivot){
2 Q4 j9 O, s, w                left++;
7 R7 ]/ {8 J- ^( {( z            }
            if (left < right) {
) L5 s5 Y; R6 k/ Z. t- y                array[right--] = array[left];
            }
2 s# P+ G4 `6 ~  h) o6 s# D        }
            array[right] = pivot;
2 V. F4 m0 W  |. Z# b% e; P        return right;
    }


! D" P$ r* @8 O4 l    public static void swap(int[] array, int left, int right){
* ^0 b7 m9 L) N" c            int value = array[left];
            array[left] = array[right];
* D( y/ C. I" b8 C0 b" ?            array[right] = value;
) _6 a! M$ r7 C1 r    }


6 H& b: W% V8 s( [7 [$ P        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                // System.out.println(Arrays.toString(array));
7 [3 |, }8 E  h0 m                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
6 X# U' S% {( {        }
}
/ f# K9 i2 k0 q$ c2 y1
, S9 P1 q8 t8 I4 w2
* r9 m% g* ~$ c3 x! l3
4
5
' X7 V5 k0 w+ o: h6
7
, ?- ]/ J* y, h! @6 I; ~8
0 p- c0 h( ~, m9
7 ~6 ~+ ]/ _, M" n6 w& v1 i10
11
: z2 O  V9 q; j12
13
7 u1 X5 v- P8 G; o% J14
# y# c; M& g3 ?15
" x4 u! y1 B. s- o16
17
18
  ?$ c' W4 E# r2 K) r19
20
21
* ^% I$ N" G/ z22
3 i3 j4 e! S; ?) l0 o0 ]23
24
0 d, `& c' _' Q8 `25
26
27
28
29
30
, n4 c& {/ _3 m31
32
33
34
6 I. R# [# F, p) f' l35
+ A, {  \( v4 b3 }# A, C1 j, S! i36
37
38
# K2 Q: e2 B$ V39
40
41
) P, `$ r7 _9 p4 f' D42
$ e, N4 K% z3 C% m8 k3 V4 C% X43
% w0 s: [  z4 \* g7 R44
& ~  C. ^6 M* ^4 T. G4 A" n9 \45
46
, u4 l; e  U% G47
, Y) V9 c+ M' C* I* R2 @& d4 {- z48
( A- A; k0 D2 ~49
8 r0 ~! d9 ~. `: x6 W/ h$ @% ?6 o50
* Z( m, k0 X) f# r3 _51
52
# Q# V5 N, ^9 P+ P" V53
54
55
. H" E+ z/ R) K8 e56
57
; W0 I1 h+ U& y$ K归并排序
! u* L9 A$ s- G% c6 n6 I: e2 S将长序列从中间分成两个子序列。
对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
. V/ f3 }' p+ w* S5 t* W: ~& ?' O平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
: N& U' D! f% @2 ^0 r1 [
3 `: H8 d  [) I6 s' B
2 O& {. ~. C, d3 F9 `, b- N. w代码实现**
1 ?7 ~5 v; [6 }5 ?. O5 k
6 g3 l- i1 G# o+ h# v9 i
public class Solution {
        public static void main(String[] args) {
+ X( D( r5 r( v! H1 ]3 W7 |                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
9 M( Y) X  D' \% @& y6 u6 r                int[] arr = MergeSort(array);
* ]3 K1 h8 Z  B4 R                System.out.println(Arrays.toString(arr));
        }


- |- _* r1 [# ]5 A' ?9 ?+ U; r9 V) ]        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
3 M1 z$ ]# K6 `2 K1 u$ k( |                        return array;
( p0 ]" i) \$ }9 e# F; Q                int middle = array.length / 2;
7 X8 W5 n: `1 p- q; q* `: q& }                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
/ z8 Y0 `# J2 X! p2 }) }6 q. E                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }


        private static int[] merge(int[] leftArray, int[] rightArray) {
/ |, x$ Z  X* {$ ~$ w5 u/ v# J; u$ Z                int[] result = new int[leftArray.length + rightArray.length];
                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
% `* m! K. T4 N* d+ I; |) u                        if (i >= leftArray.length) {
                                result[index] = rightArray[j++];
4 `; |- N# v" q% L9 B# {8 \                        } else if (j >= rightArray.length) {
( }1 T( J: ^% t9 _* c* P                                result[index] = leftArray[i++];
% d4 p. ~& }5 Y' w# J                        } else if (leftArray > rightArray[j]) {
/ \9 L: [" x! X# u" o                                result[index] = rightArray[j++];
                        } else {
                                result[index] = leftArray[i++];
9 B3 c, ~- b$ Z" k2 }# d, a                        }
; I/ n& E2 K3 ^  ]0 t- \, \                }
                return result;
        }
* K1 F* r0 p% I}


1
& T$ R" k5 x& B- Z2
4 ]7 t) g$ r% {4 e5 r1 P0 Y* U) \3
) Q$ @; l2 e5 ]) i8 h4
2 S! g3 k& _9 w2 s  j7 H1 r1 \, [  F  u5
6
7
' T* W% M0 i& w6 V* x; I4 i8 @8
9
& b% V4 W( Z# T& C9 I% f10
11
12
13
( k" Q: N5 U6 r# T* h; U. b+ e/ j" a14
15
16
17
18
# Q: T( {  p3 g' f7 X19
$ \/ z  q6 O7 `; \20
/ m# `. ^5 I/ {- T8 S6 j5 G$ l( I( k5 o21
/ U1 Q4 k" W2 C22
% R* R  c! v) T$ P" j- M& V' b23
24
  f+ M( F! p# q! _. c25
26
27
$ L3 v! Z8 S( R2 T! b28
. k+ K7 ~6 j* X+ Z# x29
30
' j, W7 t; n& W. _1 O& \31
2 ]" @) j* d- [32
) b: B; l% X: t) u33
基数排序
% u0 {# h' n8 M$ n找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
/ X5 j8 J. G6 G8 N0 d( e% o4 t将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
4 v/ w8 a1 e: D8 s3 T% u8 a
/ _7 P! U! v5 d( [* A' k+ R4 e. }6 j$ h
代码实现**
6 b# W7 `5 o- J3 M9 G4 H# K

5 B' h, C2 X4 c! \: C5 K: Y6 xpublic class RadixSort {
( v$ @4 _' n- T' l8 ]

        public static void main(String[] args) {
                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
                int[] arr = radixSort(array);
: T; p0 b  R5 X2 d/ S                System.out.println(Arrays.toString(arr));
/ R" H  s0 h/ o$ |        }
& y: A4 L$ ]" q# M- Y  z

        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
8 Z2 l. E4 I' _, f2 x! R- e2 G+ _                        return array;
                }
- ~9 c- j, H8 D# G1 i  `                // 根据最大值找到最大位数
                int max = 0;
                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
                }
1 v6 L! f- T; Q. L# ?' |               
3 L' R) r" i2 B1 k7 R/ \+ d4 l                int maxDigit = 0;
                while (max != 0) {
                        max /= 10;
                        maxDigit++;
                }
               
2 a9 f5 L) w$ I6 j) c                // 第一维: 0~9
. B3 X- P: r1 {% M                int[][] radix = new int[10][array.length];
% `5 Z9 ], @: H                // 该位为 i 的元素个数
; |( N# M- M; {9 n                int[] count = new int[10];
; G1 t2 Y( p, q2 p               
                int m = 1;
+ Q& a" H2 `- z. ~- j, m* F7 a                int n = 1;
+ }% S/ r; O+ ]: X               
4 E; V5 U& S: v" j' b9 k% A                while (m <= maxDigit) {
: Y$ d( t4 Q5 W& k. N1 q                        for (int i = 0; i < array.length; i++) {
- x* y/ I8 O# h: u* D+ X                                int lsd = (array / n) % 10;
. \% T  m! n; K4 E6 r+ S                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
                        }
! S' r& d( a) i+ H( f                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
4 _1 G3 k7 R( @8 B% |0 F3 x                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
+ R! x" J9 s- ?" o7 u( ~$ `& q                                        }
                                }
8 ]. ]! t6 V! X, R, |2 t                                count = 0;
                        }
4 @. Q8 E5 [) P" Y8 Z                        n *= 10;
                        m++;
/ b' z" n) N% h3 q1 O# O) I                }
                return array;
        }


}
: p9 P7 ~+ r0 N& ?: _* ~6 F1
" F0 g6 m( F% O: v# H& ~' o" C2
( i/ `* O1 E  b3 T: J+ U4 l( b, L3
5 J9 V! I9 L+ y) }3 `+ W2 G4
5
0 n  b* Q, k4 N7 U* b( Q/ Z6
7
8
3 c% {: a9 i3 f, w6 i9
6 D- t1 H# s- M/ S+ y! _, @/ @10
11
! y" _3 `3 [; D8 [$ J5 D12
- U9 |, K: L! k13
! Y* v" J/ J% K" {14
& D6 R! g2 ?# g% R$ H2 \$ U/ R7 D: u2 a15
16
: o& x( F' Q5 S9 E3 G17
18
3 g2 V3 _- _6 F/ K" \19
20
9 }2 B  `  {2 Y9 t/ O21
22
' L3 X) N5 A- _2 ]" V! n' g% I23
24
! R' ]. |% ]1 [# T25
26
27
8 R2 t4 ?( ~3 h# O- k28
, B  J! B& i7 T29
30
/ w$ D9 ]0 Z  s- @31
32
33
34
35
; }2 r4 |1 s# A36
37
/ u! M" d! ?. v2 D0 i" u- ?) f38
; o) ]: G5 u6 t' ~# y& s0 c" e39
40
3 x$ X1 g2 }/ z& h41
42
43
6 W4 I, L! W3 s" R# ?, h! X44
0 y/ J- I/ _+ N- A9 O8 R5 b% `# x45
46
47
2 s) Z8 ~5 J7 {3 [/ g- q  t: }48
9 r2 m. `6 j+ Y/ r  i5 Z6 S49
6 `1 s3 n# h) N7 `, O% b* g" R50
51
52
53
计数排序
9 b0 F2 l) T! d. t找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
& F9 I( K3 u5 d8 w9 C" ?' o  v时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。

- ]. t) k/ z* D% }1 d* ^
代码实现

; s1 j4 l; M( k0 p7 d
public class Solution {
) u9 e( H: f9 }- I1 P" i% b" y6 C) v
1 D2 o; h5 _4 ]+ L6 q$ I
        public static void main(String[] args) {
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
; d2 C% N' I/ q# p7 D9 ]6 G                int[] arr = countSort(array);
, L% j% Q4 m+ g4 c4 ]1 n                System.out.println(Arrays.toString(arr));
        }

# w4 \( b4 J. ?: y" A2 l7 }
* N  Y; Y. v8 q* a        private static int[] countSort(int[] array) {
3 }  c) c& H% M                if (array.length == 0)
                        return array;
               
                int min = array[0], max = array[0];
               
9 D! c% K  `( s, c8 D" l                for (int i = 0; i < array.length; i++) {
9 L9 Q& p! R* p8 |3 z0 _4 @                        if (min > array) {
2 U) K. e; u! ?7 F& v4 f                                min = array;
                        }
% X. r: h- x6 E# ]9 |; U, m  U                        if (max < array) {
                                max = array;
8 d- n! |* z/ m. G* o                        }
                }
$ S; L6 [8 h/ b# _% ?3 O/ ~               
                int[] count = new int[max - min + 1];
0 N, ?& A; v9 P8 H, Z/ ?               
' N" z) ]' }& v1 Z! S( [$ x                for (int i = 0; i < array.length; i++) {
+ g! o! \" M! V8 R- V' D% y: c1 s                        count[array - min]++;
                }
6 U0 T- |& X' }2 |9 z/ X! g: N- ]               
7 o- K& G6 B# g7 Q7 j2 z                int i = 0;
                int index = 0;
                while (index < array.length) {
                        if (count != 0) {
                                array[index] = i + min;
  r  y' d, T0 b1 x) [# J! J* N                                count--;
" }) |8 ?' P- N6 e9 O                                index++;
  a$ P8 b  d( K3 X" N                        } else {
/ _, @* L) A, ?3 L  N                                i++;
                        }
4 N5 a, _/ e4 y& q" ~$ |                }
  o$ [8 |$ @' J! t! |# s( T) ?/ j                return array;
- V, f2 L$ @. J- U0 f. f5 ?$ H4 i        }
: H. w; d% C+ T. T# }8 e       
}
1
$ i" \# t- G  {* z* S2
3
4
5
6
$ V" r+ P$ y/ ^7 O1 t2 H7
4 r0 q- O! A- P6 j8
8 O% K' H# z9 ?6 N9
  `9 j/ c5 b# V- g- }10
( ?  \' O, A3 s! a, u5 y11
4 i2 Z$ d+ _, k& @. D/ r12
13
14
! O- @8 m" P+ i" u( `15
16
) O! q2 w" A; @. a17
18
19
20
21
" `3 w3 w5 N% I22
23
24
25
! o: a5 U  [8 Y26
; H4 W8 j) N) e) l27
28
- M" c- n3 }. x3 d  B  q4 o29
30
31
32
33
5 ^- j; e# w" P7 k34
35
36
. I# Y- k# y- s. T7 @# h. `37
6 y, _, e+ t1 k5 J  `) w# x' B: t38
) Z; S& a+ ~1 A* A39
3 d7 T* J# m3 u: R2 e; H, W40
9 g& f1 P; O; m/ a# O: r41
( n& r' [$ l- a! r* c5 j42
1 B6 h# `; \+ s: |; y9 [: w43
* `% s4 ~* ]) i+ u2 X5 F) \44
4 x! A8 y* {5 o3 f桶排序
————————————————
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
8 f- U  K0 U3 A7 G* v原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
( A& y  {3 g! u2 w, ~