JavaSE-递归法解决二分查找、快速排序
704. 二分查找
https://leetcode.cn/problems/binary-search/
package demo;public class BinarySearch {public static void main(String[] args) {BinarySearch br=new BinarySearch();System.out.println(br.search(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 8));}public int search(int[] nums, int target) {int index=-1,mid= (int) Math.floor(nums.length/2);//默认为中间位置if(nums[mid]==target){index=mid;}else if(nums[mid]>target){// 向左查找index=search(nums,target,0,mid-1);}else{// 向右查找index=search(nums,target,mid+1,nums.length-1);}return index;}public static int search(int[] nums,int v,int start,int end){if(start>end){return -1;}int mid= (int) Math.floor((start+end)/2);if(nums[mid]==v){return mid;}else if(nums[mid]>v){return search(nums,v,start,mid-1);}else{return search(nums,v,mid+1,end);}}
}
牛客网——快速排序https://www.nowcoder.com/questionTerminal/53d2f8d6f4e0472d83ee83a4d16f1b8f?page=1&onlyReference=false
package demo;public class QuickSort {public static void main(String[] args) {QuickSort qs=new QuickSort();quickSort(new int[]{10,3,8,2,1,9,4,7,11},0,8);}public static void quickSort(int[] nums,int start,int end){// 递归结束条件if(start>=end){return;}int pivot=partition(nums,start,end); // 返回pivot的位置quickSort(nums,start,pivot-1); // 递归左子树quickSort(nums,pivot+1,end); // 递归右子树System.out.println("当前节点为："+pivot+"排序后的数组是");for (int i = 0; i < nums.length; i++) {System.out.print(nums[i]+" ");}System.out.println();}public static int partition(int[] nums,int start,int end){ // 快排的partition操作int pivot=nums[start];while(start<end){while(start<end&&nums[end]>=pivot){end--;}nums[start]=nums[end];while(start<end&&nums[start]<=pivot){start++;}nums[end]=nums[start];}nums[start]=pivot;return start;}
}