8.7数据结构与算法-5(冒泡排序 快速排序 选择排序 二分查找 )

1.冒泡排序的思路

思路

2.冒泡排序的代码实现

代码实现

import java.util.Arrays;

public class Demo8 {
    public static void main(String[] args) {
        int[] array = {2, 6, 8, 9, 1, 23, 45};
        int temp = 0;
        for (int j = 0; j < array.length - 1; j++) {
            for (int i = 0; i < array.length - 1 -j; i++) {
                if (array[i] > array[i + 1]) {
                    temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                }
            }
            System.out.println(Arrays.toString(array));
        }
    }
}

冒泡排序的优化

public class Demo8 {
    public static void main(String[] args) {
        int[] array = {2, 6, 8, 9, 11, 23, 45};
        int temp = 0;
        boolean temp1 = false;
        for (int j = 0; j < array.length - 1; j++) {
            for (int i = 0; i < array.length - 1 -j; i++) {
                if (array[i] > array[i + 1]) {
                    temp1 =true;
                    temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                }
            }

            System.out.println(Arrays.toString(array));
            if (!temp1){
                break;
            }
            else {
                temp1 = false;
            }
        }
    }
}

3.快速排序的示意图

找一个基准

4.快速排序代码实现(递归思想)

public class Demo8 {
    public static void main(String[] args) {


        int[] array = {1, 4, 6, 77, 77, 43};
        get2(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

    public static void get2(int[] array ,int low ,int hight){
        if (low > hight){
            return;
        }
        int i = low;
          int j = hight;
             int base =array[low];

             while (i < j){   
//上面的这个while的作用
                 while (array[j] >=base && i <j){//&&i<j 必须要加上去
                     j--;
                 }
                 while (array[i] <=base && i< j){
                     i++;
                 }
                 if (i < j) {
                     int temp = array[i];
                     array[i] = array[j];
                     array[j] = temp;
                 }
                 }
                 array[low] =array[i];
                 array[i] =base;


             get2(array,low,i-1);
             get2(array,i+1,hight);
    }
}

对于交换的代码理解: 最终目的的array[i] 值放在左边 使用的中间值起传递作用(赋值)

5.选择排序

选择排序示意图

代码实现

//两种方法实现选择排序
public class Demo5 {
    public static void main(String[] args) {
        int[] array = {1, 3, 2, 6, 8, 7, 99, 45, 22,22,22};
A1.get(array);
        //A2.get1(array);
        System.out.println(Arrays.toString(array));

    }
}
 class A1{
    public static void get(int[] arr){
        int temp =0;
        for (int i = 0; i < arr.length-1; 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;
                }
            }
        }
    }
}
class A2{
    public static void get1(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            int mindetex =i;
            int min = arr[i];
            for (int j = i +1; j < arr.length; j++) {
                if (min > arr[j]){
                    //赋值与重置
                    min = arr[j];
                    mindetex =j;
                }

            }
            if (mindetex != i) {//这个if语句是一种优化,如果不发生交换 下列语句是没有意义的.
                arr[mindetex] = arr[i];
                arr[i] = min;
            }

        }
    }
    }

7.插入排序

图解插入排序

8.二分查找示意图

示意图

9.二分查找代码

public class Demo6 {
    public static void main(String[] args) {
        int[] array = {1, 2, 5, 7, 8, 9, 11,88};
        int i = Demo7.get(array, 9);
        System.out.println(i);
    }
}
class  Demo7{
    public static int get(int[] array,int get){
        int min =0;
        int max = array.length-1;
        int bl =(min + max)/2;
        while (min <= max){
            if (get <array[bl] ){
                max = bl -1;
            }
           else if (get > array[bl]){
                min =bl+1;
            }
           else {
               return bl;
            }

            bl = (max + min) /2;

        }
        return -1;
    }
}