我被问到以下问题(根本不知道如何解决它)
给定一个n int的数组arr,我们需要对它进行排序.我们已经知道这个int的k被放置在原来的arr中,就像排序的数组一样(只是不知道它们中的哪一个)
他们告诉这样的排序比nlogn好 – 我没有任何线索…
任何建议？
给定一个n int的数组arr,我们需要对它进行排序.我们已经知道这个int的k被放置在原来的arr中,就像排序的数组一样(只是不知道它们中的哪一个)
他们告诉这样的排序比nlogn好 – 我没有任何线索…
任何建议？
解决方法
http://en.wikipedia.org/wiki/Radix_sort
关键的事实是,您正在使用整数,并且您知道最大的键,这正是使用基数排序及其复杂度是线性的.
也是第二种方法,如果他们已经被排序,你可以使用一些版本的shell排序与序列,将产生最好的结果
