初级排序算法

发表于 更新于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 6 分钟

作为对排序算法领域的第一次探索，我们将学习两种初级的排序算法以及其中一种的一个变体。深人学习这些相对简单的算法的原因在于:第一，我们将通过它们熟悉一些术语和简单的技巧；第二，这些简单的算法在某些情况下比我们之后将会讨论的复杂算法更有效；第三，以后你会发现，它们有助于我们改进复杂算法的效率。那么开始吧！

目录

排序算法类的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Example {
    //将a[]按升序排列
    public static void sort(Comparable[] a) {
        /*请见本文算法2.1、算法2.2、算法2.3*/
    }

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

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

    // 在单行打印数组
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++)
            print(a[i] + " ");
        println();
    }

    //测试数组元素是否有序
    public static boolean isSort(Comparable[] a) {
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1]))
                return false;
        return true;
    }
}

上面的print()、println()为自定义的静态方法，不再详细说明。

选择排序

一种最简单的排序算法是这样的: 首先，找到数组中最小的那个元素，其次，将它和数组的第个元素交换位置 (如果第一个元素就是最小元素那么它就和自己交换)。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Selection {
    //将a[]按升序排列
    public static void sort(Comparable[] a) {
        int n=a.length; //数组长度
        for(int i=0;i<n;i++){   //将a[i]和a[i+1..n]中最小的元素交换
            int min=i;          //最小元素的索引
            for(int j=i+1;j<n;j++)
                if(less(a[j],a[min]))
                    min=j;
                exch(a,i,min);
        }
    }
    // less()、exch()、isSorted()方法见“排序算法类的模板”
}
选择排序的轨迹（每次交换后的数组内容）

插入排序

与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。和选择排序不同的是，插人排序所需的时间取决于输人中元素的初始顺序。例如，对一个很大且其中的元素已经有序(或接近有序)的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。

1
2
3
4
5
6
7
8
9
10
11
public class Insertion {
    //将a[]按升序排列
    public static void sort(Comparable[] a) {
        int n = a.length;
        for (int i = 1; i < n; i++) {   //将a[i]插入到a[i-1]、a[i-2]、a[i-3]...之中
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--)
                exch(a, j, j - 1);
        }
    }
    // less()、exch()、isSorted()方法见“排序算法类的模板”
}
插入排序的轨迹（每次插入后的数组内容）

比较两种排序算法

说实话这部分我还说不清楚，感兴趣的可以看原著。

初级排序算法的可视轨迹图

希尔排序

为了展示初级排序算法性质的价值，接下来我们将学习一种基于插人排序的快速的排序算法。对于大规模乱序数组插人排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另-端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1次移动。希尔排序为了加快速度简单地改进了插人排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起组成的一一个数组(见图2.1.2)。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的h序列，我们都能够将数组排序。这就是希尔排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Shell {
    //将a[]按升序排列
    public static void sort(Comparable[] a) {
        int n = a.length;
        int h = 1;
        while (h < n / 3) h = 3 * h + 1;//1,4,13,40,121,364,1093,...
        while (h >= 1) {    //将数组变为h有序
            for (int i = h; i < n; i++) {   //将a[i]插入到a[i-h]、a[i-2*h]、a[i-3*h]...之中
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
                    exch(a, j, j - h);
            }
            h /=  3;
        }
    }
    // less()、exch()、isSorted()方法见“排序算法类的模板”
}
希尔排序的详细轨迹（各种插入）
希尔排序的可视轨迹）

总结

最开始看这本书有点费劲，看不下去，尤其是书中那些自定义的API不给详细代码，只给API的作用说明，想看代码只能上本书网站查看，当然这里有对java不熟悉的原因，后来觉得其实没影响的，那些都是一些简单的java系统类库的简单改写。现在越读越有意思，首先本书非常严谨，然后就是书中排版包括前后照应关系安排的太厉害了，最特殊的是本书的图文照应，几乎所有复杂难以理解的算法都有可视化图片，命题+论证+测试都是非常有意思的，就是需要一些数学知识。还有我也是初读这样的书，肯定有理解不到位的地方，谅解！

参考资料

《算法（第4版）》第二章排序2.1初级排序算法

本书网站