基本排序算法

成本模型：
一般为元素比较和交换的次数。
如果不需要比较和交换，那么我们计算数组访问的次数

1. 冒泡排序

冒泡排序，顾名思义，是通过不断交换相邻元素，让较小的元素向上浮，让较大的元素向下沉的算法。

1. 从数组头部开始，对每一对相邻元素进行比较，并交换
2. 索引加一，重复上述操作，直到索引到达数组末尾
3. 此时，可以保证数组末尾元素必定是最大的元素
4. 将索引移动范围剪一，并重复上述过程

1.1 性能

由于需要进行两层循环，冒泡排序的复杂度为 $O(N^2)$，而且对于已经有序的数组，它也同样需要 $O(N^2)$ 的复杂度。

2. 选择排序

1. 找到最小元素
2. 把它和第一个元素相交换
3. 在剩下的元素中寻找最小元素
4. 将其和第二个元素交换
5. 重复以上步骤，直到数组排序完毕（元素指针走到数组末尾）

2.1 性能

在一个长度为 $N$ 的数组中，它需要 ${N^2}/{2}$ 次的比较和 $N$ 次的交换

特点：

1. 所需时间和输入模型无关
2. 数据的移动是最少的

3. 插入排序

插入排序的主要思想是在数组的无序部分取元素插入到有序部分中，从而逐步构建有序。

举一个按照升序排列的例子

1. 将 $a[i]$ 和 $a[0]$ 到 $a[i - 1]$ 中所有比它小的元素依次交换
2. 保证在 $a[i]$ 的左边，元素总是有序的
3. 当 $i$ 指针到达数组末尾的时候，排序就完成了。

3.1 实现

public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            // Compare a[i] with the items which is at its left side.
            exch(a, j, j-1);
        }
        assert isSorted(a, 0, i);
    }
    assert isSorted(a);
}

3.2 性能

此算法的性能和输入有关。
如果输入的序列已经是部分排序的，那么使用这个算法将会比较快；
但是由于存在嵌套的 for 循环，在最坏情况下仍然需要 $N^2$ 次交换

在之后的排序算法优化中，我们会经常使用插入排序的这一特性，在小数组、部分有序数组中应用插入排序，进一步降低时间复杂度。

3.3 优化

3.3.1 使用移动代替交换

可以在上述算法实现上进行进一步调优。
可以简单的将大的元素往右移动，从而空出一个正确的位置，将所需元素插入即可；
而不是每次都要交换一次元素。
这个调优将能节省一半的数组访问开支

public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        int j = i;
        Comparable t = a[j]; // 需要插入的元素

        for (; j > 0 && less(a[j], a[j-1]); j--) {
            a[j] = a[j - 1]; // 将大的元素向右移动
        }

        a[j] = t; // 将元素插入空出的位置
        assert isSorted(a, 0, i);
    }
    assert isSorted(a);
}

3.3.2 使用二分查找

由于是在有序部分寻找恰当位置插入，可以使用二分查找提高搜索效率

public int binaryIndex(int[] arr, int lo, int hi, int key) {
    int mid;
    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        if (arr[mid] < key) {
            lo = mid + 1;
        } else if (arr[mdi] > key) {
            hi = mid - 1;
        } else {
            return mid;
        }
    }
}

4. 希尔排序

希尔排序是基于插入排序的一种排序算法。
其基本思想是让元素在 $h$ 步长中有序
如果 $h$ 很大，那么我们就可以将一个元素一次性移动很远

4.1 实现

public class Shell {
    public static void sort(Comparable[] a) {
        // Increasing order of a[]

        int N = a.lenth;
        int h = 1;

        while (h < N/3) {   // From N/3 to reduce the h
                            // 1, 4, 13, 40, 121, 364, 1093, ...
            h = 3 * h + 1;
        }

        while(h >= 1) {
            // Make the array h ordered

            for(int i = h; i < N; i++) {
                // Insert the a[i] into the 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) {
                    // Replace j-- as the j -= h
                    exch(a, j, j-h)
                }
            }
            h = h / 3;
        }
    }
}

4.2 性能

希尔排序比插入排序和选择排序都要快；
但是我们并不能给出一个准确的数学分析证明它的精确增长函数

但是一个重要的结论已经被证明：

希尔排序的复杂度达不到平方级别

这是很神奇的，只是因为改变了插入排序的步长就可以让复杂度下降到平方级别以下。