c – 如何排序比n log n快(列表中有强大的条件)？

发布时间：2020-12-16 06:03:09 所属栏目：百科来源：网络整理

导读：我被问到以下问题(根本不知道如何解决它) 给定一个n int的数组arr,我们需要对它进行排序.我们已经知道这个int的k被放置在原来的arr中,就像排序的数组一样(只是不知道它们中的哪一个) 他们告诉这样的排序比nlogn好 – 我没有任何线索… 任何建议？解决方法 h

我被问到以下问题(根本不知道如何解决它)
给定一个n int的数组arr,我们需要对它进行排序.我们已经知道这个int的k被放置在原来的arr中,就像排序的数组一样(只是不知道它们中的哪一个)
他们告诉这样的排序比nlogn好 – 我没有任何线索…
任何建议？

http://en.wikipedia.org/wiki/Radix_sort

关键的事实是,您正在使用整数,并且您知道最大的键,这正是使用基数排序及其复杂度是线性的.

也是第二种方法,如果他们已经被排序,你可以使用一些版本的shell排序与序列,将产生最好的结果

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!