首页 > 代码库 > 算法导论 第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;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。