Java基础学习第八天(选择排序、冒泡排序、折半查找)

时间:2021-06-22 22:11:54

一、选择排序(直接排序)

使用一个元素与其他的元素挨个比较一次,符合条件交换位置。

class Demo8.1
{   
    //需求: 定义一个函数接收一个int类型的数组对象, 把数组中的最大值放在数组中的第一位。
    public static void main(String[] args) 
    {
        int[] arr = {12,5,17,8,9}; //对于5元素的数组,只需要找出4个最大值就可以排序了
        selectSort(arr);
    }
    public static void selectSort(int[] arr){       
        //把最大值放在首位置
        for(int j = 0; j<arr.length-1; j++){  //控制的是轮数
            for(int i = j+1 ; i<arr.length ; i++){ //找出最大值
                if(arr[i]>arr[j]){
                    //交换位置
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        //遍历数组,查看效果
        System.out.print("目前的元素:");
        for (int i = 0 ; i<arr.length  ;i++){
            System.out.print(arr[i]+",");
        }
    }
}

二、冒泡排序

使用相邻的两个元素挨个比较一次,符合条件交换位置。

class Demo8.2 
{
    //需求: 定义一个函数接收一个int类型的数组对象, 把数组中的最大值放在数组中的最后一位。
    public static void main(String[] args) 
    {
        int[] arr = {12,8,17,5,9}; // 最大的索引值: 4 容量:5 
        bubbleSort(arr);
    }
    public static void bubbleSort(int[] arr){
        // 把最大值放在最后一个位置
        for(int j = 0 ; j<arr.length-1 ; j++){ //控制轮数
            for(int i = 0 ; i<arr.length-1-j  ; i++){  //找出一个最大值 
                //相邻的元素比较
                if(arr[i]>arr[i+1]){
                    int temp  = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
        }
        //遍历数组,查看效果
        System.out.print("目前的元素:");
        for (int i = 0 ; i<arr.length  ;i++){
            System.out.print(arr[i]+",");
        }       
    }
}

三、 折半查找(二分法)

注意:使用前提必需是有序的数组。

class Demo8.3
{
    //需求:定义一个函数接收一个数组对象和一个要查找的目标元素,函数要返回该目标元素在数组中的索引值,如果目标元素不存在数组中,那么返回-1表示。
    public static void main(String[] args) 
    {
        int[] arr = {12,16,19,23,54};
        int index = halfSearch(arr,16);
        System.out.println("元素所在的索引值是:"+ index);
    }       
    public static int halfSearch(int[] arr, int target){
        //定义三个变量分别记录最大、最小、中间的查找范围索引值,每次使用中间索引值的元素与目标元素比较一次,如果不是需要的元素,那么缩小查找的范围
        int max = arr.length-1;
        int min = 0;
        int mid = (max+min)/2;
        while(true){
            if(target>arr[mid]){
                min = mid+1;
            }else if(target<arr[mid]){
                max = mid -1;
            }else{
                //找到了元素
                return mid;
            }
            //没有找到的情况
            if (max<min){
                return -1;
            }
            //重新计算中间索引值
            mid = (min+max)/2;
        }   
    }   
    public static int searchEle(int[] arr, int target){
        for(int i = 0 ; i<arr.length ; i++){
            if(arr[i]==target){
                return i;
            }
        }
        return -1;
    }
}

四、数组的工具类(Arrays)

① 转换成字符串:toString()
② 排序:sort()
③ 找元素在数组中的位置(二分查找法):binarySearch()

import java.util.*;
class Demo8.4 
{   
    public static void main(String[] args) 
    {
        int[] arr = {12,3,1,10,8};
        //排序的方法 > 1, 3, 8, 10, 12 
        Arrays.sort(arr);  

        String info = Arrays.toString(arr);
        System.out.println("数组的元素:"+ info);

        int index = Arrays.binarySearch(arr,9);// 二分法查找 : 如果能在数组中找到对应的元素,那么就返回该数据的索引值,如果没有找到那么就返回一个负数表示
        System.out.println("找到的索引值:"+ index);       
    }
}