C++ 快速排序实现，没有正确的输出

Question

我正在实现 Cormen 的算法书 (CLRS) 中的快速排序算法。

 vector<int> numbers = {5, 6, 3, 4, 1, 2, 7, 13, -6, 0, 3, 1, -2};

 My_Quick_Sort(numbers.begin(), numbers.end());

没有错误，但是无法对数字进行排序。

书上的伪代码是这样的

1. 快速排序(A, p, r)
2. 如果 p < r
3. q = 分区(A, p, r)
4. 快速排序(A, p, q-1)

5. 快速排序(A, q+1, r)

6. 分区(A, p, r)

7. x = A[r]
8. i = p - 1
9. 对于 j = p 到 r - 1
10. ___i= i+1;
11. ___用A[j]交换A[i]
12. 用A[r]交换A[i+1]
13. 返回 i + 1;

我的实现如下所示。

 template<typename T>
 void Swap(T a, T b)
 {
     typedef typename std::iterator_traits<T>::value_type value_type;
     value_type temp;
     temp = *a;
     *a = *b;
     *b = temp;
 }

 template<typename T>
 int Partition(T begin, T end)
 {
     typedef typename std::iterator_traits<T>::value_type value_type;
     value_type x;
         x = *end;
     T i = begin - 1;
     T j;
     for(j = begin; j != end+1; ++j)
     {
         if ( x >= *j )
         {
              i++;
              Swap(i, j);
         }
         Swap(i+1, end);
     }
     return static_cast<int>(distance(begin, i) + 1);
 }

 template<typename T>
 void Q_Sort(T begin, T end)
 {
     auto length = end - begin;
     if (length < 2) return;

     if ( begin != end )
     {
         auto pivot = Partition(begin, end);
         Q_Sort(begin, begin + pivot - 1);
         Q_Sort(begin + pivot + 1, end);
     }
 }

有人知道我的代码吗？它有效，但不进行排序。例如，如果我输入随机播放:13, 0, -6, 6, -2, 5, 4, 3, 1, 1, 3, 2, 7,

输出如下My_Quick_Sort: -6, -2, 0, 6, 13, 0, 5, 1, 1, 4, 2, 3, 7,

Answer 1

关于您的实现的一些注意事项:

首先，为了简化您的 Q_Sort 方法和逻辑，我将从分区方法返回一个迭代器而不是一个 int。这将简化 Q_Sort 如下:

template<typename T>
void Q_Sort(T begin, T end)
{
    if ( begin < end )
    {
        T pivot = Partition(begin, end);
        Q_Sort(begin, pivot - 1);
        Q_Sort( pivot + 1, end);
    }
}

请注意，您不需要检查“if (length < 2) return;”

其次，在for循环的分区方法中，你的终止条件“j != end+1”与伪代码不匹配。它应该是 end - 1。这是 Partition 方法的新代码。请注意，我假设第二个参数 (end) 指向实际的最后一个值，而不是指向最后一个值之后的值。

template<typename T>
T Partition(T begin, T end)
{
    typedef typename std::iterator_traits<T>::value_type value_type;
    value_type x;

    x = *end;
    T i = begin - 1;

    for(T j = begin; j < end; ++j)
    {
        if ( x >= *j )
        {
            i++;
            Swap(i, j);
        }
    }

    Swap(i+1, end);
    //return static_cast<int>(distance(begin, i) + 1);
    return i+1;
}

最后，我相信伪代码假定第二个参数是最后一个元素，但迭代器 numbers.end() 指向最后一个元素之后的位置。因此，您需要将调用更改为快速排序，如下所示:

vector<int>::iterator iterEnd = numbers.end();
--iterEnd;
Q_Sort(numbers.begin(), iterEnd);

在考虑了以上几点后，您应该能够正确排序。