堆排序
时间复杂度：Ο(nlogn)
空间复杂度：一个辅助空间
稳定性：不稳定
排序（升序用大根堆，降序就用小根堆）：
- 将待排序数组A[0...n]构造成大根堆，此时，整个数组的最大值就是堆结构的顶端；
- 将顶端的数（A[0]）与末尾的数（A[n]）交换，此时，末尾的数为最大值；
- 剩余元素构成待排序数组A[0...n-1]，重复上述步骤，直至排序完成。
补充：
每个结点的值都大于其左、右孩子结点的值，称之为大根堆；每个结点的值都小于其左、右孩子结点的值，称之为小根堆。
优缺点：
优点：
- 堆排序效率相对稳定，不像快排在最坏情况下时间复杂度会变成O(n^2)
缺点：
- 堆排序比较和交换次数比快速排序多，所以平均而言比快速排序慢；
使用场景：
- 获取最大/小的元素，topK之类。如果你要在很多元素中找很少几个top K的元素，或者在一个巨大的数据流里找到top K，堆排序更适合。
- 优先队列。需要在一组不停更新的数据中不停地找最大/小元素
快速排序
时间复杂度：O(nlogn)，有序时最差O(n^2)
空间复杂度：O(logn)~O(n) (递归时使用的栈空间)
稳定性：不稳定
排序：
- 从数列中选择一个基准元素；
- 将比基准元素大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复上述步骤，直到各区间只有一个数。
补充：
元素的移动：1. 挖坑法；2. 指针交换法
优缺点：
优点：
- 快速排序通常明显比其他 Ο (n log n) 算法更快
缺点：
- 排序效率不稳定，数列有序时效率最差
归并排序
时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定性：稳定
排序：
归并排序的基本思想是基于合并操作，即合并两个已经有序的序列是容易的，不论这两个序列是顺序存储还是链式存储，合并操作都可以在O(m+n)时间内完成（假设两个有序表的长度为m和n）。
- 划分。划分数列为相等（或大致相等）的两部分；
- 治理。当划分后的子数列长度大于1时，递归排序子数列；当子数列长度等于1时，则已经成为有序数列；
- 组合。将两个有序子数列合并为一个有序数列。
优缺点：
优点：
- 归并排序是最常用的外部排序方法（当待排序的记录放在外存上，内存装不下全部数据时，归并排序仍然适用，当然归并排序同样适用于内部排序...）
缺点：
- 辅助空间大O(n)
- 实用性较差
直接插入排序
时间复杂度：最好情况（基本有序)：O(n) 、平均情况：O(n^2) 、最坏情况：O(n^2)
空间复杂度：一个辅助空间
稳定性：稳定
排序：
把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
优缺点：
优点：
- 数列接近有序时时间复杂度接近O(n)
缺点：
- 移动元素的次数比较多
使用场景：
- 当数组基本有序的情况下适合使用直接插入排序和冒泡排序，它们在基本有序的情况下排序的时间复杂度接近O(n)
折半插入排序
时间复杂度：最好情况（基本有序)：O(n) 、平均情况：O(n^2) 、最坏情况：O(n^2)
空间复杂度：一个辅助空间
稳定性：稳定
排序：
直接插入排序确认插入位置是通过在有序序列中逐个比较得到的。既然是有序序列中确认位置，则可以通过二分法来确认插入位置。即通过折半查找的方式确认插入位置。
折半插入排序仅减少了元素的比较次数，但是没有减少元素的移动次数，时间复杂度O(n^2)
希尔排序
时间复杂度：比直接插入排序要高，与增量序列的选取密切相关。
空间复杂度：一个辅助空间
稳定性：不稳定
排序：
- 确认一个增量序列t1, t2, t3, ... , tk。其中序列递减，且tk=1；
- 按照增量ti，将待排序列分割成ti个子序列（例如增量为3时，（0,3,6）、(1,4,7)、(2,5,8)分别为一组）；
- 分别对每个子序列进行直接插入排序；
- 取下一个增量t(i+1)，重复2/3步操作；
- 直到当增量tk=1时，所有序列作为一个序列来处理，完成排序。
补充：
希尔排序又称缩小增量排序。属于插入类排序，是对直接插入排序的改进，在时间效率上有较大改进。
希尔排序优化出发点：
- 在序列基本有序时，直接插入排序时间复杂度可接近O(n)。由此可知，在序列基本有序时，直接插入排序的效率可大大提高；
- 直接插入排序方法简单，在n值较小时效率较高
网友评论