代码之家 › 专栏 › 技术社区 › RoadRunner

对数组C进行部分排序

qsort arrays c

RoadRunner · 技术社区 · 8 年前

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

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

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

到目前为止,我一直在使用 qsort 快速排序 是 O(nlogn) 最佳案例和 O(n^2) 对于最坏的情况,有没有更有效的方法来解决这个问题?我所说的高效只是一种更快的方式,比 O(nlogn) .

任何帮助都会很好

4 回复 | 直到 8 年前

Malcolm McLean 8 年前

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

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

Edward Jezisek 8 年前

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

#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出现最坏情况,同时保持其平均情况。

coder 8 年前

我建议使用基数排序,它是这种情况下最有效的排序方法,复杂度为O(n)。你甚至可以稍微改变一下,当找到三个最大值时停止。您可以找到并理解基数缩写: https://www.cs.usfca.edu/~galles/visualization/RadixSort.html

Nikhil Pathania 7 年前

如果我们要找出三个最大的数字,那么我们可以运行 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;
 }