本文實(shí)現(xiàn)了八個(gè)常用的排序算法：插入排序、冒泡排序、選擇排序、希爾排序 、快速排序、歸并排序、堆排序和LST基數(shù)排序
首先是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; /* * 實(shí)現(xiàn)了八個(gè)常用的排序算法：插入排序、冒泡排序、選擇排序、希爾排序 * 以及快速排序、歸并排序、堆排序和LST基數(shù)排序 * @author gkh178 */public class EightAlgorithms { //插入排序：時(shí)間復(fù)雜度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; } } //冒泡排序：時(shí)間復(fù)雜度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; } } } } //選擇排序：時(shí)間復(fù)雜度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; } } //希爾排序：時(shí)間復(fù)雜度介于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; } } } //快速排序：時(shí)間復(fù)雜度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; } //歸并排序：時(shí)間復(fù)雜度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++]; } } //堆排序：時(shí)間復(fù)雜度o(nlgn) public static void heapSort(int a[], int n) { builtMaxHeap(a, n);//建立初始大根堆 //交換首尾元素，并對(duì)交換后排除尾元素的數(shù)組進(jìn)行一次上調(diào)整 for (int i = n - 1; i >= 1; --i) { int temp = a[0]; a[0] = a[i]; a[i] = temp; upAdjust(a, i); } } //建立一個(gè)長度為n的大根堆 public static void builtMaxHeap(int a[], int n) { upAdjust(a, n); } //對(duì)長度為n的數(shù)組進(jìn)行一次上調(diào)整 public static void upAdjust(int a[], int n) { //對(duì)每個(gè)帶有子女節(jié)點(diǎn)的元素遍歷處理，從后到根節(jié)點(diǎn)位置 for (int i = n / 2; i >= 1; --i) { adjustNode(a, n, i); } } //調(diào)整序號(hào)為i的節(jié)點(diǎn)的值 public static void adjustNode(int a[], int n, int i) { //節(jié)點(diǎn)有左右孩子 if (2 * i + 1 <= n) { //右孩子的值大于節(jié)點(diǎn)的值，交換它們 if (a[2 * i] > a[i - 1]) { int temp = a[2 * i]; a[2 * i] = a[i - 1]; a[i - 1] = temp; } //左孩子的值大于節(jié)點(diǎ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; } //對(duì)節(jié)點(diǎn)的左右孩子的根節(jié)點(diǎn)進(jìn)行調(diào)整 adjustNode(a, n, 2 * i); adjustNode(a, n, 2 * i + 1); } //節(jié)點(diǎn)只有左孩子，為最后一個(gè)有左右孩子的節(jié)點(diǎn) else if (2 * i == n) { //左孩子的值大于節(jié)點(diǎ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; } } } //基數(shù)排序的時(shí)間復(fù)雜度為o(distance(n+radix)),distance為位數(shù)，n為數(shù)組個(gè)數(shù)，radix為基數(shù) //本方法是用LST方法進(jìn)行基數(shù)排序，MST方法不包含在內(nèi) //其中參數(shù)radix為基數(shù)，一般為10；distance表示待排序的數(shù)組的數(shù)字最長的位數(shù)；n為數(shù)組的長度 public static void lstRadixSort(int a[], int n, int radix, int distance) { int[] newA = new int[n];//用于暫存數(shù)組 int[] count = new int[radix];//用于計(jì)數(shù)排序，保存的是當(dāng)前位的值為0 到 radix-1的元素出現(xiàn)的的個(gè)數(shù) int divide = 1; //從倒數(shù)第一位處理到第一位 for (int i = 0; i < distance; ++i) { System.arraycopy(a, 0, newA, 0, n);//待排數(shù)組拷貝到newA數(shù)組中 Arrays.fill(count, 0);//將計(jì)數(shù)數(shù)組置0 for (int j = 0; j < n; ++j) { int radixKey = (newA[j] / divide) % radix; //得到數(shù)組元素的當(dāng)前處理位的值 count[radixKey]++; } //此時(shí)count[]中每個(gè)元素保存的是radixKey位出現(xiàn)的次數(shù) //計(jì)算每個(gè)radixKey在數(shù)組中的結(jié)束位置，位置序號(hào)范圍為1-n for (int j = 1; j < radix; ++j) { count[j] = count[j] + count[j - 1]; } //運(yùn)用計(jì)數(shù)排序的原理實(shí)現(xiàn)一次排序，排序后的數(shù)組輸出到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); } } } |
最后是運(yùn)行結(jié)果如下：
以上就是Java實(shí)現(xiàn)八個(gè)常用的排序算法的全部代碼，希望大家對(duì)C++排序算法有更進(jìn)一步的了解。
