排序
排序
稳定性问题：当出现同一数值时，可以正确处理的方法即为稳定排序
时间空间稳定性一般不可兼得。
一.快速排序
思路：将一个数放到确定位置，此位置称为轴（Pivot），让后递归完成结果
1.解法1
在数组的两端设置两个指针，一个从左往右走，一个从右往左走，左侧的需要放比轴小的，右侧放比轴大的，在两侧指针都不满足的时候两个指针位置进行交互，在两边指针相互越过的时候停止。然后交换轴
接下来对左右两侧进行递归处理，完成快排。
2.解法2
二.归并排序（Merge,二路归并）
思路：两个有序数组 -> 一个有序数组（相当于两个有序的顺序表合并为一个顺序表，时间复杂度 O（N+M） ）
时间复杂度: O(nlogn) 每一趟需要 N 复杂度 执行 logN 轮
空间复杂度 O(n)
稳定排序算法
特殊情况:
三.堆排
完全二叉树，在无守卫的时候： 父节点 = (n-1) /2 左子树 = n*2+1 右子树 = n*2+2
思路：将数组建立一个逻辑上的堆
- 调整到满足最大堆的定义
- 将堆顶与最后一个元素交换，相当于删除了这个最大元素，重新构成了一个堆，重新调整到符合堆。
时间复杂度：O(nlogn)
空间复杂度：O(1)
不稳定排序