1

快速排序是一种众所周知的算法，但破译 C 很复杂（对我来说）。内联版本加快了很多http://www.corpit.ru/mjt/qsort.html ‎。

但是，它可以很容易地转换为输出N元素数组的前m个样本吗？

那么在对前m个样本进行排序后简单地停止排序的调用？我怀疑不是因为它对块进行快速排序，然后将块拼接在一起以获得最终输出。如果我将初始快速排序块的大小设置为m大小，那么我处于一个糟糕的位置，没有利用 qsort 中的聪明东西。

提前致谢

格罗格

4

3 回答 3

2

正如@R.. 建议的那样，使用Quickselect来获取第一个k元素，然后对它们进行排序。运行时间是 O(N) 来获取元素，并且 O(k log k) 来对它们进行排序。

然而，经验证据表明，如果要选择的项目数 (k) 小于元素总数 (N) 的 1%，那么使用二叉堆将比快速选择后排序更快。当我必须从 200 万个列表中选择 200 个项目时，堆选择算法要快得多。有关详细信息，请参阅链接的博客。

于 2013-11-14T20:08:03.637 回答
1

（重述问题：给定N个项目，找出其中最大的m个。）

一个简单的解决方案是优先队列。将所有N个项目送入队列，然后从列表中弹出前m个项目。输入N个项目将是 O( N log m )。每个单独的弹出操作都是O(log m)，因此删除前n 个项目将是O(m log m)。

就地算法应该相对简单。我们是一个包含N个元素的数组。数组中的每个位置都有编号，编号介于 1 和 N（含）之间。对于数组中的每个位置，取其位置并除以 2（必要时向下舍入），并将该位置定义为其父级。除了位置 1 之外，每个位置都将有一个父位置。大多数职位（不是全部）都会有两个孩子。例如：

node position:  1 2 3 4 5 6 7 8 9 ...
parent:         - 1 1 2 2 3 3 4 4 ...

我们希望交换节点，直到每个节点的值小于（或等于）其父节点。这将保证最大值位于位置 1。将数组重新排序以具有这种形式非常容易。只需从位置 1 到 N 依次遍历节点，并在其上调用此函数一次：

void fixup_position(int x) {
   if(x==1)
      return;
   int parent_position = (x/2) ; // rounding-down where necessary
   if (data[x] > data[parent_position]) {
      swap(data[x], data[parent_position]);
      check_position(parent_position);  // note this recursive call
   }
}


for(x = 1; x <= N; ++x) {
    fixup_position(x);
}

（是的，我正在计算位置为 1 的数组，而不是 0！在实际实现时您必须考虑到这一点。但这更容易理解优先级队列的逻辑。）

递归调用的平均次数（因此swap是 s）是一个常数（如果我没记错的话，是 2）。所以这会很快，即使是大型数据集。

值得花一点时间来理解为什么这是正确的。就在调用 之前fixup_position(x)，直到（但不包括 x）的每个位置都处于“正确”状态。“正确”是指它们没有完全排序，但每个节点都小于其父节点。引入了一个新值（在位置 x），并将在队列中“冒泡”。您可能会担心这会使其他职位及其父子关系无效，但不会。一次只有一个节点处于无效状态，并且它会一直冒泡到它应有的位置。

这是 O(N) 步骤，它将您的数组重新排列到优先级队列中。

删除前n项。经过上面的方法，很明显最大的数字会在位置1，但是第二大，第三大，等等呢？我们所做的是从位置 1 一次弹出一个值，然后重新排列数据，以便将下一个最大值移到位置 1。这比fixup_position.

for(int y = 1; y <= m; ++y) {
   print the number in position 1 .... it's the next biggest number
   data[1]  =  -10000000000000; // a number smaller than all your data
   fixup_the_other_way(1);  // yes, this is '1', not 'y' !
}

哪里fixup_the_other_way是：

void fixup_the_other_way(int x) {
    int child1 = 2*x;
    int child2 = 2*x+1;
    if(child1 > N)  // doesn't have any children, we're done here
        return;
    if(child2 > N) { // has one child, at position[child1]
       swap(data[x], data[child1]);
       fixup_the_other_way(child1);
       return;
    }
    // otherwise, two children, we must identify the biggest child
    int position_of_largest_child = (data[child1]>data[child2]) ? child1 : child2;
    swap(data[x], data[position_of_largest_child]);
    fixup_the_other_way(position_of_largest_child);
    return;
}

这意味着我们打印出最大的剩余项目，然后用一个非常小的数字替换它，并强制它“冒泡”到我们数据结构的底部。

于 2013-11-14T19:44:57.410 回答
0

There are two ways to solve the problem efficiently:-

1.> Priority Queues

Algorithm: -

  1. Insert first n items into Priority Queue with max heap

  2. Peek on max element to check if current element compared is less than that

  3. if less delete top element and add current

  4. Do steps for all N-n elements.

2.> Your Problem can be reduced to selection problem : -

Algorithm

  1. Do randomized selection for nth element on N elements (O(N) in average case)

  2. sort first n elements using qsort or any other efficient sorting algorithm

Using both algorithms you would get average case O(N) performance

于 2013-11-14T18:07:05.167 回答