二分查找

import java.util.ArrayList;
import java.util.List;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 9, 10, 234, 234,234, 1000, 1234};
        int i = binarySearch(arr, 0, arr.length - 1, 234);
        System.out.println(i);
        List<Integer> index = binarySearch2(arr, 0, arr.length - 1, 234);
        System.out.println(index);
    }
    // 只能找出一个值的下标 递归实现
    public static int binarySearch(int[] arr, int left, int right, int findVal){
        if (left > right){
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal){
            return binarySearch(arr, mid + 1, right,findVal); // 向左查找
        }else if (findVal < midVal){
            return binarySearch(arr, left, mid - 1, findVal); // 向右查找
        }else if (findVal == midVal){
            return mid;
        }
        return -1;
    }
    // 循环实现
    public static int binarySearch3(int[] arr, int target){
        int left = 0;
        int right = arr.length - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if (arr[mid] == target){
                return mid;
            }else if(arr[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }

    // 可以找出多个值的下标
    public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal){
        if (left > right){
            return new ArrayList<>();
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal){
            return binarySearch2(arr, mid + 1, right,findVal);
        }else if (findVal < midVal){
            return binarySearch2(arr, left, mid - 1, findVal);
        }else if (findVal == midVal){
            int temp = mid - 1; // 辅助变量
            List<Integer> result = new ArrayList<>();
            while(true){
                // 向中间值的左边找 因为为有序的数组，所以只要找到不等于findVal的值就饿可以直接退出循环
                if (temp < 0 || arr[temp] != midVal){
                    break;
                }
                result.add(temp);
                temp -= 1;
            }
            result.add(mid); // 添加中间值的下标
            temp = mid + 1;
            while(true){
                // 向中间值的右边找 因为为有序数组 所以只要找到不等于findVal的值就可以直接退出循环
                if (temp > arr.length - 1 || arr[temp] != midVal){ 
                    break;
                }
                result.add(temp);
                temp += 1;
            }
            return result;
        }
        return new ArrayList<>();
    }
}

排序算法.png

冒泡排序

public static void bubbleSort(int[] arr){ // 时间复杂度为o(n^2)
        int temp;
        boolean flag = false; // 标记变量
        for (int i = 0; i < arr.length - 1; i++) { // 一共进行多少躺排序
            for (int j = 0; j < arr.length - i - 1; j++) { // 每一趟排序都找出最大值 往后移
                if (arr[j] > arr[j+1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if (!flag){ // 如果一趟排序中一次交换都没有出现就退出循环
                break;
            }else {
                flag = false; // 重置flag方便下次判断
            }
        }
    }

插入排序

public static void insertSort(int[] arr) {
        // 从第二个元素开始
        for (int i = 1; i < arr.length; i++) {
            int insertValue = arr[i]; // 要插入的元素
            int insertIndex = i - 1; // 插入的位置
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) { // 寻找位置
                arr[insertIndex + 1] = arr[insertIndex]; // 比它大的元素后移
                insertIndex--; // 向前走
            }
            // 因为之前index = i - 1 如果没有进入到while循环就不需要插入（index = i - 1）
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertValue; // 把要元素插入到查找到的位置
            }
        }
    }

快速排序

public static void quickSort(int[] arr, int left, int right){
        int l = left; // 左下标 0
        int r = right; // 右下标 5
        // pivot 中轴值
        int pivot = arr[(left + right) / 2]; // 78
        int temp = 0;// 临时变量
        // while循环的目的是让pivot值小放到左边 比pivot值大放到右边
        while (l < r){
            while(arr[l] < pivot){ // 找出在pivot的左边比pivot大或者等的值的下标
                l += 1;
            }
            while(arr[r] > pivot){ // 找出在pivot的右边比pivot小或者等的值的下标
                r -= 1;
            }
            if (l >= r){
                break;
            }
            //交换pivot左边比他大的值 pivot右边比他小的值 
            temp = arr[r];
            arr[r] = arr[l];
            arr[l] = temp;

            if (arr[l] == pivot){ // 如果左边的这个值是等于pivot的 r--向前移动
                r--;
            }
            if (arr[r] == pivot){ // 如果右边的这个值是等于pivot的 l++ 向后移动
                l++;
            }
        }
        if (l == r){
            l += 1; // 增加l的值 不然可能出现栈溢出
            r -= 1; // 减小r的值 不然可能出现栈溢出
        }
        if (left < r){ // 在左边递归
            quickSort(arr,left,r);
        }
        if (right > l){ // 在右边递归
            quickSort(arr,l,right);
        }
    }