title: 几种常见排序方法的优化(上) toc: true date: 2020-02-24 15:38:47 cover: https://img.paulzzh.com/touhou/random?31 categories: 算法 tags: [算法, 排序]
最近花了几天重温了一下《算法(第四版)》, 重新把书中的算法实现了一下, 并且思索了一下, 把常见的比较排序算法都给优化了一下, 然后进行了性能测试. 也算是复习了一下排序算法吧.
阅读本篇之前最好有常见几种基于的比较排序算法的基础
本文内容包括:
源代码:
如果觉得文章写的不错, 可以关注微信公众号: Coder张小凯
内容和博客同步更新~
<br/>
<!--more-->对于一般的排序方法, 都会包括大量的数组访问操作、比较操作(less)以及交换操作(exch)
此外还需要一些用来检验是否已经有序的方法, 如:
为了实现代码的复用性, 本文创建了一个基本的排序抽象类BaseSort, 其中实现了排序类都应具有的一些方法
BaseSort.java
package algorithm.sort;
import algorithm.util.iostream.StdOut;
import java.util.Arrays;
/**
* 排序类的例子
*
* 主要实现了比较less()方法, 交换exch()方法
*
* 以及输出数组show(), 排序验证isSorted()方法
*
* @author zk
*/
public abstract class BaseSort {
/**
* 排序类应当实现的具体排序方法
*
*/
private static void sort() {}
/**
* 比较v和w, 返回v是否比w小
*
* @param v 比较值v
* @param w 比较值w
* @return v < w返回true, v >= w返回false
*/
public static <K extends Comparable<K>> boolean less(K v, K w) {
return v.compareTo(w) < 0;
}
/**
* 在数组a中交换索引i, j对应元素
*
* @param a 数组a
* @param i 索引i
* @param j 索引j
*/
public static <K extends Comparable<K>> void exch(K[] a, int i, int j) {
K t = a[i];
a[i] = a[j];
a[j] = t;
}
public static <K extends Comparable<K>> void show(K[] a) {
Arrays.stream(a).forEach(x -> System.out.print(x + " "));
StdOut.println();
}
/**
* 判断数组a是否有序
*
* @param a 数组
* @return a有序?
*/
public static <K extends Comparable<K>> boolean isSorted(K[] a) {
return isSorted(a, 0, a.length - 1);
}
public static boolean isSorted(int[] a) {
return isSorted(a, 0, a.length - 1);
}
public static boolean isSorted(double[] a) {
return isSorted(a, 0, a.length - 1);
}
/**
* 判断数组a[lo...hi]区间是否有序
*/
public static <K extends Comparable<K>> boolean isSorted(K[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}
public static boolean isSorted(int[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}
public static boolean isSorted(double[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}
}
<br/>
说明:
为了更好的复用排序算法, 本文尽量使用实现了Comparable接口的泛型来实现算法, 并通过less代替比较运算符进行比较
<br/>
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端
BubbleSort.java
/**
* 冒泡排序
*
* 每一轮遍历将最大的元素放在当前排序序列末尾, 并且当前数组个数从末端减一
*
* 相比于选择排序, 冒泡排序使用了更多的交换!
*
* 平均时间: O(N^2)
*
* 最好时间: O(N^2)
*
* 最坏时间: O(N^2)
*
* 空间: O(1)
*
* @author zk
*/
public class BubbleSort extends BaseSort {
/**
* 冒泡排序最基本实现
*/
public static <K extends Comparable<K>> void sort(K[] a) {
// 确定排序趟数
// 最后一次循环仅有一个元素, 所以可以i < len - 1
for (int i = 0, len = a.length; i < len - 1; i++) {
// 确定每趟比较次数
for (int j = 0; j < len - i - 1; j++) {
if (less(a[j + 1], a[j])) {
exch(a, j, j + 1);
}
}
}
}
}
① 增加排序结束标记
在交换的地方加一个标记，如果那一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去
<br/>
注: 这里用到了冒泡每次都要交换的特点, 而选择排序仅仅交换一次!
public static <K extends Comparable<K>> void sortWithFlag(K[] a) {
for (int i = 0, len = a.length; i < len - 1; i++) {
boolean finished = true; // 在此加入一个标志位, 每次循环开始则更新
for (int j = 0; j < len - 1 - i; j++) {
if (less(a[j + 1], a[j])) {
exch(a, j, j + 1);
finished = false; // 出现交换则改为false
}
}
if (finished) {
return;
}
}
}
② 修改末尾有序子数组边界
对于前面大部分是无序而后边小半部分有序的数据, 如: (1，2，5，7，4，3，6，8，9)
排序效率也不可观, 对于这种类型数据，我们可以继续优化:
可以记下最后一次交换的位置，后边没有交换，必然是有序的; 然后下一次排序从第一个比较到上次记录的位置结束即可
public static <K extends Comparable<K>> void sortWithCheckBound(K[] a) {
// k作为最后一次交换的位置循环边界
int len = a.length;
// pos用来记录最后一次交换的位置
// k作为循环终止条件(因为需要在循环内部改动pos!)
int pos = 0, k = len - 1;
for (int i = 0; i < len - 1; i++) {
boolean finished = true;
for (int j = 0; j < k; j++) {
if (less(a[j + 1], a[j])) {
exch(a, j, j + 1);
finished = false;
// 交换元素，记录最后一次交换的位置
pos = j;
}
}
if (finished) break;
// 下一次比较到记录位置即可
k = pos;
}
}
③ 双边排序
一次排序可以确定两个值，正向扫描找到最大值交换到最后，反向扫描找到最小值交换到最前面
同时, 可以记录左右两边均有序时的bound(后面选择排序的优化也进行了类似的操作)
public static <K extends Comparable<K>> void sortBilaterally(K[] a) {
// k作为最后一次交换的位置循环边界
int len = a.length;
// leftBound, rightBound记录左右冒泡最后一次交换的位置
// leftVar, rightVar作为循环终止条件(因为需要在循环内部改动pos)
int leftBound = 0, leftVar = 0, rightBound = len - 1, rightVar = len - 1;
// 同时找最大值的最小需要两个下标遍历
int n = 0;
for (int i = 0; i < len - 1; i++) {
boolean finished = true;
// 正向寻找最大值
for (int j = leftVar; j < rightVar; j++) {
if (less(a[j + 1], a[j])) {
exch(a, j, j + 1);
// 加入标记
finished = false;
// 交换元素，记录正向冒泡最后一次交换的位置
rightBound = j;
}
}
// 如果没有交换过元素，则已经有序,直接结束
if (finished) return;
// 下一次正向冒泡比较到记录位置即可
rightVar = rightBound;
// 反向寻找最小值
for (int j = rightVar; j > leftVar; j--) {
if (less(a[j], a[j - 1])) {
exch(a, j, j - 1);
finished = false;
leftBound = j;
}
}
leftVar = leftBound;
}
}
<br/>
性能测试代码说明:
性能测试每次会创建两组数组, 分别为含有大量离散元素的随机数组和大量重复元素的随机数组, 分别排序
① 随机数数组
RandomArrayUtil.getRandomBoxedIntArray(Int floor, int ceil, int len)方法:
创建一个len大小的元素在[floor, ceil)区间的随机数数组
② 定时器Stopwatch
每次new定时器时, 内部记录一个System.currentTimeMillis, 调用elapsedTime()方法, 返回一个经过的秒数
③ 保证有序
简单使用assert isSorted(arr)保证排序算法逻辑是正确的!
④ 输出为总时间
第二次输出的时间为random + duplicate, 即排序两类数组所需要的总时间
具体工具类代码见: https://github.com/JasonkayZK/Java_Algorithm/tree/master/src/main/java/algorithm/util
针对冒泡排序中各种优化方法的优化效果, 通过下面的代码进行性能测试
BubbleSortTest.java
package algorithm.sort;
import algorithm.util.iostream.StdOut;
import algorithm.util.random.RandomArrayUtil;
import algorithm.util.watch.Stopwatch;
import org.junit.Test;
import java.util.Arrays;
import static algorithm.sort.BaseSort.isSorted;
import static algorithm.sort.BaseSort.show;
import static algorithm.sort.BubbleSort.sort;
import static algorithm.sort.BubbleSort.sortBilaterally;
import static algorithm.sort.BubbleSort.sortWithCheckBound;
import static algorithm.sort.BubbleSort.sortWithFlag;
public class BubbleSortTest {
/**
* 对冒泡排序的各种方法进行性能测试
*/
@Test
public void sortCompare() {
// 正常随机数组
Integer[] a11 = RandomArrayUtil.getRandomBoxedIntArray(0, 1000000, 50000);
Integer[] a12 = Arrays.copyOf(a11, a11.length);
Integer[] a13 = Arrays.copyOf(a11, a11.length);
Integer[] a14 = Arrays.copyOf(a11, a11.length);
// 大量重复数组
Integer[] a21 = RandomArrayUtil.getRandomBoxedIntArray(0, 100, 50000);
Integer[] a22 = Arrays.copyOf(a21, a21.length);
Integer[] a23 = Arrays.copyOf(a21, a21.length);
Integer[] a24 = Arrays.copyOf(a21, a21.length);
System.out.println("Array created!");
Stopwatch stopwatch = new Stopwatch();
sort(a11);
StdOut.printf("%s (%.2f seconds)\n", "sort method[random]:", stopwatch.elapsedTime());
sort(a21);
StdOut.printf("%s (%.2f seconds)\n", "sort method[random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a11);
assert isSorted(a21);
System.out.println();
stopwatch = new Stopwatch();
sortWithFlag(a12);
StdOut.printf("%s (%.2f seconds)\n", "sortWithFlag method[random]:", stopwatch.elapsedTime());
sortWithFlag(a22);
StdOut.printf("%s (%.2f seconds)\n", "sortWithFlag method[random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a12);
assert isSorted(a22);
System.out.println();
stopwatch = new Stopwatch();
sortWithCheckBound(a13);
StdOut.printf("%s (%.2f seconds)\n", "sortWithCheckBound method[random]:", stopwatch.elapsedTime());
sortWithCheckBound(a23);
StdOut.printf("%s (%.2f seconds)\n", "sortWithCheckBound method[random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a13);
assert isSorted(a23);
System.out.println();
stopwatch = new Stopwatch();
sortBilaterally(a14);
StdOut.printf("%s (%.2f seconds)\n", "sortBilaterally method[random]:", stopwatch.elapsedTime());
sortBilaterally(a24);
StdOut.printf("%s (%.2f seconds)\n", "sortBilaterally method[random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a14);
assert isSorted(a24);
}
}
分别对五万个随机数组和随机重复数组排序, 结果如下:
sort method[random]: (9.04 seconds)
sort method[random + duplicate]: (15.53 seconds)
sortWithFlag method[random]: (8.02 seconds)
sortWithFlag method[random + duplicate]: (14.17 seconds)
sortWithCheckBound method[random]: (8.42 seconds)
sortWithCheckBound method[random + duplicate]: (15.16 seconds)
sortBilaterally method[random]: (6.47 seconds)
sortBilaterally method[random + duplicate]: (11.73 seconds)
从结果可见, 通过将最简单的冒泡排序进行逐步优化, 排序性能有了部分提高
冒泡排序性能冠军: sortBilaterally
性能提高原因: 因为使用了双向排序, 一次遍历排序出两个元素
<br/>
选择排序(Selection-sort)的工作原理:
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
以此类推，直到所有元素均排序完毕
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
SelectSort.java
package algorithm.sort;
/**
* 选择排序
*
* 每一轮遍历选择最小的的元素放在当前排序序列开头, 并且当前数组个数减一
*
* 平均时间: O(N^2) N^2/4比较 + N^2/4交换
*
* 最好时间: O(N^2) N-1比较 + 0交换
*
* 最坏时间: O(N^2) N^2/2比较 + N^2/2交换
*
* 空间: O(1)
*
* @author zk
*/
public class SelectSort extends BaseSort {
private SelectSort() {
}
/**
* 选择排序最简单实现
*/
public static <K extends Comparable<K>> void sort(K[] a) {
for (int i = 0, len = a.length; i < len; i++) {
int min = i;
for (int j = i + 1; j < len; j++) {
if (less(a[j], a[min])) {
min = j;
}
}
exch(a, i, min);
}
}
}
双边排序
每次排序可以选择两个: 最大和最小分别和左右位置进行交换
public static <K extends Comparable<K>> void sortBilaterally(K[] a) {
int left = 0, right = a.length - 1;
while (left < right) {
// 记录无序区最大元素和最小元素下标
int max = left, min = left;
for (int j = left + 1; j <= right; ++j) {
// 找最大元素下标
if (less(a[j], a[min])) {
min = j;
}
// 找最小元素下标
if (less(a[max], a[j])) {
max = j;
}
}
// 最小值如果是第一个则没有必要交换
if (min != left) {
exch(a, min, left);
}
// 这里很重要
// 如果最大元素下标是left,前面已经和最小元素交换了，此时最大元素下标应该是min
if (max == left) {
max = min;
}
// 最大值如果是最后一个则没必要交换
if (max != right) {
exch(a, max, right);
}
left++;
right--;
}
}
针对选择排序中各种优化方法的优化效果, 通过下面的代码进行性能测试
SelectSortTest.java
package algorithm.sort;
import algorithm.util.iostream.StdOut;
import algorithm.util.random.RandomArrayUtil;
import algorithm.util.watch.Stopwatch;
import org.junit.Test;
import java.util.Arrays;
import static algorithm.sort.BaseSort.isSorted;
import static algorithm.sort.BaseSort.show;
import static algorithm.sort.SelectSort.sort;
import static algorithm.sort.SelectSort.sortBilaterally;
public class SelectSortTest {
/**
* 对选择排序的各种方法进行性能测试
*/
@Test
public void compareTest() {
// 正常随机数组
Integer[] arr1 = RandomArrayUtil.getRandomBoxedIntArray(0, 1000000, 50000);
Integer[] a1 = Arrays.copyOf(arr1, arr1.length);
// 大量重复数组
Integer[] arr2 = RandomArrayUtil.getRandomBoxedIntArray(0, 100, 50000);
Integer[] a2 = Arrays.copyOf(arr2, arr2.length);
System.out.println("Array created!");
Stopwatch stopwatch = new Stopwatch();
sort(a1);
StdOut.printf("%s (%.2f seconds)\n", "sort [random]:", stopwatch.elapsedTime());
sort(a2);
StdOut.printf("%s (%.2f seconds)\n", "sort [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a1);
assert isSorted(a2);
System.out.println();
stopwatch = new Stopwatch();
sortBilaterally(arr1);
StdOut.printf("%s (%.2f seconds)\n", "sortBilaterally [random]:", stopwatch.elapsedTime());
sortBilaterally(arr2);
StdOut.printf("%s (%.2f seconds)\n", "sortBilaterally [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(arr1);
assert isSorted(arr2);
}
}
分别对五万个随机数组和随机重复数组排序, 结果如下:
sort [random]: (2.76 seconds)
sort [random + duplicate]: (4.45 seconds)
sortBilaterally [random]: (2.36 seconds)
sortBilaterally [random + duplicate]: (4.16 seconds)
从结果可见, 选择排序经过了优化, 性能略微提高
选择排序性能冠军: sortBilaterally
性能提高原因: 因为使用了双向排序, 一次遍历排序出两个元素
<br/>
它的工作原理是:
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入(类似于排序手中的扑克牌)
一般来说，插入排序都采用原地(in-place)在数组上实现
具体算法描述如下：
package algorithm.sort;
/**
* 插入排序
*
* 类似于将手中的扑克牌排序: 每次将一张牌插入到其他已经有序的牌中适当的位置
*
* 适用于小数组、已经近似有序的数组或者链表排序
*
* 平均时间: O(N^2) N^2/4比较 + N^2/4交换
*
* 最坏时间: O(N^2) N^2/2比较 + N^2/2交换
*
* 最好时间: O(N) N-1次比较 + 0次交换
*
* 空间: O(1)
*
* @author zk
*/
public class InsertionSort extends BaseSort {
/**
* 最基本的插入排序
*/
public static <K extends Comparable<K>> void sort(K[] a) {
// i可以从1开始, 当i = 0时, 内循环是没有意义的
for (int i = 1, len = a.length; i < len; ++i) {
// 将a[j]插入到a[j - 1], a[j - 2], ..., a[0]中
// 仅当a[j] < a[j - 1]时交换
// 否则因为前面是有序的, 所以一定有a[j] >= a[j - 1]而不需要再交换
for (int j = i; j > 0 && less(a[j], a[j - 1]); --j) {
exch(a, j, j - 1);
}
}
}
}
插入排序空间复杂度为O(1)且对于基本有序的序列可以很快完成排序, 因此适用于小数组、已经近似有序的数组或者链表排序
此外, 在堆排序, 快排, 桶排序等算法的优化中也经常使用插入排序
① 交换变为覆盖
由于最基本的插入排序中, 只要存在逆序就要交换, 所以可以将交换变为覆盖:
把当前待插入的元素取出，让当前元素与之前的所有元素进行一一比较
前一个元素大于当前元素直接覆盖，而到了最后当找到当前元素的合适位置时只需要一次交换即可
public static <K extends Comparable<K>> void sortWithOverride(K[] a) {
for (int i = 0, len = a.length; i < len; i++) {
// 将当前位置的元素取出
var cur = a[i];
int j = i;
// 如果这个元素比temp大就覆盖，否则就证明该元素之前已经有序就退出循环
for (; j > 0 && less(cur, a[j - 1]); j--) {
// 直接用前一个元素进行覆盖
a[j] = a[j - 1];
}
// 将temp中的元素插入合适位置
a[j] = cur;
}
}
② 折半插入排序
折半插入排序（Binary Insertion Sort）的排序算法过程:
不断的依次将元素插入前面已排好序的序列中，在寻找插入点时采用了二分查找
public static <K extends Comparable<K>> void binaryInsertSort(K[] a) {
for (int i = 1, len = a.length; i < len; i++) {
// 将当前位置的元素取出(暂存)
var temp = a[i];
// 二分查找插入index
int index = getInsertIndex(a, i, temp);
// 覆盖式的插入
int j = i - 1;
for (; j >= index + 1; j--) {
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
}
/**
* 二分法查找插入位置
*
* @param a 数组
* @param end 结束区域
* @param temp 寻找的键
* @return 插入index
*/
private static <K extends Comparable<K>> int getInsertIndex(K[] a, int end, K temp) {
int low = 0, high = end - 1;
while (low <= high) {
var m = low + (high - low) / 2;
if (less(temp, a[m])) high = m - 1;
else low = m + 1;
}
return high;
}
③ 二路插入排序算法
二路插入排序算法是在折半插入的基础上进行改进
折半插入在原先直接插入的基础上改进，通过折半查找，以较少的比较次数就找到了要插入的位置
但是在插入的过程中仍然没有减少移动次数，所以2路插入在此基础上改进，减少了移动次数，但是仍然并没有避免移动记录（如果要避免的话还是得改变存储结构）
因此我们设定一个辅助数组b，大小是原来数组相同的大小
将b[0]设为第一个原数组第一个数，通过设置head和tail指向整个有序序列的最小值和最大值
即为序列的尾部和头部，并且将其设置位一个循环数组，这样就可以进行双端插入
(之所以能减少移动次数的原因在于可以往2个方向移动记录，故称为2路插入)
具体操作思路：
@SuppressWarnings("unchecked")
public static <K extends Comparable<K>> void twoPathInsertSort(K[] a) {
int len = a.length;
K[] b = (K[]) new Comparable[len];
b[0] = a[0];
// 分别记录temp数组中最大值和最小值的位置
int i, first, tail, k;
first = tail = 0;
for (i = 1; i < len; i++) {
// 待插入元素比最小的元素小
if (less(a[i], b[first])) {
first = (first - 1 + len) % len;
b[first] = a[i];
}
// 待插入元素比最大元素大
else if (less(b[tail], a[i])) {
tail = (tail + 1 + len) % len;
b[tail] = a[i];
}
// 插入元素比最小大，比最大小
else {
k = (tail + 1 + len) % len;
// 当插入值比当前值小时，需要移动当前值的位置
while (less(a[i], b[((k - 1) + len) % len])) {
b[(k + len) % len] = b[(k - 1 + len) % len];
k = (k - 1 + len) % len;
}
// 插入该值
b[(k + len) % len] = a[i];
// 因为最大值的位置改变，所以需要实时更新tail的位置
tail = (tail + 1 + len) % len;
}
}
// 将排序记录复制到原来的顺序表里
for (k = 0; k < len; k++) {
a[k] = b[(first + k) % len];
}
}
④ 希尔排序法
见下希尔排序
对插入排序的各种方法进行性能测试
各种插入排序算法对十万个随机数组和随机重复数组排序
InsertionSortTest.java
package algorithm.sort;
import algorithm.util.iostream.StdOut;
import algorithm.util.random.RandomArrayUtil;
import algorithm.util.watch.Stopwatch;
import org.junit.Test;
import java.util.Arrays;
import static algorithm.sort.BaseSort.isSorted;
import static algorithm.sort.BaseSort.show;
import static algorithm.sort.InsertionSort.binaryInsertSort;
import static algorithm.sort.InsertionSort.shellSort;
import static algorithm.sort.InsertionSort.sort;
import static algorithm.sort.InsertionSort.sortWithOverride;
import static algorithm.sort.InsertionSort.twoPathInsertSort;
public class InsertionSortTest {
/**
* 对插入排序的各种方法进行性能测试
*
* 分别对十万个随机数组和随机重复数组排序, 结果如下:
*/
@Test
public void compareSort() {
// 正常随机数组
Integer[] a11 = RandomArrayUtil.getRandomBoxedIntArray(0, 1000000, 100000);
Integer[] a12 = Arrays.copyOf(a11, a11.length);
Integer[] a13 = Arrays.copyOf(a11, a11.length);
Integer[] a14 = Arrays.copyOf(a11, a11.length);
Integer[] a15 = Arrays.copyOf(a11, a11.length);
// 大量重复数组
Integer[] a21 = RandomArrayUtil.getRandomBoxedIntArray(0, 100, 100000);
Integer[] a22 = Arrays.copyOf(a21, a21.length);
Integer[] a23 = Arrays.copyOf(a21, a21.length);
Integer[] a24 = Arrays.copyOf(a21, a21.length);
Integer[] a25 = Arrays.copyOf(a21, a21.length);
System.out.println("Array created!");
Stopwatch stopwatch = new Stopwatch();
sort(a11);
StdOut.printf("%s (%.2f seconds)\n", "sort [random]:", stopwatch.elapsedTime());
sort(a21);
StdOut.printf("%s (%.2f seconds)\n", "sort [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a11);
assert isSorted(a21);
System.out.println();
stopwatch = new Stopwatch();
sortWithOverride(a12);
StdOut.printf("%s (%.2f seconds)\n", "sortWithOverride [random]:", stopwatch.elapsedTime());
sortWithOverride(a22);
StdOut.printf("%s (%.2f seconds)\n", "sortWithOverride [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a12);
assert isSorted(a22);
System.out.println();
stopwatch = new Stopwatch();
binaryInsertSort(a13);
StdOut.printf("%s (%.2f seconds)\n", "binaryInsertSort [random]:", stopwatch.elapsedTime());
binaryInsertSort(a23);
StdOut.printf("%s (%.2f seconds)\n", "binaryInsertSort [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a13);
assert isSorted(a23);
System.out.println();
stopwatch = new Stopwatch();
twoPathInsertSort(a14);
StdOut.printf("%s (%.2f seconds)\n", "twoPathInsertSort [random]:", stopwatch.elapsedTime());
twoPathInsertSort(a24);
StdOut.printf("%s (%.2f seconds)\n", "twoPathInsertSort [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a14);
assert isSorted(a24);
System.out.println();
stopwatch = new Stopwatch();
shellSort(a15);
StdOut.printf("%s (%.2f seconds)\n", "shellSort [random]:", stopwatch.elapsedTime());
shellSort(a25);
StdOut.printf("%s (%.2f seconds)\n", "shellSort [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a15);
assert isSorted(a25);
System.out.println();
}
}
结果如下:
对插入排序的各种方法进行性能测试
各种插入排序算法对十万个随机数组和随机重复数组排序
InsertionSortTest.java
package algorithm.sort;
import algorithm.util.iostream.StdOut;
import algorithm.util.random.RandomArrayUtil;
import algorithm.util.watch.Stopwatch;
import org.junit.Test;
import java.util.Arrays;
import static algorithm.sort.BaseSort.isSorted;
import static algorithm.sort.BaseSort.show;
import static algorithm.sort.InsertionSort.binaryInsertSort;
import static algorithm.sort.InsertionSort.shellSort;
import static algorithm.sort.InsertionSort.sort;
import static algorithm.sort.InsertionSort.sortWithOverride;
import static algorithm.sort.InsertionSort.twoPathInsertSort;
public class InsertionSortTest {
/**
* 对插入排序的各种方法进行性能测试
*
* 分别对十万个随机数组和随机重复数组排序, 结果如下:
*/
@Test
public void compareSort() {
// 正常随机数组
Integer[] a11 = RandomArrayUtil.getRandomBoxedIntArray(0, 1000000, 100000);
Integer[] a12 = Arrays.copyOf(a11, a11.length);
Integer[] a13 = Arrays.copyOf(a11, a11.length);
Integer[] a14 = Arrays.copyOf(a11, a11.length);
Integer[] a15 = Arrays.copyOf(a11, a11.length);
// 大量重复数组
Integer[] a21 = RandomArrayUtil.getRandomBoxedIntArray(0, 100, 100000);
Integer[] a22 = Arrays.copyOf(a21, a21.length);
Integer[] a23 = Arrays.copyOf(a21, a21.length);
Integer[] a24 = Arrays.copyOf(a21, a21.length);
Integer[] a25 = Arrays.copyOf(a21, a21.length);
System.out.println("Array created!");
Stopwatch stopwatch = new Stopwatch();
sort(a11);
StdOut.printf("%s (%.2f seconds)\n", "sort [random]:", stopwatch.elapsedTime());
sort(a21);
StdOut.printf("%s (%.2f seconds)\n", "sort [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a11);
assert isSorted(a21);
System.out.println();
stopwatch = new Stopwatch();
sortWithOverride(a12);
StdOut.printf("%s (%.2f seconds)\n", "sortWithOverride [random]:", stopwatch.elapsedTime());
sortWithOverride(a22);
StdOut.printf("%s (%.2f seconds)\n", "sortWithOverride [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a12);
assert isSorted(a22);
System.out.println();
stopwatch = new Stopwatch();
binaryInsertSort(a13);
StdOut.printf("%s (%.2f seconds)\n", "binaryInsertSort [random]:", stopwatch.elapsedTime());
binaryInsertSort(a23);
StdOut.printf("%s (%.2f seconds)\n", "binaryInsertSort [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a13);
assert isSorted(a23);
System.out.println();
stopwatch = new Stopwatch();
twoPathInsertSort(a14);
StdOut.printf("%s (%.2f seconds)\n", "twoPathInsertSort [random]:", stopwatch.elapsedTime());
twoPathInsertSort(a24);
StdOut.printf("%s (%.2f seconds)\n", "twoPathInsertSort [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a14);
assert isSorted(a24);
System.out.println();
stopwatch = new Stopwatch();
shellSort(a15);
StdOut.printf("%s (%.2f seconds)\n", "shellSort [random]:", stopwatch.elapsedTime());
shellSort(a25);
StdOut.printf("%s (%.2f seconds)\n", "shellSort [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a15);
assert isSorted(a25);
System.out.println();
}
}
结果如下:
sort [random]: (20.17 seconds)
sort [random + duplicate]: (32.51 seconds)
sortWithOverride [random]: (13.37 seconds)
sortWithOverride [random + duplicate]: (20.18 seconds)
binaryInsertSort [random]: (10.65 seconds)
binaryInsertSort [random + duplicate]: (16.19 seconds)
twoPathInsertSort [random]: (17.17 seconds)
twoPathInsertSort [random + duplicate]: (33.55 seconds)
Array length: 100000, Shell sort max step: 88573
shellSort [random]: (0.05 seconds)
Array length: 100000, Shell sort max step: 88573
shellSort [random + duplicate]: (0.06 seconds)
从结果可知, 对于选择了合适的递增序列的希尔排序, 和普通的插入排序的差别提升了N个数量级!
插入排序冠军: shellSort(使用了3为系数的递增序列: 1, 4, 13, 40, 121, 364, 1093, ...)
<br/>
希尔排序与插入排序的不同之处在于，它会优先比较距离较远的元素
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
ShellSort.java
package algorithm.sort;
/**
* 希尔排序法又叫“缩小增量排序法”, 是对直接插入排序法的优化:
*
* 通过设置一个增量，对原始序列进行分组，对每组用直接插入排序法排序再整合，再缩小增量，周而复始直至增量为1，完成排序
*
* 其实到希尔算法进行到最后，n的值变为1（即增量或者称跳跃数变为1）的时候，它就是直接插入排序
*
* 只不过这时候，整个序列基本上是有序的，需要交换的数据已经非常少了，提高效率
*
* @author zk
*/
public class ShellSort extends BaseSort {
/**
* 构建希尔排序递增序列的步长系数
*/
public static int step = 3;
public static <K extends Comparable<K>> void sort(K[] a) {
int h = 1, len = a.length;
// 构建插排的步长h
// 1, 4, 13, 40, 121, 364, 1093, ...
while (h < len / step) h = step * h + 1;
System.out.println(String.format("Array length: %s, Shell sort max step: %s", len, h));
while (h >= 1) {
// 根据h序列自: ... -> 121 -> 40 -> 13 -> 4 -> 1 进行插排
for (int i = h; i < len; ++i) {
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
exch(a, j, j - h);
}
}
h /= step;
}
}
}
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列
动态定义间隔序列的算法是《算法(第4版)》的合著者Robert Sedgewick提出的
选择合适的递增序列, 但是这种优化没有定性的理论基础
将不同step值的希尔排序进行比较, 并与插入排序进行比较
选取的step有: 3, 7, 19, 97, 10000000
分别对十万个随机数组和随机重复数组进行排序
ShellSortTest.java
package algorithm.sort;
import algorithm.util.iostream.StdOut;
import algorithm.util.random.RandomArrayUtil;
import algorithm.util.watch.Stopwatch;
import org.junit.Test;
import java.util.Arrays;
import static algorithm.sort.BaseSort.isSorted;
import static algorithm.sort.ShellSort.sort;
public class ShellSortTest {
/**
* 将不同step值的希尔排序进行比较, 并与插入排序进行比较
*/
@Test
public void compareStep() {
// 正常随机数组
Integer[] a11 = RandomArrayUtil.getRandomBoxedIntArray(0, 1000000, 100000);
Integer[] a12 = Arrays.copyOf(a11, a11.length);
Integer[] a13 = Arrays.copyOf(a11, a11.length);
Integer[] a14 = Arrays.copyOf(a11, a11.length);
Integer[] a15 = Arrays.copyOf(a11, a11.length);
Integer[] a16 = Arrays.copyOf(a11, a11.length);
// 大量重复数组
Integer[] a21 = RandomArrayUtil.getRandomBoxedIntArray(0, 100, 100000);
Integer[] a22 = Arrays.copyOf(a21, a21.length);
Integer[] a23 = Arrays.copyOf(a21, a21.length);
Integer[] a24 = Arrays.copyOf(a21, a21.length);
Integer[] a25 = Arrays.copyOf(a21, a21.length);
Integer[] a26 = Arrays.copyOf(a21, a21.length);
System.out.println("Array created!");
ShellSort.step = 3;
System.out.println("Step: " + ShellSort.step);
Stopwatch stopwatch = new Stopwatch();
sort(a11);
StdOut.printf("%s (%.2f seconds)\n", "[random]:", stopwatch.elapsedTime());
sort(a21);
StdOut.printf("%s (%.2f seconds)\n", "[random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a11);
assert isSorted(a21);
System.out.println();
ShellSort.step = 7;
System.out.println("Step: " + ShellSort.step);
stopwatch = new Stopwatch();
sort(a12);
StdOut.printf("%s (%.2f seconds)\n", "[random]:", stopwatch.elapsedTime());
sort(a22);
StdOut.printf("%s (%.2f seconds)\n", "[random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a12);
assert isSorted(a22);
System.out.println();
ShellSort.step = 19;
System.out.println("Step: " + ShellSort.step);
stopwatch = new Stopwatch();
sort(a13);
StdOut.printf("%s (%.2f seconds)\n", "[random]:", stopwatch.elapsedTime());
sort(a23);
StdOut.printf("%s (%.2f seconds)\n", "[random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a13);
assert isSorted(a23);
System.out.println();
ShellSort.step = 97;
System.out.println("Step: " + ShellSort.step);
stopwatch = new Stopwatch();
sort(a14);
StdOut.printf("%s (%.2f seconds)\n", "[random]:", stopwatch.elapsedTime());
sort(a24);
StdOut.printf("%s (%.2f seconds)\n", "[random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a14);
assert isSorted(a24);
System.out.println();
ShellSort.step = 10000000;
System.out.println("Step: " + ShellSort.step);
stopwatch = new Stopwatch();
sort(a15);
StdOut.printf("%s (%.2f seconds)\n", "[random]:", stopwatch.elapsedTime());
sort(a25);
StdOut.printf("%s (%.2f seconds)\n", "[random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a15);
assert isSorted(a25);
System.out.println();
System.out.println("Insertion Sort:");
stopwatch = new Stopwatch();
InsertionSort.sort(a16);
StdOut.printf("%s (%.2f seconds)\n", "[random]:", stopwatch.elapsedTime());
InsertionSort.sort(a26);
StdOut.printf("%s (%.2f seconds)\n", "[random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a16);
assert isSorted(a26);
}
}
结果如下:
Step: 3
Array length: 100000, Shell sort max step: 88573
[random]: (0.06 seconds)
Array length: 100000, Shell sort max step: 88573
[random + duplicate]: (0.07 seconds)
Step: 7
Array length: 100000, Shell sort max step: 19608
[random]: (0.04 seconds)
Array length: 100000, Shell sort max step: 19608
[random + duplicate]: (0.07 seconds)
Step: 19
Array length: 100000, Shell sort max step: 7240
[random]: (0.08 seconds)
Array length: 100000, Shell sort max step: 7240
[random + duplicate]: (0.13 seconds)
Step: 97
Array length: 100000, Shell sort max step: 9507
[random]: (0.31 seconds)
Array length: 100000, Shell sort max step: 9507
[random + duplicate]: (0.60 seconds)
Step: 10000000
Array length: 100000, Shell sort max step: 1
[random]: (16.98 seconds)
Array length: 100000, Shell sort max step: 1
[random + duplicate]: (28.00 seconds)
Insertion Sort:
[random]: (22.34 seconds)
[random + duplicate]: (33.75 seconds)
实验证明, 对于递增系数巨大的希尔排序, 性能会恶化到与插入排序性能相似!
所以对于希尔排序优化的关键就是选择合适的递增序列!
<br/>
下篇见: 几种常见排序方法的优化(下)
<br/>
文中部分说明内容转自: 十大经典排序算法（动图演示）
源代码:
如果觉得文章写的不错, 可以关注微信公众号: Coder张小凯
内容和博客同步更新~
<br/>