初级排序算法

背景

本文主要讨论几个初级排序算法，用Java语言来实现。首先给出一个排序算法类模板Example类：将排序代码放在类的sort()方法中，该类还将包含辅助函数less()和exch()以及一个示例用例main()。less()方法对元素进行比较，exch()方法将元素交换位置。下面给出代码：

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Example {
    public static void sort(Comparable[] a) {
        // 此为各种排序算法
    }

    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++) {
            StdOut.print(a[i] + " ");
        StdOut.println();
        }
    }

    // 测试数组元素是否有序
    public 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) {
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

选择排序

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

它有两个鲜明的特点：

运行时间和输入无关。
数据移动是最少的。

下面给出代码实现：

public class Selection {
    // 将a[]按升序排列
    public static void sort(Comparable[] a) {
        int N = a.length;        // 数组长度

        // 将a[i]和a[i+1..N]中最小的元素交换
        for (int i = 0; i < N; i++) {
            int min = i；     // 最小元素的索引

            for (int j = i + 1; j < N; j++) {
                if (less(a[j], a[min])) {
                    min = j;
                }
            }

            exch(a, j, min);
        }
    }
}

插入排序

插入排序即将元素插入到有序的元素中，在实现中，为了要给插入的元素腾出空间，需要将其余所有元素在插入之前都向右移动一位。

插入排序所需的时间取决于输入中元素的初始顺序。插入排序对于实际应用中常见的某些类型的非随机数组很有效。下面给出代码实现：

public class Insertion {
    // 将a[]按升序排列
    public static void sort(Comparable[] a) {
        int N = a.length;

        // 将a[i]插入到a[i-1]、a[i-2]、a[i-3]...之中
        for (int i = 1; i < N; i++) {
            for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
                exch(a, j , j-1);
            }
        }
    }
}

希尔排序

希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。即一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组。

希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。子数组部分有序的程度取决于递增序列的选择。代码如下：

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

        // 将数组变为h有序
        while(h >= 1) {
            // 将a[i]插入到a[i-h],a[i-2*h],a[i-3*h]...之中
            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 = h / 3;
        }
    }
}