十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）
+ ]( y) U! ~7 k( L& l
' r+ |0 w6 ]' ~# T* k& d十大排序算法（Java实现）
排序算法框架
排序算法性质
& V0 s1 X, Q( v5 j2 f插入排序
( C! ~' M" {7 @2 d) n8 J直接插入排序
希尔排序
选择排序
6 O! v4 M; ]9 D+ e% \简单选择排序
2 D2 A5 s: y: \6 I堆排序
交换排序
! n/ S& X, Q/ s: ]5 t9 @6 I冒泡排序
- C! x, H! r  f+ n- f8 a' ?, @% g快速排序
3 A  G/ v+ N% A' L归并排序
$ ]4 S- q* _+ i8 E; f基数排序
计数排序
桶排序
3 r* a( D7 a# ~8 W6 `更多文章点击 >> 这里

& T3 p5 H9 g9 h
( g* }  r0 I# w排序算法框架


9 I# l. X  h" P$ {" j
: O6 a! R2 C# E7 Y1 f
& A' Q4 i+ u! X$ m% {9 Z排序算法性质

$ m. ]2 k  G! l# B3 ?6 W. h1 D2 H4 T8 c
; x' m1 e6 f( P: _& s

插入排序
2 K3 S1 O  F- b) U直接插入排序
4 ?; t2 K6 ~3 w1 j) F8 @6 K从第一个元素开始，认为该元素是已排序的。
; A  c* t' X) W$ m  s取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
7 T3 q. l& e+ ]# A( e* S遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2 _( ?/ b. `0 D5 x6 O2
) 。
6 E$ e7 e& S2 L* x5 M! X& l
+ g9 G. J8 E* ~
: f+ m3 t4 k) x, H' {9 C3 `1 [. O0 @代码实现
' e! Y' r1 J, {/ C/ y+ U
4 C& l. A& W5 k" \9 Z9 }# H
1 F. ]+ T. ^- }6 _3 p* o# ?public class Solution {
% v% s, C! n# c        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
: G) H" z* x' m1 i' p                insertSort(array);
                System.out.println(Arrays.toString(array));
- F0 W! C8 Q# M, I; n, X  _        }

) |1 \# c# f/ q. P' n) _" N% @  v
        private static void insertSort(int[] array) {
  o# y# l9 y5 G9 [; E5 z2 ~                for (int i = 0; i < array.length - 1; i++) {
/ R) V4 c: ~6 T  o8 H$ X                        int data = array[i + 1];
; q$ ?1 j/ @: ^3 E8 l2 L2 a: y                        int index = i;
8 }9 J; h" h1 J; m( j                        while(index >= 0 && array[index] > data) {
% f! {. s* G* n) D' ~9 z                                array[index + 1] = array[index];
                                index--;
3 o( t% A0 r7 y- [4 f                        }
  e: S+ s4 ~9 A/ O, {! Q0 C2 b                        array[index + 1] = data;
                }
        }
}
1
/ B- f; k) _) z! `6 B! G1 }2
& s$ t! K2 R4 ~  w- S3
4
5
6
! ~! x$ \/ ^" B  n. [* p$ @/ C7
8
9
10
11
! }+ r( O6 H& ?& i* T12
13
, |' j" n! g. V3 R: ~14
15
16
$ f% r, B+ f# m! ~8 a1 W17
- q6 Z& G/ x( m18
8 w" L. }( G0 l19
希尔排序
6 e  c8 W% ?# h. Q" O. H  A: D
( k1 A7 k: c* K0 ]1 r: ~; n% [
4 z0 a- }. ~1 q4 R# S% k7 ~时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
! u  Y, u+ m6 f* {% d. ^; @- E( g

代码实现
8 X1 _! f9 A3 m$ D

public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
0 j) h4 Q1 E9 y6 G) f                shellSort(array);
) k) B: D' \/ c2 `( P* A, B                System.out.println(Arrays.toString(array));
, t6 b' e- G7 m# }% I- V        }

6 C" m- o8 D" V! }/ z; g( g( ^
- v  d2 E% U' _" K        private static void shellSort(int[] array) {
                int gap = array.length / 2;
                while (gap > 0) {
" T3 ~, w/ f* ~2 n5 Y) b                        for (int i = gap; i < array.length; i++) {
, l  ~2 C6 W( e8 Q                                int index = i - gap;
                                int temp = array;
9 }2 O; e$ w( N% Q1 K                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
                                        index -= gap;
                                }
; p3 g/ W0 M  k: u2 S9 [//                                array[index + gap] = temp;
1 e* A! J$ a' O3 e$ S) ~" u                        }
                        gap /= 2;
                        System.out.println(Arrays.toString(array));
                }
; n9 r( E3 K0 V+ v% @' \        }


        private static void swap(int[] array, int i, int index) {
                int temp = array;
* W, N/ h1 j- e: N: d                array = array[index];
                array[index] = temp;
        }
! Y4 F6 p' A, Q2 ]2 c. f( h}
1
2
3
4
5 D% q; w: ~3 R$ G$ G+ o% [5
5 `) T) @. E9 `# x2 p6
7
  G- ^2 m+ @2 A. X) B8
2 `$ i! c5 J4 D; u9
/ X; \- W$ ^8 x0 x1 ^10
( b: o& w! a9 J* v9 f11
3 C7 S; m" X8 a5 P2 i12
13
14
15
16
17
/ D- y+ C. ~# `1 v$ |18
9 B% _6 O  i. I/ f$ s9 Z7 D5 n19
# C+ V9 T/ I% w3 }20
' R9 z! G9 E% c+ v3 S: I21
22
* g. l: |( D% K$ x: z23
6 x8 p" o+ V1 }" [: A5 q2 O) k2 [9 d24
25
26
2 E, a& q+ x9 ^3 k2 Z3 \9 }7 ]27
% t( N5 f( _! }9 J28
6 h( V$ M5 S7 r( q4 m29
, z0 p1 E5 E7 k3 m, z3 w3 H2 H( ^30
3 y1 Y+ I: e% p! d( X# q选择排序
& q* Z; `7 g, y0 B& v; g4 c简单选择排序
5 m( _, U7 d0 y* P5 e从未排序的初始数组中寻找最小元素放置首位。
- L- S+ n2 Y' R; F5 u: Q从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
& Q8 w  K/ v, [时间复杂度为 O ( n 2 ) O(n^2)O(n
2
' p7 o8 I* ]% Z ) 。

6 P- e# f- x# [: p3 v' P1 z4 c
代码实现**


9 \1 d& ~$ T" \/ Ypublic class Solution {
        public static void main(String[] args) {
) v  B0 @1 L% X: F' H                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
; Y3 v3 q- C9 O: H$ [                selectionSort(array);
                System.out.println(Arrays.toString(array));
. H6 D+ ?; l: _0 ~3 w3 y! E5 i        }


        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
                        int index = i;
                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
                                        index = j;
8 ]/ ^7 F* _( t0 {                                }
                        }
5 [' \; s. U) w3 O: C                        swap(array, index, i);
                }
        }

1 H' m: g- H6 K3 i* q
        private static void swap(int[] array, int index, int i) {
- e! x6 U- |$ N3 e, m                int temp = array[index];
0 t# y: i9 ?2 ^- X5 T6 c                array[index] = array;
                array = temp;
4 }4 S( R. g* s7 ]) E$ e        }
}
3 C8 a4 @5 O7 }, X1
2 k# L+ X* J: P0 A6 x7 b8 Z2
! {. N* Y  Y; l$ E7 L8 ?  H" h& ~1 J3
4
5
6 g! j3 Z6 J5 C- `/ B6
$ {6 w0 ]/ K: K$ A7
8
9
10
9 i7 y# y/ a1 r9 B8 X- x! Q! W) Z11
12
2 S0 j) ?, p  ~! I' I0 [13
: j. k3 s2 R5 }2 S14
15
16
/ K% ~$ y2 v# U) ~5 Y$ v2 `$ ^17
, _3 a! [% Q9 v6 P% Q  Z$ K18
19
0 s# J. Z& g! A0 u. h20
  N( o7 b- }1 B' X4 l) P21
22
23
" u" X9 F- ^' L5 G2 l24
" I9 {7 V8 J4 I( t7 D# E( C- r25
堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

) {7 k- v! s/ a& P
9 L, e4 D5 \8 }0 \: ]: M代码实现**
' x% G% @0 z6 o5 E% t) X, w
& \/ Q& W% a1 q$ u2 B
public class Solution {
        // 建堆
7 X- f2 c! q; {5 `        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
, I" J; Q) @# v. C! q                for (int i = (n - 1) / 2; i >= 0; i--) {
                        percolateDown(arr, i, n);
9 D7 y% ?6 K4 T' y, n5 p                }
        }
        // 插入
% C0 \. Z6 V" o% i5 Z        private static void insertHeap(int[] array, int data, int n) {
! {6 y6 @" C9 \( C                array[n] = data;
                percolatrUp(array, n);
        }
        // 删除栈顶元素
) `; J: r0 t7 V) m1 c5 L        private static void deleteHeap(int[] arr, int n) {
3 U1 D8 X( W! X8 {1 _# `' o' P: a                arr[0] = arr[n];
                arr[n] = -1;
$ t0 F1 }$ s+ h2 S( P; Z                percolateDown(arr, 0, n - 1);
        }
- S  R& o3 U7 e  F  \0 S. n9 L        // 上浮
        private static void percolatrUp(int[] array, int n) {
  q, i, O  l' O+ z9 E" ~+ C                int data = array[n];
                int father = (n - 1) / 2;
: p. e* T" y- D  }* F% l$ N* \' U                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
                        array[father] = data;
4 X/ t3 c4 ?: A: @. f/ A- G                        n = father;
+ @; ?" i4 I1 I                        father = (n - 1) / 2;
. D& u/ d3 X8 Q- L8 |                }
                array[father] = data;
        }
        // 下滤
, @* t- N9 r$ k+ X; \* d* f, [/ k        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
                int child = 2 * i + 1;
+ R& [4 ^7 K! v; q                // 遍历整个该根结点的子树
                while (child <= n) {
                        // 定位左右结点小的那一个
                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
                                child += 1;
                        }
# `8 T- N4 Y7 j% M- M4 Y$ j                        // 若根结点比子结点小，说明已经是个小堆
                        if (father < arr[child]) {
                                break;
                        }
                        // 互换根结点和子结点
8 r4 _  P& \1 {                        arr = arr[child];
                        arr[child] = father;
                        // 重新定位根结点和子结点
& E+ c* k+ ]3 k- N                        i = child;
                        child = i * 2 + 1;
                }
' v2 R+ t0 x" E0 ]  T4 a        }
   
        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
, M3 k. `+ c2 l# d                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 1);
+ ]3 n6 a( X" m                System.out.println(Arrays.toString(array));
               
( [2 ?6 ]$ G8 l9 [  S4 [, N/ }' T                deleteHeap(array, array.length - 2);
                System.out.println(Arrays.toString(array));
               
                insertHeap(array, 3, array.length - 2);
. A, r4 B2 b) O5 d) {                System.out.println(Arrays.toString(array));
        }
6 H+ a; W5 J2 y}
1
( h; I( x6 d  Y( V+ o2
3
4
' ~$ S$ D0 g" g% E0 F8 m5
6
) y9 H& k$ q" q7
- X9 ?# S2 f5 ~; E' L8
9
10
11
4 Z$ P0 }: U6 ]" o5 A& j12
13
14
, Q5 l. e1 s* R  Y$ i3 d" f15
16
* z: f! H$ V( L) w17
8 x  s3 w: K1 K  m; X18
19
) n* I% }5 w$ t& g4 N4 K20
21
, c! K1 x. O" T7 l4 k/ E2 f# n9 H# C22
23
4 q8 t% d3 a9 e( k/ [* H24
25
3 M8 V' K; W3 w( P% B26
27
3 W* R; [/ j0 _  s' v28
29
30
31
32
33
! t/ R4 |: Y. a; K$ t% z34
* H# d' s* J" h, D" _% R2 f35
36
6 M  t! j/ J! p4 o. q1 u: ]37
4 {: I; I4 [% |1 H6 }& K38
39
40
41
" h! k! Q# k: f: M5 T+ {) Q; k42
0 G9 b. M) m: u( d$ h43
1 ~& M+ s' C8 G3 e/ O44
  U: N; k1 r0 [- c4 Z+ ?: m6 B45
46
47
  H; c- i6 F' k0 x/ g3 N. o48
49
50
51
( f7 L' E( U6 I5 U2 F6 d52
( ^6 X1 W* i6 |; E( ~53
% H6 e: p6 Y) N6 n4 _54
* @3 z9 E$ B7 A; G( M* I55
/ {  Z  n% `. D0 ?) ^) u& F2 W+ k56
; k5 |  w2 K& b# g# O57
$ F/ _+ x8 R4 A58
59
60
61
62
6 O7 q/ A5 i: _63
" y' E, ^& Q4 m/ ~4 k64
/ O4 _& [, S& J5 m' f" q65
66
67
) }6 d6 v8 W; z$ r' Q" C: Q2 F0 c  H68
8 P! a5 ]( Y) {3 X8 ?) Z69
* P( `" F9 ?0 f7 n6 S: U8 F, {70
2 d6 X5 X' S) T交换排序
/ |! f! c: U; m7 T7 M8 A冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
7 y# w4 I( b. @2 F遍历数组，直至结束。
最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
' D+ E  P. Z) t2
) 。

) s5 C" ~; `; l& }; ^6 C' h
( \! P1 q7 u+ n! }8 f! E代码实现
2 z" C  |! R6 n# R5 w  q2 T5 X

import java.util.Arrays;
public class Solution {
) l3 H6 f' E- t0 h# t" R3 k% o       
$ S" a. ~0 T1 ^7 Y4 Q        private static void bubbleSort(int[] nums) {
                // 循环次数
                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
2 b' `' S# g, H6 p8 N/ C; s                                if (nums[j] > nums[j + 1]) {
                                        swap(nums, j, j + 1);
4 x+ h3 }# ]) ^- W( a. _                                }
# i# `" g. d( C                        }
6 w  d7 d! b7 @- X. u; J8 p                }
' |5 c+ @2 ]1 ~+ @: }$ R        }
* D9 N  g( w3 g5 @, P
% H6 U  U! X) u# E3 d8 m- r
/ W2 M6 c/ p, C& N  T0 a6 P, C        private static void swap(int[] nums, int j, int i) {
8 s% S6 s& b, k+ ~9 S. S                int temp = nums[j];
5 c+ c# a' P6 Z# ?                nums[j] = nums;
                nums= temp;
        }
& q# O2 S0 j2 V8 G) s0 {: A
, C2 s3 y) K8 T& V1 A1 |& ~4 R
        public static void main(String[] args) {
/ x5 ]; A% ]0 Q; _1 u                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
) A% }- G$ ]: n1 `" C) O+ D5 R  k                System.out.println(Arrays.toString(nums));
        }
4 W( v3 d0 a4 s( U}
1
2
3
2 H/ T* R+ Y) V! l  V, U4
5
5 P3 l, n3 T( e) B6 B' c  K9 x' x6
- ?$ p) m& X# Y' W+ ?9 ~, K3 s' v7
' v! p) g; X* L- e8
9
% @, p. J  l. c8 J/ K% l10
11
/ _6 n& A. B6 _* `2 I$ [- P- p# c12
3 o  ?  V% B, E: |- F13
14
15
16
; F& g8 Z: ?/ a17
' `. i% N' l  M5 {# a' u& {$ d( `18
" e6 o5 r) Z! y  i) p: @+ C19
  v# c# K+ A$ E6 t/ k3 ?* h20
6 D1 k$ I% P5 ?5 i! B7 K$ }# s21
22
! \7 ^% e& W. A7 R2 k6 [+ U2 _23
* G7 m) a, b* J6 _4 F24
25
26
27
% [$ c. x2 ~6 l) B快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


( K4 A6 g! ^+ R" _代码实现
' H( I9 J# h  w/ \
8 ?2 E& v. y, s# i4 o
public class Solution {
( N% e. }5 t6 r5 k       
& D8 j9 e7 {, u# p, X# M        // Median-of-Three Partitioning
6 t7 t: }/ y; @: t        public static int selectPivot(int[] array, int left, int right) {
' S0 k- O; }& k  L                int middle = (left + right) / 2;
               
" J0 s7 T- N/ a0 D                if (array[middle] > array[right])
8 H7 i  k, A2 j, x) i# e/ e- T                        swap(array, middle, left);
( Q3 @! X7 O, u$ Y$ Q                if (array[left] > array[right])
                        swap(array, left, right);
, \0 C# v7 q4 g4 _" w                if (array[middle] > array[left])
( \4 n2 m6 F- P1 P9 z: G6 [                        swap(array, left, middle);
" O9 \9 t( m- N/ d( [               
% j7 ^  D  K% b+ @9 ^  O4 B                return array[left];
        }
       
        public static void sort(int[] array, int left, int right) {
- t- c$ v8 i* G  l7 S( c  i                if (left >= right)
                        return;
                int index = partition(array, left, right);
                sort(array, left, index - 1);
5 F) x4 e/ Q: d                sort(array, index + 1, right);
    }
, Y8 g& L% L1 M& b  T, u       
* A6 a) p4 \, N1 R+ b; n* L0 G        public static int partition(int[] array, int left, int right){
" b. a3 P. i& ^0 t        int pivot = selectPivot(array, left, right);
        while(left < right){
            while(left < right && array[right] >= pivot){
                right--;
            }
            if (left < right) {
- m' u6 J2 W2 {5 f4 X, j4 Q                array[left++] = array[right];
            }
            while(left < right && array[left] < pivot){
                left++;
# Y( d# x: g9 ]- h; t            }
            if (left < right) {
5 P1 L. N4 F2 o2 j7 C                array[right--] = array[left];
            }
9 d3 X0 G5 Q/ W% D/ n( @- M9 Q4 I        }
+ j! {7 u- h% r, H            array[right] = pivot;
        return right;
+ l- U% ]+ M( ^, [. }/ `1 k! e    }


, U% m! @2 ^4 p4 w" N3 }    public static void swap(int[] array, int left, int right){
            int value = array[left];
            array[left] = array[right];
& S" f3 M5 ^; y6 ?% O) E0 f            array[right] = value;
% ]: t$ h% A1 ^* Y+ u    }
  ~; Y3 @2 ]3 @
+ \- F9 U* b4 J/ ~% [% _7 X6 p
( W- ~5 f+ F# x        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
0 V$ A) Q1 _* C& w6 e0 V. r                // System.out.println(Arrays.toString(array));
- J% g/ [+ p* ]+ A3 f" N3 Z+ P                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
3 h7 H$ _1 M- Y4 L        }
}
9 @2 o, j7 Z/ v6 ~1
2
3
4
5
6
7
8
9
10
. u9 L" U+ K  O* Z7 [0 p& {11
+ s5 I4 f5 M- g/ L: U) u9 W12
13
14
15
16
17
  ^  q+ i# {' U. ~2 n0 D; g3 i18
19
# N* M9 A2 L9 [: z9 f20
2 ]5 e+ D0 b  }& k- Z21
22
23
2 S4 j, e" `0 {- P24
: k* k! \. @8 v25
; |, C7 \* g* ^+ R- O7 m8 l26
; O1 V3 A: A# c27
/ Q; T9 {7 O! x' {3 g28
29
, b' ]+ g# Q4 {30
31
6 y3 s; C, U# c* v7 L. [# v32
* P; }- ]% H( q$ d! d" W33
34
+ C1 w( s) b/ a- q1 L# z+ H' ~35
4 K3 W; M4 P5 q0 d5 Z# Z& A36
5 h" f# e0 f& X- c) p4 V37
' q# v, m$ G: i# C/ E% m: {38
8 U. N0 D; j0 w% @3 F" {39
$ S! U; _( \* _0 A. Q# j; p6 U0 d40
41
% Y9 {; F* ^8 L8 q# k42
43
44
, e" a) y3 S0 D45
+ w! |* l, f! q/ y46
! T( J# r9 n6 B+ G2 l: |4 N* x& e47
* V$ S9 X4 Q0 J' Q# n48
/ e2 Q. q1 \) g4 r4 y" S49
50
3 {5 z" x8 [! j4 j+ I  e) v51
52
53
54
, Q* |+ ?, ^. E, L1 f% b/ ]% F$ E55
56
57
  Q+ J7 a0 J' G0 s- U# S/ N归并排序
将长序列从中间分成两个子序列。
# z7 [. c; E; `# G8 k  e: A4 h对这两个子序列依次继续执行重复分裂，直至不能再分。
8 w1 U- m4 Y  ^4 c递归返回两两排好序的子序列。
0 }3 c) k2 s7 }6 i4 m& J. q平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
* S9 h0 i' q) L  m& W) a  a8 N* r

代码实现**


% x: _" \0 E9 Dpublic class Solution {
        public static void main(String[] args) {
& I1 Y& g7 t+ o, ]' U                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                int[] arr = MergeSort(array);
# W; m1 f# K; S                System.out.println(Arrays.toString(arr));
        }
4 ~& W4 L* g  Y

+ ?# B: U4 N+ C  ]. F7 y3 G+ m' u        private static int[] MergeSort(int[] array) {
. u* b( Z% r1 @9 Y* g                if (array.length < 2)
6 B; a- O- J" q                        return array;
                int middle = array.length / 2;
. X+ D" r. h7 ]- `: f: E                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
' e# m; G2 X3 e; X' S+ t9 t5 Q                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }

5 y. ~/ k* i( {* z5 {
" b+ G7 b- }3 `        private static int[] merge(int[] leftArray, int[] rightArray) {
  c0 d1 a4 C$ X6 e3 X! l                int[] result = new int[leftArray.length + rightArray.length];
                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
                        if (i >= leftArray.length) {
$ m, o6 e- W) Q- U2 m2 ~8 v9 q. v5 i" ^                                result[index] = rightArray[j++];
% s- Q9 w" u8 b+ Z# U                        } else if (j >= rightArray.length) {
7 W- ]* k7 N, M* e: @* y                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
, [8 A: o- O! l* Z  M8 b                                result[index] = rightArray[j++];
1 A# _; L- O& u+ L7 p. ^) o) L9 Q                        } else {
. N+ a# P2 n$ x3 s6 z, ~1 Q                                result[index] = leftArray[i++];
                        }
                }
                return result;
! o' S, n- W, d; r' k3 P4 F) |, q! ]/ _        }
, K/ A6 @# ^/ V! j}


' g, P! `4 T  Q9 x. |1
2
3
* f% k+ _, ]& R; @4 u$ C  S4
5
) m. D# [8 h0 y  H6
7
8
% N0 A: `2 d& z: j9
2 g! H8 g. C+ c8 G5 X10
9 B: V; b/ M3 F$ V11
3 {- g5 q: k& R! B0 M12
13
4 t( J1 [. ?+ q! v; J$ n14
) N( C4 {0 i. o8 A/ a+ l- X; u15
( G: Q3 h& k1 u. R. A+ s7 M6 `16
17
. x6 q1 c" j4 x  f; y3 d4 G' f18
4 Q5 {/ Y5 ~& n" N9 L& D5 O19
; S! R4 S% G+ j$ k20
21
22
23
24
25
: ^/ G1 r" [) R$ d$ Y$ E3 ?26
27
! d% p) @% l; L- G+ {  M28
29
% a/ N; z, u" i4 ^30
31
32
33
0 l0 H, b9 T3 V基数排序
找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
* K* A8 ?$ [6 `. K7 S6 c

代码实现**


; V1 V! D$ H1 H4 Cpublic class RadixSort {


% e/ o# ]1 f: |0 {8 ?6 f. A+ C/ n4 X        public static void main(String[] args) {
& _' j7 q' [# y$ Q9 ~                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));
        }
8 X6 g" ?6 Z6 x( F! t/ t
8 |: x: N4 Y2 @
3 d) |. }& Y/ I. r3 I5 I$ e        private static int[] radixSort(int[] array) {
1 t% _7 j4 \2 s/ N; J                if (array == null || array.length < 2) {
; M+ v6 ~/ q: b. W" {                        return array;
                }
                // 根据最大值找到最大位数
) H5 E7 [/ |  v/ L3 D                int max = 0;
                for (int i = 0; i < array.length; i++) {
! D9 e( q) e" z, n# v                        max = Math.max(max, array);
/ \2 W4 X) x7 _0 p, {                }
               
0 _4 f8 v! F8 X  O% w- q* R  P0 q. \                int maxDigit = 0;
4 T4 K/ U4 {$ b! O' ?- ]& M                while (max != 0) {
5 ~4 e3 H! H2 S& [* s: q                        max /= 10;
* \2 Z; {3 H: C/ d! l+ w3 X                        maxDigit++;
                }
& `' O+ ]7 D# }( j  \; z+ t/ r3 Z               
$ H0 N' e% T7 Z: ?                // 第一维: 0~9
5 s7 E- A3 b, K0 l6 ]0 h                int[][] radix = new int[10][array.length];
                // 该位为 i 的元素个数
                int[] count = new int[10];
7 n0 T9 R+ V( l  w               
                int m = 1;
                int n = 1;
& G; ?0 D4 M4 ~/ S7 ~               
                while (m <= maxDigit) {
* E* p" k/ F! v+ g# W+ ~" m                        for (int i = 0; i < array.length; i++) {
                                int lsd = (array / n) % 10;
: I2 s" C* ?2 N# b9 f0 Q9 y1 A                                radix[lsd][count[lsd]] = array;
& O) s5 ^" R. R+ J                                count[lsd]++;
                        }
                        for (int i = 0, k = 0; i < 10; i++) {
$ S8 H6 p$ a& k2 ^5 t                                if (count != 0) {
. g+ ], W9 B4 c, p0 f9 ]9 l                                        for (int j = 0; j < count; j++) {
3 P/ J4 n0 z8 f4 `& {                                                array[k++] = radix[j];
                                        }
* m  N& o: K) R! G                                }
                                count = 0;
( Z" u5 _$ N8 c- |. a' B                        }
                        n *= 10;
                        m++;
                }
) c+ J, _* v8 q" E1 I* n                return array;
0 l# [* r* F3 v/ N8 I% @# i: x; U- Y& ^        }
4 h$ o# L' C" a' e/ V2 V

8 w5 p  E" P3 K}
1
2
3
4
, h/ ?/ i' h6 }  K' _2 W5 o5
# L, p5 b. w: U8 P4 Z# v# j6
7
8
9
" m, q! v+ E( o# w' n) d  g! U! }10
11
" O; |- C; I& l12
13
14
15
16
7 o, @3 ~0 Z1 T+ W  `4 d; F7 L" R  Z17
3 K& m& q9 k. \# M2 Z6 }18
19
- u& W: S7 i8 J; ^  p( v: ^20
- x6 j2 Z" {$ m7 Q21
22
23
24
25
26
27
28
29
30
/ i" A. X; C6 ]# ^31
32
9 s3 l; O: s! b# Y- S! ?* G33
( f, s' y- f3 s" K. }" S34
35
- M% l, {4 ?* t# V2 F7 `36
37
38
39
, H: J$ z/ b% {2 U3 Q* c% @40
41
; c' \' E; r5 j42
43
44
45
46
47
48
( y+ u) d) J' X' r49
50
3 S- }9 E+ l- j5 t% M51
8 b& Z2 i) D9 w4 ?3 g52
& A' F- c( ~: m2 L53
计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。


代码实现


public class Solution {
; }1 c( A. O$ ]9 x8 S
9 h; n" f# @' o. O7 D) u0 S3 @
        public static void main(String[] args) {
6 ~' l9 i$ U# \* X. I: {                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
9 R$ [* ^: l) Y! N  p                int[] arr = countSort(array);
: K, k1 a6 m6 m+ q* ]1 y" R                System.out.println(Arrays.toString(arr));
6 ]% J' w# k# l4 O' T; @% I) Q% u        }

* t$ y$ F) \9 I% K# R9 T: K
        private static int[] countSort(int[] array) {
' ?& e% b. c% n' {% d                if (array.length == 0)
: R% x, A0 K. L$ @5 |9 p# j# n" l! t                        return array;
               
                int min = array[0], max = array[0];
  f. i! c' b& b9 m               
                for (int i = 0; i < array.length; i++) {
                        if (min > array) {
                                min = array;
1 M: s" H/ e# \8 ]                        }
                        if (max < array) {
                                max = array;
                        }
                }
               
                int[] count = new int[max - min + 1];
               
& j% q) v9 ]2 P0 \3 t& ^                for (int i = 0; i < array.length; i++) {
                        count[array - min]++;
                }
. M7 m: u  P* r; }# d7 {               
6 u0 ~& ?3 ]4 ~1 ~; A2 X. j$ K                int i = 0;
                int index = 0;
. X8 G% Z0 I% u                while (index < array.length) {
/ F) O# [  Y4 s1 n/ p( ?1 P                        if (count != 0) {
                                array[index] = i + min;
0 _: \& d  O: q! A) @                                count--;
6 ^+ u2 S4 y( x: t. S0 U                                index++;
  b1 x5 D) |* d0 O, w: n                        } else {
                                i++;
                        }
                }
2 C3 Z" ?3 H# v2 d9 s" J( V# U8 |                return array;
        }
3 {6 T4 @% c% F, X: {       
}
% D# |5 U- V* n2 @1
  E. u+ E) d2 |/ r) M2
" @$ d& k' x$ j, G2 Q3
4
5
6
" Q" ?# }. @/ l/ d7
9 R5 b+ G4 J$ @6 G% i- O5 T8
9
) Z1 V! q# v9 x4 E) @10
11
% o5 S1 C) m0 t3 v* q12
13
/ p4 f; r* }+ b14
- b+ w  q, z& U15
16
17
) U# ]/ y3 B1 N% r% I& [18
19
; g% ]6 x0 t8 ^7 O; }8 C20
21
: u- W: K1 U1 U1 I* |22
23
24
25
26
27
28
( F9 a/ i% J; a! S29
+ W: o+ I/ }& d30
31
) K3 u8 {" ~+ g/ Z- b32
; V' {% `" |+ I. T9 M33
34
35
36
9 b) o' W3 q( Z6 O9 g37
38
3 n+ s$ L, v) z5 h4 ^& D7 L# C- T/ H0 K39
40
41
42
  j! M% X4 T7 [4 j  @* ]7 @# I43
9 o5 w) N$ Z8 ~6 _2 k$ d- |' V$ ?44
: E& l6 V. j: b% n% `: ?桶排序
————————————————
! q9 p: Q! @# Q9 c+ A" s5 ?: m, ^版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
6 x' J9 N9 R  i  Q% y  z. _
0 Y% l1 n( ]: h$ D  k7 g, o