十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）

十大排序算法（Java实现）
排序算法框架
排序算法性质
: V* z1 V$ I4 e3 B# {! [3 B插入排序
直接插入排序
希尔排序
选择排序
简单选择排序
2 K' `8 T, X$ q1 q# n堆排序
交换排序
8 {  e5 ?9 m1 x冒泡排序
  [  G% w: e( Z! k" r, D: I+ q- k快速排序
归并排序
基数排序
计数排序
! ?" ^" N% {. L/ j7 V% o桶排序
- }5 n$ k- V9 ^( M( y) R更多文章点击 >> 这里


排序算法框架
3 q7 A/ g* ?; c! D

* O: i! ~& }8 t8 z% j9 R* O" `
2 A8 }! O$ l/ ~6 t! b7 c3 c
2 u3 P: ?" H! O& X* E" F排序算法性质
5 p2 X( E4 ?, y. J  r6 z
& M, \& V% @" K7 W, ~
% R- _: B* ]0 C/ ?
5 k2 O- Q; R6 ~' i
插入排序
直接插入排序
从第一个元素开始，认为该元素是已排序的。
9 s4 |: y1 N2 S取出下一元素，与前面已经排好序的部分进行比较。
3 ^% q; O& U  J% |$ f若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
2 L7 Z: K5 M/ R遍历数组，直至结束。
: M9 y  M% G% \1 ]最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
1 {9 G; Y8 |$ B& o1 N2
$ I3 w9 Y0 a8 H3 k# K/ _* K0 {* c ) 。
3 t5 l; }, t: x$ w' z7 w

代码实现
! W) P' ^5 K% [: Q+ C* u
7 u$ N% b! v- _: t3 k. X
public class Solution {
( f. a( M$ k9 }% F$ v2 I        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                insertSort(array);
                System.out.println(Arrays.toString(array));
& S7 V6 S. n0 \2 o        }
) [$ w) ?( ?; C, F0 ~* V

        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
$ |4 F3 f. E8 B% ?                        int data = array[i + 1];
( s0 Z, P+ K% W1 x  C/ U: |& D                        int index = i;
2 u5 s5 @/ _9 _  ~                        while(index >= 0 && array[index] > data) {
                                array[index + 1] = array[index];
4 d& q% Q1 t* C7 T                                index--;
                        }
5 u+ I; W3 `$ N* h4 b, y                        array[index + 1] = data;
                }
        }
- |9 F4 A" f- D$ I: r+ g; L% X}
1
2
3
2 o8 G9 B. ~% f( w, h4
( K; L6 @! P6 k$ _) u3 Y/ _5
3 Q" W0 V3 {& o) I0 A8 j6
7
8
9
10
  S) A8 P4 c: _3 b9 b$ J! @11
" X! `2 Q9 \& S, t9 O+ j  R12
13
14
) |- \. z+ O1 X: C+ B15
16
% G5 ^/ L0 @8 Y7 ?- v: [5 k  W17
" R; _9 W+ u! x, s4 j, T+ M18
, k& z2 N* l: |) J( D19
0 W6 g3 c  e2 u8 K$ ^, `希尔排序
$ ]- j5 Y. X9 D7 g' z$ q  m' d

时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
2 N  D' O& {+ K. x/ X7 _
2 _3 d$ L3 Y4 O: j4 H! s* A
; M+ Y3 ], f' i8 [; }5 ~代码实现
; O: f" [% G+ s  `7 c
9 {0 x9 A/ N2 x9 B, W# y- c
/ a% I. v, Q% l$ }1 kpublic class Solution {
6 T, A; e3 c$ Q1 @3 _% q* W        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                shellSort(array);
" Y! C/ c7 X: n8 o2 g                System.out.println(Arrays.toString(array));
0 d% B6 s$ o  e4 s) a        }


5 h. C$ n6 s% l6 O: P, D        private static void shellSort(int[] array) {
( K5 h0 k2 b  P                int gap = array.length / 2;
                while (gap > 0) {
                        for (int i = gap; i < array.length; i++) {
                                int index = i - gap;
                                int temp = array;
) ~( e9 i1 b7 I  O- ~                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
                                        index -= gap;
                                }
//                                array[index + gap] = temp;
                        }
& V! r: `) {# f& ?! A# ]5 O                        gap /= 2;
                        System.out.println(Arrays.toString(array));
4 r0 ~; h3 }) L0 t7 a$ N7 e                }
        }
! t7 e: g. G% \$ z% L  }/ d% @5 y
: }! F- E0 w9 X: l
        private static void swap(int[] array, int i, int index) {
                int temp = array;
! \9 O7 _, m& f/ }                array = array[index];
+ {0 x& _  r0 R2 ]                array[index] = temp;
        }
}
8 l; \5 b+ @" w' u0 Q8 g1
2
# R1 _4 |: ~9 Y& k3 O3
4
  t* V& R: Z2 q* j5
% i' E5 X) a5 f6 V% |8 \- @0 y% l. D6
) `1 [8 H  q1 O& Z% L% K" {7
$ z$ r) a, s" i: n' ]$ {& u/ B, l8
9
10
: P+ L) \% y  _, A11
& o5 ?% K& x7 v* X  \7 W12
" W1 Y! r- F+ P9 y% n9 A13
' [+ L7 K9 j; S7 O; N& q, f4 T14
15
; ?+ v, H, f9 k# t16
17
( h2 f' ], u+ I18
8 u% o/ U; ]* n9 Y/ I19
20
* o2 q+ z: Q2 K; Z) ~- M" b21
' q; ?! Y$ I/ j0 r: _22
* B. I/ I9 t/ ^$ I% e6 W23
24
" R3 O# B9 ?! S  {25
) r7 J4 @* o, T26
: v9 v0 k$ V& A% f27
. B! B' G0 ]5 H  t. u28
0 h& A3 e8 P. p0 y6 I, q29
30
& B- i9 c: n8 T选择排序
* s6 b5 c8 f* b简单选择排序
8 |; h. W2 l- R, x* F9 u2 u从未排序的初始数组中寻找最小元素放置首位。
; V' J3 y% c: ?$ Q/ M+ }  I从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
) N; N: R6 O5 f" W- [9 C3 s时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。
2 U# M2 ?( F0 N7 {" S; W

& w8 e1 w$ n2 E1 d+ {9 g2 x4 Q7 u! p代码实现**


% n- |6 [" I+ L4 N  Npublic class Solution {
8 F: n1 M  X* j/ [( r3 [        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
6 g" F  W0 }% Z  }' b2 G1 [                selectionSort(array);
4 H, G: d1 l2 Q; v0 |( S" Q- ]                System.out.println(Arrays.toString(array));
  Q* M/ O7 V4 T  R% Z  J  m/ n        }


9 P) O; R, V& k* o. e/ z        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
3 V1 h- q2 P: c5 D) K                        int index = i;
; x8 k- d, o4 W                        for (int j = i; j < array.length; j++) {
; N  p8 a! g, Q* q- T                                if (array[j] < array[index]) {
  d% H4 j3 Y2 c. J2 p5 E                                        index = j;
                                }
- R! s8 E$ b2 }3 Q  r  n* T                        }
6 ^! D5 N& K7 s# \' }3 y3 Y# H                        swap(array, index, i);
                }
        }

* D/ o: f8 r% @2 q9 C
        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
; ?2 v5 P, k8 C. k2 i% w                array[index] = array;
                array = temp;
7 E4 K: a" l8 i" R6 G        }
% {- M  W3 x$ Y4 B}
1
1 D4 J$ F  @2 c+ Z: t# |4 k1 {2
. k9 C# ~3 s  ^& S3
4
5 S8 n) A2 Q: t' k; ?; J5
6
( S% ]" j# A9 o8 U8 {7
4 o1 m* C  _6 x7 s7 ^1 {7 D7 C; g8
5 N8 k& |9 ]0 U! r) G% H9
10
8 S) h, k6 a; ?: u3 A11
12
! |+ z/ G/ n8 J7 k13
14
5 N( r' S! Q7 q' T- n  L15
16
17
8 Q/ Q( h0 f* \7 G5 i0 I18
19
20
21
22
( P- h1 n# }2 F# ]1 s4 q1 u4 P23
( Q. k5 y+ K/ B' I, D# {$ z$ V6 B0 B24
25
堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
5 x3 K) o: n' M1 {5 g
- n9 p# p& y; E# x; R
代码实现**
) K5 Z- d/ ~( g( h3 w1 `* }0 ~! r8 v  p/ o

( Y$ @) ]# P1 {) s! jpublic class Solution {
        // 建堆
        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
                for (int i = (n - 1) / 2; i >= 0; i--) {
                        percolateDown(arr, i, n);
                }
% w7 f+ _4 c' y' Y        }
        // 插入
        private static void insertHeap(int[] array, int data, int n) {
1 Q* x, F( y8 U  l2 C2 v                array[n] = data;
                percolatrUp(array, n);
        }
        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
                arr[0] = arr[n];
( `( a' n; G, Y/ ]                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
4 B: g/ M4 ?/ {9 P$ i  B4 n& i        }
        // 上浮
        private static void percolatrUp(int[] array, int n) {
                int data = array[n];
7 R1 R/ D7 k; |4 r) K2 N                int father = (n - 1) / 2;
  a: N4 X! X- ^$ y: g0 I                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
, N# i: L* }1 o+ ]9 k                        array[father] = data;
( [( `! d# Z& M/ ?. V9 S1 V                        n = father;
                        father = (n - 1) / 2;
                }
                array[father] = data;
6 a$ j7 d0 Q- Z        }
        // 下滤
; J1 T" [) k. R6 N( A        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
                int child = 2 * i + 1;
/ m# d7 [) P3 A) {; e! R/ ?                // 遍历整个该根结点的子树
$ j$ \' x( ]: s; n5 ~: v. ]3 c                while (child <= n) {
6 P3 B# J5 Z/ r4 `) Q                        // 定位左右结点小的那一个
4 A6 g8 ?  n) P6 Z; Z( ^9 _  v1 ~                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
                                child += 1;
$ E" ^3 h* O5 j/ O- l; u                        }
5 m7 O: k  _5 [( `                        // 若根结点比子结点小，说明已经是个小堆
4 C5 u& P2 _$ D& [                        if (father < arr[child]) {
                                break;
                        }
: }: [# {# l( H# u# q                        // 互换根结点和子结点
3 y. h" e, s# q                        arr = arr[child];
/ Y# e; x! A& j! M                        arr[child] = father;
                        // 重新定位根结点和子结点
6 q2 i  @( _; M& `' G9 f  A7 j0 `                        i = child;
                        child = i * 2 + 1;
; S" i% q4 m" y! B                }
  N: f' c$ C( N. }/ C. X, L- n        }
9 C( N6 f  l' O9 `- G: J+ o# D   
        public static void main(String[] args) {
% z8 U( u: m" H! p' v& O                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
/ Z% U6 _0 j( K; |8 q# k               
) P& L) W( s% i) `. `0 Z                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
+ O2 I& B5 f6 d% U* h3 ]2 n5 J                deleteHeap(array, array.length - 1);
- O  i' F6 \) h( Z5 \" I! C                System.out.println(Arrays.toString(array));
               
( }3 ?! z% [1 o/ H3 w$ ^- O                deleteHeap(array, array.length - 2);
5 k) \4 F6 v5 M3 T                System.out.println(Arrays.toString(array));
7 c$ K3 I' v& Z5 C               
                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
6 D8 S( ^! r2 J' g4 ?+ L        }
6 ^! a- |- B4 o* O# S}
8 L- O6 j- @) q; e+ ~1
  n9 D" ^0 Q* N$ O  |, h2
- Q0 m, ~  U/ y4 ~- x) X3
5 y7 C6 z5 U! K3 N% `7 q9 J1 C4
+ L- I8 O  _/ J- j) {) J5
4 r9 \' ?$ |8 n3 D' N$ C6
, T) ]9 V. W9 I0 L! K% d7
+ F) ?+ o6 R) x$ j4 i8
9
10
11
- |- g+ ?! _- I12
13
. [0 ^* K0 P, @9 N0 v14
: y1 K$ F+ v. _# a& X15
16
5 i: [/ n+ A9 J1 C; \2 Q17
( A5 o: B7 G3 W- }" d18
19
20
: S: e& q$ ^6 g4 v* B21
. l7 S; r' L  r" D22
6 g% [# U5 P& b) c& W23
24
9 N- g9 p: ~0 V% _; N; i7 a! _25
26
2 B( |& Z, Y9 g4 ~9 G, h27
28
29
30
31
% ?* _) J8 n0 _7 m: G( m32
( v' N; s+ B4 `2 j6 O& L33
34
35
5 K. s; S9 l% V. L2 d( ?) X36
+ Y% K8 d, ^) j8 n0 H2 m$ h37
38
  Z( u8 b+ n- J  n6 P# O: e39
1 e- s$ |, G, C  C# S5 T- m40
41
42
43
* e7 S' \( \, L: D, ?, |3 G! h44
45
46
* n  i  I4 C0 O/ U47
48
49
50
51
52
53
& M: b7 y6 ?& Q8 O& i* I3 B54
55
56
57
58
59
- m4 A; s" z5 h8 q, x3 [, Y+ t60
61
62
+ v2 {; q; K$ P. u/ }3 h63
- R$ t, D9 ]  F6 a5 B5 }- }: {; p64
65
; h/ ^* R$ Q6 X9 d  a66
67
) k7 e% p. ?* L; X) H68
1 y; r/ L0 v  l9 Y" C69
* v( ]6 C9 a0 `8 z' O  `& o70
: S  j; n! K0 l- j" s交换排序
冒泡排序
* o5 _6 V: ]# h5 \' W+ l* Z依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
' \* i  F/ H* U' c在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
5 p8 a4 V9 C* F/ {" {2
) 。

! p2 z# G# _# G3 [: L9 x) X1 C. o4 F
代码实现


- @1 O- e6 H. W  o, |% J6 Oimport java.util.Arrays;
) f6 y4 H& C+ xpublic class Solution {
       
        private static void bubbleSort(int[] nums) {
5 C" l$ V" e; X; L: V                // 循环次数
, e8 @, v: \9 ]: y                for (int i = 0; i < nums.length - 1; i++) {
0 B) c# q% n0 y: r) W7 |                        // 比较次数
2 H) ^: J4 q% v, G5 Q+ p6 E$ F                        for (int j = 0; j < nums.length - 1 - i; j++) {
: {- B% B9 u- _/ A0 u                                if (nums[j] > nums[j + 1]) {
9 w& w- _# s# t6 |. H% w                                        swap(nums, j, j + 1);
                                }
8 W+ f: {1 B9 D# x' b6 U/ z                        }
                }
        }

: f* |; h& P% }  v
        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
! f& U* y+ ?" P# L* E. W                nums[j] = nums;
                nums= temp;
        }


/ @9 l, y' n2 l+ _% B9 J        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
        }
}
1
. T  Z9 P% r# ^# L9 d& N9 c/ _2
3
* u  ^- \1 B8 Y$ S" J* N$ ^4
/ j' `, a! _; d: O) d5
6
' H  i. G2 @) i% J1 @7
/ e9 B* F  p' G( o- j8
9
10
0 o3 |0 [+ z% Z+ g9 R, q( }6 `6 k11
0 \: {+ O) v  f- E9 U0 W12
) f! A! X) i7 p6 f. Y: b4 D0 V13
. b: k' V  E/ B4 |9 x* e14
' W9 v, \' w! r15
  W4 r* Q) D9 P% T& q: Z16
1 O. S1 ~9 n7 Y$ D17
  f% y& \6 U1 Q: |/ F; A* }18
/ |# g6 L0 I8 F, M5 P19
20
2 i) e) ?0 p+ [" h21
22
( f' G! F& S: E: v9 `  B3 y$ L23
: o/ T3 |* w4 e24
2 b3 q- g* F- k25
$ k! w) m1 }# e9 `/ \26
27
' j6 j& K" \1 j, h快速排序
9 Y. g# H: G+ n. r* I. M# u, F时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


$ Q# Z1 u/ D6 |, x8 v+ |代码实现
; }8 }# a4 o2 e$ k5 i; n9 U+ T) d

7 o, N# X# Q" C; Ipublic class Solution {
       
        // Median-of-Three Partitioning
; Y0 U* ?2 {$ o: y, L/ J        public static int selectPivot(int[] array, int left, int right) {
                int middle = (left + right) / 2;
0 i5 {  U" k. R* c- E3 ]* P# `               
                if (array[middle] > array[right])
5 y/ V$ ]2 U0 Z" z4 t+ {                        swap(array, middle, left);
$ k& a6 i0 u; r- d, Z# Y: j                if (array[left] > array[right])
                        swap(array, left, right);
                if (array[middle] > array[left])
                        swap(array, left, middle);
               
                return array[left];
        }
       
        public static void sort(int[] array, int left, int right) {
                if (left >= right)
4 K7 F5 [0 A4 K* m& E                        return;
& l" k0 \$ _7 {- }# V                int index = partition(array, left, right);
, {8 D! q' a7 t6 I4 M7 Y8 ^6 l- ^$ Q                sort(array, left, index - 1);
                sort(array, index + 1, right);
  J: S2 d' [- H4 L6 a+ x6 y+ a    }
) B7 l! j8 A; N0 g       
        public static int partition(int[] array, int left, int right){
        int pivot = selectPivot(array, left, right);
        while(left < right){
) r; U8 K2 l' X7 q; r9 a$ _& R            while(left < right && array[right] >= pivot){
                right--;
; ?1 a- o! K" R+ Z0 ]+ I            }
            if (left < right) {
                array[left++] = array[right];
            }
            while(left < right && array[left] < pivot){
  _) m; i) O/ h! l                left++;
; ]3 D6 y  ?9 Y# K* s            }
            if (left < right) {
- q6 A3 b* Y! ]  p6 X: p: C' |                array[right--] = array[left];
' i" {- U5 y: R/ {  J            }
        }
0 c; X, V0 e  P            array[right] = pivot;
        return right;
- W* Y7 g, t( J  x: q    }
: w3 u% V6 p& L% `

2 W2 B0 u* {4 b% a    public static void swap(int[] array, int left, int right){
            int value = array[left];
  ^' ]! p1 v5 T: T            array[left] = array[right];
9 T. @* l- c4 P+ k% R$ ?            array[right] = value;
. T# w) Y5 B! w6 S- ~4 C    }
4 K! i# v/ Q$ S3 w* J

& c6 [% N9 ~) u) M8 v. L, n        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
% A* F; m8 D' s* ^* L! [                // System.out.println(Arrays.toString(array));
/ }3 d+ I3 z. ]! Q                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
        }
+ Q% g! j4 Q. V( x  p: v5 b: o2 @}
6 l) A- q+ h- h. P7 y1
2
3
* V" [/ j- F0 R  I4
5
6
7
8
9
0 [2 F7 l+ Z' K: z+ B/ o10
2 F; Q: @6 `" q- O4 s& e+ @7 j11
* g4 I1 A" n0 z1 a12
7 V; V$ r) i. B% j0 k13
+ z6 T/ p0 `/ s7 v3 H! M14
15
+ O8 H, s( A8 x5 w6 U) v16
" a* D# ^9 `  Q, n/ z17
18
19
20
& f% N. s3 P5 V21
22
23
6 o( {- C& D3 k5 Q" k24
25
+ \& E3 x. f$ O  S; x1 R26
, c  R4 ]3 x+ e1 X3 u* n1 K27
2 ~  |$ f5 E$ p# ]# H) Y28
29
30
31
! {' m. ~3 D, c* L* Y32
33
+ R5 \, R4 i) L1 Z34
# H/ P: v% w- \35
36
37
! q0 J  {* c1 F38
39
/ C' Z, r% z- i, \40
. S, J( J  H6 t9 ^; y0 H* E41
42
3 Q) a5 k  k7 g' P/ n) q5 F43
44
45
46
47
48
. i5 g* F) w  P3 ]! R$ z. B- X49
50
51
3 J$ N- ?% [+ F; Q# m8 T9 P, D8 }: W52
, Y: s* w3 y3 n; D53
4 ^) G, q& p' J' I7 h9 t$ E6 p54
) S! E! I8 R) d* l6 w  L1 g. f( p55
( O+ J1 K. Z+ y' U! K' t56
$ W+ Z2 g' ]) J$ ], X57
- e: [0 E4 e1 d+ E+ A- F/ Z归并排序
7 ~' ~- x9 y) S2 \将长序列从中间分成两个子序列。
4 c9 a3 P3 g( T3 e6 u; s8 R/ Q, x对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
9 d! u9 `4 |1 _3 ]# o( Y0 p平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

* @/ a, c! o1 j. ?4 L$ ?* U" A
' `8 q! F4 Z5 ?% Y6 ]代码实现**
/ m, A( S1 Z/ ^+ u: @3 c8 ?( G

public class Solution {
        public static void main(String[] args) {
  d0 V" j: U3 e                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
* V* H+ K$ M# A( |6 `                int[] arr = MergeSort(array);
                System.out.println(Arrays.toString(arr));
        }


- H, y  k; e( q* g. {        private static int[] MergeSort(int[] array) {
4 ^% i+ J! `- Y                if (array.length < 2)
9 C; c  d+ u. Q& m  C                        return array;
- I7 S" y4 [; M& \3 Y2 ?                int middle = array.length / 2;
                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
) N- K3 M. E. |5 J- T8 f                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }
) V. T, H) F9 ]/ [. a
, o% L% N$ F7 |, Q7 w) `; m4 F
        private static int[] merge(int[] leftArray, int[] rightArray) {
' X" p, c. ~; v0 r% [0 w                int[] result = new int[leftArray.length + rightArray.length];
2 Y; J9 r, ~& B5 s2 V2 z8 Z+ x$ A. N                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
                        if (i >= leftArray.length) {
                                result[index] = rightArray[j++];
1 {0 C% b, _) ]* ]+ k2 e                        } else if (j >= rightArray.length) {
7 G( _6 _" c) Z' [4 M# M7 Q8 s                                result[index] = leftArray[i++];
' A8 _* K1 w% W                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
5 @& h8 z. F0 c& p                        } else {
7 N- E" S1 [. q+ y. i( @                                result[index] = leftArray[i++];
3 ^1 M% U5 R1 Z+ E, v& a9 q2 {                        }
                }
                return result;
# N1 O& t$ s8 G3 {# ^8 D        }
( K: y3 Q8 ^8 X8 J1 U. W}

! H  k1 W5 h+ J+ s2 k! s$ `# R8 I
1 P+ n+ C. C! Y# F. D8 h1
, o& U9 u: C- X, p+ O2
3
4
$ x9 }* c+ Y  W1 \9 y5
6
7
. {8 P' k" x2 v' K+ f0 s8
9
10
7 y4 W7 m+ u6 L7 S11
12
6 H5 {1 [- M9 L! Z- {/ p' F13
* u+ D. w% r4 w: c1 ~5 E3 D( b/ n14
" Q1 ?. E( O7 z2 O15
4 x% V! X# \! z: P16
17
18
19
20
6 N% s' s" F- d0 \( ?7 n4 U5 ~21
22
23
# C* X. t& S# ]; @0 ^3 v- q24
( Q+ M0 D" [4 k$ W- y) v3 f+ j25
26
: m% ?5 E& F+ r; g  s6 Z27
8 M5 E8 |* D) ?  X, g1 f* {28
29
2 v( E" n4 K2 z7 A30
31
32
33
; H. C! T( q4 h: V# i2 R! J基数排序
找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
. s' \! J7 ]# k& v8 A7 y+ {7 a, L5 Z时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。

4 U) ]- b4 R+ ~- y/ t0 Q  s7 {% z
$ i$ M, s, x' Y! ?0 z0 i; G代码实现**


public class RadixSort {


        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);
4 j! _+ F+ F: q+ j8 q9 U( O                System.out.println(Arrays.toString(arr));
        }


6 W( L, E) x4 C! q8 `) L  \        private static int[] radixSort(int[] array) {
& s9 F! o6 F) \- L                if (array == null || array.length < 2) {
3 R: ?2 M  u! V3 V                        return array;
                }
: ?) ~* d+ g# W) T7 d" h+ r4 J                // 根据最大值找到最大位数
                int max = 0;
                for (int i = 0; i < array.length; i++) {
5 y' M5 {4 P, T: {" ~% E1 Q                        max = Math.max(max, array);
                }
  B7 J/ j6 ?; L' L3 G$ C5 D               
                int maxDigit = 0;
                while (max != 0) {
                        max /= 10;
5 V  l- ?* I1 J0 F3 n                        maxDigit++;
                }
( E8 Z# p) I. f- @/ D               
) a5 W2 l( \" a4 P% E1 Q4 P  k                // 第一维: 0~9
7 L- h- A, o7 Y1 G                int[][] radix = new int[10][array.length];
0 q1 a2 c# Y0 q4 e                // 该位为 i 的元素个数
                int[] count = new int[10];
9 D2 j5 E9 b" Y: I# h               
                int m = 1;
                int n = 1;
* z0 o5 m1 O& L$ ^1 Q               
                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
, I! C* U1 N0 `% j' C+ t4 O9 l# m- G3 M                                int lsd = (array / n) % 10;
2 b7 }& L, V6 M6 A$ ]2 a, x                                radix[lsd][count[lsd]] = array;
, \- N5 L$ V/ F: ~8 u0 r9 \; E6 j                                count[lsd]++;
                        }
' W$ W) a$ C- z2 r0 Y                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
/ L/ Y. k. u/ z$ E  z; w0 Z1 O, W( a                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
2 |$ I5 Z+ d7 E( z                                        }
                                }
                                count = 0;
                        }
                        n *= 10;
                        m++;
                }
8 @) u1 Q3 W' @2 S: ^5 e. k; T                return array;
) d3 `# m: T9 C& k        }


}
" P' R/ g% ^1 N6 m7 n$ F- Y1
2
3
# d7 t, D( c1 P, e, R5 A4
- J& i1 q9 V( l" m: E. j$ Q5
6
) i$ x6 S' m7 w8 g8 K7
8
6 Q# c8 l; V7 p3 h; s9
10
) G4 O6 a, h0 R11
1 I, r- P( w6 u9 }1 o12
13
14
" k5 T( ~) t' r4 R, O15
16
& _/ ]9 o7 s7 a& w2 Y17
9 `9 e2 d1 z  R- z# A8 m, H18
7 R& E$ A$ m+ T3 l19
20
21
- p8 J/ F. J" e7 n) z! ?  h, L* f22
/ C9 ]5 g6 E- C' }  u- m23
24
25
( J" `# l) b) d# f26
27
+ @2 A& n# j$ m' W, V6 ^28
7 j/ s: p$ F6 c! U29
8 o3 N& }* ^* R8 Y( ~3 c& y30
31
) d3 E" i+ T+ n# r32
" g# ]  ^/ i8 q( @. m33
34
35
36
; T  z4 e* h' b  c& C37
38
39
9 q8 P+ t3 U& G! x8 W  F; E40
41
42
43
# S; H8 H4 `0 y8 ^% Z, w! R+ \44
45
46
47
48
/ T" X" s$ U, I) W2 y" X49
( M4 R- m+ H# s7 U; S6 p50
$ Y  E. b( Q+ g' N# v7 K. C. n# v51
2 U; b& Q! V" d1 e52
53
计数排序
) d1 C2 j9 s+ r; p. i$ Y/ z找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
" ?  j) ], O' x; V, U2 X1 L# ~; D时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。


. p* l0 `% z7 V" e- B代码实现

3 C$ ]. ]: ~" n9 K
public class Solution {


8 ~8 c. i! z; T( V4 v" c" a        public static void main(String[] args) {
/ ?! ]7 B: H' L. `7 Q                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
- h; q/ S5 B# {+ }' w; G        }


        private static int[] countSort(int[] array) {
                if (array.length == 0)
                        return array;
               
                int min = array[0], max = array[0];
6 M  G4 \/ \4 v% H& @- i. \5 i               
                for (int i = 0; i < array.length; i++) {
- ~# r. p( i4 V7 J+ w" j                        if (min > array) {
                                min = array;
                        }
                        if (max < array) {
                                max = array;
                        }
                }
' k' j# A* B( ~# O8 I0 J9 _$ r               
- S/ O# }; t8 s                int[] count = new int[max - min + 1];
               
                for (int i = 0; i < array.length; i++) {
% n8 L1 _2 v1 o- u0 g                        count[array - min]++;
                }
7 Z# U# r4 T* P' z. \0 E               
                int i = 0;
                int index = 0;
- M0 N$ F0 @  ]                while (index < array.length) {
( A$ S7 e0 Z. ~0 W: L( X$ f                        if (count != 0) {
0 Q3 s+ a$ Y/ g+ r! p7 ^/ Q                                array[index] = i + min;
                                count--;
2 t4 T6 m7 m- H8 j! h( @8 m8 r                                index++;
6 u  j& s- k' }                        } else {
                                i++;
                        }
# |" j, a3 h4 A* r5 Q                }
" t7 _' J4 n% ^4 P9 k' u0 I                return array;
        }
+ f/ B; z0 o' H: H# m7 Y6 F( N       
' u* A+ o+ {' [/ ]# U}
  V2 L/ C5 I, T+ }& I& l1
2
3
) P3 k7 r8 L5 d: I2 r+ F' F4
; ~4 C/ w5 d+ L- b) k5
( m' \: l1 T* ]4 }6
  e& s( ~% ^3 |7 V# E7
' G* y# r2 {. H, m& p8
/ j1 Z( Q1 F9 y, b. Q% y. m$ e9
10
, ~- e! F& L# r! R* s11
. [. ?! x. D) s5 x$ t12
1 [- _5 N) u, u* P0 c* n, d9 V13
6 o6 ^$ b1 Y+ N! A% p14
$ s5 l7 s* z. I* S15
16
& j* P/ Y0 [2 Z( K17
  @% ?  i4 N; w. p$ J$ X, V* @18
19
20
21
22
23
24
: p3 p- z& c  V' e25
' Y2 e4 T5 v5 s( ^1 c9 G26
27
0 Q$ E8 |2 K7 ^! E) f28
. Y: R/ I6 _' L; `& W2 K29
30
31
32
33
34
( ^  _# r' ~8 O$ ]) a' ?2 ~$ x* [35
6 R2 Q% _" c% R6 Q36
# k0 y$ W9 O8 _37
38
) y4 Z$ _: L6 u2 p39
40
) F6 L3 \3 s" p+ e; }6 e41
42
43
44
桶排序
' h% C0 S' d4 M* k. x————————————————
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
1 t4 A2 a0 @  k- ^3 s: V原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153