问用倒置排序数组的最佳算法
EN

Stack Overflow用户

提问于 2017-03-22 16:25:26

回答 1查看 270关注 0票数 0

我正在一个处理数据的程序中工作。但是，由于我希望我的代码高效，我想要一个排序算法，它的运行时间不取决于数组的反转次数，所以我可以按升序排序。数组的顺序总是：

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

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

发布于 2020-05-11 14:09:08

由于您的数字在一个固定的范围(0，n/2-1)，您可以使用任何范围排序算法，如计数排序。请参阅排序

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/42957452

复制

相似问题

问用倒置排序数组的最佳算法EN