    在上一篇中，主要讨论了交换排序的两种排序算法：冒泡排序和快速排序，今天分析另外一种类型，就是插入排序。插入排序有两种排序算法：直接插入和希尔排序。

   直接插入排序的思想是：从第二个元素开始，不断向前查找第一个比它小的数据，在它之后将元素后移一位，然后将待插入的数据插到对应的位置上。

   上代码看得清楚些：
   public class DirectSort{
    public static void main(String args[]){
       int a[]={4,3,1,2,8,7,6};
       int temp ,i,j;
       //从第二个元素开始,不断向前插入到合适的位置上
       for(i=1;i             System.out.println("\n");
            temp=a[i];
           //找到第一个满足的位置（在它前面已经有序了）
            for(j=i-1;j>=0;j--){
                if(temp                   a[j+1]=a[j];
               }
               else{
                   break;
               }
           }
            //插入到相应的位置上
           a[j+1]=temp;
       }
        System.out.println("\n");
       for(i=0;i            System.out.print(a[i]+"-->");
       }
   }
}

     直接插入排序，也有它存在的问题：
     如果一个数据很小，那它需要移动的位置也很多，与冒泡排序一样。

     对于这个问题，有没有与快速排序一样的思想呢，基本上在最后位置附近呢，这就引入了希尔排序。

    希尔排序的思想：以一个间隔来分组，组内采用直插（移动的元素要少得多了），不断缩小这个间隔。

    看代码吧：
    public class Sort{
    public static void main(String args[]){
       int a[]={4,3,1,2,8,7,6};
       int temp ,i,j,gap;
       //间隔
       gap=a.length/2;
       while(gap>=1){
          for(i=gap;i             temp=a[i];
            for(j=i-gap;j>=0;j=j-gap){
                if(temp                   a[j+gap]=a[j];
               }
               else{
                   break;
               }
           }
           a[j+gap]=temp;
          }
          //不断缩小间隔
          gap=gap/2;
       }
        System.out.println("\n");
       for(i=0;i            System.out.print(a[i]+"-->");
       }
   }
}

   以上分析了两种插入排序的思想。

ITPub博客

排序之插入排序分析

最新文章