算法导论学习笔记第二章算法基础

蔚落 2022-11-06 00:59 249阅读 0赞

使用插入排序解决以下排序问题：  
输入：n个数的一个序列<a1, a2, … , an>。  
输出：输入序列的一个排列<a1’, a2’, …, an’>，满足a1’<=a2’<=…<=an’。

我们希望排序的数也称为关键词，虽然概念上我们在排序一个序列，但输入是以n个元素的数组形式出现的。

伪代码中，我们使用最清晰、最简洁的表示方式说明给定的算法，有时最清晰的表达方式是英语，伪代码通常不关心软件工程的问题，为了更简洁地表达算法地本质，常常忽略数据抽象、模块性和错误处理问题。

插入排序对于少量元素的排序是一个有效的算法，插入排序的工作方式像许多人排序一手扑克牌，开始时，我们的左手为空并且桌子上的牌面向下，然后我们每次从桌子上拿走一张牌并将它插入左手中正确的位置，为找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较，拿在左手上的牌总是排序好的。

对于插入排序，我们将其伪代码过程命名为INSERTION-SORT，参数是一个包含长度为n的要排序序列的数组A\[1…n\]，A中元素数目n用A.length表示，以下伪代码原址排序输入的数（算法在数组A中重排这些数，任何时候，最多只有其中的常数个数字存储在数组外），在以下伪代码结束时，输入数组A包含排序好的输出序列：

INSERTION-SORT(A):
    	for j = 2 to A.length
    		key = A[j]
    		// Insert A[j] into the sorted sequence A[1...j-1]
    		i = j - 1
    		while i > 0 and A[i] > key
    			A[i + 1] = A [i]
    			i = i - 1
    		A[i + 1] = key

使用以上伪代码排序的一个例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3R1czAwMDAw_size_16_color_FFFFFF_t_70]  
我们把A\[1…j-1\]的性质形式地表示为一个循环不变式：在第1~8行的for循环的每次迭代开始时，子数组A\[1…j-1\]由原来在A\[1…j-1\]中的元素组成，但已按序排列。

循环不变式主要用来帮助我们理解算法正确性，关于循环不变式必须证明三条性质：  
1.初始化：循环的第一次迭代前，它为真。  
2.保持：如果循环的每次迭代之前它为真，那么下次迭代之前它仍为真。  
3.终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法时正确的。

前两条性质成立时，在循环的每次迭代之前循环不变式为真，这类似于数学归纳法。

第三条性质也许是最重要的，因为我们将使用循环不变式证明正确性，通常，我们和导致循环终止的条件一起使用循环不变式，终止性不同于我们通常使用的数学归纳法的做法，在归纳法中，归纳步是无限使用的，这里当循环终止时，停止“归纳”。

对于插入排序，证明这些性质成立：  
1.初始化：首先证明在第一次循环迭代开始前（j=2时），循环不变式成立，此时子数组A\[1…j-1\]中只有一个元素A\[1\]，而且该子数组是排序好的。这表明第一次循环迭代开始前循环不变式成立。  
2.保持：非形式化地，for循环体的第4~7行将A\[j-1\]、A\[j-2\]、A\[j-3\]等向右移动一个位置，直到找到A\[j\]的位置，第8行将A\[j\]的值插入该位置，此时子数组A\[1…j\]由原来A\[1…j\]中的元素组成，但已按序排列。那么对for循环的下一次迭代增加j将保持循环不变式。第二条性质的一种更形式化的处理要求我们对第5~7行的while循环给出证明并证明一个循环不变式，然而这里我们不愿陷入形式主义的困境，而是依赖以上非形式化的分析证明第二条性质对外层循环成立。  
3.终止：导致for循环终止的条件是j>A.length（n），每次循环迭代j增加1，那么必有j=n+1。在循环不变式的表述中用n+1代替j，我们有：子数组A\[1…n\]由原来A\[1…n\]组成，但已按序排列，子数组A\[1…n\]就是整个数组，推断出整个数组已排序，因此算法正确。

C++实现以上插入排序伪代码：

#include <vector>
    #include <iostream>
    using namespace std;
    
    int main() { 
    	vector<int> ivec = {  5,2,4,6,1,3 };
    	
    	for (int i = 1; i < ivec.size(); ++i) { 
    		int key = ivec[i];
    		int j = i - 1;
    		while (j >= 0 && ivec[j] > key) { 
    			ivec[j + 1] = ivec[j];
    			--j;
    		}
    		ivec[j + 1] = key;
    	}
    	
    	for (int i : ivec) { 
    		cout << i << " ";
    	}
    	cout << endl;
    }

本书中伪代码：  
1.在循环退出后，循环计数器保持其值。  
2.for循环每次迭代减少其循环计数器时，使用关键词downto；每次增加循环计数器时，使用关键词to。  
3.把表示一个数组或对象的对象看作指向表示数组或对象的数据的一个指针，对于某对象x的所有属性f，复制y=x导致y.f等于x.f，若现在置x.f=3，则赋值后y.f也等于3。  
4.不指向任何对象的指针被赋值为NIL。  
5.过程的参数按值传递，但传递对象或数组时，传递的是指向它们的指针。  
6.允许return返回多个值。  
7.布尔运算符and和or都是短路的。

二进制大数加法：

#include <iostram>
    #include <vector>
    using namespace std;
    
    int main() { 
    	vector<bool> ivec1 = {  1,0,1,0,1,0,1 };
    	vector<bool> ivec2 = {  0,1,0,1,1,0,1 };
    	vector<bool> res(ivec1.size() + 1);
    
    	bool flag = 0;    // 进位标志
    	for (int i = ivec1.size() - 1; i >= 0; --i) { 
    		res[i + 1] = (ivec1[i] == ivec2[i]) ? flag : !flag;    // 正好两个为true时res[i]才为false
    		flag = (ivec1[i] == ivec2[i]) ? ivec1[i] : flag;    // 两个以上为true时flag为true
    	}
    	res[0] = flag;
    
    	for (bool b : res) { 
    		cout << b << " ";
    	}
    	cout << endl;
    }

分析算法的结果意味着预测算法需要的资源。有时我们关心内存、通信带宽或计算机的硬件资源，但通常我们想度量的是计算时间。一般，通过分析求解某个问题的几种候选算法，我们可以选出一种最有效的算法，这种分析有时可能指出不止一个可行的候选算法，但这个过程往往能抛弃几个较差的算法。

在能够分析一个算法前，我们必须有一个要使用的实现技术的模型，包括描述所用资源及其代价的模型，本书的大多数章节，我们假定一种通用的单处理器计算模型----随机访问机（random-access machine，RAM）作为我们的实现技术，在RAM模型中，指令一条接一条地执行，没有并发操作。

严格地说，我们应精确定义RAM模型地指令及其代价，但这样做既乏味又对算法的设计与分析没多大意义。还应注意不能滥用RAM模型，假如一台RAM有一条排序指令，此时只用一条指令就能排序，这样的RAM是不现实的，因为真实的计算机并没有这样的指令，所以指导意见就是真实的计算机如何设计，RAM就如何设计。RAM模型包含真实计算机中常见的指令：算术指令（如加法、减法乘法、除法、取余、向下取整、向上取整）、数据移动指令（装入、存储、复制）和控制指令（条件与无条件转移、子程序调用与返回），每条这样的指令所需时间都为常量。

RAM模型中的数据类型有整数型和浮点实数型，本书中不太关心精度，但某些应用中，精度是至关重要的，我们可以对每个数据字的规模假定一个范围，这样字长不会变得巨大的同时其上的操作都在常量时间内进行，这不现实。

真实的计算机包含上面未列出的指令，这些指令代表了RAM模型中的一个灰色区域，如指数运算是一条常量时间的指令吗？一般不是，然而某些情况下是，如左移操作在常量时间内将一个整数的各位向左移k位，即2k，所以只要k不大于计算机字中的位数，就能以常量时间计算2k，我们应避免RAM模型中这样的灰色区域，但当k是一个足够小的正整数时，我们把2k看作常量时间的操作。

RAM模型中不对当代计算机中的内存层次进行建模，即没有对高速缓存和虚拟内存进行建模，这种内存层次对真实计算机上运行的真实程序的影响有时是巨大的，但本书中不考虑这些影响，一是包含内存层次后模型复杂地多，难于使用；二是RAM模型分析通常能很好地预测实际计算机上的性能。

输入规模：依赖于研究的问题，对许多问题，如排序或傅里叶变换，最自然的量度是输入中的项数，对其他问题，如两整数相乘，输入规模的最佳量度是用二进制表示输入所需的总位数，有时需要用两个数描述输入规模更合适，如某算法的输入是一个图，则输入规模用图的顶点数和边数来描述。

运行时间：一个算法在特定输入上的运行时间指执行的基本操作数或步数，我们采纳以下观点：执行每行伪代码需要常量时间，虽然一行与另一行可能需要不同的时间，但假定第i行每次执行需要时间ci，ci是一个常量。

以下我们由繁到简地改进INSERTION-SORT伪代码地运行时间表达式：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3R1czAwMDAw_size_16_color_FFFFFF_t_70 1]  
该算法的运行时间是执行每条语句的运行时间之和：  
![在这里插入图片描述][20210309203304410.png]  
即使对给定规模的输入，一个算法的运行时间也可能依赖于给定的是该规模下的哪个输入，如上例中输入数组已排好序，则出现最佳情况，这时对每个j，第五行当i取j-1时，都有A\[i\]<=key，因此不会进入while循环，从而运行时间变为：  
![在这里插入图片描述][20210310211109104.png]  
此时运行时间是n的线性函数。

若输入数组是反向排序的，则导致最坏情况，此时需要将A\[j\]与整个已排序子数组A\[1…j-1\]中的每个元素比较，由于输入规模为n时外层for循环运行n-1次，内层的while判断次数当j为2时判断两次，j为3时判断三次…j为n时判断n次，因此c5总运行次数为`(2 + n)(n - 1) / 2`，化简得：![在这里插入图片描述][2021031021263629.png]  
而c6和c7运行次数与c5的差别在于，c5会多判断一次，因此需要运行的次数变为`(1 + n - 1)(n - 1) / 2`，化简得：  
![在这里插入图片描述][20210310212700734.png]  
因此总运行时间变为：  
![在这里插入图片描述][20210310213801592.png]  
此时运行时间是输入规模的二次函数。

本书中往往集中于只求最坏情况运行时间，理由是：  
1.一个算法的最坏情况运行时间给出了运行时间的一个上界，可确保该算法绝不需要更长时间。  
2.对某些算法，最坏情况经常出现。  
3.平均情况往往和最坏情况大致一样差，如插入排序的平均运行时间也是输入规模的一个二次函数。

我们可以使用简化的抽象来使INSERTION-SORT的分析更加容易，我们真正感兴趣的是运行时间的增长率或增长两集，常量可被抽象忽略，所以我们只考虑最重要的项，对以上的插入排序来说，是an2，因为当n很大时，低阶项相对不太重要，我们也忽略最重要的项的常系数，因为对于比较大的输入，确定计算效率时常量因子不如增长率重要，此时只剩下n2，我们记插入排序具有最坏情况运行时间θ（n2）（读作theta n平方）。

选择算法：首先找出A中最小的元素将其与A\[1\]中的元素交换，接着找出A中的次小元素与A\[2\]中的元素进行交换：

#include <vector>
    #include <iostream>
    using namespace std;
    
    int main() { 
    	vector<int> ivec = {  1,5,7,9,6,3,4,2,3 };
    	size_t sz = ivec.size();
    
    	for (size_t i = 1; i < sz; ++i) { 
    		size_t j = i - 1;
    		int min = ivec[j];
    		size_t minIndex = j;
    		while (j < sz) { 
    			if (min > ivec[j]) { 
    				min = ivec[j];
    				minIndex = j;
    			}
    			++j;
    		}
    		swap(ivec[i - 1], ivec[minIndex]);
    	}
    
    	for (int i : ivec) { 
    		cout << i << " ";
    	}
    	cout << endl;
    }

此算法最好情况下比较操作也不能省略，因此最好和最坏情况的时间复杂度都是θ（n2)。

可选择使用的算法设计技术有很多，插入排序使用了增量方法：在排序子数组A\[1…j-1\]后，将单个元素A\[j\]插入子数组的适当位置，产生排序好的子数组A\[1…j\]。还有一种算法设计方法是分治法。

许多算法在结构上是递归的：为解决一个给定问题，算法一次或多次递归调用其自身。这些算法典型地遵循分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时有三个步骤：  
1.`分解`原问题为若干子问题，这些子问题是原问题的规模较小的实例。  
2.`解决`这些子问题，递归地求解各子问题，若子问题的规模足够小，则直接得出解。  
3`合并`这些子问题的解成原问题的解。

归并排序完全遵循分治模式：  
1.分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。  
2.解决：使用归并排序递归地排序两个子序列。  
3.合并：合并两个已排序的子序列以产生已排序的答案。

当待排序的序列长度为1时，递归开始回升，此时不用做任何操作，因为长度为1的序列是有序的。

归并排序算法的关键操作是合并步骤中两个已排序序列的合并，通过一个辅助过程MERGE(A, p, q, r)来完成合并，其中A是一个数组，p、q、r是数组下标，满足p<=q<r，该过程假设子数组A\[p…q\]和A\[q+1…r\]都已排好序，它合并这两个子数组形成单一的已排好序的子数组并代替当前的子数组A\[p…r\]。

过程MERGE需要θ（n）的时间，其中n=r-p+1，是待合并元素的总数，它按以下方式工作：假设桌上有两堆牌面朝上的牌，每堆都已排序，最小的牌在顶上，我们希望把这两堆牌合并成单一的排好序的输出堆，输出堆牌面朝下地放在桌上，基本步骤是在牌面朝上的两堆牌的顶上两张牌中选取较小的一张，将该牌从其堆中移开（该堆的顶上将显露出一张新牌）并牌面朝下地将其放置到输出堆，重复这个步骤，直到一个堆为空，这时，拿起剩余的输入堆并牌面朝下地将该堆放置到输出堆。

下面伪代码实现了上面的思想，但它有一个额外的变化，以避免在每个步骤中检查是否有堆为空，在每个堆的底部放置一张哨兵牌，它包含一个特殊值，用于简化代码，以下使用∞作为哨兵值，每当显露一张值为∞的牌，它不可能为较小的牌，除非两个堆都已显露出其哨兵牌，一旦这样，所有非哨兵牌都已被放置到输出堆，我们事先知道刚好r-p+1张牌将被放置到输出堆，因此一旦已执行r-p+1个步骤，算法就可以停止：

MERGE(A, p, q, r):
        n1 = q - p + 1
        n2 = r - 1
        // let L[1 .. .n1 + 1] and R[1 ... n2 + 1] be new arrays
        for i = 1 to n1
            L[i] = A[p + i - 1]
        for j = 1 to n2
        	R[j] = A[q + j]
        L[n1 + 1] = ∞
        L[n2 + 1] = ∞
        i = 1
        j = 1
        for k = p to r
        	if L[i] <= R[j]
        		A[k] = L[i]
        		i = i + 1
        	else 
        		A[k] = R[j]
        		j = j + 1

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3R1czAwMDAw_size_16_color_FFFFFF_t_70 2]  
上图中的运行过程遵循以下循环不变式，执行r-p+1个步骤：在开始第12~17行for循环的每次迭代时，子数组A\[p…k-1\]按从小到大的顺序包含L\[1…n1+1\]和R\[1…n2+1\]中的k-p个最小元素，进而，L\[i\]和R\[j\]是各自所在数组中未被复制回A的最小元素。

证明以上循环不变式正确性：  
1.初始化：循环的第一次迭代前，k=p，子数组A\[p…k-1\]为空，这个空子数组包含L和R的k-p=0个最小元素，又因为i=j=1，所以L\[i\]和R\[j\]都是各自所在数组中未被复制回数组A的最小元素。  
2.保持：首先假设L\[i\]<=R\[j\]，此时L\[i\]是未被复制回数组A的最小元素，因为A\[p…k-1\]包含k-p个最小元素，所以在第14行将L\[i\]复制到A\[k\]之后，子数组A\[p…k\]将包含k-p+1个最小元素。增加k和i的值后，为下次迭代重新建立了该循环不变式。  
3.终止：终止时k=r+1，根据循环不变式，子数组A\[p…k-1\]是A\[p…r\]从以小到大的顺序包含L\[1…n1+1\]和R\[1…n2+1\]中的k-p=r-p+1个最小元素，除两个最大哨兵元素外，其他元素都已被复制回数组A。

把以上MERGE过程作为归并排序算法中的一个子程序来用：

MERGE-SORT(A, p, r)
    if p < r
    	q = (p + r) / 2    // q是结果向下取整的值
    	MERGE-SORT(A, p, q)
    	MERGE-SORT(A, q + 1, r)
    	MERGE(A, p, q, r)

我们初始调用MERGE-SORT(A, 1, A.length)，这里A.length=n，以下是当n为2的幂时该过程的操作：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3R1czAwMDAw_size_16_color_FFFFFF_t_70 3]  
以上过程的C++代码：

#include <iostream>
    #include <vector>
    #include <limits>
    using namespace std;
    
    void merge(vector<int>& ivec, size_t l, size_t m, size_t r) { 
    	vector<int> ivec1(ivec.begin() + l, ivec.begin() + m + 1);
    	vector<int> ivec2(ivec.begin() + m + 1, ivec.begin() + r + 1);
    
    	ivec1.push_back(numeric_limits<int>::max());
    	ivec2.push_back(numeric_limits<int>::max());
    
    	size_t i = 0;
    	size_t j = 0;
    	for (size_t k = l; k <= r; ++k) { 
    		if (ivec1[i] <= ivec2[j]) { 
    			ivec[k] = ivec1[i];
    			++i;
    		} else { 
    			ivec[k] = ivec2[j];
    			++j;
    		}
    	}
    }
    
    void mergeSort(vector<int>& ivec, size_t l, size_t r) { 
    	if (l < r) { 
    		size_t mid = (l + r) >> 1;
    		mergeSort(ivec, l, mid);
    		mergeSort(ivec, mid + 1, r);
    		merge(ivec, l, mid, r);
    	}
    }
    
    int main() { 
    	vector<int> ivec = {  1,5,7,9,6,3,4,2,3 };
    	mergeSort(ivec, 0, ivec.size() - 1);
    	for (int i : ivec) { 
    		cout << i << " " << endl;
    	}
    	cout << endl;
    }

当一个算法包含对其自身的递归调用时，我们往往可以使用递归方程或递归式描述其运行时间，该方程根据在较小输入上的运行时间来描述在规模为n的问题上的总运行时间，然后可以用数学工具求解该递归式并给出算法性能的界。

分治算法运行时间的递归式来自基本模式的三个步骤，假设T（n）是规模为n的一个问题的运行时间，若问题规模足够小，如对某个常量c，n<=c，则直接求解需要常量时间，将其写作θ（1）。假设将原问题分解成a个子问题，每个子问题的规模是原问题的1/b（对归并排序，a和b都是2），为了求解规模为n/b的子问题，需要T（n/b）的时间，所以需要aT（n/b）的时间求解a个子问题，如果分解问题成子问题需要时间D（n），合并子问题的解成原问题的解需要时间C（n），则得到递归式：  
![在这里插入图片描述][20210313170119593.png]  
假定原问题的规模是2的幂，这样基于递归式的分析将被简化，下面分析归并排序n个数的最坏情况运行时间T（n）的递归式，当有n>1个元素时，分解运行时间如下：  
分解：仅需计算子数组的中间位置，需要常量时间，因此D（n）=θ（1）。  
解决：递归求解两个规模均为n/2的子问题，将贡献2T（n/2）的运行时间。  
合并：在一个具有n个子数组上过程MERGE需要θ（n）的时间，因此C（n）=θ（n）。

因此得出T（n）：  
![在这里插入图片描述][20210313170757192.png]  
T（n）为θ（nlgn），优于插入排序：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3R1czAwMDAw_size_16_color_FFFFFF_t_70 4]  
不使用哨兵完成归并排序：

#include <iostream>
    #include <vector>
    using namespace std;
    
    void merge(vector<int>& ivec, size_t l, size_t m, size_t r) { 
    	vector<int> ivec1(ivec.begin() + l, ivec.begin() + m + 1);
    	vector<int> ivec2(ivec.begin() + m + 1, ivec.begin() + r + 1);
    
    	size_t i = 0;
    	size_t j = 0;
    	size_t k = l;
    	while (i < m - l + 1 && j < r - m) { 
    		if (ivec1[i] < ivec2[j]) { 
    			ivec[k] = ivec1[i];
    			++i;
    		} else { 
    			ivec[k] = ivec2[j];
    			++j;
    		}
    		++k;
    	}
    
    	while (i < m - l + 1) { 
    		ivec[k] = ivec1[i];
    		++i;
    		++k;
    	}
    	while (j < r - m) { 
    		ivec[k] = ivec2[j];
    		++j;
    		++k;
    	}
    }
    
    void mergeSort(vector<int>& ivec, size_t l, size_t r) { 
    	if (l < r) { 
    		size_t mid = (l + r) >> 1;
    		mergeSort(ivec, l, mid);
    		mergeSort(ivec, mid + 1, r);
    		merge(ivec, l, mid, r);
    	}
    }
    
    int main() { 
    	vector<int> ivec = {  1,5,7,9,6,3,4,2,3 };
    	mergeSort(ivec, 0, ivec.size() - 1);
    	for (int i : ivec) { 
    		cout << i << " " << endl;
    	}
    	cout << endl;
    }

二分查找：

#include <iostream>
    #include <vector>
    using namespace std;
    
    bool found = false;
    
    size_t binarySearch(vector<int>& ivec, int target) { 
    	found = false;
    	size_t l = 0, r = ivec.size() - 1;
    	size_t m = (l + r) >> 1;
    	while (l <= r) { 
    		if (ivec[m] > target) { 
    			r = m - 1;
    		}
    		else if (ivec[m] < target) { 
    			l = m + 1;
    		} else { 
    			found = true;
    			return m;
    		}
    		m = (l + r) >> 1;
    	}
    }
    
    int main() { 
    	vector<int> ivec = {  1,2,4,6,7,8,9 };
    	size_t index = binarySearch(ivec, 5);
    	if (found) { 
    		cout << index << endl;
    	} else { 
    		cout << "not found" << endl;
    	}
    }

![在这里插入图片描述][20210313180808490.png]  
首先使用归并排序排序整个输入集合，需要时间θ（nlgn），之后令两个指针分别指向排好序的集合头和尾，计算两指针指向数的和，如果和比x小，则增加头指针，如果和比x大，则减小尾指针，如果和等于x，则返回true，重复以上过程，直到两指针相遇（不存在这样的两个数）或找到和：

#include <iostream>
    #include <vector>
    using namespace std;
    
    void merge(vector<int>& ivec, size_t l, size_t m, size_t r) { 
    	vector<int> ivec1(ivec.begin() + l, ivec.begin() + m + 1);
    	vector<int> ivec2(ivec.begin() + m + 1, ivec.begin() + r + 1);
    
    	size_t i = 0;
    	size_t j = 0;
    	size_t k = l;
    	while (i < m - l + 1 && j < r - m) { 
    		if (ivec1[i] < ivec2[j]) { 
    			ivec[k] = ivec1[i];
    			++i;
    		}
    		else { 
    			ivec[k] = ivec2[j];
    			++j;
    		}
    		++k;
    	}
    
    	while (i < m - l + 1) { 
    		ivec[k] = ivec1[i];
    		++i;
    		++k;
    	}
    	while (j < r - m) { 
    		ivec[k] = ivec2[j];
    		++j;
    		++k;
    	}
    }
    
    void mergeSort(vector<int>& ivec, size_t l, size_t r) { 
    	if (l < r) { 
    		size_t mid = (l + r) >> 1;
    		mergeSort(ivec, l, mid);
    		mergeSort(ivec, mid + 1, r);
    		merge(ivec, l, mid, r);
    	}
    }
    
    bool findSum(vector<int>& ivec, int target) { 
    	size_t l = 0, r = ivec.size() - 1;
    	while (l < r) { 
    		if (ivec[l] + ivec[r] > target) { 
    			--r;
    		}
    		else if (ivec[l] + ivec[r] < target) { 
    			++l;
    		} else { 
    			return true;
    		}
    	}
    	return false;
    }
    
    int main() { 
    	vector<int> ivec = {  1,5,7,9,6,3,4,2,3 };
    	mergeSort(ivec, 0, ivec.size() - 1);
    	if (findSum(ivec, 150)) { 
    		cout << "true" << endl;
    	} else { 
    		cout << "false" << endl;
    	}
    }

虽然归并排序的最坏情况运行时间是θ（nlgn），而插入排序的最坏情况运行时间为θ（n2），但插入排序中的常量因子可能使得它在n较小时，在许多机器上实际运行地更快，因此，在归并排序中当子问题变得足够小时，采用插入排序来使递归的叶变粗是有意义的。

冒泡排序：

#include <iostream>
    #include <vector>
    using namespace std;
    
    void bubbleSort(vector<int>& ivec) { 
    	size_t sz = ivec.size();
    	for (size_t i = 0; i < sz; ++i) { 
    		for (size_t j = 0; j < sz - 1 - i; ++j) { 
    			if (ivec[j] > ivec[j + 1]) { 
    				swap(ivec[j], ivec[j + 1]);
    			}
    		}
    	}
    }
    
    int main() { 
    	vector<int> ivec = {  1,5,7,9,6,3,4,2,3 };
    	bubbleSort(ivec);
    	for (int i : ivec) { 
    		cout << i << " " << endl;
    	}
    	cout << endl;
    }

霍纳规则：  
![在这里插入图片描述][202103141555306.png]  
霍纳规则时间复杂度为θ（n）。如果展开一项一项地求解多项式，在每次求解xk时都要循环k次，k的取值为0~n，因此时间复杂度为θ（n2）。

霍纳规则的代码实现：

#include <iostream>
    #include <vector>
    using namespace std;
    
    int horner(vector<int>& ivec, int x) { 
    	int y = 0;
    	size_t sz = ivec.size();
    	while (sz > 0) { 
    		y = x * y + ivec[sz - 1];
    		--sz;
    	}
    	return y;
    }
    
    int main() { 
    	vector<int> ivec = {  2, 3 };
    	cout << horner(ivec, 2) << endl;
    }

假设A\[1…n\]是一个有n个不同数的数组，若i<j且A\[i\]>A\[j\]，则对偶（i，j）称为A的一个逆序对。在最坏情况需要θ（nlgn）的时间下求解逆序对：可在归并排序的每次合并时计算逆序对数量，具体计算方式为每次合并时如果后面数组中有大于前面数组的数，增加逆序对数量：

#include <iostream>
    #include <vector>
    using namespace std;
    
    void merge(vector<int>& ivec, size_t l, size_t m, size_t r, unsigned &num) { 
    	vector<int> ivec1(ivec.begin() + l, ivec.begin() + m + 1);
    	vector<int> ivec2(ivec.begin() + m + 1, ivec.begin() + r + 1);
    	
    	size_t index1 = 0, index2 = 0, k = l, sz1 = ivec1.size();
    	while (index1 < m - l + 1 && index2 < r - m) { 
    		if (ivec1[index1] <= ivec2[index2]) { 
    			ivec[k] = ivec1[index1];
    			++index1;
    		} else { 
    			ivec[k] = ivec2[index2];
    			num += sz1 - index1;
    			++index2;
    		}
    		++k;
    	}
    
    	while (index1 < m - l + 1) { 
    		ivec[k] = ivec1[index1];
    		++index1;
    		++k;
    	}
    	while (index2 < r - m) { 
    		ivec[k] = ivec2[index2];
    		++index2;
    		++k;
    	}
    }
    
    unsigned reverseOrderPairNum(vector<int> &ivec, size_t l, size_t r) { 
    	static unsigned num = 0;    // 首次进入函数时初始化，避免迭代时重复初始化此值
    
    	if (l < r) { 
    		size_t m = (l + r) >> 1;
    		reverseOrderPairNum(ivec, l, m);
    		reverseOrderPairNum(ivec, m + 1, r);
    		merge(ivec, l, m, r, num);
    	}
    
    	return num;
    }
    
    int main() { 
    	vector<int> ivec = {  2, 3, 8, 6, 1};
    	cout << reverseOrderPairNum(ivec, 0, ivec.size() - 1) << endl;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3R1czAwMDAw_size_16_color_FFFFFF_t_70]: /images/20221023/6233736473524688b0a2f3b3e8c38be8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3R1czAwMDAw_size_16_color_FFFFFF_t_70 1]: /images/20221023/755a9e9cbed646c4b290ec7edaeb4692.png
[20210309203304410.png]: /images/20221023/8b306a4e3ad7492888104a2ef8219db3.png
[20210310211109104.png]: /images/20221023/905fd248b7bb4fd6b94cff114933fcf9.png
[2021031021263629.png]: /images/20221023/216c1c98b660475d80d48423cb37e854.png
[20210310212700734.png]: /images/20221023/7d37b4e1a0544334a1e8451f916fca78.png
[20210310213801592.png]: /images/20221023/03f6e97bb1a245559f1c175700ac37e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3R1czAwMDAw_size_16_color_FFFFFF_t_70 2]: /images/20221023/7aebaf3fe2cd4cde82a09c56f53ff8b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3R1czAwMDAw_size_16_color_FFFFFF_t_70 3]: /images/20221023/d48bd632ceb046639b346d58d5c05eb5.png
[20210313170119593.png]: /images/20221023/bfa200b440434e4e90306b150fafc96b.png
[20210313170757192.png]: /images/20221023/3f908305fb3f4d0a8e66266c4814b785.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3R1czAwMDAw_size_16_color_FFFFFF_t_70 4]: /images/20221023/07c977b5d9b4436692f757fe36b8b68b.png
[20210313180808490.png]: /images/20221023/2814931bcc934828a1f98a223a05299b.png
[202103141555306.png]: /images/20221023/4daa2423c47f476ca9cd2ac98a12e9f4.png