排序总结
插入排序
| 直接插入排序 | 折半排序 | 希尔排序 | |
|---|---|---|---|
| 过程 | 遍历将元素插入前面的有序队列之中 | 在直接插入的基础上改进：通过折半查找找出要插入的位置 | 通过设定步长对步长内的数组进行排序，多次反复使得数组基本有序，之后使用直接插入排序 |
| 空间复杂度 | O（1） | O（1） | O（1） |
| 比较一个元素时间复杂度 | 最好（基本有序）：O（1） 最坏（顺序相反）：O（n） | 平均：O(nlog2n) | |
| 总体时间复杂度 | O（n^2） | O(n^2) | 最好：O(n^(1/3)) 最坏：O(n^2) |
| 稳定性 | 稳定 | 稳定 | 不稳定 |
| 适用性 | 顺序存储和链式存储 | 顺序存储和链式存储 | 仅顺序存储 |
| 特点 | 基本有序时效率最高，最后一趟开始之前所有元素可能都不在最终位置上 | 组内排序使用直接插入排序 |
交换排序
| 冒泡排序 | 快速排序 | |
|---|---|---|
| 过程 | 每次找出一个最值放到队头或者队尾 | 不断地将待排序表进行划分，左边都比中间小，右边都比中间大直到待排序表基本有序为止 |
| 空间复杂度 | O(1) | 最好情况：O（log2n） 最坏情况：O（n） 平均：O（log2n） |
| 比较次数 | n(n-1)/2 | |
| 时间复杂度 | O(n^2) | O(n^2) |
| 稳定性 | 稳定 | 不稳定 |
| 特点 | 元素相同时不会进行交换保证了稳定性 | 是所有内部排序算法中平均效率最高的算法 |
选择排序
| 简单选择排序 | 堆排序 | |
|---|---|---|
| 过程 | 遍历待排序表将最小（大）的放到前面，反复该过程 | 先建立堆（大顶堆或小顶堆），输出堆顶数据后将堆底的数据放到堆顶然后向下调整。对堆进行排序则是从堆的最后一个元素开始进行排序，向上调整之后向下调整。 |
| 空间复杂度 | O(1) | O(1) |
| 比较次数 | n(n-1)/2 | 实际情况实际分析 |
| 时间复杂度 | O（n^2） | O(nlog2n)（插入元素与删除元素的时间复杂度都是） |
| 稳定性 | 不稳定 | 稳定 |
| 特点 | 调整时间与树高有关，树越高调整时间越长，堆可以视为一颗完全二叉树，采用顺序存储的方式且对于大顶堆的次大值一定能在根的下一层，取出堆顶元素之后用堆最后一个元素替换堆顶元素后向下调整，若只是对堆进行排序则应该从最后一个元素开始进行排序。 |
