【Java数据结构与算法】简单排序、二分查找和异或运算

2021年7月21日 4点热度 0条评论 来源: gonghr

简单排序

选择排序

概念


首先,找到数组中最小的那个元素,其次,把它和数组的第一个元素交换位置(如果第一个元素就是最小的元素那么它就和自己交换)。再次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。这种方法叫做选择排序,因为它在不断地选择剩余元素中地最小者。

代码实现

   public static void SelectionSort(int[] arr){
        if(arr==null||arr.length<2) return;     //去除多余情况
        int N = arr.length;
        for (int i = 0; i < N-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < N; j++){
                if(arr[j] < arr[minIndex]) minIndex = j;  //更新每一轮最小元素的下标
            }
            swap(arr,i,minIndex);
        }
    }
    public static void swap(int[] arr, int i, int j){     //交换元素
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

复杂度分析

选择排序过程中,0~N-1 上任意位置i都要进行一次交换和N-1-i次比较。因此总共有N次交换和(N-1)+(N-2)+……+1=N(N-1)/2~N^2/2次比较。
也就是O(N^2)

冒泡排序

概念


从第一个元素开始遍历数组每两个元素一组比较,如果不满足从小到大的排序规则则进行交换,这样最后可以得到最大元素在数组最后的位置排好。如此往复,直到整个数组排好。

代码实现

    public static void sort(int[] arr){
        if(arr==null||arr.length<2) return;      //去除多余情况
        for(int i = arr.length - 1; i >= 0;i--){ //外层反向遍历
            for(int j = 0;j < i; j++){
                if(arr[j] > arr[j+1])
                    swap(arr,j,j+1);
            }
        }
    }
    public static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

复杂度分析

总的比较次数是(N-1)+(N-2)+……+1=N(N-1)/2~N^2/2
也就是O(N^2)

插入排序

概念


从左向右遍历,每次把遍历到的元素放到前面已经排好顺序的数组的合适位置。如此往复,直到整个数组排好。

代码实现

    public static void sort(int[] arr){
        if(arr==null||arr.length<2) return;     //去除无效情况
        for(int i = 1; i < arr.length; i++){    //i从1开始,认为i为1时已经排好
            for(int j = i-1; j >= 0 && arr[j] > arr[j+1]; j--)
                swap(arr,j,j+1);
        }
    }
    public static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

复杂度分析

总的比较和交换次数都是(N-1)+(N-2)+……+1=N(N-1)/2~N^2/2
也就是O(N^2)

二分查找

左侧边界二分查找

在arr上,找满足>=value的最左位置

   public static int nearestIndex(int[] arr, int value) {
        int L = 0;
        int R = arr.length - 1;
        int index = -1;
        while (L <= R) {      //注意等号
            int mid = L + ((R - L) >> 1);
            if (arr[mid] >= value) {  //注意
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        if(index == -1) return  -1;     //index可能为-1,防ArrayOutOfIndexException
        else if(arr[index] == value)
            return index;
        else return -1;
    }

右侧边界二分查找

在arr上,找满足>=value的最右位置

    public static int nearestIndex(int[] arr, int value) {
        int L = 0;
        int R = arr.length - 1;
        int index = -1;
        while (L <= R) {  
            int mid = L + ((R - L) >> 1);
            if (arr[mid] <= value) {  //注意
                index = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        if(index == -1) return  -1;     //index可能为-1,防止ArrayOutOfIndexException
        else if(arr[index] == value)
            return index;
        else return -1;
    }

总结

  • 左侧边界二分查找
    先写if (arr[mid] >= value)
  • 右侧边界二分查找
    先写if (arr[mid] <= value)
  • 别忘了最后对index为-1做特殊处理,防止数组越界访问

异或运算

公式

底层表现在二进制上,异或运算使得相同数字得0,不同数字得1
1 ^ 1 = 0
0 ^ 0 = 0
1 ^ 0 = 1

1 1 0 1 0 1 1 0
^ 0 1 0 0 1 1 0 0
= 1 0 0 1 1 0 1 0

0^N=N
N^N=0
满足交换律和结合律

应用

交换

a=a^b
b=a^b
a=a^b
实现了交换a,b的值
注意:前提是a,b有不同的内存空间。如果a,b是数组下标,那么当a=b的时候不能使用该方法,因为a,b代表数组一块相同的空间。
优点:位运算速度快,效率高

常考面试题

第一题

在一组数中,只有一种数出现了奇数次,其他类型的数出现了偶数次,问这个出现奇数次的数是什么,时间复杂度小于O(N)

解析:借助异或运算性质,N^N=0,只需要让所有数连续异或,最后的结果就是答案

    public static void printOddTimesNum1(int[] arr) {
		int eO = 0;
		for (int cur : arr) {
			eO ^= cur;
		}
		System.out.println(eO);
	}

第二题

在一组数中,有两种数出现了奇数次,其他类型的数出现了偶数次,问这两个出现奇数次的数是什么,时间复杂度小于O(N)

解析:设这两个数是a和b,所以所有数字第一次连续异或可以得到a^b。下面我们只需要想办法搞出a或者b。
举个例子,我们成功搞出a来,那么异或运算aba就可以得到b。注意到a和b前提是肯定不相同,那么在二进制的层面看这两个数字,它们肯定至少有一位数字是不一样的,一个是0,一个是1
a:…………0001…………
b:…………0000…………
下面要做的就是把所有出现了两次的数字根据ab这一位不同的数字进行分组。
这一位数字为0的数字为一组,这一位数字为1的数字为一组

让其中一组进行连续异或,比如这一位为1的这一组数字连续异或,出现偶数次的数字异或为0,最后只剩下a,我们就成功得到了a。
最后进行a ^ b ^ a就可以得到b
本题默认寻找a,b从右到左第一次出现的不同二进制位的位置,这也是本题的关键,等价于求ab异或后从右向左第一次出现1的位置。
记住一个公式:原码和补码做与运算可以得到二进制数从右到左第一次出现1的位置为1,其他位置为0的数

1010111100
& 0101000100
= 0000000100
    public static void printOddTimesNum2(int[] arr) {
		int eO = 0, eOhasOne = 0;
		for (int curNum : arr) {
			eO ^= curNum;
		}
		int rightOne = eO & (~eO + 1);  原码和补码做与运算
		for (int cur : arr) {
			if ((cur & rightOne) == 1) { 该位是1的为一组
				eOhasOne ^= cur;
			}
		}
		System.out.println(eOhasOne + " " + (eO ^ eOhasOne));
	}
    原文作者:gonghr
    原文地址: https://www.cnblogs.com/gonghr/p/15033050.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。