排序

最近在看算法4,复习下数据结构算法,以下内容来源于排序部分.

选择排序

不断地选择剩余元素之中的最小者

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

/**
* 将a[]按升序排列
*/
public static void sort(Comparable[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        // 最小元素的索引
        int min = i;
        // 将a[i]和a[i+1..N]中最小的元素交换
        // 从当前下标向后遍历
        for (int j = i + 1; j < n; j++) {
            // 找到比min值小的下标
            if (less(a[j], a[min])) {
                min = j;
            }
        }
        // 将找到的最小值交换到i处
        exch(a, i, min);
        assert isSorted(a, 0, i);
    }
    assert isSorted(a);
}

插入排序

public static void sort(Comparable[] a) {
    int n = a.length;
    // 对数组中的每个元素
    for (int i = 0; i < n; i++) {
        // 将 a[i] 插入到有序的 a[i-1]、a[i-2]、a[i-3]...之中
        // 从当前元素向前面元素比较,若当前元素小于前面元素,则交换元素位置.直到i前面元素都有序为止.
        for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
            exch(a, j, j - 1);
        }
        assert isSorted(a, 0, i);
    }
    assert isSorted(a);
}

希尔排序

基于 插入排序的快速的排序算法。

希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组被称为 h 有序数组。

/**
* 将a[]按升序排列
* Rearranges the array in ascending order, using the natural order.
*
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
    int n = a.length;

    // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
    int h = 1;
    while (h < n / 3) {
        h = 3 * h + 1;
    }

    while (h >= 1) {
        // h-sort the array
        // 将数组变为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);
            }
        }
        assert isHsorted(a, h);
        // 减小h范围
        h /= 3;
    }
    assert isSorted(a);
}

n = 12
h = 4

0 = {Integer@800} 1
1 = {Integer@801} 15
2 = {Integer@802} 3
3 = {Integer@803} 4
4 = {Integer@804} 10
5 = {Integer@805} 11
6 = {Integer@806} 8
7 = {Integer@807} 9
8 = {Integer@808} 12
9 = {Integer@809} 13
10 = {Integer@810} 5
11 = {Integer@811} 6

当h=4时,间隔为4,i初始化为4.考虑比较交换
a[4],a[0]
a[5],a[1]
a[6],a[2]
…
a[11],a[7],a[1]

h /= 3,得到h=1,
当h=1时,i初始化为1,考虑比较交换
a[1],a[0]
a[2],a[1],a[0]
…
a[11]插入到a[0]~a[10]

归并排序

将两个有序的数组归并成一个更大的有序数组.

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。

它能够保证将任意长度为 N 的数组排序所需时间和 NlogN 成正比；缺点:所需的额外空间和 N 成正比。

public static void sort(Comparable[] a) {
    Comparable[] aux = new Comparable[a.length];
    sort(a, aux, 0, a.length - 1);
    assert isSorted(a);
}

private static void sort(Comparable[] a, Comparable[] aux, int low, int high) {
    // 将数组a[low..high]排序
    if (high <= low) {
        return;
    }
    int mid = low + (high - low) / 2;
    // 递归调用当前方法.将左半边排序
    sort(a, aux, low, mid);
    // 递归调用当前方法.将右半边排序
    sort(a, aux, mid + 1, high);
    // 归并结果
    merge(a, aux, low, mid, high);
}
    
// 调用本方法需要保证mid左右两个部分 分别有序. 然后归并起来
// stably merge a[low .. mid] with a[mid+1 ..high] using aux[low .. high]
public static void merge(Comparable[] a, Comparable[] aux, int low, int mid, int high) {
    // precondition: a[low .. mid] and a[mid+1 .. high] are sorted subarrays
    assert isSorted(a, low, mid);
    assert isSorted(a, mid + 1, high);

    // copy to aux[]
    // 将a[low..high]复制到aux[low..high]
    for (int k = low; k <= high; k++) {
        aux[k] = a[k];
    }

    // merge back to a[]
    // 归并回到a[low...high]
    int i = low, j = mid + 1; // i初始值 左边第一个元素; j初始值 右边第一个元素
    for (int k = low; k <= high; k++) { // 遍历原始数组a中的所有元素
        if (i > mid) {
            a[k] = aux[j++];
        } else if (j > high) {
            a[k] = aux[i++]; // aux[mid]右边元素都取完了,所以剩下的都是左边的元素,把左边的元素依次放到a数组后面
        } else if (SortUtil.less(aux[j], aux[i])) { // 若右边当前元素 小于左边当前元素
            a[k] = aux[j++]; // 说明 aux数组 右边部分当前元素小于左边部分当前元素.取右边元素放入a数组,j++
        } else {
            a[k] = aux[i++]; // 说明左边部分当前元素小于右边部分当前元素.取左边元素,i++
        }
    }

    // postcondition: a[low .. high] is sorted
    assert isSorted(a, low, high);
}

快速排序

快速排序 是原地排序（只需要一个很小的辅助栈），且将长度为 N 的数组排序所需的时间和 NlogN 成正比.

快速排序是一种分治的排序算法。

它将一个数组分成 两个子数组，将两部分独立地排序。

切分函数（partition）

该方法的关键在于切分，这个过程使得数组满足下面三个条件：

对于某个 j ，a[j] 已经排定；
a[lo] 到 a[j-1] 中的所有元素都不大于 a[j] ；
a[j+1] 到 a[hi] 中的所有元素都不小于 a[j] 。
我们就是通过递归地调用切分来排序的。

private static void sort(Comparable[] a, int low, int high) {
    if (high <= low) {
        return;
    }
    // 切分,能保证下标j左侧的元素都小于a[j],j右侧的元素都大于a[j]
    int j = partition(a, low, high);
    // 将左半部分a[low .. j-1]排序
    sort(a, low, j - 1);
    // 将右半部分a[j+1 .. high]排序
    sort(a, j + 1, high);
    assert isSorted(a, low, high);
}

public static int partition(Comparable[] a, int low, int high) {
    int i = low;
    int j = high + 1;
    Comparable v = a[low]; // 切分元素.按照 a[low] 的值 v 进行切分
    while (true) {
        // 扫描左右，检查扫描是否结束并交换元素
        // find item on low to swap
        while (SortUtil.less(a[++i], v)) { // a[i] 小于 v 时,增大 i.直到找到一个a[i]大于v的值
            if (i == high) {
                break;
            }
        }

        // find item on high to swap
        while (SortUtil.less(v, a[--j])) { // a[j] 大于 v 时,减小 j,直到找到一个a[j]小于v的值
            if (j == low) {
                // redundant since a[low] acts as sentinel
                break;
            }
        }
        // 当指针 i 和 j 相遇时主循环退出
        // check if pointers cross
        if (i >= j) {
            break;
        }
        // 由于a[j]小于v,a[i]大于v. 交换 a[i] 和 a[j] 来保证 i 左侧的元素都不大于 v ，j 右侧的元素都不小于 v
        SortUtil.exch(a, i, j);
    }
    // 将v = a[j]放入正确的位置.当指针相遇时退出while循环,交换 a[low] 和 a[j].切分结束.这样切分值就留在 a[j] 中了
    // put partitioning item v at a[j]
    SortUtil.exch(a, low, j);
    // a[low..j-1] <= a[j] <= a[j+1..high] 达成
    // now, a[low .. j-1] <= a[j] <= a[j+1 .. high]
    return j; // 返回切分下标.该下标左侧的值都小于a[j].该下标右侧的值都大于a[j]
}