对数组C进行部分排序

只需保持第一，第二，第三。

   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变大，您需要使用一种正式方法。

这不能回答您实际提出的问题，即如何进行部分排序，但这似乎是您想要的。

如果您希望部分排序，则可以使用快速排序，并且只要枢轴超出您感兴趣的范围，就可以早点返回。因此，我们的第一个枢轴分为五个，两个。忽略最后两个，而实际上只执行最后五个的子分类。但是，尽管它比quicksort更快，但它不会改变游戏规则。如果您可以在第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％加一点，其余部分。我们不需要进一步处理其余部分，只需对最上面的一组进行排序。