常见的算法

冒泡排序 (1)原理 冒泡排序算法的原理如下： 比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点， 最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 (2)代码 public static void main(String[] args){ int[] arr={12,3,1,34,5,6,7,10}; 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; flag=true; } } System.out.println(Arrays.toString(arr)); } }

2.插入排序 (1)原理 首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元 素，就是数组的第一个元素。 插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并 保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。 (2)代码

public static void main(String[] args){ int[] arr={2,5,3,6,8,1,9}; for(int i=0;i<arr.length;i++){ int insert=arr[i];//要插入的数 int j=i-1; for(;j>=0;j--){ if(arr[j]>insert){ arr[j+1]=arr[j] }else break; } } arr[j+1]=insert; System.out.println(Arrays.toString); }

3.杨辉三角

public static void main(String[] args){ int line = 7; // 有几行 int[][] arr = new int[line][line];// 使用动态初始化创建一个二维数组 for (int i = 0; i < arr.length; i++) { // 外层循环控制行 // 打印数值 for (int j = 0; j <= i; j++) { // 内层循环控制列 if (j == 0 || j == i) { arr[i][j] = 1; // 每行的第1个值和最后1个值 都为1 } else { // i-1代表上一行 (j和j-1的和) arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1]; } System.out.print(arr[i][j]+"\t"); } System.out.print("\n"); } }

4.二分查找算法 (1)原理 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查 找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字， 则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成 功，或直到子表不存在为止，此时查找不成功。 (2)代码

public static int myBinarySearch(int[] a, int key) { int p = -1;//如果没有找到返回-1 // 步骤1：设置边界 int start = 0; int end = a.length - 1; while (start <= end) { System.out.println(start + "," + end); // 步骤2：找中间位置 int middle = (start + end) / 2; if (key == a[middle]) { p = middle; break; } else if (key > a[middle]) { // 去后面找 start = middle + 1; } else if (key < a[middle]) { // 去前面找 end = middle - 1; } } return p; } public static void main(String[] args){ int[] arr={2,5,3,6,8,1,9}; int index=myBinarySearch(arr,5); System.out.println(index); }

5.约瑟夫环

public static void main(String[] args) { //步骤1：布尔型数组标记每个人的状态 boolean[] persons=new boolean[5]; //步骤2：游戏开始之前，每个人都是活的true Arrays.fill(persons, true); //步骤3：开始玩自杀游戏 //记录活着的人数 int alive=persons.length; // 报数 int num=1; while(alive>1) { // 最后剩下一个,游戏结束 //开始每个人报数 for(int i=0;i<persons.length;i++) { //判断这个位置上的人是死的还是活的，活的才可以说话 if(persons[i]) { System.out.printf("下标%d的报数:%d%n",i,num); if(num%3==0) { System.out.printf("我先走了!%n"); persons[i]=false; //自杀 alive--; //自杀一个，活着的人就少一个 } num++; } } } for(int i=0;i<persons.length;i++) { if(persons[i]) { System.out.println("下标为"+i+"的人还活着!"); break; } } }