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

快速排序C++实现

2023-07-06 06:38:28 深夜i -- --

快速排序 C++ 实现

快速排序是一种高效、经典的排序算法，常用于处理大规模数据。本文将介绍使用C++实现快速排序的方法。

## 快速排序的基本思想

快速排序是通过分治的思想实现排序的，具体流程如下：

1. 选取一个元素作为基准值（一般选取第一个元素），将数组分成左右两个子数组。

2. 对左右子数组进行快速排序，递归处理。

3. 将左、中、右三个子数组合并成一个有序的数组。

## C++实现快速排序

下面是使用C++实现快速排序的代码：


#include <iostream>
using namespace std;
void quickSort(int arr[], int left, int right) {
  if (left >= right) return;
  int i = left, j = right;
  int pivot = arr[left];
  while (i < j) {
    while (i < j && arr[j] >= pivot) j--;
    if (i < j) arr[i++] = arr[j];
    while (i < j && arr[i] <= pivot) i++;
    if (i < j) arr[j--] = arr[i];
  }
  arr[i] = pivot;
  quickSort(arr, left, i - 1);
  quickSort(arr, i + 1, right);
}
int main() {
  int arr[] = { 5, 3, 8, 4, 2, 7, 1, 10 };
  int n = sizeof(arr) / sizeof(arr[0]);
  quickSort(arr, 0, n - 1);
  for (int i = 0; i < n; i++)
    cout << arr[i] << " ";
  cout << endl;
  return 0;
}

在使用该程序时，将数组、数组长度、排序的起始索引值作为参数传递给`quickSort`函数。`quickSort`函数中的变量`i`和`j`初始化分别为数组的左右两端，而`pivot`则为基准值，选择的一般是左端元素。从右端开始向左扫描，找到第一个小于`pivot`的元素，然后从左端开始向右扫描，找到第一个大于`pivot`的元素，交换它们的位置。重复这个过程，直到左右指针相遇，将这个位置与`pivot`交换，并返回这个位置。再递归左右两个子数组进行排序，直到数组有序。

## 快速排序的优缺点

快速排序的时间复杂度为O(nlogn)，空间复杂度为O(1)，是一种快速而高效的排序算法，运用范围非常广泛。然而，快速排序也有一些缺点。首先，快速排序对于一些特殊数据，如已经有序的序列或重复元素比较多的序列，其效率会明显下降；其次，由于快速排序的分区操作是不稳定的，它不能保证相等的元素的顺序不变，这也是它不适用于某些场景的原因。由此可知，针对具体问题，选择不同的排序算法是非常必要的。

## 结论

快速排序是一种高效、经典的排序算法，使用C++实现也非常简单。虽然它有一些缺点，但是在大多数情况下，快速排序仍然是一个高效的选择。

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

下一篇: 如何通过学习C++来应对C语言考试

评论区

()

相似文章