排序知识点总结（待更新.....）
排序的基本概念
概念
- 排序:将各元素按照关键字的增序或者降序进行排列
评估标准
- 稳定性：稳定性指的是相同的关键字在进行排列之后，相对位置未发生改变。
- 时间复杂度和空间复杂度
分类
- 外部排序：外部排序是数据集的麻烦，无法全部加载到内存中，需要借助外部存储进行排序的算法。外部排序通常因此需要进行多次读写外部存储，IO 成本比较高。常见的外部排序算法有多路归并排序、置换-选择排序等。
- 内部排序：内部排序是在内存中完成的排序算法，假设整个数据集都可以加载到内存中。常见的内部排序算法有快速排序、堆排序、归并排序等。
插入排序
直接插入排序
1 | 插入排序是将一个待排序的记录按其关键字的大小插入到前面已经排列好的子序列中去，直到全部的关键字都插入完成。 |
- 最好时间复杂度是O(n),序列是顺序排放的。
- 最坏时间复杂度是O(nxn)，序列是逆序排放的。
- 平均时间复杂度是O(nxn)。
- 空间复杂度是O(1)
- 直接插入排序是稳定算法。
- 注：对链表进行插入排序的话，同样时间复杂度是O(nxn)，因为比较的次数仍然是O(nxn）的量级。链表的话，移动元素确实是变少了，只需要修改指针。
折半插入排序
- 先使用折半查找找到待插入的位置
- 再移动元素，当low>high时，将[low,i-1]的元素全部右移，将空出来的位置用来存放哨兵中待插入的元素。
- 折半插入排序是稳定的排序算法。
- 时间复杂度仍然是O(nxn)。
希尔排序（缩小增量排序)
- 每次将增量缩小一半，直到增量变为1。
- 最后使用直接插入排序对序列进行最后一次排序。
- 空间复杂度是O(1)
- 目前无法使用数学手段证明这个算法的确切的时间复杂度
- 最坏时间复杂度是O(nxn)
- 仅适用于顺序表，不适合链表。
- 注意：希尔排序不是稳定的排序算法。
冒泡排序
1 | 冒泡排序是从后往前，如果这个元素比前面的元素，交换这两个元素的位置，每一趟冒泡排序都将待排序的元素中最小的元素冒泡到这些剩余元素的最前面。 |
- 空间复杂度是O(1)
- 最好时间复杂度是O(n)
- 最坏时间复杂度是O(nxn)
- 冒泡排序是稳定的排序算法。
- 冒牌排序同时适用于顺序表（从后往前）和链表（从头到尾）
题目总结
8.2.4
解析：
解析：对于希尔排序的每一趟的结果都是:按增量进行分组后，分组内应该是有序的序列，所以本题第一次的增量是5，第二次的增量是3。
评论