java数据机构.冒泡排序,选择排序 插入排序 递归算法,递归求阶乘,快速排序-CSDN博客

冒泡排序

相邻两个元素比较,大的放右边,小的放左边
第一轮循环结束最大值已经找到,在数组最右边(归为算法)
第二轮在剩余的元素比较找到次大值,第二轮可以少循环一次
如果有n个数据,总共我们只要执行n-1论代码就可以了

   public static void main(String[] args) {
        //冒泡排序'


        int arr[]={2,4,5,3,1};


        //利用冒泡索引将他变成12345
        //第一轮结束后最大值在最右边

        for (int i = 0; i < arr.length-1-0; i++) {//这里是length-1的原因是因为比较第四个元素的时候 4跟5比较  5最后一个就不需要比较了


            if(arr[i]>arr[i+1]){

                int temp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;

            }

        }

        //遍历数组
        for (int i = 0; i < arr.length; i++) {
           // System.out.print(arr[i]+ " ");//2 4 3 1 5
        }



        //第二轮

        for (int i = 0; i < arr.length-1-1; i++) {//这里是length-1的原因是因为比较第四个元素的时候 4跟5比较  5最后一个就不需要比较了


            if(arr[i]>arr[i+1]){

                int temp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;

            }

        }

        //遍历数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+ " ");//2 3 1 4 5
        }

        //第三轮....
        //第四...

    }

以上代码比较冗余
改进思路:采用嵌套循环的思路.外循环表示要执行的轮数也就是length-1
{2,4,5,3,1}比如这个要执行的轮数是0 1 2 3 . 4轮即可
内循环是每轮内执行的代码根据以上代码得出是length-1-i. i是0 1 2 3 4依次
内循环第一次0索引执行每次的比较交换代码得到2 4 3 1 5
内循环

    public static void main(String[] args) {
        //冒泡排序'


        int arr[]={2,1,5,4,3};


        //利用冒泡索引将他变成12345
        //第一轮结束后最大值在最右边

        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {//这里是length-1的原因是因为比较第四个元素的时候 4跟5比较  5最后一个就不需要比较了

                //内循环:每一轮如何比较数据并找到最大值
                //-1是防止月结
                //-i是提高效率 每一轮执行的次数应该比上一轮少一次


                if(arr[j]>arr[j+1]){

                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;

                }

            }

        }
        printarr(arr);


    }

选择排序

核心思想 一轮比较确定一个最小的数据(归为),他就排在第一个
第二轮就直接从1索引开始找第二小的
拿着索引1的跟后面所有的比较一遍 遇见小的就交换

    public static void main(String[] args) {

        //选择排序
        int arr[]={2,4,5,3,1};

        //第一轮

        //int i = 0-1因为自己没有必要跟自己比较
        for (int i = 0+1; i < arr.length; i++) {
            if (arr[0]>arr[i]){
                int temp=arr[0];
                arr[0]=arr[i];
                arr[i]=temp;
            }


        }
        //printarr(arr);//1 4 5 3 2


        //第二轮

        //int i = 0-1因为自己没有必要跟自己比较
        for (int i = 0+2; i < arr.length; i++) {
            if (arr[1]>arr[i]){
                int temp=arr[1];
                arr[1]=arr[i];
                arr[i]=temp;
            }


        }
        //printarr(arr);//1 2 5 4 3



        //第三轮

        //int i = 0-1因为自己没有必要跟自己比较
        for (int i = 0+3; i < arr.length; i++) {
            if (arr[2]>arr[i]){
                int temp=arr[2];
                arr[2]=arr[i];
                arr[i]=temp;
            }


        }
        printarr(arr);//1 2 3 5 4 


    }

以下改进

    public static void main(String[] args) {

        //选择排序
        int arr[]={2,4,5,3,1};

      //外循环 表示我拿着哪个索引上的值跟后面的比较
        //length-1是因为最后一个索引不需要跟自己比较
        for (int i = 0; i < arr.length-1; i++) {

            for (int j =i+1 ; j < arr.length; j++) {
                //内循环是每一轮我要做什么事情
                //内循环表示拿着i跟i后面的数据交换 .j相当于i后面的数据
                if(arr[i]>arr[j]){
                    int temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                }
            }
        }
        printarr(arr);
    }

插入排序

插入排序思想:将前面的索引看成有序的(前面的几个取决于有序的有几个),后买你的看成无序的. 然后遍历无序,将遍历的到的元素插入有序序列中.如遇到相同数据,插在后面

 public static void main(String[] args) {
        int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};


        //找到无序数组从哪里开始
        int startIndex=-1;
        //用-1是因为-1是无效的相当于定义为0;

        for (int i = 0; i < arr.length; i++) {

            if(arr[i]>arr[i+1]){//这个相当于找到了前面有序的索引

                startIndex=i+1;//这个i相当于有序序列的最后一个索引 加一是无序序列的起始索引

                break;



            }




        }
        for (int i = startIndex; i < arr.length; i++) {//相当于遍历无序索引

            //遍历无序  得到元素与有序交换

            int j=i;//记录要插入数据的索引
            while(j>0&&arr[j]<arr[j-1]){//j当前元素.j-1前一个元素.  arr[j]可以理解为38 j-1就是44.然后交换 交换完后j--  j还是38  然后38和3判断

                int temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;

                j--;//表示我是与前面的数据判断的

            }




        }
        printarr(arr);//2 3 4 5 15 19 26 27 36 38 44 46 47 48 50 



    }

递归算法

就是方法自己调用自己

递归要写出口(就是调用自己到什么时候不调用自己了)否则就会跟上面一样导致栈溢出

递归求1~100的和

   public static void main(String[] args) {


        //求1到100的和 用递归思想

        //大问题拆成小问题
        //1~100之间的和=100+(1~99之间的和)
        //1~99之间的和=99+(1~98之间的和)
        //..
        //1~2之间的和=2+(1~1之间的和)
        //1~1之间的和=1;这个就是出口



        //找出口


        System.out.println(getSum(100));//5050

    }

    private static int getSum(int number) {
        if(number==1){
            return 1;
        }//出口


        return number+getSum(number-1);



    }

}

递归求阶乘

public class jiecheng {
    public static void main(String[] args) {
        //5的阶乘就是5!   5×4×3×2×1



        //找借口
        //找规律

        //大问题化小问题
        //5!  就是5×4!
        //4!  就是4×3!
        //...
        //1! 就是1(出口)

        System.out.println(getNumber(5));

    }

    private static int getNumber(int number) {
        if(number==1){
            return 1;
        }

        return number*getNumber(number-1);

    }
}

原理内存图

快速排序

  //快速排序的思想是:拿到一组数据  第一个作为基准数.
    //从头开始往后找找出比基准数大的.从尾部开始往前找  找比基准数小的
    //找到了直接交换数据 找不到继续往前找start++  end--.

    public static void main(String[] args) {
        int arr[]={6,1,2,7,9,3,4,5,10,8};

//第一一个方法 传入数组 头部和尾部

        quicksort(arr,0,arr.length-1);

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

    private static void quicksort(int arr[], int i, int j){

        int start=i;
        int end=j;
        if(start>end){//起始索引跑到结束索引后面了
            return;//这是递归出口
        }

        //传入基准数
        int basicNumber=arr[i];


        //利用循环找到要交换的数字
        while(start!=end){
            //利用end从后往前找 找到比基准数小的
            while(true){
                if(end<=start||arr[end]<basicNumber){
                    break;
                }

                end--;
            }

            //利用start从前往后找 找到比基准数da的
            while(true){
                if(end<=start||arr[start]>basicNumber){
                    break;
                }

                start++;

            }

            //把start和end指向的元素进行交换
            int temp=arr[start];
            arr[start]=arr[end];
            arr[end]=temp;
        }
        //把基准数跟start或者end交换

        int temp=arr[i];
        arr[i]=arr[start];
        arr[start]=temp;


        //3 1 2 5 4 6 9 7 10 8
        //这是第一轮结束后的结果

        //后面的直接用递归调用
        //这里的i相当于起始索引
        //start-1相当于 6前面的.  因为前面start跟i进行了交换
        quicksort(arr,i,start-1);//这是6左边
        quicksort(arr,start+1,j);//这是6的右边start+1相当于9

    }

总结