常见的算法

查找算法

基本查找

Demo1

public static boolean basicSearch(int index,int[] arr){for (int i = 0; i < arr.length; i++) {if (index==arr[i]){return true;}}return false;
}

Demo2

//顺序查找，考虑重复，返回查找内容的索引
public static ArrayList<Integer> basicSearch(int index, int[] arr) {ArrayList<Integer> list = new ArrayList<>();for (int i = 0; i < arr.length; i++) {if (index == arr[i]) {list.add(i);}}return list;
}

二分查找/折半查找

前提条件：数组中的数据必须是有序的

Demo1

public static int binarySearch(int num, int[] arr) {int min = 0;int max = arr.length - 1;while (true) {if (min > max) {return -1;}//找数据//找到中间位置int mid = (min + max) / 2;//在左边if (num < arr[mid]) {max = mid - 1;}//在右边else if (num > arr[mid]) {min = mid + 1;}//找到else {return mid;}}
}

分块查找

原则1：前一块中的最大数据，小于后一块中所有的数据（块内无序，块间有序）

原则2：块数数量一般等于数字的个数开根号。比如：16个数字一般分为4块。

核心思路：先确认要查找的元素是哪一块，然后在块内挨个查找。

    public static void main(String[] args) {/**分块查找* 实现步骤：* 1.创建数组blockArr存放每一个块对象的信息* 2.先查找blockArr确定要查找的数据在哪一块* 3.单独遍历这一块数据* */int[] arr = {16, 5, 9, 12, 21, 18,32, 23, 37, 26, 45, 34,50, 58, 61, 52, 73, 66};//1.创建块对象，进行分块//要分为几块，个数开根号Block b1 = new Block(21, 0, 5);Block b2 = new Block(45, 6, 11);Block b3 = new Block(73, 12, 17);//定义数组来管理三个块的对象（索引表）Block[] blockArr = {b1, b2, b3};//定义一个变量，用来记录要查找的元素int number = 21;//调用方法，传递索引表，数组，查找的元素int index = getIndex(blockArr, arr, number);System.out.println(index);}//private static int getIndex(Block[] blockArr, int[] arr, int number) {//1.确定在哪一块int indexBlock = findIndexBlock(blockArr, number);if (indexBlock == -1) {//表示不在数组中return -1;}//获取这一块的起始索引和结束索引int startIndex = blockArr[indexBlock].getStartIndex();int endIndex = blockArr[indexBlock].getEndIndex();for (int i = startIndex; i < endIndex; i++) {if (arr[i] == number) {return i;}}return -1;}//定义一个方法，确定number在哪一块当中public static int findIndexBlock(Block[] blockArr, int number) {
/*        Block b1=new Block(21,0,5);Block b2=new Block(45,6,11);Block b3=new Block(73,12,17);*///从0索引开始，遍历blockArr，如果number小于max,表示number在这一块当中for (int i = 0; i < blockArr.length; i++) {if (number <= blockArr[i].getMax()) {return i;}}return -1;}
}class Block {private int max;private int startIndex;private int endIndex;public Block() {}public Block(int max, int startIndex, int endIndex) {this.max = max;this.startIndex = startIndex;this.endIndex = endIndex;}public int getMax() {return max;}public void setMax(int max) {this.max = max;}public int getStartIndex() {return startIndex;}public void setStartIndex(int startIndex) {this.startIndex = startIndex;}public int getEndIndex() {return endIndex;}public void setEndIndex(int endIndex) {this.endIndex = endIndex;}
}

排序算法

冒泡排序

1.相邻的数据两两比较，小的放前面，大的放后面。

2.第一轮比较完毕之后，最大值已经确定，第二轮可以少循环一次，后面以此类推

3.如果数组中有n个数据，总共我们只要执行n-1轮代码即可

//2.冒泡排序
//外循环：执行多少轮
for (int i = 0; i < arr.length - 1; i++) {//内循环：每一类如何比较数据获取最大值//-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;}}
}

选择排序

从0索引开始，拿着每一个索引的元素与后面的元素依次比较，小的放前面，大的放后面

    //外循环//表示循环几轮for (int i = 0; i < arr.length - 1; i++) {//内循环//拿着i与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;}}}printArr(arr);
}

插入排序

将0索引的元素到N索引的元素看作是有序的，把N+1索引的元素到最后一个当成是无序的。

遍历无需的元素，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面

public static void main(String[] args) {int[] arr = {3, 44, 38, 6, 47, 15, 36, 26, 27, 2, 46, 19, 60, 58};//1.找到无序的那一组，是从哪个索引开始的。 2int startIndex = -1;for (int i = 0; i < arr.length; i++) {if (arr[i] > arr[i + 1]) {startIndex = i + 1;break;}}//2.遍历后面无序的数组for (int i = startIndex; i < arr.length; i++) {//如何把遍历的数据插入？int j = i;while (j > 0 && arr[j] < arr[j - 1]) {//交换位置int temp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = temp;j--;}}printArr(arr);
}

快速排序

第一轮：把0索引的数字作为基准数，确定基准数在数组中正确的位置

比基准数小的全部放在左边，比基准数大的全部在右边

public static void quickSort(int[] arr, int i, int j) {//定义两个变量记录要查找的范围int start = i;int end = j;if (start>end){return;}//记录基准数int baseNumber = arr[i];//利用循环找到要交换的数字while (start != end) {//利用end从后往前找比基准数小的while (true) {if (end <= start || arr[end] < baseNumber) {break;}end--;}//利用start从后往前找比基准数大的while (true) {if (end <= start || arr[start] > baseNumber) {break;}start++;}//end和start交换int temp = arr[start];arr[start] = arr[end];arr[end] = temp;}//循环结束后，表示找到了，基准数的位置//基准数归位int temp = arr[i];arr[i] = arr[start];arr[start] = temp;//确定6左边的范围，重复刚做的事情quickSort(arr,i,start-1);//右边quickSort(arr,start+1,j);
}