各种排序算法的稳定性和时间复杂度小结.pdf
版权申诉
126 浏览量
2023-05-29
12:37:35
上传
评论
收藏 245KB PDF 举报
各种排序算法的稳定性和时间复杂度小结
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，
冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
冒泡法：
这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：
复杂度为 O(n*n)。当数据为正序，将不会有交换。复杂度为 O(0)。
直接插入排序：O(n*n)
选择排序：O(n*n)
快速排序：平均时间复杂度 log2(n)*n，所有部排序方法中最高好的，大多数情况下总是最
好的。
归并排序：log2(n)*n
堆排序：log2(n)*n
希尔排序：算法的复杂度为 n 的 1.2 次幂
关于快速排序分析
这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：
首先我们考虑最理想的情况
1.数组的大小是 2 的幂，这样分下去始终可以被 2 整除。假设为 2 的 k 次方，即 k=log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环 n 次，第二层循环 2*(n/2)......
所以共有 n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以算法复杂度为 O(log2(n)*n)
1 / 5
资源评论
