手写快速排序

最新推荐文章于 2025-04-20 14:01:07 发布

bug_lover_liao

最新推荐文章于 2025-04-20 14:01:07 发布

阅读量1w

点赞数 4

分类专栏：数据结构与算法文章标签：快速排序

本文链接：https://blog.csdn.net/csdn_blog_lcl/article/details/78089170

版权

本文详细介绍了快速排序算法，包括其基本思想、算法流程及代码实现。特别提到了在处理几乎有序数组和大量重复元素时的优化策略，如选择随机基准和采用三路快速排序。

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

前言

快速排序是一种很重要的排序算法，我花了不少时间去理解并总结它，希望可以通过图文的方式让你快速理解快速排序，并能手撸一个快排。

快速排序简介

快速排序是一种很不错的排序算法，算法复杂度为n*logn。快排使用了分而治之的思想，每次排序是都找到一个基准（我们学习时经常使用第一个作为基准）,然后把小于基准的元素放到基准元素的左边，大于基准的元素放到基准元素的右边，这样一次排序下来，基准元素左边都是小于（等于）基准的数，基准右边的元素都是大于（等于）基准的元素了。快速排序关键点就是找到这样一个基准并将其放到恰到的位置。

算法思路

定义一个快速排序函数，arr是要排序的数组，l指向要排序的数组最左边的元素，r指向要排序的数组最右边的元素。

public static void quick_sort(int arr[],int l,int r){
        if(l >= r) return;
        //p为快速排序返回的基准的位置
        int p = partition2(arr,l,r);
        //对基准左边的数进行快排
        quick_sort(arr,l,p-1);
        //对基准右边的数进行快排
        quick_sort(arr,p+1,r);
    }