标题: 个人分析的:最值,选择排序,冒泡排序,折半查找,元素插入 [打印本页] 作者: 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的值,将数组插入该位置就可以
*/