Problem1605--直接插入排序 inssort [1*]

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

Time Limit: 1.000 Sec  Memory Limit: 128 MB
Submit: 253  Solved: 161
[Submit] [Status] [Web Board] [Creator:]

Description

输入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个数开始进行往前插入。

Sample Input

5
2 3 1 4 6

Sample Output

1
2
3
4
6

Source/Category


[Submit] [Status]