Qsort - 交替排序顺序

Question

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

必须修改数据才能实现这一点，不能修改排序函数。

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

真正的问题是：

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

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

String 1
String 2
String 3
String 4
String 5
String 6

编辑：数据是字符串类型的char **，每个字符串中的数字是int。

期望的输出是

String 5
String 3
String 1
String 2
String 4
String 6

通常情况下，排序是按照输入1:1的降序进行的。我已经成功地生成了一种转换方式，通过在字符串后面添加1或0来呈现以下输出。

因此，要排序的内部数据看起来像这样

String 01
String 12
String 03
String 14
String 05
String 16

这将产生以下输出（变换仅用于排序，并且是暂时的）。

String 1
String 3
String 5
String 2
String 4
String 6

- Peter Lindqvist

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

- Saeed Amiri

---

实际上这与我所拥有的非常相似，不同之处在于我的数据存储在文件中，而值则存储在我的内部排序结构中。嗯，我希望这样说得通。 - Peter Lindqvist

这不是即插即用的，但它给了我一些灵感，谢谢！ - Peter Lindqvist

@Peter Lindqvist，如果数据是"string 01"这样的格式，你可以使用trim函数来获取1并在内存中进行排序。但是，如果文件大小很大（会导致异常），而且你无法将其全部读入内存，那么你可以使用原地排序算法来进行排序，请参见http://en.wikipedia.org/wiki/In-place_algorithm。 - Saeed Amiri

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;
        }
    }
}

- Jim Mischel

---

这是一个有效的解决方案，但恐怕它不能应用于我的环境。 - Peter Lindqvist

Answer 3

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

- Oswald

---

也许，如果我假设9代表INT_MAX的话。 - Peter Lindqvist

Answer 4

1. 预处理：将偶数字符串放入一个列表中（我们称之为“偶数”列表），并将奇数字符串放入另一个列表中（称为“奇数”列表）
2. 对这两个列表进行排序
3. 创建一个目标列表
4. 将_odd_列表视为堆栈：弹出_odd_的顶部，并将弹出的元素放置在目标列表的*前面*。
5. 将_evens_作为队列：弹出_evens_的顶部，并将弹出的元素放置在目标列表的*末尾*。

- David Weiser