menu
Jasonkay
文章506
标签266
分类65
本站总访问量次
本站访客数人次
本站已运行0天0小时0分0秒 ❤
© 2024 Jasonkay Powered by Hexo & Nexmoe

几种常见排序方法的优化(上)

2020年02月24日 8k 字 阅读量 大概 39 分钟 算法 排序 算法

最近花了几天重温了一下《算法(第四版)》, 重新把书中的算法实现了一下, 并且思索了一下, 把常见的比较排序算法都给优化了一下, 然后进行了性能测试. 也算是复习了一下排序算法吧.

阅读本篇之前最好有常见几种基于的比较排序算法的基础

本文内容包括:

  • 排序算法的一些通用方法抽象类(父类BaseSort)
  • 冒泡排序优化及性能测试
  • 选择排序优化及性能测试
  • 插入排序优化及性能测试
  • 希尔排序以及不同递增序列的性能测试

源代码:

如果觉得文章写的不错, 可以关注微信公众号: Coder张小凯

内容和博客同步更新~


零.排序通用方法的抽象

对于一般的排序方法, 都会包括大量的数组访问操作、比较操作(less)以及交换操作(exch)

此外还需要一些用来检验是否已经有序的方法, 如:

  • isSorted: 遍历数组, 判断数组是否已经有序
  • show: 将结果展示
  • ……

为了实现代码的复用性, 本文创建了一个基本的排序抽象类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;
    }

}

说明:

为了更好的复用排序算法, 本文尽量使用实现了Comparable接口的泛型来实现算法, 并通过less代替比较运算符进行比较


一.冒泡排序优化及性能测试

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端

1.算法描述

  • 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  • 针对所有的元素重复以上的步骤，除了最后一个；
  • 重复步骤1~3，直到排序完成

2.动图演示

BubbleSort.gif

3.代码实现

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);
                }
            }
        }
    }

}

4.优化方法

① 增加排序结束标记

在交换的地方加一个标记，如果那一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去


注: 这里用到了冒泡每次都要交换的特点, 而选择排序仅仅交换一次!

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;
    }
}

5.性能测试


性能测试代码说明:

性能测试每次会创建两组数组, 分别为含有大量离散元素的随机数组和大量重复元素的随机数组, 分别排序

① 随机数数组

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)

6.性能测试总结

从结果可见, 通过将最简单的冒泡排序进行逐步优化, 排序性能有了部分提高

冒泡排序性能冠军: sortBilaterally

性能提高原因: 因为使用了双向排序, 一次遍历排序出两个元素


二.选择排序优化及性能测试

选择排序(Selection-sort)的工作原理:

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾

以此类推，直到所有元素均排序完毕

1.算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

  • 初始状态：无序区为R[1..n]，有序区为空；
  • 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
  • n-1趟结束，数组有序化了

2.动图演示

SelectionSort.gif

3.代码实现

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);
        }
    }
}

4.优化方法

双边排序

每次排序可以选择两个: 最大和最小分别和左右位置进行交换

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--;
    }
}

5.性能测试

针对选择排序中各种优化方法的优化效果, 通过下面的代码进行性能测试

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)

6.性能测试总结

从结果可见, 选择排序经过了优化, 性能略微提高

选择排序性能冠军: sortBilaterally

性能提高原因: 因为使用了双向排序, 一次遍历排序出两个元素


三.插入排序优化及性能测试

它的工作原理是:

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入(类似于排序手中的扑克牌)

1.算法描述

一般来说，插入排序都采用原地(in-place)在数组上实现

具体算法描述如下：

  • 从第一个元素开始，该元素可以认为已经被排序；
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  • 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  • 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  • 将新元素插入到该位置后；
  • 重复步骤2~5

2.动图演示

InsertionSort.gif

3.代码实现

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)且对于基本有序的序列可以很快完成排序, 因此适用于小数组、已经近似有序的数组或者链表排序

此外, 在堆排序, 快排, 桶排序等算法的优化中也经常使用插入排序

4.优化方法

① 交换变为覆盖

由于最基本的插入排序中, 只要存在逆序就要交换, 所以可以将交换变为覆盖:

把当前待插入的元素取出，让当前元素与之前的所有元素进行一一比较

前一个元素大于当前元素直接覆盖，而到了最后当找到当前元素的合适位置时只需要一次交换即可

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路插入)

具体操作思路：

  1. 将原数组第一个元素赋值给b[0],作为标志元素
  2. 按顺序依次插入剩下的原数组的元素
    • 将带插入元素与第一个进行比较，偌大于b[0],则插入b[0]前面的有序序列，否则插入后面的有序序列
    • 对前面的有序序列或后面的有序序列进行折半查找
    • 查找到插入位置后进行记录的移动，分别往head方向前移和往tail方向移动
    • 插入记录
  3. 将排序好的b数组的数据从head到tail，按次序赋值回原数组
@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];
    }
}

④ 希尔排序法

见下希尔排序

5.性能测试

对插入排序的各种方法进行性能测试

各种插入排序算法对十万个随机数组和随机重复数组排序

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)

6.性能测试总结

从结果可知, 对于选择了合适的递增序列的希尔排序, 和普通的插入排序的差别提升了N个数量级!

插入排序冠军: shellSort(使用了3为系数的递增序列: 1, 4, 13, 40, 121, 364, 1093, …)


四.希尔排序以及不同递增序列的性能测试

希尔排序与插入排序的不同之处在于，它会优先比较距离较远的元素

1.算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  • 按增量序列个数k，对序列进行k趟排序；
  • 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

2.动图演示

ShellSort.gif

3.代码实现

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提出的

4.优化方法

选择合适的递增序列, 但是这种优化没有定性的理论基础

5.性能测试

将不同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)

6.性能测试总结

实验证明, 对于递增系数巨大的希尔排序, 性能会恶化到与插入排序性能相似!

所以对于希尔排序优化的关键就是选择合适的递增序列!


附录

下篇见: 几种常见排序方法的优化(下)


文中部分说明内容转自: 十大经典排序算法（动图演示）

源代码:

如果觉得文章写的不错, 可以关注微信公众号: Coder张小凯

内容和博客同步更新~



本文作者：Jasonkay
本文链接：https://jasonkayzk.github.io/2020/02/24/几种常见排序方法的优化(上)/
版权声明：本文采用 CC BY-NC-SA 3.0 CN 协议进行许可