java快速排序算法

package mytest;

import java.util.Arrays;

public class qkSort {
    public static void main(String[] args) {
        int [] arr = {5,6,8,1,2,4,6,2};
        quick(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }


    
    static  void quick(int [] arr,int i, int h){
        if ( i >= h){
            return;
        }
        // 进行分区 返回中间基准点正确位置的下标
        int partition = partition(arr, i, h);
        // 左分区 原来的左基准点i到中间基准点-1
        quick(arr,i,partition-1);
        // 右分区 中间基准点+1 到 原来的右基准点
        quick(arr,partition+1 ,h);
    }
    // 将数组分区，将基准点元素移动到正确的位置，并返回其下标
    static int partition(int [] arr,int i, int h) {
        // j指针从左向右移动，遇到比h小的数，与i指针交换,直到h前一位
        for(int j = i;j < h ;j++){
            if (arr[j] <= arr[h]){
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
                i++;
            }
        }
        // h 和 i 的元素交换，因为 arr[i]不小于arr[h],此时arr[i]就在它正确的位置上，下次分区就以他作为左右分区的标准
        int temp = arr [h];
        arr [h] = arr[i];
        arr [i] = temp;
        return i;
    }

}

时间复杂度O(nlogn)