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

C++快速排序算法代码实现

2023-07-04 19:20:09 深夜i -- --

C++ 快速排序算法代码实现

快速排序是一种高效的排序算法，它采用分治的思想，在平均情况下时间复杂度为O(nlogn)。C++是一种广泛使用的编程语言，我们可以使用C++来实现快速排序算法。

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


#include <iostream>
#include <algorithm>
using namespace std;
int partition(int arr[], int low, int high) {
  int pivot = arr[high];
  int i = low - 1;
  for(int j=low; j<=high-1; j++) {
    if(arr[j] < pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i+1], arr[high]);
  return (i+1);
}
void quicksort(int arr[], int low, int high) {
  if(low < high) {
    int pi = partition(arr, low, high);
    quicksort(arr, low, pi-1);
    quicksort(arr, pi+1, high);
  }
}
int main() {
  int arr[] = 7;
  int n = sizeof(arr) / sizeof(arr[0]);
  quicksort(arr, 0, n-1);
  for(int i=0; i<n; i++) {
    cout << arr[i] << " ";
  }
  return 0;
}

这份代码首先定义了一个名为partition的函数，它用于将数组分成小于和大于主元素的两个部分。这里我们选择数组的最后一个元素作为主元素，但是主元素也可以是数组的中间元素等。

快排函数quicksort通过递归将数组分成越来越小的子数组，并将它们分别排序。当子数组的大小为1时，递归结束。

在主函数中，我们定义了一个整型数组arr，将其传递给quicksort函数进行排序。排序完成后，我们输出排序后的数组。

对于一个长度为n的数组，快速排序算法的时间复杂度为O(nlogn)（平均情况下），因此它是一种非常高效的排序算法。C++语言中提供了快速排序算法的STL实现（std::sort），但是自己实现快速排序算法可以更好地掌握算法的原理和实现方式。

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

下一篇: C++期末考试题库

评论区

()

相似文章