博客

快速排序思路：

对于一个待排数组，将数组的最后一个数作为num，遍历除num之外的数组中的其他元素，小于num的放在数组左边，等于num的放中间，大于num的放右边，然后把num与大于区域的第一个数进行交换，此时num在数组中的位置就找到了，然后分别对小于区域和大于区域的数重复上述操作，直到所有的数都排好。

Java代码：

public class quickSort {

    public static void quicksort(int[] arr) {
        if (arr == null || arr.length < 2) {
            System.out.println("此数组无法排序！");
            return;
        }
        zhengli(arr, 0, arr.length - 1);
    }
    public static void zhengli(int[] arr , int l, int r){
        //左边区域指针
        int left = 0;
        //右边区域指针
        int right = 0;
        for(int i = l; i < r - right; i++){
            if(arr[i] < arr[r]){
                swap(arr, i, l + left);
                left++;
            }else if(arr[i] > arr[r]){
                swap(arr, r - 1 - right, i);
                right++;
                i--;
            }
        }
        swap(arr, r, r - right);

        if(left <= 2){
            if(arr[l] > arr[l + 1]){
                swap(arr, l, l + 1);
            }
        }else{
            zhengli(arr, l, l + left - 1);
        }

        if(right <= 2){
            if(arr[r - 2] > arr[r - 1]){
                swap(arr, r - 2, r - 1);
            }
        }else{
            zhengli(arr, r - right, r);
        }
    }
    //交换两个数
    public static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args){
        int[] arr = {3,5,4,2,6,4,9,1,3,5,2,7,4,7,2,7,1,4,8};
        quicksort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

以上内容为个人学习总结，如有错误，欢迎指正。