C++输出排序后原来对应的位置值，快排的比较函数应该怎么写

在C++中，快速排序（Quick Sort）通常会通过递归的方式对数组进行分割，并在每个分割过程中进行元素交换。如果你想要记录排序后的元素原本在未排序数组中的位置，你可以自定义一个比较函数，这个函数不仅负责元素间的大小比较，还同时存储原始索引信息。

假设你有一个`Pair<int, int>`类型的结构体，其中包含一个整数值`val`和一个表示原索引的`index`，那么比较函数（例如`compare`）可以长这样：

bool compare(const Pair<int, int>& a, const Pair<int, int>& b) {
    if (a.val == b.val) {
        return a.index < b.index; // 如果值相等，按原索引升序排列
    } else {
        return a.val < b.val; // 值不相等，直接按照值的顺序
    }
}

在快速排序的过程中，你可以使用`std::stable_sort`，它保持相等元素原有的相对顺序，然后传递上述自定义比较函数：

void quicksort_with_indices(Pair<int, int>[] arr, int low, int high, bool ascending = true) {
    if (low < high) {
        auto pivot_index = partition(arr, low, high, compare);
        quicksort_with_indices(arr, low, pivot_index - 1, ascending);
        quicksort_with_indices(arr, pivot_index + 1, high, ascending);
    }
}

int partition(Pair<int, int>[] arr, int low, int high, bool (*cmp)(const Pair<int, int>&, const Pair<int, int>&)) {
    Pair<int, int> pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; ++j) {
        if (ascending ? cmp(arr[j], pivot) : cmp(pivot, arr[j])) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}