我正在尝试对具有以下属性的数组进行排序
它增加到一定程度然后开始减少，然后增加然后减少等等。是否有任何算法可以通过利用部分排序来以低于 nlog(n) 的复杂度对其进行排序？
数组示例 = 14,19,34,56,36,22,20,7,45,56,50,32,31,45......... 最多 n
提前致谢
任何数字序列都会向上和向下、再次向上和向下等等，除非它们已经完全排序（当然可以从向下开始）。您可以遍历序列，注意它改变方向的点，然后对序列进行合并排序（反向读取向后序列）
一般来说，复杂度是 N log N，因为我们此时不知道它是如何排序的。如果它排序得比较好，即方向变化较少，则需要较少的比较。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
