锁定老帖子 主题:排序算法---插入排序
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-10-08
插入排序的算法原理比较简单,通过一点点构建有序序列来达到排序的目的。比如给出一个数组a,长度为5,那么首先会将第一个元素作为一个已经排序的序列,然后从第二个元素开始向已经排序的序列(就是第一个元素)从后向前扫描,如果比这个序列中的元素小的话,就插入到相应元素的前面,而插入后需要后移元素。然后第三个元素再从这两个元素组成的有序序列的后面扫描,找到比它小的位置后就插入,否则继续向前扫描,以此类推。
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序。
算法复杂度如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。
下面的是用JAVA实现的三种方式
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, 97, 76, 13, 27] [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, 97, 76, 13, 27] [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]
可以看到,运行结果比第一种方式要好一些,不过原理都是一样的 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
浏览 2457 次