C++快速排序算法 |21xrx.com

C++快速排序算法

2023-07-14 20:29:09 深夜i -- --

C++语言快速排序算法分治法递归

快速排序算法是一种基于比较的排序算法，它是一种高效的、广泛应用的排序算法，也是C++程序员必须掌握的一种算法。

快速排序算法的思想非常简单，它采用分治策略，将一个大问题分解为若干个小问题，再一个个解决，最后组合在一起就解决了整个大问题。具体来说，它通过选取一个基准元素，将待排序序列分成两个子序列，其中一个序列中的元素都小于等于基准元素，另一个子序列中的元素都大于等于基准元素，然后对这两个子序列递归地应用快速排序算法，直到排序完成。

快速排序算法有多种实现方式，其中最常用的是“Hoare partition scheme”，其平均时间复杂度为O(nlogn)，空间复杂度为O(logn)，在实际应用中往往表现出很高的效率。

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


#include <iostream>
using namespace std;
// 定义快速排序函数
void quickSort(int arr[], int left, int right) {
  if (left >= right) return;    // 如果左指针大于等于右指针，直接返回
  int i = left, j = right, mid = arr[(left + right) / 2];  // 定义左右指针和中位数
  while (i <= j) {  // 开始排序
    while (arr[i] < mid) i++;  // 找到左边第一个大于等于中位数的数字
    while (arr[j] > mid) j--;  // 找到右边第一个小于等于中位数的数字
    if (i <= j) {  // 如果i指向的数字小于等于j指向的数字
      swap(arr[i], arr[j]);  // 交换两个数字
      i++; j--;  // 左指针右移，右指针左移
    }
  }
  quickSort(arr, left, j);  // 递归排序左半部分
  quickSort(arr, i, right);  // 递归排序右半部分
}
int main() {
  int arr[] = 4;  // 待排序数组
  int len = sizeof(arr)/sizeof(int);   // 数组长度
  quickSort(arr, 0, len-1);  // 调用快速排序函数
  for (int i = 0; i < len; i++) {
    cout << arr[i] << " ";  // 输出排序后的数组
  }
  return 0;
}

在上述示例代码中，我们首先定义了一个快速排序函数，接着在主函数中定义了一个待排序数组，调用快速排序函数对其进行排序，并输出排序后的数组。

快速排序算法是一种高效的排序算法，在实际应用中广泛使用。C++中的STL中也提供了快速排序算法的函数，在需要使用排序算法时，可以直接调用库函数进行排序操作。

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

下一篇: C++多边形面积计算程序

评论区

()

相似文章