-
Notifications
You must be signed in to change notification settings - Fork 25
/
ch11s02.html
34 lines (31 loc) · 7.43 KB
/
ch11s02.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>2. 插入排序</title><link rel="stylesheet" href="styles.css" type="text/css" /><meta name="generator" content="DocBook XSL Stylesheets V1.73.2" /><link rel="start" href="index.html" title="Linux C编程一站式学习" /><link rel="up" href="ch11.html" title="第 11 章 排序与查找" /><link rel="prev" href="ch11s01.html" title="1. 算法的概念" /><link rel="next" href="ch11s03.html" title="3. 算法的时间复杂度分析" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">2. 插入排序</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch11s01.html">上一页</a> </td><th width="60%" align="center">第 11 章 排序与查找</th><td width="20%" align="right"> <a accesskey="n" href="ch11s03.html">下一页</a></td></tr></table><hr /></div><div class="sect1" lang="zh-cn" xml:lang="zh-cn"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id2745253"></a>2. 插入排序</h2></div></div></div><p>插入排序算法类似于玩扑克时抓牌的过程，玩家每拿到一张牌都要插入到手中已有的牌里，使之从小到大排好序。例如（该图出自<a class="xref" href="bi01.html#bibli.algorithm" title="Introduction to Algorithms">[<abbr class="abbrev">算法导论</abbr>]</a>）：</p><div class="figure"><a id="id2745274"></a><p class="title"><b>图 11.1. 扑克牌的插入排序</b></p><div class="figure-contents"><div><img src="images/sortsearch.sortcards.png" alt="扑克牌的插入排序" /></div></div></div><br class="figure-break" /><p>也许你没有意识到，但其实你的思考过程是这样的：现在抓到一张7，把它和手里的牌从右到左依次比较，7比10小，应该再往左插，7比5大，好，就插这里。为什么比较了10和5就可以确定7的位置？为什么不用再比较左边的4和2呢？因为这里有一个重要的前提：手里的牌已经是排好序的。现在我插了7之后，手里的牌仍然是排好序的，下次再抓到的牌还可以用这个方法插入。</p><p>编程对一个数组进行插入排序也是同样道理，但和插入扑克牌有一点不同，不可能在两个相邻的存储单元之间再插入一个单元，因此要将插入点之后的数据依次往后移动一个单元。排序算法如下：</p><div class="example"><a id="id2745314"></a><p class="title"><b>例 11.1. 插入排序</b></p><div class="example-contents"><pre class="programlisting">#include <stdio.h>
#define LEN 5
int a[LEN] = { 10, 5, 2, 4, 7 };
void insertion_sort(void)
{
int i, j, key;
for (j = 1; j < LEN; j++) {
printf("%d, %d, %d, %d, %d\n",
a[0], a[1], a[2], a[3], a[4]);
key = a[j];
i = j - 1;
while (i >= 0 && a[i] > key) {
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
printf("%d, %d, %d, %d, %d\n",
a[0], a[1], a[2], a[3], a[4]);
}
int main(void)
{
insertion_sort();
return 0;
}</pre></div></div><br class="example-break" /><p>为了更清楚地观察排序过程，我们在每次循环开头插了打印语句，在排序结束后也插了打印语句。程序运行结果是：</p><pre class="screen"><span class="emphasis"><em>10</em></span>, 5, 2, 4, 7
<span class="emphasis"><em>5, 10</em></span>, 2, 4, 7
<span class="emphasis"><em>2, 5, 10</em></span>, 4, 7
<span class="emphasis"><em>2, 4, 5, 10</em></span>, 7
<span class="emphasis"><em>2, 4, 5, 7, 10</em></span></pre><p>如何严格证明这个算法是正确的？换句话说，只要反复执行该算法的<code class="literal">for</code>循环体，执行<code class="literal">LEN-1</code>次，就一定能把数组<code class="literal">a</code>排好序，而不管数组<code class="literal">a</code>的原始数据是什么，如何证明这一点呢？我们可以借助Loop Invariant<a id="id2745384" class="indexterm"></a>的概念和数学归纳法来理解循环结构的算法，假如某个判断条件满足以下三条准则，它就称为Loop Invariant：</p><div class="orderedlist"><ol type="1"><li><p>第一次执行循环体之前该判断条件为真。</p></li><li><p>如果“<span class="quote">第N-1次循环之后（或者说第N次循环之前）该判断条件为真</span>”这个前提可以成立，那么就有办法证明第N次循环之后该判断条件仍为真。</p></li><li><p>如果在所有循环结束后该判断条件为真，那么就有办法证明该算法正确地解决了问题。</p></li></ol></div><p>只要我们找到这个Loop Invariant，就可以证明一个循环结构的算法是正确的。上述插入排序算法的Loop Invariant是这样的判断条件：<span class="emphasis"><em>第<code class="literal">j</code>次循环之前，子序列a[0..j-1]是排好序的</em></span>。在上面的打印结果中，我把子序列a[0..j-1]加粗表示。下面我们验证一下Loop Invariant的三条准则：</p><div class="orderedlist"><ol type="1"><li><p>第一次执行循环之前，<code class="literal">j=1</code>，子序列a[0..j-1]只有一个元素<code class="literal">a[0]</code>，只有一个元素的序列显然是排好序的。</p></li><li><p>第<code class="literal">j</code>次循环之前，如果“<span class="quote">子序列a[0..j-1]是排好序的</span>”这个前提成立，现在要把<code class="literal">key=a[j]</code>插进去，按照该算法的步骤，把<code class="literal">a[j-1]</code>、<code class="literal">a[j-2]</code>、<code class="literal">a[j-3]</code>等等比<code class="literal">key</code>大的元素都依次往后移一个，直到找到合适的位置给<code class="literal">key</code>插入，就能证明循环结束时子序列a[0..j]是排好序的。就像插扑克牌一样，“<span class="quote">手中已有的牌是排好序的</span>”这个前提很重要，如果没有这个前提，就不能证明再插一张牌之后也是排好序的。</p></li><li><p>当循环结束时，<code class="literal">j=LEN</code>，如果“<span class="quote">子序列a[0..j-1]是排好序的</span>”这个前提成立，那就是说a[0..LEN-1]是排好序的，也就是说整个数组<code class="literal">a</code>的<code class="literal">LEN</code>个元素都排好序了。</p></li></ol></div><p>可见，有了这三条，就可以用数学归纳法证明这个循环是正确的。这和<a class="xref" href="ch05s03.html#func2.recursion">第 3 节 “递归”</a>证明递归程序正确性的思想是一致的，这里的第一条就相当于递归的Base Case，第二条就相当于递归的递推关系。这再次说明了递归和循环是等价的。</p></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch11s01.html">上一页</a> </td><td width="20%" align="center"><a accesskey="u" href="ch11.html">上一级</a></td><td width="40%" align="right"> <a accesskey="n" href="ch11s03.html">下一页</a></td></tr><tr><td width="40%" align="left" valign="top">1. 算法的概念 </td><td width="20%" align="center"><a accesskey="h" href="index.html">起始页</a></td><td width="40%" align="right" valign="top"> 3. 算法的时间复杂度分析</td></tr></table></div></body></html>