数据结构（三）简单排序算法

1. O(n^2) ： 选择排序、冒泡排序、插入排序、希尔排序
2. O(nlogn) ：归并排序、快速排序、堆排序
3. O(n+1) ：桶排序、基数排序、计数排序

---

选择排序（Selection Sort）

选择排序是一种最简单的排序算法，它的算法步骤如下：

1. 找到数组中最小的元素
2. 将它和数组的第一个元素交换位置（如果相同，也交换）
3. 在剩下的元素中找到最小的元素
4. 将它和数组的第二个元素交换位置
5. 重复。。

选择排序交换的总次数为N，算法的效率取决于比较的次数。

特点：

• 运行时间和输入无关、移动数据是最少的
• 选择排序是不稳定的排序方法
• 对于长度为 N 的数组，选择排序需要大约 N²/2次比较和 N 次交换
• 时间复杂度 O(n^2)

public static void selectSort(int[] arr){

    int size = arr.length;

    for (int i = 0; i < size; i++) {
        int min = i;
        // 第二个for循环找出最小元素
        for (int j = i; j < size; j++) {
            if (arr[j] < arr[min]) min = j;
        }
        Swap.swap(arr, min, i);
    }

}

---

插入排序（Insertion Sort）

插入排序，将数插入到其他已经有序的数中的适当位置。为了给要插入的数腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。

插入排序所需的时间取决于输入中元素的初始顺序。(原始数据越接近有序，越快)

命题：对于随机排列的长度为 N 且主键不重复的数组，平均情况下插入排序需要约 N²/4 次比较以及 N²/4 次交换。最坏情况下需要 约 N²/2 次比较以及 N²/2 次交换，最好情况下需要 N-1 次比较 和 0 次交换。

时间复杂度：O(n^2)

/**
 * 原理：插入排序，将数插入到其他已经有序的数中的适当位置
 * 思路：从 a[0] 开始，a[0] 已经是第一个，所以不用动
 *       a[1] 与 a[0] 比较 -> 得出顺序
 *       a[2] 与 a[1] a[0] 比较 -> a[2] 先与 a[1] 比较 ，如果 a[2] 比 a[1] 小，则交换， 然后 a[1] 与 a[0] 比较
 *       a[3] 与 a[2] a[1] a[0] 比较 -> 插入适当位置
 *       ...
 */
private static void insertSort(int[] arr){
    for (int i = 1; i < arr.length; i++) {
        for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
            Swap.swap(arr, j, j-1);
        }
    }
}

---

希尔排序（Shell Sort）

在插入排序和选择排序中，由于它们只能交换相邻的元素，如果有位于数组起始的大元素，则需要多次遍历才能交换到队尾，很不划算。希尔排序以更大的间隔来比较和交换元素，这样，大元素在交换的时候，可以向右移动不止一个位置。

希尔排序只需要在插入排序的代码中将移动的元素距离由1改为h即可。

希尔排序依赖于间隔(step)的选取。

public class Shell {
    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...

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

---

冒泡排序

比较相邻元素，大的放右边

要点：第一躺结束后，最右元素一定是最大的，因此第二趟最右元素不参与，即 size - i - 1

时间复杂度：O(n^2)

public static void bubbleSort(int[] arr){

    int size = arr.length;

    for (int i = 0; i < size; i++) {
        // 第一躺结束后，最右元素一定是最大的，因此第二趟最右元素不参与，即 size - i - 1
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j+1]) Swap.swap(arr, j, j+1);
        }
    }
}