常用的排序算法（4）：

插入排序（小数据基本有序），快速排序，归并排序（大数据集），堆排序

冒泡排序和选择排序实际场景不会使用性能差

如何评估排序算法的性能：时间复杂度，空间复杂度，稳定性

日常说一个算法的时间复杂度是O(xx)，通常都是指该算法的最坏情况时间复杂度。

当算法的输入数据已部分接近或就是理想状态时，选择算法考虑它的最好情况。

平均情况时间复杂度有助于了解算法在一般情况下的性能表现，是大多数实际应用中最为关注的指标。

选择排序是不稳定的：3 3‘ 2 

对于稳定性的判断，如果是长距离交换就容易出现不稳定的情况 

插入排序一般写法是稳定的，但是如果是相等的还交换就不稳定

希尔排序就是使得可以一次性可以一次性跨越多个元素位置提高效率，在基本有序的时候效率更高

3. 归并排序

递归和分治思想：递归和分治往往是结合的

归并排序就是分解再合并

取中间元素注意可能溢出 left + ((right-left) >>1); 采用移位的方式可以运算速度更快

递归分解左右区间，是逻辑上的分解，实际上并没有进行分解

在合并中需要用到临时数组，因为如果是还是用原数组进行逻辑上的排序，会导致交换数据以后顺序就乱了。

在主函数中进行临时数组的分配和回收而不是在递归中，因为太复杂混乱

大数据集归并排序的最大优势就是稳定（短距离遍历），时间效率低（递归），空间效率低（需要用到额外数组）

归并排序的时间复杂度是O(nlogn),归并排序与数据内容（有序否）是什么无关（都是拆开合并）。

总结归并排序主要优点就是稳定，性能不是那么好。

4.快速排序 (不稳定)

快速排序一般不会用随机位置作为中间值，效果不好不能选到数值是中间的值，所以一般是选开头或者结尾的元素

快排的效率是最高的。

快排不将递归视作空间复杂度的提高时可以视为原地排序，是O(nlogn)，

快排普遍采用递归实现，并且用于大的数据集，如果数据是接近有序的情况下可能会出现栈溢出的情况。

注意递归的时候结束条件写在最上面

5.堆排序（最大的优点是不用递归）(快排和归并排序是递归)

虚拟内存的堆和数据结构的堆没有关系，数据结构的堆理解为特殊的完全二叉树（大小顶堆仅仅是根节点是最大的或者最小的，没有其他关系）

在进行堆排序的时候，并不需要额外的内存空间，将原地的数组视为一个堆构建为大顶堆。

数组的首元素视为完全二叉树根节点，左右子树根节点的下表是2i+1和2i+2；

堆排序与数据本来的情况是无关的（与归并排序一样），构建大顶堆的时间复杂度是O(n)

堆化的时间复杂度是O(logn)，总的时间复杂度是O(nlogn)

堆排序是不用递归的，不用占用额外的空间，但是是不稳定的。

插入排序：小数据集！！！！      基本有序最好

归并排序：大数据集，稳定

快速排序：大数据集，通用，效率高，但不稳定，递归可能导致栈溢出可以转用堆排序

堆排序：大数据集，不稳定排序算法，O(1)且不递归

5.二分查找

在工作中很少光使用二分查找，因为有很大的不确定性，不确定是第一个出现还是最后一个出现