day17_选择排序_数组的搜索算法

选择排序

规律:

image.png

//数组的排序操作（冒泡排序）
class ArraySortDemo 
{
    public static void main(String[] args) 
    {
        int[] arr = new int[]{2,9,6,7,4,1};
        ArraySortDemo.printArray(arr);//[2,9,6,7,4,1]
        selectinonSort(arr);
        ArraySortDemo.printArray(arr);//[1,2,4,6,7,9]
    }
    //选择排序
    static void selectinonSort(int[] arr)
    {
        /*
        //第一轮
        for (int i = 1;i <= arr.length - 1 ;i ++ )
        {
            if (arr[0] > arr[i])
            {
                swap(arr,0,i);
            }
        }
        //第二轮
        for (int i = 2;i <= arr.length - 1 ;i ++ )
        {
            if (arr[1] > arr[i])
            {
                swap(arr,1,i);
            }
        }
        //第三轮
        for (int i = 3;i <= arr.length - 1 ;i ++ )
        {
            if (arr[2] > arr[i])
            {
                swap(arr,2,i);
            }
        }
        */
        //代码加强
        for (int j = 1;j <= arr.length - 1;j ++ )
        {
                for (int i = j;i <= arr.length - 1 ;i ++ )
            {
                if (arr[j - 1] > arr[i])
                {
                    swap(arr,j - 1,i);
                }
            }
        }   
    }
}
    static void swap(int[] arr,int index1,int index2)
    {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
        static void printArray(int[] arr)
    {
        //思路:先打印数组"[]",再获取arr数组里面的元素,然后再做if判断,判断如果当前i的值不是最后一个索引,则拼接
        if (arr == null)
        {
            System.out.println("null");
            return;
        }
        String ret = "[";
        for (int i = 0;i < arr.length ;i ++ )
        {
            ret = ret + arr[i];
            //如果当前i不是最后一个索引,则拼接", "
            if (i != arr.length - 1)
            {
                ret = ret + ", ";
            }
        }
        ret = ret  +  "]";

        System.out.println(ret);
    }
}

数组的搜索算法之二分搜索法

image.png
image.png

//二分搜索法/二分查找法/折半查找
class BinarySeacheDemo 
{
    public static void main(String[] args) 
    {
        int[] arr =new int []{1,2,3,4,5,6,7,8,9,10};
        int index = binarySearch(arr,8);
        System.out.println(arr[index]);
    }
    //从arr数组中搜索key的元素,找到返回其索引,否则返回-1
    static int binarySearch(int[] arr,int key)
    {
        int low = 0;//最小的索引
        int high = arr.length - 1;//最大的索引
        while (low <= high)
        {
            System.out.println(low+"----------"+high);
            int mid = (low + high) >> 1 ;//中间索引
            int midVal = arr[mid];//将中间索引的元素赋值给变量midVal
            if(midVal > key)//猜大了
            {
                high = mid - 1;//最大的索引=中间索引-1(缩小搜索范围)
            }
            else if(midVal < key)//猜小了
            {
                low = mid + 1;//最小的索引=中间索引+1(缩小搜索范围)
            }
            else
            {
                return mid;//如果中间索引刚好=key值,就直接返回mid
            }
        }
        return -1;//假如说传入的元素没有在数组中,直接返回-1,表示不在该数组范围内,越界了.
    }
}