Rcpp 中的非递归快速排序

Question

我在 Rcpp:

中对这段代码使用了 recursive quick 排序算法

void Quick(NumericVector arr,int left,int right) { 
  int i=left;int j=right;
  double tmp;
  double pivot=arr[(left+right)/2];
  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--;

      }
    }
  if(left<j)
    Quick(arr,left,j);
  if(i<right)
    Quick(arr,i,right);
}


    // [[Rcpp::export]]
    NumericVector sort_quick(NumericVector A) {
      NumericVector tmp=clone(A);
       Quick(tmp,0,tmp.size()-1); 
      return tmp;
    }

如何获得 iterative 进程来加速代码？

Answer 1

在快速排序的常见迭代实现中，您使用本地数组模拟调用堆栈。完成对子数组的分区后，检查分区索引的左侧是否有元素。如果是这样，您将一对索引推到代表该子数组的 "stack" 上。然后，对分区索引右侧的子数组执行相同的操作。在循环的下一次迭代中，您从堆栈中弹出一对子数组索引，对该子数组执行分区，然后执行我上面描述的操作。

http://www.geeksforgeeks.org/iterative-quick-sort/

我不确定由此带来的性能提升是否非常显着，但它可能是某种东西。

对于非常大的输入大小，您可能会考虑做的另一件事是从向量中提取元素并将它们放入缓冲区，然后对缓冲区进行排序。访问开销，至少对于 std::vector，似乎是直接进入内存的两倍左右，因此一旦您超过某个输入大小阈值，这就变得值得了。这是我在实现并行合并排序算法时偶然发现的。