排序算法(Java)

0707添加桶排序

桶排序

参考链接

排序分类

内排序和外排序。
在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存(并不是不需要内存),则称为外排序。

时间复杂度

时间复杂度

总结

内排序分类

插入排序

直接插入排序、二分法插入排序、希尔排序。
思想:每步将一个待排序的记录,按其顺序码大小插入到前面已经排序的字序列的合适位置,直到全部插入排序完为止。
关键问题:在前面已经排好序的序列中找到合适的插入位置。

选择排序

简单选择排序、堆排序
思想:每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置,直到全部排完。
关键问题:在剩余的待排序记录序列中找到最小关键码记录。

交换排序

冒泡排序、快速排序

归并排序

基本思想:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

基数排序

稳定性

结论

稳定:冒泡排序(相同元素不交换)、插入排序(当前元素大于待排元素,则在当前元素之前插入待排)、归并排序(两个元素的序列如果元素相等不交换)和基数排序
不稳定:选择排序(挑出当前最小放到对应的位置,这个交换过程可能会影响稳定性)、快速排序、希尔排序、堆排序

详解

冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无 聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改 变,所以冒泡排序是一种稳定排序算法。

选择排序

选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个 元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么 交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

插入排序

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开 始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相 等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳 定的。

快速排序

快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11, 现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j] 交换的时刻。

归并排序

归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有 序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定 性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结 果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

基数排序

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优 先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。

希尔排序(shell)

希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小, 插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元 素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

堆排序

我们知道堆的结构是节点i的孩子为2i和2i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, …1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没 有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

平均时间复杂度

O(n^2):直接插入排序,简单选择排序,冒泡排序。
在数据规模较小时(9W内),直接插入排序,简单选择排序差不多。当数据较大时,冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本上是相邻元素进行比较,基本上都是稳定的。
O(nlogn):快速排序,归并排序,希尔排序,堆排序。
其中,快排是最好的, 其次是归并和希尔,堆排序在数据量很大时效果明显。

排序算法的选择

数据规模较小

  1. 待排序列基本序的情况下,可以选择直接插入排序;
  2. 对稳定性不作要求宜用简单选择排序,对稳定性有要求宜用插入或冒泡

数据规模不是很大

  1. 完全可以用内存空间,序列杂乱无序,对稳定性没有要求,快速排序,此时要付出log(N)的额外空间。
  2. 序列本身可能有序,对稳定性有要求,空间允许下,宜用归并排序

数据规模很大

  1. 对稳定性有求,则可考虑归并排序。
  2. 对稳定性没要求,宜用堆排序

序列初始基本有序(正序)

宜用直接插入,冒泡

代码

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
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Sort {
public static void main(String[] args) {
int[] a = new int[] { 8, 1, 6, 11, 2, 4, 23, 5, 158, 45, 95, 21, 0 };
radixSort(a);
// for (int num : a) {
// System.out.print(num + ",");
// }
System.out.println(Arrays.toString(a));
}
// -----------------------------------插入排序--------------------------------
/*
* 插入排序 思想:每步将一个待排序的记录,按其顺序码大小插入到前面已经排序的字序列 的
* 合适位置(从后向前找到合适位置后)直到全部插入排序完为止。
*/
public static void insertSort(int[] a) {
for (int i = 1; i < a.length; i++) {
// 将当前需要排序的元素保存在临时变量中
int t = a[i], j;
// 从i-1开始
for (j = i - 1; j >= 0 && a[j] > t; j--) {
// 带排序元素比之前元素小,则将大元素后移
a[j + 1] = a[j];
}
// 因为出循环之前j被--过
a[j + 1] = t;
}
}
/*
* 二分法插入排序 思想:二分法插入排序的思想和直接插入一样,只是找合适的插入位置的方式 不同,
* 这里是按二分法找到合适的位置,可以减少比较的次数。
*/
public static void binarySort(int[] a, int n) {
for (int i = 2; i < n; i++) {
int t = a[i];
int left = 0, right = i - 1, middle = 0;
// 二分查找的思想
while (left <= right) {
middle = (left + right) / 2;
if (t < a[middle])
right = middle - 1;
else {
left = middle + 1;
}
}
// 找到了插入的位置就在left处,将之后的元素后移
for (int j = i - 1; j >= left; j--) {
a[j + 1] = a[j];
}
// 将待排序元素放到需要放的位置上
a[left] = t;
}
}
/*
* 希尔排序(shell sort) 基本思想:先取一个小于n的整数d1作为第一个增量,把文件
* 的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中 先在各组内进行直接
* 插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1) ,
* 即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
*/
public static void shellSort(int[] a, int n) {
while (true) {
n = n / 2;
// 分为n/2组
for (int x = 0; x < n; x++) {
// 各组进行直接插入排序
for (int i = x + n; i < a.length; i = i + n) {
int t = a[i], j;
for (j = i - n; j >= 0 && a[j] > t; j = j - n) {
a[j + n] = a[j];
}
a[j + n] = t;
}
}
if (n == 1) {
break;
}
}
}
// -----------------------------------选择排序--------------------------------
/*
* 基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中
* 再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。
*/
public static void selectSort(int[] a, int n) {
for (int i = 0; i < a.length; i++) {
int t = a[i], index = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < t) {
// 记录当前获取的最小值
t = a[j];
index = j;
}
}
// 将最小值和a[i]进行交换
a[index] = a[i];
a[i] = t;
}
}
/*
* 用大根堆排序的基本思想
*
* ① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
* ②再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序
* 区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key
* ③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次
* 将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的
* 无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,
* 同样要将R[1..n-2]调整为堆。 直到无序区只有一个元素为止。
*
* 大根堆排序算法的基本操作: ① 初始化操作:将R[1..n]构造为初始堆; ②
* 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新
* 的无序区调整为堆(亦称重建堆)。注意:①只需做n-1趟排序,选出较大的n-1个关键字即可以
* 使得文件递增有序。②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序
* 和直接选择排序相反:在任何时刻堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
*/
public static void heapSort(int[] a, int length) {
for (int i = 0; i < length - 1; i++) {
// 建堆
buildMaxHeap(a, length - 1 - i);
// 交换堆顶和最后一个元素
swap(a, 0, length - 1 - i);
}
}
// 对数组从0到lastIndex建大顶堆
public static void buildMaxHeap(int[] data, int lastIndex) {
// 从lastIndex处节点(最后一个节点)的父节点开始,(lastIndex - 1) / 2为lastIndex的父节点
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
// t保存正在判断的节点
int t = i;
// 如果当前t节点的子节点存在
while (t * 2 + 1 <= lastIndex) {
// 用biggerIndex记录t节点的左子节点的索引
int biggerIndex = 2 * t + 1;
// 如果左子节点的索引biggerIndex小于lastIndex,即说明t节点的右子节点存在
if (biggerIndex < lastIndex) {
// 若果右子节点的值较大
if (data[biggerIndex] < data[biggerIndex + 1]) {
// biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
// 如果k节点的值小于其较大的子节点的值
if (data[t] < data[biggerIndex]) {
// 交换他们
swap(data, t, biggerIndex);
// 将biggerIndex赋予t,开始while循环的下一次循环,重新保证t节点的值大于其左右子节点的值
t = biggerIndex;
} else {
break;
}
}
}
}
// 交换
private static void swap(int[] data, int i, int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
// -----------------------------------交换排序--------------------------------
/*
* 基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数
* 依次进行比较和调整,让较大的数往右移动,较小的往左移动。即:每当两相邻的数比较后发现它
* 们的排序与排序要求相反时,就将它们互换。
*/
public static void bubbleSort(int[] a, int n) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length - i - 1; j++) {
// 这里 -i主要是每遍历一次都已经把最大的i个数移到右边,没有必要再替换
// 如果元素比其后元素大,则将其右移
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
/*
* 基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排
* 序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后
* 的正确位置然后再用同样的方法递归地排序划分的两部分。
*/
public static void quickSort(int[] a, int left, int right) {
if (left > right)
return;
// temp存基准数
int temp = a[left], i = left, j = right, t;
// 循环直到两个哨兵相遇
while (i != j) {
// 哨兵开始移动,元素比基准大j向左移动,一直到找到比基准小的为止
while (a[j] >= temp && i < j)
j--;
// 再找左边的
while (a[i] <= temp && i < j)
i++;
// 交换两个数在数组中的位置
if (i < j) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
// i==j,两个哨兵相遇,该位置即为基准需要归位的位置,交换
a[left] = a[i];
a[i] = temp;
quickSort(a, left, i - 1);// 递归处理左边
quickSort(a, i + 1, right);// 递归处理右边
}
/*
* 基本思想:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把
* 待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
*/
public static void mergeSort(int[] a, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
// 对左边进行递归
mergeSort(a, left, middle);
// 对右边进行递归
mergeSort(a, middle + 1, right);
// 合并
merge(a, left, middle, right);
}
}
public static void merge(int[] a, int left, int middle, int right) {
int[] tmpA = new int[a.length];
int mid = middle + 1; // 右边部分的起始位置
int tmp = left;
int t = left;
while (left <= middle && mid <= right) {
// 从两个数组中选取较小的数放入临时数组
if (a[left] <= a[mid]) {
tmpA[t++] = a[left++];
} else {
tmpA[t++] = a[mid++];
}
}
// 将剩余的部分放入临时数组
while (left <= middle) {
tmpA[t++] = a[left++];
}
while (mid <= right) {
tmpA[t++] = a[mid++];
}
// 将临时数组复制回原数组
while (tmp <= right) {
a[tmp] = tmpA[tmp++];
}
}
// ----------------------------------基数排序-----------------------------
/*
* 基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,
* 从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一 个有序序列。
*/
private static void radixSort(int[] array) {
// 找到最大数,确定要排序几趟
int max = 0;
for (int i = 0; i < array.length; i++) {
if (max < array[i]) {
max = array[i];
}
}
// 判断位数
int digits = 0;
while (max > 0) {
max = max / 10;
digits++;
}
// 0-9十个数字,建立十个队列
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList q = new ArrayList();
queue.add(q);
}
// 进行digits次分配和收集
for (int i = 0; i < digits; i++) {
// 分配
for (int j = 0; j < array.length; j++) {
// 获得array[j]第i+1为值
int x = array[j] % (int) Math.pow(10, i + 1)
/ (int) Math.pow(10, i);
ArrayList q2 = queue.get(x);
q2.add(array[j]);
// 更新x位置上的元素q2
queue.set(x, q2);
}
// 收集
int count = 0;
for (int j = 0; j < 10; j++) {
while (queue.get(j).size() > 0) {
ArrayList<Integer> q3 = queue.get(j);
array[count] = q3.get(0);
q3.remove(0);
count++;
}
}
}
}
}