稳定排序
| 排序法 |
平均时间 |
最差时间 |
额外空间 |
稳定性 |
数据量 |
| 冒泡排序 |
O(n2) |
O(n2) |
O(1) |
稳定 |
数量较小时使用 |
| 插入排序 |
O(n2) |
O(n2) |
O(1) |
稳定 |
大部分有序时使用 |
| 基数排序 |
O(logRB) |
O(logRB) |
O(n) |
稳定 |
B是真数(0-9)，R是基数 |
| 归并排序 |
O(nlogn) |
O(nlogn) |
O(1) |
稳定 |
数量大时使用 |
不稳定排序
| 排序法 |
平均时间 |
最差时间 |
额外空间 |
稳定性 |
数据量 |
| 交换排序 |
O(n2) |
O(n2) |
O(1) |
不稳定 |
数量较小时使用 |
| 快速排序 |
O(nlogn) |
O(n2) |
O(nlogn) |
不稳定 |
数量大时使用 |
| 选择排序 |
O(n2) |
O(n2) |
O(1) |
不稳定 |
数量较小时使用 |
| 希尔排序 |
O(nlogn) |
O(ns) 1 < s < 2 |
O(1) |
不稳定 |
s 是所选分组 |
| 堆排序 |
O(nlogn) |
O(nlogn) |
O(1) |
不稳定 |
数量大时使用 |
交换排序
int[] arr = new int[2000];
for (int i = 0; i < arr.length; i ++) {
arr[i] = new Random().nextInt(20000);
}
System.out.println("start --> " + System.currentTimeMillis());
for (int i = arr.length - 1; i >= 0; i --) {
for (int j = i - 1; j >= 0; j --) {
if (arr[i] < arr[j]) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
}
System.out.println("end --> " + System.currentTimeMillis());
for (int i = 0; i < arr.length; i ++) {
System.out.print(arr[i] + ", ");
}
System.out.println();
选择排序
for (int i = 0; i < arr.length; i ++) {
arr[i] = new Random().nextInt(20);
}
System.out.println("start --> " + System.currentTimeMillis());
for (int i = 0; i < arr.length; i ++) {
int temp = i;
for (int j = i + 1; j < arr.length; j ++) {
if (arr[temp] < arr[j]) {
temp = j;
}
}
if (temp != i) {
arr[i] = arr[temp] ^ arr[i];
arr[temp] = arr[temp] ^ arr[i];
arr[i] = arr[temp] ^ arr[i];
}
}
System.out.println("end --> " + System.currentTimeMillis());
for (int i = 0; i < arr.length; i ++) {
System.out.print(arr[i] + ", ");
}
