6

这是我在实现快速排序算法时遇到的代码。你能解释一下递归是如何在这里工作的吗？

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

  /* partition */
  while (i <= j) {
        while (arr[i] < pivot)
              i++;
        while (arr[j] > pivot)
              j--;
        if (i <= j) {
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
    }
}
/* recursion */
if (left < j)
    quickSort(arr, left, j);
if (i < right)
        quickSort(arr, i, right);
}

请注意，这不是家庭作业。

4

3 回答 3

8

不确定“解释递归是如何工作的”是什么意思。但是给你：

您发布的函数需要一个整数数组和两个索引。它不会对整个数组进行排序，而只会对两个索引之间的部分进行排序，而忽略它们之外的任何内容。这意味着如果您传递第一个和最后一个索引，则相同的函数可以对整个数组进行排序，或者如果您传递的left值不是数组的第一个元素的索引和/或right不是最后一个元素的索引。

排序算法是众所周知的快速排序。作为枢轴，它使用中心元素（它也可以使用任何其他元素）。它将数组划分为子数组less than (or equal to) pivot和子数组greater than (or equal to) pivot，留下一个元素等于两个分区之间的枢轴。

然后它递归地调用自己对两个分区进行排序，但只有在必要时才会这样做（因此递归调用之前的 ifs ）。

实现工作，但在许多方面都不是最佳的，并且可以改进。以下是一些可能的改进：

  1. 如果数组足够短，则切换到另一种排序算法
  2. 选择枢轴值作为三个值的中位数（通常是第一个、最后一个和中间）
  3. 最初将一个枢轴值移出数组（将其放在第一个或最后一个位置，并将焦点减少到数组的其余部分）然后更改测试以传递等于枢轴的值以减少涉及它们的交换次数. 您将在最后进行最终交换时将枢轴值放回原处。如果您不遵循建议 2 并选择第一个/最后一个元素而不是本实现中的中间元素，这将特别有用。
于 2012-08-15T19:06:47.250 回答
4

回复晚了，但我只是添加了一些打印件，它可能会帮助遇到此问题的人理解代码。

#include<iostream>
using namespace std;

void quickSort(int arr[], int left, int right)
 {
  int i = left, j = right;
  int tmp;
  int pivot = arr[abs((left + right) / 2)];
  cout<<"pivot is"<<pivot<<endl;

  /* partition */
  while (i <= j) {
        while (arr[i] < pivot)
              i++;
        while (arr[j] > pivot)
              j--;
        if (i <= j) {
              cout<<"i and j are"<<i<<" "<<j<<"and corresponding array value is"<<arr[i]<<" " <<arr[j]<<endl;
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
              cout<<"entering first big while loop"<<endl;
         for(int i=0;i<7;i++)
    cout<<arr[i]<<" "<<endl ;
    }
}
cout<<"recursion"<<endl;

/* recursion */
if (left < j)
    quickSort(arr, left, j);

if (i< right)
        quickSort(arr, i, right);
}
int main(){
    int arr[7]= {2,3,8,7,4,9,1};
        for(int i=0;i<7;i++)
    cout<<arr[i]<<" " ;
    quickSort(arr,0,6);
    cout<<endl;
    for(int i=0;i<7;i++)
    cout<<arr[i]<<" " ;
int wait;
cin>>wait;
return 0;
}
于 2012-11-26T09:23:22.357 回答
1

Here is your answer -- in the common case both the recursive calls will be executed because the conditions above them will be true. However, in the corner case you could have the pivot element be the largest (or the smallest) element. In which case you have to make only one recursive call which will basically attempt the process one more time by choosing a different pivot after removing the pivot element from the array.

于 2012-08-15T18:52:48.120 回答