C++:将数组的初始部分按升序排序，另一部分按降序排序

Question

我是 C++ 的新手，我正在尝试做 this :

我有一个包含 N 元素的数组。用户应该能够输入数组的所有元素和一个数字K。之后，我必须对数组进行排序，以便第一部分(元素 1 到 K)按升序排序，第二部分(元素 K 到 N) 降序排列。

排序功能是自己实现的。我可以使用 qsort来自 cstdlib，但不是很有趣。

我编写了对数组进行排序的代码，但我不明白如何将数组分成两部分进行排序。

#include <iostream>
#include <string>

void print_array(int[], int);
void qsort(int[], int, int);

int main()
{
    int array_length;
    int *array, k;
    std::cout << "Write array length: ";
    std::cin >> array_length;
    array = new int[array_length];
    for (int i = 0; i < array_length; i++) {
        std::cout << "Write " << i + 1 << " element: ";
        std::cin >> array[i];
    }
    print_array(array, array_length);
    do {
        std::cout << "Write k: ";
        std::cin >> k;
    } while (k >= array_length);
    qsort(array, 0, k);
    print_array(array, array_length);
}


void print_array(int* array, int length) {
    for (int i = 0; i < length; i++) {
        std::cout << array[i] << "\n";
    }
}

void qsort(int arr[], int fst, int last)
{
    int i, j, pivot, tmp;
    if (fst < last)
    {
        pivot = fst;
        i = fst;
        j = last;
        while (i < j)
        {
            while (arr[i] <= arr[pivot] && i < last)
                i++;
            while (arr[j] > arr[pivot])
                j--;
            if (i < j)
            {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        tmp = arr[pivot];
        arr[pivot] = arr[j];
        arr[j] = tmp;
        qsort(arr, fst, j - 1);
        qsort(arr, j + 1, last);
    }
}

Answer 1

你正在对一半进行排序:

qsort(array, 0, k);

同样，你需要对另一半进行排序:

qsort(array+k, 0, array_length-k);

现在，问题是两个部分都将按升序排列。因此，您需要一种方法来告诉 qsort() 将一半按升序排序，另一半按降序排序。将另一个标志传递给 qsort() 以更改交换顺序。所以你可以传递一个 bool 来表示它:

void qsort(int arr[], int fst, int last, bool pass)
{
           ....
           if (pass && i < j)
            {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
            if(!pass && i > j) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
       ...
       qsort(arr, fst, j - 1, pass); 
       qsort(arr, j + 1, last, pass);

当您调用它时，您可以传递 true 和 false 来“切换”交换顺序:

  qsort(array, 0, k, true);
  qsort(array+k, 0, array_length-k, false);

相应地更改qsort() 的原型(prototype)。