Java常见算法整理
兔子问题（斐波那契数列规律）
台阶问题 （兔子问题变种，递归规律）
素数问题（判断素数、质数方式）
水仙花数问题（数字分解）
查找算法（二分查找）
排序算法（选择排序，冒泡排序，快速排序）
兔子问题，重点是找到规律。
斐波那契数列 1、1、2、3、5、8、13、21、34、55
规律为：F(n)=F(n-1)+F(n-2)（n>2，n∈N*）
public static void main(String[] args) {for (int i = 1; i <= 20; i++)
System.out.println("第" + i + "个月:" + function(i));
}
private static int function(int x) {
if (x == 1 || x == 2)
return 1;
else
return function(x - 1) + function(x - 2);
}
台阶问题:有n步台阶，一次只能上1步或2步，共有多少种走法?
规律为：F(n)=F(n-1)+F(n-2)
public static void main(String[] args) {
System.out.println(function(10));
}
private static int function(int n) {
if (n <= 2) {
return n;
}
return function(n - 1) + function(n - 2);
}
判断素数（质数），重点是记住判断方式。
判断number是否是素数有这么几种方法：
（1）用2至number-1之间的所有数去整除number,如果有一个能被整除,说明number是非素数；除非所有的数都不能被整除,才说明number是素数.
（2）用2至number/2之间的所有数去整除number,如果有一个能被整除,说明number是非素数；除非所有的数都不能被整除,才说明number是素数.
（3）用2至number的平方根之间的所有数去整除number,如果有一个能被整除,说明number是非素数；除非所有的数都不能被整除,才说明number是素数
public static void main(String[] args) {
for (int i = 1; i <= 200; i++) {
if (function(i)) {
System.out.println("素数:" + i);
}
}
}
private static boolean function(int x) {
for (int i = 2; i <= x / 2; i++) {
if (x % i == 0) {
return false;
}
}
return true;
}
水仙花数，重点是分解百位、十位、个位。
public static void main(String[] args) {
for (int i = 1; i <= 999; i++) {
if (function(i)) {
System.out.println("水仙花数:" + i);
}
}
}
private static boolean function(int x) {
int i = 0, j = 0, k = 0;
i = x / 100;
j = (x % 100) / 10;
k = x % 10;
if (x == i * i * i + j * j * j + k * k * k)
return true;
else
return false;
}
查找算法（二分查找）
对于二分查找算法要求, 查找前的数据必须是已经排好序的, 然后得到数组的开始位置start和结束位置end, 取中间位置mid的数据a[mid]跟待查找数据key进行比较, 若 a[mid] > key, 则取end = mid - 1; 若 a[mid] < key, 则取start = mid + 1; 若 a[mid] = key 则直接返回当前mid为查找到的位置. 依次遍历直到找到数据或者最终没有该条数据.
public static void main(String[] args) {
int[] nums = new int[] { 1, 3, 5, 7, 9, 11, 13, 17 };
System.out.println(function(nums, 5));
}
private static int function(int[] nums, int key) {
int start = 0;
int end = nums.length - 1;
int mid = -1;
while (start <= end) {
mid = (start + end) / 2;
if (nums[mid] == key) {
return mid;// 已经查到返回！
} else if (nums[mid] > key) {
end = mid - 1;
} else if (nums[mid] < key) {
start = mid + 1;
}
}
return -1;
}
选择排序，冒泡排序，快速排序
public static void main(String[] args) {
int[] nums = new int[] { 6, 3, 8, 2, 9, 1 };
bubbleSort(nums);
System.out.println("bubbleSort:" + Arrays.toString(nums));
//
nums = new int[] { 6, 3, 8, 2, 9, 1 };
QuickSort(nums, 0, nums.length - 1);
System.out.println("QuickSort:" + Arrays.toString(nums));
//
nums = new int[] { 6, 3, 8, 2, 9, 1 };
ChoiceSort(nums);
System.out.println("ChoiceSort:" + Arrays.toString(nums));
}
// 冒泡排序
public static void bubbleSort(int[] a) {
int len = a.length;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a, j + 1, j);
}
}
}
}
// 快速排序
public static void QuickSort(int a[], int low, int hight) {
int i, j, index;
if (low > hight) {
return;
}
i = low;
j = hight;
index = a[i]; // 用子表的第一个记录做基准
while (i < j) { // 从表的两端交替向中间扫描
while (i < j && a[j] >= index)
j--;
if (i < j)
a[i++] = a[j];// 用比基准小的记录替换低位记录
while (i < j && a[i] < index)
i++;
if (i < j) // 用比基准大的记录替换高位记录
a[j--] = a[i];
}
a[i] = index;// 将基准数值替换回 a[i]
QuickSort(a, low, i - 1); // 对低子表进行递归排序
QuickSort(a, i + 1, hight); // 对高子表进行递归排序
}
// 选择排序
public static void ChoiceSort(int[] a) {
for (int i = 0; i < a.length; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[min] > a[j]) {
min = j;
}
}
if (i != min) {
int tmp = a[min];
a[min] = a[i];
a[i] = tmp;
}
}
}
// 交换元素
private static void swap(int[] a, int i, int j) {
int tmp;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
