题解 | #排序#
排序
https://www.nowcoder.com/practice/2baf799ea0594abd974d37139de27896
递归要素
- 递推公式
- 终止体条件
- 本级函数
- 递归函数的入参,返回值
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; } }