数据结构与算法--排序之冒泡、选择、插入、希尔

我们关注的主要对象是重新排列数组元素的算法，每个元素都有一个主键，排序算法的目的是将所有元素按照某种方式排列，排列后索引大的元素的主键大于等于索引小的元素的主键。元素和主键在不同的应用中可能各不相同，在Java中元素通常都是对象，而且一般都是可相互比较的对象——即实现了Comparale接口。

1、Comparable和compareTo方法

实现了Comparable接口，因此必须实现compareTo，一般来说，习惯于当v < w、v = w和v > w时，v.compareTo(v)分别返回-1、0、1。如果v和w两者之一是null或者两者无法比较将会抛出异常。而且需要满足下面几个条件。

• 自反性。对于所有的v，有v = v；
• 反对称性。对于所有的v > w都有w < v，且当v = w时有w = v；
• 传递性。对于所有的v、w、x，如果v <= w且w <= x，则v <= x.

2、排序的稳定性

如果待排序的序列中存在多个元素相同，在排序前后它们的相对位置没有发生改变，就称该排序算法是稳定的。举个例子，比如待排序序列如下

[3, 5, 4, 2, (5), 6]

最后一个元素5和第二个元素5是相同的，特别用括号标明它。此时5在(5)的前面。如果排序后的序列是

[2, 3, 4, (5), 5, 6]

此时5在 (5)的后面了，它们的相对位置发生了改变，所以该排序算法是不稳定的。

如果排序后变成下面的样子，它们的相对位置和排序前一样，则该排序算法是稳定的。

[2, 3, 4, 5, (5), 6]

现在来看几个简单的排序算法。

最容易想到的排序法

有种排序是最容易想到的，当然性能肯定不咋滴。数组中第一个位置的元素和它后面的每个元素相比，如果后面的更小，两个元素交换，于是更小的元素被换到了数组第一个位置，接着用这第一个位置的元素和后续元素比较，直到和数组中每个元素都比较过一次，期间可能发生了多次交换，最后数组第一个位置肯定是最小元素了；第一个位置确定了，接下来同样的办法确定第二个位置....直到最后一个位置确定，排序完成。根据描述，写出如下代码。

package Chap9;

public class SimpleSort {
    public static void sort(Comparable[] a) {
        // 倒数第二个元素确定了，那最后一个元素自然而然就确定了，其实i < a.length - 1就好
        // 但是i < length也是可以的，进入第二层循环后j = a.length直接跳出循环
        for (int i = 0; i < a.length; i++) {
            for (int j = i +1; j < a.length; j++) {
                // 如果后面的比当前元素小，就交换
                if (less(a[j], a[i])) {
                    swap(a, i, j);
                }
            }
        }
    }

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

    private static void swap(Comparable[] a, int p, int q) {
        Comparable temp = a[p];
        a[p] = a[q];
        a[q] = temp;
    }


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

    public static String toString(Comparable[] a) {
        if (a.length == 0) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < a.length; i++) {
            sb.append(a[i]);
            if (i == a.length - 1) {
                return sb.append("]").toString();
            } else {
                sb.append(", ");
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Integer[] a = {9, 1, 5, 8, 3, 7, 4, 6, 2};
        SimpleSort.sort(a);
        System.out.println(SimpleSort.toString(a));
        System.out.println(isSorted(a)); // true
    }

}

算法的轨迹如下，9和1比较，1被换到了数组第一个位置。之后1再和后续元素相比，都没有1小，因此不交换；然后第二个位置，5比9小所以交换，5和3比又交换，3和2比又交换，最后2最小确定在数组第二个位置......剩下的元素就不一一叙述了。

可以发现在确定第二小元素的时候，进行了三次交换。可真正有用的交换是最后把2换过来的那一次，前面的若干次交换都是多余的，其实直接将最小元素交换过来就可以了。基于此对上面的算法的改进就是简单选择排序了。

这种算法有缺陷，不仅无效的交换操作很多，而且还会把本来较小的元素交换到后面去，比如，上例中3本来在数组中间，经过两轮循环的排序后，它竟然到了数组的末端。

简单选择排序

具体来说：选择数组中最小的元素，将它与数组中第一个元素交换，如果第一个元素就是最小值，那就和自己交换或者不交换；在剩下的元素中找到最小元素，和数组中第二个元素进行交换....

交换发生在每次循环中选择出最小元素之后，而不是盲目地看见一个比当前元素小的就马上交换，因此简单选择排序比起上面的排序算法，元素交换的操作大大减少，性能得到一定提升。

public class SelectSort {
    public static void sort(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            // min保存目前最小元素的下标，刚开始假设位置i的元素最小，然后和之后每个元素比较，
            int minIndex = i;
            // 只要后面更小就更新min，因此一轮循环下来min肯定是最小元素下标
            for (int j = i + 1; j < a.length; j++) {
                if (less(a[j], a[minIndex])) {
                    minIndex = j;
                }
            }
            // 如果第一个元素就是最小值，无需交换
            if (i != minIndex) {
            // 最小元素换到位置i
                swap(a,i, minIndex);
            }
        }
    }
}

实现中用一个minIndex的int型值记录在每轮循环中数组最小元素的下标。一开始假设数组中第一个元素是最小的，然后和后面所有元素比较，如果后面的元素更小，就更新minIndex为后面元素的下标（第一种算法直接交换，看出用下标记录最小值的好处了吧），当和所有元素比较后，minIndex自然是数组中最小元素的下标，因此将minIndex处的元素和数组第一个位置的元素交换（如果第一个元素的下标就是minIndex，无需交换）；接着假设数组第二个位置的元素是最小的，按照相同的方法选择出剩下元素中的最小者，其下标是minIndex，因此将数组第二个位置的元素和minIndex处的元素交换，这样就确定了第一二个位置...后面都不会再访问到这些已经有序的元素，之后的元素也是同样的操作，直到数组最后一个位置的元素也确定了，排序也就完成了。

下图是某字符数组的选择排序轨迹，红色圆圈内的是每轮循环中的最小元素。第一轮选出最小元素A和数组第一个位置S交换；第二轮选出最小元素E和数组第二个元素O交换....

简单选择排序有如下两个特点：

• 运行时间和输入状态无关，已经有序的数组或者主键全部一样的数组以及随机排列的数组所用的排序时间是一样的！都需要比较N * (N - 1) / 2次
• 数据交换的次数很少，最好情况下交换0次，最坏情况下交换N - 1次。

简单选择排序是不稳定的排序算法，举个例子[5, 4, 5, 3, 2]，第一轮会将最下的2与数组第一个位置的5交换，两个等值的5相对位置发生了改变。

冒泡排序

冒泡排序的思路：相邻元素之间两两比较，不断将较大的元素往后推（或者不断将较小元素往前推）。以后者为例，从后往前遍历数组，数组中最后一位和倒数第二位元素比较，较小者被交换到前面；然后用较小者和左边相邻的元素比较，继续将较小者换到前面，最后最小元素就在数组的第一个位置确定下来。第二轮同样的操作，将剩下元素中的最小元素在数组的第二个位置确定下来...如此反复。

public class BubbleSort {
    public static void sort(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            // 从最后一个元素开始，不断将较小的往前推，被推到数组左端就是最小元素
            for (int j = a.length - 1; j > i; j--) {
                // 后面的比前面的小就交换
                if (less(a[j], a[j - 1])) {
                    swap(a, j - 1, j);
                }
            }
        }
    }
}

下面的图演示了前两个最小元素是怎么被“冒泡”到数组的前端的。

冒泡算法的优化

试想一种比较特殊的情况，如果待排序的序列基本有序如[2, 1, 3, 4, 5, 6, 7 ,8, 9]，只要在第一轮冒泡中将2和1交换后，其实整个序列就已经有序了，但是算法依然在进行比较，因此这些比较都是无意义的，直接跳出循环就好。

所以设置一个标志位isSorted，如果在某轮循环中没有发生元素交换，说明序列已经有序，直接break跳出循环，结束没有必要的比较。

public static void sort2(Comparable[] a) {
    boolean isSorted;
    for (int i = 0; i < a.length; i++) {
        // 每轮循环都先假设已经有序，若之后有元素交换了说明可能还没有达到有序，变成false。
        isSorted = true;
        // 从最后一个元素开始，不断将较小的往前推，被推到到数组左端就是最小元素
        for (int j = a.length - 1; j > i; j--) {
        // 后面的比前面的小就交换
            if (less(a[j], a[j - 1])) {
                swap(a, j - 1, j);
                isSorted = false;
            }
        }
        // 如某轮循环没有发生交换，说明已经有序了，直接跳出循环
        if (isSorted) {
            break;
        }
    }
}

冒泡排序的比较和元素交换都发生在两个相邻元素之间，相邻的等值元素不会进行交换，就算等值元素不相邻，在交换后也会相邻，依然不会交换它们的位置，因此冒泡排序是稳定排序算法。

插入排序

想象生活中打扑克，从牌堆摸起一张牌，将它插到其他已经有序的牌中的合适位置。在数组中对应着插入操作，为了给插入的元素腾出空间，需要将其他比它大的元素都向右移动一位。和选择排序、冒泡排序一样，当前索引之前的元素已经有序，但有区别。对于冒泡、选择排序，当前索引之前的元素不仅有序而且最终位置也确定了，在之后的循环中不会被访问到；而对于选择排序，当前索引之前的元素虽然是有序的，但是最终位置还不确定，后来的元素如果更小将插入其中，每次插入后都使得当前数组是有序的，所以当最后一个元素插入到数组中合适的位置时，整个数组排序就完成了。

插入排序所需的时间取决于待排序数组的初始顺序，对一个接近有序的数组进行排序比随机顺序的数组要快得多。

public class InsertSort {

    public static void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            // 当前索引如果比它前一个元素要大，不用插入，否则需要插入
            if (less(a[i], a[i-1])) {
                // 待插入的元素先保存
                Comparable temp = a[i];
                // 元素右移
                int j;
                for (j = i; j > 0 && less(temp, a[j-1]); j--) {
                    a[j] = a[j -1];
                }
                // 插入
                a[j] = temp;
            }
        }
    }
}

因为用到了数组下标i - 1，所以最外层循环从1开始。当前索引i之前的元素已经有序，所以如果当前索引的元素比它前面一个元素大（自然就比前面的所有元素都大），则无需进行插入操作；否则需要插入，插入之前先将要插入的元素用temp保存下来，然后内层for循环就是右移元素，直到某个j-1处的元素是小于temp为止，然后temp插入到位置j处。

下图反映了插入排序的轨迹，被红色圆圈包住的元素就是被插入到合适位置的元素了，灰色的元素都没有移动，其余黑色的元素都往右移动了一格。

从代码可以推测插入排序通常比选择排序比较次数更少，特别是对于接近有序的数组。下图可以反映这一趋势。

用条形图的高矮表示元素的大小，那些黑色条形图参与了比较，可以看出插入排序的比较次数比选择排序的要少。

插入排序对于部分有序的数组更有优势，以下是几种典型的部分有序数组：

• 数组中的每个元素离它们的最终位置都不远；
• 一个有序的大数组接一个小数组；
• 数组中只有几个元素的位置不正确

对于上述几种类型的数组，插入排序通常比其他算法要快些。

插入排序的元素移动是依据插入元素与前面元素的大小来决定的，当插入元素遇到和它等值的元素时就停止移动了，因此很好的保持了它们原来的相对位置，因此插入排序是稳定的排序算法。

希尔排序

希尔排序基于插入排序。对于大规模乱序数组插入排序很慢（因此更适合于小规模的部分有序数组），元素移动只是每次移动一格，因此如果最小元素在数组的末端，要将它插入到合适的位置需要N - 1次移动。希尔排序正是基于这一点，使得元素可以一次移动多格。

具体来说，希尔排序按照增量h将原数组分成了h个子数组（插入排序可以看做是增量为1），然后分别对这h个子数组进行插入排序；之后按照一定的关系减小增量h，再对h个子数组插入排序，每次排序后的数组越来越接近部分有序，最后保证增量h会减小到1，对这个数组最后进行一次插入排序，整个数组排序完成。

增量h和子数组的关系如下图所示

增量为4，因此下标为0、4、8、12的组成一个子数组，1、5、9、13也组成一个子数组。总共4个，可以看到一个h有序数组就是由h个有序子数组组成的。

在代码中只需要将插入排序中的增量1换成h即可。另外为了使得最后的增量能减小到1，使用了一个1 / 2(3^k - 1)序列，满足递推关系为h = 3h + 1，这是基于数学分析上的考虑，在大量实验中证明该序列可以保证较好的性能。

public class ShellSort {

    public static void sort(Comparable[] a) {
        int h = 1;
        while (h < a.length / 3) {
            h = 3 * h + 1; // 1, 4, 13...
        }
        // 上面的代码是将初始增量设置为 小于N/3且满足序列3h + 1的最大值

        // 最后一次增量h = 1，之后h = 0退出while
        while (h >= 1) {
            // 和插入排序比将i = 1换成了i = h；i还是自增1，表示处理下一个子数组（交替处理各个子数组）
            for (int i = h; i < a.length; i++) {
                // a[i - 1]换成了a[i - h]
                if (less(a[i], a[i - h])) {
                    // 待插入的元素先保存
                    Comparable temp = a[i];
                    // 元素右移
                    int j;
                    // j > 0（即j >= 1）换成了j >= h;less(temp, a[j - 1])中1换成了h；j--换成了j = j - h
                    for (j = i; j >= h && less(temp, a[j - h]); j = j - h) {
                        // a[j - 1]换成了a[j - h]
                        a[j] = a[j - h];
                    }
                    // 插入
                    a[j] = temp;
                }
            }
            // 缩小增量h，最终肯定能缩小到1
            h = h / 3; // ...13, 4, 1
        }
    }
}

注释中加入了和插入排序的对比，的确是将增量1改成了增量h就可以了！第一个while循环是设置初始增量，基于数学上的分析，一个较优值是取增量h为小于数组长度N / 3且满足序列1 / 2(3^k - 1)的最大值。在对所有子数组都进行过插入排序后，缩小增量h。由于缩小的方法和增长的方法一致，所以最后h一定能被缩小到1，从而保证了最后一次是增量为1的插入排序**。之后h = 1 / 3 = 0会退出while循环（注意，这个除法当然是Java中的除法操作）。

我们看上面的实现是怎么对每个子数组进插入排序的，你可能觉得它是在完成一个子数组的排序后再对下一个子数组的进行插入排序的，按上面h = 4的图来说就是，先对下标0、4、8、12的子数组完成排序后，再进行下标1、5、9、13的子数组排序，但以这样的顺序处理各个子数组，代码应该会更复杂。实际上我们采用了更简单的方法，如下

for (int i = h; i < a.length; i++)

结合上图，i++表明我们是交替对每个子数组进行插入排序的，比如开始i = h = 4，表示对下标0、4、8、12的子数组LMPT进行插入排序，然后i自增后等于5，转而对下标1、5、9、13的子数组EHSS进行插入排序...当i自增到8时，又回来对下标0、4、8、12的子数组LMPT排序，这样最后也达到了对每个子数组进行插入排序的目的。硬要打个比方的话，h个子数组可以看成h个线程，单核处理器并发处理这h个任务，即在这h个线程中切换（因此会中断当前线程去处理其他线程），交替执行h个线程。

看希尔排序的轨迹图，被红色圆圈包住的元素是当前索引元素，它要么原地不动要么被插入到合适的位置。黑色元素是移动过的，灰色元素则没有移动。

通常，希尔排序比选择排序和插入排序都要快，并且数组规模越大，优势体现得越明显。另外，增量h的序列如何选择才能达到最好的性能，到现在依然是个数学难题。因此无需纠结为什么非得取1/2 (3^k - 1)这样的序列，只要记住采用这个序列可以取得不错的性能就好了。

希尔排序由于增量一般较大，元素的移动跨度很大，是跳跃性的，而且各个子数组的元素移动交替进行，因此很有可能就不能保证等值元素的相对位置。因此希尔排序不是稳定排序算法。

by @sunhaiyu

2017.10.27