gpt4 book ai didi

algorithm - 什么是适合嵌入式系统的排序算法?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:29:14 25 4
gpt4 key购买 nike

我正在为嵌入式系统开发软件,我需要实现排序例程,但我在选择最佳解决方案时遇到了麻烦。我的要求如下:

  1. 因为这是一个内存非常有限的系统,所以空间复杂度是一个主要因素。
  2. 由于要排序的元素数量通常很少,并且排序只是偶尔发生,因此时间复杂度不一定是主要因素。
  3. 我的申请需要稳定的算法。
  4. 因为这是一个嵌入式系统,所以代码大小是一个因素。
  5. 不能保证数据最初会以接近排序的顺序排列。

我考虑过以下算法:

  • 冒泡排序(是的,虽然我不好意思说出来)
  • 侏儒排序
  • 插入排序
  • 就地归并排序(尽管在我看来这对于链表比数组更理想?)

虽然答案(针对我的具体情况)很可能是“呃,呃,这并不重要,我们只关心使用冒泡排序”,这个答案不是很有用。 一般来说,哪些排序算法对嵌入式系统有用?

最佳答案

插入排序也不错,实际运行速度快,稳定,就地。它与 gnome 排序非常相关,在实践中速度更快,但对于 gnome 排序,代码更小并且占用的辅助空间更少(不是大 O,区别在于常量)

编辑:是的,我搞砸了一点,把它们颠倒了——我可能不应该在喝咖啡之前回答问题。它之前说插入​​排序比 gnome 排序有更少的代码和空间

关于algorithm - 什么是适合嵌入式系统的排序算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7357581/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com