文档章节

算法学习笔记二:插入排序及循环不变式

Angelks
 Angelks
发布于 2017/01/26 15:12
字数 373
阅读 38
收藏 1

一、算法分析:

插入排序的工作方式类似于打牌时排序一手扑克牌:

下标j指出正被插入到手中的“当前牌”。

for循环(循环变量为j)每次迭代的开始,a[0]-a[j-1]的子数组构成当前左手中的牌。

剩余的子数组a[j+1]-a[LEN-1]相当于桌子上牌堆里面的牌。

二、循环不变式:

a[0]-a[j-1]就是原本0~j-1的元素,但现在已经排好序。我们把a[0]-a[j-1]的这些性质形式地表示为一个循环不变式

循环不变式主要用于证明算法的正确性。关于循环不变式我们必须证明三点:

1、初始化:在第一次迭代之前,它为真。

2、保持:如果循环的某次迭代之前它为真,那么下次迭代之前它仍为真。

3、终止:在循环终止时,不变式为我们提供一个有用的性质,该性质有助于证明算法是正确的。

 

三、C语言代码:

#include <stdio.h>
#include <stdlib.h>
#define LEN 5

void InsertSort(double a[]);

int main()
{
	double a[] = { 1.6,1.1,6.9,2.1,3 };
	InsertSort(a);
	system("pause");
}

void InsertSort(double a[])
{
	double  key;
	int i, j;
	for (j = 1; j < LEN; j++)
	{
		key = a[j];
		i = j - 1;
		while (i >= 0 && a[i] > a[j])
		{
			a[i + 1] = a[i];
			i--;
			a[i + 1] = key;
		}
	}

	for (int  k = 0; k < LEN; k++)
	{
		printf("%.2f \t", a[k]);
	}
}

 

© 著作权归作者所有

Angelks
粉丝 0
博文 10
码字总数 6719
作品 0
马鞍山
前端工程师
私信 提问
剑指offer-调整数组顺序使奇数位于偶数前面

调整数组顺序使奇数位于偶数前面 一、问题描述 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇...

MarkKobs
02/20
0
0
闲话选择排序算法

闲话选择排序算法 导语 考虑排序存储在数组A中的n个数:首先找出A中的最小元素并将其与A[1]中的元素进行交换。接着,找出A中的次最小元素并将其与A[2]中的元素进行交换。对A中前n-1个元素按该...

国士梅花
2016/04/21
47
0
排序算法(3) -- 插入排序

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/87967009 一、前言 直接插入排序(...

dby_freedom
02/27
0
0
[译] 排序算法入门 — Go 语言实现

[译] 排序算法入门 — Go 语言实现 Go语言学习园地博客2017-07-0915 阅读 go算法排序 排序算法是一种采用列表或数组并以特定顺序对其元素进行重新排序的算法。有几十种不同的排序算法,如果你...

Go语言学习园地博客
2017/07/09
0
0
排序算法总结(一)---- 直接插入排序,希尔排序(java实现)

一、概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 二、稳定性,时间复杂度...

ljheee
2017/04/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

vue预渲染

prerender-spa-plugin 安装prerender-spa-plugin (插件使用见npm官网)[https://www.npmjs.com/package/prerender-spa-plugin] npm install prerender-spa-plugin --save-dev 配置prerender-s......

莫西摩西
47分钟前
1
0
Command模式

https://www.cnblogs.com/devinzhang/archive/2012/01/06/2315235.html

南桥北木
今天
1
0
由于PostgreSQL9.x二进制输出格式默认值改变导致的读取图片错误

今天从社区邮件看到一个这样的问题,感觉很有意思,在这分享给大家~具体如下: 问题现象: 作者有一个很老的Java应用,当时后端采用的PostgreSQL数据库版本为8.x,该系统除了正常的数据增删...

闻术苑
今天
2
0
导入sql时出现Invalid default value for 'create_time'报错处理方法

当运行SQL会出现:[Err] 1067 - Invalid default value for 'create_time',是因为Mysql版本不同,如果版本不 < 5.6请去的话报错的处理方法如下: 方法 :alter table table_name modify cre......

writeademo
今天
1
0
对ssm(spring,springmvc,mybatis)的了解总结

ssm框架现在是java web开发的三个主流框架 ,其实严格来算只算是两个框架,因为springmvc属于spring框架 ,是spring的一个mvc子框架 那么我们下面就来了解一下三大框架把 一 .Spring spring...

咸鱼-李y
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部