快速排序实现Java版本

采用第一个元素作为轴值的快速排序方法

import java.util.Arrays;
/**
 * @author:xwh
 * @create: 2022-09-17 14:39
 * @Description:
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr=new int[]{-9,78,0,23,-567,70};
        quickSort(arr,0,arr.length-1);
        System.out.println("arr="+ Arrays.toString(arr));
    }
    //left和right表示当前两边的索引
    public static void quickSort(int[] arr,int left,int right){
        if(left>=right){
            return;         //注意递归终止条件的判断
        }
        int l=left;     //左下标
        int r=right;    //右下标
        //选择第一个元素作为当前的轴值
        int pivot=arr[left];

        //开始进行探测
        while(l<r){
            //注意：由于选了最左边的作为轴值  此处移动的时候先移动右指针r
            while(l<r&&arr[r]>=pivot){      //满足条件时右指针的移动
                r--;
            }
            while(l<r&&arr[l]<=pivot){      //满足条件时左指针的移动
                l++;
            }
            //当两个指针都停止移动时  表示需要进行位置交换了
            if(l<r){
                int temp=arr[l];
                arr[l]=arr[r];
                arr[r]=temp;
            }
            //然后再进行新一轮的移动
        }
        //退出循环表示l和r指针相遇l==r  当前位置应该是轴值位置  需要交换值
        arr[left]=arr[l];
        arr[l]=pivot;
        //此时轴值左边数据都小于等于pivot  右边数据都大于等于pivot
        //开始对pivot左右两边进行递归
        quickSort(arr,left,l-1);
        quickSort(arr,l+1,right);
    }
}
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