问题 2842. -- 直接插入排序 inssort [1*]

2842: 直接插入排序 inssort [1*]

时间限制: 1 Sec  内存限制: 128 MB
献花: 1  解决: 0
[献花][花圈]

题目描述

输入n个整数,用直接插入排序的方法进行排序(升序,由小到大排)
【插排方法:】将第1和第2个数排好序,则前2个数有序,
第3个数往前比较,插入到前2个有序数的适当位置,使前3个数有序,
第4个数往前比较,插入到前3个有序数的适当位置,使前4个数有序,
依此类推,使所有n个数都有序。
【插入的方法:】第设前5个数已经有序,将第6个数保存到x,x逐个与第5到第1个数比较,直到找到x的正确位置m。
将第5到第m个数都往后移动一位,将x保存的位置m,则前6个数有序。
【思考:】要找到x的位置,a[j]与x的比较条件是什么?找到第一个满足条件的元素,用while循环。
提示,找到位置m再移动的方法效率低,可以变找边移动。
要用一个指针i记住已经有序的位置已经到了哪里,用另一个指针j来寻找x的位置。
实际上前两个数不用单独处理,因为第一个数可以认为是有序的,从第2个数开始进行往前插入。

输入

输出

提示

来源

[献花][花圈]