插入排序与循环不变式

布满荆棘的人生 2022-08-12 01:00 110阅读 0赞

首先，给出本文要使用的例子，对一个数组a进行升序的插入排序

**算法的C语言描述**

**\[cpp\]**  [view plain][] [copy][view plain]

1.  **void** inserSort(**int** a\[\], **int** length)  
2.  \{  
3.          **int** i = 1;  
4.          **for**(i = 1; i < length; i++)  
5.          \{     
6.                  **int** key = a\[i\];  
7.                  **int** j = i-1;  
8.                  **for** (j = i-1; j>=0 && a\[j\]>key; j--)  
9.                  \{     
10.                         a\[j+1\] = a\[j\];  
11.                 \}      
12.                 a\[j+1\] = key;  
13.       
14.         \}     
15. \}<strong>  
16. </strong>

# 什么是循环不变式 #

循环不变式是用于检验算法的正确性的。

在算法中，有一些特定的性质（也是我们我们实现这个算法最关注的性质），它在循环迭代中是稳定不变的。

如插入排序算法中，有循环不变式：当我们要第i个元素前，a\[0,...,i-1\]是有序的。

循环不变式有三个性质：

**初始化**： 第一次迭代前，循环不变式为真。如前面的代码中，i=1时，循环不变式为真（因为i前面a\[0\]一个元素，可以视为有序）

**保持**：     第n次迭代之前，为真，那么在第n+1次迭代之前也一定为真。在插入a\[i\]时，a\[i\]只是找寻特定的位置插入，没有破坏原来的不变式，

且a\[i\]插入后, 在下一次迭代之前（此时i已经自加），a\[0,...,i-1\]仍然有序。   类似数学归纳。

**终止**： 循环终止时，我们会得到一个有用的性质，该性质有助于验证算法正确性。（循环不变式的终止时循环不变式里最重要的一节），实际上，我们在循环终止时，也没有破坏循环不变式的稳定性。

[view plain]: http://blog.csdn.net/windeal3203/article/details/38920177#

发表评论取消回复

表情：

评论列表（有 0 条评论，110人围观）

还没有评论，来说两句吧...

相关阅读

相关 java 里的循环不变式百度百科_算法中的循环不变式

算法导论中提出的循环不变式，计算机领域解决实际问题的强大方法，值得牢记。数学基础循环不变式的数学基础是是数学归纳法数学归纳法范式给定命题P(n) 证明当n=1

﹏ヽ暗。殇╰゛Y/ 2022年11月06日 12:59/ 0 赞/ 135 阅读

相关 [珠玑之椟]浅谈代码正确性：循环不变式、断言、debug

这个主题和代码的实际写作有关，而且内容和用法相互交织，以下只是对于其内容的一个划分。《编程珠玑》上只用了两个章节20页左右的篇幅介绍，如果希望能获得更多的实例和技巧，我比较推崇

冷不防/ 2022年08月20日 15:07/ 0 赞/ 122 阅读

相关插入排序与循环不变式

首先，给出本文要使用的例子，对一个数组a进行升序的插入排序算法的C语言描述 \[cpp\] [view plain][] [copy][view plain] 1.

布满荆棘的人生/ 2022年08月12日 01:00/ 0 赞/ 111 阅读

相关链式直接插入排序

2016年7月27日18:13:11 假设用户数据为:[22,6,17,8] 数据的存贮:pHead->[22]->[6]->[17]-

拼搏现实的明天。/ 2022年07月16日 13:40/ 0 赞/ 140 阅读

相关双向循环链表的插入排序

前两篇博文，我讨论了链表的冒泡排序和选择排序（以Linux内核链表为例），这篇文章，我想说说插入排序。一、复习数组的插入排序插入排序在算法思想中属于“减治法”。

Dear 丶/ 2022年06月04日 01:41/ 0 赞/ 215 阅读

相关利用循环不变式写出正确的二分查找及其衍生算法

利用循环不变式写出正确的二分查找及其衍生算法一.你能准确写出二分查找吗？先看看定义 > 二分查找的搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则

约定不等于承诺〃/ 2022年05月31日 04:17/ 0 赞/ 170 阅读

相关 java插入排序及循环不变式

循环不变式的三个性质：初始化：循环的第一次迭代之前，它为真。保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。终止：在循环终止时，不变式为我们提供

旧城等待，/ 2022年05月15日 01:18/ 0 赞/ 133 阅读

相关冒泡排序与插入排序

![70][] 冒泡排序: void BubbleSort(int a[],int n){ flag=0; for(p=n-1;p>0;p--)

偏执的太偏执、/ 2022年05月12日 08:38/ 0 赞/ 213 阅读

相关扑克牌式插入排序及升级版希尔排序

插入排序问题提出：为什么叫做扑克牌式插入排序这里我就得给大家解释一下，为什么我要叫做扑克牌式插入排序，很简单，小编本人喜欢打扑克牌。。。相信扑克牌大

た入场券/ 2022年02月15日 02:23/ 0 赞/ 159 阅读

相关【数据结构】排序：插入排序（直接插入排序、希尔排序、折半插入排序、2-路插入排序等）详解与实现（C++）

\笔记整理内部排序分类目录： -[\->插入排序][-] \- [交换排序][Link 1] \- [选择排序][Link 2] \- [归并排序][Lin

刺骨的言语ヽ痛彻心扉/ 2021年12月09日 23:51/ 0 赞/ 285 阅读