c++ - 快速排序显然是选择o(n^2)当左或最右元素作为枢轴时

Question

那么，嗯，我正在尝试学习快速排序并已为其实现了以下代码。但是，当我将最左边或最右边的元素作为枢轴时，它似乎在 O(n^2) 而不是 O(nlogn) 中运行......

我无法弄清楚我的代码有什么问题，但我很可能犯了一些非常基本的愚蠢错误；谁能帮我解释我哪里出错了？

提前致谢!这是我的代码:

   #include <iostream>
   #include <vector>

   typedef  int64_t  int64;

   int64 numberOfComparisons;

   using namespace std;
   int partitionAroundPivot(vector<int64>& a, int l, int r) {

   numberOfComparisons = numberOfComparisons + (r - l) - 1 ;


   int ppos;
   ppos = l;


   int64 p = a[ppos]; //Gives pivot

   if(ppos != l)
       swap(a[ppos], a[l]);

   int i = l + 1, j;
   for(j = l + 1; j <= r; j++){
       if(a[j]  < p)
       {
           swap(a[j], a[i]); //Swap with leftmost element bigger than pivot, i.e. v[i]
        i++;
       }

   }
   //Now pivot needs to go to its proper place
   swap(a[l], a[i - 1]);

   return ppos; //WRONG, will return l always, need to return i-1

   }
   void quickSort(vector<int64>& a, int l, int r) //Inplace so no return stuff
   {
   if( r - l <= 0)
       return ;



   int pivotPosition =  partitionAroundPivot(a, l, r);
   cout << "Called Qsort with positions  l " <<l << "   r  " << r << " Pivot pos " << pivotPosition <<  endl;

   for (int i = l; i < r; i++)
       cout << a[i] <<"  " ;

   cout << endl;
   quickSort(a, l              , pivotPosition - 1 );
   quickSort(a, pivotPosition + 1  , r                 );

}

int main() {

 vector<int64> x  = {3, 2, 1, 8, 6, 7, 6, 4};
 quickSort(x, 0, x.size() -1);

 return 0;
}

部分输出如下:

Called Qsort with positions  l 0   r  9 Pivot pos 0
1  2  3  4  6  10  9  5  7
Pivot: 2
Called Qsort with positions  l 1   r  9 Pivot pos 1
2  3  4  6  10  9  5  7
Pivot: 3

编辑:我问这个的部分原因是因为我应该计算理论上完成的总比较次数，我只是使用(每个分区调用的子数组大小 - 1)作为值(实际的会有所不同，我知道因为只有部分比较实际上发生了)。这可以在上面的 numberOfComparisons 变量中看到。

现在的问题是，为了对 100 个数字进行排序，全部从 1 到 100，没有唯一的并且大部分是随机的，它显示计算次数为 4851，接近 100*99/2 又名 n*(n-1)/2 其中 n = 100。这让我相信它正在执行 O(n^2) 时间。这是正确的...？

EDIT2:毕竟我太蠢了。 partitionAroundPivot 总是返回子数组的第一个位置，导致其中一个拆分为零长度子数组，另一个拆分为数组的其余部分。我需要传回a[l]实际去的位置而不是l； i-1 在这种情况下。吸取教训，我想。

非常感谢你们的帮助，伙计们!

Answer 1

Qucksort 的复杂度为 O(n log n)，但平均而言，最坏情况下为 O(n^2)，最佳情况下为 O(nlogn)。获得良好效率的最重要方面是选择一个好的支点。

在您的程序中，您选择了最差的主元之一，因为如果您选择第一个或最后一个，在有序(或反向排序) vector 的情况下，您的算法在最坏情况下效率最高。

这就是为什么您必须考虑您的算法来选择枢轴的原因。最常用的方法之一是选择三个元素的中位数，例如第一个、中间和最后一个元素。因此，应用于有序 vector 的算法是 O(nlogn)。

更新:复杂性取决于增长情况，而不是具体情况。事实上，对于特定大小的问题，您可能具有非常高的值，而当问题大小变得非常大时，配置文件的增加会更加平稳。在检查任何东西之前，使用达到非常大 n 的几个单独值运行程序。