插入排序法是什么??
发布网友
发布时间：2022-04-23 02:06
共1个回答
热心网友
时间：2022-05-22 02:12
排序
排序(Sorting)的基本功能是依某种条件将资料项目按顺序排列,例如依照数字的大小由
小至大排列,或是按笔画顺序排列姓名 .
插入排序法 :
所谓插入排序法乃是将一个数目插入该占据的位置.假设我们输入的是
5,1,4,2,3
我们从第二个数字开始,这个数字是1,我们的任务只要看看1有没有正确的位置,我
们的做法是和这个数字左边的数字来比,因此我们比较1和5,1比5小,所以我们就交
换1和5,原来的排列就变成了
1,5,4,2,3
接下来,我们看第3个数字有没有在正确的位置.这个数字是4,它的左边数字是5,4
比5小,所以我们将4和5交换,排列变成了
1,4,5,2,3
我们必须继续看4有没有在正确的位置,4的左边是1,1比4小,4就维持不动了.
再来看第四个数字,这个数字是2,我们将2和它左边的数字相比,都比2大,所以就
将2一路往左移动,一直移到2的左边是1,这时候排序变成了
1,2,4,5,3
最后,我们检查第五个数字,这个数字是3,3必须往左移,一直移到3的左边是2为止,
所以我们的排列就变成了
1,2,3,4,5
排序因此完成了.
所谓插入排序法,就是检查第i个数字,如果在它的左边的数字比它大,进行交换,这
个动作一直继续下去,直到这个数字的左边数字比它还要小,就可以停止了.
插入排序法主要的回圈有两个变数:i和j,每一次执行这个回圈,就会将第i个数字放
到左边恰当的位置去.
时间复杂度： O(n的平方)
