相关疑难解决方法(0)

我最近被问到这个面试问题:

您将获得一个几乎已排序的数组,因为每个N元素可能被错放的k位置不超过正确排序顺序的位置.找到一种节省空间和时间的算法来对数组进行排序.

我有一个O(N log k)解决方案如下.

让我们表示arr[0..n)从索引0(包括)到N(不包括)的数组元素.

• 分类 arr[0..2k)
  • 现在我们知道arr[0..k)它们处于最终的排序位置......
  • ......但arr[k..2k)可能仍然被错放了k!
• 分类 arr[k..3k)
  • 现在我们知道arr[k..2k)它们处于最终的排序位置......
  • ......但arr[2k..3k)可能仍然被错放了k
• 分类 arr[2k..4k)
• ....
• 直到你排序arr[ik..N),然后你就完成了!
  • 如果2k剩下的元素少于其他元素,那么最后一步可能比其他步骤便宜

在每个步骤中,您对大多数2k元素进行排序,在每个步骤O(k log k)结束时将至少k元素放在最终排序位置.有O(N/k)步骤,所以整体复杂性O(N log k).

我的问题是:

• 是O(N log k)最佳的？这可以改进吗？
• 你可以在没有(部分)重新排序相同元素的情况下做到这一点吗？

我正在尝试qsort使用自定义比较函数调用Cython,但我不明白如何传递函数引用.首先,我有一个结构:

cdef struct Pair:
    int i,j
    float h

比较功能按以下方式排序h:

cdef int compare(const_void *a, const_void *b):
    cdef float v = ((<Pair*>a)).h-((<Pair*>b)).h
    if v < 0: return -1
    if v > 0: return 1
    return 0

这是我遇到麻烦的部分:

    cdef Pair[5] pa
    for i in range(5):
        pa[i].i = i;
        pa[i].j = i*2;
        pa[i].h = i*.5;
    qsort(pa,5,sizeof(Pair),compare)

最后一行不会编译并生成此错误,我认为这与我无法弄清楚如何compare作为参考传递的事实有关qsort:

Cannot assign type 'int (const_void *, const_void *)' to 'int (*)(const_void *, const_void *) nogil'