对数组 C 进行部分排序

我有一个如下所示的数组：

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

我只是想知道我可以使用什么方法对该数组进行部分排序，以将前三个最大的双精度数放在前面。我正在寻找最有效的方法来获取该数组中前三个最高的数字。

到目前为止我一直在使用qsort，但我只是在寻找另一种方法来做到这一点，它可能会更快。我知道qsort is O(nlogn)对于最好的情况和O(n^2)对于最坏的情况，但是有没有更有效的方法来解决这个问题？我所说的高效只是一种更快的方法，比O(nlogn).

任何帮助都会很棒

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

   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% 加一点，其余的。我们不需要进一步处理其余的，只需对最上面的组进行排序即可。