为什么“快速排序”算法的这两种变体在性能上有如此大的差异？

Question

最初，我想出了一些排序算法以C ++进行编码以进行实践。人们告诉我这是非常低效的（实际上，对数百个数字进行排序大约需要10秒钟）。该算法是记住向量中的第一个元素（“枢轴”），然后解析每个其他元素，然后将每个元素移到枢轴的左侧（如果较小），否则将不执行任何其他操作。这会将列表分成较小的列表进行排序；其余的通过递归完成。

因此，现在我知道将列表分为两部分并进行这样的递归本质上是快速排序的工作（尽管如何进行分区有很多变体）。我不明白为什么我的原始代码效率低下，所以我写了一个新的代码。有人提到这是因为insert（）和delete（）函数，所以我确保不要使用那些，而要使用swap（）。

旧（慢）：

void sort(vector<T>& vec){
  int size = vec.size();
  if (size <= 1){ //this is the most basic case
    return;
  }

  T pivot = vec[0];
  int index = 0; //to help split the list later
  for (int i = 1; i < size; ++i){ //moving (or not moving) the elements
    if (vec[i] < pivot){
      vec.insert(vec.begin(), vec[i]);
      vec.erase(vec.begin() + i + 1);
      ++index;
    }
  }

  if (index == 0){ //in case the 0th element is the smallest
    vec.erase(vec.begin());
    sort(vec);
    vec.insert(vec.begin(), pivot);
  }
  else if(index == size - 1){ //in case the 0th element is the largest
    vec.pop_back();
    sort(vec);
    vec.push_back(pivot);
  }

  //here is the main recursive portion
  vector<T> left = vector<T>(vec.begin(), vec.begin() + index);
  sort(left);
  vector<T> right = vector<T>(vec.begin() + index + 1, vec.end());
  sort(right);

  //concatenating the sorted lists together
  left.push_back(pivot);
  left.insert(left.end(), right.begin(), right.end());

  vec = left;
}

新（快速）：

template <typename T>
void quickSort(vector<T>& vec, const int& left, const int& right){
  if (left >= right){ //basic case
    return;
  }
  T pivot = vec[left];
  int j = left; //j will be the final index of the pivot before the next iteration

  for (int i = left + 1; i <= right; ++i){
    if (vec[i] < pivot){
      swap(vec[i], vec[j]); //swapping the pivot and lesser element
      ++j;
      swap(vec[i], vec[j]); //sending the pivot next to its original spot so it doesn't go the to right of any greater element
    }
  }

  //recursion
  quickSort(vec, left, j - 1);
  quickSort(vec, j + 1, right);
}

性能上的差异是疯狂的；新版本可以在不到一秒钟的时间内对成千上万个数字进行排序，而第一个数字不能用100个数字进行排序。究竟到底要使用多少ase（）和insert（）来减慢速度？确实是导致瓶颈的“ ease（）”和“ insert（）”，还是我遗漏了其他东西？

Answer 1

首先，是的，insert()而且erase()会比慢得多swap()。

insert()在最佳情况下，将要求您将插入向量中的点之后的每个元素移到向量中的下一个点。想一想，如果您将自己推入拥挤的人群中间，会发生什么情况-您身后的每个人都必须退后一步为您腾出空间。在最坏的情况下，由于插入向量会增加向量的大小，因此向量可能会在其当前内存位置中用完空间，从而导致整个向量（逐个元素）被复制到一个新的空间中，该空间可以容纳新插入的项目。当向量中间的元素为erase()'d时，其后的每个元素都必须复制并向上移动一个空格；就像排成一排的每个人都落后一步一样。相比下，swap() 仅移动被交换的两个元素。

除此之外，我还注意到两个代码示例之间的另一个重大效率改进：

在第一个代码示例中，您具有：

vector<T> left = vector<T>(vec.begin(), vec.begin() + index);
sort(left);
vector<T> right = vector<T>(vec.begin() + index + 1, vec.end());
sort(right);

它使用C ++向量的范围构造函数。每次代码到达这一点时，它在创建left和right时都会遍历整个vec元素，并将每个元素一一复制到两个新向量中。

在较新的，更快速的代码，没有元件被不断复制到新的向量; 整个算法发生在原始编号所在的确切存储空间中。