十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）
) g; S! {+ C; {
十大排序算法（Java实现）
5 z- j4 B9 v7 X# c排序算法框架
) @# k: M3 K5 }2 ]: S% `) X' I排序算法性质
& b( I& h" J, B4 _插入排序
) _, _# r; {% j2 `% G# Q5 u直接插入排序
5 R2 t. R4 g: o: G6 T希尔排序
' `" Y4 t, I; p% o2 {- e! M) E5 o选择排序
/ U3 B$ h/ w; `0 u简单选择排序
堆排序
交换排序
0 k( F$ P9 H* J/ ~冒泡排序
* r" A& @* s. G2 f5 s) T快速排序
' g- P8 P& R6 t/ V5 l归并排序
$ S5 k. l3 X8 V. t8 X  x0 G基数排序
( i4 E; U, @# n$ y' y, t计数排序
桶排序
更多文章点击 >> 这里
2 \$ i) `  ?7 P/ T6 ~1 h

# F4 k; S* S1 S1 p排序算法框架
4 v; U) P) w; f

/ ~% \# D& i# a7 G
; n9 \% d; L; }1 @2 ]5 Y) W  H" R. {
排序算法性质
! U. q; a6 ]- J1 t" J! T. p+ a
& H( f2 d$ M, f
: i0 }8 P, h/ L, h+ G) F  ^, Z

插入排序
. R7 N* }& V! i4 \7 l, ]直接插入排序
3 w/ V: V# b! }# t% `4 y从第一个元素开始，认为该元素是已排序的。
取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
# b6 u* N! d4 F) m; n+ q9 t( o最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
" w1 A5 [1 ]. b/ d2
) 。


代码实现

! ~' c5 `& ^# s3 V
* ]5 A: u/ N8 [! ]; z- gpublic class Solution {
2 ~( v  ^+ Z. S0 Z# R        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
  o; v4 X% S6 c1 F* _; W                insertSort(array);
                System.out.println(Arrays.toString(array));
        }

! J. Z/ d# V) d2 i, |
        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
* }6 k8 [2 X8 V8 H# o) K2 D                        int index = i;
  h" t3 x( [' b7 I) W1 x                        while(index >= 0 && array[index] > data) {
; j8 ]" G: ]" _8 d* Z2 J                                array[index + 1] = array[index];
3 o8 S# E) k. L5 x: S                                index--;
  W5 h4 I  H' p. R% w' F                        }
                        array[index + 1] = data;
$ N  K% ~4 p) n$ n                }
- g# f! J& c) o0 K6 s. g9 b        }
}
5 n: w% T. t! n+ `" t1 O( J1
9 s7 k  T/ g( h5 Y0 @3 o2
& }- z, X5 l5 J3 e; e. J* n4 I3
1 }7 w' ?8 B+ Z' F* V4
5
' l/ o# v8 D$ A9 x5 L6 @6
7
5 C5 ~3 u; J0 S' B7 O# `- [, x0 R8
9
9 X  t  a$ r) \6 N& i* Q3 z10
# t+ _/ e3 P: Z' j3 I9 V8 B6 }11
! q3 V; ^3 R, d- _12
13
14
% F8 P6 d* p) F5 r15
& q( ^0 @( ~1 _! }/ q! F& P5 A16
, @9 r3 q1 y0 \  Y; B3 U# Z' f8 m3 |17
: g0 L/ B! @+ F" s18
' b( x6 Z% p! v8 O3 g19
希尔排序


时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
$ `/ }- M% P1 J! N9 L% O  d* P

# Y- ^* E$ W4 I8 J4 Q4 X  C3 M代码实现
' y! r* E0 s: C5 L7 d$ |1 ?6 P# x
% X6 h9 J2 ^' d5 @5 X
# [" P4 X! I1 i4 rpublic class Solution {
+ F$ a2 ]6 x* r) E        public static void main(String[] args) {
0 n# T/ y/ \* h5 m) V4 V0 Q                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
8 q; D, _2 b5 k                shellSort(array);
                System.out.println(Arrays.toString(array));
        }

* G( q$ M+ L5 L1 W6 O2 R4 v) c
$ _7 [  ?9 z/ r% e        private static void shellSort(int[] array) {
                int gap = array.length / 2;
% M# \! z) P6 u" R                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
                                int index = i - gap;
                                int temp = array;
1 j0 O* H& s* C# W; Q2 n- X                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
  ^; v0 k5 R! Z7 l                                        index -= gap;
0 H2 [% o6 q# W0 q! d/ l! ?* u                                }
//                                array[index + gap] = temp;
. U+ _9 f# u1 }/ y                        }
4 S5 g* U5 D$ \6 x1 R6 _                        gap /= 2;
                        System.out.println(Arrays.toString(array));
                }
" L. k- Q. a/ C# t5 a( e$ H        }
. L; q+ d3 E# o# L. j2 @$ Q) b

( `$ V: N& ]" I0 k* {        private static void swap(int[] array, int i, int index) {
# c2 }3 ?& B  w, p                int temp = array;
: m: m8 Y& ]- ~8 V                array = array[index];
                array[index] = temp;
        }
5 }' g3 f5 V$ Y2 i- k, L}
! \8 l# P# k3 q) _% N1
5 z& G+ i3 A6 d$ @. @2
3
4
% t7 v0 ^3 W5 r4 @0 F  B5
8 n& a& {# z" W% R* D) A- D4 v6
" F' F- R: E- \8 O2 `& E: f7
' E/ T5 P8 X7 y6 Q8
9
10
4 k( v; _' m3 G11
12
( h- \6 S8 i. _$ m6 _/ c4 o13
14
7 c5 A8 g8 o& y3 V3 z/ z15
16
0 s- H. O, S% _8 M( v4 O! I17
. A( i3 V$ Z  A! L3 P18
( U+ d5 b, S( T/ \+ [+ w19
20
" O( `/ k0 ?) M2 `1 o; T' x% U21
22
23
. \2 ?5 y5 S" X) u" h( r24
. b! N/ g, j5 h25
26
. b9 T8 M% i; O9 ?27
. R. A" H3 X+ e. ]# u28
' [$ ]8 q/ s& w$ s29
30
$ l! Q. R& R( A/ f选择排序
简单选择排序
从未排序的初始数组中寻找最小元素放置首位。
从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
时间复杂度为 O ( n 2 ) O(n^2)O(n
& D* W' i- v" D) v0 L5 e2
3 X0 j" L& B/ w! p9 R& b: ? ) 。

% z& t$ B7 K$ `! o
2 O, \$ ?6 c$ _1 |代码实现**
; x5 y( K0 Y/ e" a8 _+ B) H

public class Solution {
        public static void main(String[] args) {
% z0 B; r. Y% B                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
                System.out.println(Arrays.toString(array));
& u* I" J. f6 ?6 O2 E        }

3 k' D* l" t4 x' z4 q+ e
        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
                        int index = i;
; k% v( I" y5 M: t9 D                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
                                        index = j;
5 T! z: U: t; m: |: ^% h6 G) o                                }
# F0 B: g; W4 Y( R, h                        }
% U$ C6 }, O- X4 R                        swap(array, index, i);
% D' @* T; D; D; b. Y  W                }
1 S+ m6 D7 `; t$ ?9 c: l0 t) p1 m1 _4 v        }
4 a6 L- P; T) F1 k1 c/ j. H
+ ~5 p1 |8 ^1 \$ m5 @) j
        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
2 ]% r0 q& l$ Q* V4 X9 G3 y) h                array[index] = array;
! V' Z* P$ M  {6 m                array = temp;
4 \, R2 V* C; O9 p0 e, e        }
4 X( q) c  W  w* K" H}
1
: {$ l$ |6 n8 ]# _2 f- ~4 M/ o2
3 M! k* Q) g" \* e1 l3
; `0 t$ z, ]% x4
( h% q. l0 e6 d: I( `5
# E$ @* y5 E0 V. K  R1 W/ J6
7
8
9
10
11
12
13
3 _: c% ^4 W7 C+ ?  m1 v2 ]6 o14
15
16
17
4 k6 w& S6 P9 i* g18
19
20
21
22
23
24
0 O! L/ J: c* w, f# C  n0 {25
堆排序
6 J% K6 h$ f% m6 N时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现**


public class Solution {
- a4 g8 \; ?: }5 C% m6 N5 U        // 建堆
" o5 Z" R  a! v1 q0 k+ ?% G        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
. |8 J4 T& [9 J1 U- V9 B5 o9 g" G: B                for (int i = (n - 1) / 2; i >= 0; i--) {
) K! P/ ]! k1 f& A, k                        percolateDown(arr, i, n);
                }
3 V1 q5 ~# L/ {2 i        }
        // 插入
        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
0 z& }! s9 K' }$ K; W0 l" L                percolatrUp(array, n);
2 N& U4 B: G1 \# J7 Q" b        }
: j" {1 e# y' Z        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
5 r% V1 ~/ |) B9 S- ~, _4 R' N                arr[0] = arr[n];
( B- N7 a) e3 O+ G3 A6 p' J8 a                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
- y5 M6 q* K; |- z6 s; y! a4 R0 n        }
+ S1 \8 J2 P& F# u1 I1 q        // 上浮
        private static void percolatrUp(int[] array, int n) {
4 }$ m: {! P. k                int data = array[n];
                int father = (n - 1) / 2;
' [' U! Q( M7 |" p: e" F                while (data < array[father] && father >= 0) {
1 d, W  i. B3 U8 ?" W  ~& \4 U- A                        array[n] = array[father];
                        array[father] = data;
                        n = father;
                        father = (n - 1) / 2;
( N/ `7 c; |3 ?  x                }
                array[father] = data;
        }
        // 下滤
9 a3 i$ F* D( x3 A        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
                int child = 2 * i + 1;
                // 遍历整个该根结点的子树
                while (child <= n) {
' Z- }% _: O- q  N                        // 定位左右结点小的那一个
                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
                                child += 1;
$ Q3 g( P2 z; l$ u% L* u5 N                        }
+ B' P5 M+ Z5 P9 }% }                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
! n; W" {/ Z) ?                                break;
. z1 ~1 H& k+ a# ~                        }
) Q/ I7 n' r) G" p) L                        // 互换根结点和子结点
7 l; Q* ^* f& R. Y) R0 s9 P                        arr = arr[child];
                        arr[child] = father;
                        // 重新定位根结点和子结点
7 d) ~. H) h3 S' {! k# _! `                        i = child;
                        child = i * 2 + 1;
                }
) E# K) k7 H. h% y        }
   
        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
2 M9 M( `& h8 X8 G' Z" B, k9 ~& ~                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
/ b, O4 k+ M% v7 ]( D$ ?               
                deleteHeap(array, array.length - 2);
                System.out.println(Arrays.toString(array));
               
                insertHeap(array, 3, array.length - 2);
: B- I) G' a3 q6 V3 E                System.out.println(Arrays.toString(array));
        }
: w8 i* H6 _$ ~2 I! X( y}
1
% x  j& C' W4 Y; c" A2
& m. ?$ k; Y6 h6 e8 |3
/ ^, Z- U5 H6 h+ ~) R% a/ x+ B4
5
4 M8 ~% t* p1 [/ {4 E/ V+ B5 z6
7
4 W% }! E7 d; ~$ n/ ~* J4 t# J6 J8
! g+ c2 I- e# b9
3 U. l0 ~0 }) n+ e. J9 H10
11
12
13
+ S1 T3 ]" \: ?) M, G6 J. }8 I14
15
/ Z* E1 Q! J! Z+ k* H: q% ]16
' h* x+ s0 `( r+ L17
6 q4 |3 i: n9 D8 J: B: I18
% _( q5 w4 Y7 y: P% _1 {+ W19
4 s- b2 m" E! z0 T  p20
! f; j" m& n# u" W$ C& O1 D21
22
23
24
25
( Q8 M% O8 V, H* X- b9 T* y26
27
28
29
5 o, A* h& r% g) p" `( ?: u' r- X30
31
32
# Y- y" J- v  r# f33
7 W$ r  D$ a5 ?5 K0 L8 c# S34
35
( J( o5 B# X; \36
37
& z+ S8 n9 h& d2 k9 k& ~38
39
( u: E4 Z, k9 U% m! B40
2 Q1 ?$ ?% O$ ]& ?& n41
42
43
44
45
, ^3 S6 t" n5 C7 `6 {2 D46
47
48
49
50
51
3 \3 J2 p- ?- o( ^8 u) W* \& u2 f52
53
$ ?, S$ y- `0 i3 m6 [) P. i* M54
& C  d1 O7 |8 C/ z" ^" G' V55
56
57
58
# |' H+ n  F" w3 y  i59
$ Y5 C0 W5 W  {- N8 z& o60
61
62
63
+ [" G+ R) s" X1 A$ O, l7 g: q64
: ]! c+ w6 g$ e* t65
! _7 ?2 x) q0 r$ ~  J$ k: J0 z66
! F! X6 b! E  l# `67
" b/ x7 k4 B8 P: H( r* o- _) ^68
6 X5 |+ a5 d7 h& ~69
4 z- U0 x$ A' m& @: q0 U70
7 K8 a. E# p  p) O% S- h- L交换排序
7 i: X! W+ h( V7 c( F冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
. }. ?: T, H8 s' q4 c0 L0 Y  r在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。

$ _+ h% o0 h6 Q! I4 J* h
代码实现

$ k5 a  d* D. s/ y& n$ v% W
import java.util.Arrays;
  P  @( d+ b* gpublic class Solution {
. ~3 p8 U+ J( N0 r  Y  H7 {       
        private static void bubbleSort(int[] nums) {
                // 循环次数
, Q8 o; g4 j; |' i+ e3 |5 \                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
$ Z' j0 [: ~* [: n% O3 t* N                                if (nums[j] > nums[j + 1]) {
                                        swap(nums, j, j + 1);
                                }
                        }
                }
        }


        private static void swap(int[] nums, int j, int i) {
- Z% k; g! F( f! b7 A9 p5 S                int temp = nums[j];
; o$ H" O2 m  r3 H. N  ~                nums[j] = nums;
/ B5 Z+ m- c. |9 z0 i6 t                nums= temp;
6 C& q+ {4 B" C# f7 s# G        }

) t: |+ O- W! N, \  U; Z
        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
        }
}
1
/ q( ]& [/ [; z* y2
. k. _" x( J( W& L& i3
" s. z, v1 `) N3 k: e( H# o6 s* V6 {4
) q% B2 f$ s& J5
9 |( r. m- g2 z+ N! Z# ~6
, S- k. d  g  S& l: {; W& p7 @) R/ b0 l7
8
9
* p  D0 e/ f0 l& B10
11
. n( `, U4 f3 ?. a# M& F12
13
+ I" E; m4 d" D, Z3 u+ x- r' z( p* i14
% W$ |/ v$ o% \4 `: A7 _15
16
17
# Z; K3 ^- h! W! I$ y, i: n18
6 p; L3 J+ _+ X- e5 u; P19
4 @5 o6 c) ?# H7 J4 u, J, N20
% F' p' B' i  Q( t6 ]& I* m21
* _5 e8 O  p% A/ O& z" S6 U0 [$ `) i22
23
24
9 ~6 `1 h* K" T7 x8 X5 y+ F25
! R* A+ j" d1 V" k- E/ j26
# t( c) q9 r: Z+ m27
& m' U: k" K+ l  f快速排序
2 W, U; ?5 d. s& t3 }时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现
) Z9 e/ M/ b9 w. D. ]

( E" y& b  v! X& Xpublic class Solution {
       
' o6 G0 z3 Q5 X1 u; G' b+ U        // Median-of-Three Partitioning
        public static int selectPivot(int[] array, int left, int right) {
                int middle = (left + right) / 2;
               
                if (array[middle] > array[right])
7 a' p& I2 J3 k, S+ y- j                        swap(array, middle, left);
                if (array[left] > array[right])
                        swap(array, left, right);
/ M7 L( v' {9 ]( Y4 G                if (array[middle] > array[left])
! v5 q% v0 G7 h3 Q  B' _+ o" x                        swap(array, left, middle);
8 Q9 L( O0 {- Z' `- [5 }               
                return array[left];
, ]& T  y8 ^1 W1 M9 U* ]' P4 @: y( Q        }
       
6 r* r1 m& g- u$ h        public static void sort(int[] array, int left, int right) {
                if (left >= right)
0 R# a0 x. P1 G9 K0 e                        return;
                int index = partition(array, left, right);
$ h1 ^7 J; {  N" Y' l                sort(array, left, index - 1);
                sort(array, index + 1, right);
+ l# m6 f. K9 S    }
% [9 B; _" t1 T       
        public static int partition(int[] array, int left, int right){
3 b( `5 _+ U2 e( u3 ]        int pivot = selectPivot(array, left, right);
        while(left < right){
; s' v$ i5 B8 V; I( A) O/ K            while(left < right && array[right] >= pivot){
                right--;
. s+ Z; W2 {% S3 \# Y, k            }
# c$ L, r; A- o& w; W- N            if (left < right) {
                array[left++] = array[right];
            }
* H$ B0 @3 ~* S) h            while(left < right && array[left] < pivot){
1 n2 d8 `: S$ M7 h* `$ H  R                left++;
" V5 X5 e5 u3 ]0 x            }
            if (left < right) {
                array[right--] = array[left];
  B; t& I2 n7 i( l            }
        }
( X8 f* _( k% ]- _1 h* {            array[right] = pivot;
7 |: L0 a9 i& }( \! Y2 t        return right;
, m! }* g$ K) @$ R0 u: X    }


    public static void swap(int[] array, int left, int right){
            int value = array[left];
5 ^3 F9 o8 g& y& A/ b! }            array[left] = array[right];
" H" h& u; @! e/ h  w            array[right] = value;
2 k  ^1 _4 @/ Y/ J9 J9 H    }

& c' s* Z7 f0 ~# H) Q& r
        public static void main(String[] args) {
' M3 h  m4 K+ f/ J; }2 p4 }6 M+ [4 @                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                // System.out.println(Arrays.toString(array));
                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
        }
}
+ U$ o3 ^" {' R$ e4 G) p1
/ y$ R. o- f3 n  y2
3
4
5
0 J& T7 J* c9 z$ u; e" w) ]6
" y; B. f2 `4 u* {$ I9 `7
8
9
10
11
12
13
14
15
16
2 L" `3 _& j1 q/ W- ]$ [17
18
0 `2 y8 t* t7 I+ A19
/ k% p8 U3 f1 G! y20
21
2 `1 X" y1 R: p4 m9 `22
) v/ T) i% h% ?0 G) k23
9 j2 O" C: V; y- u8 }- j24
25
26
27
( @4 T' u7 {) N- q28
29
30
; F0 Q# b! t; P' `  K) `31
32
, z3 D' o+ B/ M1 P6 r2 T33
34
35
) `) U% V! c$ Z: Y36
37
: ~. H2 A) b* k0 C5 J7 l* u38
+ E* A. J- v# u- u39
- p# t, f# l2 b4 v, o40
4 l3 t% t: e/ p5 c2 I41
42
43
44
* I; K- T9 I& m/ c% ^8 a; W45
, ^3 F/ n1 h+ n) a46
" }: O9 j. L* Q  J" [: x# `47
. Z( X4 k( Y" P" s  |6 Y48
$ m% C+ p" `- B) K& m49
$ G9 ~4 y: w: G  x2 j6 j8 ~50
& j5 e% ]4 G2 y51
52
53
- o( {& V/ @6 P+ L% P, h  o, M4 \54
3 _4 e& P8 {2 w8 m55
56
9 v1 m' R- n. {: n' X! n57
) {1 G0 m# E8 @+ s3 v! n9 Q7 B7 @归并排序
将长序列从中间分成两个子序列。
. y; M, E$ q- b) S对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
3 c* u: E; T  c: T! k6 G平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

7 k2 k; `9 F6 h( ~
' l$ X1 k1 V" \8 X6 I代码实现**

' u3 ]  n* R' k: a$ o7 p
public class Solution {
% P# v- C  X1 S% e% X$ W8 Z: _0 w        public static void main(String[] args) {
8 j$ f$ F; `  A& \& j( A8 \: R( b                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                int[] arr = MergeSort(array);
7 ^6 `& T# t/ @& o9 G3 Q% y                System.out.println(Arrays.toString(arr));
9 N9 X! ]! k5 j( R3 G: B! j        }
3 q- X" M% E/ V0 }' E
; L; W; \, D+ h3 q4 a4 S9 N
# W. {' d/ h8 W* U        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
- ~7 w$ X6 W2 J* t                        return array;
/ k# z. z+ W6 X8 s0 d                int middle = array.length / 2;
                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
1 d+ @( z8 z  o" G( ]                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }


! e$ _. B5 |6 Y; v: Z* z9 e        private static int[] merge(int[] leftArray, int[] rightArray) {
+ A3 M4 V) x. `7 N# B5 F                int[] result = new int[leftArray.length + rightArray.length];
9 t+ y: i7 T5 N& @2 q9 t                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
5 k6 Z& s- g' q1 K9 o. K) g5 R1 a                        if (i >= leftArray.length) {
$ O7 P0 x# s; T                                result[index] = rightArray[j++];
$ k- \: g& c) h3 P" h: x                        } else if (j >= rightArray.length) {
* _! v( {! }" `+ P                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
/ a. C; ^  G3 O2 M7 O                                result[index] = rightArray[j++];
; }, m$ P" x# T1 T6 l3 r9 N                        } else {
                                result[index] = leftArray[i++];
  ~) A2 _" B  ~9 O: |& K+ V$ [; J                        }
                }
                return result;
        }
}


1
( V! T* h% q9 P4 S2
3
- T# ~7 I0 {/ R# V9 d; P4
5
# `* I: }6 V. ?( s' w) Z6
6 i1 z; Q) h5 r0 h4 e7
1 A0 Q- ~  m% i3 H2 `8
1 Y+ j, S" Z- }3 a9
9 b: A! j; c  x10
  {. U( ~$ G* `11
' k$ d9 d  e7 W4 P' `8 v12
13
14
- `( e  _  \: S: y4 Q, J; d15
' q( e. j" Q/ G16
17
18
19
* j2 m& O5 M' u3 {20
/ j5 A& x- G. a6 O! h21
22
- R9 X2 n3 q% E/ S% {23
24
25
2 Q, P3 m) G) _1 K9 _26
# x! v6 s' f. D. K3 {1 i* V27
7 p+ H. ]5 s( D3 Z% N9 D5 R& ]0 s28
29
30
5 V: e0 r  ?7 m" Z31
32
1 R- k: Q3 H2 {; ?  @33
0 D* Q6 |+ @$ s基数排序
找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
3 W, R2 S4 ?& w* f: G* ?* ]1 h将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
+ g# z$ N' T& N" S' d时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。


: n- z- t$ t& y4 X4 f0 P8 G' [. |代码实现**
3 e& K* e. ^8 @1 Y" H
' e4 ~* p7 ]8 P2 Y% p: x! e0 V
( X4 u) P' F8 b/ [public class RadixSort {
+ z! Q  d5 S. L( O" |5 S
" v" \/ N8 j: r; K
        public static void main(String[] args) {
                int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
* G! w8 J1 O: ?8 J* p                int[] arr = radixSort(array);
                System.out.println(Arrays.toString(arr));
  I6 e6 ?( K" S; n2 Y; j' D' X) p        }
% X8 i5 n5 L3 y' O5 ^
) R  q* G% e/ I( B  }
        private static int[] radixSort(int[] array) {
; N* H1 J' H$ i0 h# [* l% y                if (array == null || array.length < 2) {
                        return array;
                }
9 ]4 ]% f+ R. q2 ^                // 根据最大值找到最大位数
                int max = 0;
7 T; g7 y) ?$ e! A8 F" B                for (int i = 0; i < array.length; i++) {
+ F! {7 B' ?. p7 W" z                        max = Math.max(max, array);
                }
' d. r0 C* d$ E+ |4 w               
5 J% t7 A% i) ?5 F- o                int maxDigit = 0;
7 K9 ]2 l) z: T  r6 n3 R# @8 @                while (max != 0) {
                        max /= 10;
                        maxDigit++;
                }
. B3 x0 E& f$ |& ]               
3 z' p2 S+ u( [! b- Q9 |6 o                // 第一维: 0~9
! I3 x6 n% k, o/ ]. s                int[][] radix = new int[10][array.length];
" Y& {. y2 j# r; E                // 该位为 i 的元素个数
                int[] count = new int[10];
/ B( `! W# z+ c               
                int m = 1;
                int n = 1;
6 ]5 l/ ]$ K: v# }5 o  t3 ^               
                while (m <= maxDigit) {
/ P7 [7 I7 }7 w3 b* U                        for (int i = 0; i < array.length; i++) {
7 C# w1 Q% G3 r/ ?0 r8 a7 P                                int lsd = (array / n) % 10;
# r4 e% c& l' D) g2 x) F9 e. e! w                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
$ T1 Q/ Q6 v2 N. |                        }
                        for (int i = 0, k = 0; i < 10; i++) {
) k# u! E8 x, I4 j5 p/ T0 K                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
- h( f" D5 z3 W6 \* ~# I! V9 p                                                array[k++] = radix[j];
5 k& U/ W7 j& e/ N+ b# `3 I* \: e5 E                                        }
3 |7 |" {3 L3 o. A& n+ C                                }
                                count = 0;
( Q4 B% @& ~1 v2 c: V9 S/ C                        }
, P5 r$ `0 ^- q  K# s' i5 s                        n *= 10;
% `" s. l8 \0 P9 y6 }                        m++;
/ J$ U1 R0 V- D+ p: u2 N                }
                return array;
        }
1 u) a( a6 ?' N5 i! y9 I* K3 P
3 K. U+ o% x8 P* C
}
  ^8 T6 C+ f  u+ E0 _1
2
3
+ y' y6 R5 L3 K; r! \8 P4
; R- n, ?! |6 g5 X5
6
7
8
* T0 P# A, A2 X8 N5 Y9
2 F" X7 D" m: R- z9 P  Y10
11
# N- B, Y* [$ {/ c1 A8 G7 p( B4 b12
2 l( v1 d; L/ L& W; c; \13
14
15
16
7 M+ A* E9 I! h* {& d% v- k4 ~17
18
19
20
, {; v0 r! L! z$ x2 U  t# _4 ]21
" q5 u5 c. ]% B1 s22
23
( l& \3 r# R" ~% {, w5 w2 ?. i+ }24
2 g3 V" C9 i7 k3 |0 }25
26
27
9 D6 [8 v# v$ {/ y; u7 v+ s& N0 v5 p28
* y6 o4 _3 C6 l, s" N1 b  ]29
30
% P( H9 x: @! g31
. U! K* B# h  S& j7 z32
33
& B# D- X# u1 B1 y9 j34
35
$ O' U* |8 V# X) U36
37
4 u  e7 ?( @& m6 N+ Q( S$ Q38
39
40
5 r0 I3 i: N' u- k4 u& e# g41
42
2 F* j4 e5 v: V  m  B* l* }. M43
44
45
46
47
48
" A  O6 C- K% U49
7 v" g% w. N) w$ E+ P# j50
0 x- r, w# M, Q  K1 [' z51
6 W/ f& b( ]% ?  }& N7 i52
: r9 V! H: Y9 A3 Q& S$ X! o53
. m5 U6 b7 j9 a计数排序
8 y) |2 }1 S: I& R+ k  S! }& B找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
) \9 r" U3 v# t2 N最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
2 U$ b( Z* C( \; ?7 r3 @# N( h1 T时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
' r* i6 n) s6 A! m% J

代码实现
' k* P9 v; s4 p( V4 U( G( A3 f  p

public class Solution {


1 i0 _+ m9 W1 a2 g        public static void main(String[] args) {
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
        }
2 I) U, Z/ H2 _5 z0 f0 g
' j! C& e& B7 O) x! i4 v
        private static int[] countSort(int[] array) {
                if (array.length == 0)
                        return array;
               
                int min = array[0], max = array[0];
               
                for (int i = 0; i < array.length; i++) {
                        if (min > array) {
                                min = array;
" x! B/ [: c4 T% h                        }
                        if (max < array) {
1 Y5 @7 @6 ^& a                                max = array;
                        }
                }
               
6 I1 q* p% N. v$ n: w                int[] count = new int[max - min + 1];
               
                for (int i = 0; i < array.length; i++) {
                        count[array - min]++;
9 O) E; `0 A+ a* J& }; `& A                }
+ F, T# j' T5 f* C! v4 e) W" W' J               
                int i = 0;
+ [+ [) C* D9 P! d; g                int index = 0;
1 `  [6 X) n; @; }" W                while (index < array.length) {
, V9 W6 J8 A  W- S; p6 a5 v9 }+ ~% p                        if (count != 0) {
                                array[index] = i + min;
& R2 r* K  V/ ]9 T* y0 ^8 d6 I/ P1 ]                                count--;
7 F& h2 L( g4 r" F+ n8 s3 [' T# w                                index++;
                        } else {
                                i++;
                        }
, z/ Y* I# D4 j6 \5 i: P                }
                return array;
3 Q+ G; x2 e+ t) L0 f1 ^, K        }
  Y, g$ h! w" e. H* r/ O       
) R5 X  V! S0 d* f/ w5 d+ z}
9 D/ e: R, v4 z, D1
2
3 f3 c  `% g, G5 g3
4
5
6 O( R* o6 \0 l2 c5 d0 l6
+ Y' H" \  R8 U* V. l( y) A7
( @8 ~8 y' e; v: R4 }8
9
) s" Y  K1 c! S! q8 m& Z10
/ B1 H+ r; z9 U: Y+ [, E( o11
: X2 k4 ?% h' m8 c4 Z  W12
: ?) R9 ?+ F8 m* y13
14
15
16
17
- z% I5 T9 W/ {! V# _. J18
. Q: [+ T) [# t0 e  F! \6 ]19
6 A8 b; U% @  p/ v# Z20
: S4 p. F+ j" n) v6 u6 Q4 N; S21
22
* K$ E' d% m9 h3 t% ^23
4 n! b- j# O# h6 G% P$ S24
25
- a$ A, T- N' Q4 F* _/ |* R. D26
0 o& [& ^( i4 J  L# D" U27
2 f4 Q  i1 L- }- H4 e5 V5 p2 _28
2 Y6 O: d" j9 |29
, @9 x4 B7 M5 h30
! M2 E  y5 W0 a: J4 K31
; |) t' Y7 c/ ?32
33
3 @) c9 i: v( }0 P- R/ Y/ @. z34
35
) Z: \# Y" f) j8 M& W) N36
37
38
39
9 F3 g" d% C; M# c/ E9 {40
' V( d2 t( k3 x41
42
; _' g+ s! Z5 ]8 g% ]* X" _- ?  ?43
44
桶排序
  [6 p% o$ O  ^, {1 ]2 J. ^————————————————
2 [: L, S' Y5 a& e& z版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 b! [2 N3 g' G  T/ c# [4 A& C原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
( i" }2 z7 D9 s, [; @

5 v! c/ G8 s+ A7 ?: t