c++ - 需要有关(尝试)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 到 200 之间的 100 个随机值填充的数组。

抱歉更新缓慢。 至于代码，我重写了大部分。 这就是现在的样子:

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 时，它不起作用。

解决了。删除了很多代码，使其变得更加简单，但至少它可以工作。 甚至不知道你是否可以再称其为快速搜索，但这是最终版本:

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 的数组时，它很有可能会起作用。

编辑:

感谢您提供了一个可重现的示例。

此代码在递归之前失败。第一步是选择一个枢轴元素并移动一些元素，直到该枢轴元素不小于其左侧的任何元素且不大于其右侧的任何元素。您的代码无法追踪它认为是枢轴元素的元素；它交换了枢轴元素，但似乎认为相同的位置仍然是枢轴。尝试用铅笔和纸来完成到目前为止的算法，您就会明白我的意思。