黑马程序员技术交流社区

标题: 插入排序，分享和请求指教。 [打印本页]
作者: 张玉建    时间: 2013-8-9 13:58
标题: 插入排序，分享和请求指教。
插入排序
   插入排序它的实现原理 通俗讲就是把数组元素看做一个有序表和一个无序表，
   开始有序表只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，
   把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
   也就是说
   （为了方便理解我就想是建立一个临时容器进行存储，但是数组类型，数组是一个不变长度的类型，这是不成立只是为了理解）

public static int[] insert(int[] arr)//封装成一个方法以便函数调用，
{
  //定义一个数组，用于对排序好的元素进行存储，返回数组类型。
  int[] newarr;
  //遍历原数组，从角标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--;  //位置向前移动。
   }
  }
  newarr=arr;  //把排序好的数组传入一个定义好的数组中，
        return newarr; //返回一个数组以便对象调用。
}
这个插入还可以如何优化！解释！
还可以做到折半插入，求解释
作者: xkfxm    时间: 2013-8-9 15:19
  1. class InsertTest
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.               int[] arr = {8,2,5,3,6,2,9,23,1};
  6.              int[] newarr = insert(arr);
  7.              for(int a : newarr)
  8.              {
  9.                      System.out.println(a);
  10.              }
  11.         }
  12.         
  13.         public static int[] insert(int[] arr)//封装成一个方法以便函数调用，
  14.         {
  15.                   for (int x=1;x<arr.length ;x++ )
  16.                   {
  17.                             //这里这么定义只是为了好理解
  18.                             int value = arr[x];// 待插入的值
  19.                             int index = x;// 待插入的位置
  20.                            
  21.                             //循环判断条件比较大小，当index>0时，比较条件满足直接交换值，插入了值与此同时待插入的角标位重新赋值，角标位向前移动。
  22.                             while (index>0 && value<arr[index-1])
  23.                             {
  24.                                             //定义第三方变量，插入值
  25.                                              int temp=arr[index];   
  26.                                              arr[index]=arr[index-1];  //待插入的位置重新赋更大的值
  27.                                              arr[index-1]=temp;   
  28.                                              index--;  //位置向前移动。
  29.                             }
  30.                           }
  31.                 return arr; //返回一个数组以便对象调用。
  32.         }
  33. }
复制代码
楼主的代码中定义了一个新的数组newarr，但是没有真正的起作用，而且还让代码变得复杂了；
简化代码，可以去掉newarr的定义以及所有用到它的地方。因为你将数组中从角标1开始的数和前面所有的相比，这样每次比完，前面的都是排好序的。
得到的数组就是已经排好序的了，不需要再赋给新的数组返回。
要想折半插入，就要用到那个新数组，但是要保证插入的数组是有序的。然后找到一个数在该数组中应该插入的位置，就好了。
折半查找位置代码如下：
  1.         //折半查找，提高效率，但必须保证数组有序
  2.         public static int halfSearch(int[] arr,int key)
  3.         {
  4.                 int min,max,mid;
  5.                 min=0;
  6.                 max=arr.length-1;
  7.                 mid = (min+max)/2;
  8.                 while(arr[mid]!=key)
  9.                 {
  10.                         if(key>arr[mid])
  11.                                 min=mid+1;
  12.                         else
  13.                                 max=mid-1;
  14.                         if(min>max)
  15.                                 return -1;
  16.                         mid=(min+max)/2;
  17.                 }
  18.                 return mid;
  19.         }
复制代码
作者: 会飞的狼    时间: 2013-8-9 16:10
public static void charuSort(int[] arr)
{
        for(int y=1;y<arr.length;y++)
            {
                  for(int x=0;x<y;x++)
                      {
                             if(arr[y]<=arr[x])
                                {
                                      int temp =arr[y];
                                      for(int i=y;i>x;i--)
                                          {
                                                arr[i]=arr[i-1];
                                          }
                                      arr[x]=temp;
                                      break;  
                     }
                     }      
          }
}

我给你提供一个比较简洁的插入算法
作者: 黄兴旺    时间: 2013-8-9 17:44
领教........



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