有效的函数排序
我正在为 TI-Nspire 编写一个函数，所以我无法使用函数内部的内置函数。在不修改列表本身的情况下对数字列表进行排序的最普遍有效的算法是什么？ （递归和列表分割是公平的游戏，数学的一般用途也是如此。）
I'm programming a function for a TI-Nspire, so I can't use the builtins from inside a function. What is the most generally efficient algorithm for sorting a list of numbers without modifying the list itself? (recursion and list-splitting are fair game, as is general use of math.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
归并排序直接、简单、高效且稳定：拆分列表、递归排序并合并结果。
更具体地说，归并排序的时间复杂度为 O(N log N)，这是渐近最优的。此外，在实践中（将两种算法修改为使用特殊用途的排序对短子列表进行排序），合并排序可以成为 C/C++ 标准库中使用的修改后的快速排序的有力竞争对手。
编辑：与快速排序和插入排序等就地排序不同，合并排序需要辅助内存，并且最简单地通过复制而不是交换来实现。
Mergesort is straightforward, simple, efficient, and stable: split the list, sort recursively, and merge the results.
To be more specific, mergesort takes O(N log N), which is asymptotically optimal. Also, in practice (with both algorithms modified to sort short sublists with a special-purpose sort), mergesort can be a close competitor to the modified quicksort used in the C/C++ standard libraries.
Edit: unlike in-place sorts like quicksort and insertion sort, mergesort requires auxiliary memory, and is simplest to implement by copying rather than swapping.
Timsort 用于 python 和 java SE 7。它结合了归并排序和插入排序的优点。插入排序的时间复杂度为 O(n^2)，但对于较小的数字列表，它比合并排序更快！
因此，您可以将其用作通用排序算法，如此处所述
Timsort is used in python and java SE 7. It takes the best of merge sort and insertion sort. Insertion sort is O(n^2) but with small lists of numbers it is faster than merge sort!
So you can use this as a generic sorting algorithm as stated here