Qsort - 交替排序顺序

Question

我有一个程序使用（并且必须继续使用）实现 qsort 的旧排序函数。我还必须为排序函数提供正确的数据，以按升序（如果字符串包含偶数）或降序（如果字符串包含奇数）对数据进行排序。

必须更改数据才能实现此目的，但不能更改排序功能。

该代码是用C编写的，但我没有针对这个特定问题的相关代码片段。

真正的问题是：

如何转换数据以使输出与下面所需的输出匹配？

我有以下数据（或类似数据）

<前><代码>字符串 1 字符串2 字符串 3 字符串 4 字符串 5 字符串 6

编辑：数据是许多字符串类型 char **，每个字符串内的数字是一个 int。

期望的输出是

<前><代码>字符串 5 字符串 3 字符串1 字符串2 字符串 4 字符串 6

排序通常以降序方式与输入 1:1 匹配。我已经成功地通过在字符串后面的数字前面添加 1 或 0 来生成呈现以下输出的转换。

所以要排序的内部数据看起来像这样

<前><代码>字符串 01 字符串 12 弦03 字符串 14 弦05 字符串 16

这会产生以下输出（转换仅用于排序，并且是临时的）。

<前><代码>字符串 1 字符串 3 字符串 5 字符串2 字符串 4 字符串 6

Answer 1

您应该有一个包含数据和值的结构：

Struct DataValue
{
   string data;
   int value;
} 

如 {"01", 1}
然后按值排序并输出数据，
如果你想进行常规排序，排序并不难：
首先按值排序以创建像您所示的列表。 （对于值）
现在创建一个空的数据值数组（具有基本数组大小），从最后一项开始并按如下方式填充：

    int j = 0;
    for (int i = a.Count - 1; i >= 0; i -= 2) // fill bottom of list
    {
        b[a.Count - 1 - j] = a[i];
        j++;
    }

    j = 0;
    for (int i = a.Count - 2; i >= 0; i -= 2)  // fill root of list
    {
        b[j] = a[i];
        j++;
    }

最后输出值。

我用c#写的，在c中没有太大不同。
你会得到：

  List<int> a = new List<int>{1,2,3,4,5,6,7};

   b==> 6,4,2,1,3,5,7

and for:
  List<int> a = new List<int>{1,2,3,4,5,6};
  b==> 5,3,1,2,4,6

Answer 2

这可以使用自定义比较例程就地完成（即使用单个值数组，不需要单独的列表）。下面的函数假设您直接对字符串进行排序。最好对数据进行预处理，以便从字符串中提取数字并将两者放入结构中。但这会给你这个想法。

您可以将指向此比较函数的指针传递给qsort。

int Comparer(void * v1, void * v2)
{
    char *s1 = (char *)v1;
    char *s2 = (char *)v2;

    // Here, extract the numbers from the ends of the strings.
    int n1 = // extract number
    int n2 = // extract number

    // First comparison sorts odd numbers above even numbers
    if ((n1 % 2) == 1)
    {
        // first number is odd
        if ((n2 % 2) == 1)
        {
            // second number is odd, so sort the numbers ascending
            return (n1 - n2);
        }
        else
        {
            // second number is even, which is "greater than" any odd number
            return -1;
        }
    }
    else
    {
        // first number is even
        if ((n2 % 2) == 0)
        {
            // second number is even, so sort the numbers descending
            return (n2 - n1);
        }
        else
        {
            // second number is odd, which is "less than" any even number
            return 1;
        }
    }
}

Answer 3

如果 i 是奇数，则在前面添加 9-i。否则在前面加上 9。

Answer 4

1. 预处理：将偶数字符串放入列表中（我们称此列表为 _evens_）并将奇数字符串放入单独的列表中（称为 _odds_）
2. 对两个列表进行排序
3. 创建目标列表
4. 将 _odds_ 列表视为堆栈：弹出 _odds_ 的顶部并将弹出的元素放置到目标列表的*前面*。
5. 将 _evens_ 视为队列：弹出 _evens_ 的顶部并将弹出的元素放置在目标列表的 *end* 处。