欢迎光临
我的个人博客网站

第 31 题:以上十种排序算法的区别有哪些?


算法分类(比较和非比较)

非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破 O(nlogn),因此称为非线性时间比较类排序

线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序

第 31 题:以上十种排序算法的区别有哪些?

排序算法评价标准

时间复杂度

时间复杂度分为:最坏时间复杂度、平均时间复杂度、最好时间复杂度。主要反应的是执行程序的次数

空间复杂度

是对一个算法在运行过程中临时占用存储空间大小的量度

稳定性

稳定性的意思是对于序列中键值(Key value)相同的元素,它们在排序前后的相对关系保持不变。对于 int 这样的基本数据类型,稳定性基本上是没有意义的,因为它的键值就是元素本身,两个元素的键值相同他们就可以被认为是相同的。但对于复杂的数据类型,数据的键值相同,数据不一定相同,比如一个 Student 类,包括 Name 和 Score 两个属性,以 Score 为键值排序,这时候键值相同元素间的相对关系就有意义了。
总结就是经过排序之后,能使值相同的数据保持原顺序中的相对位置不变

内排序

所有排序操作都在内存中完成,适用于数据规模不是特别大的情况

外排序

由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行

各排序算法总结

第 31 题:以上十种排序算法的区别有哪些?

名词解释:

n: 数据规模(即序列的长度)

k: “桶”的个数

In-place: 占用常数内存,不占用额外内存

Out-place: 占用额外内存

参考资料:
值得收藏的十大经典排序算法

文章的内容/灵感都从下方内容中借鉴

赞(0) 打赏
未经允许不得转载:张拓的天空 » 第 31 题:以上十种排序算法的区别有哪些?
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏