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

Question

我是新的C++,我试图做此:

我有一个N元素的数组.用户应该能够输入阵列和数目的所有元素ķ.之后,我必须对数组进行排序,使第一部分(元素1到K)按升序模式排序,第二部分(元素K到N)按降序排序.

排序功能由我自己实现.我可以使用快速排序的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().