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

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

2023-06-30 09:09:45 深夜i 14 0

C++ 快速排序算法代码

快速排序算法是一种经典的排序算法，也是C++程序员经常使用的排序算法之一。和其他排序算法不同，快速排序采用了一种“分治”策略，将待排序数据集递归地分成两个子序列，然后对子序列进行排序，最终将整个序列排序完成。

下面是一个使用C++语言实现的快速排序算法的代码，包括了快速排序的递归和非递归两种实现方式。其中，递归实现是快速排序的经典实现方式，而非递归实现则可以避免递归带来的栈溢出问题。

#include <iostream>
#include <stack>
using namespace std;
int Partition(int a[], int low, int high)
{
  int pivot = a[low];  // 用子序列的第一个元素作为基准元素
  while (low < high) {
    while (low < high && a[high] >= pivot) high--;
    a[low] = a[high];
    while (low < high && a[low] <= pivot) low++;
    a[high] = a[low];
  }
  a[low] = pivot;
  return low;
}
// 递归实现
void QuickSort(int a[], int low, int high)
{
  if (low < high) {
    int pivotPos = Partition(a, low, high);
    QuickSort(a, low, pivotPos - 1);
    QuickSort(a, pivotPos + 1, high);
  }
}
// 非递归实现
void QuickSortNorec(int a[], int low, int high)
{
  stack<int> s;
  s.push(low);
  s.push(high);
  while (!s.empty()) {
    int r = s.top();
    s.pop();
    int l = s.top();
    s.pop();
    if (l < r) {
      int pivotPos = Partition(a, l, r);
      s.push(l);
      s.push(pivotPos - 1);
      s.push(pivotPos + 1);
      s.push(r);
    }
  }
}
int main()
{
  int a[] = 97;
  int n = sizeof(a) / sizeof(int);
  QuickSort(a, 0, n - 1);
  // QuickSortNorec(a, 0, n - 1); // 非递归实现
  for (int i = 0; i < n; i++) {
    cout << a[i] << " ";
  }
  return 0;
}

以上是使用C++编写的快速排序算法的代码，可以看到，代码还比较简单，容易理解。如果你对C++有一定的编程基础，那么学习和使用快速排序算法应该会非常容易。

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

下一篇: C++中的函数指针执行方法

评论区

相似文章