需要C++中的快速排序算法（尝试）的帮助

Question

我试过了一堆不同的方法来写这个，但大多数时候我陷入了一个无限循环。 这个版本的代码根本没有排序，我不知道问题是什么。

void quickSort(int unsorted[], int left, int right) { 
     int i = left, j = right; 
     int pivot = (left + right)/2; 

     while (i == pivot || j == pivot) { 
      if (unsorted[i] >= unsorted[pivot] && unsorted[pivot] >= unsorted[j]) 
       swap(unsorted[i], unsorted[j]); 

      if (i < pivot) 
       i++; 
      if (j > pivot) 
       j--; 
     }; 

     if (left < j && unsorted[left] != unsorted[j]) 
      right = pivot, quickSort(unsorted, left, right); 
     if (i < right && unsorted[right] != unsorted[i]) 
      left = pivot +1, quickSort(unsorted, left, right); 

} 

unsorted是填充有从0 100个随机值200

我为更新缓慢遗憾的阵列。 关于代码，我重新编写了大部分代码。 这是它看起来像现在：

void quickSort(int unsorted[], int left, int right) 
{ 
    int i = left, 
     j = right, 
     count = 0; 
    int pivot = (left + right)/2; 

    do 
    { 
      while (unsorted[i] < unsorted[pivot]) 
       i++; 
      while (unsorted[j] > unsorted[pivot]) 
       j--; 

      if (unsorted[i] >= unsorted[j] && i <= j) 
      { 
       swap(unsorted[i], unsorted[j]); 
       i++; 
       j--; 
       count++; 
      } 
      if (i == pivot && unsorted[pivot] < unsorted[j] && count == 0) 
      { 
       swap(unsorted[i], unsorted[j]); 
       i++; 
       j--; 
       count++; 
      } 
      if (j == pivot && unsorted[pivot] < unsorted[i] && count == 0) 
      { 
       swap(unsorted[i], unsorted[j]); 
       i++; 
       j--; 
       count++; 
      } 

      if (i == j && unsorted[i] > unsorted[pivot] && count == 0) 
      { 
       swap(unsorted[i], unsorted[pivot]); 
       i++; 
       j--; 
       count++; 
      } 
      if (i == j && unsorted[i] < unsorted[pivot] && count == 0) 
      { 
       swap(unsorted[i], unsorted[pivot]); 
       i++; 
       j--; 
      } 

      count = 0; 

    } while (i < j); 

    if (left < j) 
     quickSort(unsorted, left, j); 
    if (i < right) 
     quickSort(unsorted, i, right); 

} 

我已经一遍又一遍地用10个随机值尝试这种代码，它工作的大部分时间。有些情况下它不起作用，我试图找出什么时候。

时它不工作的一个例子是当值是：160，151，159，112，如图7所示，121，105，48，186

解决它。删除了很多代码，使它更简单，但至少可以工作。 甚至不知道如果u可以称之为快速搜索了，但这里是最后的版本：

void quickSort(int unsorted[], int left, int right) 
{ 
    int i = left, 
     j = right; 
    int pivot = right; 

    do 
    { 
     while (unsorted[i] < unsorted[pivot]) 
      i++; 
     while (unsorted[j] > unsorted[pivot]) 
      j--; 

     if (unsorted[i] >= unsorted[j] && i <= j) 
     { 
      swap(unsorted[i], unsorted[j]); 
      i++; 
      j--; 
     } 
    } while (i < j); 

    if (left < j) 
     quickSort(unsorted, left, j); 
    if (i < right) 
     quickSort(unsorted, i, right); 
} 

Answer 1

你没长1

得到那个工作的阵列上测试你的函数，然后尝试长度的数组2.

一旦这样的工作，有一个很好的机会，它会当你给它长度的阵列工作3.

编辑：

奖励用于包括可再现的例子。

此代码在递归之前失败。第一步是选择一个pivot元素并移动一些元素，直到pivot元素不小于它的左边任何一个，并且不超过它的右边的任何元素。你的代码失去了它认为哪个元素是pivot元素的轨道;它掉出元素，但似乎认为位置仍然是关键。尝试使用铅笔和纸制作算法，你会明白我的意思。

Answer 2

没有看到swap，我的第一直觉是你的swap按值接受它的参数。即它交换两个副本，而不是参数本身。

Answer 3

此检查觉得奇怪，我

while (i == pivot || j == pivot) 

是不是应该至少

while (i != pivot && j != pivot) 

附：我认为这不会是唯一的问题，但一开始...

Answer 4

哦，亲爱的。我很抱歉乔，但事情看起来不太适合你的代码。它需要许多计算血管手术，即使如此，我也不确定它会如何。让我们来写一个处方，我会让你使用手术刀：

1. 如果left> = right，则返回。不要惹一个元素的数组。
2. 用你最左边的元素交换你的元素（最右边的也很好，但我必须选择一个）。最后，您会将其交换到分区之间的正确位置。您可以通过将最左边的元素（包含您的透视图）与最左边的分区的最右边元素交换来做到这一点，如下一步所示。

3. 现在我们需要进行分区。让我们来做一个我们能想到的最简单的分区。下面是我刚刚开始使用quicksort时建议的一个：[ < pivot | >= pivot | unsorted ]。这是我们每一步都想要的不变性。一开始，所有东西都在未分类的分区中。最后，未分类的分区中将没有任何内容。我们应该怎么做？

   1. 从阵列中的left+1到right环路。
   2. 如果元素小于主元，我们用正确的交换将它添加到[ < pivot ]分区（我留给你 - 你会想要跟踪左边两个分区之间的边界）。如果不是，我们继续前进。
4. 将主元放置到位后，您的阵列应看起来像[ < pivot | pivot | >= pivot ]。快速排列最左边和最右边的分区和事物应该真的在查找这个代码。

尝试像[ < pivot | unsorted | >= pivot ]分区（如果正确完成，速度会更快）等更加奇妙的事物。我认为你目前的实现是试图进行这种分区，但除非我或j指向一个等于主元的元素，否则不会进行任何交换。这种分区比较棘手，我建议我们在进入任何种族之前给你的代码一个脉冲。

这会希望能够让你的代码变得有形，但它只会是一个非常基本的快速排序。您应该研究Bentley-McIlroy分区和选择方法以使其更加先进。