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

【学习背景】

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