小文’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 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

Python字符串index()方法应用案例一则

553
来自专栏CSDN技术头条

常用 XML 解析技术

现在的软件项目都不是独立的一个项目,都是多系统协调工作。这样的话就涉及到系统间的通讯,通讯就会跟报文传输挂上关系。系统间使用怎样的报文格式进行通讯呢?有的使用固...

703
来自专栏Danny的专栏

正则表达式

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

1062
来自专栏阮一峰的网络日志

Javascript 面向对象编程(一):封装

学习Javascript,最难的地方是什么? 我觉得,Object(对象)最难。因为Javascript的Object模型很独特,和其他语言都不一样,初学者不容...

3397
来自专栏Golang语言社区

【JS游戏编程基础】关于js里的this关键字的理解

this关键字在c++,java中都提供了这个关键字,在刚开始学习时觉得有难度,但是只要理解了,用起来就方便多了,下面通过本篇文章给大家详解js里this关键字...

41810
来自专栏听雨堂

未解决:长字符串含…

用reduce拼了一个超长sql语句,大约65000字符,运行通不过,报错: OperationalError: (1054, "Unknown column ...

1959
来自专栏Java编程

Java正则表达式详解

Java 提供了功能强大的正则表达式API,在java.util.regex 包下。本教程介绍如何使用正则表达式API。

6960
来自专栏个人随笔

析构函数(C#)

 析构函数又称终结器,用于析构类的实例。 定义   析构函数(destructor) 与构造函数相反,当对象结束其生命周期时(例如对象所在的函数已调用完毕),系...

3097
来自专栏Kotlin源码阅读

kotlin源码阅读——基础数据类型

基本和所有编程语言一样,基本数据类型有Byte/Short/Int/Long/Float/Double,且和Java一样都是有符号性的。

2413
来自专栏大数据钻研

总结一些前端的知识点 (一)

一、W3C 标准盒模型和 IE 盒模型区别: 1. W3C 标准盒模型: ? 盒子的高宽是由盒子的内容区仅由 width, height 决定的,不包含边框,内...

3247

扫码关注云+社区