选择排序
时间复杂度O(n^2) 空间复杂度 O(1) 稳定
- 0 - n-1 选择一个最小的排在0号位置
- 1 - n-1选择一个最小的排在1号位置
- 2 - n -1选择一个最小的排在2号位置
...
以此类推，代码如下：
public class SelectSort {
public static void selectSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
// 从0到n-1选一个最小的
// 从1到n-1选一个最小的
for(int i = 0;i < arr.length;i++){
// 每次最小值都默认为起始元素
int minIndex = i;
for(int j = i+1;j < arr.length;j++){
// 找到每一轮中的最小值
minIndex = arr[minIndex] > arr[j] ? j : minIndex;
}
// 让最小值到每轮开头的位置
swap(arr,minIndex,i);
}
}
private static void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
冒泡排序
时间复杂度O(n^2) 空间复杂度O（1） 稳定
public static void maoPao(int[] arr){
if(arr == null || arr.length < 2){
return;
}
// 两两交换 最大的往后沉
int n = arr.length;
for (int i = n -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 temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
插入排序
时间复杂度O（n^2） 空间复杂度O（1） 稳定
public static void insertSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
int n = arr.length;
for (int i = 0; i < n; i++) {
for(int j = i;j > 0 && arr[j] < arr[j -1];j--){
swap(arr,j,j-1);
}
}
}
private static void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
二分
- 在一个有序数组中找一个数是否存在。
- 在一个有序数组中，找>=某个数最左侧的位置。
- 在一个有序数组中，找<=某个数最右侧的位置。
- 局部最小值问题。
- 有序数组二分
public static boolean isE(int[] arr,int target){
if(arr == null || arr.length == 0){
return false;
}
int L = 0;
int R = arr.length-1;
while(L <= R){
int mid = L + ((R -L) >>1);
if(arr[mid] == target){
return true;
}else if(arr[mid] > target){
R = mid - 1;
}else{
L = mid + 1;
}
}
return false;
}
- // 有序数组中寻找 大于等于目标值最左侧位置
public static int findLeftNum(int[] arr, int target){
if(arr == null || arr.length <=0){
// 负一时没有
return -1;
}
int index = -1;
int L = 0;
int R = arr.length-1;
while (L <= R){
int mid = L + ((R - L) >>1);
if(arr[mid] >= target){
index = mid;
R = mid - 1;
}else{
L = mid + 1;
}
}
return index;
}
- // 寻找小于等于目标值最右侧的位置
public static int findRightNum(int[] arr,int target){
if(arr == null || arr.length <= 0){
return -1;
}
int L = 0;
int R = arr.length - 1;
int index = -1;
while(L <= R){
int mid = L + ((R - L)>>1);
if(arr[mid]<= target){
index = mid;
L = mid + 1;
}else{
R = mid - 1;
}
}
return index;
}
- // 局部最小值，在无序数组中返回一个局部最小值的位置
public static int findMinNum(int[] arr){
if(arr == null || arr.length <= 1){
return -1;
}
int L = 0;
int R = arr.length - 1;
if(arr[0] < arr[1]){
return 0;
}
if(arr[R] < arr[R -1]){
return R;
}
// 前面都不满足则一定存在局部最小值在中间
while(L <= R){
// 先判断首位元素是否满足要求
int mid = L + ((R - L)>>1);
if(arr[mid] < arr[mid-1] && arr[mid] < arr[mid +1]){
return mid;
}else if(arr[mid] > arr[mid -1]){
R = mid - 1;
}else{
L = mid + 1;
}
}
return -1;
}
异或运算
- 无进位相加
- 0 ^ N = N N ^ N = 0
- 满足交换律和结合律
- 交换两个值
// 交换a ,b的值,内存要独立
int a = 1;
int b = 2;
a = a ^ b;
b = a ^ b;
a = a ^ b;
- 一个数组中有一种数出现了奇数次，其余数都是偶数次，找出这个数。（利用异或运算，计算性质，N ^ N=0,交换律结合律，偶数次的数字最终会全部消掉，剩下奇数次的数）。
public static int getNum(int[] arr){
int eor = 0;
for(int item : arr){
eor ^= item;
}
return eor;
}
提取一个数最右边的1
int n =2;
int res = n &(~n+1); // 等价于 n & (-n)
- 一个数组中，有两个数出现了奇数次，其余都出现了偶数次，找出这两个数。
- 由于只有两个数出现了基数次，不妨设出现奇数次的两个数分别为 a,b则由题意可得，
所有数异或起来可得eor = a ^ b且不等于0,则必存在a,b中至少有一位不相等，假设a,b中第八位不同时相等，a 中第八位为1，b中第八位为0，则，数组可以分成两部分，第八位为1的（a），和第八位为0的(b)，让a堆所有数异或，则最后会剩下一个奇数，则求出了一个奇数，另一个奇数就好求了。
public static int[] getNum(int[] arr){
if(arr == null || arr.length == 0){
return new int[0];
}
int eor = 0;
// 求a , b的异或值
for(int item : arr){
eor ^= item;
}
// 求出 eor中最右边的1
int rightOne = eor & (-eor);
int eor2 = 0;
for(int item : arr){
if((item & rightOne) != 0){
// item中此位位1
eor2 ^= item;
}
}
// 一个奇数位eor2 ，则另一个位eor ^ eor2
return new int[]{eor2,eor2^eor};
}
- 一个数组arr中有一种数出现K次，其他数都出现了M次，
M > 1, K < M
找到，出现了K次的数，
要求，额外空间复杂度O(1)，时间复杂度O(N)
- 思路：
- 如果是int 型数组，申请一个大小为32的int型数组t，统计arr中所有的数的二级制为出现的次数放入t中
- 用遍历t，判断t中每一个元素能否被M整除（取模），能被整除说明统计的都是出现M次的数字贡献的，此时出现K次的数的该位置是0，不能整除，出现K次的数的该位置二进制是1。
public static int mM(int[] arr, int k, int m) {
if (k >= m) {
return -1;
}
// 统计所有数每个位上的次数
int[] t = new int[32];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < 32; j++) {
t[j] += ((arr[i] >> j) & 1);
}
}
// t中每一位和m取模，如果刚好无余数，则该为的1不是k中的数贡献的
int res = 0;
for (int i = 0; i < 32; i++) {
if (t[i] % m != 0) {
res |= 1 << i;
}
}
return res;
}
