黑马程序员技术交流社区

标题: 选择排序的问题 [打印本页]
作者: 董凯    时间: 2013-7-23 21:14
标题: 选择排序的问题
本帖最后由 杨兴庭 于 2013-7-24 21:03 编辑

  2. <P>class  Demo
  3. {
  4.         public static void main(String[] args)
  5.         {
  6.                 int temp[]={23,11,44,33,6,77,88,22};
  7.                 print88(temp);
  8.                 print99(temp);

  10.                
  11.         }
  12.         public static void  print88(int arr[])
  13.         {
  14.                 for (int i=0;i<arr.length-1 ;i++ )//比较的轮数
  15.                 {
  16.                         int min=i;
  17.                         for (int j=i+1;j<arr.length;j++ )//依次比较
  18.                         {
  19.                                 if (arr[min]>arr[j])
  20.                                 {
  21.                                       min=j;                           }
  22.                         }
  23.                         if(min!=i)
  24.                         {
  25.                               swap  (arr,i,min);
  26.                         }
  27.                 }
  28.         }</P>
  29. <P>public static void  swap(int arr[],int x,int y)
  30. {
  31.   int temp=arr[x];
  32.   arr[x]=arr[y];
  33.   arr[y]=temp;</P>
  34. <P> }

  36.         public static void print99(int arr[])//输出答应功能
  37.         {
  38.                 for (int z=0;z<arr.length ;z++ )
  39.                 {
  40.                         System.out.print(arr[z]+" ");
  41.                 }
  42.         }
  43. }
  44. </P>
复制代码
print88这段有点看不懂，谁能给解析一下那！
作者: ☆今☆    时间: 2013-7-23 21:34
因为选择比较是第一轮是:第一个数依次跟后面的全部数比较.
               第二轮:是从第二个数开始依次跟后面的数比较
               以此类推..........

总共比较完总共需要数组长度减1轮;所以是:for (int i=0;i<arr.length-1 ;i++ )
每一轮,都要从i跟i的后一个数开始比较(即j=i+1开始),一直到数组结束;
所以是for (int j=i+1;j<arr.length;j++ )
然后比较值,将较小值元素的数组下标存在min中;如果不是当前的i元素,就交换值.
(arr,i,min);应该是不完整的吧,是交换值的函数吧.
作者: 月亮人生    时间: 2013-7-23 21:50
  1. class  Demo2
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 int temp[]={23,11,44,33,6,77,88,22};
  6.                 print88(temp);
  7.                 print99(temp);

  9.                
  10.         }
  11.         public static void  print88(int arr[])
  12.         {
  13.                 for (int i=0;i<arr.length-1 ;i++ )//比较的轮数
  14.                 {
  15.                         int min=i;
  16.                         for (int j=i+1;j<arr.length;j++ )//依次比较
  17.                         {
  18.                                                         //这里应该改为   if(arr[i]>arr[j]){min=j;}
  19.                                                         //这个是选择排序。特点是：访问内存次数较少了。
  20.                                                         //因为：内层for循环是每轮比较的是 arr[i]  和 角标从（i+1）到arr.length-1的每个值，
  21.                                                         //比较结果中比arr[i]小的值，用min记录下来，而不用立刻去交换这两个数，这就较少了访存的次数。
  22.                                 if (arr[min]>arr[j])
  23.                                 {
  24.                                         min=j;
  25.                                 }
  26.                         }
  27.                         if(min!=i) //  如果每轮比较结束后，有较小的，min的值就会改变，这样就可以来完成两个数的交换。
  28.                         {
  29.                                 swap(arr,i,min);
  30.                         }
  31.                 }
  32.         }
  33.                 public static void  swap(int arr[],int x,int y)
  34.                 {
  35.                   int temp=arr[x];
  36.                   arr[x]=arr[y];
  37.                   arr[y]=temp;
  38.                 }


  41.         public static void print99(int arr[])//输出打印功能
  42.         {
  43.                 for (int z=0;z<arr.length ;z++ )
  44.                 {
  45.                         System.out.print(arr[z]+" ");
  46.                 }
  47.         }
  48. }
复制代码
作者: 周骑骏    时间: 2013-7-23 22:09
本帖最后由 周骑骏 于 2013-7-23 22:11 编辑

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);
                                }
                        }
                }
        }
我们学的选择排序，每次都把最大的放在最后，冒泡就是每次将大的放在前面 仔细分析吧
作者: liuzhming    时间: 2013-7-23 22:35
这是一个简单选择排序，它采用最简单的选择方式，从头到尾顺序扫描序列，找出最小的一个记录，和第一个记录交换，接着从剩下的记录中继续这种选择和交换，最终使序列有序。
        public static void  print88(int arr[])
    {
                /*
                 * 下面这个循环每循环一次，从无序记录中选出最小的一个，并做交换。
                 * 这样每次有序序列增加一个，无序序列减少一个
                 * */
            for (int i=0;i<arr.length-1 ;i++ )//比较的轮数。
            {
                    int min=i;
                    //这个循环是算法的关键，它从无序序列中挑出一个最小的元素
                    for (int j=i+1;j<arr.length;j++ )//依次比较
                            if (arr[min]>arr[j])
                                  min=j;
                    if(min!=i)
                    swap(arr,i,min);//最小元素与无序序列第一个元素进行交换  
            }
    }
作者: の放下执著    时间: 2013-7-23 23:02
首先分析一下选择排序的原理：每次遍历数组，找出最小的元素，然后拿最小的元素与指定位置的元素互换就可以了。比如第一次遍历数组，找出数组中最小的元素与数组中第一个元素互换。第二次遍历数组，找出第二小的元素与数组中第二个元素互换.......当进行n-1次后，数组就成了有序的数组了。
public static void  print88(int arr[])
        {
                for (int i=0;i<arr.length-1 ;i++ )//遍历的次数
                {
                        //注意：每次遍历后，都要在把无序数组中最小的元素交换到 i 处，
                        //比如第一次把最小的放到i=0处，第二次把第二小的放到i=1处......
                        int min=i;//min用于记录每次遍历数组时最小元素的角标
                        for (int j=i+1;j<arr.length;j++ )//依次比较
                        {
                                if (arr[min]>arr[j])//当发现更小的元素时，记下它的角标
                                {
                                      min=j;     
                                }
                        }
                        if(min!=i)//如果最小的元素不在应该在的地方，交换，就OK了
                        {
                              swap  (arr,i,min);
                        }
                }
        }</P>




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2