Java一些基本常用算法
包括排序：冒泡排序、选择排序、插入排序、快速排序
常见查找：线性查找、折半查找
其他算法：水仙花数、回文查询、进制转换
排序
冒泡排序
- 算法思想
冒泡排序的基本思想就是不断比较相邻的两个数，让较大的元素不断地往后移。经过第1轮比较，就选出最大的数；经过第2轮比较，就选出次大的数，以此类推。
- 举例说明
第一轮排序过程
3 2 4 1 （最初）
2 3 4 2 （比较3和2，交换）
2 3 4 1 （比较3和4，不交换）
2 3 1 4 （比较4和1，交换）
第一轮结束，最大的数4已经在最后面，因此第二轮排序只需要对前面三个数进行再比较。
第二轮排序过程
2 3 1 4 （第一轮排序结果）
2 3 1 4 （比较2和3，不交换）
第二轮结束，第二大的数已经排在倒数第二个位置，所以第三轮只需要比较前两个元素。
第三轮排序过程 2 1 3 4 （第二轮排序结果）
1 2 3 4 （比较2和1，交换）
至此，排序结束。
- 代码例子
public class Test{
public static void main(String[] args) {
int a[] = { 49, 38, 65, 97, 76, 13, 27 };
bubbleSort(a);
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
//基本实现
public static void bubbleSort(int a[]){
for(int i=0;i<a.length-1;i++)
for(int j=0;j<a.length-i-1;j++)
if(a[j]>a[j+1])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
//优化实现
public static void bubbleSortBetter(int a[]){
for(int i=0;i<a.length-1;i++)
{
boolean isSort=true;
for(int j=0;j<a.length-i-1;j++)
if(a[j]>a[j+1])
{
isSort=false;
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
if(isSort)
break;
}
}
选择排序
- 算法思想
首先，选出最小的数，放在第一个位置；然后，选出第二小的数，放在第二个位置；以此类推，直到所有的数从小到大排序。
注意：选择排序是一种不稳定的排序算法，可能会打乱两个相同数字的原有顺序。
- 举例说明
在实现上，我们通常是先确定第i小的数所在的位置，然后，将其与第i个数进行交换。 下面，以对 3 2 4 1 进行选择排序说明排序过程，使用min_index记录当前最小的数所在的位置。
第1轮排序过程（寻找第1小的数所在的位置）
3 2 4 1（最初，min_index=1）
3 2 4 1（3 > 2，所以min_index=2）
3 2 4 1（2 < 4，所以min_index=2）
3 2 4 1（2 > 1，所以min_index=4，这时候确定了第1小的数在位置4）
1 2 4 3 （第1轮结果，将3和1交换，也就是位置1和位置4交换）
第2轮排序过程（寻找第2小的数所在的位置）
1 2 4 3（第1轮结果，min_index=2，只需要从位置2开始寻找）
1 2 4 3（4 > 2，所以min_index=2）
1 2 4 3（3 > 2，所以min_index=2）
1 2 4 3（第2轮结果，因为min_index位置刚好在第2个位置，无需交换）
第3轮排序过程（寻找第3小的数所在的位置）
1 2 4 3（第2轮结果，min_index=3，只需要从位置2开始寻找）
1 2 4 3（4 > 3，所以min_index=4）
1 2 3 4（第3轮结果，将3和4交换，也就是位置4和位置3交换）
至此，排序完毕。
- 代码例子
public static void selectSort(int a[]){
for(int i=0;i<a.length-1;i++){
int min_index=i;
for(int j=i+1;j<a.length;j++){
if(a[j]<a[min_index])
min_index=j;
}
if(i!=min_index){
int temp=a[i];
a[i]=a[min_index];
a[min_index]=temp;
}
}
}
插入排序
- 算法思想
将元素逐个添加到已经排序好的数组中去，同时要求，插入的元素必须在正确的位置，这样原来排序好的数组是仍然有序的。
插入排序是排序算法的一种，它不改变原有的序列（数组），而是创建一个新的序列，在新序列上进行操作。
- 举例说明
下面，以对 3 2 4 1 进行选择排序说明插入过程，使用j记录元素需要插入的位置。
排序目标是使数组从小到大排列。
第1轮
【3 】【2 4 1】（最初状态，将第1个元素分为排序好的子数组，其余为待插入元素）
【 3 】【 2 4 1 】 （由于3>2，所以待插入位置j=1）
【 2 3 】【 4 1 】 （将2插入到位置j）
第2轮
【 2 3 】【 4 1 】（第1轮排序结果）
【2 3 】【 4 1 】（由于2<4，所以先假定j=2）
【2 3 】【4 1 】（由于3<4，所以j=3）
【2 3 4 】【 1 】（由于4刚好在位置3，无需插入）
第3轮
【2 3 4 】【 1 】（第2轮排序结果）
【 2 3 4 】【 1 】 （由于1<2，所以j=1）
【1 2 3 4 】 （将1插入位置j，待排序元素为空，排序结束）
- 代码例子
public static void insertSort(int[] a) {
for (int i = 1; i < a.length; i++) {
// 首先找到元素a[i]需要插入的位置
int j = 0;
while ((a[j] < a[i]) && (j < i)) {
j++;
}
// 将元素插入到正确的位置
if (i != j) { // 如果i==j，说明a[i]刚好在正确的位置
int temp = a[i];
for (int k = i; k > j; k--) {
a[k] = a[k - 1];
}
a[j] = temp;
}
}
}
快速排序
- 算法思想
将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分操作，直到所有要进行排序的数据变为有序为止。
- 举例说明
快速排序（Quicksort）是对冒泡排序的一种改进。
①以第一个关键字 K 1 为控制字，将 [K 1 ,K 2 ,…,K n ] 分成两个子区，使左区所有关键字小于等于 K 1 ，右区所有关键字大于等于 K 1 ，最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。 ②把左区作为一个整体，用①的步骤进行处理，右区进行相同的处理。（即递归） ③重复第①、②步，直到左区处理完毕。
- 代码例子
static void quicksort(int n[], int left, int right) {
int dp;
if (left < right) {
dp = partition(n, left, right);
quicksort(n, left, dp - 1);
quicksort(n, dp + 1, right);
}
}
static int partition(int n[], int left, int right) {
int pivot = n[left];
while (left < right) {
while (left < right && n[right] >= pivot)
right--;
if (left < right)
n[left++] = n[right];
while (left < right && n[left] <= pivot)
left++;
if (left < right)
n[right--] = n[left];
}
n[left] = pivot;
return left;
}
查找
线性查找
- 算法思路
从数组的第一个元素开始查找，并将其与查找值比较，如果相等则停止，否则继续下一个元素查找，直到找到匹配值。
注意：被查找的数组中的元素可以是无序的、随机的。
- 代码例子
import java.util.*;
public class Test
{
public static void main(String args[]) {
int iArr[] = { 32, 9, 78, 44, 29, 18, 97, 49, 56, 61 };
System.out.println("数组的所有元素为：");
for (int i : iArr)
System.out.print(i + " ");
System.out.println();
System.out.print("请输入你要查找的元素：");
Scanner scan = new Scanner(System.in);
int iNum = scan.nextInt();
int index = straightSearch(iArr, iNum);
if (index == -1)
System.out.println("没有找到元素" + iNum);
else
System.out.println("找到元素" + iNum + ", 下标为:" + index);
}
public static int straightSearch(int[] arr, int num) {
int i = 0;
for(; i < arr.length; i++) {
if(arr[i] == num)
return i;
}
return -1;
}
}
折半查找
- 算法思路
假设被查找数组中的元素是升序排列的，那我们查找值时，首先会直接到数组的中间位置(数组长度/2)，并将中间值和查找值比较，如果相等则返回，否则，如果当前元素值小于查找值，则继续在数组的后面一半查找(重复上面过程)；如果当前元素值大于查找值，则继续在数组的前面一半查找，直到找到目标值或者无法再二分数组时停止。
注意：二分查找只是针对有序排列的各种数组或集合。
- 代码例子
//不利用递归实现
import java.util.*;
public class Test
{
public static void main(String args[])
{
int iArr[] = { 1, 2, 3, 4, 6, 8, 22, 44, 99, 111, 112, 116 };
System.out.println("数组的所有元素为：");
for (int i : iArr)
System.out.print(i + " ");
System.out.println();
System.out.print("请输入你要查找的元素：");
Scanner scan = new Scanner(System.in);
int iNum = scan.nextInt();
int index = binarySearch(iArr, iNum, 0, iArr.length - 1);
if (index == -1)
System.out.println("没有找到元素" + iNum);
else
System.out.println("找到元素" + iNum + ", 下标为:" + index);
}
public static int binarySearch(int[] arr, int num, int iMin, int iMax) {
while (iMin <= iMax) {
int iMid = (iMin + iMax) / 2;
if (num == arr[iMid])
return iMid;
else if (num < arr[iMid])
iMax = iMid - 1;
else
iMin = iMid + 1;
}
return -1;
}
}
//利用递归实现
import java.util.*;
public class Test
{
public static void main(String args[])
{
int iArr[] = { 1, 2, 3, 4, 6, 8, 22, 44, 99, 111, 112, 116 };
System.out.println("数组的所有元素为：");
for (int i : iArr)
System.out.print(i + " ");
System.out.println();
System.out.print("请输入你要查找的元素：");
Scanner scan = new Scanner(System.in);
int iNum = scan.nextInt();
int index = binarySearch(iArr, iNum, 0, iArr.length- 1);
if(index==-1)
System.out.println("没有找到元素"+iNum);
else
System.out.println("找到元素"+iNum+", 下标为:"+index);
}
public static int binarySearch(int[] arr, int num, int iMin, int iMax){
int iMid = (iMin + iMax) / 2;
if (num < arr[iMin] || num > arr[iMax])
return -1;
else if (num == arr[iMid])
return iMid;
else if (num < arr[iMid])
return binarySearch(arr, num, iMin, iMid - 1);
else
return binarySearch(arr, num, iMid + 1, iMax);
}
}
其他
递归实现字符颠倒
- 代码例子
import java.util.Scanner;
public class Demo {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
System.out.println("输入一串字符串：");
String str = in.nextLine();
System.out.println(reverseChat(str));
}
public static String reverseChat(String str){
if(str.isEmpty())
return str;
return reverseChat(str.substring(1))+str.charAt(0);
}
}
二进制十进制互转
- 代码例子
import java.util.Scanner;
public class Demo {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
System.out.println("请输入转换类型，1：十进制转二进制；2：二进制转十进制:");
int Type = in.nextInt();
switch(Type){
case 1:
System.out.println("输入一个十进制数：");
int a = in.nextInt();
int[] b = new int[10] ;
int i=0;
while(a!=0)
{
b[i]=a%2;
a/=2;
i++;
}
System.out.println("二进制为：");
i--;
for(;i>=0;i--)
System.out.print(b[i]);
System.out.println("");
break;
case 2:
System.out.println("输入一个二进制数：");
int x = 0;
in.nextLine();
String str = in.nextLine();
for(char c: str.toCharArray())
x = x * 2 + (c == '1' ? 1 : 0);
System.out.println(x);
break;
}
}
}
回文查询
- 代码例子
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
public class Demo {
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader bufr = new BufferedReader(new InputStreamReader(System.in));
System.out.println("输入一串字符串：");
String str = bufr.readLine();
StringBuilder sb = new StringBuilder(str);
sb.reverse();
int n = 0;
for(int i = 0;i<str.length();i++){
if(str.charAt(i)==sb.charAt(i))
n++;
}
if(n==str.length())
System.out.println(str+" Yes!");
else
System.out.println(str+" No!");
}
}
计算式
- 代码例子
import java.util.Scanner;
public class Demo {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//String str = "54151+819*5165+15-48/189+5961";
System.out.println("输入一个算式：（1+2*3...）按回车键结束：");
String str = scan.nextLine();
String regex = "([0-9]+[\\+\\-\\*\\/])*[0-9]+";
float num = 0;
if(!str.matches(regex))
System.out.println("输入不合规则！");
else
System.out.println(cacComplex(str));
}
private static double cacComplex(String str) {
if (str.equals(""))
return 0;
System.out.println("CAC:" + str);
str = str.replaceAll("[\\[\\{]", "(").replaceAll("[\\]\\}]", ")");
int cl = str.lastIndexOf('(');
if (cl == -1)
return cac(str);
int cr = str.indexOf(')', cl);
String left = str.substring(0, cl);
String right = str.substring(cr + 1);
String middle = str.substring(cl + 1, cr);
return cacComplex(left + cac(middle) + right);
}
public static double cac(String str) {
if (str.equals(""))
return 0;
int ml = str.indexOf('*');
int dl = str.indexOf('/');
if (ml == -1 && dl == -1) {
return cacNoMD(str);
}
int index = ml == -1 ? dl : ml;
// 4+5*6*7+8
String left = str.substring(0, index);// 4+5
String m1 = lastNumber(left);
left = left.substring(0, left.length() - m1.length());
String right = str.substring(index + 1);// 6*7+8
String m2 = firstNumber(right);// m2:6
right = right.substring(m2.length());// *7+8
double d1 = Double.parseDouble(m1);
double d2 = Double.parseDouble(m2);
double tmp = 0;
if (index == ml) {
tmp = d1 * d2;
} else if (index == dl) {
tmp = d1 / d2;
}
return cac(left + tmp + right);
}
private static String lastNumber(String str) {
StringBuilder sb = new StringBuilder();
for (int i = str.length() - 1; i >= 0; i--) {
char c = str.charAt(i);
if (!Character.isDigit(c) && c != '.')
break;
sb.append(c);
}
return sb.reverse().toString();
}
private static String firstNumber(String str) {
StringBuilder sb = new StringBuilder();
for (char c : str.toCharArray()) {
if (!Character.isDigit(c) && c != '.')
break;
sb.append(c);
}
return sb.toString();
}
private static double cacNoMD(String str) {
double ret = 0;
StringBuilder sb = new StringBuilder();
char sign = '+';
for (char c : (str + "+").toCharArray()) {
if (!Character.isDigit(c) && c != '.') {
if (sb.length() == 0)
continue;
double tmp = Double.parseDouble(sb.toString());
if (sign == '+') {
ret += tmp;
} else {
ret -= tmp;
}
sb = new StringBuilder();
sign = c;
} else {
sb.append(c);
}
}
return ret;
}
}
乘法表
- 代码例子
public class Demo {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
for(int x=1;x<=9;x++)
{
for(int y=1;y<=x;y++)
System.out.print(y+"x"+x+"="+(x*y)+" ");
System.out.println("");
}
}
}
水仙花数
- 代码例子
public class Demo {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
test();
}
//穷举(水仙花数,三位正整数:其每位数位上的数字的立方和与该数相等)
public static void test(){
for(int i=100;i<=999;i++){
if(Math.pow(i%10, 3)+Math.pow(i/10%10, 3)+Math.pow(i/100, 3)==i){
System.out.print(i+" ");
}
}
}
}
一元非线性方程求根
牛顿迭代法
- 算法说明
牛顿迭代法又称牛顿切线法：
| 先任意设定一个与真实的根接近的值x0作为第一次近似根，由x0求出f(x0),过(x0，f(x0))点做f(x)的切线，交x轴于x1，把它作为第二次近似根，再由x1求出f(x1),过(x1，f(x1))点做f(x)的切线，交x轴于x2，……如此继续下去，直到足够接近（比如 | x- x0 | <1e-6时）真正的根x*为止。而f ‘(x0)=f(x0)/( x1- x0) 所以 x1= x0- f(x0)/ f ‘ (x0) |
例如，用牛顿迭代法求下列方程在1.5附近的根：2x3-4x2+3x-6=0。
- 代码例子
public static void main(String[] args) {
// TODO Auto-generated method stub
double x,x0,f,f1;
x=1.5;
do{
x0=x;
f=2*x0*x0*x0-4*x0*x0+3*x0-6;
f1=6*x0*x0-8*x0+3;
x=x0-f/f1;
}while(Math.abs(x-x0)>=1e-6);
System.out.println(x);
}
二分法
- 算法说明
算法要领是：先指定一个区间[x1, x2]，如果函数f(x)在此区间是单调变化的，则可以根据f(x1)和 f(x2)是否同号来确定方程f(x)=0在区间[x1, x2]内是否有一个实根；如果f(x1)和 f(x2)同号，则f(x) 在区间[x1, x2]内无实根，要重新改变x1和x2的值。当确定f(x) 在区间[x1, x2]内有一个实根后，可采取二分法将[x1, x2]一分为二，再判断在哪一个小区间中有实根。如此不断进行下去，直到小区间足够小为止。 具体算法如下： （1）输入x1和x2的值。 （2）求f(x1)和f(x2)。 （3）如果f(x1)和f(x2)同号说明在[x1, x2] 内无实根，返回步骤（1），重新输入x1和x2的值；若f(x1)和f(x2)不同号，则在区间[x1, x2]内必有一个实根，执行步骤（4）。 （4）求x1和x2的中点：x0=（x1+ x2）/2。 （5）求f(x0)。 （6）判断f(x0)与f(x1)是否同号。 ①如果同号，则应在[x0, x2]中寻找根，此时x1已不起作用，用x0代替x1，用f(x0)代替f(x1)。 ②如果不同号，则应在[x1, x0]中寻找根，此时x2已不起作用，用x0代替x2，用f(x0)代替f(x2)。 （7）判断f(x0)的绝对值是否小于某一指定的值（例如10-5）。若不小于10-5，则返回步骤（4）重复执行步骤（4）、（5）、（6）；否则执行步骤（8）。 （8）输出x0的值，它就是所求出的近似根。 例如，用二分法求方程2x3-4x2+3x-6=0在(-10，10)之间的根。
- 代码例子
public static void main(String[] args) {
// TODO Auto-generated method stub
double x1,x2,x0,fx1,fx2,fx0;
Scanner in = new Scanner(System.in);
do{
System.out.println("输入x1和x2的值：");
x1=in.nextDouble();
x2=in.nextDouble();
fx1=2*x1*x1*x1-4*x1*x1+3*x1-6;
fx2=2*x2*x2*x2-4*x2*x2+3*x2-6;
}while(fx1*fx2>0);
do {
x0=(x1+x2)/2;
fx0=2*x0*x0*x0-4*x0*x0+3*x0-6;
if((fx0*fx1)<0)
{
x2=x0;
fx2=fx0;
}
else
{
x1=x0;
fx1=fx0;
}
}while(Math.abs(fx0)>1e-5);
System.out.println(x0);
}
梯形法计算定积分
- 代码例子
public class 梯形法计算定积分 {
/**
* 矩形法求定积分则更简单，就是将等分出来的图形当作矩形，而不是梯形。
例如：求定积分 的值。等分数n=1000。
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
double y;
y=DJF(0, 4);
System.out.println(y);
}
public static double DJF(double a,double b){
double t,h;
int n,i;
n=1000;
h=Math.abs(a-b)/n;
t=(HSZ(a)+HSZ(b))/2;
for(i=1;i<=n-1;i++)
t=t+HSZ(a+i*h);
t=t*h;
return t;
}
private static double HSZ(double x) {
// TODO Auto-generated method stub
return (x*x+3*x+2);
}
}
质数查询
- 代码例子
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Demo {
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader bufr = new BufferedReader(new InputStreamReader(System.in));
System.out.println("输入一个数：");
String str = bufr.readLine();
int num = Integer.parseInt(str);
if(num<=1){
System.out.println("不是质数");
}else if(num==2||num==3){
System.out.println("是质数");
return;
}else{
int k = (int)Math.sqrt(num);
for(int i=2;i<=k;i++){
if(num%i==0){
System.out.println("不是质数");
return;
}
}
System.out.println("是质数");
}
}
}