一、基本查找、二分查找
略
二、分块查找
将数组分块，每一个块中最大值小于后一个块中的最小值：块内无序，块间有序。
块：创建一个块类
按照规则划分好块之后，对要查询的值设计方法进行查询。
import java.util.Scanner;public class Main {public static void main(String[] args){ //JDK8int arr[]={16,5,12,9,21,18,32,23,37,26,45,34,25,48,61,52,73,66};Block block1=new Block(21,0,5);Block block2=new Block(37,6,11);Block block3=new Block(73,12,17);Block[] blockArr=new Block[]{block1,block2,block3};int index=getBlock(blockArr,52);if(index!=-1){int startindex = blockArr[index].getStartindex();int endindex = blockArr[index].getEndindex();System.out.println("输入你要找的数字: ");Scanner sc=new Scanner(System.in);int number = sc.nextInt();index=getindex(arr,number,startindex,endindex);if(index!=-1)System.out.println("索引： "+index);else System.out.println("不存在");}else System.out.println("不存在");}public static int getBlock(Block[] arr,int number){//确定数字number是在哪个块中for(int i=0;i<arr.length;i++){if(number<arr[i].getMax())return i;}return -1;}public static int getindex(int[] arr,int number,int startindex,int endindex){for(int i=startindex;i<endindex;i++){if(arr[i]==number)return i;}return -1;}}
class Block{int max;int startindex;int endindex;public Block() {}public Block(int max, int startindex, int endindex) {this.max = max;this.startindex = startindex;this.endindex = endindex;}/*** 获取* @return max*/public int getMax() {return max;}/*** 设置* @param max*/public void setMax(int max) {this.max = max;}/*** 获取* @return startindex*/public int getStartindex() {return startindex;}/*** 设置* @param startindex*/public void setStartindex(int startindex) {this.startindex = startindex;}/*** 获取* @return endindex*/public int getEndindex() {return endindex;}/*** 设置* @param endindex*/public void setEndindex(int endindex) {this.endindex = endindex;}public String toString() {return "Block{max = " + max + ", startindex = " + startindex + ", endindex = " + endindex + "}";}
}
三、冒泡排序
public static int[] MaoPaoSort(int[] arr){int temp;for(int i=0;i<arr.length;i++){for(int j=i+1;j<arr.length;j++){if(arr[j]<arr[j-1]){temp=arr[j];arr[j]=arr[j-1];arr[j-1]=temp;}}}return arr;}
四、选择排序
public static int[] SelectSort(int[] arr){ //选择排序 小———大int temp;for(int i=0;i<arr.length;i++){for(int j=i+1;j<arr.length;j++){if(arr[i]>arr[j]){temp=arr[i];arr[i]=arr[j];arr[j]=temp;}}}return arr;}五、插入排序
自己写的：
public static int[] InsertSort(int[] arr){int N=0,temp,beginindex=0;for(int j=N+1;j<arr.length;j++){if(arr[j]>=arr[N]){}else if(arr[j]<=arr[0]){temp=arr[j];backMove(arr,0,j);arr[0]=temp;}else if(arr[j]>arr[0]&&arr[j]<arr[N]){for(int i=0;i<N;i++){if(arr[j]<arr[i]){beginindex=i;break;}}temp=arr[j];backMove(arr,beginindex,j);arr[beginindex]=temp;}N++;}return arr;}private static int[] backMove(int[] arr,int beginindex,int endindex) {for(int i=endindex;i>beginindex;i--){arr[i]=arr[i-1];}return arr;}标准答案：
public static int[] InsertSort(int[] arr){int N=0,temp,beginindex=0;for(int j=N+1;j<arr.length;j++){while(j>0&&(arr[j]<arr[j-1])){temp=arr[j-1];arr[j-1]=arr[j];arr[j]=temp;j--;}N++;}return arr;}六、递归算法
递归指方法中调用方法本身的现象。
注意：递归一定要有出口（设定结束递归的条件），否则会造成内存溢出。
递归作用：
把一个复杂的问题层层转换成一个与原问题相似，但规模较小的问题来求解。
只需要少量的程序就可以描述出解题所需要的多次重复计算。
示例：
public static int getsum(int number){
//返回0~number 所有数的和if(number>0)return number+getsum(number-1);else return 0;} public static int getJieChen(int number){//获取number的阶乘if(number==1)return 1;elsereturn number*getJieChen(number-1);}七、快速排序
public static void QuickSort(int[] arr,int i,int j){int start=i,end=j;if(start>end){return;}int point=arr[i];//一定要把end部分放在start前面，这样才会在最后递归时指向比基准值小或者等于的元素while(start!=end){while (true) {if (end <= start || arr[end] < point) {break;}end--;}while (true) {if (start >= end || arr[start] > point) {break;}start++;}int temp=arr[start];arr[start]=arr[end];arr[end]=temp;}arr[i]=arr[start];arr[start]=point;QuickSort(arr,i,start-1);QuickSort(arr,start+1,j);}
