【Java数据结构与算法】简单排序、二分查找和异或运算
简单排序
选择排序
概念
首先，找到数组中最小的那个元素，其次，把它和数组的第一个元素交换位置（如果第一个元素就是最小的元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断地选择剩余元素中地最小者。
代码实现
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));
}
