Java中的常用算法
一、冒泡排序
重点规律：冒泡排序的最外层的次数是arr.length-1
第二层的循环的次数是arr.length-1-i
package com.qu;
?
import java.util.Arrays;
?
public class D4 {
?
public static void main(String[] args) {
// 冒泡排序
int[] arr = {1,2,33,11,222,754,998};
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-1-i; j++) {
if (arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
?
}
?
}
?
二、选择排序
思路：先把第i个当成默认值，然后与后面的数进行比较（i+1）取最小值，判断第i个数不等于最小值就交换位置
...循环
package com.qu;
?
import java.util.Arrays;
import java.util.Iterator;
?
public class XuanZeSort {
?
public static void main(String[] args) {
// 选择排序 简单写法
int[] arr = {222,322,11,2,3213,2222,5634,7,89,654};
// for (int i = 0; i < arr.length-1; i++) {
// for (int j = i+1; j < arr.length; j++) {
// if (arr[i]>arr[j]) {
// int temp = arr[i];
// arr[i] = arr[j];
// arr[j] = temp;
// }
// }
// }
// System.out.println(Arrays.toString(arr));
// 选择排序2
for (int i = 0; i < arr.length-1; i++) {
int min = i; //这个地方是索引
for (int j = i+1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
System.out.println(Arrays.toString(arr));
?
}
?
}
?
三、插入排序
思路：第一次比较12个，第二次比较123个，第三次比较1234个...
package com.qu;
?
import java.util.Arrays;
?
public class ChaRuSort {
?
public static void main(String[] args) {
// 插入排序
int[] arr = {1,23,22,11,2,6,84,99};
//待插入的队列
for (int i = 1; i < arr.length; i++) {
int n = i; //插入的位置
while(n>0 && arr[n]<arr[n-1]) {
int temp = arr[n];
arr[n] = arr[n-1];
arr[n-1] = temp;
n--;
}
}
System.out.println(Arrays.toString(arr));
}
?
}
?
四、二分查找法
必须是一个有序序列，要用while的死循环，因为不知道要查多少次，还有就是要记得break关闭
package com.qu;
?
import java.util.Scanner;
?
public class D3 {
?
public static void main(String[] args) {
// 二分查找法 必须是有序数组 不知道查多少次，用while的死循环
int[] arr = {1,5,9,11,15,22,58,99,100};
Scanner sc = new Scanner(System.in);
System.out.println("请输入一个你要查找的数：");
int num = sc.nextInt();//拿一个容器去接这个数
int start = 0;//定义初始值 是索引
int end = arr.length-1;
while(true) {
int mid = (end+start)/2;
if (arr[mid] == num) {
System.out.println("猜对了，这个数的索引是"+mid);
break;
}else if (arr[mid] > num) { //猜的数小了
end = mid-1;
}else { //arr[mid] > num 猜的数大了
start = mid+1;
}
if (start>end) {
System.out.println("没有这个数");
break;
}
}
?
}
?
}
?
五、杨辉三角
package com.qu;
?
public class YangHui {
public static void main(String[] args) {
int n = 10;
int[][] arr = new int[n][];
for (int i = 0; i < n; i++) {
arr[i] = new int[i+1];
for (int j = 0; j <= i; j++) {
if (j==0 || j==i) {
arr[i][j] = 1;
System.out.print(1+" ");
}else {
arr[i][j] = arr[i-1][j]+arr[i-1][j-1];
System.out.print(arr[i][j]+" ");
}
}
System.out.println();
}
}
}
?
六、Arrays工具类
①打印多维数组（deepToString）
int[][] arr = {{1,2}{2,3}};
System.out.println(Arrays.deepToString(arr));
②binarySearch，二分查找（有返回值）
int[][] arr3 = {1，2，3，5，21，4};
int num = Arrays.binarySearch(arr3,5);
System.out.println(num); //4 找得到就返回索引，找不到就是负数
③排序 sort
Arrays.sort(arr3);//这个工具类只能从小到大排序
System.out.println(Arrays.toString(arr3));
④替换数组指定角标位置元素，fill
Arrays.fill(arr3,0,2,666);//把索引位0-2的替换成666，左闭右开
System.out.println(Arrays.toString(arr3));//[666,666,3,5,21,4]
⑤截取数组（copyOfRange）有返回值
int arr4 = Arrays.copyOfRange(arr3,0,2);//左闭右开
?
System.out.println(Arrays.toString(arr4));//[1,2]
?
|