直接插入排序（java实现）

直接插入排序，指每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。具体方法是第一趟比较前两个数，然后把第二个数按大小插入到有序表中；第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。它是由两层嵌套循环组成的，外层循环标识并决定待比较的数值，内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

算法描述

对一个有n个元素的数据序列，排序需要进行n-1趟插入操作：

第1趟插入，将第2个元素插入前面的有序子序列--此时前面只有一个元素，当然是有序的。

第2趟插入，将第3个元素插入前面的有序子序列，前面2个元素是有序的。

第n-1趟插入，将第n个元素插入前面的有序子序列，前面n-1个元素是有序的。

public class InsertSort {
   public static void insertSort(int[] data) {
       for (int i = 1; i < data.length; i++) {
           // 得到i处的元素值
           int tmp = data[i];
           //判断元素是否大于前面的有序列
           if (data[i]<data[i-1]) {
               //得到有序列的最后一个元素
               int j=i-1;
               //和前面有序列依次比较
               while (j>=0&&data[j]>tmp) {
                   data[j+1]=data[j];
                   j--;
               }
               //找到了合适的位置
               data[j+1]=tmp;
           }
       }

   }
   public static void main(String[] args) {
       int[] data={8,6,7,1,4,7,6,4,9,8,5};
       print(data);
       insertSort(data);
       print(data);

   }
   public static void print(int[] data) {
       for (int i = 0; i < data.length; i++) {
           System.out.print(data[i] + "\t");
       }
       System.out.println();
   }
}

结果为：

8 6 7 1 4 7 6 4 9 8 5
1 4 4 5 6 6 7 7 8 8 9

直接插入排序（java实现）

相关推荐