归并排序

public static void mergeSort(int[]arr, int left, int right){
        if (left >= right) return;
        int mid = (left + right) / 2;
		//左递归分解数组
        mergeSort(arr, left, mid);
        //右递归分解数组
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
    	//每次合并都要一个临时数组，数组长度不一样，第一次就是2
        int[] temp = new int[right - left + 1];
        //要合并的两个数组的开始索引，第一个数组是left,结尾mid
        //第二个数组是j（mid+1）,末尾是right
        int i = left;
        int j = mid + 1;
        int index = 0;
        while (i <= mid && j <= right){
            if (arr[i] > arr[j]){
                temp[index++] = arr[j++];
            }else {
                temp[index++] = arr[i++];
            }
        }
        //看看谁还剩余
        while (i <= mid){
            temp[index++] = arr[i++];
        }
        while (j <= right){
            temp[index++] = arr[j++];
        }
		//原数组，复制其实位置，新数组，其实位置，复制的长度
        System.arraycopy(temp,0,arr,left,right - left + 1);
    }

快速排序

private static void quickSort(int[] arr, int left, int right){

        if (right < left) return;

        int i = left;
        int j = right;

        while (i < j){

            //一定先找右边的比left小的，要不然left就变了；= 带着
            while (i < j && arr[j] >= arr[left]){
                j--;
            }

            while (i < j && arr[i] <= arr[left]){
                i++;
            }
            swap(arr, i, j);
        }
        //退出来肯定i == j
        swap(arr, i, left);
        quickSort(arr,left,i - 1);
        quickSort(arr,i + 1,right);
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

二分查找

前提： 必须有序的数组

返回单个目标值索引，递归实现

private int binarySearch(int[] arr, int target, int left, int right){
        if (left > right) return  -1;
        int mid = (left + right) / 2;
        if(arr[mid] == target){
            return mid;
        }else if(arr[mid] > target){
        	//左边界好像是0也没毛病
            return binarySearch(arr,target,left,mid - 1);
        }else {
           return binarySearch(arr,target,mid + 1,right);
        }
    }

返回所有的目标值的索引

private  List<Integer> binarySearchAll(int[] arr, int target, int left, int right){
        if (left > right) return null;
        List<Integer> res = new ArrayList<>();
        int mid = (left + right) / 2;
        if (target > arr[mid]){
            return binarySearchAll(arr, target, mid + 1, right);
        }else if (target < arr[mid]){
            return binarySearchAll(arr,target,0, mid - 1);
        }else {
            int temp = mid;
            while (temp >= left && arr[temp] == arr[mid]){
                res.add(temp);
                temp--;
            }
            int rTemp = mid + 1;
            while (rTemp <= right && arr[rTemp] == arr[mid]){
                res.add(rTemp);
                rTemp++;
            }
            return  res;
        }
    }