原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。

稳定性指的是，如果待排序的序列中存在值相等的元素，经排序后，相等元素之间原有的先后顺序不变。比如有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。这组数据里有两个 3。经过某种排序算法排序后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。

比如，我们要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。现在有 10 万条订单数据，希望按照金额从小到大对订单数据排序。对于金额相同的订单，希望按照下单时间从早到晚有序。对于该需求，借助稳定排序算法可以非常简洁地解决：我们先按照下单时间给订单排序，注意是按照下单时间。排序完成后，我们用稳定排序算法，按照订单金额重新排序即可。

因为稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。第一次排序之后，所有的订单按照下单时间从早到晚有序了。在第二次排序中，我们用的是稳定的排序算法，所以经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序。

冒泡排序

冒泡排序（Bubble Sort）只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。假如，我们现在要对一组数据 4，5，6，3，2，1 从小到大进行排序。第一次冒泡操作的详细过程就是这样：

可以看出，经过一次冒泡操作之后，6 这个元素已经存储在正确的位置上。要想完成所有数据的排序，我们只要进行 6 次这样的冒泡操作就行了。

动画演示：

代码实现：

public static void sort(int[] array) {
    if (array == null || array.length < 2) {
        return;
    }
    // 外层循环定义每次冒泡需要比较的元素个数，随着冒泡执行，待排序的元素个数会递减
    for (int i = array.length; i > 1; i--) {
        // 内层循环定义每次冒泡过程中，元素比较的次数
        for (int j = 0; j < i - 1; j++) {
            if (array[j] > array[j+1]) {
                int temp = array[j+1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
    }
}

实际上，上面的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到了完全有序的状态，就不用再继续执行后续的冒泡操作。如下图所示，这里面给 6 个元素排序，只需要 4 次冒泡操作就可以了。

代码实现：

public static void betterSort(int[] array) {
    if (array == null || array.length < 2) {
        return;
    }
    for (int i = array.length; i > 1; i--) {
        // 排序提前结束的标志
        boolean flag = false;
        for (int j = 0; j < i - 1; j++) {
            if (array[j] > array[j+1]) {
                int temp = array[j+1];
                array[j + 1] = array[j];
                array[j] = temp;
                flag = true;
            }
        }
        // 没有进行过任何一次数据交换，表示现在的数据已经是有序的了
        if (!flag) {
            break;
        }
    }
}

冒泡排序是原地排序算法吗？
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。

冒泡排序是稳定的排序算法吗？
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是一种稳定的排序算法。

冒泡排序的时间复杂度是多少？
最好情况下，要排序的数据已经是有序的了，我们只需进行一次冒泡操作就可以结束，所以最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n2)，而平均情况时间复杂度通过概率分析也为 O(n2)。

插入排序

我们先来看一个问题。一个有序的数组，我们往里面添加一个新的数据后，如何继续保持数据有序呢？很简单，我们只要遍历数组，找到数据应该插入的位置将其插入即可。

这是一个动态排序的过程，即动态地往有序集合中添加数据，我们可以通过这种方法保持集合中的数据一直有序。而对于一组静态数据，我们也可以借鉴上面讲的插入方法，来进行排序，于是就有了插入排序算法。

实现思路
首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。如下图所示，假设我们要排序的数据是 4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。

动画演示：

代码实现

public static void insertSort(int[] array) {
    if (array == null || array.length < 2) {
        return;
    }
    // 因为初始已排序区间为数组的第一个元素，所以下标从1开始
    for (int i = 1; i < array.length; i++) {
        // 获取当前未排序区间的第一个元素
        int value = array[i];
        // 获取当前已排序区间的最后一个元素下标
        int j = i - 1;
        // 这个循环是遍历已排序区间，与当前这个未排序区间的第一个元素依次进行比较，确定其插入位置
        for (; j >= 0; j--) {
            if (value < array[j]) {
                // 向后移动数据，直接覆盖，不需要交换，因为上面已经保存了value
                array[j + 1] = array[j];
            } else {
                // 因为前面已经是排好序的了，直接返回
                break;
            }
        }
        // 把数组元素后移后，最后会空出一个元素来，把value赋进去，就保证了已排序区间的有序性
        // 因为上面有个j--，在退出循环后这里要加上1
        array[j + 1] = value;
    }
}

插入排序是原地排序算法吗？
从实现过程可以明显看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，即这是一个原地排序算法。

插入排序是稳定的排序算法吗？
在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

插入排序的时间复杂度是多少？
如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入位置。因此最好情况时间复杂度为 O(n)。如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新数据，此时需要移动大量的数据，因此最坏情况时间复杂度为 O(n2)。对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 O(n2)。

冒泡排序和插入排序的时间复杂度相同且都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎？
冒泡排序不管怎么优化，元素交换的次数是一个固定值。插入排序同理。但从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个。所以，虽然冒泡排序和插入排序在时间复杂度上是一样的，都是 O(n2)，但如果想把性能优化做到极致，则首选插入排序。插入排序的算法思路也有很大优化空间，其他的比如希尔排序等。

希尔排序

希尔排序是一种基于插入排序的排序算法，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。实际上，插入排序是很循规蹈矩的，不管原数组分布是怎样，依然一步步的对元素进行比较，移动，插入。这在面对大规模乱序数组时排序很慢，因为它只会交换相邻的元素以找到合适的插入位置，因此元素只能一点点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要 N-1 次移动。

而希尔排序在数组中采用了跳跃式分组的策略，通过某个增量（gap）将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为 1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，直到增量为 1 时，整个数组就有序了。

实现思路：
首先，我们选择初始增量 gap=length/2，缩小增量以 gap= gap/2 的方式，用序列 n/2、(n/2)/2 … 1 来表示。如下图所示，初始增量为 gap=length/2=4。

第二次，增量 gap 缩小为 2：

第三次，增量 gap 缩小为 1，得到最终排序结果：

代码实现：

public static void shellSort(int[] array) {
    // 逐步缩小增量 gap
    for (int gap = array.length / 2; gap > 0; gap /= 2) {
        // 从第 gap 个元素，逐个对其所在组进行插入排序
        for (int i = gap; i < array.length; i++) {
            int j = i;
            int tmp = array[j];
            // 对组内元素进行插入排序
            if (tmp < array[j - gap]) {
                while (j >= gap && tmp < array[j - gap]) {
                    array[j] = array[j - gap];
                    j -= gap;
                }
            }
            array[j] = tmp;
        }
    }
}

选择排序

选择排序（Selection Sort）算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。具体是这样的：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。然后在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法就叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

动画演示：

代码实现

public static void selectSort(int[] array) {
    if (array == null || array.length < 2) {
        return;
    }
    // 外层循环用于确定交换次数
    for (int i = 0; i < array.length; i++) {
        // 先让最小值等于未排序区间中的第一个元素
        int minValue = array[i];
        int minIndex = i;
        // 内存循环用于获取未排序区间中的最小值
        for (int j = i + 1; j < array.length; j++) {
            if (minValue > array[j]) {
                minValue = array[j];
                minIndex = j;
            }
        }
        // 将未排序区间的第一个值和最小值交换
        array[minIndex] = array[i];
        array[i] = minValue;
    }
}

选择排序是原地排序算法吗？
选择排序空间复杂度为 O(1)，是一种原地排序算法。

选择排序的时间复杂度是多少？
选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n2)。

选择排序是稳定的排序算法吗？
选择排序是一种不稳定的排序算法。从图中可以看到，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。比如 5，8，5，2，9 使用选择排序算法来排序的话，第一次找到最小元素2，与第一个5 交换位置，那第一个5和中间的5顺序就变了，所以就不稳定了。因此相对于冒泡排序和插入排序，选择排序稍逊一筹。