前言
本篇文章笔者将会对排序算法的所有时间复杂度和稳定性进行分析.
一、相关复杂度
● 简单选择排序
首先,选择排序的效率是不高的 , 时间复杂度考虑的是最坏情况 , 那么对于选择排序来说, 最坏情况下需要进行 n-1 次选择和交换操作 , 那么对于 n 个数来说就是 N^2.
但选择排序是不额外开辟空间的.
故:
○ 时间复杂度 : O(N^2) .
○ 空间复杂度 : O(1) .
● 冒泡排序
考虑最坏情况下, 一个数与每个数都要交换 , 才可达有序 , 则 : n 个数 就会进行 n-1 次交换.
故:
○ 时间复杂度 : O(N^2) .
○ 空间复杂度 : O(1) .
● 堆排序
堆排涉及向下调整算法 , 每次交换后就要与末尾元素交换进行堆的调整 , 最坏情况下 , 要调整 log N 层 , 其中共 n 个数 .
故:
○ 时间复杂度 : O(N * log N) .
○ 空间复杂度 : O(1) .
● 直接插入排序
该排序的思想是 [0 , end] 有序 ,end + 1 位置插入 . 那么最坏情况就是该序列逆序时 , 要排升序 , 则 n 个数要进行 n - 1 次插入 . 那么最好的情况就是有序时 , 将 end + 1位置插入 , 只需遍历一遍就可以达到效果 .
故:
○ 时间复杂度最坏情况 : O(N ^ 2) .
○ 时间复杂度最好情况 : O(N) .
○ 时间复杂度 : 介于 O(N) ~ O(N ^ 2) 之间.
○ 空间复杂度 : O(1) .
● 希尔排序
本排序需要重点记忆 !
○ 时间复杂度 : O(N ^ 1.3 )
○ 空间复杂度 : O(1) .
● 快速排序
快排每次取中 , 递归左边,右边. 会涉及递归的过程 , N 个数会递归 log N 层.
但最坏情况 , 当 key 选到原序列的最大或最小时 , 导致划分一边子序列为空
一边子序列为 n - 1 , 那么递归深度就会 n - 1 层 .
故:
○ 时间复杂度最坏情况 : O(N ^ 2) .
○ 时间复杂度最好情况 : O(N*log N) .
○ 时间复杂度 : 为了更好效率,一般追求 O(N*logN).
○ 空间复杂度 : O(log N) .
重点理解快排空间复杂度
为什么是 log N 呢 ? 首先 ,快排涉及递归 , 递归的深度是 log N , 二分的递归情况下就会多开辟 log N 个空间.
● 归并排序
归并排序中要借助第三方数组 , 并且左右有序才会归并. 所以要涉及分割左右子序列.
故:
○ 时间复杂度 : O(N ^ log N)
○ 空间复杂度 : O(N) .
● 计数排序
计数排序也是借助第三方数组 , 但该排序只需遍历一遍原数组就可以达到排序的效果.
故:
○ 时间复杂度 : O(N)
○ 空间复杂度 : O(N) .
二、相关稳定性
稳定性的分析可结合相关排序的思想理解 !
◎ 稳定性介绍
稳定性指 : 排序前后两个相等的数的相对位置 .
○ 相对位置改变 , 即 : 该排序不稳定.
○ 相对位置没有改变 , 即 : 该排序稳定.
● 简单选择排序
重点理解 !
思想: 第一次在原始序列中选择一个最小的和最左边的交换 , 依次选择 ,直至有序.
特殊情况:
以上这种情况 , 虽然保证了 1 的稳定性 , 但是对于 3 来说 ,其相对位置是发生改变的.
故: 简单排序是 不稳定 的.
● 冒泡排序
思想 : 相邻两个比较进行交换 , 相等时就不交换了 . 所以 ,相等的数的相对位置不会发生变化.
故: 冒泡排序是 稳定 的.
● 堆排序
思想 : 堆顶元素和堆最后一个元素要发生交换 , 交换以后还要进行堆调整. 这其中一定会发生相对位置的变化.
故: 堆排序是 不稳定 的.
● 直接插入排序
思想 : [ 0 , end ] 有序 , end + 1 位置插入 , 当 end + 1 位置大于有序中的某一位置时停止 --end ,进行插入 , 因为该排序不涉及交换 , 所以相等数的相对位置不会发生改变.
故: 直接插入排序是 稳定 的.
● 希尔排序
思想 : 分 gap 组 , 每组进行插入排序的思想 , 虽然也不涉及交换 , 但分为了不同组别在不同组的插入中会有相等数相对位置变化的情况 .
故: 希尔排序是 不稳定 的.
● 快速排序
思想 : 选 key , 左边找大, 右边找小 , 找到了交换 , 当左边做 key 时右边先走 , 那么相遇位置一定比 key 小 ,就要和 key 位置交换.
这样的场景 6 的相对位置发生改变 .
故: 快速排序是 不稳定 的.
● 归并排序
思想 : 左右有序开始归并 , 两个区间小的尾插到新的空间中 , 等于时两个顺序是不变的.
故: 归并排序是 稳定 的.
三、表格总结
蓝色部分为重点排序 , 红色部分需要特别注意 !!!
总结
以上是排序部分的所有内容 , 后续内容请持续关注 ~