部分排序数组 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

如果我们要找出三个最大的数字，那么我们可以运行 findMax 方法三次，一旦找到最大值，用数组中的最大值替换适当的索引 (1, 2 or 3) .通过这种方式，我们将 3 数组开头的最大元素留给您 c * O(n) 时间复杂度。

注意：我使用了你必须找到前三个最大双倍的事实

double findMax(double arr[i], double prevMax){
    double maximum = -100000000000;
    for(int i = 0; i < arr.length; i++){
        if(arr[i] < prevMax)
        maximum = max(arr[i], maximum);
    }
    return maximum;
 }

Answer 2

我建议基数排序是这种情况下最有效的排序方法，复杂度为 O(n)。您甚至可以稍微更改它以在找到三个最大数字时停止。你可以找到-理解基数简称： https://www.cs.usfca.edu/~galles/visualization/RadixSort.html

Answer 3

对于您的特定问题，最快的方法是执行类似于以下的操作，因为您只需要三个元素：（使用优先级队列或不同的数据结构可能会更快，但速度不会很明显)

#include"stdio.h"
void moveThreeMaxToFront(double * arr, int length);
void moveMaxToFront(double*arr, int length);
int main() {
  int i;
  double meh[]={ 5,3,1,7,2,9,11};
  moveThreeMaxToFront(meh, 7);
  for(i=0; i<7; i++)
    printf("%f \n", meh[i]);
}
void moveThreeMaxToFront(double * arr, int length) {
  for(int i=0; i<3; i++)
    moveMaxToFront(arr++, length-i);
}
void moveMaxToFront(double* arr, int length) {
  int i;
  for(i=1; i<length; i++) {
    if(arr[i]>arr[0]) {
      double tmp=arr[i];
      arr[i]=arr[0];
      arr[0]=tmp;
    }
  }
}

但是，如果 k 变得非常大以实现 Quickselect 或使用 partial_sort 方法，我认为它可以实现 quickselect，这可能会更快。然而，给定案例的 quickselect 算法的平均常数约为 3.4-4.4，略大于上述常数 (3)。另请注意，quickselect 的平均运行时间为 O(n)。这个运行时间可以使用 3 的中位数来保证，但不建议这样做，因为它会显着增加平均常数。 Intro-select 正确处理了这个问题，以防止 quickselect 的最坏情况，同时保留其平均情况。

Answer 4

简单保持第一、第二、第三。

   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 变大，您需要转向正式方法。

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

如果您希望部分排序，您可以使用快速排序，并且只需 return 在枢轴超过您感兴趣的界限的早期就可以了。所以我们的第一个支点分为五个，两个。忽略最后两个，实际上只做最后五个的子排序。但是虽然它比快速排序更快，但它不会改变游戏规则。如果您可以获得第 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% 加一点，其余的。剩下的我们不用再处理了，直接对top组进行排序即可。

部分排序数组 C

Partially sorting an array C

c

arrays

qsort