赞
踩
先来个表格总结直观展示下:
算法种类 | 时间复杂度 | 空间复 杂度 | 稳定性 | |||
最好情况 | 平均情况 | 最坏情况 | ||||
插入排序 | 直接插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
折半插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 | |
希尔排序 | O(n^1.3) | O(nlogn) | O(n^2) | O(1) | 不稳定 | |
交换排序 | 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | 不稳定 | |
选择排序 | 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | |
归并排序 | 二路归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | 稳定 |
下面详细说明一下:
1.时间复杂度:(不包括基数排序)
平均情况下,快速排序、希尔排序(和增量有关,n在特定范围内为O(n^1.3))、归并排序、堆排序时间复杂度为O(nlogn),其他均为O(n^2);
最坏情况下,快速排序、希尔排序为O(n^2),其他均和平均情况下相同;
最好情况下,直接插入排序、折半插入排序、冒泡排序时间复杂度为O(n)(初始序列有序)。
2.空间复杂度:
快速排序O(logn),2路归并排序O(n),基数排序O(r),其他都是O(1)。
3.稳定性:
希尔排序、快速排序、简单选择排序、堆排序不稳定,其他都是稳定的。
4.其他:
经过一趟排序,能保证一个元素到达最终位置:交换排序(冒泡排序、快速排序)、选择排序(简单选择排序、堆排序)。
5.例题:
若输入数据存储在带头结点的双向循环链表中,下面排序算法是否仍然适用?
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。