# 前言

排序算法的成本模型计算的是比较和交换的次数。less()方法对元素进行比较，exch()方法将元素交换位置。

  1. public static void exch(Comparable[] a, int i, int j) {
  2.     Comparable temp = a[i];
  3.     a[i] = a[j];
  4.     a[j] = temp;
  5. }
  7. public static boolean less(Comparable a, Comparable b) {
  8.     return a.compareTo(b) < 0;
  9. }

# 选择排序

首先找到数组中最小的元素，将它和数组中的第一个元素交换位置。然后在剩下的元素中继续寻找最小的元素，将它和数组的第二个元素交换位置。如此往复直到将整个数组排序。选择排序不断地选择剩余元素中的最小值。
bc6be2d0-ed5e-4def-89e5-3ada9afa811a.gif

| 特点

  • 运行的时间和输入无关：一个有序的数组或者主键全部相等的数组或者一个元素随机排列的数组所用的时间是一样长的。

  • 数据的移动是最少的：每次交换都会改变两个数组元素的值，使用了N次交换——交换次数和数组的大小是线性关系。

    | 复杂度分析

    比较次数与初始状态无关，总次数：初级排序 - 图2
    交换次数最好情况是已经有序，交换 0 次；最坏情况是逆序，交换 n-1 次。

  • 时间复杂度

    • 最好：О(n²)
    • 最坏：О(n²)
    • 平均：О(n²)
  • 空间复杂度 O(1)

  • 不稳定

    | 实现

    1. public class Selection {
    2.   public static void sort(Comparable[] a) {
    3.       int n = a.length;
    4.       for (int i = 0; i < n; i++) {
    5.           int min = i;
    6.           for (int j = i+1; j < n; j++) {
    7.               if (less(a[j], a[min])) min = j;
    8.           }
    9.           exch(a, i, min);
    10.       }
    11.   }
    12. }

    # 插入排序

    插入排序是一种简单有效的排序算法。它的工作原理是通过构造有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。

    | 特点

  • 插入排序所需的时间取决于输入元素的初始顺序。

  • 插入排序对于部分有序的数组十分高效。

    | 复杂度分析

    最好情况：数组是升序排列，需要比较 n-1 次，不需要进行交换；
    最坏情况：数组是降序排列，需要比较 n × (n - 1) / 2 次，交换 n × (n - 1) / 2 次；

  • 时间复杂度

    • 最好：О(n)
    • 最坏：О(n²)
    • 平均：О(n²)
  • 空间复杂度 O(1)
  • 稳定

    | 实现

    1. public class Insertion {
    2.   public static void sort(Comparable[] a) {
    3.       int N = a.length;
    4.       for (int i = 1; i < N; i++) {
    5.           for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
    6.               exch(a[j], a[j - 1]);
    7.           }
    8.       }
    9.   }
    10. }

    | 改进

    * 不需要交换的插入排序

    在内循环中将较大的元素都向右移动而不总是交换两个元素（这样访问数组的次数就能减半）。
    1. // 不需要交换的插入排序
    2. public class InsertionB {
    3.   public static void sort(int[] a) {
    4.       int N = a.length;
    5.       for (int i = 1; i < N; i++) {
    6.           int t = a[i];
    7.           int j;
    8.           for (j = i; j > 0 && t < a[j - 1]; j--) {
    9.               a[j] = a[j - 1];
    10.           }
    11.           a[j] = t;
    12.       }
    13.   }
    14. }

    * 插入排序的哨兵

    哨兵：是能够省略判断条件的元素。哨兵机制是常见的规避边界测试的方法。

在插入排序中，先找出数组中最小的元素并置于数组的最左边，这样可以省略内循环中的 j > 0 判断条件。

  1. public static void sort(int a[]) {
  2.     int N = a.length;
  4.     // 将最小的元素先放到数组的最左边作为哨兵
  5.     int min = Integer.MAX_VALUE, min_index = 0;
  6.     for (int i = 0; i < a.length; i++) {
  7.         if (a[i] < min) {
  8.             min = a[i];
  9.             min_index = i;
  10.         }
  11.     }
  12.     int t = a[0];
  13.     a[0] = a[min_index];
  14.     a[min_index] = t;
  16.     // 内循环中的j > 0可以去掉
  17.     for (int i = 2; i < N; i++) {
  18.         for (int j = i; a[j] < a[j - 1]; j--) {
  19.             t = a[j];
  20.             a[j] = a[j - 1];
  21.             a[j - 1] = t;
  22.         }
  23.     }
  24. }

# 希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序的核心思想是使数组中任意间隔为 h 的元素都是有序的，这样的数组称为 h 有序数组。

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

| 特点

  • 希尔排序的时间复杂度与递增序列密切相关，所以分析希尔排序的时间复杂度是个比较麻烦的事。
  • 希尔排序对于中等大小的数组表现良好，但是对规模非常大的数组不是最优选择。
  • 希尔排序实现简单，几乎任何排序工作在开始时都可以用希尔排序。若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法。

    | 实现

    1. public static void sort(Comparable[] a) {
    2.   int N = a.length;
    3.   int h = 1;
    4.   while (h < N / 3) {
    5.       h = 3 * h + 1;
    6.   }
    7.   while (h >= 1) {
    8.       for (int i = h; i < N; i++) {
    9.           for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
    10.               exch(a, j, j - h);
    11.           }
    12.       }
    13.       h = h / 3;
    14.   }
    15. }