c++ - 带有 vector 对象 C++ 的快速排序函数

Question

我正在尝试将此函数转换为使用 vector 对象而不是整数数组。 vector 对象如下所示:

std::vector<Heltal *> htal;

Heltal 类包含一个名为 heltal 的私有(private)整数。

如何使用下面的函数对 htal vector 进行排序？

void Array::Sort(int a[], int first, int last)
{
    int low = first;
    int high = last;
    int x = a[(first+last)/2];
    do {
        while(a[low] < x) {
            low++;
        }
        while(a[high] > x) {
            high--;
        }
        if(low<=high) {
            std::swap(a[low],a[high]);
            low++;
            high--;
        }
    } while(low <= high);
    if(first < high)
        Array::Sort(a,first,high);
    if(low < last)
        Array::Sort(a,low,last);
}

Answer 1

正确的解决方案是放弃自定义排序并使用 std::sort 来自 <algorithm> .在几乎所有情况下，这几乎都可以保证更快、更优化。那么你只需:

#include <algorithm>
...
std::vector<Heltal *> htal;
...
// sort by pointer value
std::sort(htal.begin(), htal.end());

如果您想按对象值而不是指针值排序，请使用 std::vector<Heltal>而不是 std::vector<Heltal *> (无论如何，这几乎肯定是您应该做的)，或者将比较函数传递给 std::sort。

为此使用 C++11 lambda 的示例:

std::sort(htal.begin(), htal.end(), [](Heltal *a, Heltal *b) { return *a < *b; });