排序算法

快速排序

• 思想：分治
  • 1、选一个基准
  • 2、头、尾指针遍历，小于基准在左边，大于基准在右边
  • 3、递归基准的左边、右边
• 时间复杂度：最好情况每次递归都平分数组，一共需要递归logn次，每次需要n时间，复杂度为O(n*logn)，最坏情况每次都把数组分成1和n-1，一共需要递归n次，每次需要n时间，总体复杂度为O(n^2)。平均总体时间复杂度为O(nlogn)。
• 空间复杂度：和时间复杂度相关，每次递归需要的空间是固定的，总体空间复杂度即为递归层数，因此平均/最好空间复杂度为O(logn)，最坏空间复杂度为O(n)
• 稳定性：不稳定
• 场景：小数据量排序

冒泡排序

• 思想：双层遍历，逐个对比
  • 1、对比相临的数值，大者交换到后面
  • 2、重复对比
• 时间复杂度：n^2
• 空间复杂度：1
• 稳定性：稳定

归并排序

• 思想：分治
  • 1、递归对半分组，交换位置
  • 2、归并megre分组后结果
• 时间复杂度：任何情况下为O(nlogn)
• 空间复杂度：n
• 稳定性：稳定
• 场景：大数据量排序

堆排序（堆:完全二叉树)

• 思想：
  • 1、构建堆，(升序构建最大堆,降序构建最小堆）
  • 2、将堆顶元素下沉到数组尾部
  • 3、重新调整堆，重复下沉堆顶元素
• 时间复杂度：O(nlogn)
• 空间复杂度：原地排序，O(1)
• 稳定性：不稳定
• 场景：