小文’s blog–插入排序–《蓝桥杯代码笔记5》

小文好久都没更新,今天周末更新一个题


插入排序

算法提高 插入排序

时间限制:1.0s   内存限制:256.0MB

问题描述

排序,顾名思义,是将若干个元素按其大小关系排出一个顺序。形式化描述如下:有n个元素a[1],a[2],…,a[n],从小到大排序就是将它们排成一个新顺序a[i[1]]<a[i[2]]<…<a[i[n]] i[k]为这个新顺序。 插入排序,顾名思义,是通过插入操作完成排序。其直觉和方法来源于打牌时安排牌的方法。每次摸起一张牌,你都会将其插入到现在手牌中它按顺序应在的那个位置。插入排序每一步都类似这个摸牌过程。比如现在有整数数组:{3, 1, 5, 4, 2} 第一步:插入3 得到新序列{3} 第二步:插入1 得到新序列{1 3} 第三步:插入5 得到新序列{1 3 5} 第四步:插入4 得到新序列{1 3 4 5} 第五步:插入2 得到新序列{1 2 3 4 5} 为了看程序中如何完成插入过程,我们以第五步为例: 初始时:1 3 4 5 2 将2存入临时变量tmp 将下标j指向2之前的元素5,然后根据tmp和a[j]的大小关系决定该元素是否应该后移。如果a[j]>tmp,则将a[j]后移到a[j+1],序列变成1 3 4 5 5。 将下标j前移 判断a[j]>tmp,后移a[j]到a[j+1],得到1 3 4 4 5 将下标j前移 判断a[j]>tmp,后移a[j]到a[j+1],得到1 3 3 4 5 因为a[j]<=tmp,所以将tmp放回a[j+1],得到 1 2 3 4 5 现在,输入n个整数,根据以上算法,输出插入排序的全过程。


输入格式

第一行一个正整数n,表示元素个数 第二行为n个整数,以空格隔开


输出格式

有n个元素,因此输出部分分为n个部分,每个部分开头行为:Insert element[i],i为第几个元素。然后对于每一个部分,输出该部分该元素在插入排序过程中的每一步产生的新序列,初始时的序列以Init:打头,然 后每一步后移数组元素后的元素序列以Move back:打头,最后得到的最终结果序列以Final:打头。序列元素间以一个空格隔开。示例请看样例输出。每一个部分的Insert element[i]之后的每一步的输出行之前要缩进两格,即输出两个空格。


样例输入

5 3 1 5 4 2

样例输出

Insert element[1]: Init:3 Final:3 Insert element[2]: Init:3 1 Move back:3 3 Final:1 3 Insert element[3]: Init:1 3 5 Final:1 3 5 Insert element[4]: Init:1 3 5 4 Move back:1 3 5 5 Final:1 3 4 5 Insert element[5]: Init:1 3 4 5 2 Move back:1 3 4 5 5 Move back:1 3 4 4 5 Move back:1 3 3 4 5 Final:1 2 3 4 5


数据规模和约定

n<=100 整数元素在int范围内

题目比较长,我们直接看输入和输出就差不多可以理解意思了。

题目详解

大概意思就是说到了一个排序的问题,插入排序,顾名思义。

只不过要你把排序的过程输出而已。我们可以新建一个长度为100的数组,然后按照插入-输出-排序-输出-插入...的顺序一直循环到排序完成。

代码示例

#include <stdio.h> void insertsort(int a[],int len) { int i=0,j,k,key; while(i<len) { printf("Insert element[%d]:\n",i+1); printf("Init:"); for(j=0;j<=i;j++) printf("%d ",a[j]); printf("\n"); key=a[i]; k=i; while(k>0 && key<a[k-1]) { printf("Move back:"); a[k]=a[k-1]; k--; for(j=0;j<=i;j++) printf("%d ",a[j]); printf("\n"); } a[k]=key; printf("Final:"); for(j=0;j<=i;j++) printf("%d ",a[j]); printf("\n"); i++; } } int main() { int a[101],n,i; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",a+i); insertsort(a,n); return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142

#include <stdio.h>void insertsort(int a[],int len){ int i=0,j,k,key; while(i<len) { printf("Insert element[%d]:\n",i+1); printf("Init:"); for(j=0;j<=i;j++) printf("%d ",a[j]); printf("\n"); key=a[i]; k=i; while(k>0 && key<a[k-1]) { printf("Move back:"); a[k]=a[k-1]; k--; for(j=0;j<=i;j++) printf("%d ",a[j]); printf("\n"); } a[k]=key; printf("Final:"); for(j=0;j<=i;j++) printf("%d ",a[j]); printf("\n"); i++; } }int main(){ int a[101],n,i; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",a+i); insertsort(a,n); return 0;}


运行截图


知识点回顾

这题最难的地方就在move back:

就是移动的过程

moveback部分  特写

while(k>0 && key<a[k-1]) { printf("Move back:"); a[k]=a[k-1]; k--; for(j=0;j<=i;j++) printf("%d ",a[j]); printf("\n"); } a[k]=key;

12345678910

while(k>0 && key<a[k-1]) { printf("Move back:"); a[k]=a[k-1]; k--; for(j=0;j<=i;j++) printf("%d ",a[j]); printf("\n"); } a[k]=key;

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

5426
来自专栏张善友的专栏

Mix 10 上的asp.net mvc 2的相关Session

Beyond File | New Company: From Cheesy Sample to Social Platform Scott Hansel...

2547
来自专栏落花落雨不落叶

canvas画简单电路图

61011
来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

6768
来自专栏hbbliyong

WPF Trigger for IsSelected in a DataTemplate for ListBox items

<DataTemplate DataType="{x:Type vm:HeaderSlugViewModel}"> <vw:HeaderSlug...

4064
来自专栏张善友的专栏

Miguel de Icaza 细说 Mix 07大会上的Silverlight和DLR

Mono之父Miguel de Icaza 详细报道微软Mix 07大会上的Silverlight和DLR ,上面还谈到了Mono and Silverligh...

2707
来自专栏大内老A

The .NET of Tomorrow

Ed Charbeneau(http://developer.telerik.com/featured/the-net-of-tomorrow/) Exciti...

31510
来自专栏一个会写诗的程序员的博客

Spring Reactor 项目核心库Reactor Core

Non-Blocking Reactive Streams Foundation for the JVM both implementing a Reactiv...

2142
来自专栏陈仁松博客

ASP.NET Core 'Microsoft.Win32.Registry' 错误修复

今天在发布Asp.net Core应用到Azure的时候出现错误InvalidOperationException: Cannot find compilati...

4848
来自专栏码匠的流水账

聊聊NettyConnector的start及shutdown

reactor-netty-0.7.6.RELEASE-sources.jar!/reactor/ipc/netty/NettyConnector.java

851

扫码关注云+社区