排序总结

排序总结 插入排序

直接插入排序 折半排序 希尔排序
过程 遍历将元素插入前面的有序队列之中 在直接插入的基础上改进:通过折半查找找出要插入的位置 通过设定步长对步长内的数组进行排序,多次反复使得数组基本有序,之后使用直接插入排序
空间复杂度 O(1) O(1) O(1)
比较一个元素时间复杂度 最好(基本有序):O(1)
最坏(顺序相反):O(n)
平均:O(nlog2n)
总体时间复杂度 O(n^2) O(n^2) 最好:O(n^(1/3))
最坏:O(n^2)
稳定性 稳定 稳定 不稳定
适用性 顺序存储和链式存储 顺序存储和链式存储 仅顺序存储
特点 基本有序时效率最高,最后一趟开始之前所有元素可能都不在最终位置上 组内排序使用直接插入排序
交换排序
冒泡排序 快速排序
过程 每次找出一个最值放到队头或者队尾 不断地将待排序表进行划分,左边都比中间小,右边都比中间大直到待排序表基本有序为止
空间复杂度 O(1) 最好情况:O(log2n)
最坏情况:O(n)
平均:O(log2n)
比较次数 n(n-1)/2
时间复杂度 O(n^2) O(n^2)
稳定性 稳定 不稳定
特点 元素相同时不会进行交换保证了稳定性 是所有内部排序算法中平均效率最高的算法
选择排序
简单选择排序 堆排序
过程 遍历待排序表将最小(大)的放到前面,反复该过程 先建立堆(大顶堆或小顶堆),输出堆顶数据后将堆底的数据放到堆顶然后向下调整。对堆进行排序则是从堆的最后一个元素开始进行排序,向上调整之后向下调整。
空间复杂度 O(1) O(1)
比较次数 n(n-1)/2 实际情况实际分析
时间复杂度 O(n^2) O(nlog2n)(插入元素与删除元素的时间复杂度都是)
稳定性 不稳定 稳定
特点 调整时间与树高有关,树越高调整时间越长,堆可以视为一颗完全二叉树,采用顺序存储的方式且对于大顶堆的次大值一定能在根的下一层,取出堆顶元素之后用堆最后一个元素替换堆顶元素后向下调整,若只是对堆进行排序则应该从最后一个元素开始进行排序。

    推荐阅读