Java--换工作也要学废的快速排序之三部曲解法

吾日三省贾斯汀 发表于 2021/12/13 22:49:21 2021/12/13
【摘要】 【学习背景】 Hi,大家好,我是贾斯汀,最近换了新工作,也换了租房,比较忙,一直拖着没怎么更新博客,更换新工作后工资UP、UP、UP的涨了不少,换了租房,位置就在公司楼下几百米远,再也不用挤深圳的...

【学习背景】

Hi,大家好,我是贾斯汀,最近换了新工作,也换了租房,比较忙,一直拖着没怎么更新博客,更换新工作后工资UP、UP、UP的涨了不少,换了租房,位置就在公司楼下几百米远,再也不用挤深圳的死亡4号线地铁!
最近在熟悉公司的业务以及公司自己封装的技术架构,虽然正常搬砖,但总感觉还是少了些什么,原来是少了写博客的那种feel,写博客对于我来说,可以使自己处于一个比较好的学习状态,既能巩固很多的基础知识,还可以新的知识技能,能够保持业界的一定竞争力!
今天呢,主要分享通过Java实现快速排序的三部曲解法,很多人都说算法主要是为了应付大厂的面试,但其实不然,我们公司的技术框架当中就有封装了关于快速排序的公共方法,有不少应用场景都有应用到,所以还是很有必要复习一下的,本文主要分享一下我觉得不错的一种解法,希望对大家有帮助!

【思路及代码实现】

package com.justin.java.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * Java实现快速排序之三部曲
 * 前奏:定义指针、变量、校验
 * 第一部曲:定义基准值(这里为方便说明,一般以起始位置的值作为基准值)
 * 第二部曲:根据基准值划分数组为两部分(小于基准数的放在左边,大于基准数的放在右边)
 * 第三部曲:最后对基准值所在位置左右两边的元素进行递归(最终完成左右两边的元素排序)
 *
 */
public class QuickSort {
    public static void main(String[] args) {
        //(1)简单测试
//        int[] arr = {6,3,5,7,2,10,4,9,8,1};
//        quickSort(arr,0,arr.length - 1);
//        System.out.println(Arrays.toString(arr));

        //(2)构建百万随机数据测试
        int maxSize = 1000000;
        int [] arr = new int[maxSize];
        for(int i=0;i<maxSize;i++){
            Random random = new Random();
            arr[i] = random.nextInt(maxSize);
        }
        long startTime = System.currentTimeMillis();
        quickSort(arr,0,arr.length - 1);
        long endTime = System.currentTimeMillis();
        long time = endTime - startTime;
        System.out.println(maxSize + "数据,快速排序耗时:" + time + "毫秒!");
        System.out.println(Arrays.toString(arr)); //控制台输出信息不全,可以通过修改IDEA安装目录bin\idea.properties的idea.cycle.buffer.size参数大小
    }

    /**
     * 快速排序
     * @param arr 要排序的数组
     * @param start 起始元素位置
     * @param end 结束元素位置
     */
    public static void quickSort(int [] arr, int start, int end){
        //前奏:定义指针、变量、校验
        int left,//左指针
                right,//右指针
                temp,//临时变量
                k;//与基准值进行交换的位置
        if(start > end){//起始位置大于结束位置,说明排序已经完成,直接返回,可以防止数组越界问题
            return;
        }
        left = start;//将左指针默认设置为起始位置
        right = end;//将右指针默认设置为结束位置

        //第一部曲:定义基准值(这里为方便理解,以起始位置的值作为基准值)
        int stand = arr[start];

        //第二部曲:根据基准值划分数组为两部分(小于基准数的放在左边,大于基准数的放在右边)
        while(left < right){
            //从右边找到目标值(小于基准值)所在位置
            while(arr[right] >= stand && left < right){//如果元素大于等于基准值,并且左右位置还没相等,说明没找到目标值,需继续向前找(right--)
                right--;
            }
            //从左边找到目标值(大于基准值)所在位置
            while(arr[left] <= stand  && left < right){//如果元素小于等于基准值,并且左右位置还没相等,说明没找到目标值,需继续向后找(left++)
                left++;
            }
            //经过上面左右两边的while循环,表明左右两边都已经找到了目标元素所在位置,此时再交换左右两边目标位置的值
            if(left < right){
                temp = arr[right];
                arr[right] = arr[left];
                arr[left] = temp;
            }
        }
        //经过上面的while循环,表明已经走完了一轮交换,此时left和right位置是一样的,该位置就是k,取该位置的值与基准值所在位置的值进行交换
        k = left;
        arr[start] = arr[k];
        arr[k] = stand;
        //第三件部曲:最后对基准值所在位置左右两边的元素进行递归(最终完成左右两边的元素排序)
        quickSort(arr,start,k-1);
        quickSort(arr,k+1,end);
    }

}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83

文章来源: blog.csdn.net,作者:吾日三省贾斯汀,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/JustinQin/article/details/121822396

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。