• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

Insertion Sort

AOJ 站点默认 6个月前 (03-28) 191次浏览 已收录 0个评论
文章目录[隐藏]

Write a program of the Insertion Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:

Note that, indices for array elements are based on 0-origin.

To illustrate the algorithms, your program should trace intermediate result for each step.

Input
The first line of the input includes an integer N, the number of elements in the sequence.

In the second line, N elements of the sequence are given separated by a single space.

Output
The output consists of N lines. Please output the intermediate sequence in a line for each step. Elements of the sequence should be separated by single space.

Constraints
1 ≤ N ≤ 100

Sample Input 1
6
5 2 4 6 1 3
Sample Output 1
5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6
Sample Input 2
3
1 2 3
Sample Output 2
1 2 3
1 2 3
1 2 3
Hint
Template in C

Meaning

实现插入排序的过程

Solution

插入排序第二层循环中是从当前处(也是未排序的这个数)向前寻找比其大的数,如果有向后移动一位。临界条件两个,1,不能再向前了(判断此刻指针下标大于0)2,有比其更小的数(判断指针是否比当前处的数小)。最后将当前数插入到指针的位置

Coding


个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:Insertion Sort
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到