21xrx.com
2024-12-22 21:01:02 Sunday
登录
文章检索 我的文章 写文章
C++的快速排序算法
2023-07-08 07:28:19 深夜i     --     --
C++ 快速排序算法 排序 分治思想

快速排序是一种基于比较的排序算法,也是C++中最为常用的排序算法之一。它通过递归地将数据分为较小的子集,并在此基础上对子集进行排序,最终得到一个完整有序的序列。快速排序的时间复杂度为O(nlog n),属于计算效率较高的算法。

快速排序算法的核心思想是分治法。它将待排序序列分为两个子序列,一个利用快速排序进行排序,另一个利用递归实现快速排序。首先,选择一个基准元素(pivot),将所有小于它的元素放在它的左侧,所有大于它的元素放在右侧。这个过程称为分区(partition)。然后对左右两个子序列分别递归地执行分区操作,直至所有子序列只有一个元素。

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


void quickSort(vector<int>& nums, int left, int right) {

  if (left >= right) return; // 边界条件,当子序列只有一个元素时结束递归

  int i = left, j = right;

  int pivot = nums[(left + right) / 2]; // 选取基准元素

  while (i <= j) { // 分区操作

    while (nums[i] < pivot) i++;

    while (nums[j] > pivot) j--;

    if (i <= j) {

      swap(nums[i], nums[j]);

      i++;

      j--;

    }

  }

  quickSort(nums, left, j); // 对左侧子序列排序

  quickSort(nums, i, right); // 对右侧子序列排序

}

在这个代码实现中,我们使用了vector类型存储待排序的数据,它是C++标准库中的容器类型,可以动态调整其大小。函数的参数left和right分别表示子序列的左右边界。

快速排序的优化方法也很多,比如三向切分、随机化等。三向切分是在分区操作时,将序列分为小于pivot、等于pivot和大于pivot的三个部分。随机化则是在选择基准元素时随机选择一个元素,以避免最坏情况的出现。

总之,快速排序是一种高效的排序算法,适用于各种数据量规模和数据分布。掌握其核心思想和实现方式,对于C++编程和算法学习都是非常重要的。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复