上往建站提供服务器空间服务商，百度快照排名，网站托管，百度推广运营,致力于设计外包服务与源代码定制开发，360推广，搜狗推广,增加网站的能见度及访问量提升网络营销的效果,主营：网站公司,百度推广公司电话,官网搭建服务,网站服务企业排名,服务器空间,英文域名等业务，专业团队服务，效果好。

秦皇岛微信公众号开发【秦皇岛网络推广】秦皇岛建站、秦皇岛网站维护、秦皇岛网页制作、秦皇岛微信小程序代运营公司

秦皇岛，简称“秦”，别称港城、临榆，是河北省地级市，国务院批复确定的中国环渤海地区重要的港口城市，著名的滨海旅游、休闲、度假胜地 [1]  。截至2019年，全市下辖4个区、3个县，总面积7813平方千米，常住人口314.63万人，城镇人口191.04万人，城镇化率60.72%。 [2] 

秦皇岛地处中国华北地区、河北东北部、南临渤海，是中国首批沿海开放城市、首都经济圈的重要功能区、京津冀辐射东北的重要门户和节点城市 [3]  ，华北、东北和西北地区重要的出海口、全国性综合交通枢纽、京津冀协同发展与振兴东北老工业基地两大国家战略的交汇点，是中国最早的自主通商口岸、中国最大铝制品生产加工基地、北方最大粮油加工基地，被誉为“车轮制造之都”。 [4-5] 

秦皇岛因秦始皇东巡至此派人入海求仙而得名，是中国唯一一个因皇帝帝号而得名的城市，因《浪淘沙·北戴河》而闻名遐迩，汇集了丰富的旅游资源，是驰名中外的旅游休闲胜地，山海关区是国家历史文化名城 [6]  。秦皇岛作为国家创新型城市试点，拥有13所高等院校，八十余名享受国务院特殊津贴专家，15万名在校大学生，人才密度居全省首位 [7]  。

秦皇岛曾获中国最美海滨城市、全国十佳生态文明城市、中国北方最宜居城市、中国最佳休闲城市、中国最具爱心城市、中国最具幸福感城市等荣誉。秦皇岛曾协办北京亚运会和北京奥运会，是中国唯一协办过奥运会和亚运会的地级市。2017年获全国文明城市称号。2018年获得国家森林城市称号。

在图2-10中看到，在测试之前有一点被标记为循环不变式命题S(k)，我们很快就会发现这是个什么样的命题。第一次到达该测试时，j的值为i+1，而small的值为i。第二次到达该测试时，j的值是i+2，因为j已经递增了一次。因为循环体（第4行和第5两行）会在A[i+1]比A[i ]小的条件下将small置为i+1，所以我们看到small总是A[i ]和A[i+1]中较小的那个的下标。5

5为防止出现持平的情况，small应该是i。不过一般情况下我们会假设不会出现持平的情况，并将“最小元素第一次出现”说成“最小的元素”。

类似地，当第三次到达测试时，j的值是i+3，而small则是A[i..i+2]中最小那个的下标。因此我们将试着证明看似一般规则的如下命题。

命题S(k)。在k 为循环下标j的值的情况下，如果到达第(3)行的for声明中对j<n的测试，那么small的值就是A[i..k-1]中最小元素的下标。

请注意，我们在这里使用字母k 来表示变量j在循环进行时可能具有的值。这不像用j来表示j的值那样烦琐，因为有时候需要保持k不变，而同时j的值又在变化。还要注意，S(k)的表述中有“如果到达……”，这是因为某些k 的值比循环下标j的值更小而使循环中断，所以可能根本没法到达循环测试。如果k 是这些值之一，那么S(k)一定为真，因为任何“若A则B”形式的命题在A为假时都为真。

依据。依据情况是k=i+1，其中i为第(3)行中变量i的值。6在循环开始时，有j=i+1。也就是说，我们刚执行完第(2)行，把i赋值给small，并且将j初始化为i+1，以开始该循环。S(i+1)表示，small是A[i..i]中最小元素的下标，也就是说small的值一定是i。从技术上讲，我们还必须证明，除了第一次到达测试时之外，j的值从不可能是i+1。从直观上说，其原因就是每次进行循环时，j都会递增，所以它再也不会有i+1这么小了。（为了精益求精，我们应该在除了第一次通过测试外都有j>i+1的假设下进行归纳证明。）因此，归纳依据S(i+1)被证明为真。

6就行(3)到行(5)的循环而言，i是不会改变的。因此i+1是可用作根据值的合适常数。

归纳。现在假定我们的归纳假设S(k)对某些k≥i+1成立，并证明S(k+1)为真。首先，如果k≥n，那么在j的值为k，或更早之前，循环就中断了，所以肯定不会在j的值等于k+1时到达该循环测试。在这种情况下，S(k+1)一定为真。

因此，我们假设k<n，如此一来，实际上已经进行了j等于k+1时的测试。S(k)说的是small表示A[i..k-1]中最小元素的下标，而S(k+1)则是说small表示A[i..k]中最小元素的下标。如果考虑当j的值为k 时循环体（第4行和第5行）中会发生的事情，就会出现如下两种情况，具体取决于第(4)行的测试是否为真。

1. 如果A[k]不小于A[i..k-1]中的最小值，那么small的值不会改变。不过，在这种情况下，small还要表示A[i..k]中最小元素的下标，因为A[k]不是最小的。因此，在这种情况下S(k+1)表述的结论为真。

2. 如果A[k]小于A[i ]到A[k-1]这些值的最小值，那么就要将small置为k。S(k+1)表述的结论还是成立，因为k 是A[i..k]中最小元素的下标。

因此，不管哪种情况，small都是A[i..k]中最小元素的下标。我们通过递增变量j来进行for循环。因此，在循环测试之前，当j的值为k+1时，S(k+1)表述的结论成立。现在就证明了由S(k)可以得到S(k+1)。我们已经完成了归纳，并得到S(k)对所有k≥i+1的值都为真这样的结论。

接下来，应用S(k)来声明第(3)行到第(5)行的内层循环。当j的值达到n 时，程序会退出循环。因为S(n)表示small是A[i..n-1]中最小元素的下标，所以可以得出一个有关内层循环工作方式的重要结论。我们会在下一个示例中看看如何利用这个结论。

示例 2.13

现在，考虑整个SelectionSort函数，我们在图2-11中重现了其核心部分。表示这段代码的流程图如图2-12所示，其中“循环体”是指图2-11中的第(2)到(8)这几行。归纳断言T(m)还是关于在循环终止的测试开始前什么一定为真的命题。通俗地说，就是当i的值为m 时，我们选中较小的m 个元素，并将它们排序在数组开头的位置。更具体地讲就是，我们要通过对m 的归纳证明以下命题T(m)为真。

(1)        for (i = 0; i < n-1; i++) {(2)            small = i;(3)            for (j = i+1; j < n; j++)(4)                if (A[j] < A[small])(5)                    small = j;(6)            temp = A[small];(7)            A[small] = A[i];(8)            A[i] = temp;
           }复制代码

图 2-11　SelectionSort函数的主体

图 2-12　整个选择排序函数的流程图

命题T(m)。如果到达第(1)行中i<n-1的循环测试时变量i的值等于m，那么有：

(a) A[0..m-1]是有序排列的，也就是说，A[0]≤A[1]≤…≤A[m-1]。

(b) A[m..n-1]的所有元素不小于A[0..m-1]中任一元素。

依据。依据情况是m=0。依据为真的原因微不足道。如果考虑命题T(0)，那么(a)部分就是说A[0..-1]是已排序的。不过在A[0]、…、A[-1]的范围内没有元素，所以(a)一定为真。类似地，T(0)的(b)部分是说，A[0..n-1]的所有元素都至少与A[0..-1]中任一元素一样大。由于后者描述的范围内没有元素，所以(b)部分也为真。

秦皇岛微信公众号开发【秦皇岛网络推广】秦皇岛建站、秦皇岛网站维护、秦皇岛网页制作、秦皇岛微信小程序代运营公司

上往建站提供搭建网站，域名注册，官网备案服务，网店详情页设计，企业网店，专业网络店铺管理运营全托管公司咨询电话，服务器空间，微信公众号托管，网页美工排版,致力于域名申请，竞价托管，软文推广，全网营销,提供标准级专业技术保障，了却后顾之忧,主营：虚拟主机，网站推广，百度竞价托管，网站建设，上网建站推广服务，网络公司有哪些等业务，专业团队服务，效果好。

服务热线：400-111-6878 手机微信同号:18118153152（各城市商务人员可上门服务）