Java 10种排序算法的实现和比较
2022-04-22 本文已影响0人
rome753
https://www.cnblogs.com/hokky/p/8529042.html
这篇文章总结得非常好，图表很详细，是Python的。下面我用Java实现一下。
1 比较类排序
1.1 冒泡排序
比较和交换相邻两个数，每一趟将最大的数移动到最后一位（参与比较的）。下一趟最后一位不动，对剩下的数重复前面的操作。
static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
1.2 选择排序
每一趟比较出最小的数，放到第一位（参与比较的）。下一趟，第一位不动，对剩下的数重复前面的操作。
static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = arr[i];
int minI = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < min) {
min = arr[j];
minI = j;
}
}
int temp = arr[i];
arr[i] = arr[minI];
arr[minI] = temp;
}
}
1.3 插入排序
从第一位开始，将左边数组视为排好序的，把左边数组的右边第一个数插入到左边数组中。插入方法是对左边数组从右向左比较和右移。每一趟左边数组向右扩大一位。
static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int cur = arr[i];
int j = i - 1;
for (; j >= 0; j--) {
if (arr[j] > cur) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = cur;
}
}
1.4 希尔排序
选一个gap（间隔），将数组分成gap组（k = 0 ~ gap-1）
0, 0 + gap, 0 + gap * 2...
1, 1 + gap, 1 + gap * 2...
k, k + gap, k + gap * 2...
对每组进行插入排序。然后gap缩减，重复前面的操作。
gap的选择对算法效率是有影响的，简单的做法是初始值使用数组长度n/2，下一次gap减半，直到gap=1。有兴趣可以研究选择不同gap的效率。
希尔排序是插入排序的高级版。也可以说插入排序是 gap = 1 的希尔排序，插入排序是希尔排序的最后一步。下面的算法我特意使用了跟前面插入排序相同的循环变量i、j，可以明显看出内部的插入排序。
static void shellSort(int[] arr) {
int gap = arr.length / 2;
while(gap >= 1) {
// 分为gap组
for (int k = 0; k < gap; k++) {
// 对每组进行插入排序
for (int i = k + gap; i < arr.length; i += gap) {
int cur = arr[i];
int j = i - gap;
for (; j >= 0; j -= gap) {
if (arr[j] > cur) {
arr[j + gap] = arr[j];
} else {
break;
}
}
arr[j + gap] = cur;
}
}
gap /= 2;
}
}
1.5 快速排序
选一个base（基准值），一般选数组第一位，从左右两边同时往中间比较和交换，保证数组左边的数都小于base，右边的都大于base。然后分别将左边和右边当成子数组递归调用前面的操作，直到数组长度为1。
快速排序跟冒泡排序一样是基于交换的，可以当做冒泡排序的高级版。它的代码非常对称有规律，边界值的判断需要非常严谨。
private static void quickSort(int[] arr, int low, int high) {
if (low >= high) {
return;
}
int i = low;
int j = high;
int base = arr[i];
while (i < j) {
while (i < j && arr[j] >= base) {
j--;
}
if (i < j) {
arr[i] = arr[j];
}
while (i < j && arr[i] < base) {
i++;
}
if (i < j) {
arr[j] = arr[i];
}
}
arr[i] = base;
quickSort(arr, low, i - 1);
quickSort(arr, i + 1, high);
}
1.6 堆排序
将数组看做一种特殊的数据结构：大顶堆。它是一颗完全二叉树，每个节点的值都大于它的左右子节点（如果有的话）的值。构建完大顶堆后，根节点就是数组最大值，把它跟最后一位交换。这样最大值就放到最后不动，对剩下的数重新整堆（注意是整堆不是建堆！），然后交换最大值，重复前面的操作。
我看的几乎所有的资料都没有强调“建堆”和“整堆”是两个不同的过程。
- 建堆（创建堆）只有第一次需要，它是从下向上遍历节点（从最后一个非叶子节点开始，位置是数组长度n / 2 - 1），对每一个节点进行整堆。建堆完成后，后面的操作不会彻底打乱堆，不需要重新建堆，只需要整堆。
- 整堆（调整堆）是将左右子节点的最大值和当前节点比较，如果子节点的值更大，就跟当前节点交换，然后对交换后的子节点进行递归整堆。
因为完全二叉树的子节点位置可以直接计算 —— 节点位置 i，左子节点是 i * 2 + 1，右子节点是 i * 2 + 2，所以可以用循环代替递归。
堆排序跟选择排序一样每次选出最大值放到末尾，可以当作选择排序的高级版。
static void heapSort(int[] arr) {
heapBuild(arr, arr.length);
for (int len = arr.length; len > 0; len--) {
int temp = arr[0];
arr[0] = arr[len - 1];
arr[len - 1] = temp;
heapAdjust(arr, 0, len - 1);
}
}
// 建堆
private static void heapBuild(int[] arr, int len) {
for (int i = len / 2 - 1; i >= 0; i--) {
heapAdjust(arr, i, len);
}
}
// 整堆
private static void heapAdjust(int[] arr, int i, int len) {
// if (i >= len) { // 没有子节点
// return;
// }
while (i < len) {
int left = i * 2 + 1;
if (left >= len) {
return;
}
int right = left + 1;
int iNext = i;
if (right >= len || arr[left] > arr[right]) { // 没有右节点或左边大于右边
if (arr[left] > arr[i]) {
iNext = left;
}
} else { // 有右节点且右边不小于左边
if (arr[right] > arr[i]) {
iNext = right;
}
}
if (iNext == i) {
return;
}
int temp = arr[iNext];
arr[iNext] = arr[i];
arr[i] = temp;
i = iNext;
}
// heapAdjust(arr, iNext, len);
}
1.7 归并排序
将数组分成左右两个子数组，对它们分别进行递归归并排序，排序之后再将两个有序数组合并，合并方法是：从左向右同时遍历两个数组，比较大小，将小的放进缓存数组里，坐标右移；同时遍历完后再从当前位置分别遍历两个数组一次，将上次没遍历完的元素全部放进缓存数组，然后将缓存数组复制到原数组。
归并排序利用递归思想，非常巧妙：合并子数组前，认为子数组排序好了；子数组认为子子数组排序好了...直到碰到数组长度1的递归收敛条件，才真正开始合并数组，合并完后上层数组开始合并，然后上上层...直到最外层合并完成。
static void mergeSort(int[] arr) {
mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
}
private static void mergeSort(int[] arr, int low, int high, int[] temp) {
if (low >= high) {
return;
}
int mid = (high + low) / 2;
mergeSort(arr, low, mid, temp);
mergeSort(arr, mid + 1, high, temp);
merge(arr, low, mid, high, temp);
}
private static void merge(int[] arr, int low, int mid, int high, int[] temp) {
int i0 = low, j0 = mid;
int i1 = mid + 1, j1 = high;
int k = low;
while(i0 <= j0 && i1 <= j1) {
if (arr[i0] < arr[i1]) {
temp[k++] = arr[i0++];
} else {
temp[k++] = arr[i1++];
}
}
while(i0 <= j0) {
temp[k++] = arr[i0++];
}
while(i1 <= j1) {
temp[k++] = arr[i1++];
}
for (int i = low; i <= high; i++) {
arr[i] = temp[i];
}
}
1.8 算法效率比较
public static void main(String[] args) {
check("bubble");
check("select");
check("insert");
check("shell");
check("quick");
check("merge");
check("heap");
}
static void check(String name) {
int n = 10000;
int[] arr = new int[n];
Random r = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = r.nextInt(n);
}
long t = System.currentTimeMillis();
switch (name) {
case "bubble":
bubbleSort(arr);
break;
case "select":
selectSort(arr);
break;
case "insert":
insertSort(arr);
break;
case "shell":
shellSort(arr);
break;
case "quick":
quickSort(arr);
break;
case "merge":
mergeSort(arr);
break;
case "heap":
heapSort(arr);
break;
default:
break;
}
t = System.currentTimeMillis() - t;
System.out.println(name + "Sort\t" + "time(ms): " + t);
}
生成一个长度n的随机数组，计算不同排序算法的运行时间，n从一万增加到一千万（超过十万后只计算高级排序的）。
n = 10000
bubbleSort time(ms): 50
selectSort time(ms): 19
insertSort time(ms): 26
shellSort time(ms): 4
quickSort time(ms): 2
mergeSort time(ms): 2
heapSort time(ms): 3
n = 100000
bubbleSort time(ms): 10922
selectSort time(ms): 1068
insertSort time(ms): 1974
shellSort time(ms): 19
quickSort time(ms): 29
mergeSort time(ms): 17
heapSort time(ms): 24
n = 1000000
shellSort time(ms): 153
quickSort time(ms): 105
mergeSort time(ms): 117
heapSort time(ms): 144
n = 10000000
shellSort time(ms): 2393
quickSort time(ms): 948
mergeSort time(ms): 1195
heapSort time(ms): 1849
从耗时可以简单分析出几点：
- 简单排序（冒泡、选择、插入）的耗时远远超过高级排序。几种简单排序耗时接近，几种高级排序耗时也接近。
- 简单排序里：数量增加后冒泡排序耗时是其他的几倍，因为它执行了更多无效的交换操作。
- 高级排序里：数量十万左右时，希尔排序和归并排序更快，其他数量都是快速排序和归并排序最快（这两种排序都是递归分治的思想）。
2 非比较排序
2.1 计数排序
遍历一遍数组，用另一个数组记录每个数出现的次数，然后把次数转换成数字数组。
它只能用来给数字排序，而且排序后的数组元素并不是原来的数组元素，相当于全部换了一遍，虽然数值相同。
static void countSort(int[] arr) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int a : arr) {
if (a < min) {
min = a;
}
if (a > max) {
max = a;
}
}
int[] bucket = new int[max - min + 1];
for (int a : arr) {
bucket[a - min]++;
}
int cur = min;
int i = 0;
for (int b: bucket) {
while(b-- > 0) {
arr[i++] = cur;
}
cur++;
}
}
2.2 桶排序
先遍历一遍数组，根据数字大小给数字分组，也就是放到不同的“桶”里。再对桶里的数字用某种方法排序。由于每个桶的大小不确定，只能用高级数据结构List保存。
为了方便，桶里的数字我直接用Collections.sort方法排序了。
static void bucketSort(int[] arr) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int a : arr) {
if (a < min) {
min = a;
}
if (a > max) {
max = a;
}
}
int dis = max - min;
if (dis == 0) {
return;
}
int bMAX = 1000;
int bn = dis < bMAX ? dis : bMAX;
int gap = dis / bn + 1;
List<List<Integer>> bucket = new ArrayList<>();
for (int i = 0; i < bn; i++) {
bucket.add(new ArrayList<>());
}
for (int a: arr) {
int i = (a - min) / gap;
bucket.get(i).add(a);
}
int k = 0;
for (int i = 0; i < bn; i++) {
List<Integer> bi = bucket.get(i);
Collections.sort(bi);
for (int b: bi) {
arr[k++] = b;
}
}
}
2.3 基数排序
把数字按十进制的每一位排序。建立0~9十个桶，先按个位是几把数字放进对应的桶里；然后按桶里顺序取出来，按数字的十位放进桶里...直到最大数字的最高位为止。
它也是一种桶排序，每个桶的大小也不确定，需要用List保存。它遍历的次数是最大数字的十进制位数，每次遍历需要把数字从数组倒进桶里，遍历完再放回数组。
static void radixSort(int[] arr) {
int max = Integer.MIN_VALUE;
for (int a : arr) {
if (a > max) {
max = a;
}
}
List<List<Integer>> bucket;
int m = 1;
while(m < max) {
bucket = new ArrayList<>();
for (int i = 0; i < 10; i++) {
bucket.add(new ArrayList<>());
}
for (int a: arr) {
int i = a / m % 10;
bucket.get(i).add(a);
}
int k = 0;
for (List<Integer> list: bucket) {
for (int a: list) {
arr[k++] = a;
}
}
m *= 10;
}
}
2.4 算法效率比较
n = 10000
countSort time(ms): 2
bucketSort time(ms): 22
radixSort time(ms): 10
n = 100000
countSort time(ms): 11
bucketSort time(ms): 79
radixSort time(ms): 26
n = 1000000
countSort time(ms): 20
bucketSort time(ms): 280
radixSort time(ms): 238
n = 10000000
countSort time(ms): 168
bucketSort time(ms): 2172
radixSort time(ms): 2726
简单分析
- 因为只遍历一遍，所以计数排序的速度非常快，比另外两种快10倍，比前面表现最好的快速排序还快5倍！
- 因为需要用高级数据结构，桶排序和基数排序比其他的高级排序至少慢一倍。
3 搞笑类排序
3.1 睡眠排序
遍历一遍数组，每个数开启子线程，按数字大小设置不同的延时，按延时结束的时间将数字放到一个新的集合中。
虽然是搞笑类，但是睡眠排序的确是可以工作的！并且是将时间转换成空间的思想。为了并发安全，新的集合使用了线程安全的Vector。睡眠时间不能设置得太小，需要统一放大一些，否则会受到CPU调度等时间影响。
static void sleepSort(int[] arr) {
Vector<Integer> temp = new Vector<>();
for (int a: arr) {
Thread t = new Thread(){
@Override
public void run() {
try {
Thread.sleep(a * 10);
} catch (InterruptedException e) {
e.printStackTrace();
}
temp.add(a);
if (temp.size() == arr.length) {
for (int i = 0; i < arr.length; i++) {
arr[i] = temp.get(i);
}
}
};
};
t.start();
}
}
