数学建模社区-数学中国

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

---

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

十大排序算法（Java实现）
* M3 s: S; O0 J
十大排序算法（Java实现）
排序算法框架
排序算法性质
插入排序
1 {& g8 _4 H  y  }2 P9 m3 g直接插入排序
希尔排序
选择排序
简单选择排序
# v) v  e2 ^. \- I# `; Z$ E堆排序
交换排序
* ~9 n* c0 ~& v8 V) ]冒泡排序
快速排序
* P3 W& Y! w0 T# B归并排序
基数排序
: `, S5 ?* S3 c5 i; a& V# ]) p计数排序
桶排序
更多文章点击 >> 这里
0 G) E5 i( x* d

. _5 E$ o+ a- i. i) C排序算法框架



6 V, N" n& |& s; h  M
  s3 |, p  e2 t1 i" l排序算法性质

& D) y1 j" h& c1 X

, K$ ?" q1 e: I( M- E
# q. q$ C0 E+ P. t: O插入排序
直接插入排序
从第一个元素开始，认为该元素是已排序的。
1 X2 |: J$ X5 `; |/ Z取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
8 U4 o. p( E% U最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
3 s. n1 ~& |6 J+ v5 x% z, \2
3 v; P4 V; `! c& I# {% D4 Y4 u ) 。


代码实现

$ @$ |2 G. A( x; J
public class Solution {
8 }( O' m4 }* P6 g" v. ?/ o        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
/ i% n( x% [, ~' u' O" f; N                insertSort(array);
" [$ ~3 v0 w7 o( E  j2 F/ Q                System.out.println(Arrays.toString(array));
        }
. z* m) S3 k$ q9 @  D
' d1 T3 c( r  `. x
        private static void insertSort(int[] array) {
                for (int i = 0; i < array.length - 1; i++) {
4 p) W6 n$ _) b' c  b6 F, m8 T, ~                        int data = array[i + 1];
                        int index = i;
/ k; k# P" h) f  J, k5 _                        while(index >= 0 && array[index] > data) {
5 P+ S- q7 P# {4 @( U                                array[index + 1] = array[index];
                                index--;
) H) ]& [, A8 U& D, y5 d                        }
                        array[index + 1] = data;
                }
        }
9 Q: k& y' y( c$ w# T}
1
( s( w2 Z3 S. b+ Q/ p, X) X: n2
3
* y# J( l. D$ g% W; s) Z7 P4
5
6
7
8
9
10
11
: m$ D& |& y8 `4 e8 A* k12
" H' w3 U2 U6 b& ]4 x" E13
) U) l" H1 P" e/ S4 L7 G14
15
, |( x( t- m& Z2 R16
+ Z( K. j( _" i17
18
19
8 R4 Q; J: }/ ~希尔排序

! H7 {# t/ I8 [, l! ?- T
7 S. o" s! z7 _  H6 ?6 E7 o- {时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


代码实现
6 d, e2 S2 k( `& V+ _4 r+ a; J1 I( M
% j9 W' n7 X* M
# i' h2 S4 t6 R% Upublic class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
                shellSort(array);
  H2 z" }6 c) G! o                System.out.println(Arrays.toString(array));
        }


        private static void shellSort(int[] array) {
# p1 o4 C* Q, ~                int gap = array.length / 2;
                while (gap > 0) {
. H( |7 Y2 t1 @# Y$ p; U, V3 H. f                        for (int i = gap; i < array.length; i++) {
. p. O+ z' B9 i$ i                                int index = i - gap;
/ X0 o4 @; _- ]                                int temp = array;
; n8 U: x4 N3 A) `( t# D) K4 z, r; a3 z                                while (index >= 0 && array[index] > temp) {
# h2 K; ]' F- m$ d. J2 X                                        swap(array, index, index + gap);
9 s) d2 J, \$ u% A2 U                                        index -= gap;
- `/ g9 P! X! g) J4 n# v6 Q                                }
! Y" k: g3 ]3 X9 v3 m) ^( V/ L' `//                                array[index + gap] = temp;
                        }
7 t; f1 X$ d2 q                        gap /= 2;
4 M0 x6 J( n9 w% u0 n) [                        System.out.println(Arrays.toString(array));
! }; \3 |* S  @( j/ j0 T                }
4 X  N! u6 ~& H) G  w        }
* f3 \9 r6 |( M  t8 ]- j

% V) W( `0 |  ^6 T7 l        private static void swap(int[] array, int i, int index) {
- u, n( v& y+ g& i) [                int temp = array;
                array = array[index];
  I* s/ R/ U$ u0 j2 K( ?: A1 e                array[index] = temp;
, p6 O3 J8 U/ F6 _" T8 b9 y5 W        }
# U( J3 T  p# S; o: w4 @7 ~$ j}
7 `1 M6 S3 o9 q- z7 A: j& u, B1
' k7 F3 o9 R" F" e4 `2
3
4
0 `0 m/ b( i" O! Y$ o8 I5
1 z0 ]0 ~$ E" S9 \, ?2 {4 F1 L7 D: h6
7
3 Z1 D8 h5 E3 ^% U4 x8
9
/ Z( p. O- E8 @# G& }3 i10
7 [/ k+ R8 @* g1 q11
12
13
14
1 Y' r! Q, N1 f/ ]( H* b5 K15
16
7 c/ o1 _; d  j2 m3 {6 g17
( @  X$ J. i6 H6 N9 `; G18
# `6 A8 H$ T0 {0 F( d+ y: ?: W5 @3 c19
9 N, i3 N6 f9 ~$ W3 V2 @$ I20
21
* \" S* z% x& ]/ q$ B8 M, o# l22
* \& W5 }/ t: d8 p% z9 x/ \23
24
3 G" B3 a  R3 E; x4 o25
26
27
" {) `# v# H2 Q7 l5 ]% ~28
$ a9 c1 y( ]2 y! K6 Z29
30
选择排序
简单选择排序
从未排序的初始数组中寻找最小元素放置首位。
从剩余元素中继续寻找最小元素，放到已排序序列的尾部
2 J/ y+ c$ U9 g# j3 Z遍历数组，直至结束。
: M0 H& D: B+ N1 e# n/ h' O5 S. _时间复杂度为 O ( n 2 ) O(n^2)O(n
8 Y% Z6 V) e. J& ]: C/ V5 b9 }7 B2
) 。

* F: m9 x( B" E; p9 I: o( b
代码实现**
+ |+ ]( `- v7 R: c# k1 ~4 w( _: V

public class Solution {
        public static void main(String[] args) {
0 G2 x" q8 c6 p: I+ n# e' G$ B$ z                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                selectionSort(array);
& S( G/ h2 n4 J' b9 x' V, _9 ~                System.out.println(Arrays.toString(array));
        }
2 F7 M! o8 M9 m4 b- C5 _& c4 `! s

        private static void selectionSort(int[] array) {
. ^! F. C6 q6 p$ f4 }. d' ]7 t: H                for (int i = 0; i < array.length; i++) {
                        int index = i;
# p) d' R- i$ h5 n/ z                        for (int j = i; j < array.length; j++) {
                                if (array[j] < array[index]) {
( A& h9 `' \# w( }. G  R3 E2 b                                        index = j;
                                }
) J; k. K: ~2 F* ~+ ~4 M; }                        }
* o+ b: Y4 N0 n2 O# q; e" `* u5 ?                        swap(array, index, i);
                }
        }
8 e! s% c, b0 W8 w

6 P: q# `5 |$ b- a+ a        private static void swap(int[] array, int index, int i) {
$ z4 Y% b8 b$ B' o                int temp = array[index];
                array[index] = array;
                array = temp;
        }
" b9 \% V* D+ G  z+ ^2 }}
% R( k4 g% }( z  J% p$ E3 e6 ^1
2 i; O7 {, y* I2
. k! I# h5 p! V9 ?3 O3
4
* ~  q- D6 w8 u& z5
4 E6 J; I, ?' T9 S$ b, D6
7
8
6 D; y) O# Q% y3 A9
10
2 H; `' F% c. I" K3 b11
12
7 u& _' O- P' }% k8 s) p0 q13
14
15
16
17
18
" O( r! A1 e2 s7 d! l3 Y# i19
! K5 u' [! P0 e. ~' }; j20
& G( Z; V- b- B9 h21
. V% Y& c& X/ m' }22
23
24
25
* {4 V6 x6 Z; y; u" q* j堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。


) L/ H5 ~7 p; L- V1 K5 v  N3 K8 ^代码实现**


- x( I( _- c1 T, Y+ ^' a0 _* W" E% upublic class Solution {
. d6 O( k" P0 X. f. o: P% _: n        // 建堆
        public static void creatHeap(int[] arr, int n) {
; k- E  p5 d5 e4 e/ w                // 因为数组是从0开始的
                for (int i = (n - 1) / 2; i >= 0; i--) {
4 m+ O6 g( ~8 {4 T                        percolateDown(arr, i, n);
                }
        }
: q6 [3 f" e5 c0 y6 L        // 插入
8 V( L  |- I4 M8 H+ O        private static void insertHeap(int[] array, int data, int n) {
                array[n] = data;
                percolatrUp(array, n);
. [% t) u6 e  p) A+ D5 U7 I        }
3 d! ^  u4 Q6 u: n$ O        // 删除栈顶元素
        private static void deleteHeap(int[] arr, int n) {
                arr[0] = arr[n];
                arr[n] = -1;
0 {2 _$ t% r/ l* w6 N                percolateDown(arr, 0, n - 1);
        }
3 P$ h2 N+ \/ h0 ~+ \        // 上浮
        private static void percolatrUp(int[] array, int n) {
7 ~5 P+ x1 U( A) @! }: {                int data = array[n];
: B2 E! l) [. D! u+ M- }) J0 u5 J                int father = (n - 1) / 2;
                while (data < array[father] && father >= 0) {
                        array[n] = array[father];
                        array[father] = data;
                        n = father;
                        father = (n - 1) / 2;
                }
                array[father] = data;
' C$ z7 @( [5 W, c) \% K1 `8 C- I) _        }
) k/ n& w: y6 Y. F8 n        // 下滤
( F7 m' ~. y6 L+ U+ a( F+ k) D        private static void percolateDown(int[] arr, int i, int n) {
                int father = arr;
2 C- [) v4 L( `3 L; l                int child = 2 * i + 1;
, B" s' l5 {  b                // 遍历整个该根结点的子树
1 i- b7 P- n8 T, o( G$ l                while (child <= n) {
                        // 定位左右结点小的那一个
& p4 {( K. d6 o0 j' ^2 Y1 O, i. h' ~                        if (child + 1 <= n && arr[child + 1] < arr[child]) {
5 u/ s- t  d8 d  L4 T& \# Z' g& i                                child += 1;
                        }
. G( {9 A+ v* `: E/ k9 `5 ~+ W8 T                        // 若根结点比子结点小，说明已经是个小堆
! ]/ b0 y; d7 L! i6 _                        if (father < arr[child]) {
                                break;
                        }
" O4 Z' Z  h8 I+ a# s                        // 互换根结点和子结点
9 W: z0 w2 J7 @3 u) L                        arr = arr[child];
4 t  {3 ~- y$ X" q                        arr[child] = father;
* v# h$ @$ W/ u* V2 A                        // 重新定位根结点和子结点
                        i = child;
                        child = i * 2 + 1;
+ P# A1 _9 L' b2 p) ]: {                }
9 C. g  e/ p' o, K        }
& A8 e2 @! T- J; K* D* ~   
0 Y1 l; [- e: x# v8 ^5 n        public static void main(String[] args) {
                int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
               
                creatHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
                deleteHeap(array, array.length - 1);
                System.out.println(Arrays.toString(array));
               
! `# j/ v& D! A. j1 S6 Q- U8 F                deleteHeap(array, array.length - 2);
3 W" M6 S1 e+ o0 d4 }6 P                System.out.println(Arrays.toString(array));
5 }! A% p0 k! Q/ K               
/ k- x# C' _" v' q8 I1 o/ u/ ]                insertHeap(array, 3, array.length - 2);
                System.out.println(Arrays.toString(array));
6 q2 [8 X, ^. S* i. g        }
9 [5 M9 F+ P% t& g1 y}
+ R& t5 S1 r0 z; _1
2
  q  x* W9 c) D8 h- X( d3
4
. c  K7 O, I- U: m7 b5
4 j; k" W% V  k9 J$ _* N6
, |4 g2 C, t2 s4 u$ f  H  n7
; h. B# ~) r* G3 }8
/ a) A+ ^0 `4 ^# Z6 T" C) x% [9
( U' i! k' p" F$ ]# r3 n10
; j; D1 [5 i& R. ]% B" n( w11
12
" D$ ~2 N! v" F  l13
14
15
16
17
18
19
20
; z. q& m. H& d) \21
1 }* ~* \, B) u! \6 f; B, e22
23
( }  z2 y" N6 e6 k24
1 }9 W; _+ Q: e% |& O25
26
27
  Z/ F' G: y% O7 ?! l3 _28
. ^; W- B& R' F29
. k3 I1 O5 z8 E, y/ R30
5 R; N) g$ j- W# b+ y/ I31
2 M+ G$ F( R" _0 F* i( ]0 Z32
33
34
* i# f. `0 a9 i8 I35
4 x& x2 ~. S# C. G% w* j36
37
& l0 ^2 y7 D' H% q& C+ G38
39
40
$ L; P2 z: i" L/ V; b41
; _- `( g) C8 E4 h5 A+ a! r* k42
43
44
45
5 l( d' f! P3 r2 E/ y4 j46
, a; `8 t/ |$ W  y47
1 r; f1 B( u# I# r48
7 t1 l* P$ F( ]# _8 Z0 V  A49
50
7 h/ q. y" O( x, _% N7 ~4 |51
52
53
54
) {# A" q) {  i55
56
2 P+ @3 ^: P  E57
2 O, Y) x- k, U7 a3 M4 U. y4 n- I58
59
60
# z1 @/ B: z1 W61
. Z. y3 s* K. x( E  u* t( P) H62
63
% u& F+ [- o+ {; Z' K3 F64
65
66
; C9 Q& S& F. k9 [  A67
( X. t. o4 Z4 N% ^, m$ d68
3 [. o5 \" t: ^" _, S3 B: I69
( M$ A5 T% B8 e; C& ]9 B70
交换排序
1 O) o' V1 }' ?) ]2 K9 u. o- O冒泡排序
1 I2 Z0 P* Y& J% v0 Q依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
4 \6 c( `9 v# [% g- `在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
& j3 |% B* w0 m# b, ^* e" x  q最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
" }. A1 N7 v/ E ) 。

. ~  K* o5 Z$ v4 p& M
代码实现
- I! ~$ Z$ O4 X4 X

import java.util.Arrays;
, x/ s8 n& v( S( y! v/ F: X6 Fpublic class Solution {
. d8 ^8 o9 U/ d       
        private static void bubbleSort(int[] nums) {
1 v6 J" A6 r' v. \/ `( T                // 循环次数
1 V: ?1 t2 G# m$ @3 C                for (int i = 0; i < nums.length - 1; i++) {
                        // 比较次数
                        for (int j = 0; j < nums.length - 1 - i; j++) {
: [' b4 Y/ n# V$ }( X1 a                                if (nums[j] > nums[j + 1]) {
8 d, ~8 E7 `* r, j$ R$ y7 R                                        swap(nums, j, j + 1);
                                }
* F' Y; H1 S$ W0 \; E& X' K2 L                        }
* w9 n3 m3 o) T7 I1 w. D                }
        }
; I, P! |& U3 q: P# o
1 d% O: O+ P1 r
  q2 Y8 @2 ~4 {1 o( O0 F5 A        private static void swap(int[] nums, int j, int i) {
                int temp = nums[j];
                nums[j] = nums;
( ?/ M% K* ^& H! U2 q                nums= temp;
; }" |4 B1 b6 I6 s        }

2 d) e8 W2 s5 d( j
* O" X% t- V+ ~0 P- B& E        public static void main(String[] args) {
+ P8 n9 u# Q/ ~: Z( o                int[] nums = { 6, 3, 8, 2, 9, 1 };
                bubbleSort(nums);
  U1 T+ D/ T/ z( w" l" [5 A# J! U                System.out.println(Arrays.toString(nums));
8 i2 \# a" x" h9 A2 M% _% Q% v        }
}
1
9 e' D9 `1 ?( G7 m% A2
# G( c' k0 a9 w3
4
: f* n$ ]- Y: l6 Y% }) z) O0 m5
# |& v0 q* q3 ]! `. X( w9 \1 \6
7
8
7 A7 l( Z$ d; m" [4 m9
: [$ `# J7 Z6 ]4 C10
11
( R' a/ V$ @- U& E( h; E12
13
" M- `7 _5 j) G14
15
16
17
; W& e, O  i1 y7 [# z18
19
20
21
% R$ Y6 l! O4 n22
6 k, J0 \. x3 |5 C: |  M# z4 P23
" B7 N9 {7 l0 T1 o* E: `24
25
% n' D' g: a4 a2 [) L$ h26
27
快速排序
; o& U  n; `8 z9 _- c  [2 h+ {时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
" a, ~' i/ `* @9 [3 v

代码实现
+ U. O% O2 m# I+ ?% f- t
# }. K4 K4 Z+ ]! H$ Y8 K2 ~( D
public class Solution {
+ ?6 t& k' F* u       
  W2 w4 W# u2 o+ n% B" E        // Median-of-Three Partitioning
( A; M7 ]3 i0 N5 ]7 k3 @        public static int selectPivot(int[] array, int left, int right) {
8 Q+ t" w) T! b  y4 G; W( N                int middle = (left + right) / 2;
- G2 a4 O2 ?: U$ R& @% n: \( x               
                if (array[middle] > array[right])
                        swap(array, middle, left);
                if (array[left] > array[right])
/ W( |: ?9 l$ M. v: s                        swap(array, left, right);
/ }; U. W, W" \+ m# S                if (array[middle] > array[left])
5 e  Z: ^6 V1 {/ D                        swap(array, left, middle);
6 n; y7 E0 c" H7 X2 x7 t+ Y               
                return array[left];
        }
       
) z& X) I! w7 R1 `" P& O        public static void sort(int[] array, int left, int right) {
                if (left >= right)
; j( {! t" T9 }4 \! ]; X' Q( ^( s                        return;
! Z6 e  v5 r/ \* s' Z                int index = partition(array, left, right);
                sort(array, left, index - 1);
                sort(array, index + 1, right);
    }
       
        public static int partition(int[] array, int left, int right){
        int pivot = selectPivot(array, left, right);
2 o9 t; g" D! L& e- t& I        while(left < right){
            while(left < right && array[right] >= pivot){
                right--;
            }
9 N8 ]- ?+ j. e* m$ g$ }1 v            if (left < right) {
" A' U. v& Z0 {( n6 M0 I$ ~4 c                array[left++] = array[right];
* H8 M7 C: U( n/ L& Y            }
4 R$ K' J  S* g! T  a' G, v            while(left < right && array[left] < pivot){
/ i* S" k4 M8 V                left++;
4 _, r1 G6 C5 @; n7 ^9 |, t            }
            if (left < right) {
  M5 n+ s$ b* e1 }$ g: V                array[right--] = array[left];
            }
        }
            array[right] = pivot;
1 C- y( N  F  C, `( M& x- B        return right;
    }
2 D* S( Q) x, g( s' W# O) f

    public static void swap(int[] array, int left, int right){
6 }5 i3 p+ X& E+ p            int value = array[left];
8 e! _" Q6 M2 E# M" k+ A            array[left] = array[right];
: o! _* R- O1 [0 w            array[right] = value;
& U3 P6 N. i, g+ X& C7 B    }
: W! Q% Q1 I, x" }$ c

: W) k! G( @' b/ S7 O5 H4 d! e        public static void main(String[] args) {
                int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
                // System.out.println(Arrays.toString(array));
                sort(array, 0, array.length - 1);
                System.out.println(Arrays.toString(array));
8 F" }/ u9 T, a9 k& t, q4 D        }
}
2 }: Y( ~" i9 V( ^( a1
( T, R5 Y2 g# E2
3
$ t6 q8 Q! D# l5 x4
5
- G/ W/ v8 D% x" F# T' D6
7
8
9
10
11
. j" j3 G# N& L5 N12
13
0 x9 S- ^: Q2 `/ s4 L* P8 b0 G14
15
16
17
1 p8 w  i3 i- Z# I) d1 N; N18
: ]& i6 G; ?+ u: x19
20
" H$ ~. D1 W" Q7 U, V21
( b8 h1 @7 W. c22
3 m. o  K9 n: R) a; Y23
24
* |; A0 w& T  r5 A$ G& b$ }25
2 h* i4 ]0 M) G( H" @  P$ c26
6 ?3 g7 `, |: ^4 r8 P27
28
29
  _' d/ ^) ]% C* y/ u* z30
1 {0 n, C" B5 ?31
32
33
34
35
36
* e2 A7 U  W) P3 x. E% h; u, B37
38
/ N" p' p% p$ U+ V39
4 n+ j7 Q! l! z1 G0 K9 \40
41
& N  Z. ^! k5 u, E, u+ b8 X42
43
3 k; s" \  d- }1 M44
' W! h& H' J6 |* _; k, U4 }) Y45
46
! H! b; l- j5 |9 r- V47
2 N1 D) K1 a. O48
49
& K0 G9 Y% q: u2 Z' N2 o50
51
52
53
( |: Q0 p8 f. S54
55
56
57
归并排序
将长序列从中间分成两个子序列。
3 g7 z, n# J8 t( P对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
! }6 ~2 g3 f0 T; p' Z6 h0 l
3 ~+ h6 a( `& S/ \) u1 A* |
- \2 _/ R# r0 n: @8 |' Y代码实现**
) l* z  R( R# s

public class Solution {
        public static void main(String[] args) {
                int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
3 f7 G  A/ h- \) e! E                int[] arr = MergeSort(array);
                System.out.println(Arrays.toString(arr));
        }


        private static int[] MergeSort(int[] array) {
                if (array.length < 2)
" F  g- z8 {8 N' S* F: _9 I1 N( m9 x                        return array;
, J9 j, j$ y% i6 _  m                int middle = array.length / 2;
; _+ W. m, X$ m% a0 n4 q- M                int[] leftArray = Arrays.copyOfRange(array, 0, middle);
! V$ E. D5 b8 _& e" S7 o: v. f7 }                int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
) F5 P0 w8 V+ \$ t1 h) A" w/ j                return merge(MergeSort(leftArray), MergeSort(rightArray));
% Y+ ^/ b" E& w3 e( d        }
4 @9 L9 B# f& L1 j
- P. i6 A; a, `
        private static int[] merge(int[] leftArray, int[] rightArray) {
$ |6 k  _( t  a) _5 Z0 B& S                int[] result = new int[leftArray.length + rightArray.length];
                for (int index = 0, i = 0, j = 0; index < result.length; index++) {
9 k0 o' I  V* e( n8 i7 u* T                        if (i >= leftArray.length) {
                                result[index] = rightArray[j++];
& M4 `/ V/ E. x, J6 A8 p                        } else if (j >= rightArray.length) {
# R8 e+ A3 c' A, S9 y3 O' @- e                                result[index] = leftArray[i++];
                        } else if (leftArray > rightArray[j]) {
% g9 F2 @2 Z3 z0 y' J  w$ {                                result[index] = rightArray[j++];
2 b. Y+ r( l$ [, M1 X# L                        } else {
; A) S+ \4 U3 f  C( X0 X                                result[index] = leftArray[i++];
                        }
, z4 C4 K' P, Z( Q) v                }
                return result;
        }
}

( Y2 r: ^: C+ m! i$ }5 F
3 ^) M2 S5 O0 c" J, ~/ f. A1
& j0 ^: v" L  z0 a! ~2
3
4
3 Z. F: T2 |/ v; A5
6
7
. U2 E5 ]8 l2 b' f% t( ^8
9
10
11
  f" `. N7 G. e1 n  o12
13
14
6 L6 s' ?$ W" c8 W15
16
17
* d2 {( Z* r0 ?18
19
20
3 q0 J/ C' X: Q. D3 K; ~21
22
23
24
25
/ c  }3 w5 a# ]% K; t# g3 @9 y: E7 K4 R26
7 X, f0 n: j: |  i27
28
29
" e0 Q/ R8 F0 }9 s, v; I30
* g3 q5 N1 s& x$ R7 L" m  x31
32
33
基数排序
1 K$ W5 j6 q9 s9 U找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。

8 o  C, w9 {) }+ W
代码实现**
* P8 h6 \# B5 h+ K: ^# S! Q* s
) H( G! ^. f# _" U' v
9 D6 L' h2 G! I& c5 F. Wpublic class RadixSort {
' U  l/ R: Z, M! G& ?+ r

9 p1 l1 I, C+ N) R) q8 Y" Z$ I        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);
" e$ N# h3 M9 p) T/ X. {                System.out.println(Arrays.toString(arr));
1 t7 {" q3 H+ b9 U6 K        }
8 U  `6 Y$ P; t, W' e  m
1 o: R: v) Z8 c0 T# b# x
        private static int[] radixSort(int[] array) {
                if (array == null || array.length < 2) {
. U& L' c  i* x: x, T                        return array;
                }
0 u1 V2 X. |. Q                // 根据最大值找到最大位数
6 @5 b7 w! A3 M4 L' w% D                int max = 0;
, ?; ?5 W! ^- |4 ?                for (int i = 0; i < array.length; i++) {
                        max = Math.max(max, array);
+ c$ J: ?, d5 k7 t" T                }
( j2 H+ {& a( I$ M) A0 |: i               
5 ~( L/ J9 r3 K9 v+ q1 ?3 x: q( u                int maxDigit = 0;
                while (max != 0) {
                        max /= 10;
. \7 \3 r+ o4 `) U                        maxDigit++;
- F1 u' p$ {( q& J                }
! s" X/ K3 q2 U               
: o- h( q3 x, ?: n& D7 m! O                // 第一维: 0~9
2 y- l3 I6 q6 N; k# }' {. A$ O- W% U                int[][] radix = new int[10][array.length];
                // 该位为 i 的元素个数
                int[] count = new int[10];
               
                int m = 1;
                int n = 1;
               
3 V) q' P7 L( Z0 Y6 S% q/ v6 a                while (m <= maxDigit) {
                        for (int i = 0; i < array.length; i++) {
                                int lsd = (array / n) % 10;
; [- n/ Z3 Z+ B  P: F                                radix[lsd][count[lsd]] = array;
+ N. `2 e3 p5 M- i                                count[lsd]++;
5 _) L! j# S" x1 U+ ]5 b5 o3 E" R                        }
: v6 \, b  z( P+ E' i# ]: [9 C0 j2 L                        for (int i = 0, k = 0; i < 10; i++) {
                                if (count != 0) {
, G, p* c% x) L, F* U                                        for (int j = 0; j < count; j++) {
                                                array[k++] = radix[j];
' b; H1 O! \  P) Q* I; {- q, U$ h                                        }
                                }
( H5 I9 Q* u3 i  H. F                                count = 0;
                        }
                        n *= 10;
                        m++;
                }
; q5 T5 T8 O. \* e5 a                return array;
        }
( d; v( h" b( K

}
# g, b5 j( G0 ^& I* m, o( B1
0 y% z, A6 A- c7 F! @+ |2
3
5 ~. K; _- D; E* P# ]9 Z5 E4
. v8 l: I, f( D& W7 O5
* L0 F# ~6 G; g8 \6
7
8
! B+ [3 F4 l5 f. p3 O. a$ Q/ r9
1 w; M( l- `3 [# e10
! |0 Z( O: m) U! K( M6 W11
12
13
14
/ a- t3 m( J' t( g8 C; H15
9 r) b4 T- Z: G% x16
7 t# x5 A/ A# n2 T8 o# a- q; T$ [2 _17
18
5 ?: m$ y) m2 R( |  l4 h19
20
21
22
23
24
. |$ K2 A' A5 b3 Y( k/ ]/ Z25
26
27
. B, W2 c! u& z+ v* e28
+ P( w3 d% B) ]7 B. v9 r7 o7 D29
30
: O+ _( o: x) s- R, w/ O31
32
" _& F3 @/ k1 l) `33
34
0 K9 B! z) Y" z; t' S35
36
37
! d) H0 ^! p' Q4 [38
( }* k. \9 v* _2 x3 E! _" \' x4 q39
3 z" v, E- @0 ]8 ?0 K  p8 J; ?40
41
' ~' y9 @* ^# ]0 f2 q- x42
% M# P7 ?$ z5 S43
3 ^% k- V+ A! e( s% j44
45
- x, X" b* H- ~0 I4 e46
- ~( y5 k& x8 z4 _& A) o, W# i47
  z# M2 x% K( z- E1 ~% k48
% Y2 [! ]/ t2 `- p; s49
50
' E0 M# b0 o2 i1 K: E51
52
1 q2 m$ [7 C0 B. J53
计数排序
1 [6 Q5 w, [! J* l2 t找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
- c" T+ I' `/ F# r0 Z) n  R统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
! E0 r4 r' T! ]/ M# S1 B# |3 f时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
9 B( x  |/ x3 ^' N
# b8 f4 K5 \; f* }
代码实现

, z, H" j6 S- N2 @1 K1 R; z7 w* X
$ D1 c1 H& f) Hpublic class Solution {

# u1 F: s& m; d. y% n# N8 \
        public static void main(String[] args) {
; Z4 A% w& D0 Z, [7 I/ e9 l                int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
; k$ X6 m9 j2 ~' }                int[] arr = countSort(array);
/ W3 s4 _- t. l4 K- }                System.out.println(Arrays.toString(arr));
# j: R; v/ P* u( g        }
6 s0 k8 b4 S! S6 m4 t9 d! [1 S; v
0 c5 J! T+ }) [6 R) J/ D
        private static int[] countSort(int[] array) {
                if (array.length == 0)
                        return array;
# Y! @1 u& |# Y- ?               
0 y% }" |7 T9 ]                int min = array[0], max = array[0];
8 N& T+ L; e' ^1 v- N               
: @6 y# w7 m% ^                for (int i = 0; i < array.length; i++) {
                        if (min > array) {
2 W& ^& |6 N8 v, F% I. |                                min = array;
                        }
+ n! e7 b# w* z/ F5 D# I                        if (max < array) {
                                max = array;
                        }
6 m# R3 M/ d8 D4 c6 Z9 r! U                }
               
                int[] count = new int[max - min + 1];
               
  ~! V* K7 l, J# A                for (int i = 0; i < array.length; i++) {
- V6 e: {, w2 |& u6 M                        count[array - min]++;
                }
4 H  ?3 m" N" K8 p               
" L; N5 _8 I" N" h                int i = 0;
                int index = 0;
                while (index < array.length) {
                        if (count != 0) {
                                array[index] = i + min;
3 K4 d3 v! i2 s                                count--;
                                index++;
/ a/ C& v# Z# l                        } else {
                                i++;
                        }
$ u5 [$ c; w# J6 a' E                }
                return array;
        }
       
}
1
2
3
, g0 C6 J0 t% D4
5
6
) ~3 u4 j; k/ B2 g  {2 z$ x  R7
, ^7 @( J1 d; Z2 ]9 I8
4 i" N* g+ [  R% z9
& d4 a- k2 E- w- T" s10
" h, U6 u  H# P0 }  B! v3 m- u; w, H, Y11
0 {5 {: u- E, @) w' h, r12
13
14
2 z9 M$ R) d0 b* C9 p6 |15
16
; h+ A$ Y) P9 o3 M. D17
( ~3 J( {, o1 K7 s7 C18
19
20
  {  r/ a6 C! ]' W# s& E21
* |& T) x3 i+ J* n  @- p7 e22
23
0 J, }8 N$ q0 N: p+ g  W$ K3 ~24
25
26
27
28
29
30
; i" y1 x8 r2 l) R9 T31
32
' q8 K' b1 s1 g$ B8 z# {' {4 M33
% V  `7 _6 \2 w- L# y, _" i34
& A- s' h+ K8 i35
! j  [2 E+ _9 z4 ^( j' N% J36
37
6 l8 S4 S, C8 J5 |3 Y38
39
8 E' S8 m3 ?: `; k6 V, R40
% M$ v+ A- o- t% _3 V' P41
42
43
44
: l: L& E& _6 [6 r5 L# Q5 R桶排序
& O  v" j/ K2 n3 I3 |8 R+ T————————————————
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
7 d& a  T+ y4 H( K. n$ q+ B% r0 b3 ^
; L% M% }" t/ h/ E! \% r) ], w8 N/ m
9 o1 A1 L/ |$ s8 n2 @& D

---

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

Powered by Discuz! X2.5