按升序排序降序的最佳排序算法是什么？

Question

当有一个从一开始就按降序存储数据的数组时，例如5, 4, 3, 2, 1排序算法(快速排序，合并排序.)是按升序排序这个数组的最佳方法吗？为什么？

Answer 1

自然合并排序或TimSort的变化(类似于自然合并排序)，将扫描增加或减少的序列，当遇到它们时会逆转减少的序列。如果整个数组是递减序列，那么当整个数组反转时，初始扫描将对整个数组进行排序。

Answer 2

在经典排序算法中，当输入(几乎)按降序排序时，堆排序将做得很好，因为最大堆构造阶段将涉及(几乎)无交换(而大多数交换将发生在输入已经按升序排序时)。

请注意，排序的速度取决于许多因素(如数据类型、比较功能、并行计算的可用性、内存组织、...etc)。另见堆排序与其他排序的比较。

Answer 3

最好的方法是避免排序，只需反向序列。

它是一种简单、快速的线性算法。