JAVA学习日记（十二）算法

一、基本查找、二分查找

略

二、分块查找

将数组分块，每一个块中最大值小于后一个块中的最小值：块内无序，块间有序。

块：创建一个块类 

按照规则划分好块之后，对要查询的值设计方法进行查询。

import java.util.Scanner;

public class Main {
    public static void main(String[] args){ //JDK8

        int 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;
        else
        return 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);

    }