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

相关文章

来自专栏racaljk

Leetcode 8. String to Integer (atoi) atoi函数实现 (字符串)

这道题的corner cases非常多,请务必确保下面cases都能通过的情况下再提交。

1743
来自专栏阿凯的Excel

Vlookup最高阶应用的全网唯一解决方案

古有烟笼寒水月笼沙的缥缈朦胧,今有查询函数的假模糊匹配的终极应用!今天分享的内容是全网唯一哦~ 为啥是假模糊匹配呢?一会和你说! 嗯嗯,Vlookup函数应该...

2755
来自专栏Petrichor的专栏

tensorflow: Shapes and Shaping 探究

821
来自专栏逆向技术

逆向知识十一讲,识别函数的调用约定,函数参数,函数返回值.

      逆向知识十一讲,识别函数的调用约定,函数参数,函数返回值. 在反汇编中,我们常常的会看到各种的函数调用,或者通过逆向的手段,单独的使用这个函数,那么...

2419
来自专栏小詹同学

Leetcode打卡 | No.22 括号生成

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

1671
来自专栏伪君子的梦呓

题解 ~ 输出三个数中的最大值 ~ C++ 做法

1865
来自专栏小樱的经验随笔

1305 Pairwise Sum and Divide

1305 Pairwise Sum and Divide 题目来源: HackerRank 基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度...

3509
来自专栏Golang语言社区

map按key和按value排序

看一个题: 查找和排序 题目:输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。 例示: jack 70...

3083
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》 附录A NumPy高级应用A.1 ndarray对象的内部机理A.2 高级数组操作A.3 广播A.4 ufunc高级应用A.5 结构化和记录式数组A.6 更多

在这篇附录中,我会深入NumPy库的数组计算。这会包括ndarray更内部的细节,和更高级的数组操作和算法。 这章包括了一些杂乱的章节,不需要仔细研究。 A.1...

6346
来自专栏前端儿

小学生算术

很多小学生在学习加法时,发现“进位”特别容易出错。你的任务是计算两个三位数在相加时需要多少次进位。你编制的程序应当可以连续处理多组数据,直到读到两个0(这是输入...

943

扫码关注云+社区