1、复杂度
1.1时间复杂度
时间复杂度是指执行某个算法所需要的计算工作量,写作T(n)=O(f(n)),当f(n)相等时,需要在相同的情况下计算具体的运行时间来比较两个算法的优劣,常见的有:
- 常数时间复杂度
- 对数时间复杂度
- 次方时间复杂度
- 线性时间复杂度
- 线性对数时间复杂度
- 质数时间复杂度
1.2空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度,写作S(n)=O(f(n))。
2、异或运算
异或运算可以理解为一种无进位相加,常用规则有:
- 0 ^ N = N ; N ^ N = 0
- 交换律结合律:a ^ b = b ^ a ; (a ^ b) ^ c = a ^ (b ^ c)
- 同一组数异或结果与顺序无关
例一:一组数中,已知有一种数的出现次数为奇数,其他类型的数出现的次数为偶数,求出现次数为奇数的数。
public static int test1(int[] arr, int n) {
int temp=0;//临时变量,用来储存异或结果
for (int i=0; i<n; i++) {
//N ^ N = 0
temp = temp ^ arr[i];
}
return temp;
}
例二:一组数中,已知有两种数的出现次数为奇数,其他类型的数出现的次数为偶数,求出现次数为奇数的两个数。
public static void test2(int[] arr, int n) {
int temp=0;//临时变量,用来储存异或结果
int i=0;//循环变量
int a=0,b=0;//两个奇数
for (i=0; i<n; i++) {
//N ^ N = 0
temp = temp ^ arr[i];//temp = a ^ b;
}
//取最左边的1
int left = temp & ( ~temp + 1);
//与该位为1的数相异或得到其中一个数
for (i=0; i<n; i++) {
if((arr[i] & left) == 1) {
a ^= arr[i];
}
}
b = a ^temp;
System.out.println("a = "+a+"\nb = "+b);
}
3、基本排序算法
3.1选择排序
时间复杂度O(n^2),空间复杂度O(1),稳定排序。
//选择排序
public static int[] selectSort(int[] arr) {
int n = arr.length;//数组长度
int i,j;//循环变量
int min;//局部最小值
for(i = 1; i<n; i++) {
min = i-1;
for(j=i; j<n; j++) {
if(arr[j]<arr[min]) {
min = j;
}
}
if(min!=(i-1)) {
//相加后减交换法
arr[i-1] = arr[i-1] + arr[min];
arr[min] = arr[i-1] - arr[min];
arr[i-1] = arr[i-1] - arr[min];
}
}
return arr;
}
3.2冒泡排序
时间复杂度O(n^2),空间复杂度O(1),稳定排序。
//冒泡排序
public static int[] bubblingSort(int[] arr) {
int n = arr.length;//数组长度
int i,j;//循环变量
for(i=0; i<n-1; i++) {
for (j=0; j<n-i-1; j++) {
if(arr[j]>arr[j+1]) {
//异或交换法
arr[j] = arr[j] ^ arr[j+1];
arr[j+1] = arr[j] ^ arr[j+1];
arr[j] = arr[j] ^ arr[j+1];
}
}
}
return arr;
}
3.3插入排序
时间复杂度O(n^2),空间复杂度O(1),稳定排序。
//插入排序
public static int[] insertSort(int[] arr) {
int n = arr.length;//数组长度
int i,j;//循环变量
int temp;//临时变量
for(i=1;i<n;i++) {
j = i;
while(j>0&&(arr[j-1]>arr[j])) {
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
j--;
}
}
return arr;
}
arr[j] = arr[j-1];
arr[j-1] = temp;
j--;
}
}
return arr;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/106590.html