C++实现快速排序 |21xrx.com

C++实现快速排序

2023-07-04 23:36:49 深夜i -- --

C++ 实现快速排序算法数组排序

快速排序是一种高效的排序算法，它被广泛用于计算机科学领域。C++作为一种强有力的编程语言，可以实现快速排序。

快速排序的基本思想是将待排序的序列分成两个子序列，递归地对这两个子序列进行排序，直到整个序列有序为止。它的核心是分治法和递归算法。具体实现过程如下：

1. 选择一个基准元素，通常是列表中的第一个元素。

2. 分割原始列表，将此基准元素从列表中分割出来。

3. 遍历整个列表，将小于基准元素的元素放在一个新的列表中，将大于基准元素的元素放在另一个新列表中。

4. 对于这两个新列表，递归地重复以上步骤直到列表为空。

5. 将小于基准元素的列表和大于基准元素的列表合并。

C++ 实现快速排序需要用到递归的思想，即将一个大的复杂问题分化为小的问题，进行逐层解决。下面是一个例子：


#include <iostream>
#include <vector>
using namespace std;
void quick_sort(vector<int>& nums, int start, int end) {
  if (start >= end)
    return;
  
  int left = start;
  int right = end;
  int pivot = nums[start]; //设当前序列的第一个元素为基准元素
  while (left < right) {
    while (left < right && nums[right] >= pivot)
      right--;
    
    nums[left] = nums[right];
    while (left < right && nums[left] <= pivot) {
      left++;
    }
    nums[right] = nums[left];
  }
  nums[left] = pivot; // 基准元素归位
  quick_sort(nums, start, left - 1); // 递归调用
  quick_sort(nums, left + 1, end); // 递归调用
}
int main() {
  vector<int> nums = 8;
  quick_sort(nums, 0, nums.size() - 1);
  for (int num : nums)
    cout << num << " ";
  
  return 0;
}

这里定义了一个 quick_sort 函数，它的参数 nums 是待排序的数组，start 和 end 分别是数组的起点和终点。在 quick_sort 函数中，首先判断序列长度是否大于 1，如果不大于 1，就不需要排序了。接下来，将序列中的第一个元素作为基准元素 pivot，并将 left 置为起点和 right 置为终点。接着，利用 while 循环找到左侧>=pivot的数和右侧<=pivot的数，然后交换，将基准元素放到正确的位置。

递归调用 quick_sort 函数将左右两个列表分别排序。最后，函数返回一个有序的列表。

使用 C++实现快速排序可以使程序更高效、更简洁。当然，快速排序也可以用于对其他类型的数据进行排序，如字符串、浮点数等。

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

下一篇: C++调用Java代码

评论区

()

相似文章