0

所以我有这个功能可以在枢轴上排序，我遇到的问题是让枢轴在到达中间数字后切换到它，它对枢轴之间的数字右侧和数字左侧进行排序，但一次它到达了它没有跨越的中心。我认为这与我的 while 循环有关。请帮忙！

void qsort(int *arry, unsigned int size);

int main()
{
   int arry[] = {45, 27, 82, 21, 63, 22, 35, 19, 4, 5};

   qsort(arry, 10);


   system("pause");
   return 0;
}


void qsort(int *arry, unsigned int size)
{
   int piv = *arry;
   int *left, *right, temp;  // create the traversal pointers
   if (size > 1)
   {


      while(WHAT GOES HERE?!)
      {

         left  = arry + 1;
         right = arry + (size - 1);


          //process left pointer for value larger than piv.
          while((*left < piv) && (left < right))
          {
              ++left;
          }
          cout << *left << endl;

          //process right pointer for value smaller tham piv
          while((*right > piv) && (right > left ))
          {
              right--;
          }
          cout << *right << endl;
          temp   = *left;
          *left  = *right;
          *right = temp;
       }

   }  //How do I verify the placement of the pivot value?
   for(unsigned int i=0; i < size; i++)
      cout << arry[i] << " ";
   cout << endl;
}
4

1 回答 1

1

此处发生的事情并不是您应该对此代码唯一关心的问题。可能会出现许多问题。

首先，您的 left-ptr 和 right-ptr 初始化程序不应该在循环内；他们需要在外部时间之前成为设置的一部分。您的函数序言应如下所示：

void quicksort(int *arry, size_t size)
{
    if (size <= 1)  // skip 1-length lists.
        return;

    // since you're using a static pivot location, 
    //  may as well use the one at the right end.
    int *left = arry;
    int *right = arry + (size-1);

    // choose a pivot value. ideally a random trio is chosen, and the
    //  middle element of those three is selected. for this simple case
    //  we're using the element at the right-most location of the list
    int piv = arry[size-1];

接下来是限制器，它最终阻止了你在 while 循环中的疯狂。传统上就是这样：

while (left < right)

一旦你的左指针赶上你的右指针（反之亦然），就不再需要继续循环了。请记住，left-ptr 左侧的所有值都已知小于（并且可能等于，但我们将在一分钟内到达）枢轴。同样，已知 right-ptr 右侧的所有值都大于枢轴。折叠枢轴窗口背后的想法是，在您有两个需要交换位置的项目之前，您永远不会真正交换。

这将我们带到了内部的while循环。

  //process left pointer for value larger than piv.
  while((*left < piv) && (left < right))
      ++left;

  //process right pointer for value smaller tham piv
  while((*right > piv) && (right > left ))
      right--;

这样做的根本问题是在同时（在两个不同的插槽中）遇到枢轴值时会发生*left 什么。 *right他们都停下来，然后他们都这样做：

temp   = *left;
*left  = *right;
*right = temp;

然后循环继续。下一次围绕这两个循环将立即终止（因为它们都位于一个枢轴值上，它们将返回交换，再次切换它们，然后重复这个......永远。为了解决这个问题，这些指针之一必须包括枢轴作为允许的越过。此外，仅当 left-ptr 仍小于 right-ptr 时才交换。

// walk up until we find a value strictly larger than the pivot
while(left < right && (*left <= piv))
    ++left;

// walk down until we find a value smaller than the pivot
while (right > left && (*right > piv))
    --right;

if (left < right)
    swap(*left, *right);

注意：这使用std::swap()函数，一个最方便的实用程序。

最后是底部缺失的部分，即递归。我们递归到我们刚刚用我们的步行者标识的两个部分，但只有在确保底部分区和顶部分区确实是分开的之后。

// make sure left and right are properly ordered.
if (left > right)
    swap(left,right);

// sort subslices
quicksort(arry, (left - arry));
quicksort(arry + (right - arry), size - (right - arry));

把它们放在一起，以及一个测试它的示例程序：

示例程序

#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <cstdlib>
#include <ctime>
using namespace std;

// in-place quicksort.
void quicksort(int *arry, size_t size)
{
    if (size <= 1)
        return;

    // since you're using a static pivot location,
    //  may as well use the one at the right end.
    int *left = arry;
    int *right = arry + (size-1);

    // choose a pivot value. ideally a random trio is chosen, and the
    //  middle element of those three is selected. for this simple case
    //  we're using the element at the right-most location of the list
    int piv = arry[size-1];

    while(left < right)
    {
        // walk up until we find a value strictly larger than the pivot
        while(left < right && (*left <= piv))
            ++left;

        // walk down until we find a value smaller than the pivot
        while (right > left && (*right > piv))
            --right;

        if (left < right)
            swap(*left, *right);
    }

    // make sure left and right are properly ordered.
    if (left > right)
        swap(left,right);

    // sort subslices
    quicksort(arry, (left - arry));
    quicksort(arry + (right - arry), size - (right - arry));
}

int main()
{
    int arry[] = {45, 27, 82, 21, 63, 22, 35, 19, 4, 5};

    // before picture
    std::copy(arry, arry+10, ostream_iterator<int>(cout, " "));
    cout << endl;
    quicksort(arry, 10);

    // after picture
    std::copy(arry, arry+10, ostream_iterator<int>(cout, " "));
    cout << endl;

    std::srand((unsigned)std::time(0));
    std::vector<int> vals(30);
    for (size_t i=0;i<15;++i)
        vals[i] = vals[15+i] = int(i+1);
    std::random_shuffle(vals.begin(), vals.end());

    // before picture
    std::copy(vals.begin(), vals.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    quicksort(vals.data(), vals.size());

    // after picture
    std::copy(vals.begin(), vals.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

样本输出

45 27 82 21 63 22 35 19 4 5 
4 5 19 21 22 27 35 45 63 82 
14 9 2 1 3 11 8 4 12 15 10 13 5 3 2 11 14 7 7 12 8 15 6 9 6 5 10 4 13 1 
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15

我希望这能回答您关于一般快速排序如何工作的一些问题。我个人更喜欢单端就地扫描版本。我发现它更容易解释，当然也更容易理解。如果你想看，请告诉我。

于 2013-04-29T23:57:11.943 回答