排序总结
插入排序
| 间接插入排序 | 折半排序 | 希尔排序 | |
|---|---|---|---|
| 过程 | 遍历将元素插入后面的有序队列之中 | 在直接插入的根底上改良：通过折半查找找出要插入的地位 | 通过设定步长对步长内的数组进行排序，屡次重复使得数组根本有序，之后应用间接插入排序 |
| 空间复杂度 | 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)（插入元素与删除元素的工夫复杂度都是） |
| 稳定性 | 不稳固 | 稳固 |
| 特点 | 调整工夫与树高无关，树越高调整工夫越长，堆能够视为一颗齐全二叉树，采纳顺序存储的形式且对于大顶堆的次大值肯定能在根的下一层，取出堆顶元素之后用堆最初一个元素替换堆顶元素后向下调整，若只是对堆进行排序则应该从最初一个元素开始进行排序。 |