不同的排序方式，如有错误请评论指出，我会及时更改

冒泡排序及其优化

冒泡排序 稳定排序，平均复杂O(n^2) 最优 O(n)

选择排序

//选择排序，选择最小和开始交换
好坏平均复杂度 O(n^2) 不稳定

插入排序

插入排序 稳定排序 时间O(n^2)

快排及其优化

快排 不稳定排序 O(nlogn) 还有多路快排优化

• 初始版本

• 增加随机数

• 三路快排
  三路快排，分三部分，1小于tmp部分，等于tmp部分，大于tmp部分
  2022.3.15 全新版本

归并排序

稳定排序 时间O(nlogn) 空间O(n) 有多路归并
归并可以结合很多其他知识 链表，树等等,分治思想很重要（至少面试会问）
海量数据排序可以使用多路归并

希尔排序

间隔插入排序 懒得写了

堆排序

堆排序 不稳定 时间复杂O(nlogn)

建堆时间复杂度为O(n) 计算方式参考
topk问题，优先队列实现，建议手动写堆写下合并链表的题目
leetcode 合并k个排序链表，最优解使用优先队列，和堆有关

• 另外一种堆排写法，差不多

自行验证

数组中第k大元素

• 堆排序方式,大顶堆移除堆顶k-1次

• 快排方式,不需要完全排序,每次只排一遍
  时间复杂度O(n)