部分排序数组C.

Question

我有一个看起来像这样的数组:

int array[] = {4.53, 3.65, 7.43, 9.54, 0.72, 0.0}

我只是想知道我可以用什么方法对这个数组进行部分排序,将前三个最大的双打带到前面.我正在寻找最有效的方法来获得这个数组中前三个最高的数字.

到目前为止,我一直在使用qsort,但我只是在寻找另一种方法,可以更快.我知道这qsort是O(nlogn)最好的情况和O(n^2)最坏的情况,但有没有更有效的方法来实现这个问题？我所说的高效是一种更快捷的方式,比这更好O(nlogn).

任何帮助都会很棒

Answer 1

只需保持第一、第二、第三即可。

   first =  array[0];
   second = array[1];
   third = array[2];

   /* scratch sort for three elements */
   if(first < second)
     swap(first, second);
  if(first < third)
     swap(first, third);
  if(second < third)
     swap(second, third);

  /* now go through, bubbling up if we have a hit */ 
  for(i=3;i<N;i++)
  {
      if(third < array[i])
      {
         third = array[i];
         if(second < third)
         {
            swap(second, third);
            if(first < second)
              swap(first, second);
         }
      }
  }     

我不会尝试扩大到 k = 4。我认为三个是关于硬编码它的限制。随着 k 变大，您需要转向正式方法。

这并没有回答您实际提出的问题，即如何部分排序，但它似乎是您想要的。

如果您希望部分排序，您可以使用快速排序，并且只需在枢轴超出您感兴趣的界限时提前返回即可。所以我们的第一个枢轴分为五、二。忽略最后两个，只实际执行最后五个的子排序。虽然它比快速排序更快，但它不会改变游戏规则。如果您可以获得第 k 个项目的保守上限（例如，最小值和平均值之间最多始终为 25%），您可以快速消除大部分数据。如果你弄错了，那只是再过一两遍。

使用快速排序方法

  int sortfirstk_r(int *array, int N, int k)
  {
     int pivot = 0;
     int j = n -1;
     int i = 1;

     while(i <= j)
     {
        if(array[pivot] < array[i])
          swap(array[i], array[j--])
        else
          i++;

     }
     sortfirstk_r(array, i, k < i ? k : i);
     if(i < k)
       sortfirstk_r(array +i, N -i, k - i); 

  }

（未经测试，稍微棘手的排序逻辑可能存在错误）。

然而，我们天真地使用第一个元素作为枢轴。如果我们对一个大型数据集进行排序，并且它具有正态分布，并且我们想要前 1%，则 z 得分为 2.326。采取更多一点以允许我们出现一些采样误差，我们将第一遍的枢轴设置为高于平均值 2.3 个标准差。然后我们将分布分成两组，前 1% 加一点，其余的。我们不需要进一步处理其余的，只需对最上面的组进行排序即可。