首页 > 代码库 > 算法导论 第2章

算法导论 第2章

本章主要是算法知识的基础讲解,介绍了循环不变式,几个简单的排序算法,递归分治算法等内容。

1、循环不变式

循环不变式主要用来说明算法的正确性,那么什么是循环不变式呢,其实就是在循环过程中,一些元素数据必须保持的一些性质,例如在插入排序中,数组为A,必须保证三个性质:

(1) 初始化:在循环开始之前,循环不变式是成立的,即:A[0]是有序的,A[1...n-1]是无序的。

(2) 保持:在循环的某一次迭代开始之前,循环不变式是成立的,那么在此次迭代结束后依然应该是成立的,即:A[0...i]是有序的,A[i+1...n-1]是无序的。

(3) 终止:当循环结束的时候,从循环不变式就可以得出我们的算法的正确性,即:整个数组A是有序的,排序成功。

/*
 *	算法导论 第二章 插入排序
 *	使用增量方法,依次遍历数组并逐个插入有序队列
 *	插入时从后至前,找到不大于当前元素的第一个位置
 *	将此位置后面的元素一次向后移动,将元素插入此位置
 *	时间复杂度为O(n^2)
 */

#include <iostream>
using namespace std;

void printArray(int arr[], int len)
{
	for (int i=0; i<len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

int main()
{
	int arr[] = {12, 21, 9, 80, 3, 11, 90, 4, 67};
	int len = sizeof(arr) / sizeof(arr[0]);

	cout << "原数组:" << endl;
	printArray(arr, len);

	for (int i=1; i<len; i++)
	{
		int temp = arr[i];
		int j = i - 1;
		while (j >= 0 && arr[j] > temp)
		{
			arr[j+1] = arr[j];
			j = j - 1;
		}
		arr[j+1] = temp;
	}

	cout << "插入排序后的数组:" << endl;
	printArray(arr, len);

	return 0;
}

2、在算法分析中,我们通常都主要考虑算法的时间复杂度,因为空间资源相对比较廉价,容易满足,而时间是目前主要追求,而且是考虑算法的最坏情况下的时间复杂度。算法的时间复杂度的具体分析通常可以采用递归式求解(列出时间复杂度的表达式,猜想验证或者直接计算),递归树分析等。

3、分治法

很多算法在结构上是递归的,算法一次有一次的调用自身来解决相关的子问题。这种算法通常采用的就是分治策略:将原问题分成若干个较小的子问题,在递归的解决这些子问题,最后将自问题的解合并成原问题的解。主要分为三个步骤:

分解:将原问题分解成为一些列的子问题。

解决:递归的解决各个子问题,若子问题足够小,就直接解决。

合并:将子问题的解合并成原问题的解。

以下是合并排序以及 习题2-4 的逆序对数量计算

/*
 *	算法导论 第二章 合并排序
 *	利用递归分治法
 *	同时计算序列中逆序对数量
 *	时间复杂度为O(nlgn)
 */
#include <iostream>
using namespace std;

//定义最大整数
#define MAX_NUMBER 0x7fffffff

void printArray(int arr[], int len)
{
	for (int i=0; i<len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

void mergeSort(int arr[], int p, int r);
void merge(int arr[], int p, int q, int r);

//统计序列中元素的逆序对数量
int count;

int main()
{
	int arr[] = {12, 21, 9, 80, 3, 11, 90, 4, 67};
	int len = sizeof(arr) / sizeof(arr[0]);

	cout << "原数组:" << endl;
	printArray(arr, len);

	mergeSort(arr, 0, len-1);

	cout << "合并排序后的数组:" << endl;
	printArray(arr, len);

	cout << "逆序对数量:" << count << endl;

	return 0;
}

void mergeSort(int arr[], int p, int r)
{
	if (p < r)
	{
		int q = (p + r) / 2;
		mergeSort(arr, p, q);
		mergeSort(arr, q+1, r);
		merge(arr, p, q, r);
	}
}

void merge(int arr[], int p, int q, int r)
{
	int n1 = q - p + 1;
	int n2 = r - q;
	int *left = new int[n1+1];
	int *right = new int[n2+1];
	for (int i=0; i<n1; i++)
	{
		left[i] = arr[p+i];
	}

	for (int i=0; i<n2; i++)
	{
		right[i] = arr[q+1+i];
	}

	left[n1] = right[n2] = MAX_NUMBER;

	int i = 0, j = 0;
	for (int k=p; k<=r; k++)
	{
		if (left[i] <= right[j])
		{
			arr[k] = left[i];
			i++;
		} else {
			/* 因为left数组元素都是在right的左边
			 *	所以一旦left[i]>right[j],则left[i]以后的元素都大于right[j]
			 *	逆序对数量增加 n1-1-i+1=n1-i 对
			 */
			count += n1 - i;

			arr[k] = right[j];
			j++;
		}
	}
	delete[] left;
	delete[] right;
}

4、冒泡排序

/*
 *	算法导论 第二章 冒泡排序
 *	思想:冒泡排序,顾名思义就是每一次将序列中最小的元素(较轻)移到前面去
 *	轻的往上冒,重的往下掉,每次将未排序部分的最轻元素冒到最上面
 *	时间复杂度为O(n^2)
 */

#include <iostream>
using namespace std;

void printArray(int arr[], int len)
{
	for (int i=0; i<len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

int main()
{
	int arr[] = {12, 21, 9, 80, 3, 11, 90, 4, 67};
	int len = sizeof(arr) / sizeof(arr[0]);

	cout << "原数组:" << endl;
	printArray(arr, len);

	for (int i=0; i<len; i++)
	{
		for (int j=len-1; j>i; j--)
		{
			if (arr[j] < arr[j-1])
			{
				int temp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = temp;
			}
		}
	}

	cout << "冒泡排序后的数组:" << endl;
	printArray(arr, len);

	return 0;
}

5、习题2.3-7 解答

/*
 *	算法导论 第二章 习题2.3-7
 *	此题利用合并排序+二分查找法
 *	利用合并排序法对数组进行排序时间为O(nlgn)
 *	对S中的每个元素进行一次二分查找时间为O(n*lgn)
 *	所以总的时间复杂度为O(nlgn)
 */

#include <iostream>
using namespace std;

int binarySearch(int arr[], int low, int high, int x);
void mergeSort(int arr[], int p, int r);
void merge(int arr[], int p, int q, int r);
void printArray(int arr[], int len)
{
	for (int i=0; i<len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

int main()
{
	int S[] = {12, 21, 9, 80, 3, 11, 90, 4, 67};
	int x = 22;

	int len = sizeof(S) / sizeof(S[0]);

	cout << "原数组S:" << endl;
	printArray(S, len);
	//利用合并排序法对S排序
	mergeSort(S, 0, len-1);

	int i, index = -1;
	for (i=0; i<len; i++)
	{
		//利用二分查找S中是否存在x-S[i]的元素
		index = binarySearch(S, 0, len-1, x-S[i]);
		if (index != -1 && index != i)
		{
			break;
		}
	}

	if (index != -1)
	{
		cout << "S中的元素:" << S[i] << " + " << S[index] << " = " << x << endl;
	} else {
		cout << "S中不存在和为" << x << "的两个元素" << endl;
	}

	return 0;
}

int binarySearch(int arr[], int low, int high, int x)
{
	while (low <= high)
	{
		int middle = (low + high) / 2;
		if (x > arr[middle])
		{
			low = middle + 1;
		} else if (x < arr[middle]) {
			high = middle - 1;
		} else {
			return middle;
		}
	}

	return -1;
}

void mergeSort(int arr[], int p, int r)
{
	if (p < r)
	{
		int q = (p + r) / 2;
		mergeSort(arr, p, q);
		mergeSort(arr, q+1, r);
		merge(arr, p, q, r);
	}
}

void merge(int arr[], int p, int q, int r)
{
	int n1 = q - p + 1;
	int n2 = r - q;
	int *left = new int[n1+1];
	int *right = new int[n2+1];
	for (int i=0; i<n1; i++)
	{
		left[i] = arr[p+i];
	}

	for (int i=0; i<n2; i++)
	{
		right[i] = arr[q+1+i];
	}

	left[n1] = right[n2] = 0x7fffffff;

	int i = 0, j = 0;
	for (int k=p; k<=r; k++)
	{
		if (left[i] <= right[j])
		{
			arr[k] = left[i];
			i++;
		} else {
			arr[k] = right[j];
			j++;
		}
	}
	delete[] left;
	delete[] right;
}