c++快速排序(附完整源码)

源代码大师

于 2021-02-09 08:37:02 发布

阅读量737

点赞数

分类专栏： C和C++算法完整教程 C和C++Everything教程

不予转载，严禁转载，违者必纠。

本文链接：https://blog.csdn.net/it_xiangqiang/article/details/113505304

版权

C和C++Everything教程同时被 2 个专栏收录

10029 篇文章 ¥99.90 ¥299.90

订阅专栏

超级会员免费看

C和C++算法完整教程

811 篇文章 ¥29.90 ¥99.00

订阅专栏

超级会员免费看

本文详细介绍了快速排序算法，包括选择轴值的重要性、代码实现、性能分析及优化方法，如三者取中法和小规模数组处理策略。快速排序在平均情况下的时间复杂度为O(nlogn)，是最优的内部排序算法之一。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

快速排序

首先选择一个轴值，小于轴值的元素被放在数组中轴值左侧，大于轴值的元素被放在数组中轴值右侧，这称为数组的一个分割(partition)。快速排序再对轴值左右子数组分别进行类似的操作
选择轴值有多种方法。最简单的方法是使用首或尾元素。但是，如果输入的数组是正序或者逆序时，会将所有元素分到轴值的一边。较好的方法是随机选取轴值

快速排序代码

template <class Elem>
int partition(Elem A[],int i,int j)
{
   
    //这里选择尾元素作为轴值,轴值的选择可以设计为一个函数
    //如果选择的轴值不是尾元素，还需将轴值与尾元素交换
    int pivot = A

了解本专栏

超级会员免费看