排序问题的时间复杂度
选择排序
工作原理：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法
时间复杂度O(N^2)
void selectSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
冒泡排序
工作原理：主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的
时间复杂度O(N^2)
void bullSort(int[] arr){
if (arr == null || arr.length < 2){
return;
}
for (int e = arr.length-1; e > 0; e--){
for (int i = 0; i < e; i++){
if (arr[i] > arr[i+1]){
swap(arr,i,i+1);
}
}
}
}
交换
以下方法：若i和j是同一个未知的话，会报错
//通过异或运算交换两个数的位置
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];
}
思考
问题一：
在一个整形数组中，有一个数出现了奇数次，其余数出现了偶数次，请问如何通过异或运算求得该数？
思路：
声明一个int类型的变量eor，让eor依次与该数组中的数值进行异或运算，最后求得eor就是出现了奇数次的数值
问题二：
在一个整形数组中，有两个数出现了奇数次，其余数出现了偶数次，请问如何通过异或运算求得这两个数？
思路：
假设这两个数分别为a，b
声明一个int类型的变量eor，让eor依次与该数组中的数值进行异或运算，最后求得eor为a^b
假设此时a和b中的第八位数值不同（这里采用二进制数，整形32位）并且a的第八位为一
然后声明一个int类型的变量eor1，让eor1分别对第八位为一的数值进行异或运算，最后求得eor1即为a
然后再将eor与eor1进行异或运算，得到b
void oddTimesNum2(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
//~eor是eor的取反
int onlyOne = 0;
for (int cur:arr){
if ((cur & rightOne) == 0){
onlyOne ^= cur;
}
}
System.out.println(onlyOne + " " + (eor ^ onlyOne));
}
插入排序
工作原理：每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，寻找最适当的位置，直至全部记录插入完毕
时间复杂度O(N^2)
void insertSort(int[] arr){
if (arr == null || arr.length < 2){
return;
}
//0~0有序的
//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);
}
}
}
二分法
经典二分：
在一个有序数组中，找出等于X的数组下标
时间复杂度O(logN)
补充
在一个有序数组中，找出大于等于X最左侧的数组下标（该数组含有多个与X值相同的值）
时间复杂度O(logN)
局部最小值
局部最小：同时小于左侧和右侧的值
在一个无序数组中，任何两个相邻的数不相等，求一个局部最小的数组下标
对数器的概念和使用
1.有一个你想要测的方法a
2.实现复杂度不好但是容易实现的方法b
3.实现一个随机样本产生器
4.把方法a和方法b跑相同的随机样本，看看得到的结果是否一样
5.如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a或者方法b
6.当样本数量很多时比对测试依然正确，可以确定方法a已经 正确
（个人理解）用自己所写的方法产生的结果与系统所提供的的方法（或者自己所写的另一种实现相同目的方法）产生的额结果进行大规模的对比实验，来判断该方法的正确性