十大排序算法（Java实现）

杨利霞

十大排序算法（Java实现）
* _6 z3 P2 T, Y# Q% T* F
十大排序算法（Java实现）
排序算法框架
排序算法性质
) e# F0 h8 c# k5 j. H6 ~8 ~插入排序
8 i( k/ b+ x+ T. ^; {% H7 j& z直接插入排序
希尔排序
! W' c( f' G5 z% Q& I选择排序
简单选择排序
! u* Q& y' W& z& t堆排序
交换排序
冒泡排序
快速排序
归并排序
基数排序
计数排序
桶排序
更多文章点击 >> 这里
" x9 m& x5 X2 t5 X! U) o% p+ W

7 E' f$ z5 D7 q排序算法框架
0 |/ c4 S2 J' U0 V


4 {. `+ ~* c/ B, w  B, U" Q
. w' N) Q' a; [. \1 {6 v8 p排序算法性质
4 y/ O. `+ T% U( l

3 e( C- r* h  E- X" y( g! `
# r! R' `( v6 m& K1 d8 l4 e0 g  O  r
( @3 T% v* ~. J5 p+ t' b" D插入排序
直接插入排序
从第一个元素开始，认为该元素是已排序的。
0 u8 H% N% T$ g" t* E4 S9 v- O取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
* b% c4 X# \" q% }5 u6 B, E最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2
; ?( k4 U; m% O! J ) 。

0 \/ t( P2 ]2 A  h; W1 [0 |
代码实现


& E7 m- V, q4 D% B* Gpublic class Solution {
        public static void main(String[] args) {
& n  b3 }" I0 }( i+ t4 A                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
$ {6 H$ @, S: [3 g/ f/ H                insertSort(array);
                System.out.println(Arrays.toString(array));
        }

4 r3 N8 z/ m! y& j; K
1 l6 h" u% n# ]) v+ Y& A1 t  _        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
5 c, O! F, H( u( y) p7 S                        int data = array[i + 1];
                        int index = i;
                        while(index >= 0 && array[index] > data) {
- @2 s4 |* M- @                                array[index + 1] = array[index];
0 p' K9 l: D9 I$ W0 H/ ^                                index--;
. @$ [* D+ s- P5 G                        }
$ M) v# |1 j4 v7 `                        array[index + 1] = data;
                }
3 N0 X- x- s- C2 Q# s5 Z        }
% L9 t0 u. W: B: M6 K+ d0 V" H0 P6 c}
  U! p' k4 |6 I' B& t1
2
% R  \$ s9 Q2 z) Z: j4 c. Y3
4
5
5 ?9 ?' _, @1 u; }6
( Z# ^6 E4 |- K7
8
9
10
. ^0 @2 o. S. q$ j; t11
6 W6 @, s- }. u- r12
; M  P3 R. H0 \# n13
: g/ S# T" d/ b" P7 F14
15
, d% m7 K9 m4 T( z16
17
18
, K' x7 K& b# k- |- N; ]19
希尔排序


时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
4 c1 |) p3 O# X1 V$ q
1 D. u  J& U# V1 O. F$ r$ J
0 F. n( H: b. }2 P% ]) `' I; K- g代码实现
7 `1 \! N( }. B/ y7 H
$ `+ m; f! m5 a' \9 O( M/ @0 }, n. Y
public class Solution {
        public static void main(String[] args) {
7 H2 @0 p( C2 F- V2 [  _* q                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
4 b" P# z$ B1 U                shellSort(array);
                System.out.println(Arrays.toString(array));
$ m. e; s! w1 y: {9 C( o" e5 H        }


        private static void shellSort(int[] array) {
                int gap = array.length / 2;
4 Z! i( x8 l. T' J                while (gap > 0) {
" B8 S. i, S# b! o% U                        for (int i = gap; i < array.length; i++) {
                                int index = i - gap;
                                int temp = array;
                                while (index >= 0 && array[index] > temp) {
. i& e5 d! c1 U                                        swap(array, index, index + gap);
                                        index -= gap;
* E/ `6 G- ?3 _- t5 M                                }
* |+ Z2 e  H0 x( H/ ?//                                array[index + gap] = temp;
" H9 O$ Z- l! W! y+ i9 _. L                        }
% m0 ]- p/ W( b0 b                        gap /= 2;
                        System.out.println(Arrays.toString(array));
2 m/ i/ r0 a3 }. d  q+ S                }
7 M" B) |/ X) c( J: c( ]0 W9 r        }
6 T! q; A4 R3 X5 H0 ^% C( x( ~

7 m; l, s, g) o$ P4 n# W. z        private static void swap(int[] array, int i, int index) {
                int temp = array;
                array = array[index];
                array[index] = temp;
        }
}
1
  _) w6 L+ q$ v8 k. k+ J+ A0 H2
3
4
5
6
7
7 z6 B6 e- `$ E( c  Z' l8 Z8
9
3 h( i% c# m( _7 T% x/ G4 s10
11
; u: G! R: P, E% {, k# S3 f2 w! ]12
13
14
15
16
17
18
19
20
21
4 O# X! T3 |6 d% Y22
23
24
25
26
27
" y; |4 m/ X, ]4 G28
, e: K0 p! I; D8 J7 Z4 ^# i. Y29
+ \/ k+ f. b. C, A4 ]/ f% O7 {; g30
+ H, E. k6 c7 K+ e选择排序
简单选择排序
从未排序的初始数组中寻找最小元素放置首位。
从剩余元素中继续寻找最小元素，放到已排序序列的尾部
: W" {1 X" g9 q遍历数组，直至结束。
) T3 d3 _. b- l! N7 z& D& H0 [时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。


代码实现**


public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
                System.out.println(Arrays.toString(array));
        }
, n0 K7 T8 \% @( [. [8 o# P

  F5 Y9 p6 W8 ^, A( w7 {* k1 ?        private static void selectionSort(int[] array) {
                for (int i = 0; i < array.length; i++) {
                        int index = i;
% x* i) K4 `0 V1 R: R0 U" ~* `  i                        for (int j = i; j < array.length; j++) {
9 R" h0 v( t! n% I5 \7 X                                if (array[j] < array[index]) {
                                        index = j;
" z+ }7 o1 T. Y. D5 e8 \, B" g& B                                }
% @& g7 r* U" H5 n2 r2 i/ S                        }
7 z+ l' k  q0 t7 _                        swap(array, index, i);
                }
- v( M& t+ z8 N8 }! \$ E        }


' u& B# X" R  Y9 W  s+ J+ c& ^4 R        private static void swap(int[] array, int index, int i) {
                int temp = array[index];
+ n( y7 a/ M2 U5 C# e( Z, {                array[index] = array;
% J% p( V) V- ]9 b                array = temp;
        }
$ t8 d% l5 \/ y2 x}
1
2
3
+ y# d4 X# v( E2 S4 e% H3 Z+ Q3 z7 n4
% O- z8 c* W/ O8 g5
9 Y! p+ m, m5 M6
7
' F: C" g* U0 p7 m, T5 A! z8
0 F; z% b) K& G( C9
! z4 g& j9 Z) d/ u' G* F10
11
12
+ e6 e8 l1 w% e  ^, A13
14
15
16
17
$ l2 ]$ u2 Z0 o+ [18
" @2 X' v8 L& L* h6 Q$ N: [" \: ?19
20
21
1 A, ]# G( \/ a$ b+ a: k22
23
24
+ P# @. r, Z' S; S4 F5 i4 `25
# A) \( m8 S- i. x1 u6 T3 K, N堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

( e% a2 b3 Q# v( w9 u
- y  q1 |6 F' T1 E5 x! N代码实现**
% U% d- K3 A; L  H
4 k% L' p" [& p! l
public class Solution {
        // 建堆
        public static void creatHeap(int[] arr, int n) {
                // 因为数组是从0开始的
, i/ q1 T/ H; H8 H4 Z2 E                for (int i = (n - 1) / 2; i >= 0; i--) {
. u% W# W& v9 x3 P7 Q! S                        percolateDown(arr, i, n);
$ k! S& g+ Q$ Q; U9 Z- f                }
# q$ d! ?8 ~1 b, P7 o) g5 ~. o: p! p9 P        }
0 b$ x( ~, [. }$ w7 c3 O& I$ E8 P) e        // 插入
; C& r6 \9 ~5 w8 Y" ]1 l& z) M        private static void insertHeap(int[] array, int data, int n) {
( L3 g" `" I* I6 I7 P/ c) `5 n% q$ |                array[n] = data;
                percolatrUp(array, n);
        }
        // 删除栈顶元素
3 G- e+ c( K% V7 o& h4 F2 K8 z7 q; `" H        private static void deleteHeap(int[] arr, int n) {
                arr[0] = arr[n];
, p* t# H4 D3 @/ f                arr[n] = -1;
0 s" N4 ~7 }+ _* I8 ~3 m1 f; j) E                percolateDown(arr, 0, n - 1);
        }
        // 上浮
        private static void percolatrUp(int[] array, int n) {
; I' W. N0 I! `2 i" I6 y- E                int data = array[n];
                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
. I6 B. e1 z6 ]# N                        array[father] = data;
                        n = father;
- M$ l7 m: R% u6 t3 d. j4 Q# b                        father = (n - 1) / 2;
                }
9 U3 |# g% V* D2 d5 q- J                array[father] = data;
        }
        // 下滤
        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
                int child = 2 * i + 1;
                // 遍历整个该根结点的子树
                while (child <= n) {
                        // 定位左右结点小的那一个
7 _; x( Q' ^5 g                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
                                child += 1;
: {) X4 f) u2 v  s# ~                        }
                        // 若根结点比子结点小，说明已经是个小堆
) M( t* U- J. R6 B                        if (father < arr[child]) {
7 v& I; T& ~' y- D% j; U7 w                                break;
                        }
                        // 互换根结点和子结点
+ e* B. l) f# ]; z9 v5 n* }/ ^                        arr = arr[child];
                        arr[child] = father;
3 \+ m( ~& ?1 _+ j4 H0 H0 j+ I: R7 Q                        // 重新定位根结点和子结点
                        i = child;
) L- X3 X5 G9 W- H! i8 _" g                        child = i * 2 + 1;
                }
3 B- H& I& H% o- P9 ~/ Z9 |4 `        }
   
        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
                creatHeap(array, array.length - 1);
2 s' E# m% |8 `7 ^* `                System.out.println(Arrays.toString(array));
3 \4 t0 J/ f6 Y0 g1 a; K               
                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
( @; P3 j) k4 Z% {: s" r! A: u               
                deleteHeap(array, array.length - 2);
                System.out.println(Arrays.toString(array));
) e) N2 t& p2 P( I- X8 K- c               
                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
' ?, r" e/ O! L' E6 U        }
}
1
2
3
4
5
/ y: X' M& ~3 |- s% Q$ X6
8 `, S6 B1 @/ c) w6 Z7
8
/ \) w: w; I5 q1 i; S1 E. y" F9
10
11
* b% i) |" g8 i. W5 l12
6 v/ b' e" j# J13
14
8 E$ p, I# p5 y15
2 N' ~* N$ H1 b4 D+ r% j7 @16
1 y  W: ^$ `' j; A' e7 L17
18
, K" q) l+ }$ Z/ P* s' s7 q19
20
# h; c: N' X$ ]2 s' O21
! @# q% n- G+ A8 [22
23
$ V  \/ U4 [; ]! s% F* f3 r' o24
9 E: M' S9 J- y: {* x  J% {25
26
6 _3 V9 K8 m; H# H; e- F- `27
" |1 v6 O! G  I6 W28
+ J7 g5 K% w) d5 K6 n+ U29
30
$ p& Z3 @* M, O+ O31
7 |! V: j) u; j% g* h5 O32
) ?5 \( ~: A2 V, ?6 b: Y9 @- X33
34
35
36
3 }; I( {6 c/ L. p+ [, ~* O( Z. d37
38
) k* Q4 d" @9 k: T0 h39
40
  |8 B( [3 f- L/ l7 i' s41
42
43
/ Z  x. |% M4 P& o8 L; y44
- e6 U& f2 H  B9 L$ Z% j8 G9 `/ O# c45
46
# l; ~* Z2 o5 N5 y% h! ^) P, Y, s; z47
- x. j2 ^, t) P; L& f) t# ]4 Y48
49
50
6 z5 {7 }0 C9 ?8 J51
52
53
54
1 ]4 Y: w+ c# C/ T55
* [  |* l; ~* T" C, q56
57
58
59
: l' {7 y/ m8 ^( _; m60
6 I/ h' G2 Q: G* u" ?" T; B61
62
63
6 x8 z6 }9 ]  |  ]( y7 @64
4 I0 H3 q2 C, V/ ]- [2 \65
66
67
68
69
70
交换排序
冒泡排序
6 f! P& G7 a- ?" v* F& ~依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
# Y7 c3 s' H" @0 d7 X遍历数组，直至结束。
最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
. u% k/ ]( E, S0 G ) 。


* b7 Q3 ^' i: O' y  x代码实现
& ?; J) ]# F0 C% V7 }% d8 U6 t
* p# d, L$ z% a$ j5 G9 q0 B
import java.util.Arrays;
5 }  E7 m6 h* F  \3 apublic class Solution {
       
        private static void bubbleSort(int[] nums) {
- e2 T  P- v6 g9 R& |; l6 p9 Q                // 循环次数
                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
. u' m- L; g' a+ e                        for (int j = 0; j < nums.length - 1 - i; j++) {
                                if (nums[j] > nums[j + 1]) {
. `! T/ V0 F% i  a                                        swap(nums, j, j + 1);
" g9 Y2 [1 p! Q+ K                                }
. D! P" u' `. ?+ ]: }                        }
                }
        }

. T' m) t9 b6 j2 Z, r# p
        private static void swap(int[] nums, int j, int i) {
8 O9 \* i. W; R. X+ e! U                int temp = nums[j];
                nums[j] = nums;
* I) L0 q* i4 W8 b4 V                nums= temp;
        }

! P) n! i* }+ \( a
        public static void main(String[] args) {
8 k3 `! p1 d8 o! t                int[] nums = { 6, 3, 8, 2, 9, 1 };
. |' \, k1 c# ]% |# F! L  K. r# i                bubbleSort(nums);
1 m2 Q: U: v. L0 }                System.out.println(Arrays.toString(nums));
        }
}
) s1 G9 E1 H5 w1
5 v  x  q8 q1 l0 }2
( y. ?7 k8 {- c* b3
4
) e  r  Z; r$ G$ {% ^6 f( r5
6
7 d& o  A1 W$ f9 f7
) D/ q/ n0 S# X, [" B* ~8
9
2 V; y& F1 Q; ^; ~% X10
, g  X4 i" f/ s) C6 U7 M11
12
13
( C1 r( D" m! g! c14
15
1 q  [$ P$ V/ h. c7 c1 ]( Z. t16
17
: k4 C. Y* I; z! U7 d1 G18
19
1 D0 g1 a2 z3 O! J) r20
21
22
$ d* _( ]7 u. s- J23
  M3 [7 m7 T, \% E24
25
1 K* y, }* U+ e4 m0 C& J3 \  m. v26
27
, D; h4 H5 O( A9 M1 r快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
: h& s$ i2 i" A& `, B: K, K9 V& |: B
5 o) Q8 b3 Q$ Z; w/ Y
代码实现


, \$ O; f0 @1 p4 K, f7 \/ c* gpublic class Solution {
0 _  J: m( M* m) M       
        // Median-of-Three Partitioning
        public static int selectPivot(int[] array, int left, int right) {
) G2 U. f  h8 D; Y0 C) T, ?                int middle = (left + right) / 2;
               
1 w. M' }6 `0 o8 \, Y                if (array[middle] > array[right])
+ \6 Z# D1 R9 J0 d% m                        swap(array, middle, left);
# i! c" E1 w  j; o                if (array[left] > array[right])
                        swap(array, left, right);
                if (array[middle] > array[left])
                        swap(array, left, middle);
               
7 ]' ~1 ?+ }1 t* Z( {                return array[left];
        }
       
        public static void sort(int[] array, int left, int right) {
1 A% L- D* h6 n                if (left >= right)
                        return;
* K% `: c3 a! ^                int index = partition(array, left, right);
                sort(array, left, index - 1);
                sort(array, index + 1, right);
, V! H+ d) {4 N* X( ?    }
5 c- p8 p1 J6 ]# }. N$ K       
        public static int partition(int[] array, int left, int right){
        int pivot = selectPivot(array, left, right);
        while(left < right){
            while(left < right && array[right] >= pivot){
$ g2 q7 q; L; ]) I                right--;
* K" |5 ?8 r4 Q! t0 r7 v8 Q' R            }
2 G. u; v. j4 d            if (left < right) {
( {( Z  o8 Q1 M1 M- ?                array[left++] = array[right];
  q* ?2 R: G: S& D            }
            while(left < right && array[left] < pivot){
  j6 b  i4 r1 \' R/ p: X1 p                left++;
+ p! H. I5 g' k$ N" D$ Z% f. C, {6 X            }
: v- J8 U) P# c! V9 L- o            if (left < right) {
                array[right--] = array[left];
            }
        }
/ w4 N, G. k- C' z' Y            array[right] = pivot;
. F# v) E/ V4 L" k6 \# {( F( d        return right;
    }
# I8 }8 n4 |8 O/ D# K

8 v! d4 e. K9 c5 P    public static void swap(int[] array, int left, int right){
            int value = array[left];
& e: |3 \/ K. U( \, L: b# K            array[left] = array[right];
% E3 B* k& d: }; d  }  q+ v7 M            array[right] = value;
    }
3 v9 a% v* ^* C2 E
' b+ N7 D, b) ^# |, X4 d$ p  B4 z
$ Y, F. z# D# e2 p        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
0 t+ l- X3 w7 C) K9 s/ f                // System.out.println(Arrays.toString(array));
                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
5 p, G  L" ?/ g  l0 I        }
}
1
2
- S2 f' {5 U+ T5 w7 m  w; S  o; i3
! V) [7 q5 s) \3 O1 t# T4
# g% S4 I) x( x* z: t5
6
7
8
9
7 \4 h. {! ?9 q10
4 v4 Y7 S+ d; v2 C11
3 s. s0 a1 k/ \, S12
13
14
- R4 p# Z" U* V* e15
; r( M: E7 t; D2 V" D: x16
17
18
19
20
% H7 }% H  d) R- {: u" {21
22
23
  w: @9 X7 @) d1 C, n& ?24
25
26
27
28
29
30
4 n+ H' W* ?+ n/ h! X  t31
32
8 j6 V) v% }6 r2 v4 F; B3 I" F+ k33
34
35
36
. Z2 B. f; ^* n" a- t1 d4 Z. \+ _37
38
39
40
41
9 z; j+ r2 w% |% A7 ^; j42
( B8 b% C, E; T' W43
% I) T2 s" H# v1 A" o- E' M44
' u% W5 e: j  d( k% X( T& {- S45
# v, c8 F! y  W9 w" v46
* A" i9 C. I% g5 ^2 r* X47
+ b0 q6 `) H4 f48
49
; \3 R) m. @; S$ v50
. R& P; Y& V0 g4 z/ E51
52
53
54
6 W& L5 C: T6 t9 {& L+ R! d55
56
57
归并排序
将长序列从中间分成两个子序列。
  `% g4 f; N$ b+ n% l对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

9 P7 n2 T- c8 }! \& z
代码实现**
* ^2 d; I: Q1 O6 I3 o
* Q4 E6 V8 |4 Q5 O) _
public class Solution {
4 F+ h: ~, L8 J! s' a2 I        public static void main(String[] args) {
2 @; N. d' v$ q% z2 B4 b5 m                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
: Q3 W" w% |1 `: y4 ?9 C  E) Q8 K                int[] arr = MergeSort(array);
                System.out.println(Arrays.toString(arr));
0 v# Z  O: o% o5 c( N# o: f7 [        }
# M* N2 _) B6 ~2 @8 R

        private static int[] MergeSort(int[] array) {
; Y9 t1 S9 w5 U2 p& K' P                if (array.length < 2)
- u  L1 P6 F& J( E1 U; G; A6 ]                        return array;
- G. W% e/ }7 B( `                int middle = array.length / 2;
                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
4 j  f) s/ d2 \3 X                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
7 p) c6 U; }! z" u7 Z0 w. C                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }


        private static int[] merge(int[] leftArray, int[] rightArray) {
1 J; r& J4 Y* |* _% O5 {3 S! Y! y" {                int[] result = new int[leftArray.length + rightArray.length];
                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
# n' D4 @( B! i9 F" q, y                        if (i >= leftArray.length) {
- p( W# j9 e% z% A, X' {, z                                result[index] = rightArray[j++];
+ |/ c/ K& z5 `, {                        } else if (j >= rightArray.length) {
                                result[index] = leftArray[i++];
% L% f- y% E& c                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
' k2 o7 O7 K! L8 L* Z! n. ^                        } else {
                                result[index] = leftArray[i++];
! e' G5 n3 G, s% T                        }
                }
% f" v4 }1 Z& ]! ?! s                return result;
        }
}

8 C& c/ q) ~' \4 X0 ]) c+ D3 V
1
3 @: r9 n- w: W- Y2
3 j& A' G3 [5 p' {7 a, z+ U6 F, Z3
4
- i' z3 W' O# R8 G5
6
7
8
* D, C) C' J! y6 D* C9
( E( Q3 Q) Y7 x9 |6 |10
11
7 a" D% z3 ~; P6 K4 ?+ d8 y/ g12
13
14
15
16
' ]8 q% V+ m- I6 o, u5 m# K17
18
19
2 I  R9 {7 y0 K3 E. x) K20
7 r9 A' }2 F& H7 {" J. ~6 w8 B21
22
23
  Q+ t4 w) M9 y+ O24
+ J/ m: C9 B* k* l2 Y; G25
8 X% p# f. Z4 E: e+ [26
27
0 j1 l+ B" @- x. [, _9 g0 K  e& M28
29
30
31
32
0 [4 O: L2 j2 J33
基数排序
找到数组中最大的数，确定最多一共有几位数。
( F" D4 L' u& R# P0 v  E8 q0 X" J按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
% y: z5 W! ~4 S+ s% a0 V- q. R时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。


% ^$ S  M$ g7 M代码实现**
6 |. K1 v5 g2 G$ n) N
" O' v/ N9 d$ d
) r) ?1 Q7 F5 Z% Tpublic class RadixSort {


: G7 O! E2 b1 t# i7 L+ n$ G        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);
                System.out.println(Arrays.toString(arr));
$ H2 P, o4 K( A9 }/ x. r& w        }
8 B: N' r' o* p+ {5 C

/ n2 a$ U, h/ K4 g6 x        private static int[] radixSort(int[] array) {
( w- j* g: A+ g9 ]8 n: s0 b                if (array == null || array.length < 2) {
                        return array;
' R2 R7 s% K5 O                }
                // 根据最大值找到最大位数
( R2 a% u7 k) K4 h                int max = 0;
- Z+ K$ ^* X3 O( g+ h8 p! C' i5 O' X  e                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
                }
               
# W) L0 l/ V+ e6 V+ p# J1 z5 H                int maxDigit = 0;
' Q/ W, W2 [4 a6 a3 `, W% v& K                while (max != 0) {
3 q4 W& h0 i: k! m                        max /= 10;
! }7 y8 S3 Z5 P" b) C5 F                        maxDigit++;
                }
: W( v, J3 ~1 c4 k7 ?' v8 t) P               
  m. l" z. @  j! U! Q0 B- }                // 第一维: 0~9
, l" e' i8 J+ d3 U                int[][] radix = new int[10][array.length];
& ~$ S0 |* C2 y8 \" T                // 该位为 i 的元素个数
! o; S; D% L  R4 T" \3 l" D                int[] count = new int[10];
               
                int m = 1;
                int n = 1;
# J, N* w% g( Y0 [- v3 F               
# {1 `- d! h5 Q, g+ L7 G. o                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
                                int lsd = (array / n) % 10;
3 J% J5 f5 }" v2 z                                radix[lsd][count[lsd]] = array;
                                count[lsd]++;
( O5 g8 h0 y9 L& j8 I. k/ S                        }
                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
7 N3 R) y& ], e/ C                                                array[k++] = radix[j];
1 \7 n+ `! p4 r: K8 V: r                                        }
                                }
  D' v+ H& q( ^- Z) ]                                count = 0;
/ M$ J6 M3 ]4 [0 d; @5 G) y                        }
                        n *= 10;
                        m++;
                }
! e, t) K/ E7 r& L$ T9 C* U7 d                return array;
! w4 v0 P1 J, Q0 O1 S/ P; k        }
2 g4 Z5 c8 p: r1 L8 e6 l

7 W9 s$ ~* b4 z}
1
3 I5 F. C3 A: x- o2
3
% ]1 {6 [3 ~! W9 e2 y- I4
5
6
7
& K4 U$ ?; j/ `# R- w8 {/ ^+ D8
9
10
11
12
13
- D5 f2 d% _9 X" o* B3 A14
! s$ h, N1 W6 y2 m3 K1 P+ n; T8 b15
& m0 _5 k: I1 ~7 O16
17
18
19
20
21
22
23
24
% P8 o% S5 i; L) Z25
26
: m4 S9 z! A6 C8 z9 W% J& v' _27
28
29
  `+ |' A- g/ \: h30
/ \4 F7 k: f/ H0 I31
* I. e; s# D! Y5 w32
( T- q6 u7 r$ X33
- x$ \5 |7 U# s7 ~4 p+ g0 |0 J34
35
; t1 W2 w+ z& B0 ]36
37
38
39
1 u+ j( T. T2 p8 w! B6 r0 {' k40
( h( C3 M0 |5 U( y7 u7 D41
4 `4 Q! d$ J& Q8 t+ f42
43
44
, D( |* ^  _& h5 J45
( x- B) k/ J7 k1 `: p9 U46
47
1 v) K4 `# ?/ I; s0 H& f48
49
& s. x# q' v" g) H  S0 {4 ^0 t1 A50
51
52
/ ?/ L9 S" J% O+ N. h( Y53
& g: G7 G' [( H: _4 N/ M计数排序
) |2 w; r& t; i5 b找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
( c  I+ z5 I+ U最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
" c5 g- y0 q9 \( n时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。


代码实现

" O3 U2 y9 h8 T+ h* w% Q6 R
4 ^9 W2 d8 j+ {4 T8 m$ mpublic class Solution {
) O# C. r9 E, C* [) c  s

        public static void main(String[] args) {
" J" y3 H* ]8 c' g7 e6 C- d                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
3 p, A2 `) u& v$ w        }


        private static int[] countSort(int[] array) {
+ k# d9 v' y- s0 `                if (array.length == 0)
                        return array;
               
4 E; B' E- g. M2 P( m$ ]                int min = array[0], max = array[0];
) n7 l6 Q, Q. Q! v7 C& H7 U: M2 h: e               
                for (int i = 0; i < array.length; i++) {
6 d6 W; s! l( ]& l5 A! Q                        if (min > array) {
                                min = array;
' }( O7 o+ |' p7 J/ q) y- i7 g                        }
                        if (max < array) {
' w, h7 Q; ^* }5 j. L# Z3 B; [                                max = array;
6 s/ C+ y+ c3 S5 e) m" i5 o/ _4 z9 A                        }
                }
, I$ {# c& j/ Y5 a5 D  [" x               
& L) F, Q' Z$ J0 C; c& L                int[] count = new int[max - min + 1];
               
                for (int i = 0; i < array.length; i++) {
' d! v& h( A: j- ?& r8 b& b# R% c                        count[array - min]++;
! s5 E, Y/ i4 U6 x7 C3 A; Z                }
               
. m) ]! \2 k7 L# F8 Z( E* w                int i = 0;
                int index = 0;
9 |  n( T( u% s( F4 ~2 y                while (index < array.length) {
3 V( Q- G9 [. E7 l) g; _/ _                        if (count != 0) {
+ q  s2 J) z/ y* B+ ~                                array[index] = i + min;
                                count--;
                                index++;
                        } else {
                                i++;
* g3 A% k8 q, C8 ?1 n- C4 d1 v                        }
                }
                return array;
        }
       
}
1
2
3
  P: B  u5 _4 [  c( t4
5
9 ~+ g- |& h( F5 n1 {# Y6
7
8
9
10
5 C- C  d- Q" K+ u* |+ u11
12
$ i) p# \$ V0 ^! H' g1 l% K  Z13
14
+ E! L8 c4 v) X* m( J* ?% E8 w- f15
1 [( _1 y* n! r4 Q' p7 s( n16
* Z3 J2 T8 V( X  Y6 K" b0 N17
* o) V; _& j0 J2 i18
19
20
21
22
* u, s8 k3 Z! T/ F; B6 P23
# |% |2 h% G' C% ]9 X0 [24
' u- a, c0 U: U/ P% H# C. ]# r25
& w( r7 j) |! r; i/ O4 v5 S26
27
28
29
8 E* R! `5 G" X30
3 r" }- ^& r3 p7 w; v( C; ]31
0 \7 Z: c. }/ D# X- Q( Q32
33
5 F9 ]) ^+ p( G& T8 O7 H34
" w' ]1 l$ c5 x2 g- o35
& d3 W/ ~* v$ M  v36
37
38
6 t% l! ~2 d9 {0 d5 w/ ~! A39
40
" M1 o+ t( b5 W7 V$ i+ @1 L) e41
42
43
44
1 @+ J- J1 z! r; [; o1 D桶排序
————————————————
8 ]! t2 Q; c# A! V3 e% v. f" A版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! X! G1 t' O) P# O原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153

7 r3 l. c8 G: [' G3 F' |
4 N% N8 R1 f/ n" i6 m