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
3. Q=划分(A，p，r)
4. 快速排序(A，p，q-1)
5. 快速排序(A，q+1，r)
6. 划分(A，p，r)
7. X= Ar
8. I=p-1
9. 对于j=p到r-1
10. _____i= i+1；
11. _____exchange Ai与Aj
12. 与Ar交换Ai+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);
    }
}

请注意，您不需要检查“如果(长度< 2)返回；”

其次，在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);

在考虑了上述各点之后，您应该能够正确地排序。

Answer 2

在几乎所有失败的快速排序()算法中，最主要的罪魁祸首是分区算法，该算法未能正确地排除枢轴槽或其中低端和高下的不正确的数学。这也没什么不同。执行就地分区的见活生生的例子。

在您的情况下，我将确保您的parition算法假设被分区的区域从begin开始，以end之前的元素结束，换句话说：

for(j = begin; j != end+1; ++j)

应该是这样：

for(j = begin; j != end; ++j)

导致快速排序()失败的第二个主要原因是未能跳过上次分区运行中的支点。如果您做了前面代码中提到的正确的事情，那么如下所示：

 auto pivot = Partition(begin, end);
 Q_Sort(begin, begin + pivot - 1);  // <<=== -1 should not be here.
 Q_Sort(begin + pivot + 1, end);

实际上应该是这样：

 auto pivot = Partition(begin, end);
 Q_Sort(begin, begin + pivot);
 Q_Sort(begin + pivot + 1, end);

记住，C++迭代器运行到end()，这是继最后一个您想要的元素之后的第一个元素，所以需要使用No-1。给定一个序列，如。

int ar[] = { 5,6,2,7,9,8 }

假设枢轴槽位于第四个插槽(pivot=3)，那么

 Q_Sort(begin, begin + pivot);    // includes 5,6,2, NOT 7
 Q_Sort(begin + pivot + 1, end);  // includes 9,8, again, NOT 7

我知道这听起来有些奇怪，但如果你不小心不想跳过枢轴插槽，那么调用将是这样的：

 Q_Sort(begin, begin + pivot);   // beginning through (pivot-1)
 Q_Sort(begin + pivot, end);     // pivot through end

这是快速排序()实现中的另一个常见错误。

在这些基础上努力，你应该做得很好。