黑马程序员__排序、查找和进制转换

时间:2022-09-12 23:44:22

 ------- 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;运算后maxminmid

//三者的值可能相等,然后再次经过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;//当要插入的数值不和数组中任意一个元素相等时的情况。一定是返回的maxmin中最大的那个值(并且一定是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、体现了结构化程序设计思想了