[数据结构与算法]DAY 2 插入排序和分治法

插入排序

概念速记：

循环不变式性质：
1.初始化：循环的第一次迭代之前，它为真。
2.保持：如果循环的某次迭代之前它是真，那么下次迭代之前它仍是真。

形式：
给出一组数组a[7]:2,9,3,6,1,7,4，请使用插入排序从小到大排个序吧

#include<stdio.h>
int main()
{
	int a[7]={2,9,3,6,1,7,4};
	int key,j,i;
	for(j=1;j<=6;j++)
	{
		key=a[j];
		i=j-1;
		while(i>=0&&a[i]>key)
		{
			a[i+1]=a[i];
			i=i-1;
		}
		a[i+1]=key;
	}
	for(i=0;i<7;i++)
		printf("%d ",a[i]);
	return 0;
}

结果：

1 2 3 4 6 7 9

这个代码的过程十分简洁清晰哈，不过我脑子太慢，想了老久终于绕清了，下面记一下步骤的意思。

//整个代码的核心思想是数学归纳法，当然也利用了循环不变式。
#include<stdio.h>
int main()
{
	int a[7]={2,9,3,6,1,7,4};
	int key,j,i;
	for(j=1;j<=6;j++)
	{
		key=a[j];
		i=j-1;
		while(i>=0&&a[i]>key)//将循环不变式中的每一个数字都与key值作比较
		{
			a[i+1]=a[i];
			i=i-1;
		}
		a[i+1]=key;
	}
	for(i=0;i<7;i++)
		printf("%d ",a[i]);
	return 0;
}

分治法

思想：将原问题分解成几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题来建立原问题的解。
三步骤：

• 分解
• 解决
• 合并

归并排序

需要开辟一个临时数组merge辅助归并

#include<stdio.h>
void merge(int arr[],int L,int M,int R)
{
	int LEFT_SIZE=M-L;
	int RIGHT_SIZE=R-M+1;
	int left[LEFT_SIZE];
	int right[RIGHT_SIZE];
	int i,j,k;
	
	//
	for(i=L;i<M;i++)
		left[i-L]=arr[i];

	//
	for(i=M;i<=R;i++)
		right[i-M]=arr[i];
		
	//
	i=0;j=0;k=L;
	while(i<LEFT_SIZE&&j<RIGHT_SIZE)
	{
		if(left[i]<right[j])
		{
			arr[k]=left[i];
			i++;
			k++;
		}
		else
		{
			arr[k]=right[j];
			j++;
			k++;
		}
	}
	
	while(i<LEFT_SIZE)
	{
			arr[k]=left[i];
			i++;
			k++;
	}
	while(j<RIGHT_SIZE)
	{
		arr[k]=right[j];
			j++;
			k++;
	}
	
/*	for(i=0;i<LEFT_SIZE;i++)
		printf("%d ",left[i]);
	
	printf("\n");
	
	for(i=0;i<RIGHT_SIZE;i++)
		printf("%d ",right[i]);
		
	printf("\n");*/
}
void mergeSort(int arr[],int L,int R)
{
	if(L==R)
		return;
	else
	{
		int M=(L+R)/2;
		mergeSort(arr,L,M);
		mergeSort(arr,M+1,R);
		merge(arr,L,M+1,R);
	}
	
}
int main()
{
	int arr[]={2,8,9,10,4,5,6,7};
	int L=0;
	int R=7;
	mergeSort(arr,L,R);
	
	int i;
	for(i=0;i<=R;i++)
		printf("%d ",arr[i]);
	return 0;
}

『这段代码来源于b站视频
链接：归并排序』