排序与搜索算法（Java实现）

一些排序算法与搜索算法的个人记录

1、排序算法

1.1、冒泡排序

//谁大谁去最后面
public class _01冒泡排序 {
    public static void main(String[] args) {
        int[] arr = {5, 6, 3, 8, 9, 1, 2, 7, 0, 4};
        arrange(arr);
        //操作数组名，static可以直接改变数组值
        for (int i : arr) {
            System.out.print(i + " ");

        }
    }
public static void arrange(int[] arr) {
        //引入数组需要定义,数组名可以和主函数名字相同，static
    for (int i = 0; i < arr.length - 1; i++) {
        //涉及到[i+1],要进行length-1
        boolean b = true;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            //减掉外层的i,以进行优化
            if (arr[j] > arr[j + 1]) {
                b = false;
                //如果已经拍好了，就不继续排序了，以进行优化
                int temp = arr[j];
                //for中的桥梁变量可以一直int?
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if (b) {
            //for中的桥梁变量可以一直int?
            break;
        }
        for (int k : arr) {
            //一个级别的for循环一个字母
            System.out.print(k + " ");
        }
        System.out.println();
        }
    }
}

1.2、插入排序

//从左到右的每一个元素从右到左挨个比较，放到对应的位置
public class _02插入排序 {
    public static void main(String[] args) {
        int[] arr = {5, 6, 3, 8, 9, 1, 2, 7, 0, 4};
        arrange(arr);
        //操作数组名，static可以直接改变数组值
        for (int i : arr) {
            System.out.print(i + " ");

        }
    }

    static void arrange(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >0;j--) {
                if (arr[j]<arr[j-1]){
                    int temp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                }
                else{break;}
            }
        }
    }
}

1.3、选择排序

//从左到右，与后面最小的进行交换，最小的直接交换最前面（区别于慢慢冒泡的冒泡排序）
public class _03选择排序 {
    public static void main(String[] args) {
        int[] arr={6,4,5,7,0,2,8,1,9,3};
        arrange3(arr);
        for(int i : arr){
            System.out.print(i+" ");
        }
    }
    public static void arrange3(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            int min=arr[i],pos=i;
            for (int j = i; j < arr.length; j++) {
                if(arr[j]<min){
                    min=arr[j];
                    pos=j;
                }
            }
            int temp=arr[i];
            arr[i]=arr[pos];
            arr[pos]=temp;
        }

    }
}

1.4、快速排序

//递归
//不断的把中间值（基准值）放在中间

//1.找出中间值放在中间，小于中间值的都在左边，大于中间值的都在右边
//2.递归的时候不能初始化值，要后进行值的传入

public class _04快速排序 {
    public static void main(String[] args) {
        int[] arr=new int[]{9,2,1,4,5,7,8,6,3,0};
        //已经定义了数组，再进行传值的时候，不用再加[]
        //长度：arr.length   最后一个标号：arr.length-1
        quickSort(arr,0,arr.length-1);

        //< length  ;     <=length-1
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

    //关于数组传入，要进行定义形参
    static void quickSort(int[] arr,int start,int end){

        //if语句进行递归的终止
        if (start >= end) {return;}
        //在递归内部对函数的变量进行定义
        //两层指针，一个start和end用来明确下一次递归
        // low和high一起进行当前递归
        int k = arr[start],low=start,high=end;
        //条件不是start<end,有可能是偶数，所以不用==
        while(low<high){
            while(low < high && k <= arr[high]) {
                high--;
            }
            arr[low] = arr[high];
            while(low < high && k >= arr[low]) {
                low++;
            }
            arr[high]=arr[low];
        }
        arr[high] = k;

        quickSort(arr,start,high-1);
        quickSort(arr,high+1,end);
    }
}

2、查找算法

2.1、二分搜索

public class _05二分搜索 {
    public static void main(String[] args) {
        //测试用例
        //有序数组
        int[] arr = new int[]{1,4,5,6,7,10,12,14,20,22,26};
        System.out.println(test(arr, 12));
    }

    private static int test(int[] arr,int target){
        //实现算法，找到target返回下标，没找到则返回-1
        int start = 0,end = arr.length-1;
        //明确循环多少次的时候用for,不明确的时候，类似搜索，用while
        while(start <= end){
            int mid = (start + end + 1)/2;
            if(arr[mid] == target) {
                return mid;
            }else if(arr[mid]>target){
                end=mid-1;
            }else if(arr[mid]<target){
                start=mid+1;
            }
        }return -1;
    }
}