【C语言实现-左神算法课p3习题】

左神算法课p3

• • 1.master公式分析递归函数的时间复杂度
  • 2.递归求解数组最大值
  • 3.归并排序
  • • 1.补充--new和delete的用法
    • 2.归并排序
  • 4.归并排序扩展--小和问题
  • • 1.补充--vector使用详解
    • 2.小和问题
    • • 1.使用new动态开辟数组版本
      • 2.使用vector动态开辟数组版本
  • 5.归并排序扩展--逆序对问题
  • 6.快速排序引例--荷兰国旗问题
  • • 1.问题1
    • 2.问题2
    • 3.完整代码及测试
  • 7.快速排序

1.master公式分析递归函数的时间复杂度

2.递归求解数组最大值

使用master公式分析以下程序时间复杂度为O(n)

#include
using namespace std;
int Max(int a, int b) {
	return a > b ? a : b;
}
int ArrMax(int *arr, int left, int right) {
	if (left == right) //递归出口
		return arr[left];
	int mid = (left + right) / 2;
	int left_part_max = ArrMax(arr, left, mid);
	int right_part_max = ArrMax(arr, mid + 1, right);
	return Max(left_part_max, right_part_max);
}
int main() {
	int test[] = { 3,4,1,8,6,4,2,6,9,4,1 };
	int len = (sizeof(test) / sizeof(test[0]));
	cout << ArrMax(test, 0, len - 1);
}

3.归并排序 1.补充–new和delete的用法

2.归并排序

#include
using namespace std;
void Print(int *arr, int len) {
	for (int i = 0; i < len; i++)
		cout << arr[i] << ' ';
	cout << endl;
}
void Merge(int *arr, int left, int mid, int right) {
	int *res = new int[right - left + 1];
	if (res == NULL) {
		cout << "内存不足" << endl;
		return;
	}
	int i = left, j = mid + 1, k = 0;
	while (i <= mid && j <= right)
		res[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
	while (i <= mid)
		res[k++] = arr[i++];
	while (j <= right)
		res[k++] = arr[j++];
	//将排好序的res覆盖arr，注意下标不同，但一一对应
	for (int m = left, n = 0; m <= right; m++, n++)
		arr[m] = res[n];
	//释放res
	delete []res;
	res = NULL;
}
void MergeSort(int *arr, int left, int right) {
	if (left == right) //递归出口
		return;
	int mid = (left + right) / 2;
	//分解
	MergeSort(arr, left, mid);
	MergeSort(arr, mid + 1, right);
	//有序合并
	Merge(arr, left, mid, right);
}
int main() {
	int test[] = { 2,4,1,6,5,8,9,0 };
	Print(test, 8);
	MergeSort(test, 0, 7);
	Print(test, 8);
}

4.归并排序扩展–小和问题 1.补充–vector使用详解

#include
#include
using namespace std;
int main() {
	//构造及初始化
	/*
	vector v1;  //v1是一个空vector，它潜在的元素是T类型的，执行默认初始化
	vector v2(v1); //v2中包含有v1所有元素的副本
	vector v2 = v1;//等价于v2(v1)，v2中包含有v1所有元素的副本
	vector v3(n, val);//v3包含了n个重复的元素，每个元素的初始值都是val
	vector  v4(n); //v4包含了n个重复执行了值初始化的对象
	vector  v5{ a,b,c... };//v5包含了初始值个数的元素，每个元素被赋予相应的初始值
	vector  v5 = { a,b,c... };//等价于 v5{a,b,c...};
	*/
	vector<int> test1{ 1,2,3,4,5 };
	vector<float> test2(5, 0);

	//迭代器及遍历容器元素
	//注意 auto自动推断数据类型，但使用时必须初始化
	// auto b = v.begin(), c = v.end(); b表示v的第一个元素 c表示v尾元素的下一个位置
	//v.cbegin()和v.cend()是C++11新增的，它们返回一个const的迭代器，不能用于修改元素，建议使用
	for (auto it = test1.cbegin(); it != test1.cend(); it++)
		cout << *it << " ";
	cout << endl;

	//添加元素，不能用下标形式添加元素，比如v[len]=3
	//v.push_back负责把一个值当成vector对象的尾元素"压到（push）"vector对象的"尾端（back）"
	int add;
	while (cin >> add)  //输入ctrl+z结束输入
		test1.push_back(add);
		//v.emplace_back()：在容器尾部添加一个元素，调用构造函数原地构造，不触发拷贝构造和移动构造，比push_back()更加高效
		//test1.emplace_back(add);
	//显示
	for (auto it = test1.cbegin(); it != test1.cend(); it++)
		cout << *it << " ";
	cout << endl;
	
	//与添加对应的--删除 *** 作
	//v.pop_back();//删除最后一个元素

	//获取元素
	//v.at(int idx);//返回索引idx所指的数据
	//v.front();//返回容器中第一个数据元素
	//v.back();//返回容器中最后一个数据元素

	//其它常用函数
	//v.size();//返回容器中的元素个数
	//v.resize(int num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除
	//v.clear();//删除容器中所有元素
}

2.小和问题

解题思路：递归+归并

1.使用new动态开辟数组版本

//使用new动态开辟数组版本
#include
using namespace std;
int MergeSum(int *arr, int left, int mid, int right) {
	int *temp = new int[right - left + 1]; //动态开辟和arr等规模的数组
	int i = left, j = mid + 1, k = 0, res = 0;
	//以下 *** 作，在计算merge小和同时，保证了让arr有序
	while (i <= mid && j <= right) {
		res += (arr[i] < arr[j] ? arr[i] * (right - j + 1) : 0);
		temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
	}
	while (i <= mid)
		temp[k++] = arr[i++];
	while(j <= right)
		temp[k++] = arr[j++];
	//用temp更新arr
	for (int t = 0; t < (right - left + 1); t++)
		arr[t + left] = temp[t];
	return res;
}
int SmallSum(int *arr, int left, int right) {
	if (left == right)
		return 0;  //递归出口，只有一个元素，没有小和
	int mid = left + ((right - left) >> 1);
	return SmallSum(arr, left, mid) + SmallSum(arr, mid + 1, right) + MergeSum(arr, left, mid, right);
}
int main() {
	int test[] = { 4,7,2,5,1 };
	cout << SmallSum(test, 0, 4);
}

2.使用vector动态开辟数组版本

//使用vector动态开辟数组版本
#include
#include
using namespace std;
int MergeSum(vector<int> &v, int left, int mid, int right) {
	vector<int> temp(right - left + 1); //动态开辟和arr等规模的数组
	int i = left, j = mid + 1, k = 0, res = 0;
	//以下 *** 作，在计算merge小和同时，保证了让arr有序
	while (i <= mid && j <= right) {
		res += (v[i] < v[j] ? v[i] * (right - j + 1) : 0);
		temp[k++] = v[i] < v[j] ? v[i++] : v[j++];
	}
	while (i <= mid)
		temp[k++] = v[i++];
	while(j <= right)
		temp[k++] = v[j++];
	//用temp更新arr
	for (int t = 0; t < (right - left + 1); t++)
		v[t + left] = temp[t];
	return res;
}
int SmallSum(vector<int> &v, int left, int right) {
	if (left == right)
		return 0;  //递归出口，只有一个元素，没有小和
	int mid = left + ((right - left) >> 1);
	return SmallSum(v, left, mid) + SmallSum(v, mid + 1, right) + MergeSum(v, left, mid, right);
}
int main() {
	vector<int> test{ 4,7,2,5,1 };
	cout << SmallSum(test, 0, 4);
}

5.归并排序扩展–逆序对问题

#include
using namespace std;
int MergeCount(int *arr, int left, int mid, int right) {
	int *temp = new int[right - left + 1]; //动态开辟和arr等规模的数组
	int i = left, j = mid + 1, k = 0, res = 0;
	//和小和问题的一些 *** 作区别：保证temp逆序而不是升序；计算的是个数，不是值
	while (i <= mid && j <= right) {
		res += (arr[i] > arr[j] ? (right - j + 1) : 0);
		temp[k++] = (arr[i] > arr[j] ? arr[i++] : arr[j++]);
	}
	while (i <= mid)
		temp[k++] = arr[i++];
	while(j <= right)
		temp[k++] = arr[j++];
	//用temp更新arr
	for (int t = 0; t < (right - left + 1); t++)
		arr[t + left] = temp[t];
	return res;
}
int ReverseCP(int *arr, int left, int right) {
	if (left == right)
		return 0;  //递归出口，只有一个元素，没有逆序对
	int mid = left + ((right - left) >> 1);
	return ReverseCP(arr, left, mid) + ReverseCP(arr, mid + 1, right) + MergeCount(arr, left, mid, right);
}
int main() {
	int test[] = { 4,7,2,5,1 };
	cout << ReverseCP(test, 0, 4);
}

6.快速排序引例–荷兰国旗问题

1.问题1

//问题1：分成 <=num， >num 的两部分
void SplitTwoPart(int *arr, int len, int num) {
	int left = -1; //记录左区
	int i = 0; //用于记录当前下标
	while (i < len) {
		if (arr[i] > num)
			i++;
		else {
			if (left + 1 != i)
				Swap(arr[left + 1], arr[i]);
			left++; //扩左区
			i++;
		}
	}
}

2.问题2

//问题2：分成 num 的三部分
void SplitThreePart(int *arr, int len, int num) {
	int left = -1, right = len; //记录左区和右区
	int i = 0; //记录当前下标
	while (i < right) { //进入右区内则已经达到要求
		if (arr[i] == num)
			i++;
		else if (arr[i] > num) { //和右区前一个交换，扩右区
			if (i != right - 1)
				Swap(arr[i], arr[right - 1]);
			right--;  //扩右区
		}
		else { //和左区后一个交换，扩左区，i++
			if (i != left + 1)
				Swap(arr[i], arr[left + 1]);
			left++;
			i++;
		}
	}
}

3.完整代码及测试

//荷兰国旗问题
#include
using namespace std;
//数组打印函数
void Print(int *arr, int len) {
	for (int i = 0; i < len; i++)
		cout << arr[i] << ' ';
	cout << endl;
}
//两数交换函数
void Swap(int &a, int &b) {
	a = a ^ b;
	b = a ^ b;
	a = a ^ b;
}
//问题1：分成 <=num， >num 的两部分
void SplitTwoPart(int *arr, int len, int num) {
	int left = -1; //记录左区
	int i = 0; //用于记录当前下标
	while (i < len) {
		if (arr[i] > num)
			i++;
		else {
			if (left + 1 != i)
				Swap(arr[left + 1], arr[i]);
			left++; //扩左区
			i++;
		}
	}
}
//问题2：分成 num 的三部分
void SplitThreePart(int *arr, int len, int num) {
	int left = -1, right = len; //记录左区和右区
	int i = 0; //记录当前下标
	while (i < right) { //进入右区内则已经达到要求
		if (arr[i] == num)
			i++;
		else if (arr[i] > num) { //和右区前一个交换，扩右区
			if (i != right - 1)
				Swap(arr[i], arr[right - 1]);
			right--;  //扩右区
		}
		else { //和左区后一个交换，扩左区，i++
			if (i != left + 1)
				Swap(arr[i], arr[left + 1]);
			left++;
			i++;
		}
	}
}
//测试
int main() {
	int test1[] = { 8,5,4,2,7,2,6,4,1 };
	int test2[] = { 8,5,4,2,7,2,6,4,1 };
	int len = (sizeof(test1) / sizeof(test1[0]));
	Print(test1, len);

	cout << "问题1--分成两区--结果：" << endl;
	SplitTwoPart(test1, len, 4);
	Print(test1, len);

	cout << "问题2--分成三区--结果：" << endl;
	SplitThreePart(test2, len, 4);
	Print(test2, len);
}

7.快速排序

#include
using namespace std;
//数组打印函数
void Print(int *arr, int len) {
	for (int i = 0; i < len; i++)
		cout << arr[i] << ' ';
	cout << endl;
}
//快速排序
void QuickSort(int *arr, int left, int right) {
	if (left >= right)
		return;
	int temp = arr[left]; //选择第一个数作为基准值
	int i = left, j = right;
	while (i < j) {
		while (i<j&&arr[j]>temp)
			j--;
		if(i<j)
			arr[i++] = arr[j];
		while (i < j&&arr[i] <= temp)
			i++;
		if(i<j)
			arr[j--] = arr[i];
	}
	arr[i] = temp; //i处的值已经安置好
	QuickSort(arr, left, i - 1);
	QuickSort(arr, i + 1, right);
}
//测试
int main() {
	int test[] = { 8,5,4,2,7,2,6,4,1 };
	Print(test, 9);
	QuickSort(test, 0, 8);
	Print(test, 9);
}