黑马程序员技术交流社区

标题: 个人分析的:最值,选择排序,冒泡排序,折半查找,元素插入 [打印本页]

作者: c8984771    时间: 2015-12-27 15:21
标题: 个人分析的:最值,选择排序,冒泡排序,折半查找,元素插入
/*
需求1:求数组最大值
思路:
        定义功能函数,接收一个数组,返回最大值
        需要进行循环遍历来比较
        每次比较都会产生一个较大的值
        定义变量来进行临时存储
        最后将该变量所存储的元素就是最值
*/
class ArrayTest
{
        public static int max(int[] arr)
        {
                int temp = 0;
                for (int x = 1; x < arr.length ;x++ )
                {
                        if (arr[x] > arr[temp])
                        {       
                                temp = x;               
                        }
                }
                return arr[temp];
        }
        /*
        需求2:定义一个功能用来实现选择排序
        思路:选择排序:选择0角标为目标位置,不断和后面的元素比较,与较小的元素进行位置互换.这样可以0角标位得到数组最小值
                0角标位比较结束后,再以下一个角标位的元素为目标位置和后面的元素比较,与较小元素位置互换,
                当选择从0角标位开始比较,会发现目标位置越往后移,比较次数越少,类似与for嵌套循环打印的倒三角一样
                外循环每循环一次,与内循环的循环挨个比较一遍,所以选择排序可使用for嵌套循环的方法实现.
                注意:外循环可以少遍历一次,因为最后一个元素不需要再比较了
        */
        public static void selectSort(int[] arr)
        {
                for (int x = 0;x < arr.length-1;x++ )
                {
                        for (int y = x+1;y < arr.length ;y++ )
                        {
                                if (arr[x]>arr[y])
                                {
                                        int temp = 0;
                                        temp = arr[x];
                                        arr[x] = arr[y];
                                        arr[y] = temp;
                                }
                        }
                }
        }
        /*
        需求:定义功能冒泡排序
        思路:冒泡排序:相邻两个元素比较,如果满足条件就换位,每次从0角标位开始比,如果比下一个元素大,就进行位置互换,这样进行
                 一轮比较后,值最大的元素就被换到了数组最后的位置上.
                 再从头进行一轮比较,数组中第二大的元素就被换到了倒数第二的位置上,此时就不用再与最后面那个元素比较了
                 也就是没一轮比较都可以较上一轮少比较一次.可以看出,整体的步骤就是:每次从0角标位开始,随着每轮比较数
                 递增,与后面元素的比较次数在递减,所以可用for嵌套循环实现.
                 注意:外循环也可以少遍历一次,内循环必须少遍历一次,否则当第一次遍历到最大角标位时,一旦要求与下一个
                 元素进行比较就越界了
        */
        public static void bubbleSort(int[] arr)
        {
                for (int x = 0;x < arr.length-1 ;x++ )
                {
                        for (int y = 0; y < arr.length-x-1;y++ )
                        {
                                if (arr[y] > arr[y+1])
                                {
                                        int temp = 0;
                                        temp = arr[y];
                                        arr[y] = arr[y+1];
                                        arr[y+1] = temp;
                                }
                        }
                }
        }
        /*
        功能:打印数组
        */
        /*
        需求:折半查找,定义函数时,传入目标数组和目标元素,返回该元素在数组中的位置角标
        思路:折半查找:
                一个较高效的查找方式,只能操作有序的数组
                需要定义三个值,最小值min代表0角标,最大值max代表末尾角标arr.length-1,中间值mid=(min+max)/2,
                查找的过程用while循环完成,循环条件是mid位置的元素不等于key,这样找到key后会自动停止
                如果目标元素key的值比mid位置元素值大时,说明目标范围在数组的后半段,这时把min的位置改为mid+1,
                如果目标元素key的值比mid位置元素值小时,说明目标范围在数组的前半段,这时把max的位置改为mid-1,
                重新确定中间值mid,再重复拿mid位置的值与key作比较,当出现arr[mid]==key时,目标找到,返回mid
                当目标元素key不存在数组中时,某一时刻min值大于max值,此时返回-1

        */
        public static int halfSeek(int[] arr, int key )
        {
                int min = 0;
                int max = arr.length-1;
                int mid = (min+max)/2;
                while (arr[mid] != key)
                {
                        if (arr[mid] < key)
                                min = mid+1;
                        else
                                max = mid-1;
                        mid = (min+max)/2;
                        if(min > max)
                                return -1;
                }
                return mid;
        }

        public static void arrPrint(int[] arr)
        {
                System.out.print("[");
                for (int x = 0;x < arr.length ;x++ )
                {
                        if (x < arr.length-1)
                                System.out.print(arr[x]);
                        else
                                System.out.println(arr[x]+"]");
                }
        }
        public static void main(String[] args)
        {
                int[] arr = {1,9,2,3,8,4,7,5,6};
                //int a = max(arr);
                //selectSort(arr);
                bubbleSort(arr);
                int k = halfSeek(arr,1);
                arrPrint(arr);
                System.out.println(k);
        }
}
/*
插入元素练习:有一个有序数组,想要将一个元素插入到该数组中,还要保证该数组有序.
             其实就是折半查找的演变方法.可以将要插入的元素作为目标数组进行折半查找,
             如果数组中存在该元素,就插入到该元素所在的位置,
             如果不存在该元素,就让查找方法返回min的值,将数组插入该位置就可以
*/


作者: 三分醉    时间: 2015-12-27 15:34
不说别的了 已收藏




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2