快速排序是一种常用的排序算法，在大数据集下表现出色。但在某些情况下，我们需要对序列进行下标排序，即按照元素原本的下标顺序对元素进行排序。C++实现快速排序的下标排序可以很好地解决这个问题。

实现下标排序的方法很简单，只需要在快速排序的过程中记录排序前的下标信息，在返回结果时按照下标排序输出即可。具体实现如下：

void quicksort(vector<int>& nums, vector<int>& idxs, int left, int right) {
  if (left < right) {
    int pivotidx = rand() % (right - left + 1) + left;
    int pivot = nums[idxs[pivotidx]];
    swap(idxs[pivotidx], idxs[right]);
    int i = left;
    for (int j = left; j < right; ++j) {
      if (nums[idxs[j]] <= pivot) {
        swap(idxs[i], idxs[j]);
        ++i;
      }
    }
    swap(idxs[i], idxs[right]);
    quicksort(nums, idxs, left, i - 1);
    quicksort(nums, idxs, i + 1, right);
  }
}
vector<int> sortIndexes(vector<int>& nums) {
  vector<int> idxs(nums.size());
  for (int i = 0; i < idxs.size(); ++i) {
    idxs[i] = i;
  }
  quicksort(nums, idxs, 0, nums.size() - 1);
  return idxs;
}

在以上代码中，`quicksort()`函数是快速排序的实现，`sortIndexes()`函数将原数组按顺序排序后返回索引信息。具体而言，`quicksort()`函数中用 `idxs` 记录原数组中的下标信息，并在排序中据此交换元素以进一步排序。经过排序后，`idxs` 记录的就是原数组按下标排序后的顺序。

要使用该函数，只需要先创建一个需要进行下标排序的数组，然后调用该函数即可。例如：

vector<int> nums 2;
vector<int> sortedIdxs = sortIndexes(nums);
for (int i : sortedIdxs) {
  cout << nums[i] << " ";
}

输出为：

1 2 3 4 5 6 7 8 9

可以看到输出结果已经按原数组下标排序。

因此，C++实现快速排序的下标排序可以非常方便地排序任意类型的数组，同时保留下标信息。在需要排序后仍需要访问原数组下标信息的场合，这种方法会非常有用。

相似文章

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客