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

C++实现快排算法

2023-09-12 01:27:00 深夜i -- --

C++ 快排算法实现

快速排序算法是一种高效的排序算法，常用于对大量数据进行排序。它的思想是通过分治的方式将待排序的数据分成两部分，一部分小于或等于基准值，一部分大于基准值，然后递归地对两部分数据进行排序。

C++是一种广泛使用的编程语言，它提供了强大的库函数和工具来实现各种算法，包括快速排序算法。下面我将介绍如何使用C++来实现快速排序算法。

首先，我们需要定义一个函数来实现快速排序算法。函数的输入是待排序的数组和数组的起始和结束位置，输出是排好序的数组。具体的实现步骤如下：

1. 首先，我们要选择一个基准值。基准值可以是数组中的任意一个元素，一般选择数组的第一个元素。

2. 然后，我们将数组分成两部分，一部分小于或等于基准值，一部分大于基准值。为了实现这个过程，我们可以定义两个指针，一个指向数组的起始位置，一个指向数组的结束位置。我们从数组的起始位置开始，依次比较数组中的元素与基准值的大小关系，如果小于或等于基准值，则将该元素交换到起始位置的后面，然后起始位置向后移动一位。如果大于基准值，则将该元素交换到结束位置的前面，然后结束位置向前移动一位。直到起始位置与结束位置相遇为止。

3. 接下来，我们递归地对两部分数据进行排序，即对小于或等于基准值的部分和大于基准值的部分分别调用快速排序函数。

4. 最后，我们将两部分排序好的数据合并起来，即将小于或等于基准值的部分放在基准值的左边，将大于基准值的部分放在基准值的右边。

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


#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
  int pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] >= pivot)
      --high;
    
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}
void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pivotPos = partition(arr, low, high);
    quickSort(arr, low, pivotPos - 1);
    quickSort(arr, pivotPos + 1, high);
  }
}
int main() {
  int arr[] = 8;
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << "Original array: ";
  for (int i = 0; i < n; ++i) {
    cout << arr[i] << " ";
  }
  cout << endl;
  quickSort(arr, 0, n - 1);
  cout << "Sorted array: ";
  for (int i = 0; i < n; ++i) {
    cout << arr[i] << " ";
  }
  cout << endl;
  return 0;
}

上述代码定义了一个`partition`函数和一个`quickSort`函数来实现快速排序算法。`partition`函数用于将数组分成两部分，并返回基准值的位置。`quickSort`函数通过递归地调用`partition`函数来对数组进行排序。

在`main`函数中，我们首先定义一个待排序的数组`arr`，然后调用`quickSort`函数对数组进行排序。最后，我们输出排好序的数组。

这是使用C++实现快速排序算法的一个简单示例。通过理解和学习这个示例，我们可以更深入地了解快速排序算法的实现原理和C++编程的一些基本技巧。希望这篇文章对你有所帮助！

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

下一篇: 解决ffmpeg 闪退问题的方法

评论区

()

相似文章