哪种排序算法应该用于以下场景？

Question

给出的问题陈述是"您正在使用一个只有4 KB可用内存的嵌入式设备(ATM),并且您希望按提取的金额对2,000,000个交易的抽签历史进行排序(丢弃原始交易顺序) )".

对于这个问题陈述,据我说我们应该使用合并排序,这个排序算法有什么问题吗？

Answer 1

这就是嵌入式系统的问题。他们的工作记忆有限。

我的回答分为两部分。

1. 算法角度的最佳排序

毫无疑问，至少谈论使用冒泡排序、插入排序、选择排序是没有意义的，因为它们在内存方面和性能方面都不是很有效。

以下是一些时间和空间复杂度最差的高级排序。

快速排序，O(n n) ---- O(n log(n))

归并排序，O(n*log(n)) ---- O(n)

蒂姆排序，O(n*log(n)) ---- O(n)

堆排序，O(n*log(n)) ---- O(1)

希尔排序，O(n*log(n)^2) ---- O(1)

桶排序，O(n*n) ---- O(n)

基数排序，O(nk) ---- O(n+k)

因此，由于您需要节省内存并加快处理时间，我相信堆排序将是这里的最佳选择，因为在最坏的情况下，它也在 O(n*log(n)) 和 O(1) 时间和空间复杂度下运行。

2. 性能方面

由于高性能对于这种情况至关重要，因此您需要考虑代码优化、使用 EEPROM和扩展内存。