如何为快速排序设置比较器

Question

我在使用 C++ 中的比较器时遇到问题。现在，我只是想在 Goodrich 的书 Data Structures and Algorithms in C++ 中使用通用参数实现快速排序。这是书中的代码：

#include <iostream>
#include <vector>
#include <functional>

template <typename E, typename C> // quick-sort S void quickSort(std::vector<E>& S, const C& less) {
void quickSort(std::vector<E>& S, const C& less){
        if (S.size() <= 1)
            {return;}// already sorted
        quickSortStep(S, 0, S.size()-1, less); // call sort utility
}


template <typename E, typename C>
void quickSortStep(std::vector<E>& S, int a, int b, const C& less) {
    if (a >= b) {return;}
    E pivot = S[b];
    int l=a;
    int r=b-1;
    while (l <= r) {
        while (l <= r && !less(pivot, S[l]))
            {l++;}//pivot is greater than S[l]
        while (r >= l && !less(S[r], pivot))
            {r--;}
        if (l < r)
            {std::swap(S[l], S[r]); std::swap(S[l], S[b]);}
        quickSortStep(S, a, l-1, less);
        quickSortStep(S, l+1, b, less);
    }
}

我找到了用于比较整数和双精度的模板的代码，并且正在尝试使其适用于该程序。但是，当我将函数 isLess 作为参数传入并尝试运行程序时，我收到构建错误：Call to function 'quickSortStep' that is neither visible in the template definition nor found by argument-dependent lookup。我已经在下面粘贴了 isLess 函数的代码以及我的 main ，如果有任何关于如何实现比较器的建议，我将不胜感激。

template <typename T>
bool isLess(T a, T b)
{
    return a<b;
}


int main(int argc, const char * argv[]) {
    //vector and comparator
    int myInts[]={15,2,7,99};
    std::vector<int>myVec(myInts,myInts+sizeof(myInts)/sizeof(int));
    int a,b;
    quickSort(myVec,isLess<int>(a, b));
    return 0;
}

编辑::

本书的代码排序不正确，所以我对 quickSortStep() 进行了以下调整，现在可以正常工作了：

void quickSortStep(std::vector<E>& S, int a, int b, const C& less) {
    if (a >= b) {return;}
    E pivot = S[b];
    int l=a;
    int r=b-1;
    while (l <= r) {
        while (l <= r && !less(pivot, S[l]))
            {l++;}//pivot is greater than S[l]
        while (r >= l && !less(S[r], pivot))
            {r--;}
        if (l < r)
            {
                std::swap(S[l], S[r]);

            }
    }
    std::swap(S[l], S[b]);
    quickSortStep(S, a, l-1, less);
    quickSortStep(S, l+1, b, less);
}

Answer 1

下面的代码回答了您的问题。但是快速排序不起作用。可能是你写错了。

template <typename T>
bool isLess(T a, T b)
{
    return a<b;
}


int main(int argc, const char * argv[]) {
    //vector and comparator
    std::vector<int> myVec { 15,2,7,99 };
    quickSort(myVec,isLess<int>);
    auto OK = std::is_sorted(myVec.begin(), myVec.end());
    assert(OK);
    return 0;
}

如何为快速排序设置比较器

How to Set Up Comparator for QuickSort

c++

comparator