黑马程序员—排序与一些算法的认识

发布时间:2017-2-20 9:40:46 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"黑马程序员—排序与一些算法的认识",主要涉及到黑马程序员—排序与一些算法的认识方面的内容,对于黑马程序员—排序与一些算法的认识感兴趣的同学可以参考一下。

1.排序,排序有很多中,在代码应用最多的排序,一般的是,选择排序,冒泡排序,插入排序,虽然一些排序效率很高,(例如:希尔排序)但一般应用较少而且难以理解 (1)选择排序    它的原理是数组中的一个元素跟其他元素依次进行比较,来确定自己的位置。  (2)冒泡排序    它的原理是数组中的相邻的两个元素进行比较,比较出现大小,根据是升序还是降序交换位置,    比较完一次就可以把数组的最后一位就确定(最大值或最小值)这样最后一位就不用参与比较,    这样依次就可以排出数组顺序,相较于选择排序,冒泡较为提高效率。  (3)插入排序    插入排序它的实现原理 通俗讲就是把数组元素看做一个有序表和一个无序表,    开始有序表只包含一个元素,无序表中包含n-1个元素,排序过程中每次从无序表中取出第一个元素,    把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。    也就是说    (为了方便理解我就想是建立一个临时容器进行存储,但是数组类型,数组是一个不变长度的类型,这是不成立只是为了理解) class Test1 {  public static void main(String[] args)  {   //创建一个数组   int[] arr= {4,5,1,7,8,9,2};   //调用排序方法   arr=insert(arr);   //对排序后的数组进行打印   System.out.print("int[] arr={");   for (int i=0;i<arr.length;i++ )   {    //对数组角标位进行判断    if(i!=arr.length-1)     System.out.print(arr[i]+",");    else     System.out.println(arr[i]+"}");   }        } //插入排序  public static int[] insert(int[] arr)//封装成一个方法以便函数调用,  {   //遍历原数组,从角标1开始,因为当进行比较时,必须是两个元素比较大小的   //0角标位上元素和1角标位上的元素。   for (int x=1;x<arr.length ;x++ )   {    //这里这么定义只是为了好理解    int value = arr[x];// 待插入的值     int index = x;// 待插入的位置        //循环判断条件比较大小,当index>0时,比较条件满足直接交换值,插入了值与此同时待插入的角标位重新赋值,角标位向前移动。    while (index>0 && value<arr[index-1])    {     //定义第三方变量,插入值      int temp=arr[index];                    arr[index]=arr[index-1];  //待插入的位置重新赋更大的值                  arr[index-1]=temp;                    index--;  //位置向前移动。    }   }         return arr; //返回一个数组以便对象调用。  }  //冒泡排序!  public static void maoPao(int[] arr)  {   //外循环x控制的是比较的范围。角标不能自己跟自己比,所以想x<arr.length-1   for (int x= 0;x<arr.length-1 ;x++ )   {    //内循环时,相邻的角标比,比出大小,交换位置,比完一次后,最值就出现在了最后一个角标上,    //当第二次比较时y的范围就要缩小x,所以y<arr.length-x-1,每次的最值都会出现在被比较的最后一个角标上了    //以此类推,一个有序的数组就出来了,    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;     }    }   }  } //选择排序  public static void select(int[] arr)  {   //0角标上的元素依次与1角标、2角标...arr.length-1角标比较。   //外循环控制的是 比较角标,内循环控制的是被比较角标。   //外形循环直取到arr.leng-2角标,就不取了,因为arr.length-1角标不会自己跟自己比。   //内循环,是被比较的角标,他首先是比外循环的角标要大1,这样被比较的角标和比较角标不会相同,而是相邻。   //而且内循环被比较的角标是可以取到arr.length-1角标的   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;     }    }   }  } } 通过常用相关资料对于算法一些认识 1.递归算法: /* 猴子吃桃的问题:猴子第一天摘下来N个桃子,当天就吃了一半,但是还不过瘾,又多吃了一个,第二天早上又将 剩下的桃子吃了一半,又多吃了一个,以后每天早上都吃了前一天剩下的一半零一个,到第十天早上的时候就发现剩下 一个桃子了.求第一天一共摘下了多少桃子呢? */ class  TaoZi {         public static void main(String[] args)         {                 int sum = 0;                 sum = sum(1); System.out.println("一共吃了"+sum+"个桃子");         }         public static int sum(int day)//递归算法         {                 int count = 0;                 if(day == 10)                 count = 1;                 else                         count = (sum(day+1)+1)*2;//今天的总量等于下一天的总量加上一个的和的2倍                 return count;         } } 2.枚举算法(暴力算法) 五只猴子一起摘了一堆桃子,因为太累了,它们商量决定,先睡一觉再分。一会其中的一只猴子来了,它见别的猴子没来,便将这堆桃子平均分成5份 ,结果多了一个,就将多的这个吃了,并拿走其中的一份。一会儿,第2只猴子来了,他不知道已经有一个同伴来过,还以为自己是第一个到的呢,于是将地上的桃子堆起来,再一次平均分成5份,发现也多了一个,同样吃了这1个,并拿走其中一份。接着来的第3、第4、第5只猴子都是这样做的……根据上面的条件,问这5只猴子至少摘了多少个桃子?第5只猴子走后还剩下多少个桃子? 设总的桃子数为S0,五子猴子的桃子数分别为S1、S2、S3、S4、S5,则有以下关系式:S0 = 5*S1 + 1;4*S1 = 5*S2 + 1;4*S2 = 5*S3 + 1;4*S3 = 5*S4 + 1;4*S4 = 5*S5 + 1;我们可以枚举桃子总数S0,从5开始直到满足条件,此时S0的值就是最少的总桃子数。程序如下:   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include <stdio.h> int main(void) {     int s[6] = {0};     int i;       for(s[0]=5; ;s[0]++)     {         s[1] = s[0] - 1;         if (s[1]%5)  // (s[0] – 1)要能被5整除             continue;         else             s[1] /= 5;                    s[2] = 4 * s[1] - 1;         if (s[2]%5)  // (4 * s[1] - 1)要能被5整除             continue;         else             s[2] /= 5;                s[3] = 4 * s[2] - 1;         if (s[3]%5)             continue;         else             s[3] /= 5;                s[4] = 4 * s[3] - 1;         if (s[4]%5)             continue;         else             s[4] /= 5;                    s[5] = 4 * s[4] - 1;         if (s[5]%5)             continue;         else             s[5] /= 5;                    break; } printf("摘了%d个桃子, 剩下%d个桃子/n", s[0], s[5]*4);     for (i=0; i<6; i++)         printf("%d  ", s[i]);     getchar();     return 0;  } 程序输出:摘了3121个桃子, 剩下765个桃子。 在进行归纳推理时,如果逐个考察事件的所有结果,因而得出一般结论,那么这结论是可靠的,这种归纳方法叫做枚举法。特点:将问题的所有可能的答案一一列举,然后根据一般的结果进行判断是否合适,合适就保留,不合适就丢弃。 3.hash算法 hash算法也是散列算法,也就是散列表,它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的做法。顾名思义,该数据结构可以理解为一个线性表,但是其中的元素不是紧密排列的,而是可能存在空隙。 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 比如我们存储70个元素,但我们可能为这70个元素申请了100个元素的空间。70/100=0.7,这个数字称为负载因子。我们之所以这样做,也是为了“快速存取”的目的。我们基于一种结果尽可能随机平均分布的固定函数H为每个元素安排存储位置,这样就可以避免遍历性质的线性搜索,以达到快速存取。但是由于此随机性,也必然导致一个问题就是冲突。所谓冲突,即两个元素通过散列函数H得到的地址相同,那么这两个元素称为“同义词”。这类似于70个人去一个有100个椅子的饭店吃饭。散列函数的计算结果是一个存储单位地址,每个存储单位称为“桶”。设一个散列表有m个桶,则散列函数的值域应为[0,m-1]。       解决冲突是一个复杂问题。冲突主要取决于: (1)散列函数,一个好的散列函数的值应尽可能平均分布。 (2)处理冲突方法。 (3)负载因子的大小。太大不一定就好,而且浪费空间严重,负载因子和散列函数是联动的。       解决冲突的办法:      (1)线性探查法:冲突后,线性向前试探,找到最近的一个空位置。缺点是会出现堆积现象。存取时,可能不是同义词的词也位于探查序列,影响效率。      (2)双散列函数法:在位置d冲突后,再次使用另一个散列函数产生一个与散列表桶容量m互质的数c,依次试探(d+n*c)%m,使探查序列跳跃式分布。        

上一篇:位操作-找到数组中只出现一次的数字
下一篇:PHP分页类

相关文章

相关评论