重庆龙头寺找做墩子师傅网站网站浏览器
目录
算法
查找算法
基本查找（顺序查找）
二分查找（折半查找）
分块查找
排序算法
冒泡排序
选择排序
插入排序
快速排序
递归算法
算法
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
查找算法
基本查找（顺序查找）
关键：
从0索引开始依次向后查找
方法：
public static boolean basicSearch(int[] arr,int number) {//基本查找 遍历数组查找所需结果for (int i = 0; i < arr.length; i++) {if(number == arr[i]){return true;}}return false;}}二分查找（折半查找）
关键：
数组中的数据是有序的
每次排除一半的查找范围，节省查找次数
方法：
public static int BinarySearch(int[] arr,int number) {//定义变量确定查找范围 最小肯定是0索引的int min = 0;//最大的索引是数组长度-1int max = arr.length-1;//开始循环查找数据，利用while循环，查找出索引直接返回结果while(true){if(min > max){//返回-1，调用时可以将-1与0作比较，得出数据索引是否存在return -1;}//中间位置int mid = (min + max) / 2;//arr[mid]>numberif(arr[mid]>number){max = mid - 1;}//arr[mid]<numberelse if(arr[mid]<number){min = mid + 1;}else{return mid;}}}分块查找
关键：
块内无序，块间有序。
一般分块是按照数组长度的开根号
具体问题，具体分析
方法：
//判断number在哪个块中private static int findIndexBlock(Block[] bArr,int number){//循环判断number在哪个块中for (int i = 0; i < bArr.length; i++) {if(number <= bArr[i].getMax()){return i;}}return -1;} //利用分块查找获取索引private static int getIndex(Block[] bArr,int[] arr,int number){int indexBlock = findIndexBlock(bArr,number);//数据不在数组中if(indexBlock == -1){return -1;}//数据在数组中 刚才获取了数据所属块的索引int startIndex = bArr[indexBlock].getStartIndex();int endIndex = bArr[indexBlock].getEndIndex();//遍历for (int i = startIndex; i <= endIndex; i++) {if(arr[i] == number){return i;}}return -1;}排序算法
冒泡排序
关键：
将相邻的数据进行比较，小的放前面，大的放后面。
方法：
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 tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}}选择排序
关键 ：
从0索引开始，用每个索引的元素与后面依次比较，小的放前面，大的放后面。
方法：
//循环次数for(int i = 0; i < arr.length-1;i++){//从哪个索引开始比较for (int j = 1+i; j < arr.length; j++) {if (arr[i] > arr[j]) {int tmp = arr[i];arr[i] = arr[j ];arr[j ] = tmp;}}}插入排序
关键：
将0索引到n索引看成有序的，n+1到最大索引是无序的。遍历无序数据，将其插入有序数据的合适位置
方法：
//确定无序数据的开始索引，依次插入有序数据中for (int i = startIndex; i < arr.length; i++) {int j = i;//相当于依次向左比较，直至到0索引为止while(j > 0 && arr[j] < arr[j-1]){int tmp = arr[j];arr[j] = arr[j-1];arr[j-1] = tmp;j--;}}快速排序
关键：
将0索引的数据作为基准数，左边都是比基准数小的，右边都是比基准数大的
方法：
public static void QuickSort(int[] arr, int startIndex, int endIndex) {//定义两个查找的范围 start~endint start = startIndex;int end = endIndex;//递归的出口if(end < start){return;}//0索引为基准数int baseNumber = arr[startIndex];while(end != start){while (true) {if (start >= end || arr[end] < baseNumber) {break;}end--;}while (true) {if (start >= end || arr[start] > baseNumber) {break;}start++;}int tmp = arr[start];arr[start] = arr[end];arr[end] = tmp;}int tmp = arr[start];arr[start] = arr[startIndex];arr[startIndex] = tmp;//递归条件QuickSort(arr,startIndex,start-1);QuickSort(arr,start+1,endIndex);}递归算法
方法中调用方法本身的现象
关键：
递归算法一定要有出口，否则内存会溢出
以大化小解决问题
方法：
//简单的累加递归public static int Recursion(int number) {if(number == 1){return 1;}return number+Recursion(number-1);}
//简单的求阶乘的递归public static int getNumber(int number) {if(number == 1){return 1;}return number * getNumber(number-1);}