排序算法(3)-特征记录

最小内存写

选择排序内存写只需要O(n),而圈排序是最小的,圈排序每个元素要么写0次(如果已经在对的位置),要么写一次,所以最多写 n 次,最少写 0 次

快速排序最差情况

以下三种将会是快速排序的最差情况(其实就是每次的基准值(pivot)都取到最大值或者最小值)

1.正序排列好了

2.逆序排列好了

3.所有元素都相同(即为1,2的特殊情况)

基于比较的排序算法的下界

最少需要 nlogn 次比较

数字范围 0 到 n^2 通过基数排序可以达到线性时间

快速排序更适合数组,归并排序更适合链表

对于数组,快速排序是 in-place 排序,无需额外空间,而归并排序需要额外的 n 空间

大多数快速排序设计需要用到随机访问,只有数组支持

快速排序算法是缓存友好算法,局部访问特点可以增加cpu缓存的使用

对于链表来说,插入删除都只是指针的操作,无需额外的开销

上一篇: 排序算法(2)-c实现
下一篇: 动态规划
作者邮箱: 203328517@qq.com