21xrx.com
2024-11-22 07:06:25 Friday
登录
文章检索 我的文章 写文章
C++实现快速排序的下标排序
2023-07-07 14:59:39 深夜i     --     --
C++ 快速排序 下标排序

快速排序是一种常用的排序算法,在大数据集下表现出色。但在某些情况下,我们需要对序列进行下标排序,即按照元素原本的下标顺序对元素进行排序。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++实现快速排序的下标排序可以非常方便地排序任意类型的数组,同时保留下标信息。在需要排序后仍需要访问原数组下标信息的场合,这种方法会非常有用。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复