排序算法总结

1. 概述

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

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

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

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

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

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

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

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

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

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

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

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

特点：不稳定，就地，始终 O(nlgn)

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

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

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

适用场景：外部排序

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