在同一数组中对负数按降序排序，对正数按升序排序

Question

我有一个有趣的问题：给定一个包含唯一整数的数组。编写一个函数对数组进行排序，使负数出现在正数之前。负数按降序排列，正数按升序排列。并且不能使用辅助数组 - 这意味着所有这些都需要“就地”排序

例子：

int arr[] = {12, 56, -9, 4, -8, 46, 3, 7, -16, 78, 69};

会导致-8 -9 -16 3 4 7 12 46 56 69 78

我能够编写一个简单的程序，除了保留数量负数之外，它首先按升序对所有内容进行排序。然后，我交换负数的第一个和最后一个位置，并继续直到所有负数的末尾......最后，我返回数组。

有没有更复杂/更有效的方法来做到这一点。

这是我目前的代码：

int *negDescPosAsc(int *arr, int size)
{
    //treat negative numbers differently than positive numbers
    //sort negative numbers in descending order
    //sort positive numbers in ascending order
    //return the sorted array
    int negCount = 0;
    for (int i = 0; i < size; i++)
    {

        //do normal sort then reverse the negatives
        for (int j = 0; j < size - 1; j++)
        {
            if (*(arr + j) > *(arr + j + 1))
            {
                if (*(arr + j) < 0)
                {
                    negCount++;
                }
                int temp = *(arr + j);
                *(arr + j) = *(arr + j + 1);
                *(arr + j + 1) = temp;
            }
        }
    }

    int i = 0;
    while (negCount > 0)
    {
        int temp = *(arr + i); //store the value of the current element
        *(arr + i) = *(arr + negCount); //replace the current element with the last element
        *(arr + negCount) = temp; //replace the last element with the current element
        negCount--; //decrement the negative count
        i++; //increment the index
    }
    

    return arr;
}

Answer 1

您可以更改默认的比较函数来解决此问题。然后你可以使用qsort, 或std::sort或 你自己的排序方法。我将演示std::sort：

    std::vector<int> items = {12, 56, -9, 4, -8, 46, 3, 7, -16, 78, 69};
    auto comp = [](int A, int B) { return (A < 0 && B < 0) ? B < A : A < B; };
    std::sort(items.begin(), items.end(), comp);
    for (auto item : items) cout << item << " ";
    cout << endl;

输出是：-8 -9 -16 3 4 7 12 46 56 69 78

在这里我们检查两个数字是否为负数。如果是，我们就反转比较。

C 等效项：

int compare(const void *_A, const void *_B)
{
    int A = *(const int *)_A, B = *(const int *)_B;
    return (A < 0 && B < 0) ? B > A : A > B;
}

int main()
{
    int count = 11;
    int items[] = {12, 56, -9, 4, -8, 46, 3, 7, -16, 78, 69};
    qsort(items, count, sizeof(int), compare);
    for (int i = 0; i < count; ++i) printf("%i ", items[i]);
    printf("\n");
}