选择排序、冒泡排序、插入排序、二分法_excel自动排序用的是冒泡法二分法

选择排序

    private static void resole(int[] arr) {
        if(arr == null || arr.length < 2){
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) { //i ~ n-1
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) { //i ~ n-1 上找最小值得下标
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr,i,minIndex);
        }
    }
    /**
     * 最常见的交换
     */
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

冒泡排序

    private static void resole(int[] arr) {
        if(arr == null || arr.length < 2){
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length -1 -i; j++) {
                if(arr[j] > arr[j+1])
                swap(arr,j,j+1);
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11

插入排序

    private static void resole(int[] arr) {
        if(arr == null || arr.length < 2){
            return;
        }
        //0 位置上有序
        //想(0~1) (0~2) (0~3)...(0~i)位置上有序
        for (int i = 1; i < arr.length; i++) { 
            for (int j = i - 1 ; j >= 0 && arr[j] > arr[j+1]; j--) {
                swap(arr,j,j+1);
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

通过异或运算交换两个数，但是i,j必须是内存中两个不同的地址

    /**
     * 亦或交换
     * int a = 甲，int b = 乙
     * ① a = 甲 ^ 乙，b = 乙
     * ② a = 甲 ^ 乙，b = 甲 ^ 乙 ^ 乙 = 甲
     * ③ a = 甲 ^ 乙 ^ 甲 = 乙，b = 甲
     */
    private 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
4
5
6
7
8
9
10
11
12

异或运算可以理解为无进位相加
例题1.有一个数组中有很多数，只有两个数出现了奇数次，请找出这两个数

    private static void resolve(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }

        //rightOne 找到eor最右侧的1,eor = a ^ b,因为a != b，所以eor最少有一个1，
        int rightOne = eor & (~eor + 1);
        //一侧
        int sideOne = 0;
        for (int i = 0; i <arr.length; i++) {
            if((rightOne & arr[i]) == 1){ //根据找的一个1，来取到为0的一侧或者为1的一侧
                sideOne ^= arr[i];
            }
        }
        //另一侧
        int otherSideOne = eor ^ sideOne;
        System.out.println(sideOne + " " + otherSideOne);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二分法

例题二
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引

    public int searchInsert(int[] nums, int target) {
       int n = nums.length;
       int l = 0,r = n -1 ;
       while(l<=r){
       		//int mid = (l + r)/2 可能会溢出
           int mid = l+((r-l) >> 1);
           if(nums[mid]==target){
             return mid;
           }else if(nums[mid]>target){
               r = mid -1;
           }else{
               l = mid + 1;
           }
       }
       return l;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二分法拓展：
1、在一个有序数组中，找某个数是否存在
2、在一个有序数组中，找>=某个数最左侧的位置
3、局部最小值的问题

以上所有内容是皆来自于算法课程
B站-左程云左神的教学视频