c++ - 使用快速排序算法的类型问题

Question

我在使用迭代器模板实现快速排序算法时遇到不同类型的问题，我无法弄清楚发生了什么。

算法如下:

template <typename I> void ordenacion_rapida(I i, I j, int n0=1)
{
    int n = j-i;

    if (n<=n0)
        ordenacion_insercion<I>(i, j);
    else
    {
        I p = pivote(i, j);
        ordenacion_rapida<I>(i, p);
        ordenacion_rapida<I>(p+1, j);
    }
}

template <typename I> I pivote(I i, I j)
{
    I p = i;
    typedef typename iterator_traits<I>::value_type tipo;
    tipo x = *(i);

    for (I k=i+1; k<j; ++k)
        if (*(k)<=x)
        {
            ++p;
            tipo aux = *(p);
            *(p) = *(k);
            *(k) = aux;
        }
    *(i) = *(p);
    *(p) = x;
}

template <typename I> void ordenacion_insercion(I i, I j)
{
    typedef typename iterator_traits<I>::value_type tipo;
    for (I k=i+1; k<j; ++k)
    {
        tipo x = *(k);
        while (k!=i && x<*(k-1))
        {
            *(k) = *(k-1);
            --k;
        }
        *(k) = x;
    }
}

代码量过多请见谅，问题出在哪一行，我已经详尽分析过了。

问题是，当我尝试对 vector<double 进行排序时或 vector<float>我报错了，而我用vector<int>没有这个问题.

问题出在哪里？

Answer 1

我看不出你的代码有什么问题，它工作得很好。唯一的问题是您忘记在 pivote 中返回一些东西。

#include <iterator>
#include <vector>
using namespace std;

template <typename I> void ordenacion_insercion(I i, I j)
{
    // snip
}

template <typename I> I pivote(I i, I j)
{
    // snip

    // Assuming you intended to return P
    return p;
}

template <typename I> void ordenacion_rapida(I i, I j, int n0=1)
{
    // snip
}

#include <iostream>

int main() {
    std::vector<double> v = { 1.2f, 0.5f, 3.5f, 0.2f };
    ordenacion_rapida(v.begin(), v.end());
    for (unsigned int i = 0; i < v.size(); i++)
        std::cout << v[i] << " ";
} // 0.2 0.5 1.2 3.5