C++快速排序的递归实现—

C++快速排序的递归实现——Leetcode

2023-06-26 21:03:51 深夜i -- --

C++ 快速排序递归实现 Leetcode 算法

快速排序是一种经典的排序算法，可以在较短的时间内对大规模的数据进行排序。在Leetcode上，我们可以使用C++语言来实现快速排序。

快速排序的基本思想是：选择一个基准值，将数据分成两部分，使得左边的数据小于等于基准值，右边的数大于等于基准值，然后递归地进行排序。

我们可以利用C++语言的递归特性，快速实现快速排序。首先，我们需要实现一个分割函数，用来将数据分成左右两部分：


int partition(vector<int>& nums, int start, int end) {
  int p = nums[start], i = start + 1, j = end;
  while (i <= j) {
    if (nums[i] < p) {
      i++;
    } else if (nums[j] >= p)
      j--;
     else {
      swap(nums[i++], nums[j--]);
    }
  }
  swap(nums[start], nums[j]);
  return j;
}

上述代码中，我们选择第一个元素作为基准值，利用双指针的方法进行分割，然后将基准值放到分割的位置，最终返回基准值的下标。

接下来，我们就可以递归地进行快速排序了：


void quickSort(vector<int>& nums, int start, int end) {
  if (start >= end) {
    return;
  }
  int p = partition(nums, start, end);
  quickSort(nums, start, p - 1);
  quickSort(nums, p + 1, end);
}

上面的代码表示，如果起始位置大于等于结束位置，则直接返回。否则，进行一次分割，然后递归地对左右两部分进行快速排序。

最后，我们只需要在主函数中调用快速排序函数即可：


int main() {
  vector<int> nums = {5, 1, 8, 2, 7, 3};
  quickSort(nums, 0, nums.size() - 1);
  for (int num : nums) {
    cout << num << " ";
  }
  return 0;
}

上面的代码就可以对给定的数据进行排序，并输出排序结果。

总体来说，使用C++语言实现快速排序非常简单。只需要递归地调用分割函数和排序函数即可。不过需要注意的是，我们需要选择一个合适的基准值。对于极端情况下分割的不平衡，可以选择随机化快速排序。

上一篇: idea打包java可执行jar包

下一篇: "C++中的栈和堆区别与应用"

评论区

()

相似文章