如何对数组进行排序以获得与数组开头相同的所有数字

问题描述 投票：0回答：2

我正在编写一个来自yahtzee的程序，我正在尝试获取所有给予不同点的情况，例如3种、4种或一种等。

为此，我考虑排列玩家骰子的值并验证第一个 x 是否相等并从那里开始。我尝试进行选择排序和冒泡排序，但无法让它们工作，因为当数字相同时它们无法决定做什么。我有什么想法可以让它发挥作用吗？

这是我为此目的尝试过的代码：

#include <stdio.h>
#include <stdlib.h>

#define n 5

void
switches(float *v, float *m)
{
    int temp;

    temp = *v;
    *v = *m;
    *m = temp;

}

void
selection(int size, int *v)
{

    int min, i, j;

    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if (v[j] <= v[min])
                min = j;
        }

        if (min != i)
            switches(v[i], v[min]);
    }
}

int
main(void)
{
    int size = n;
    int v[n] = { 2, 1, 3, 3, 3 };
    int m[n] = { 1, 3, 4, 3, 3 };

    selection(n, v);

    for (int i = 0; i < 6; i++)
        printf("The values for the array are:%d\n", v[i]);

    return 0;
}

这是另一个文件上的测试代码，因为我还没有在实际程序中尝试过。

arrays c sorting
2个回答
0
投票

C 中的一个好的经验法则是：当您在同一个句子中听到“排序/排序”和“数组”时，您的第一个想法应该是

qsort
。 （这可能也是很多评论中提到
qsort
的原因）

qsort
的一个重要部分是比较功能。比较函数获取 2 个数组元素的值（实际上是一个指向两个数组元素的指针），并且仅根据这些值，比较函数需要返回以下 3 个结果中的 1 个：

  1. A 在 B 之前
  2. B 在 A 之前
  3. 没关系

在大多数情况下，可以编写这样的比较函数，因此可以使用 

qsort
进行数组排序。

但是... 问题中要求的排序不仅仅基于两个元素的值。请求的排序涉及整个数组中每个骰子值的频率（也称为出现次数）。

由于我们无法仅从特定值本身得知该值的频率，因此我们无法编写比较函数。我们需要一些无法获得的额外信息。所以...

结论是：我们不能用

qsort

除非...我们愿意“作弊”/“做肮脏的事”/“...”

如果我们愿意这样做，我们可以通过使用（可怕的）全局变量（哦天哪......）将额外的信息添加到比较函数中。

它可能类似于下面的代码。这个想法是计算每个骰子值的频率并将其存储在全局变量中before调用

qsort
。然后比较函数可以访问全局变量来检索频率信息。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


// Global variable :-(
int cnt[7];  // 7 elements but element at index zero won't be used
             // as dice values are 1, 2, ..., 6

#define CNT_ARRAY_SIZE (sizeof cnt / sizeof cnt[0])

#define DICES 5

void roll_dices(int n, int roll[])
{
  for (int i=0; i < n; ++i) roll[i] = rand() % (CNT_ARRAY_SIZE-1) + 1;
}

void print_dices(int n, int roll[])
{
  for (int i=0; i < n; ++i) printf("%d ", roll[i]);
}

int cmp(const void *pa, const void *pb)
{
  int a = *(int*)pa;
  int b = *(int*)pb;

  // if A more frequent than B, return -1
  if (cnt[a] > cnt[b]) return -1;

  // if B more frequent than A, return 1
  if (cnt[a] < cnt[b]) return 1;

  // if A greater than B, return -1
  if (a > b) return -1;

  // if B greater than A, return 1
  if (a < b) return 1;

  // Same frequency, same value, retun 0
  return 0;
}

void sort_dices(int n, int roll[])
{
  // Calculate frequency
  for (size_t i=0; i < CNT_ARRAY_SIZE; ++i) cnt[i] = 0;
  for (int i=0; i < n; ++i) ++cnt[roll[i]];

  // Call qsort
  qsort(roll, n, sizeof roll[0], cmp);
}

int main(void) {
  srand(time(NULL));

  int roll[DICES];

  for (int i=0; i < 20; ++i)
  {
    roll_dices(DICES, roll);
    print_dices(DICES, roll);
    printf("-> ");
    sort_dices(DICES, roll);
    print_dices(DICES, roll);
    puts("");
  }

  return 0;
}

输出示例：

4 5 2 2 4 -> 4 4 2 2 5 
5 5 6 1 4 -> 5 5 6 4 1 
4 6 1 6 6 -> 6 6 6 4 1 
5 2 6 1 3 -> 6 5 3 2 1 
2 5 4 1 2 -> 2 2 5 4 1 
3 2 4 3 4 -> 4 4 3 3 2 
3 6 2 5 6 -> 6 6 5 3 2 
3 3 2 3 1 -> 3 3 3 2 1 
3 4 4 3 2 -> 4 4 3 3 2 
4 6 1 1 4 -> 4 4 1 1 6 
3 2 6 4 2 -> 2 2 6 4 3 
1 4 1 3 1 -> 1 1 1 4 3 
5 5 4 4 1 -> 5 5 4 4 1 
1 1 1 6 1 -> 1 1 1 1 6 
5 2 4 3 3 -> 3 3 5 4 2 
3 4 2 3 4 -> 4 4 3 3 2 
3 4 4 2 1 -> 4 4 3 2 1 
3 1 5 4 3 -> 3 3 5 4 1 
3 2 5 4 5 -> 5 5 4 3 2 
6 5 3 4 4 -> 4 4 6 5 3

注意：全局变量的主要问题是它无法在多线程应用程序中正常工作。对于多线程应用程序，需要一些额外的代码来确保两个线程不会同时更新相同的全局变量而相互干扰。

-1
投票

顺便说一句，基本的选择排序：

void selection_sort_int( int * array, size_t n )
{
  // Each time through this loop the array is one element more sorted
  for (size_t sorted_index = 0;  sorted_index < n-1;  sorted_index++)
  {
    // SUV == “smallest unsorted value”’s index
    size_t suv_index = sorted_index;

    // Find the suv in the remaining (unsorted) array
    for (size_t index = suv_index;  index < n;  index++)
      if (array[index] < array[suv_index])
        suv_index = index;

    swap_int( array+sorted_index, array+suv_index );
  }
}

我们可以将其重写为更简洁的形式：

void selection_sort_int( int * array, size_t n )
{
  while (n --> 1)
  {
    int * min_value = array;
    for (size_t i = 0;  i < n+1;  i++)
      if (array[i] < *min_value)
        min_value = array + i;
    swap_int( array++, min_value )
  }
}

如果您希望它具有与 

qsort()
相同的通用界面，我们也可以这样做。 （我们只需要一个通用的辅助函数来交换元素。）

void memswap( void * a, void * b, size_t nbytes )
{
  if (a == b) return;
  unsigned char * x = a;
  unsigned char * y = b;
  while (nbytes--)
  {
    unsigned char c = *x;
    *x++ = *y;
    *y++ =  c;
  }
}

void selection_sort(
    void * array, size_t n, size_t element_size, 
    int (* compare)( const void *, const void * ) )
{
  char * bytes = array;
  while (n --> 1)
  {
    char * min_value = bytes;
    for (size_t i = 0;  i < n+1;  i++)
      if (compare( bytes + i * element_size, min_value ) < 0)
        min_value = bytes + i * element_size;
    memswap( bytes, min_value, element_size );
    bytes += element_size;
  }
}

我们可以按照通常的方式在整数数组上使用它：

#include <stdio.h>

int compare_ints( const void * a, const void * b )
{
  if (*(const int *)a < *(const int *)b) return -1;
  if (*(const int *)a > *(const int *)b) return  1;
  return 0;
}

#define sizeof_array(xs) (sizeof(xs)/sizeof(xs[0]))

int main(void)
{
  int xs[] = { 3, 4, 2, 7, 3, 6, 7, 1, 5 };

  selection_sort( xs, sizeof_array(xs), sizeof(xs[0]), &compare_ints );

  printf( "%d", xs[0] );
  for (size_t n = 1;  n < sizeof_array(xs);  n++)
    printf( " %d", xs[n] );
  printf( "\n" );

  return 0;
}

一些要点：

  • 选择排序不是是一种稳定的排序。 （其中的“交换”功能对此造成了麻烦。如果您需要稳定，请使用插入排序或合并排序。）
    • 与其他排序相比，选择排序相当“慢”。无论如何，你应该使用
  • qsort()。 
    • PS。我只是凭空写下了这个。如果我有任何错误，请务必评论。

PPS。好吧，我想我已经改正了所有错别字。

    




    

    


  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.