c++ - 如何化简两个相似的函数

Question

我是一名学习计算机工程的学生。今天我正在学习使用 C++ 进行快速排序。这是非常棒的算法，我认识到快速排序需要升序和相反的两个函数。以下是我的代码!

#include <iostream>
#define ASCENDING 0 
#define DESCENDING 1
#define MAX_SIZE 50001

using namespace std;


int numberCnt;
int sortManner;
int list[MAX_SIZE];

void GetInput();
void QuickSort(int* list, int left, int right, int(*partition)(int*, int, int));
int PartitionAscending(int* list, int left, int right);
int PartitionDescending(int* list, int left, int right);
void Swap(int &a, int &b);

int main(){
    GetInput();
    QuickSort(list, 0, numberCnt - 1, sortManner == ASCENDING ? PartitionAscending : PartitionDescending);
    for (int i = 0; i < numberCnt; i++){
        cout << list[i] << endl;
    }

    return 0;
}

void QuickSort(int* list, int left, int right, int (*partition)(int*,int,int)){
    if (left < right){
        int pivot = partition(list, left, right);
        QuickSort(list, left, pivot - 1, partition);
        QuickSort(list, pivot + 1, right, partition);
    }
}
int PartitionAscending(int* list, int left, int right){
    int pivotVal = list[left];
    int pivotIdx = left;
    int low = left;
    int high = right + 1;

    do{
        do{
            low++;
        } while (list[low] < pivotVal);
        do{
            high--;
        } while (list[high] > pivotVal);
        if (low < high)
            Swap(list[low], list[high]);
    } while (low < high);

    Swap(list[pivotIdx], list[high]);

    return high;
}

int PartitionDescending(int* list, int left, int right){
    int pivotVal = list[left];
    int pivotIdx = left;
    int low = left;
    int high = right + 1;

    do{
        do{
            low++;
        } while (list[low] > pivotVal);
        do{
            high--;
        } while (list[high] < pivotVal);
        if (low < high)
            Swap(list[low], list[high]);
    } while (low < high);

    Swap(list[pivotIdx], list[high]);

    return high;
}

void Swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void GetInput(){
    cin >> numberCnt >> sortManner;
    for (int i = 0; i < numberCnt; i++)
        cin >> list[i];
}

你知道彼此的功能非常相似!这对我来说太浪费了!

如何精简功能？

如果你不懂我的池子英文请不要犹豫，让我知道:)

Answer 1

您的分区可以采用比较仿函数，例如:

template <typename Comp>
int Partition(int* list, int left, int right, Comp comp){
    int pivotVal = list[left];
    int pivotIdx = left;
    int low = left;
    int high = right + 1;

    do{
        do{
            low++;
        } while (comp(list[low], pivotVal));
        do{
            high--;
        } while (!comp(list[high], pivotVal));
        if (low < high)
            Swap(list[low], list[high]);
    } while (low < high);

    Swap(list[pivotIdx], list[high]);

    return high;
}

int PartitionAscending(int* list, int left, int right){
    return Partition(list, left, right, [](int l, int r){ return l < r; });
    // or return Partition(list, left, right, std::less<int>());
}

int PartitionDescending(int* list, int left, int right){
    return Partition(list, left, right, [](int l, int r){ return l > r; });
    // or return Partition(list, left, right, std::greater<int>());
}