黑马程序员技术交流社区

标题: 数组选择排序的优化，求分析？ [打印本页]
作者: 黑马17期-闫东东    时间: 2013-3-8 22:06
标题: 数组选择排序的优化，求分析？
class Demo2
        {
                public static void main(String[] args)
                {
                        int[] arr={1,3,5,2,6};

                        selectSort(arr);
                        printArray(arr);
                       
                }
       
        public static void selectSort(int[] arr)
        {
                for(int i=0;i<arr.length-1;i++){
                       
                        int index=i;
                       
                        for(int j=i+1;j<arr.length;j++)
                        {
                               
                                if(arr[index]>arr[j]){
                                        index=j;
                                }
                        }
                       
                        if(index!=i){
                                int tmp=arr[i];
                                arr[i]=arr[index];
                                arr[index]=tmp;
                        }
                }
        }
        public static void printArray(int[] arr)
        {
               
                System.out.print("[");

                for(int i=0;i<arr.length;i++)
                {
                       
                        if(i==arr.length-1)
                                System.out.print(arr[i]);
                        else
                        System.out.print(arr[i]+",");
                       
                }

                System.out.println("]");
        }
}

       
作者: 何旭程    时间: 2013-3-8 22:44
static void selectSort1(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;
                                }
                        }
                }
        }






以上是视频里选择排序的第一个算法，原理是假定数组第一个元素为全数组最小元素，将第一个元素与数组其它元素依次比较，当某个元素比第一个元素小时，就把这个元素和第一个元素交换位置，这样始终保持第一个元素为最小元素，比较第一趟结束后第一个位置上的元素即确定为数组中的最小元素，接下来假定数组第二个元素为除第一个元素外数组的最小元素，重复和第一个元素一样的比较，第二趟结束后第二个位置上的元素即为数组中第二小的元素，如此重复，最后一个元素无需进行上述比较即可确定位置，所以总共比较arr.length-1趟，每次确定一个最小元素。

你贴出来的是经过适当优化的算法，这个优化体现在：第一个算法假定最小元素和其它元素进行比较的时候，一旦发现有比假定最小元素更小的元素，当即交换两个元素的位置，优化后的算法设置了一个index，这个index相当于一个指针,当发现有比假定最小元素更小元素的时候，只将此元素的下标赋值给index,一趟结束后index里存的是本趟比较最小元素的下标，然后再和假定最小元素交换位置，这样避免了许多无效的数组元素交换，两个数组元素交换位置，借助第三个变量的话需要进行三次赋值操作，将最小元素下标赋值给index只需要一次赋值操作。


作者: 梁耀今    时间: 2013-3-8 22:51
本帖最后由 梁耀今 于 2013-3-8 22:56 编辑

兄弟，我看了一下，终于看懂了你写的程序了，写得很有思维，不错！你的排序主要分两个部分，一个是序列号，一个是里面数值。
  for(int i=0;i<arr.length-1;i++){
                        
                        int index=i;
                        
                        for(int j=i+1;j<arr.length;j++)
                         {
                                 
                                if(arr[index]>arr[j]){
                                         index=j;
                                }
                         ｝
这个是第一部分，先把比较大小，如果大于，然后把序列号赋给index
if(index!=i){
        int tmp=arr;
        arr=arr[index];
        arr[index]=tmp;
   }
然后这里就是进行判断看看序列号的内容是不是原来的，如果不是，就进行调换，这样如果是大量的数据的话，确实是能很优化程序的。
作者: 小丑的媳妇2    时间: 2013-3-8 23:06
本帖最后由 朱荣宁. 于 2013-3-8 23:08 编辑

你这个问题在毕老师视频里第4天的课程 数组选择排序里的内容 我在这里给你详细说一下数组的选择排序
假如我们定义了一个数组 int[] arr = {3,1,4,2,7,5}; 用选择排序法进行排序 结构图如下:
从图片上可以得到 算法思想是:

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

具体来说分为一下几步:
n个记录的文件的选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

程序如下:

*
对给定数组进行排序。
{3,1,4,2,7,5};

*/
class ArrayTest2
{
 /*
选择排序。
内循环结束一次，最值出现头角标位置上。
*/
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);
    }
   }
  }
}

 /*
发现无论什么排序。都需要对满足条件的元素进行位置置换。
所以可以把这部分相同的代码提取出来，单独封装成一个函数。
*/
public static void swap(int[] arr,int a,int b)
{
  int temp = arr[a];
  arr[a] = arr;
  arr = temp;
}
public static void main(String[] args)
{
  int[] arr = {3,1,4,2,7,5};
  //排序前；
  printArray(arr);
  //排序
  //selectSort(arr);
  //bubbleSort(arr);
  //Arrays.sort(arr);//java中已经定义好的一种排序方式。开发中，对数组排序。要使用该句代码。
  //排序后：
  printArray(arr);
   
}
 public static void printArray(int[] arr)
{
  System.out.print("[");
  for(int x=0; x<arr.length; x++)
  {
   if(x!=arr.length-1)
    System.out.print(arr[x]+", ");
   else
    System.out.println(arr[x]+"]");
  }  
}
}

E{16L$U3212T3}FSG6%$1GF.jpg (39.29 KB, 下载次数: 15)

选择排序 数组{3,1,4,2,7,5}

选择排序 数组{3,1,4,2,7,5}
作者: 移动小坦克    时间: 2013-3-9 00:07
本帖最后由 韩松范 于 2013-3-9 00:16 编辑

这个优化后的代码中的精髓是在这
index=j;
之所以说这个精髓是因为，它避免了在第2个for循环中，如果发现比自己小的数
每次都要置换数组中元素的弊端，它是记住了最小数的角标，当第2个for循环结束后，
如果index!=i，就置换一下，index角标的元素和i角标的元素，就可以了。
也就是说该程序最多置换arr.length-1次元素，这个次数要小于等于，直接置换元素，所产生的置换次数
当然该程序美中不足的是，置换元素的代码其实可以封装成一个函数，这样提高了代码的复用性。
public static void swap(int arr,int index,int i)
{
      int tmep = arr[index];
      arr[index] = arr;
      arr = temp;
      
}
调用
if(index!=i)
{
                              /*  int tmp=arr;
                                arr=arr[index];
                                arr[index]=tmp;*/
      swap(arr,index,i);
}
作者: 黑马17期-闫东东    时间: 2013-3-9 18:59
{:soso_e183:}



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