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

概述我被问到以下问题(根本不知道如何解决它) 给定一个n int的数组arr,我们需要对它进行排序.我们已经知道这个int的k被放置在原来的arr中,就像排序的数组一样(只是不知道它们中的哪一个) 他们告诉这样的排序比nlogn好 – 我没有任何线索… 任何建议？ http://en.wikipedia.org/wiki/Radix_sort 关键的事实是,您正在使用整数,并且您知道最大的键,这正是使 我被问到以下问题(根本不知道如何解决它)
给定一个n int的数组arr,我们需要对它进行排序.我们已经知道这个int的k被放置在原来的arr中,就像排序的数组一样(只是不知道它们中的哪一个)
他们告诉这样的排序比nlogn好 – 我没有任何线索…
任何建议？解决方法 http://en.wikipedia.org/wiki/Radix_sort

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

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

总结

以上是内存溢出为你收集整理的c – 如何排序比n log n快(列表中有强大的条件)？全部内容，希望文章能够帮你解决c – 如何排序比n log n快(列表中有强大的条件)？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。