3 
 int a[] = {0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 2, 1, 1, 0, 0, 0, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0};

对此类系列进行排序的最佳方法是什么？请记住，我想要最小的复杂性。

4

5 回答 5

4

如果数字的上限较小，则可以使用计数排序：计算每个项目在数组中出现的次数，然后遍历数组，并为每个值放入与计数一样多的项目。

例如，在您的情况下，您将计算 17 个零、7 个 1 和 4 个 2。设置前 17 项为 0，后面 7 项为 1，其余 4 项为 2，得到排序后的数组。

这种方法具有线性复杂性。

于 2013-07-25T19:44:44.110 回答
2

您可以使用Counting Sort对此类系列进行排序。

于 2013-07-25T19:44:00.483 回答
2

如果数字系列确实限于值 0-2，那么最好的办法是使用计数样式排序。

void CountedSortMaxThree(int* array, size_t length) { 
  int count0 = 0;
  int count1 = 0;
  int count2 = 0;

  for (int i = 0; i < length; i++) { 
    switch(array[i]) {
      case 0: count0++; break; 
      case 1: count1++; break;
      case 2: count2++; break;
    }
  }

  int index = 0;
  while (count0-- > 0) array[index++] = 0;
  while (count1-- > 0) array[index++] = 1;
  while (count2-- > 0) array[index++] = 2;
}

为了可重用，您需要定义一个等于最大值与硬编码数字的桶数组

void CountedSort(int* array, int length, int max) { 
  int* buckets = malloc(sizeof(int) * max);
  for (int i = 0; i < length; i++) { 
    bucket[array[i]]++;
  }

  int index = 0;
  for (int i = 0; i < max; i++) {
    while (buckets[i]-- > 0) {
      array[index++] = i;
    }
  }
  free(buckets);
}

请注意，仅当值的范围较小时才应使用计数排序。在您的示例中，范围是 3（包括 0 到 2），因此可以进行计数排序。如果范围要高得多（想想Int32.Max），那么你最终会分配一个巨大的桶数组，这最终会变得相当低效

于 2013-07-25T19:46:33.637 回答
0 
void sort012Dutch(int A[],int n)
{
int pos0=0,pos2=n-1,i=0;
    while(i<n)
{
    if(A[i]==0)
    {
        A[i]=A[pos0];
        A[pos0]=0;
        pos0++;
    }
    if(A[i]==2&&i<pos2)
    {
        A[i]=A[pos2];
        A[pos2]=2;
        pos2--;
        i--;//0 could be swapped
    }
    i++;
}
}

pos0 indicates the next index in the array where 0 is to be inserted
pos2 indicates the next index in the array where 2 is to be inserted

于 2013-07-26T05:50:53.263 回答
0

您可以使用该qsort功能。

于 2013-07-25T19:43:08.490 回答