专栏首页Android技术干货java数据结构与算法-快速排序
原创

java数据结构与算法-快速排序

基本思想

快速排序使用分治法策略来把一个序列分为两个子序列,基本步骤为:

  1. 先从序列中取出一个数作为基准数(为了方便一般选数组的第一个数作为基准数)。
  2. 分区过程:将把这个数大的数全部放到它的右边,小于它的数全放到它的左边。
  3. 递归的对左右两个子序列进行步骤2,知道各区间只有一个数。

java代码实现

public  void sort(int[] arr, int left, int right){
        if(left >= right){
            return;
        }
        //左边哨兵开始索引
        int i = left;
        //右边哨兵开始索引
        int j = right;
        //基准数
        int tmp = arr[left];
        //只要还满足左侧索引小于右侧索引,就不停的从右侧找比基准数小的,从左侧找比基准数大的,然后交换
        //通过交换可以将比基准数大的放到基准数右边,将比基准数小的放到基准数左边
        while(i < j){
            //先从右边开始找,找到一个比基准数小的停止
            while(tmp <= arr[j] && i < j){
                j--;
            }
            //再从左边开始找,找到一个比基准数大的停止
            while(tmp >= arr[i] && i < j){
                i++;
            }
            //将左右找到的两个数进行交换
            if(i < j){
                int m = arr[j];
                arr[j] = arr[i];
                arr[i] = m;
            }
        }
        //当左侧哨兵和右侧哨兵的索引相等时(既 i=j),结束循环,将基准数与当前位置上的数进行交换
        //为啥当 i 和 j 相遇时要将当前位置和基准数交换呢?
        //如果是 j 走向 i 导致的相遇,那说明在上一轮 i 这个位子是比基准数大的,通过和 j 交换,
        //这时 i 的位子上的数变成了以前 j 位置上的数,因此比基准数小,所以要交换。
        //如果是因为 i 走向 j 导致相遇,那说明在这一轮中右侧找到了比基准数小的(就是 j 位置上的数),
        //而左侧没找到比基准数大的,此时 i 和 j 位置一样,所以当前位置上的数比基准数小,因此交换。
        arr[left] = arr[i];
        arr[i] = tmp;
        //对左右子集进行递归调用
        sort(arr,left,j -1);
        sort(arr,j + 1,right);

    }

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Android 性能优化最佳实践

    快,稳,省,小,这四点很形象的代表了性能的四个方面,同时也让我们知道我们 App 现在是否是款性能良好的 APP,如果有一项不达标,那么说明我们的应用有待优化。

    李林LiLin
  • Android Binder 设计篇

    之前看过一篇关于Binder设计相关的文章,但是之前的连接打不开了。于是在网上搜索很久才找到原文地址:https://blog.csdn.net/univers...

    李林LiLin
  • Activity 的启动方式和 flag 详解

    活动的:Activity 在栈顶,它是可视、有焦点、可接受用户输入的。Android 试图尽最大可能保持它活动状态,杀死其它 Activity 来确保当前活动 ...

    李林LiLin
  • LeetCode 第 27 场双周赛(1125/1966,前57.2%)

    全国排名:1125 / 1966,57.2%;全球排名:4236 / 7924,53.5%

    Michael阿明
  • 腾讯居然也在做“雾霾”治理?因为腾讯举报中心正式上线啦!

    如果还没有听说过雾霾蓝,那你就out了!2016年时尚界最火的颜色之一就是“雾霾蓝”。据说一个雾霾蓝的手袋真是时尚时尚最时尚呢。

    腾讯举报中心
  • Unity3D网络通讯(六)-- UnityWebRequest实现WebService通讯

    前面几篇文章把主要的网络通讯方式都已经讲完了,今天是这个系列的最后一讲,关于WebService的通讯,主要是现在这个也不是主流,但是像如果对数据交互的老系统中...

    Vaccae
  • linux shell数组基础

    不管数值型还是字符串型,都是用一对圆括号表示,并且数组的元素之间用空格隔开,但是字符型的元素需要加引号 比如

    Y大宽
  • [Go] Golang练习项目-GO实现冒泡排序以及优化算法

    变量lastSwapIndex ,记录最后一次发生交换的位置,后续元素不再进行比较

    陶士涵
  • 选择排序算法,只需这篇文章就够了

    一直想写一些简单易懂的文章,因为平时看的很多的书籍或者文章都是看着很难受的感觉,当然,这并不是说书籍写的不好,只是说对于一些没有太多基础或者基础不是很好的来说,...

    好好学java
  • cPanet面板绑定域名和删除已绑定域名教程

    cPanel面板是一款功能强大的主机面板,国外众多大型主机商都在使用。对于cPanel面板中几十个上百个按钮功能,其实能用上的也不多。这里我们直接先步入正题,把...

    主机测评

扫码关注云+社区

领取腾讯云代金券