本文实现了八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序 、快速排序、归并排序、堆排序和LST基数排序
首先是EightAlgorithms.java文件，代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
|
import java.util.Arrays;
/*
* 实现了八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序
* 以及快速排序、归并排序、堆排序和LST基数排序
* @author gkh178
*/
public class EightAlgorithms {
//插入排序：时间复杂度o(n^2)
public static void insertSort(int a[], int n) {
for (int i = 1; i < n; ++i) {
int temp = a[i];
int j = i - 1;
while (j >= 0 && a[j] > temp) {
a[j + 1] =a[j];
--j;
}
a[j + 1] = temp;
}
}
//冒泡排序：时间复杂度o(n^2)
public static void bubbleSort(int a[], int n) {
for (int i = n - 1; i > 0; --i) {
for (int j = 0; j < i; ++j) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
//选择排序：时间复杂度o(n^2)
public static void selectSort(int a[], int n) {
for (int i = 0; i < n - 1; ++i) {
int min = a[i];
int index = i;
for (int j = i + 1; j < n; ++j) {
if (a[j] < min) {
min = a[j];
index = j;
}
}
a[index] = a[i];
a[i] = min;
}
}
//希尔排序：时间复杂度介于o(n^2)和o(nlgn)之间
public static void shellSort(int a[], int n) {
for (int gap = n / 2; gap >= 1; gap /= 2) {
for (int i = gap; i < n; ++i) {
int temp = a[i];
int j = i -gap;
while (j >= 0 && a[j] > temp) {
a[j + gap] = a[j];
j -= gap;
}
a[j + gap] = temp;
}
}
}
//快速排序：时间复杂度o(nlgn)
public static void quickSort(int a[], int n) {
_quickSort(a, 0, n-1);
}
public static void _quickSort(int a[], int left, int right) {
if (left < right) {
int q = _partition(a, left, right);
_quickSort(a, left, q - 1);
_quickSort(a, q + 1, right);
}
}
public static int _partition(int a[], int left, int right) {
int pivot = a[left];
while (left < right) {
while (left < right && a[right] >= pivot) {
--right;
}
a[left] = a[right];
while (left <right && a[left] <= pivot) {
++left;
}
a[right] = a[left];
}
a[left] = pivot;
return left;
}
//归并排序：时间复杂度o(nlgn)
public static void mergeSort(int a[], int n) {
_mergeSort(a, 0 , n-1);
}
public static void _mergeSort(int a[], int left, int right) {
if (left <right) {
int mid = left + (right - left) / 2;
_mergeSort(a, left, mid);
_mergeSort(a, mid + 1, right);
_merge(a, left, mid, right);
}
}
public static void _merge(int a[], int left, int mid, int right) {
int length = right - left + 1;
int newA[] = new int[length];
for (int i = 0, j = left; i <= length - 1; ++i, ++j) {
newA[i] = a[j];
}
int i = 0;
int j = mid -left + 1;
int k = left;
for (; i <= mid - left && j <= length - 1; ++k) {
if (newA[i] < newA[j]) {
a[k] = newA[i++];
}
else {
a[k] = newA[j++];
}
}
while (i <= mid - left) {
a[k++] = newA[i++];
}
while (j <= right - left) {
a[k++] = newA[j++];
}
}
//堆排序：时间复杂度o(nlgn)
public static void heapSort(int a[], int n) {
builtMaxHeap(a, n);//建立初始大根堆
//交换首尾元素，并对交换后排除尾元素的数组进行一次上调整
for (int i = n - 1; i >= 1; --i) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
upAdjust(a, i);
}
}
//建立一个长度为n的大根堆
public static void builtMaxHeap(int a[], int n) {
upAdjust(a, n);
}
//对长度为n的数组进行一次上调整
public static void upAdjust(int a[], int n) {
//对每个带有子女节点的元素遍历处理，从后到根节点位置
for (int i = n / 2; i >= 1; --i) {
adjustNode(a, n, i);
}
}
//调整序号为i的节点的值
public static void adjustNode(int a[], int n, int i) {
//节点有左右孩子
if (2 * i + 1 <= n) {
//右孩子的值大于节点的值，交换它们
if (a[2 * i] > a[i - 1]) {
int temp = a[2 * i];
a[2 * i] = a[i - 1];
a[i - 1] = temp;
}
//左孩子的值大于节点的值，交换它们
if (a[2 * i -1] > a[i - 1]) {
int temp = a[2 * i - 1];
a[2 * i - 1] = a[i - 1];
a[i - 1] = temp;
}
//对节点的左右孩子的根节点进行调整
adjustNode(a, n, 2 * i);
adjustNode(a, n, 2 * i + 1);
}
//节点只有左孩子，为最后一个有左右孩子的节点
else if (2 * i == n) {
//左孩子的值大于节点的值，交换它们
if (a[2 * i -1] > a[i - 1]) {
int temp = a[2 * i - 1];
a[2 * i - 1] = a[i - 1];
a[i - 1] = temp;
}
}
}
//基数排序的时间复杂度为o(distance(n+radix)),distance为位数，n为数组个数，radix为基数
//本方法是用LST方法进行基数排序，MST方法不包含在内
//其中参数radix为基数，一般为10；distance表示待排序的数组的数字最长的位数；n为数组的长度
public static void lstRadixSort(int a[], int n, int radix, int distance) {
int[] newA = new int[n];//用于暂存数组
int[] count = new int[radix];//用于计数排序，保存的是当前位的值为0 到 radix-1的元素出现的的个数
int divide = 1;
//从倒数第一位处理到第一位
for (int i = 0; i < distance; ++i) {
System.arraycopy(a, 0, newA, 0, n);//待排数组拷贝到newA数组中
Arrays.fill(count, 0);//将计数数组置0
for (int j = 0; j < n; ++j) {
int radixKey = (newA[j] / divide) % radix; //得到数组元素的当前处理位的值
count[radixKey]++;
}
//此时count[]中每个元素保存的是radixKey位出现的次数
//计算每个radixKey在数组中的结束位置，位置序号范围为1-n
for (int j = 1; j < radix; ++j) {
count[j] = count[j] + count[j - 1];
}
//运用计数排序的原理实现一次排序，排序后的数组输出到a[]
for (int j = n - 1; j >= 0; --j) {
int radixKey = (newA[j] / divide) % radix;
a[count[radixKey] - 1] = newA[j];
--count[radixKey];
}
divide = divide * radix;
}
}
}
|
然后测试代码TestEightAlgorithms.java，代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
public class TestEightAlgorithms {
public static void printArray(int a[], int n) {
for (int i = 0; i < n; ++i) {
System.out.print(a[i] + " ");
if ( i == n - 1) {
System.out.println();
}
}
}
public static void main(String[] args) {
for (int i = 1; i <= 8; ++i) {
int arr[] = {45, 38, 26, 77, 128, 38, 25, 444, 61, 153, 9999, 1012, 43, 128};
switch(i) {
case 1:
EightAlgorithms.insertSort(arr, arr.length);
break;
case 2:
EightAlgorithms.bubbleSort(arr, arr.length);
break;
case 3:
EightAlgorithms.selectSort(arr, arr.length);
break;
case 4:
EightAlgorithms.shellSort(arr, arr.length);
break;
case 5:
EightAlgorithms.quickSort(arr, arr.length);
break;
case 6:
EightAlgorithms.mergeSort(arr, arr.length);
break;
case 7:
EightAlgorithms.heapSort(arr, arr.length);
break;
case 8:
EightAlgorithms.lstRadixSort(arr, arr.length, 10, 4);
break;
default:
break;
}
printArray(arr, arr.length);
}
}
}
|
最后是运行结果如下：
以上就是Java实现八个常用的排序算法的全部代码，希望大家对C++排序算法有更进一步的了解。