C++非递归实现快速排序 |21xrx.com

C++非递归实现快速排序

2023-07-10 19:39:04 深夜i -- --

C++ 非递归快速排序

快速排序（Quicksort）是一种常用的高效的排序算法，它可以将一组未排序的数据进行排序。在C++中，快速排序可以通过递归的方式实现，但是如果待排序的数据过大，递归会导致栈溢出，因此我们可以采用非递归的方式来实现快速排序。

快速排序的基本思想是先选择一个基准数，然后将序列中的元素按照这个基准数进行划分，小于基准数的在左边，大于基准数的在右边，然后对左边和右边的序列分别进行快速排序，直到整个序列都有序。

在非递归实现中，我们可以使用栈来模拟递归的过程。具体实现过程如下：

首先将最初的序列压入栈中。然后循环弹出栈元素，进行划分操作，将小于基准数的压入栈底，大于基准数的压入栈顶，然后继续循环，直到栈为空为止。

下面是快速排序的C++非递归实现代码：


#include <iostream>
#include <stack>
using namespace std;
void quickSort(int arr[], int low, int high) {
  stack<int> st;
  st.push(low);
  st.push(high);
  while (!st.empty()) {
    int h = st.top();
    st.pop();
    int l = st.top();
    st.pop();
    int pivot = arr[(l + h) / 2];
    int i = l, j = h;
    while (i <= j) {
      while (arr[i] < pivot) i++;
      while (arr[j] > pivot) j--;
      if (i <= j) {
        swap(arr[i], arr[j]);
        i++;
        j--;
      }
    }
    if (l < j) {
      st.push(l);
      st.push(j);
    }
    if (i < h) {
      st.push(i);
      st.push(h);
    }
  }
}
int main() {
  int arr[] = 8;
  int n = sizeof(arr)/sizeof(arr[0]);
  quickSort(arr, 0, n - 1);
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
  return 0;
}

在这段代码中，我们定义了一个栈st，将序列的左右边界分别压入栈中，然后进行循环。在每次循环中，我们首先弹出栈顶元素，然后进行划分操作。如果左右两边序列的长度大于1，将左右序列的边界压入栈中，这样就完成了一次将序列划分的操作。

总之，通过非递归的方式实现快排，可以大大减少栈溢出的风险，提高程序的鲁棒性和健壮性。

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

下一篇: 如何生成C++密钥

评论区

()

相似文章