时间复杂度是O(nlogn)的排序算法有希尔排序、堆排序、快排、归并排序。
希尔排序
取arr.length / 2 做为间隔，逐一减小间隔
按照间隔，将子数组做插入排序
堆排序
构建大顶堆，从堆最后一个非叶子（数组下标 n/2 - 1）节点开始堆化，一直到堆顶
取出大顶堆的堆顶元素，与数组最后一位交换
从当前堆顶，重新堆化
快排
随机取一个基准，即privot，将大于基准的放入右侧，小于基准的放入左侧
递归的跳出条件，start = end || start = end + 1
将大于基准放入左侧，小于基准放入右侧采用双指针法
归并排序
将连个有序数组合并为一个数组
通过递归，将数组拆分为只有一个的数组
反过来，再按照合并有序数组的方式合并
对比
时间复杂度都在O(n) ~ O($n^2$)
希尔排序、堆排序、快排是不稳定的排序，归并是稳定的排序
空间复杂度不一样，希尔排序、堆排序是O(1)，快排是O(logn)，归并是O(n)