排序就是将一组对象按照某种逻辑顺序重新排列的过程。排序算法有很多种，这里聊一聊初级排序算法

选择排序

选择排序的原理

选择排序是所有排序中最简单的排序算法N，选择排序的过程是这样的：首先，找到数组中最小的那个元素，然后与数组中第一个元素交换位置（如果数组第一个元素就是最小的，那它就和它自己交换）。再次，在剩下的元素中找到最小的元素，并和数组第二个元素进行交换，如此往复交换，直到将整个数组排序。之所以叫做选择排序，是因为它总是寻找数组中剩余元素的最小者（当然也可以寻找最大者来完成排序）
原理如下图所示
选择排序

选择排序的算法复杂度

在选择排序中，交换元素的代码写在内循环之外，每次交换都能排定一个元素，因此交换的总次数为N，这个算法的时间效率取决于比较的次数。

对于长度为N的数组，选择排序需要大约N2 / 2 次比较和N次交换。选择排序的时间复杂度为O(N2),因为没有用到额外的存储空间，故选择排序的空间复杂度为O(1)

选择排序的特点

  • 运行时间和输入无关：一个有序的数组或是一个元素都相同的数组还是一个乱序的数组进行排序所花费的时间是相同的
  • 数据移动是最少的：大部分排序算法增长数量级和都是线性对数或是平方级别。

选择排序的代码实现

使用Java实现选择排序，代码如下

public class Selection {
    public static void sort(Comparable[] a) {
        //将a[]升序排列
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int min = i;
            for (int j = i+1; j < n; j++) {
                if (a[j].compareTo(a[min]) < 0) min = j;
            }
            Object swap = a[i];
            a[i] = a[min];
            a[min] = swap;
        }
    }
}

插入排序

插入排序的原理

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤2~5。

原理如下图所示
插入排序

插入排序的性能

对于随机列的长度为N且比较元素不重复的数组，平均情况下插入排序需要～N2 / 4次比较以及～N2 / 4次交换。最坏的情况下需要～N2 / 2次比较和～N2 / 2次交换，最好的情况下需要N-1次比价和0次交换。

插入排序的特点

数组中倒置（数组中两个顺序颠倒的元素）的数量小于数组大小的某个倍数，那么这个数组是部分有序的，例如下面这几种：

  • 数组中每个元素距离它的最终位置都不远
  • 一个有序的大数组接一个小数组
  • 数组中只有几个元素的位置不正确

插入排序对这样的数组很有效，而选择排序就不行了，当倒置的数量很少时，插入排序很可能比其他排序算法都要快。

插入排序的代码实现

public class Insertion {
    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--) {
                Object swap = a[j];
                a[j] = a[j-1];
                a[j-1] = swap;
            }
        }
    }
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
}

希尔排序

希尔排序原理

希尔排序为了加快速度简单地改进了插入排序，交换不相邻元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
希尔排序的思想是数组中任意间隔为h的元素都是有序的，一个h有序数组就是h个相互独立的有序数组编制在一起组成的一个数组。在进行排序时，如果h很大，就能将元素移动到很远的地方，为实现更小的h有序数组创造方便。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  • 按增量序列个数k，对序列进行k 趟排序；
  • 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

原理如下图所示：
希尔排序

希尔排序的代码实现

public class Shell {

    public static void sort(Comparable[] a) {
        int n = a.length;
        int h = 1;
        while (h < n/3) h = 3*h + 1;

        while (h >= 1) {
            // h-sort the array
            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 /= 3;
        }
    }


    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
}