arrays - 用反转对数组进行排序的最佳算法

Question

我正在一个处理数据的程序中工作。但是，因为我希望我的代码高效，所以我想要一个排序算法，它的运行时间不依赖于数组具有的反转次数，因此我可以按升序对其进行排序。数组的顺序总是：

• n = 数组的大小

• 列表 = (1,2,3,...,(n/2 -1), (n/2),(n/2 + 1),...3,2,1

我知道数组的反转总数等于：

• (n/2 -1) + (n/2 -2) + (n/2 - 3) +...+ 1

我认为这是一个对称数组的很多反转，因为我知道数组的顺序总是这样，我想要一个算法在 O(n) 时间内对它们进行排序。我知道插入排序的复杂性取决于数组的反转次数，但我不确定数组的反转次数取决于 n

Answer 1

由于您的数字在固定范围内 (0, n/2-1)，您可以使用任何范围排序算法，例如计数排序。请参见Non-comparison_sorts