题解 | #排序#

递归要素

• 递推公式
• 终止体条件
• 本级函数
• 递归函数的入参，返回值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        if(arr.length==0)
        {
            return arr;
        }
        //健壮性
        quickSort(arr,0,arr.length-1);
        return arr;
    }

    private void quickSort(int[] arr,int left,int right){//入参

        //终止条件：left = right 返回
        if(left >= right)
        {
            return;
        }
        //本级函数：把首个元素排到中间

        int key = arr[left];//用待排数组的第一个作为中枢
        int i = left;
        for (int j = left + 1; j <= right; j++) {
            if (arr[j] < key) {
                i++;
                swap(arr, j, i);     
            }
        }
        arr[left] = arr[i];
        arr[i] = key;

        //递推公式：分为左右两组，分别快排
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }

    private void swap(int[] arr,int i,int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}