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

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

2023-07-07 04:47:35 深夜i -- --

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

快速排序是一种常用的排序算法，它的效率比较高，应用广泛，特别是在需要排序的数据量较大的情况下，可以快速地完成排序操作。在C++中，我们可以通过类来实现快速排序算法的代码。

首先，我们需要定义一个类，用来实现快速排序算法。该类包含一个快速排序函数，以及一个用来交换两个元素的函数。下面是类的定义代码：


class QuickSort {
public:
  void quicksort(int[], int, int);
private:
  void swap(int*, int*);
};

在该类中，定义了一个public类型的快速排序函数quicksort，它接受三个参数，分别为需要排序的数组、数组的第一个元素的下标、数组的最后一个元素的下标。该函数的作用是将输入的数组按升序排列。另外，类中还定义了一个private类型的swap函数，它接受两个参数，分别为需要交换的两个元素的地址，该函数用来交换两个元素的值。

接下来，我们来看一下快速排序函数的实现。快速排序的基本思想是通过一趟排序将待排序的数据分成两部分，其中一部分的所有元素均比另一部分的所有元素小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行直到整个序列有序。下面是快速排序函数的代码实现：


void QuickSort::quicksort(int array[], int left, int right) {
  if(left >= right) {
    return;
  }
  int pivot = array[(left + right) / 2];
  int i = left, j = right;
  while(i <= j) {
    while(array[i] < pivot) {
      i++;
    }
    while(array[j] > pivot) {
      j--;
    }
    if(i <= j) {
      swap(&array[i], &array[j]);
      i++;
      j--;
    }
  }
  if(left < j) {
    quicksort(array, left, j);
  }
  if(i < right) {
    quicksort(array, i, right);
  }
}

在该函数中，首先判断左右下标是否相同，如果相同则说明已经排好序，直接返回。然后取pivot值，将数组分为两部分，使得一部分的所有元素均比pivot小，而另一部分的所有元素均比pivot大。接着，将i指针从左向右移动，找到第一个不小于pivot的元素；将j指针从右向左移动，找到第一个不大于pivot的元素；交换array[i]和array[j]，并依次移动i和j，直到i不小于j为止。然后，递归执行对左右两部分的快速排序操作。

最后，我们来看一下swap函数的代码实现：


void QuickSort::swap(int* a, int* b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

该函数接受两个整型指针作为参数，交换它们所指的两个元素的值。

综上所述，通过上述的代码实现，我们可以很方便地使用快速排序算法对数组进行排序。

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

下一篇: C++6.0软件下载

评论区

()

相似文章