使用Java编写一个插入排序算法?很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。
<强>一,算法原理
插入排序法:所谓插入排序法乃是将一个数目插入该占据的位置。
假设我们输入的是“69年53岁,27岁,36岁,15日,,42”我们从第二个数字开始,这个数字是27日,我们的任务只要看看27有没有正确的位置,我们的做法是和这个数字左边的数字来比,因此我们比较27岁和53岁,27比53小,所以我们就交换27岁和53岁,原来的排列就变成了”27日,53岁,36岁,15日,69年,42“
接下来,我们看第三个数字有没有在正确的位置。这个数字是36岁,它的左边数字是53岁,36比53小,所以我们将36岁和53岁交换,排列变成了“27岁,36岁,53岁,15日,69年,42“我们必须继续看36有没有在正确的位置,36岁的左边是27日,27日比36小,36就维持不动了,这时候排序还是“69年27岁,36岁,53岁,15日,42“。
再来看第四个数字,这个数字是15,我们将15和它左边的数字相比,都比15大,所以就将15一路往左移动,这时候排序变成了”15日27日,36岁,53岁,69年,42”。
再来看第五个数字,这个数字是69年,我们将69和它左边的数字相比,都比69小,所以就69维持不动了,这时候排序变成了”15日27日,36岁,53岁,69年,42“
最后,我们检查第六个数字,这个数字是42岁42必须往左移,一直移到42岁的左边是36为止,所以我们的排列就变成了”15日27日,36岁,42岁,53岁,69年“排序因此完成了。
ps:读者也可以自己打开下面的链接,自己设定要排序的数组,进行排序演练
直接插入排序动画演示
所谓插入排序法,就是检查我第个数字,如果在它的左边的数字比它大,进行交换,这个动作一直继续下去,直到这个数字的左边数字比它还要小,就可以停止了。插入排序法主要的回圈有两个变数:i和j,每一次执行这个回圈,就会将我第个数字放到左边恰当的位置去。
<强>二,算法描述
1,从第一个元素开始,该元素可以认为已经被排序。
2,取出下一个元素,在已经排序的元素序列中从后向前扫描。
3,如果该元素(已排序)大于新元素,则将该元素移到下一位置。
4,重复步骤,直到找到已排序的元素小于或者大于新元素的位置。
5,将新元素插入到该位置。
6,重复步骤2 .
<强>三、效率分析
如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况如下。
最好情况:序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n - 1)次即可。
最坏情况:序列是降序排列,那么此时需要进行的比较共有n (n - 1)/2次。
直接插入排序属于稳定的排序,最坏时间复杂度为O (n ^ 2),最好时间复杂度为O (n),空间复杂度为O (1)。
插入排序的赋值操作是比较操作的次数加上(n - 1)次。
因此,插入排序不适合对于数据量比较大的排序应用。
<强>四、代码实现
公共类InsertSortTest {
公共静态孔隙InsertSort (int[]源){
int i, j。
int insertNode;//要插入的数据//从数组的第二个元素开始循环将数组中的元素插入
(i=1;我& lt;source.length;我+ +){//设置数组中的第2个元素为第一次循环要插入的数据
insertNode=[我]来源;
j=i - 1;//如果要插入的元素小于第j个元素,就将第j个元素向后移
在((j祝辞=0),,insertNode & lt;源[j]) {
来源[j + 1]=[j]来源;
j——;
}//直到要插入的元素不小于第j个元素,将insertNote插入到数组中
来源[j + 1]=insertNode;
System.out.print(第“;+我+“趟排序:“);
printArray(源);
}
}
私有静态孔隙printArray (int[]源){
for (int i=0;我& lt;source.length;我+ +){
System.out.print (“\ t"+源[我]);
}
System.out.println ();
}
公共静态void main (String [] args) {
源int []=new int[]{69年53岁,27岁,36岁,15日,42};
System.out.print(“初始关键字:“);
printArray(源);
System.out.println (“;”);
InsertSort(源);
System.out.print (“\ n \ n排序后结果:“);
printArray(源);
}
}
<强>五、运行结果
初始关键字:53 27 36 15 69 42 第1趟排序:27 53 36 15 69 42 第2趟排序:27 36 53 15 69 42 第3趟排序:15 27 36 53 69 42 第4趟排序:15 27 36 53 69 42 第5趟排序:15 27 36 42 53 69 排序后结果:15 27 36 42 53 69使用Java编写一个插入排序算法
