开发者社区 问答 正文

常用的排序算法特点和逻辑数据模型特点

常用的排序算法特点和逻辑数据模型特点

展开
收起
知与谁同 2018-07-21 09:21:39 1967 分享 版权
1 条回答
写回答
取消 提交回答
  • 常用的排序算法有插入排序,希尔排序,冒泡排序,快速排序,归并排序,堆排序还有基数排序。
    排序算法一般考虑的就是两个方面,即时间复杂度和空间复杂度。
    其中插入排序,冒泡排序是简单排序,排序的平均时间复杂度是O(n^2), 最坏的情况是O(n^2),辅助存储空间是O(1)。
    快速排序的平均时间复杂度是O(nlogn), 最坏的情况是O(n^2), 辅助存储空间是O(logn)
    归并排序的平均时间复杂度是O(nlogn), 最坏的情况是O(nlogn), 辅助存储空间是O(n)
    堆排序平均时间复杂度是O(nlogn), 最坏的情况是O(nlogn), 辅助存储空间是O(1)
    基数排序平均时间复杂度是O(d(n+rd)), 最坏的情况是O(d(n+rd)), 辅助存储空间是O(rd),其中d关键字的个数,rd是关键字的取值的个数。

    从平均性能上来而言,快速排序最佳,其所需的时间最省,但快排在最坏的情况下的时间性能不如堆排序和归并排序。而后者相比的结果是,在n较大的时候,归并排序需要的时间比堆排序省,但它需要的辅助存储空间比较多。

    从方法的稳定性来比较,基数排序是稳定的内排序,所有时间复杂度为O(n^2)的简单排序都是稳定的。然而,快速排序,归并排序,堆排序等时间性能较好的排序方法都是不稳定的。

    具体每个排序的思想,楼主可以百度一下,百度百科都有相应的词条。
    2019-07-17 22:50:15
    赞同 展开评论
问答分类:
问答地址: