A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 李志广 中级黑马   /  2012-6-27 10:39  /  2432 人查看  /  9 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 007lzg 于 2012-6-30 16:21 编辑

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;
                                }
                        }
                }
        }
关于arr.length-x-1老师讲的我还是有点不明白。我想问一下,还有没有其他的方法来解决冒泡问题呢,我记得以前学习C语言事也遇到过这样的问题?

9 个回复

倒序浏览
本帖最后由 王明明 于 2012-6-27 11:14 编辑

public static void bubbleSort(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;
                                }
                        }
                }
        }
选择排序
先说说冒泡排序
49 38 65 97 76 13 27 看这组数字
经过第一轮49跟38交换 然后 到65跟97交换
一轮结束 38 49 65  76 13 27 97 最大的就放到最后面去了
然后第二轮 76 就放后面去了
一轮放一个大的后面去
至于 你说的 y<arr.length-x-1 你看上面 就知道每次 比较的数字减少一个 所以y也减去X

说说选择排序
49 38 65 97 76 13 27
首先 一轮  
13 49 65 97 76 38  27
13 27 65 97 76 49 38  
选择性的把最小的排到最前面
用X跟后面所有的比较
把最小的位置往前排





评分

参与人数 1技术分 +1 收起 理由
黄奕豪 + 1 赞一个!

查看全部评分

回复 使用道具 举报

参考下看看
int temp;//临时变量,用来进行数据交换。
for(int i=0;i<nums.length;i++){//冒泡排序每次只能将一个最大或者最小的数找出来,因此外层循环决定一共冒多少次
  for(int j=0;i<nums.length-i-1;j++){//内循环是完成一次冒泡,每次都从第一个数开始,比较次数是N-1次,因为不需要和自己比,至于减掉的i则是已经冒出去的数,已经冒出的数不是最大就是最小,没有必要去比。
   if(nums[j]<nums[j+1]){//升序或者降序只需要修改if中的大于或者小于就可以了。
       temp=nums[j];//这里进行的是数据的交换。就相当于将2个杯子里的水交换,需要用第三个杯子来临时存放其中的一杯水一样。
       nums[j]=nums[j+1];
       nums[j+1]=temp;

评分

参与人数 1技术分 +1 收起 理由
刘蕴学 + 1 赞一个!

查看全部评分

回复 使用道具 举报
冒泡法就是相邻的元素比较大小,把最值往后放,下面详细介绍一下这段代码的执行过程
public static void bubbleSort(int[] arr)
         {
                w: for(int x=0; x<arr.length-1; x++)
                 {                                                                        
                      k:  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;
                                 }
                         }
                 }
         }

把外循环标记为w,内循环标记为k,假定数组arr是长度为4的数组,也就是下标从0~3。arr[4]={3,5,4,9};
第一次比较:w:arr[0]     x=0
                   k:第一次:arr[0](3)<arr[1](5),满足条件,交换位置。此时,arr[0]=5,arr[1]=3.
                      第二次:arr[1](3)<arr[2](4),  满足条件,交换位置。此时,arr[1]=4,arr[2]=3.
                      第三次:arr[2](3)<arr[3](9),  满足条件,交换位置。此时,arr[2]=9,arr[3]=3.
                      共次:arr.length-x-1=4-0-1
         第一次循环后arr[4]={5,4,9,3},此时arr[3]=3是最小的元素,不需要再参于比较了。
第二次比较:w:arr[1]    x=1
                   k:第一次:arr[0](5)>arr[1](4),  不满足条件。
                     第二次: arr[1](4)<arr[2](9),  满足条件,交换位置。此时,arr[1]=9,arr[2]=4.
                     共次:arr.length-x-1=4-1-1=2.
            第二次循环后arr[4]={5,9,4,3},此时arr[2]=4是倒数第二小的元素,不需要再参于比较了。
第三次比较:w:arr[2]     x=2
                   k:第一次:arr[0](5)<arr[1](9),  满足条件,交换位置。此时,arr[0]=9,arr[1]=5.
                      共次:arr.length-x-1=4-2-1
             第三次循环后arr[4]={9,5,4,3},排序完成。


评分

参与人数 1技术分 +1 收起 理由
黄奕豪 + 1 赞一个!

查看全部评分

回复 使用道具 举报
  for(int y=0; y<arr.length-x-1; y++)//因为内循环每次比较的次数都随着x的增加而减少,所以要减去x;因为比较的是arr[y]<arr[y+1],减1是
                                 //为了防止角标越界

{
           if(arr[y]<arr[y+1])
          {
                       int temp = arr[y];
                         arr[y] = arr[y+1];
                        arr[y+1] = temp;
              }
}

评分

参与人数 1技术分 +1 收起 理由
刘蕴学 + 1 赞一个!

查看全部评分

回复 使用道具 举报
本帖最后由 Forever。 于 2012-6-27 11:48 编辑

其实上面说了那么多就是楼上同学一针见血嘛,就是为了防止数组下表越界嘛……
同学我建议你大可试一下吧-1删除的时候你试试会出现什么事情。其实问题就自然出来了。
回复 使用道具 举报
  for(int x=0; x<arr.length-1; x++)                                                                    
        for(int y=0; y<arr.length-x-1; y++)
这个循环楼主你不太能理解,外层循环是控制循环次数,内层循环是控制每次比较的次数。冒泡的思想就是每通过一次比较,讲一个最大的或者最小的值放在数组的最前端或者最后端,下次比较从这个值的后边开始进行,所以内层每次比较的次数都得减小,故而要减去外层的x,冒泡排序是一种运算效率比较高的算法,当然你也可以使用其他的排序算法,比如选择排序、堆排序

评分

参与人数 1技术分 +1 收起 理由
黄奕豪 + 1 赞一个!

查看全部评分

回复 使用道具 举报
嗯 冒泡排序的原理先说一下,就是将大的数沉到底,小的数网上浮  
举个简单的例子吧  现在有五个数要比较  1,2,5,8,3 首先我们可以在纸上画一下他的比较过程 来帮助你理解程序,冒泡排序的算法是这样的,从第一个开始跟第二个比较,如果小于第二个不交换,如果大于,就交换,就好像咱们这个程序,给数组定个名字吧 a ,a[0]<a[1]所以不用交换,然后拿第二个和第三个比,这样比较下来之后总是大的在最下面,所以第一趟比较后 的结果就是 1,2,5,3,8 这样最大的8 就沉到下面了,那第二趟我们只需比较前面四个就行了,这时要比较三次,a[0]和a[1]    a[1]和a[2]   a[2]和a[3] 这样就能将5放在8的上面,第三趟就比较两次,就好,第四趟比较1次,这样就排好顺序了 。
所以我们总结了,有N个数,需要比较n-1趟,每一趟需要比较多少次,5个的话,第一趟是4次,第二趟是3次,第三趟是2次,依次类推,这样假如比较第i趟,那么就需要比较n-1-i趟,i从1 开始

这样我们通过双重循环就能控制了,外边一层控制比较的趟数,里面控制比较的次数 这样就很容易实现了
for(int i=1;i<N;i++)
  for(int j=0,j<N-i;<j++)这里就讲你的疑惑吧,假如N是5,第一趟i=1 内循环j最大为3,这样的话,数组下边最大为3 也就是到a[3] 这样你才能arr[y]<arr[y+1 这样比啊,正好是a[3]和a[4]不就是第五个数吗,第二趟也是  依次类推 你可以在纸上画一下

评分

参与人数 1技术分 +1 收起 理由
刘蕴学 + 1

查看全部评分

回复 使用道具 举报
这貌似是基础测试题
回复 使用道具 举报
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int number;



struct student
{
int num;
char name[20];
float score;
}s1[15];


void input(struct student a[]);
void output();
void sort();
void search();
void shouye();
void fanhui();
void biaoti();
int max();









main()
{   biaoti();
int c;
while(true)
{    shouye();  
     printf("请输入选项 ");
  scanf("%d",&c);
   switch(c)
{
     case 1 : input(s1);fanhui();break;
     case 2: output();fanhui();break;
        case 3: sort();fanhui();break;
  case 4: search();fanhui();break;
  case 5: exit(0);
     default:printf("错误");
}
       fflush(stdin);
        getchar();
        system("cls");

      
    }
      


}

void input(struct student a[])
{   char choice='y';
    int m=0;
   while(choice=='y')
   {    printf("请输入姓名:");
        scanf("%s",&a[m].name);
        printf("学号:");
        scanf("%d",&a[m].num);
        printf("成绩:");
  float ff;
        scanf("%f",&ff);
        a[m].score=ff;
        m++;
  printf("%d",m);
  printf("继续添加?(y/n) \n");
  fflush(stdin);
  choice=getchar();

  }
   number=m;
   

}

void output()
{
    int i=0;
    printf("以下是全部学生成绩\n");
    printf("\t姓名\t学号\t成绩\n");
    for(i=0;i<number;i++)
    {
        printf("\t%s\t%d\t%f\n",s1[i].name,s1[i].num,s1[i].score);
    }
}

void shouye()
{。。。。}
void fanhui()
{printf("\t===>按Enter键返回主菜单\n");}

void biaoti()
{。。。}


void sort()
{   
int i=0,j=0,numtemp=0;
float scoretemp;
  char nametemp[20];

  for(i=0;i<number;i++)     
  {
   for(j=0;j<number-i;j++)
   {  
   if(s1[j].score>s1[j+1].score)
   {  
      scoretemp=s1[j].score;
      s1[j].score=s1[j+1].score;  
      s1[j+1].score=scoretemp;
      
      numtemp=s1[j].num;
      s1[j].num=s1[j+1].num;  
      s1[j+1].num=numtemp;
      
   strcpy(nametemp,s1[j].name);
   strcpy(s1[j].name,s1[j+1].name);
   strcpy(s1[j+1].name,nametemp);


      

   }
   }
  }
printf("排序结果:\n");
printf("\t成绩\t学号\t姓名\n");
for(i=0;i<number;i++)   
   
printf("\t%f\t%d\t%s\n",s1[i].score,s1[i].num,s1[i].name);

}


void search()
{   char name[20];
int i;
printf("请输入学生姓名:");
scanf("%s",&name);
for(i=0;i<number;i++)
{ if (strcmp(name,s1[i].name)==0)
{printf("\t姓名\t学号\t成绩\n");
  printf("\t%s\t%d\t%f\n",s1[i].name,s1[i].num,s1[i].score);}
}
else
{printf("未找到该学生信息"}
}
=======================分割线=======================================
输入的是这样的 a 1 1
               b 2 2
               c 3 3
               d 4 4

点评

这个我就不警告你了,但这是java论坛,请贴java代码  发表于 2012-6-28 16:23
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马