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

Question

当有一个数组从一开始就按降序存储数据时，比如5, 4, 3, 2, 1哪种排序算法（快速排序、归并排序...）是对这个数组进行升序排序的最佳方式？为什么？

标签： algorithmsorting

Answer 1

自然归并排序或 TimSort 的变体（类似于自然归并排序）将扫描递增或递减序列，并在遇到递减序列时反转它们。如果整个数组是一个递减序列，那么初始扫描将在反转数组时对整个数组进行排序。