大三笔记

@TOC大三笔记

欢迎来到大三学子，自救笔记

你好！ 凡觉咸鱼者，必咸鱼也。巴山楚水凄凉地，二十三年弃置身。谁还没有优秀过呢？只不过相比的人不同罢了！

新的改变

其实很多年前就开始关注博客，但写作来讲，这是第一次，很是激动与紧张。激动于咸鱼可能翻身，紧张于实在是没什么实力，毕竟大三的水平。
这篇文章及以后的文章大概都是记录一些大学基本的东西，不深澳都很基础

分治算法

今天先做一个分治算法。
所谓分治，即分而治之，大事化小，小事化了。
实现归并排序。

#include <iostream>
using namespace std;

//函数声明
void merge_sort(int a[],int left,int right);
void merge(int b[],int left ,int mid, int right);

int main() {
    int q;
    cout<<"To invoke the default array, enter 1, and the user-defined array input 2 :"<<endl;
    cin>>q;
    if(1 == q){
        //固定数组
	    int a[9] = {12, 45, 5, 58, 48, 85, 27, 82, 2};
	    cout<<"The array before the sort ： "<<endl;
	    for(int i=0; i<9; i++)
	    cout<<a[i]<<" ";
	    cout<<endl;
	    //对数组进行归并排序
	    merge_sort(a, 0, 8);       //调用排序函数
	    cout<<"Sorted array ： "<<endl;     //输出排序后的数组
	    for(int i=0; i<9; i++)
	        cout<<a[i]<<" ";
	    cout<<endl;
    }
    else{
        //用户*输入数组
	    int n;   //数组大小
	    cout<<"Please enter the size of the array : ";   //用户定义数组大小
	    cin>>n;
	    int a[n];
	    cout<<"Please enter the array data : "<<endl;
	    for(int i=0;i<n;i++){       //用户输入数组数据
            cin>>a[i];
        }
	    //对数组进行归并排序
	    merge_sort(a, 0, n-1);     //调用排序函数
	    cout<<"Sorted array ： "<<endl;   //输出排序后的数组
	    for(int i=0; i<n; i++)
	        cout<<a[i]<<" ";
	    cout<<endl;
    }
	return 0;}
void merge_sort(int a[],int left,int right){
    if(left<right){
		int mid = (left + right)/2;     //求数组的中间元素标号
		merge_sort(a,left,mid);       //对数组左半部分调用归并排序函数
		merge_sort(a,mid+1,right);   //对数组右半部分调用归并排序函数
		merge(a,left,mid,right);  //将左右部分合并到同时排好序到原数组上
	}
}

void merge(int a[],int left ,int mid, int right){
//创建动态数组，暂时存储对左右部分排序后的数组
	int *temp = new int[right-left+1];   
	int p,q,r;     //设置三个变量，一次代替left，mid，right
	p=left;
	q=mid+1;
	r=right;
	int i=0;