数学建模社区-数学中国

标题: 十大排序算法（Java实现） [打印本页]

---

作者: 杨利霞    时间: 2021-7-14 15:14
标题: 十大排序算法（Java实现）

8 U0 H/ w. e% ~0 v2 G' L( ~$ ~7 A# T十大排序算法（Java实现）

十大排序算法（Java实现）
排序算法框架
$ x! {0 i- }4 Z$ q3 s; k! w排序算法性质
- t  W4 \3 b, A: g) |. P. {7 c6 i插入排序
直接插入排序
& `: X; Y2 [' E$ x! {  V希尔排序
选择排序
简单选择排序
4 R! K5 p9 f9 }& d* [堆排序
  S7 E3 ~5 x9 a9 H8 m9 ?3 d2 }交换排序
冒泡排序
快速排序
$ F$ r# {3 N( ^' A/ Q) y1 Q归并排序
基数排序
7 C+ g* w" \  ~& O* C& ~6 X计数排序
桶排序
6 T+ o+ }4 a1 h% C7 ?2 A: k更多文章点击 >> 这里


排序算法框架
! y8 k/ H: ?8 C5 Y8 ~! [0 Q
( N' m  A1 d2 R

# C6 S' M% `* f* s
$ t; u) ?$ D" }  [0 T排序算法性质

& {8 F+ ?# r( h2 {2 n5 a7 D0 N
0 k3 |( h6 J% o& i

( h2 _, ^" h4 j2 Y插入排序
直接插入排序
9 t. I1 d3 J  Q从第一个元素开始，认为该元素是已排序的。
取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
) @* p8 X& ]+ o0 b# d5 ?/ z最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
  R! i# I7 Y1 j) }8 u2
- L1 G! a8 k# d ) 。
6 I5 j6 B6 Z. G' ~" ?( H' O
& E5 Z) x, J0 `* m( c
7 }7 d4 F" S! Y, z1 s% c代码实现


# t! w) w) g* N3 ]& dpublic class Solution {
        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
% @, H- x0 F' Q( [6 c! o                insertSort(array);
                System.out.println(Arrays.toString(array));
        }

0 _9 U1 i4 z  X/ ~
        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
                        int data = array[i + 1];
1 _" n0 y4 c/ Z: [8 @( c- B4 d                        int index = i;
                        while(index >= 0 && array[index] > data) {
                                array[index + 1] = array[index];
- h  @5 Q% t8 M3 A- g* g                                index--;
% ~) l1 B4 T$ J                        }
                        array[index + 1] = data;
                }
        }
}
2 w! z3 p" ^" R; R! T* T7 K1
, g  s2 |7 V8 F+ T. \4 y/ n2
3
4
5
6
$ M- d" H" C( A- _& P0 L  v7
) q5 v) Y5 H9 K0 r9 M, y8
: C+ v* t$ Z* o4 {9
10
11
: o6 X9 B% r2 z2 \. V: h12
) M) ]8 Z* Q. q3 Q  V13
14
15
# b& o, C; {8 G) `6 E# s* [$ q& Z16
) v* j8 \# D/ D. T2 W! W+ S# N% h17
0 O! Y+ m# j' j! u% ?18
, a, ~' p1 N+ ^3 q19
4 Z4 s. J# C  \5 r2 |希尔排序

# C- q$ V; J7 \4 X* j, t% m
7 e- A/ ?3 V' y0 ~+ b1 t- W时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
& z6 z* ~+ e+ ]$ x

/ h! m; f, }( M9 `代码实现
% c& b, p7 _- P' U6 H! e% g  h" P
/ p. c1 y6 X  n& k2 _4 }
public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                shellSort(array);
                System.out.println(Arrays.toString(array));
        }
9 Y- v) Z; a; ?) G9 D& M

        private static void shellSort(int[] array) {
, M* L  a- i: ~: o! A# J                int gap = array.length / 2;
                while (gap > 0) {
, B3 m0 h9 O& w                        for (int i = gap; i < array.length; i++) {
# R3 I" s. S+ d7 p                                int index = i - gap;
) c6 v/ w% D8 t9 B; T                                int temp = array;
, z1 l0 @" T, |                                while (index >= 0 && array[index] > temp) {
                                        swap(array, index, index + gap);
                                        index -= gap;
2 R& O" |: X/ t0 [0 G8 k8 N- W( _                                }
//                                array[index + gap] = temp;
                        }
) Z6 F# x+ K+ m  S$ m                        gap /= 2;
                        System.out.println(Arrays.toString(array));
& z2 P0 e' ~- M5 E, Y9 g6 ], d                }
        }
# M* X. s. q% L$ A. d& x
, }! t# @' w" @% z! P0 v8 d
9 w+ [8 s, B' {        private static void swap(int[] array, int i, int index) {
                int temp = array;
                array = array[index];
! C+ e( G8 e+ |$ ^1 G                array[index] = temp;
/ v  m7 x; f+ j0 D4 U9 {        }
+ U0 W8 h5 W0 Y% c1 G# t}
! X( L9 c; H# L0 @1
2
+ N  Z1 ]$ m% c4 g* K3
: r+ d' ~' ^2 Z; }4
5
4 N! z( B7 {* y6
7
4 T+ n3 e! w* c7 M8
9
10
11
12
13
14
+ S! u5 b9 m; `8 v  I4 J1 V3 U9 U15
" f% v. E1 e; O6 @16
8 a# |5 @4 c+ l9 U17
18
* M' O9 i  ]/ I+ e' i$ @' H  N19
' v$ T( L" V8 V$ t7 n4 @20
21
22
( X! F6 u+ X( g  ~7 d& h23
# i  O* ~4 ?8 ^24
, j6 E9 K8 z+ \+ c" v$ B25
9 P, j! [- C9 T3 Z, e# T# i; V: \% @26
5 y& @! k4 z+ B8 \& @# m% Z8 T. z27
28
29
30
选择排序
简单选择排序
4 W' z4 |3 y( q6 H从未排序的初始数组中寻找最小元素放置首位。
从剩余元素中继续寻找最小元素，放到已排序序列的尾部
: x6 ~7 k1 ]8 A$ E' a5 r遍历数组，直至结束。
时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。


代码实现**


public class Solution {
7 e  g6 z& L8 p0 E& m( v# g3 L        public static void main(String[] args) {
# r/ T0 B+ ~) ]8 `$ F                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
                System.out.println(Arrays.toString(array));
' D; o( `% _; N2 i        }


: ?1 {+ e, P( f6 _# O4 s; g' L        private static void selectionSort(int[] array) {
/ [2 @# z0 ?) C; a' J                for (int i = 0; i < array.length; i++) {
- ?& T! j; b$ |) C- G# L8 E& m                        int index = i;
                        for (int j = i; j < array.length; j++) {
' O( y0 J5 M. k1 l6 [+ H/ m, N                                if (array[j] < array[index]) {
                                        index = j;
                                }
! a/ H2 ]. ^0 f: K; E4 o                        }
1 z: E8 ?% R; Z7 V+ [) P                        swap(array, index, i);
) x, g6 [- U2 ?: H                }
$ i" x, z2 c  m, Y        }

- m0 F6 O: N# Q. D4 r: V' [
8 @  q: G: Z: P' m- M& ^6 q        private static void swap(int[] array, int index, int i) {
# n: R. H" g. |; e# O                int temp = array[index];
; V( b( v" Z0 L& U- D                array[index] = array;
; V4 |! N/ v& {, Q                array = temp;
        }
, U6 P& S$ o/ e8 w% A+ j5 o}
$ S* m7 F! j  z2 C! T8 G' S1
2
; a: p& ]( A8 O7 k; o3
4
5
2 U4 h0 K) ^% \$ Y9 S3 U6
; |! g% V: i5 `5 ]% h* D# F7
8
6 j( u1 E- l- y$ H) e7 r0 f9
  w/ d4 d! E+ M! _' w0 p10
11
12
13
14
15
16
) Q! s. x" _3 {: k6 k17
* U1 y8 G5 m) J6 v* {18
19
20
, ]: _7 l+ J6 {6 R: x21
1 R- k5 h+ T: b: m5 Q22
3 S% z0 x/ E  w) ^$ T* N23
3 }! Q( P' Y0 ?, d+ G9 i3 R24
* Y$ g6 Z5 s% L, c3 K25
堆排序
, _4 N' t% Z, y$ G" Q3 ?( H6 W1 y7 i时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

' ]! z4 b$ X3 Y4 V; y4 `  s
代码实现**
' j# U7 n% \+ ]
" ?! ~: U" G) b4 j# F
  i+ l, v7 c' o7 u1 @' _5 ~' F/ Jpublic class Solution {
        // 建堆
        public static void creatHeap(int[] arr, int n) {
4 u9 q. k. ]+ R- Q$ Y  g- i* e                // 因为数组是从0开始的
, Y% e7 K( y+ Q) V& a                for (int i = (n - 1) / 2; i >= 0; i--) {
+ u7 J, C9 N" D: z3 H$ M                        percolateDown(arr, i, n);
" S' V8 a/ P$ z8 z                }
6 s& u1 j1 r3 S* {9 N7 T/ a/ I  g+ g) E        }
, t; c7 t+ x. }% I+ R$ ]        // 插入
        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
  u5 O: s7 M; [" `4 G* W6 W* W9 L                percolatrUp(array, n);
        }
        // 删除栈顶元素
1 B% j6 m5 [7 T; L- c2 l: k2 L        private static void deleteHeap(int[] arr, int n) {
0 n7 _; z0 t% S                arr[0] = arr[n];
9 t2 \0 a+ _) J8 A5 k: t5 R                arr[n] = -1;
                percolateDown(arr, 0, n - 1);
4 n3 b3 G& }, e- c% r3 U6 v: V. s) ^        }
* B  F1 u: r' [" h2 ^" V8 I" g        // 上浮
; v/ ?4 Q' P$ a$ g. J4 r) G        private static void percolatrUp(int[] array, int n) {
                int data = array[n];
                int father = (n - 1) / 2;
( P, O1 p0 s. O# h* N; J0 R                while (data < array[father] && father >= 0) {
$ x8 e3 p2 Y6 D% D1 C                        array[n] = array[father];
: t+ u$ w6 {. e' r" O" [  y0 m                        array[father] = data;
                        n = father;
                        father = (n - 1) / 2;
6 E" z! f1 Z% B, U' x" I- R1 Y                }
                array[father] = data;
1 n- x- f- I: C, h        }
        // 下滤
2 h. @& @/ r# x3 k        private static void percolateDown(int[] arr, int i, int n) {
" O6 h' ^% a/ y                int father = arr;
( P5 s- _7 l+ ?' l1 y0 U( N                int child = 2 * i + 1;
                // 遍历整个该根结点的子树
6 E+ K  a: F2 \. Q) }5 f: s                while (child <= n) {
                        // 定位左右结点小的那一个
0 L5 b# f3 R& \: Z; T                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
8 [& y: Q, x! z0 s3 b% D9 ^                                child += 1;
) j6 }6 `# ~6 f) l# l                        }
                        // 若根结点比子结点小，说明已经是个小堆
% H! M+ q: L( x6 i* a! w& m  N' r                        if (father < arr[child]) {
                                break;
                        }
: K2 j) q' w0 `3 M" ~  O, A' X0 A. Z                        // 互换根结点和子结点
: @# u- k6 G8 D, \                        arr = arr[child];
) t1 t5 R2 @: G; }! o. s                        arr[child] = father;
                        // 重新定位根结点和子结点
4 o8 b! M% Z* }4 V8 z1 V                        i = child;
                        child = i * 2 + 1;
                }
+ ?. f" ?! B! U# c2 J# N        }
   
        public static void main(String[] args) {
8 J. B# J7 H0 l5 ]                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
: P6 V. p' l' X' b. d2 s                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
0 w) |' Y9 G; B7 [               
                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
) s8 Z, V/ r. ~5 I  o- X. p# b               
                deleteHeap(array, array.length - 2);
                System.out.println(Arrays.toString(array));
( E( D/ ~# J9 z. s# |; P               
                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
' _9 [! e: Y( {4 r. W        }
}
1
2
/ x% k% |5 \( `3
0 C1 \6 d. a' k) v1 S4
5
6
" \2 p3 U# F/ p. ^5 L& O& g8 `7
8
+ Q0 a1 J; d' i. L* R0 i9
0 {* m, q1 d7 z7 ?# G10
11
( x* B# ^: k. s* Q: Y7 }0 n12
13
14
15
3 f: X0 h$ ?. {16
. S( S6 ~) r4 h. |# }17
" U  f7 |( e- g+ @4 P18
19
. u4 [& f$ t3 D% X, s% l20
21
- K! Y. ]$ N9 n22
* a  W  Z* Y- ]: x! k. S" \23
24
; w$ c0 V* i+ h4 L( g3 n25
26
27
! F# r7 h) ]+ E6 e2 V) f: c' g28
1 C9 N# k9 g6 r* O29
30
31
32
- B; a3 y+ g) x' a* @: P5 t6 r33
34
/ U1 W0 n9 a( x35
36
3 E) `5 C' O( j37
38
& W$ ^) C5 J4 l/ `7 Q- [3 L, R( |* z39
6 G" f9 R, B* j6 m0 E40
41
42
: a! I6 t, v2 R4 v# b$ Q2 N3 C( m43
+ V4 p+ C& H1 s6 `$ B! e44
45
% |* g  Z$ R( O1 [4 Q- j46
47
48
49
50
2 [) \0 w9 g% Y5 o51
52
# z3 ]6 U; @7 K* L53
54
* L. {$ }+ r% E2 I7 F: l3 q  _/ A' p; N55
, G* {: A" J( D( u& S( g56
9 |$ I% X* P" c1 t+ A57
% Y: L  x" m* k' E  h58
6 j; O( B* z8 i59
/ v5 c; l% m  F; W1 E60
61
- n$ b9 t: s% M/ d+ X6 H62
; W$ y3 h' R9 {63
64
65
9 `8 s$ h  r! h# e+ P66
3 r. }: d! {; v& p67
$ i- `' T( _- l! j68
3 n8 o* i- ^2 X. t69
* n8 s3 T( j, q  L% b  Y: E) ?' g70
交换排序
/ G4 W3 B$ p" L5 x4 b, y冒泡排序
) Y' \6 c$ L3 W4 l7 U# N依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
( J* ^. i' E5 v+ u% K3 K/ L最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2 z% Y) C0 F0 X2
) 。


" v9 b+ ]* n2 N" [! C' l代码实现

$ [) w% c/ @" m/ ~1 U, F: L, \# [( Y
import java.util.Arrays;
public class Solution {
; }7 t$ U5 G4 H- W, \  e: i       
        private static void bubbleSort(int[] nums) {
' O) ], ~. d$ t, x                // 循环次数
                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
( Y; v$ y9 d+ c8 U/ \0 T2 K& L                                if (nums[j] > nums[j + 1]) {
                                        swap(nums, j, j + 1);
                                }
                        }
                }
        }


        private static void swap(int[] nums, int j, int i) {
5 i7 X! U* f9 J- V2 D2 `                int temp = nums[j];
                nums[j] = nums;
( c* A) a  s7 H! l1 A7 l* v, K                nums= temp;
        }
; P& R1 W, c$ p4 @# Z: |$ g: N
$ O  T/ V2 x$ T" w9 s+ {
3 u1 `9 W  J6 F8 z2 H7 g0 E, p  h; [        public static void main(String[] args) {
                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
                System.out.println(Arrays.toString(nums));
        }
}
1
7 _: A' x  B" T3 ~( C6 G' e+ X' p2
3
8 ?# m5 y  L2 p+ J# U1 S8 J6 u6 v4
5
6
7
8
" k- @& X! Y7 n( q2 F& w5 K9
10
0 y8 H. h4 O& E, |9 h6 z) j, T11
" _6 g% }, ]/ K! l8 O8 x2 _3 E, J! k12
# ]1 N- I' m; p  r5 w# c" ]# u' Z13
; E! N% j5 ^  Q8 B- ~14
15
3 g. s/ E4 d, W% H& q( ~4 y' ^( _16
/ r2 j# X9 a* t" R17
( e2 u: w$ g5 Z% Y* `- Z) ]! J18
19
; K$ L3 C9 [( ]4 ^0 |# M20
9 _$ v4 M) q8 R21
22
23
+ B2 ]. {! K2 K4 }  x0 H24
5 z3 D4 F) A% d" ?8 G% Q7 X25
26
27
: j$ K4 i+ @: r8 a& E3 x, j9 }. O快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。

2 f/ T$ k6 e5 J8 S' F" y% X
代码实现
- z/ p# P  r8 \' d
& D* a  S5 g8 H+ B3 A( h
public class Solution {
, |) u# }/ A. R0 E9 W  B% D       
        // Median-of-Three Partitioning
        public static int selectPivot(int[] array, int left, int right) {
                int middle = (left + right) / 2;
4 j/ @2 e8 R$ F4 |. O7 n. n1 K               
1 `8 H+ B  {7 f+ b4 @+ I                if (array[middle] > array[right])
                        swap(array, middle, left);
                if (array[left] > array[right])
                        swap(array, left, right);
                if (array[middle] > array[left])
                        swap(array, left, middle);
3 j; H, Z/ [9 a& O               
                return array[left];
        }
+ ], D4 Z$ O- {5 y* ^1 [* e       
4 x7 R' w! M; G" _. f  O        public static void sort(int[] array, int left, int right) {
- S; z5 ^9 Z3 \) e+ @* ~                if (left >= right)
8 ^8 T( j) D$ d8 e! @                        return;
5 W3 e7 W. F  A                int index = partition(array, left, right);
* d9 }+ a- _1 T  W& v" b4 i                sort(array, left, index - 1);
+ `9 w$ V6 S; d                sort(array, index + 1, right);
  b* |# ]  {1 n+ e/ @    }
/ z9 f: y. ?  _$ F& W- E  A  l" ~- B       
+ z/ z+ {7 A' l# L9 P$ l        public static int partition(int[] array, int left, int right){
        int pivot = selectPivot(array, left, right);
        while(left < right){
% z% _; w" {! G" e# u* L8 e            while(left < right && array[right] >= pivot){
- ~: s  c- w8 T8 J8 ^                right--;
5 B  l2 x) B- Y8 i& z            }
            if (left < right) {
% J% R, }1 Y7 h  k  Q6 r3 @                array[left++] = array[right];
            }
& _$ D- z8 e- e+ G            while(left < right && array[left] < pivot){
                left++;
            }
            if (left < right) {
                array[right--] = array[left];
% I3 @8 Q- j* u) s% n/ Q( d3 K            }
4 V( L+ ?. F' b4 e# P' l        }
) N) C2 I5 t- p1 u: n9 ]  X# [            array[right] = pivot;
: W( _, ~$ W& q- X" e, U9 }* _4 S        return right;
    }


    public static void swap(int[] array, int left, int right){
            int value = array[left];
/ W8 [) }1 a  z7 `0 z( j# I            array[left] = array[right];
; F& o# C- r, W$ P, E            array[right] = value;
    }


        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
0 e+ _% B8 J- n. B+ U' A: n                // System.out.println(Arrays.toString(array));
, t7 f) u6 q. F3 L: W. l                sort(array, 0, array.length - 1);
* t( @! C5 }3 T. ~8 Z5 `$ i% b                System.out.println(Arrays.toString(array));
6 x  {: u5 a; a        }
}
1
2
0 j4 c) n( n& ~7 N1 E& d3
" l$ r# z8 b. m3 F1 Y1 p, j4
5
# s% ^& R0 d' Z- `7 `) R7 `6
7
$ L# a) \9 u/ h) ?5 @" N6 g6 G' Z/ V. d8
1 q: i' E$ K1 c4 K4 p9 G9
$ M, m) }% m; a10
11
12
13
14
( d6 ~8 ]) U+ I& m; v# q! Y6 k% U15
16
17
18
19
% c8 O( R* z# v20
: O: x' |0 J4 D) R5 F2 R9 w21
! |, ^+ v" Y  ^5 M' y# u3 f# O22
23
24
" P9 D5 ~6 [1 [- V6 [- B25
26
, J- G8 f, d, d27
28
1 [0 c3 W! m( I- H! D2 P6 |! A+ i29
# D2 S# i: \: q3 u30
: b. v5 A# `& `31
32
33
1 M: R+ B! T; M# K: q34
35
2 M+ D& O0 D$ S/ d! ~! W8 ]36
$ ^3 @# B) f/ k& I- G% u+ v37
38
  J  v8 C5 P: p39
40
* F4 }9 L, ~5 E5 k6 [41
; x! B1 b3 N- W6 }6 T42
' g- j" `; P  k: q43
44
45
, H& ?; f4 E) p  L46
47
/ G9 a1 C( R: p& o* Y48
) L& Y% E  B- R- C0 R+ D- E' ^49
  ?! z6 Q; O, y- W2 `50
51
52
- J6 [" O: p! \3 {0 k53
  U9 M: ]8 ~/ O5 a% \  p3 q54
0 |1 F5 W0 F+ p5 T" {" ~6 A* G( j55
56
1 X( V2 f9 h  o: q& ^% b: p57
归并排序
( l' ~; e! \6 |# `) d4 a将长序列从中间分成两个子序列。
+ g) g  P  {9 U9 b6 p对这两个子序列依次继续执行重复分裂，直至不能再分。
3 B- j! v7 ?5 l/ o5 s; {: Y递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现**
6 O  {, [+ }  G& Y0 K
  C$ j0 N0 \6 D
public class Solution {
" D- j5 X( s$ d+ p( q        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                int[] arr = MergeSort(array);
3 w7 B: L: n: h6 R* P" c                System.out.println(Arrays.toString(arr));
        }

8 f2 ~  w. w) C
. M7 b; L3 N4 Y; w* h3 ?& _        private static int[] MergeSort(int[] array) {
$ W  M2 `4 d' w% R0 \, M) A8 A                if (array.length < 2)
                        return array;
                int middle = array.length / 2;
2 i) O% E7 G8 t  l) x                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
6 L) [( L" ~/ n- V( J3 K/ d                return merge(MergeSort(leftArray), MergeSort(rightArray));
        }
+ {% F! \" [: w

        private static int[] merge(int[] leftArray, int[] rightArray) {
2 j4 Y& E" E! y' y* k9 ], {                int[] result = new int[leftArray.length + rightArray.length];
                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
8 w0 I  p6 F2 H' d1 j/ ?3 Y                        if (i >= leftArray.length) {
% Z/ g/ R% d9 n7 E2 c; @                                result[index] = rightArray[j++];
4 N1 ]8 g9 B: w( ]+ m: L( [                        } else if (j >= rightArray.length) {
                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
                                result[index] = rightArray[j++];
                        } else {
                                result[index] = leftArray[i++];
                        }
                }
                return result;
        }
) I* L" p: ]3 a5 s}


2 |3 k' w, B4 t* f' n1
$ ~& {1 u' z8 ^/ [2
+ m3 V4 |% U, k2 z6 }; _3
. g7 @4 v) f* R, S5 s6 {4
9 w1 C) i/ Q3 H  M( Q! @7 n0 @5
6
3 k' Y* l  l7 o4 [" `/ Y* X! O5 l  V7
" Y6 n8 [+ t: N6 ~8 y# P8
' D* I' Z. z! [  ]  J4 Y' i# \9
10
7 }% A0 x- c' A1 V6 ]11
12
13
! `6 x4 k4 y- N" ^3 h' f1 z14
& S$ E5 t- m( \9 H$ i+ H; ]15
' Y, U: i0 x+ H1 B16
17
; [/ y1 }1 v) D/ K18
19
20
( p6 Q$ ^) s! u2 z/ ^21
3 I9 a0 S; l: ?- t22
23
24
25
0 l6 d/ w0 \  u" Y* |26
27
28
) _$ o) ]( o  D% E' b- i29
1 u  y9 b2 j4 E$ h30
" q" o0 A( P# i0 E! l31
32
33
基数排序
找到数组中最大的数，确定最多一共有几位数。
' T& k- u6 A5 {; x5 o3 {' a按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
  b  \- C% k; o$ ~4 \8 V将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。

2 K1 W/ d  ^( o7 r7 L, O
. b& X& K- J" @+ Q4 t7 X代码实现**
  n1 p2 [  ~, d& S3 k/ t+ L

; @; T7 ]8 \0 ^# _" c6 Rpublic class RadixSort {
7 O: O& D4 N, `  X. l
) X' G* i/ E" i' L8 T8 C& R
3 u5 h% g/ G* W5 z; F        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);
# Y9 H: \# u7 |+ Y2 K                System.out.println(Arrays.toString(arr));
        }


" b4 G) D( v& W% E$ \        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
! X9 j% j, L# x. z9 F4 q' {3 [                        return array;
                }
3 o+ z8 f2 ^6 N3 V; Z" [9 l4 N                // 根据最大值找到最大位数
                int max = 0;
                for (int i = 0; i < array.length; i++) {
6 S& b% I3 p  v+ e& j( Z                        max = Math.max(max, array);
1 [& U" z# X/ o) e0 h                }
               
                int maxDigit = 0;
                while (max != 0) {
( s) \  t- j4 z% ~, m$ G' \- [                        max /= 10;
) }* ^& a* q( t& z                        maxDigit++;
                }
               
) Z, `1 i2 F$ R- `. G                // 第一维: 0~9
# p) Y  Y( d' C- T4 M                int[][] radix = new int[10][array.length];
                // 该位为 i 的元素个数
1 H. _2 ^8 i) c- V8 s" ]                int[] count = new int[10];
4 u, ^1 A2 y2 Y               
0 A) `1 ^7 R9 X% s                int m = 1;
0 B; t) S" L$ X, f& L                int n = 1;
               
! w1 }4 U4 \3 F                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
3 q7 w: g: a- I# _3 S9 c8 b                                int lsd = (array / n) % 10;
                                radix[lsd][count[lsd]] = array;
1 [6 Q' q( [7 r- a! Z) q3 r+ O                                count[lsd]++;
- A9 S5 [5 ?: Y  n, ^0 ~                        }
, k$ Y: V* [6 _) L8 B0 l% f                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
                                        for (int j = 0; j < count; j++) {
* L( U4 A3 l, j: ?- Z. L2 B                                                array[k++] = radix[j];
  b0 R% b; M" N* y+ a& A0 @1 m7 ]                                        }
; t+ _' F7 b! I6 \                                }
! u' U- x* t: S$ O, m: O                                count = 0;
                        }
                        n *= 10;
                        m++;
                }
. ^. Z3 v0 \; o- C' R                return array;
        }
: W, B8 @3 s" |0 W1 T

}
1
2
/ N4 W$ o9 e" p: m5 {2 ?3
4
2 o, o' f8 l9 ?7 p5
6
! n; ~. k! s  O5 `; M/ q7
  R0 l8 ^, I5 @8
9
10
  \9 u. R6 Z) t# X- @11
12
0 d; L, T* ^3 w0 w13
. o( }4 C* _7 l. _14
# b8 B& C% M, ?: a15
16
( r- _$ L8 b+ l2 D3 i17
18
19
/ ?6 u  m$ ?% j) r3 Y7 {: b* g3 z20
21
4 M" t( U' Y0 F& a* V) B5 w  r22
, R3 _, C. F, k3 s) P. J) x5 a23
24
25
" r0 s0 N5 K. b26
( g9 w/ k3 i- M, k5 B$ ]5 i! [$ |27
" `  V  r% \; Y* f% L$ H) K0 F28
29
: m" K' p0 m  A4 f" x. y1 J30
. a; ]( f2 O1 W) m! R; b6 G/ H5 ?% I31
32
" L) o# F6 p8 w8 G! e3 L33
34
* y7 ^/ W6 Y$ q1 C" L35
) o, |" n% j) A3 E8 d* ?36
37
9 |, [7 |9 J& E8 X0 D38
39
+ t/ c9 j+ s- Q6 Y8 a40
1 [2 n5 W" o  b3 m' C! b& e; T) p/ b41
42
- H. `5 \+ b& V3 v3 n43
) g& u# S5 P  @1 e& H" T. L44
' N! P* ]4 i; i9 s( t" O+ F45
# i' F0 c  n: ?8 h" T5 q$ Z46
+ j8 I  u) c7 }" ^47
48
49
( k0 T+ M: n4 W- w3 f1 c' o  o* ~50
& Q$ q2 E' r8 R1 R2 H51
* `% q: V( Y  u52
53
( I; J* X$ g; V* R" Y' }2 @' o. @计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
" b2 V6 B  _9 ~8 f3 l$ ^最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
7 {7 _5 T' M2 B! Q7 |6 Z% G- \& A9 L时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。

; S% \/ P; A; J) ]% f# V5 y! T3 o( E
) o9 l9 J1 p7 v" M代码实现


public class Solution {


  ?" C8 g$ J7 i6 z0 z( ~        public static void main(String[] args) {
                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
8 k) o4 E) _* D7 A2 ~                int[] arr = countSort(array);
                System.out.println(Arrays.toString(arr));
  [/ u+ h, a: c) w  ^/ n: e        }
% i1 U% ]  m, v0 h9 k
7 q$ i& L9 c2 x2 R8 u1 g+ w$ O
1 `9 X' |  \* E9 f8 D& X3 p& p0 ~        private static int[] countSort(int[] array) {
                if (array.length == 0)
9 O6 m6 _, K8 I  ^, H8 j. C% |7 m                        return array;
               
+ a; T+ L0 `  u, J- f" a8 d/ b                int min = array[0], max = array[0];
. h* c) v1 o, i               
                for (int i = 0; i < array.length; i++) {
/ H4 a0 X, W7 V2 |6 q: I8 E. l. o                        if (min > array) {
3 q2 ]: @/ M6 i( O                                min = array;
& r( t& F& `' w1 t: q( W* }                        }
. W6 W4 l/ x( ^$ ~2 q                        if (max < array) {
: g: \, u! _$ z9 k                                max = array;
: s( B4 z) B3 T0 _1 t                        }
                }
               
                int[] count = new int[max - min + 1];
               
                for (int i = 0; i < array.length; i++) {
& _+ h* u: Q) K0 T; O* p5 ]                        count[array - min]++;
                }
4 r4 O1 A  O8 m5 R7 \7 x               
                int i = 0;
3 f. }& d, n" z# e; n+ ~                int index = 0;
                while (index < array.length) {
                        if (count != 0) {
" s* l' e0 x& g$ n0 U% A* s                                array[index] = i + min;
0 l8 X4 Y3 u1 g7 i+ X+ A                                count--;
                                index++;
( [) r  l) q/ C- m                        } else {
                                i++;
                        }
                }
) b# i  Z; }) I) t                return array;
        }
) N& ~8 p' I1 \8 {( W) j' a       
) k9 V6 U6 {( }* l9 `}
: B! C8 H2 N% R) e3 u1
9 A0 N$ L% x) R7 Y( e2
3
4
5
6
+ x; P' F  @# t7
8
9
10
8 y0 i+ W5 n+ o' l: j+ r+ T) y11
0 G$ ^1 m4 o( l& u( L" L12
' b, k; P! z7 D1 a/ i. h% q13
/ ^4 i  }- u. I) V5 K+ O14
* K. d/ c+ p, \15
16
) c, I% k4 A' |$ v4 A0 c! ^, K17
18
19
- V! U/ Y. g$ Z( h8 r; I) f$ P* J3 j20
21
( h/ y5 p7 H; n) V22
7 X3 G! F2 ]% S9 i) g5 d& K' m4 Z23
# m2 ?$ t3 }$ m; N; `24
25
  ]5 `8 U1 m. X' ?: C, [% l. ^26
) a1 J9 A! r/ q8 U, G" k27
+ a4 x$ v5 R: r2 a28
29
, |! P! b; P% ~# a9 N30
31
32
# y; c- f& ?& @3 o8 G) y! N33
34
35
6 d  V0 d/ I6 t; [& P: @- i; N36
37
0 N5 H* ~7 U2 {38
6 \! [! C- J4 s. Q39
40
* }* p/ ]2 O- o! n& l41
7 B- c4 m, W  {0 p% S: J42
43
- y4 M  g* ]2 _' k% G4 F4 d44
+ Q! r& K# s; P0 E3 S1 G桶排序
————————————————
. i; F$ k' p- G) `# x: A版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* r) V8 b4 l& M: Z6 J原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
" }  w! N# i, F7 ?- n( J6 D7 R
# S. H0 s3 ?6 ?( n  p" C% A

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5