C++：将数组的前半部分按升序排列，后半部分按降序排列

Question

我是C++的新手，我正在尝试完成这个问题：（链接）：

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

排序函数是由我自己实现的。我可以使用cstdlib中的qsort，但它并不那么有趣。

我已经编写了一个用于排序数组的代码，但我不知道如何将数组分成两部分进行排序。

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

- KardanovIR

---

通过将您先前的解决方案中的“<”更改为“>”（或反之亦然），您应该能够得到答案，不是吗？ - Ian

请注意，这不是C语言，而是C++。 - Pawan

你对C或C++感兴趣吗？答案会有很大的不同。 - juanchopanza

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()的原型。

- P.P

Answer 2

根据我所看到的，你的数组仅包含原始的整数值，可以使用C ++ sort方法进行排序。

#include <algorithm> // this is to access c++ std::sort method

...

std::sort(array + first, array + last) // input range of index of array to be sorted

...

我会翻译以下内容：

这应该会解决它。

另一个需要注意的点是默认情况下按升序排序。所以你可以尝试使用CompareTo方法等进行操作。但我的最爱技巧是将数组中的所有值乘以-1，然后进行排序，再将-1乘回去，最终得到按降序排序的数组。

- seokhoonlee

Answer 3

C++编写数组和其他数据序列的算法的方式是通过迭代器：

template <typename Iter>
void qsort(Iter begin, Iter end)
{
    auto pivot = begin + (end - begin) / 2;
    std::nth_element(begin, pivot, end);
    qsort(begin, pivot);
    qsort(pivot + 1, end);
}

将其与 reverse_iterator 相结合，我们就可以得到您想要的行为：

auto lhBegin = array;
auto lhEnd = array + K;
qsort(lhBegin, lhEnd);
// [ 0, 1, ..., K-2, K-1 ] is now in sorted order

auto rhBegin = std::make_reverse_iterator(array + N);
auto rhEnd = std::make_reverse_iterator(array + K);
qsort(rhBegin, rhEnd);
// [ N-1, N-2, ..., K+1, K ] is now in sorted order

- Brian Rodriguez

Answer 4

您只需要替换以下行，以便按降序获取数据：

        //while (arr[i] <= arr[pivot] && i < last)
        while (arr[i] >= arr[pivot] && i < last)
            i++;
        //while (arr[j] > arr[pivot])
        while (arr[j] < arr[pivot])

- Pawan