排序总结

1. 概述

基于比较

1. 插入：直接插入 / 希尔
2. 交换：冒泡 / 快排
3. 选择：堆排序
4. 归并

2. 插入

直接插入

特点：稳定，就地，平均，最好情况(初始有序)下

思想：数组被分成两个部分，一个有序一个无序，依次将无序中的元素插入有序部分。

数据若基本有序，插入排序可以大大减少数据交换次数，提升效率。

希尔排序

特点：非稳定，就地， (1 < λ < 2)

思想：先将序列按增量划分为元素个数近似的若干组，使用直接插入排序法对每组进行排序，不断缩小增量并排序，直到增量为1。

因为增量初始值不容易选择，所以该算法不常用。

3. 交换

冒泡排序

特点：稳定，就地，平均 ，最好(初始有序)

思想：数组被分成两个部分，一个有序一个无序，不断将较大元素冒泡到无序子序列首。

若某趟冒泡未发生交换，说明数组已经有序，可提前结束。

快速排序

特点：不稳定，就地，平均 ，最差情况(每次 partition 后 pivot 在最前或最后)

思想：每次选定一个 pivot 将数组分割成两个部分，对二者递归应用这个过程。

3. 选择

堆排序

特点：不稳定，就地，始终

思想： 数组建大根堆，不停地 remove 第一个元素放到最后，并重新调整堆。

4. 其他

归并排序

特点：稳定，非就地，时间始终是 ，空间

思想：首先，将整个序列（共N个元素）看成N个有序子序列，然后依次合并相邻的两个子序列，这样一直下去，直至变成一个整体有序的序列。

适用场景：外部排序

5. 总结

大部分简单排序(直接插入排序 / 冒泡排序)都是稳定排序；
大部分高级排序都是不稳定排序，除了 归并排序。