很容易想到的一种排序思路是，每次都遍历数组，查看相邻的两个数字的大小并交换位置，这样每次都能够将较大的那个元素移动至数组的另一端。每一次遍历，较大的元素都会像气泡一样慢慢的“浮动”至数组另一端，这便是这个算法被叫做冒泡排序的原因。

下面这张动图展示了冒泡排序的整个过程：

冒泡排序很容易理解，复杂度也很好分析，在最好的情况下，如果数组本来就是有序的，那么只需要遍历一次数组即可，时间复杂度是 O(n)，在最坏的情况下，每排列一个数据，都需要遍历整个数据集，因此时间复杂度是 O(n²)，平均情况下也接近 O(n²)。排序过程不会使用到额外的存储空间，因此空间复杂度是 O(1)，是原地排序。

冒泡排序是稳定的吗？从上面的图中可以看到，每次比较都是交换的两个数值不相等的数据，而相等的数据要么不满足条件不移动，要么满足条件则全部移动，这保证了相等数据的前后顺序不发生改变，因此冒泡排序是稳定的。

下面是一个简单的代码实现供参考：

public class BubbleSort extends AbstractSort {

    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        int n = nums.length;
        boolean swap = true;
        for (int i = 0; swap && i < n; i++) {
            swap = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (compare(nums[j + 1], nums[j])){
                    swap(nums, j, j + 1);
                    swap = true;
                }
            }
        }
    }
}

需要注意的是，代码中使用到了一个辅助变量 swap，它的作用是标识数据是否已经没有交换了，如果没有则说明数据已经有序了，直接跳出循环，这样可以避免多余的冒泡操作。例如数据 1 2 3 4 5 6，第一遍历之后，发现已经是有序的了，就没有必要再进行后续的遍历。

选择排序也很容易理解，对于一个要排序的数组，我们每次都从数组中寻找最小值，并把它和第一个元素交换，然后在剩下的数据中继续寻找最小值，然后将其与数组第二个元素交换，如此循环往复，直到整个数组有序。

下面这张动图可以帮助你理解选择排序的整个过程：

无论在最好还是平均情况下，选择排序的时间复杂度都是 O(n²)，因为就算是要排序一个已经有序的数组，选择排序的逻辑还是要遍历数组寻找最小值。空间复杂度则和冒泡排序一样，是 O(1)。

需要注意的是，选择排序是不稳定的，这是由它的交换特性决定的，我举个例子就容易明白了，例如数据 3 3 2 0 1 5，第一次遍历，我们找到了最小值 0，并把它和第一个数据 3 交换位置，那么这两个 3 的前后顺序就被改变了，因此选择排序不能保证稳定性。

下面是一个简单的代码示例供参考：

public class SelectionSort extends AbstractSort {

    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int min = i + 1;
            for (int j = i; j < n; j++) {
                if (compare(nums[j], nums[min])){
                    min = j;
                }
            }
            swap(nums, i, min);
        }
    }

}

插入排序的基本思路是：依次遍历每一个数字，并将其和前面已排序的数据进行对比，将其插入到合适的位置。生活中也有很多这样的例子，假如我们手中有一副扑克牌，当新来了一张扑克牌之后，我们便会依次查找，将新来的扑克牌放到合适的位置。

插入排序的过程如下图：

插入排序的时间复杂度和冒泡排序类似，这里不再赘述了，平均情况下的时间复杂度是 O(n²)，空间复杂度是 O(1)，是原地排序。并且插入排序也是稳定的，从上图也很容易明白，在每个数据的遍历交换过程中，相同数据的前后顺序肯定不会被改变。

下面是一个简单的代码示例供参考：

public class InsertionSort extends AbstractSort {
    
  	@Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int j = i + 1;
            Object k = nums[j];
            while (j > 0 && compare(k, nums[j - 1])){
                nums[j] = nums[--j];
            }
            nums[j] = k;
        }
    }
}

希尔排序其实是插入排序的一个优化版本，如果你搞懂了插入排序，那么弄懂希尔排序就非常容易了。回想一下，插入排序的特点是：每次比较的时候交换相邻元素，因此数据每次只能移动一位。如果这样的话，对于一些大规模乱序的数据，例如最大值刚好在头部，那么将其移动至尾部，需要移动大概 n - 1 次。

而希尔排序则将数据分成了 n 个组，对每个组内的数据分别进行插入排序，这样就能够将较大的数据一次性移动很多位，为后续的比较交换提供了便利。文字描述起来可能比较的晦涩抽象，可以结合下面的图来看一下：

我们先定义一个增量 k，k 一般为数组长度的 1 / 2 ，上图中要排序的原始数据的个数是 8 ，因此 k = 8 / 2 = 4，所以第一次可以将数组分为 4 组，分别是 (9, 5), (2, 1), (4, 0), (3, 6)，即上图中用直线连接起来的数据，然后将每个组内的数据分别进行插入排序，那么第一次排序之后的结果为：5 1 0 3 9 2 4 6。

可以看到最开始 9 在数组最前面，但是经过第一次排序之后，9 已经向后移动了 4 位，相较于插入排序，这样就减少了移动的次数，希尔排序的性能提升就主要体现在这里。

然后继续进行分组，这时 k 缩小一半变为 2，因此我们将数组分为两组，然后在组内再进行插入排序，如下图：

此时分为了两组，分别是(5, 0, 9, 4), (1, 3, 2, 6)，进行排序之后的结果是：0 1 4 2 5 3 9 6，可以看到此时数组已经基本上是有序的了。

然后 k 再次缩小为 1，我们将数组分为 1 组，其实就是原始的数据了，然后再进行一次插入排序，由于其实数据已经是基本上有序的了，因此只需要微调即可，一般不会进行大量的数据移动：

整个排序的过程当中，增量 k 是一步一步缩小的，正因此，希尔排序其实也叫做缩小增量排序。

下面是一个简单的希尔排序的代码示例：

public class ShellSort extends AbstractSort {

    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        int n = nums.length;
        int k = n / 2;
        while (k >= 1){
            for (int i = 0; i < n - k; i++) {
                int j = i + k;
                Object v = nums[j];
                while (j > k - 1 && compare(v, nums[j - k])){
                    nums[j] = nums[j - k];
                    j = j - k;
                }
                nums[j] = v;
            }
            k = k / 2;
        }
    }
}

前面说到的这几种基础排序算法，在实际当中的使用并不是很多，因为它们的时间复杂度较高，应用在大规模数据中的话，效率将会非常低下，因此它们只适合小规模的数据排序。例如 Java 中的双轴快速排序，在数据量小于 47 时便使用了插入排序。

你也许会纳闷，为什么插入排序、冒泡排序、选择排序的平均时间复杂度都是 O(n²)，但是在大多数情况下，针对数据量较少的情况，一般都会采用插入排序呢？

简单分析一下，选择排序就不用说了，因为它的性能并没有绝对优势，即便是在数组已经有序的情况下，它的时间复杂度仍然是 O(n²)，并且它还不是稳定的，因此选择排序一般并不会考虑使用。

接下来再看看冒泡排序和插入排序，这两者虽然时间复杂度是一样的，但是在实际的排序过程中，冒泡排序的数据交换次数更多，你可以从上面的代码示例中看到，冒泡排序的一次交换涉及到三次操作，而插入排序只需要一次数据赋值，这样的话便使插入排序要稍微快一些。

你可以构造一组随机数据来测试这两种排序算法，例如我在本机测试了一组 5 万个数据，冒泡排序的耗时是 8 秒多一点，而插入排序只使用了不到 3 秒。

//冒泡排序，swap 函数涉及到三次赋值操作
for (int j = 0; j < n - i - 1; j++) {
   if (compare(nums[j + 1], nums[j])){
     swap(nums, j, j + 1);
     swap = true;
   }
}

//插入排序，交换时只需要一次数据赋值
while (j > 0 && compare(k, nums[j - 1])){
   nums[j] = nums[j - 1];
   j--;
}

最后再来看看希尔排序，希尔排序发明于 1959 年，它是最早的时间复杂度突破 O(n²) 的排序算法之一，但是它的应用并不是很广泛，原因在于它遇到了更强劲的“对手”，相较于归并排序，它并不是稳定的，而相较于快速排序，它的性能又没有任何优势可言，因此归并排序和快速排序更受青睐。

在介绍归并排序之前，先简单说下分治思想。分治，顾名思义就是分而治之，它是一种解决问题的思路，将原始问题分解为多个相同或相似的子问题，然后将子问题解决，并将子问题的求得的解进行合并，这样原问题就能够得到解决了。分治思想是很多复杂算法的基础，例如归并排序、快速排序、二分查找等等。

言归正传，再来看归并排序，它的概念理解起来非常简单，如果我们要对一组数据进行排序，我们可以将这个数组分为两个子数组，子数组再进行分组，这样子数组排序之后，将结果合并起来，就能够得到原始数据排序的结果，相信你已经发现了，这就是典型的利用分治思想解决问题的思路。

下面这张图展示了将一个问题分解为多个子问题的过程：

子问题得到解决之后，需要将结果合并，合并的过程如下图：

下面的动图比较直观的展示了归并排序的整个过程，可以对照起来理解一下：

如果使用一个简单的公式来表示归并排序的话，那么可以写成这样：

 merge_sort(data, p, r) = merge(merge_sort(data, p, q), merge_sort(data, q + 1, r));

我来简单解释一下这个公式，我们将排序的数组叫做 data，p 和 r 分别表示其起始和终止下标，因为要进行分组，因此取 p 和 r 的中间值 q，然后对 p 到 q 和 q + 1 到 r 的数据分别再进行排序。

排序之后的结果需要用一个合并的函数来将结果合并，这个函数可以叫做 merge，merge 函数的功能很简单，对于两个已排序的数据区间，假设下标是 p ~ r，我们可以新建一个临时数组，然后依次比较两个已排序的数据区间的值，并将其一 一复制到临时数组中，你可以结合下图来理解一下：

理解了这些之后，再来看归并排序的代码实现就会非常简单了，下面是一个代码示例：

public class MergeSort extends AbstractSort {

    private Object[] temp;

    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        int n = nums.length;
        temp = new Object[n];
        sortHelper(nums, 0, n - 1);
    }

    private void sortHelper(Object[] data, int p, int r){
        if (p >= r){
            return;
        }

        int q = p + (r - p) / 2;
        sortHelper(data, p, q);
        sortHelper(data, q + 1, r);
        merge(data, p, q, r);
    }

    private void merge(Object[] data, int p, int q, int r){
        int i = p, j = q + 1;
        System.arraycopy(data, p, temp, p, r - p + 1);

        for (int k = p; k <= r; k++) {
            if (i > q) data[k] = temp[j++];
            else if (j > r) data[k] = temp[i++];
            else if (compare(temp[j], temp[i])) data[k] = temp[j++];
            else data[k] = temp[i++];
        }
    }
}

归并排序的时间复杂度，一般可以使用两种方式来进行推导，假如将要排序的数组的长度记为 n，排序一个长度为 n 的数组的时间记为 T(n)，由于归并排序需要将原问题分解成子问题，因此 T(n) 又可以写成 T(n) = 2 * T(n/2) + n，其中 n 表示合并两个子数组所需要的时间。

然后继续进行分解，这个公式可以表示成这样：

T(n) = 2 * T(n/2) + n
     = 2 * ( 2 * T(n/4) + n/2) + n                = 4 * T(n/4) + 2n
     = 2 * ( 2 * (2 * T(n/8) + n/4) + n/2) + n    = 8 * T(n/8) + 3n
     … … … 
     = 2^k * T(n/2^k) + k*n

可以看到，时间计算公式可以记为：T(n) = 2^k * T(n/2^k) + k * n，当 n / 2^k = 1 的时候，可以得到 k = logn，然后再将 k 代入到公式中，可以得到 T(n) = Cn + nlogn （C 为常数），使用大 O 表示法，那么归并排序的时间复杂度可以大致记为 O(nlogn)。

当然这种分析方式较为复杂抽象，还有一种更加简单直观的方式，我们可以将归并排序的过程使用树的方式，形象的展示出来，大致就是这样的：

可以看到，归并排序的时间复杂度可以使用树结构分级展示，每一层涉及到的操作是分组和合并，所消耗的时间都是一样的 n，因此算法的总体时间复杂度就是 n * 树的高度，可以很明显的看出，这是一颗满二叉树，满二叉树的高度一般是 logn，因此归并排序的时间复杂度就是 O(nlogn)。

归并排序的空间复杂度比较简单，从代码中可以看到，当进行子数组合并的时候，需要一个临时数组 temp，数组的长度等于要排序的数组长度，因此空间复杂度可以表示为 O(n)。

其实归并排序并没有像快速排序那样应用广泛，其中很重要的原因便是它并不是原地排序算法，这是它的一个致命弱点。

最后思索一下归并排序是稳定的吗？这个问题比较好理解，数组的拆分并不会涉及到数据交换，只有合并才会，因此归并排序是否稳定主要取决于 merge 的过程。

假设我们需要合并 1 3 3 5 和 2 3 4 6，可以看到在合并的过程当中，我们的判断条件是单一的，如果第一个数字被放到的了临时数组中，那么后续相同的数字也会依次被放到临时数组中，前后顺序不会被改变，因此归并排序是稳定的。

上面讲到的归并排序是最常见的一种类型，它的特点是自顶向下进行数据拆分，你可以从最开始的分解图清晰的看出来，其实还有另外一种归并排序，它的顺序恰恰相反，是自底向上的，只不过这种方式理解起来并不如上面的直观，你可以简单做个了解。

其思路是这样的：首先进行两两归并（你可以将数组想象成多个只有一个元素的子数组），然后是四四归并（将长度为 2 的子数组合并为长度为 4 的子数组），然后是八八归并，一直进行下去。

下面是一个简单的代码示例：

public class MergeSortBottomUp extends AbstractSort {

    private Object[] temp;

    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        int n = nums.length;
        temp = new Object[n];
        for (int i = 1; i < n; i = 2 * i) {
            for (int j = 0; j < n - i; j += (2 * i)){
                merge(nums, j, j + i - 1, Math.min(j + 2 * i - 1, n - 1));
            }
        }
    }

    private void merge(Object[] data, int p, int q, int r){
        if (compare(data[q], data[q + 1])){
            return;
        }
        int i = p, j = q + 1;
        System.arraycopy(data, p, temp, p, r - p + 1);

        for (int k = p; k <= r; k++) {
            if (i > q) data[k] = temp[j++];
            else if (j > r) data[k] = temp[i++];
            else if (compare(temp[j], temp[i])) data[k] = temp[j++];
            else data[k] = temp[i++];
        }
    }
}

快速排序通常叫做“快排”，它应该是应用最广泛的一个排序算法了，很多编程语言内置的排序工具，都或多或少使用到了快速排序，因为快速排序的时间复杂度可以达到 O(nlogn)，并且是原地排序，前面介绍的几种排序算法都无法将这两个优点结合起来。

快排和归并排序类似，都采用了分治思想，但是它的解决思路却和归并排序不太一样。如果要排序一个数组，我们可以从数组中选择一个数据，做为分区点（pivot），然后将小于分区点的放到分区点的左侧，大于分区点的放到其右侧，然后对于分区点左右两边的数据，继续采用这种分区的方式，直到数组完全有序。

概念读起来可能有点抽象，这里我画了一张图来帮助你理解整个排序的过程：

上图展示了第一次分区的过程，假设要排序的数组的下标是 p ~ r，我们取数组的最后一个元素 5 做为分区点，然后比 5 小的数字 0 3 1 2 移动到 5 的左边，比 5 大的数字 9 6 8 7 移动到 5 的右边。

然后以数字 5 为分界点，其左边的数字（下标为 p ~ q - 1），以及右边的数字（下标为 q + 1 ~ r），分别再进行同样的分区操作，一直分下去，直到数组完全有序，如下图：

下面的动图展示了快速排序的完整过程（注意动图中是选择第一个元素做为分区点的）：

如果使用一个简单的公式来表示快速排序，可以写成