------- android培训、java培训、期待与您交流! ----------
1、选择排序:
/*
选择排序。(从小到大 升序排列)
内循环结束一次,最值出现头角标位置上。
*/
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 = arr[x];
arr[x] = arr[y];
arr[y]= temp;
*/
swap(arr,x,y);
}
}
}
}
2、 冒泡排序:
/*
冒泡排序。(从小到大 升序排列)
*/
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 = arr[y];
arr[y] = arr[y+1];
arr[y+1] = temp;
*/
swap(arr,y,y+1);
}
}
}
}
/*
发现无论什么排序。都需要对满足条件的元素进行位置置换。
所以可以把这部分相同的代码提取出来,单独封装成一个函数。
*/
public static void swap(int[] arr,int a,int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
另一种冒泡排序:
for(int x=arr.length-1;x>0;x--)
{
for(int y=0;y<x;y++)
{
if(arr[y]>arr[y+1])
{
int temp=0;
temp=arr[y];
arr[y]=arr[y+1];
arr[y+1]=temp;
}
}
}
3、 关于快速排序(递归排序)见当前文件夹文件 TwoSortArray.java 。
关于这两种排序的总结:
都是外层循环控制比较的趟数,趟数的得出是根据每一趟需要排列多少个剩余元素的个数而定的,内层循环控制每一趟比较的次数(比较次数的确定关键在于把握每一趟中有多少个元素需要进行比较)
4、速度最快、效率最高的排序就是希尔排序。
把堆内存中频繁的换位置转移到栈内存中,因为堆内存中换位置比较消耗资源,且效率较低(相对于栈内存来说)。参见第五节14分钟处
查找
1、折半查找:
第一种形式:
/*
折半查找。提高效率,但是必须要保证该数组是有序的数组。
*/
public static int halfSearch(int[] arr,int key)
{
int min,max,mid;
min = 0;
max = arr.length-1;
mid = (max+min)/2;
while(arr[mid]!=key)
{
if(key>arr[mid])
min = mid + 1;
else if(key<arr[mid])
max = mid - 1;
if(min>max) //用于判断数组arr中是否有和key相等的元素
return -1;
mid = (max+min)/2;
}
return mid; //返回与key值相等的数组元素值的下标
}
第一种形式的变体(我的方式,这个方式好!!)
public static int halfSearch(int[] arr,int key)
{
int min,max,mid;
min = 0;
max = arr.length-1;
mid = (max+min)/2;
while(arr[mid]!=key)
{
if(min==max)//当先经过mid = (max+min)/2;运算后max、min、mid
//三者的值可能相等,然后再次经过while(arr[mid]!=key)运算为true时,只要
//在在这里判断min==max就可以肯定,数组中没有与key相等的元素。
return -1;
if(key>arr[mid])
min = mid + 1;
else if(key<arr[mid])
max = mid - 1;
mid = (max+min)/2;
}
return mid;
}
第二种形式:(这是一种最好的方式)就记住这种方法啦,其他的都不记了!!
/*
折半的第二种方式折半查找提高效率,但是必须要保证该数组是有序的数组。
*/
public static int halfSearch_2(int[] arr,int key)
{
int min = 0,max = arr.length-1,mid;
while(min<=max)//与第一种方式的不同之处。
{
mid = (max+min)>>1;
if(key>arr[mid])
min = mid + 1;
else if(key<arr[mid])
max = mid - 1;
else
return mid;
}
return -1;
}
2、向数组中插入一个数。(这是一种最好的方式)就记住这种方法啦,其他的都不记了!!
/*
有一个有序的数组,想要将一个元素插入到该数组中,还要保证插入后的数组是有序的。如何获取该元素在数组中的位置。函数getIndex_2实现了该功能。
*/
public static int getIndex_2(int[] arr , int key)
{
int min = 0,max = arr.length-1,mid;
while(min<=max)
{
mid = (max+min)>>1;
if(key>arr[mid])
min = mid + 1;
else if(key<arr[mid])
max = mid - 1;
else
return mid+1;//当要插入的数值和数组中的某一个元素相等时的
//情况。其实也可以返回mid,但是返回mid+1可以使//需要移动的数组元素少一个。(把key插入到与之相等//的数组元素之后)
}
return min;//当要插入的数值不和数组中任意一个元素相等时的情况。一定是返回的max、min中最大的那个值(并且一定是min大于max的)。
}
3、普通的插入和查找:(我感觉这个普通的更加简单,而且不用管数组是否有 序!!)
/** 普通查找查找一个数组中的元素key */
public static int search(int[] arr , int key)
{
for(int i=0; i<arr.length; i++)
{
if(key==arr[i])
return i;
}
return -1; //表示没有找到key;
}
/**普通插入向一个升序数组中插入一个元素key*/
public static void insertIndex(int arr[] , int key)
{
for(int i=0;i<arr.length;i++)
{
if(key<arr[i])
return i;
}
return i;
}
进制转换:
1、 十进制转换成二进制:
/*
十进制-->二进制
*/
public static void toBin(int num)
{
StringBuffer sb = new StringBuffer();
while(num>0)
{
//System.out.println(num%2);
sb.append(num%2);//这种方法不能用来转换负数。(也即num不能为
//负数)
num = num / 2;
}
System.out.println(sb.reverse());
}
另外一种方法:使用递归!
public static void toBin(int num)
{
if(num>0)
{
toBin(num/2);
sop(num%2);
}
}
2、十进制转换成二进制的另一种方式(这种方法可以用来转换负数关键在于这两句):
public static void toBin(int num)
{
//定义二进制的表。
char[] chs = {'0','1'};
//定义一个临时存储容器。
char[] arr = new char[32];
//定义一个操作数组的指针
int pos = arr.length;
while(num!=0)
{
int temp = num & 1;
arr[--pos] = chs[temp];
num = num >>> 1;
}
for(int x=pos; x<arr.length; x++)
{
System.out.print(arr[x]);
}
}
3、十进制转换成十六进制:(其实也可以像十进制-->二进制类似来个模16除十六)
/*
十进制-->十六进制。
*/
public static void toHex(int num)
{
StringBuffer sb = new StringBuffer();
for(int x=0; x<8; x++)
{
int temp = num & 15;
if(temp>9)
//System.out.println((char)(temp-10+'A'));
sb.append((char)(temp-10+'A'));
else
//System.out.println(temp);
sb.append(temp);
num = num >>> 4;
}
System.out.println(sb.reverse());
}
我的方法:
int a=Integer.parseInt(args[0]); //获取要转换的数字
int[] b= new int[8];
int i=0;
while(a!=0)
{
b[i]=a&15;
i++;
a=a>>>4;
}
for(int j=i-1;j>=0;j--)
{
if(b[j]<10)
System.out.print(b[j]+" ") ;
else
System.out.print(((char)(b[j]+55))+" ");
}
4、查表法十进制转换成十六进制:
/*
0 1 2 3 4 5 6 7 8 9 A B C D E F ==十六进制中的元素。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
查表法:将所有的元素临时存储起来。建立对应关系。
每一次&15后的值作为索引去查建立好的表。就可以找对应的元素。
这样比 -10+'a'简单的多。
发现终于出结果了。但是是反着的。想要正过来呢?可以通过StringBuffer reverse功能来完成。
但是这个工具还没有学习。
所以可以使用已经学习过的容器:数组来完成存储。;
*/
public static void toHex(int num)
{
char[] chs = {'0','1','2','3'
,'4','5','6','7'
,'8','9','A','B'
,'C','D','E','F'};
//定义一个临时容器。
char[] arr = new char[8];
int pos = arr.length; //pos用于表示存储当前temp的值的arr下标
while(num!=0)
{
int temp = num & 15;
//System.out.println(chs[temp]);
arr[--pos] = chs[temp];
num = num >>> 4;
}
System.out.println("pos="+pos);
//存储数据的arr数组遍历。
for(int x=pos;x<arr.length; x++)
{
System.out.print(arr[x]+",");
}
}
5、十进制转换成二、八、十六进制的代码优化:(查表法进制转换)这种方 法是最好的方法,就记忆这种方法啦!!
/*
十进制-->二进制
*/
public static void toBin(int num)
{
trans(num,1,1);
}
/*
十进制-->八进制
*/
public static void toBa(int num)
{
trans(num,7,3);
}
/*
十进制-->十六进制
*/
public static void toHex(int num)
{
trans(num,15,4);
}
public static void trans(int num,int base,int offset)//base表示的是与(&)上的
//数值,offset表示无符号右移(>>>)的位数
{
if(num==0)
{
System.out.println(0);
return ;
}
char[] chs = {'0','1','2','3'
,'4','5','6','7'
,'8','9','A','B'
,'C','D','E','F'};
char[] arr = new char[32];
int pos = arr.length;
while(num!=0)
{
int temp = num & base;
arr[--pos] = chs[temp];
num = num >>> offset;
}
for(int x=pos; x<arr.length; x++)
{
System.out.print(arr[x]);
}
return ;
}
关于进制转换的总结:
1、最好采用位运算中的与运算(&)和无符号右移运算(>>>)这样做也可以转换负数
2、关于“十进制转换成二、八、十六进制的代码优化”的问题,用函数trans( int num , int base , int offset )来实现的好处就是减少了编写函数的复杂程度,这样做也符合了结构化程序设计的思想。如果把这个函数的参数定义成“源进制-->目的进制”那么会加大编写这种函数的复杂程度,这样做也不符合结构化程序设计的思想。如果要把源进制和目的进制作为进制转换函数trans_one_two()的参数,那么可以让这个函数调用trans ( int num , int base , int offset )函数来实现。
3、体现了结构化程序设计思想了。