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

C++快速排序算法代码

2023-07-09 18:15:26 深夜i -- --

C++ 快速排序算法代码

C++快速排序算法是一种常见的排序算法，它的优点是速度快，适用于大数据量的排序。下面是C++快速排序算法的代码：


#include <iostream>
using namespace std;
// 快速排序函数
void quick_sort(int arr[], int left, int right) {
 int i, j, pivot;
 if (left < right) {
  i = left;
  j = right + 1;
  pivot = arr[left];
  do {
   do i++; while (arr[i] < pivot);
   do j--; while (arr[j] > pivot);
   if (i < j) swap(arr[i], arr[j]);
  } while (i < j);
  swap(arr[left], arr[j]);
  quick_sort(arr, left, j - 1);
  quick_sort(arr, j + 1, right);
 }
}
int main() {
 int arr[5] = 5;
 quick_sort(arr, 0, 4); // 调用快速排序函数
 for (int i = 0; i < 5; i++) {
  cout << arr[i] << " ";
 }
 return 0;
}

以上代码是一个简单的例子，演示如何使用C++的快速排序算法对一个数组进行排序。快速排序算法的核心代码在quick_sort函数中，这里使用了递归来实现排序。在函数中，首先定义了三个变量：i、j和pivot。其中，i和j用于指向数组中需要交换的元素，pivot是用于分割数组的基准元素。

在实现快速排序算法时，需要注意以下几点：

- 选定基准元素pivot后，将数组分为左侧和右侧两个部分。左侧部分的元素都小于pivot，右侧部分的元素都大于pivot。

- 设置两个指针i和j，分别指向左侧和右侧的第一个元素。

- i从左向右扫描，如果发现比pivot大的元素则停止，j从右向左扫描，如果发现比pivot小的元素则停止。

- 当i和j都停止时，交换arr[i]和arr[j]所指的元素。

- 循环执行以上步骤，直到i>=j。

- 最后交换基准元素pivot和arr[j]所指的元素，完成一轮排序。

- 通过递归调用quick_sort函数，对分割后的左侧和右侧部分递归执行以上步骤，直到整个数组排序完成。

快速排序算法的时间复杂度为O(nlogn)，非常适用于需要对大量数据进行排序的场景。同时，快速排序算法也是一个基础的算法，熟练掌握该算法有助于更好地理解和应用其他排序算法。

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

下一篇: 使用C++编写计算器程序

评论区

()

相似文章