跟着左神刷爆算法——简单排序算法

选择排序：

 public static void selectionSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        for(int i = 0; i < arr.length; i++){
            int minIndex = i;
            for(int j = i+1; j < arr.length; j++){
                minIndex = arr[i] < arr[j]?j:minIndex;
            }
            swap(arr, i, minIndex);
        }
    }
    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    } 

冒泡排序：

    public static void bubbleSort(int[] arr){
        if(arr == null || arr.length <2){
            return;
        }
        for(int e = arr.length - 1; e > 0; e--) { // 0~e
            for(int i = 0; i< e; i++) {
                if(arr[i] > arr[i+1]){
                    swap(arr,i,i+1);
                }
            }
        }
    }
    //交换arr的i和j位置上的值
    public static void swap(int[] arr, int i, int j){
        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }

异或运算：相同为0，不同为1（可以理解为无进位相加）

异或运算不是对内存里的元素值进行运算，而是对元素的内存地址进行运算

异或相关面试题：

一个整型数组中，已知只有一种数出现奇数次，其余所有数出现偶数次

问题1：找到该奇数次的数

int eor = 0  ; eor ^ 数组中所有的数，得到eor该数

    public static void printOddTimesNum1(int[] arr){
        int eor = 0;
        for(int i = 0; i < arr.length; i++){
            eor ^= arr[i];
        }
        System.out.println(eor);
    }

问题2：如果有两种数出现奇数次，其余所有数出现偶数次，找出出现奇数次的两个数

提取一个数最右边的1的方式是  int rightOne =  eor & (~eor +1);

    public static void printOddTimesNum2(int[] arr){
        int eor = 0;
        for(int i = 0; i < arr.length; i++){
            eor ^= arr[i];
        }
        // eor = a^b;
        // eor != 0
        // eor必然有一个位置上是1
        int rightOne = eor ^ (~eor + 1); // 提取出一个数最右边的1
        int onlyOne = 0;
        for(int cur : arr){
            if((cur & rightOne) == 0){
                onlyOne ^= cur;
            }
        }
        System.out.println(onlyOne + " " + (eor^onlyOne));
    }

插入排序：

    public static void insertSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        // 0~0上有序
        // 0~i上有序
        for(int i = 1; i < arr.length; i++){ // 0~i上做到有序
            for(int j = i-1; j >= 0 && arr[j] > arr[j-1]; j--){
                swap(arr,j,j+1);
            }
        }
    }
    // i和j是一个位置的话，会出错
    public static void swap(int[] arr, int i, int j){
        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }

二分法：

问题1：在一个有序数组中，找某个数是否存在

问题2：在有序数组中，找 >=某个数最左侧的位置

问题3：局部最小值问题 ： arr中，无序，相邻数一定不相等

    public int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; // 注意

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1; // 注意
            else if (nums[mid] > target)
                right = mid - 1; // 注意
        }
        return -1;
    }