C++ 快速排序代码的两种实现方式 |21xrx.com

C++ 快速排序代码的两种实现方式

2023-07-07 17:48:35 深夜i -- --

C++ 快速排序代码实现递归迭代

快速排序是一种高效的排序算法，其时间复杂度为 O(nlogn)。在 C++ 中，我们可以使用两种方式来实现快速排序的代码，分别是递归实现和迭代实现。

递归实现：

首先来看递归实现方式的代码，其基本思路是将数组分为两部分，分别对其进行排序，然后合并两部分。具体实现如下：


void quicksort(int arr[], int left, int right) {
  if (left < right) {
    int pivot = arr[(left + right) / 2];
    int i = left - 1;
    int j = right + 1;
    while (true) {
      while (arr[++i] < pivot);
      while (arr[--j] > pivot);
      if (i >= j) break;
      swap(arr[i], arr[j]);
    }
    quicksort(arr, left, i - 1);
    quicksort(arr, j + 1, right);
  }
}

在这个实现中，我们使用了递归的方式来将数组划分为左子数组和右子数组，并对它们分别进行排序。在每一次递归调用中，我们都会选取一个中心点 pivot，将小于 pivot 的元素放到左边，将大于 pivot 的元素放到右边，最终将数组排好序。

迭代实现：

除了递归实现，我们还可以使用迭代的方式来实现快速排序。相比于递归实现，迭代实现方式的递归深度更浅，运行效率更高。具体实现如下：


void quicksort(int arr[], int len) {
  int left = 0;
  int right = len - 1;
  int stack[len - 1];
  int top = -1;
  stack[++top] = left;
  stack[++top] = right;
  while (top >= 0) {
    right = stack[top--];
    left = stack[top--];
    int i = left - 1;
    int j = right + 1;
    int pivot = arr[(left + right) / 2];
    while (true) {
      while (arr[++i] < pivot);
      while (arr[--j] > pivot);
      if (i >= j) break;
      swap(arr[i], arr[j]);
    }
    if (left < j) {
      stack[++top] = left;
      stack[++top] = j;
    }
    if (i < right) {
      stack[++top] = i;
      stack[++top] = right;
    }
  }
}

在这个实现中，我们使用了一个栈来存储每一个待排序的子数组的左右端点。我们不断地从栈中弹出待排序的子数组，选取一个中心点 pivot，将小于 pivot 的元素放到左边，将大于 pivot 的元素放到右边，最终将数组排好序。

总结：

无论是递归实现还是迭代实现，快速排序都是一种非常高效的排序算法。在实际编程中，我们可以根据具体的情况来选择使用哪种方式来实现快速排序。无论采用哪种方式，关键在于选取合适的中心点 pivot，以确保排序效率的同时，不会引起死循环等错误。

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

下一篇: 有效的现代C++ GitHub

评论区

()

相似文章