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

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

2023-07-04 22:13:52 深夜i 17 0

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

快速排序是一种常用的排序算法，在许多的编程语言中都有对应的实现方式。C++作为一门强类型的编程语言，其面向对象的特性使得利用类来实现快速排序算法成为可能。

以下是一个使用类实现快速排序算法的C++代码：

#include <iostream>
class QuickSort {
 public:
  void sort(int arr[], int left, int right) {
    if (left < right) {
      int pivot = partition(arr, left, right);
      sort(arr, left, pivot - 1);
      sort(arr, pivot + 1, right);
    }
  }
 private:
  int partition(int arr[], int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
      if (arr[j] < pivot) {
        i++;
        swap(arr[i], arr[j]);
      }
    }
    swap(arr[i + 1], arr[right]);
    return i + 1;
  }
  void swap(int& a, int& b)
    int temp = a;
    a = b;
    b = temp;
  
};
int main() {
  int arr[] = 4;
  int n = sizeof(arr) / sizeof(arr[0]);
  QuickSort qs;
  qs.sort(arr, 0, n - 1);
  for (int i = 0; i < n; i++) {
    std::cout << arr[i] << " ";
  }
  std::cout << std::endl;
  return 0;
}

在这个代码里，我们定义了一个名为QuickSort的类，其中包含一个sort方法进行排序，和一个partition方法用于将数组分为两个部分，并返回分界点的下标。

类方法sort的实现非常简单，它接收一个数组、一个左边界和一个右边界作为参数。如果左边界小于右边界，则继续进行分治，将数组分为两个部分，并通过pivot（分界点）将数组分割。然后用递归方式重复过程，直到左边界等于右边界时停止。

类方法partition的实现相当于一个单独的快速排序步骤。在这种情况下，我们选择数组的最后一个元素作为pivot，将数组分为两个部分。其余的工作就和基于数组的快速排序算法一样了！

这个基于类的快速排序算法绝对是一个很好的练习机会，能够帮助我们更好地理解类的定义和使用。同时也巩固了快速排序算法的工作流程，使我们更能熟练地运用到其他的问题中。

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

下一篇: C++交互设计心得：高效编程的关键要素

评论区

相似文章