C++快速排序实现降序排列 |21xrx.com

C++快速排序实现降序排列

2023-07-05 10:30:54 深夜i -- --

C++ 快速排序实现降序排列

快速排序是一种高效的排序算法，它的实现可以使用C++语言来完成。在快速排序中，通常采用递归的方式对数组进行分割和排序。该算法的时间复杂度为O(nlogn)，是十分快速的。

快速排序是一种不稳定的排序算法，它的基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分的所有记录均比另一部分小，然后再分别对这两部分记录进行排序，重复以上步骤直到整个序列有序为止。

实现降序排列需要在快速排序的基础上进行一些修改。在快速排序的过程中，选取的基准数默认是比较小的，对于降序排列来说，我们需要选择比较大的基准数，并将大于基准数的数放在左边，小于基准数的数放在右边。

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


void quickSort(int a[], int left, int right){
  int i, j, temp;
  int pivot = a[(left + right) / 2]; // 选择基准数
  i = left;
  j = right;
  while(i <= j){
    while (a[i] > pivot) i++; // 找到左边第一个小于基准数的
    while (a[j] < pivot) j--; // 找到右边第一个大于基准数的
    if(i <= j){ // 交换两者的位置
      temp = a[i];
      a[i] = a[j];
      a[j] = temp;
      i++;
      j--;
    }
  }
  if(left < j) quickSort(a, left, j); // 递归调用
  if(i < right) quickSort(a, i, right);
}

在上述代码中，我们通过选择基准数并交换数的位置来实现快速排序。在代码中可以看到，递归地调用quickSort函数可以将整个数组进行排序，而在每一次递归中选择的基准数不同，并且位置也不同，这使得快速排序可以更加灵活和高效。

需要注意的是，在上述快速排序代码中，我们并没有进行降序排列，因此要将数组降序排序，我们需要在选择基准数时，选择最大的数作为启示位置。以下是实现降序排列的代码：


void quickSortDescend(int a[], int left, int right){
  int i, j, temp;
  int pivot = a[(left + right) / 2];
  int start = right; // 新增开始位置
  i = left;
  j = right;
  while(i <= j){
    while (a[i] < pivot) i++;
    while (a[j] > pivot) j--;
    if(i <= j){
      temp = a[i];
      a[i] = a[j];
      a[j] = temp;
      i++;
      j--;
    }
  }
  // 修改递归调用位置
  if(left < j) quickSortDescend(a, left, j);
  if(i < start) quickSortDescend(a, i, start);
}

可以看到，在快速排序降序排列代码中，我们只需要修改了选择基准数和交换数的位置的方法，而其他的都与普通快速排序相同。C++快速排序实现降序排列的代码就是这样。

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

下一篇: C++编译小游戏——从入门到精通

评论区

()

相似文章