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

C++ 实现快速排序算法

2023-07-11 22:08:30 深夜i -- --

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

快速排序算法是一种常用的排序算法，它的时间复杂度通常为 O(n log n)，效率比较高。在 C++ 中，使用递归方式实现快速排序算法非常简单。

首先，我们需要定义一个 partition 函数来将数组分成两个部分，比指定元素小的放在左边，比指定元素大的放在右边。代码如下：


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);
  }
}

最后，我们可以调用 quickSort 函数来排序整个数组。代码如下：


int main() {
  int arr[] = 7;
  int n = sizeof(arr)/sizeof(arr[0]);
  quickSort(arr, 0, n-1);
  cout << "Sorted array: \n";
  printArray(arr, n);
  return 0;
}

以上代码实现了一个基本的快速排序算法，并可以进行测试。如果需要对其他类型的数据进行排序，也可以将以上代码做出相应的修改即可。

总之，C++ 实现快速排序算法非常简单，只需要编写一个 partition 函数和一个递归的快速排序函数即可。使用快速排序算法进行排序可以大大提高排序的效率，是一种非常实用的算法。

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

下一篇: C++中的&符号表示什么？

评论区

()

相似文章