C++快速排序代码：双路和三路分区法 |21xrx.com

C++快速排序代码：双路和三路分区法

2023-07-05 00:46:56 深夜i -- --

C++ 快速排序双路分区法三路分区法代码

C++是一种高效且广泛使用的编程语言，也是许多程序员喜欢的语言。其中，快速排序是C++编程中的一个常见算法，它能够帮助我们迅速排序数据，并提供了两种常见的分区方法，即双路分区法和三路分区法。

首先，双路分区法是快速排序的一种基础方法。它用两个指针 i 和 j 分别从数组的左侧和右侧向中间遍历数组，并逐步将所有小于或等于基准元素的元素移到数组的左侧，大于基准元素的元素移到右侧。最后，将基准元素插入到数组中间。下面是双路分区法的代码实现：


void quickSort(int arr[], int left, int right) {
  if(left >= right)
    return;
  int i = left, j = right;
  int temp = arr[left];
  while(i < j) {
    while(i < j && arr[j] >= temp)
      j--;
    arr[i] = arr[j];
    while(i < j && arr[i] <= temp)
      i++;
    arr[j] = arr[i];
  }
  arr[i] = temp;
  quickSort(arr, left, i - 1);
  quickSort(arr, i + 1, right);
}

以上是使用双路分区法实现的快速排序代码，它能够快速地排序数组，并且在大多数情况下表现出优越的算法性能。

然而，在某些情况下，双路分区法可能表现不佳，因为它可能会出现特定的数据重复。为了解决这个问题，我们引入了另一种分区方法，即三路分区法。三路分区法将数组分成三部分，其中一部分存放相等的元素，另外两部分存放小于和大于基准元素的元素。下面是三路分区法的代码实现：


void quickSort(int arr[], int left, int right) {
  if(left >= right)
    return;
  int i = left + 1, lt = left, gt = right;
  int temp = arr[left];
  while(i <= gt) {
    if(arr[i] < temp) {
      swap(arr[i++], arr[lt++]);
    } else if(arr[i] > temp) {
      swap(arr[i], arr[gt--]);
    } else {
      i++;
    }
  }
  quickSort(arr, left, lt - 1);
  quickSort(arr, gt + 1, right);
}

以上是使用三路分区法实现的快速排序代码，可以较好地处理元素重复的情况，并在大数据集上表现出相对优良的性能表现。

总之，快速排序是C++编程中常见的算法，并有多种分区方法可以选择。尝试在不同数据集合上使用双路和三路分区法，以了解它们的性能差异和不同应用场景。

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

下一篇: C++ Builder 6.0中文版介绍

评论区

()

相似文章