《算法》笔记 3 - 选择排序、插入排序、希尔排序

• 排序通用代码
• 选择排序
• 插入排序
• 希尔排序

排序通用代码

通用代码支持任意实现了Comparable接口的数据类型的排序，不同的排序算法的差异体现在sort方法的实现上。

public class Selection {
    public static void sort(Comparable[] a) {
        //待实现
    }

    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i - 1])) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] input = StdIn.readAllInts();
        Integer[] a1 = new Integer[input.length];
        for (int i = 0; i < input.length; i++) {
            a1[i] = input[i];
        }
        sort(a1);
        assert isSorted(a1);
    }
}

选择排序

选择排序的过程是：找到数组中最小的那个元素，然后将它和数组中的第一个元素交换位置，如果第一个元素就是最小的元素，就和它自己交换。接着在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置，如此反复，直到处理完数组的所有元素。

public static void sort(Comparable[] a) {
    int minIndex = 0;
    for (int i = 0; i < a.length; i++) {
        // min = a[i];
        minIndex = i;
        for (int j = i + 1; j < a.length; j++) {
            if (less(a[j], a[minIndex])) {
                // min = a[j];
                minIndex = j;
            }
        }
        exch(a, i, minIndex);
    }
}

算法特点

排序算法的开销主要包括数组元素的交换和比较两方面。
选择排序的交换次数为N，等于数组的规模。
选择排序的比较次数可以从算法的执行过程得知，外层循环N次，每次排好一个元素，下一次的内层循环的起始索引加1，则比较次数减1，所以一共比较(N-1)+(N-2)+...+(1)=(N-1)*(N-2)/2次，~N^2/2

选择排序算法的增长数量级是平方级别的，此外这种算法还有如下特点：

• 运行时间与输入无关
  为了找出最小的元素而扫描一遍数组并不能为下一次扫描提供什么信息，所以排序随机元素组成的数组和排序元素已经有序的数组或元素值全部相同的数组所用的时间是一样的。
• 数据移动次数是所有排序算法中最少的
  选择排序交换次数和数组的大小是线性关系，随后学习的其它排序算法都不具备这个特性，大部分的增长数量级是线性对数或者平方级别的。

插入排序

将纸牌排序时，一般采用的方法是一张一张来，把当前的这张牌插入到已经排好序的牌中的合适位置。插入排序的原理与这个类似。唯一的区别是：将一个元素插入数组中的某个位置时，这个位置之后的所有元素都需要向后移动一位。

public static void sort(Comparable[] a) {
    for (int i = 1; i < a.length; i++) {
        for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
            exch(a, j, j - 1);
        }
    }
}

算法特点

插入排序所需的时间则是与输入数组的特点有很大关系的，最快的时候可以在线性时间内完成，最慢的时候却达到平方级别。
最好情况既输入本身已经是有序的，那么外层循环会执行N-1次，每次循环都会执行less(a[j], a[j - 1])，所以需要比较N-1次，但进入内层循环的条件都不会满足，则交换0次。
最坏的情况则是输入是倒序的，那么从索引=1开始，每个元素都会被移动，且每次比较都会对应一次移动，比较与移动的次数相等。第二个元素比较1次，第三个较2次，第4个3次，...第N个N-1此，一共约_{N^2/2次比较，}N^2/2次移动；
那么在输入元素随机的情况下，可以认为平均每个元素都可能移动半个数组的距离，所需的比较、移动次数为最坏情况的一般，约_{N^2/4次比较，}N^2/4次移动。
插入排序的特点，决定了它非常适用于实际应用中常见的部分有序的数组的排序。

希尔排序

希尔排序是对插入排序的改进。插入排序对于随机输入的增长数量级在平方级别，对于规模较大的问题其运行时间会比较慢。因为插入排序只会交换相邻的元素，元素只能一点一点地从当前位置移动到其应该呆的位置。
希尔排序针对这一的进行了改进，增加了元素移动的跨度。希尔排序的思想是使数组中任意间隔为h的元素都是有序的，这样的数组被称为h有序数组。一个h有序数组就是h个互相独立的有序数组编织在一起组成的数组。如下所示，h为2时，数组可以分为2个独立的子数组，将这两个子数组排序后，再进行一次排序，整个数组就是有序的了。

L   E   E   A   M   H   L   E  
L-------E-------M-------L      
    E-------A-------H-------E      

如果h很大，则可以把移动到很远的地方。希尔排序在运行时，先使用较大的h进行粗排，然后按照一定的规律逐步减小h，当h减小到1时，即完成了数组的最终排序。这样做有什么效果呢，多轮排序会不会反而速度更慢呢？实际上希尔排序的比插入排序快得多。这是因为希尔排序权衡了子数组的规模和有序性，排序之处，各个子数组都很短，排序后期子数组又都是部分有序的，插入排序在这两种情况下都特别适合。
如下为希尔排序的实现，h序列选择了最常用的3*h+1序列，即1,4,13,40,121,364,1093...

public static void sort(Comparable[] a) {
    int N = a.length;
    int h = 1;
    while (h <= N / 3) {
        h = 3 * h + 1;
    }

    while (h >= 1) {
        for (int i = h; i < N; i++) {
            for (int j = i; j > h && less(a[j], a[j - h]); j -= h) {
                exch(a, j, j - h);
            }
        }
        h /= 3;
    }
}

算法特点

h序列的选择对希尔排序的性能影响很大，但透彻理解希尔排序的性能至今仍然是一项挑战，有很多论文研究了各种不同的地址序列，但都无法证明某个序列是“最好的”。
可以通过比较三种算法的时间来直观地感受不同算法的差异，下面是处理10万条int数组时的时间对比：

Selection, 37.595 s
Insertion, 76.14 s
Shell, 0.136 s

由此可见，希尔排序相比选择排序和插入排序要高效得多。对于中等大小规模的数组，希尔排序的运行时间是可接受的，其它一些更高级的算法可能只会比希尔排序快2倍，但这些算法的代码却更复杂。在没有可用的系统排序算法可用，或者为嵌入式系统编写代码时，可以考虑使用希尔排序。