初级排序算法

时间：2019-08-22 15:30:11 阅读：97 评论：0 收藏：0 [点我收藏+]

初级排序算法

排序模板

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

sort - 排序算法的具体实现
less - 比较元素
exch - 元素交换位置
show - 打印数组
isSorted - 判断数组元素是否有序
main - 标准输入读取字符串，将它们排序并输出

选择排序

首先找到最小的那个元素，其次，将它和数组第一个元素交换位置,再次，
在剩下的元素中找到最小的元素，将它与数组的第二个元素交换，知道整个数组排序

public static void sort(Comparable[] a) {
    // 将 a[] 按升序排列
    int N = a.length;
    for(int i = 0 ; i < N; i++) {
        // 将 a[i] 和 a[i...N]中最小的元素交换
        int min = i;    // 最小元素的索引
        for(int j = i+1; j < N; j++)
            if(less(a[j], a[min]))
                min = j;
        exch(a, i, min);
    }
}

技术分享图片

)

特点

运行时间和输入无关：一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间一样长；
数据移动是最少的：每次交换都会改变两个数组元素的值，因此选择排序用了 N 次交换——交换次数和数组的大小是线性关系。其他算法大多都是线性对数或是平方级别。

插入排序
- 与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定。为了给更小的元素腾出空间，它们可能会向右移动。当索引到达数组的右端时，数组排序就完成了。
- 与选择排序不同的是，排序所需的时间取决于输入元素中的初始化顺序

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

技术分享图片

特点

查入排序堆部分有序的数组十分高效，也适合小规模数组

比较

插入排序不会访问索引右侧元素，而选择排序不会访问索引左侧元素

希尔排序

使数组中任意间隔为 h(增量) 的元素都是有序的。这样的数组被称为 h(增量) 有序数组。
增量不断缩小直到为1时，数组有序，排序结束

//算法4例子
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) {
        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;//缩小增量
    }
}
public static void sort02(Comparable[] a) {
    int N = a.length;
    int gap = N / 2;//增量每次减半
    while (gap >= 1) {
        for (int i = gap; i < N; i++) {
            for (int j = i; j >= gap && less(a[j], a[j - gap]);j -= gap) {
                exch(a, j, j - gap);
            }
        }
        gap = gap / 2;
    }
}

技术分享图片