排序算法-插入排序

2012-10-11

排序算法---插入排序插入排序的算法原理比较简单，通过一点点构建有序序列来达到排序的目的。比如给出一个数

排序算法---插入排序

插入排序的算法原理比较简单，通过一点点构建有序序列来达到排序的目的。比如给出一个数组a，长度为5，那么首先会将第一个元素作为一个已经排序的序列，然后从第二个元素开始向已经排序的序列（就是第一个元素）从后向前扫描，如果比这个序列中的元素小的话，就插入到相应元素的前面，而插入后需要后移元素。然后第三个元素再从这两个元素组成的有序序列的后面扫描，找到比它小的位置后就插入，否则继续向前扫描，以此类推。

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置中
重复步骤2

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

package sort;import java.util.Arrays;public class InsertSort {public static void main(String args[]){int array[]={49,38,65,97,76,13,27};insertSort(array,0,array.length-1);System.out.println("----------最终结果----------");System.out.println(Arrays.toString(array));}public static void insertSort(int array[],int first,int last){int i,j;int temp;for(i=first+1;i<=last;i++){temp = array[i];j=i-1;//与已排序的数逐一比较，大于temp时，该数后移while((j>=first)&&(array[j]>temp)){array[j+1]=array[j];j--;}//被排序数放在正确的位置array[j+1]=temp;System.out.println(Arrays.toString(array));}}}

?运行结果：

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 76, 97, 13, 27]

[13, 38, 49, 65, 76, 97, 27]

[13, 27, 38, 49, 65, 76, 97]

----------最终结果----------

[13, 27, 38, 49, 65, 76, 97]

结果分析：

int array[]={49,38,65,97,76,13,27};

1、在方法insertSort()中需要传递三个参数，第一个参数是要排序的数组，第二个参数是数组的第一个元素下表，

即0，第三个元素是数组的最后一个下表，即array.length-1

2、方法体中

第一次：首先将array[i]赋值给temp，其实也就是第2个元素array[1]=38.

此时array[0]=49（看做一个有序序列），然后while中判断如果array[0]>temp，即49>38.

则将array[0]赋给array[1]，即array[1]=49,此时j--后j的值变成了-1，然后再array[j+1]=temp，即

array[0]=38，这样其实就是将要排序的数放到了正确的位置。

第二次：i=2,temp=array[2]，即65是待排序的数组，其中38、49为有序序列。j=1，while循环里，

array[1]=49,temp=65，array[1]<temp，所以不执行while循环，直接将temp的值65放在array[2]的

位置。

依次类推，如果发现向前扫描的时候，元素比要插入的元素大，就继续向前找，直到找到一个

第一个比它小的数，然后插入。

程序2：

package sort;import java.util.Arrays;public class InsertSort2 {public static void main(String args[]){Comparable c[]={49,38,65,97,76,13,27};insertSort(c);System.out.println(Arrays.toString(c));}public static void insertSort(Comparable data[]){for(int i=1;i<data.length;i++){Comparable key = data[i];int position = i;while(position>0&&data[position-1].compareTo(key)>0){data[position]=data[position-1];position--;}data[position]=key;}}}

?运行结果：

[13, 27, 38, 49, 65, 76, 97]

分析：这里用到了Comparable类，主要是在比较数值的时候用到了compareTo方法进行两个元素的比较

第三种实现方式：

package sort;import java.util.Arrays;public class InsertSort3 {public static void main(String args[]){int array[]={49,38,65,97,76,13,27};insertSort(array,array.length-1);System.out.println("------------排序后的结果------------");System.out.println(Arrays.toString(array));}public static void insertSort(int array[],int size){int i,j,temp;for(i=1;i<size;i++){//取出一个数字用来排序，第一个元素array[0]看成一个已经排序的序列temp=array[i];//在排序序列中查找位置for(j=i-1;j>=0&&temp<(array[j]);--j){array[j+1]=array[j];//向后移动数据}array[j+1]=temp;//插入数据到序列System.out.println(Arrays.toString(array));}}}

?运行结果：

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 76, 97, 13, 27]

[13, 38, 49, 65, 76, 97, 27]

------------排序后的结果------------

[13, 38, 49, 65, 76, 97, 27]

可以看到，运行结果比第一种方式要好一些，不过原理都是一样的

热点排行

编程

排序算法-插入排序