遞歸與分治
算法介紹
算法是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制盈包。也就是說沸呐，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出呢燥。
如果一個(gè)算法有缺陷崭添，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問題叛氨。不同的算法可能用不同的時(shí)間呼渣、空間或效率來完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量寞埠。
二分搜索：
//從小到大排好序的數(shù)組list[low:high]中查找x
int binarySearch(int *list,int low,int high,int x)
{
int left=low;
int right=high;
while(left<=right)
{
int minddle(left+right)/2;
if(list[middle]==x)return middle;
if(list[middle]<x)
left=middle+1;
else
right=middle-1;
}
return -1;
}
?
//從小到大排好序的數(shù)組list[low:high]中查找x
int binarySearch(int *list,int low,int high,int x)
{
int left=low;
int right=high;
while(left<=right)
{
int minddle(left+right)/2;
if(list[middle]==x)return middle;
if(list[middle]<x)
left=middle+1;
else
right=middle-1;
}
return -1;
}?
歸并排序：
//將a[low,mid]和a[mid+1屁置，high]歸并
void merge(int* a,int low,int mid,int high)
{
int i=low;
int j=mid+1;
for(int k=low;k<=high;k++)
{
aux[k]=a[k];
}
for(int k=low;k<=high;k++)
{
if(i>mid)
a[k]=aux[j++];
else if(j>high)
a[k]=aux[i++];
else if(aux[i]<aux[j])
a[k]=aux[i++];
else
a[k]=aux[j++];
}
}
void mergeSort(int *list,int low,int high)
{
if(high<=low)return ;
int mid=(low+high)/2;
mergeSort(list,low,mid);
mergeSort(list,mid+1,high);
merge(list,low,mid,high);
}
//將a[low,mid]和a[mid+1屁置，high]歸并
void merge(int* a,int low,int mid,int high)
{
int i=low;
int j=mid+1;
for(int k=low;k<=high;k++)
{
aux[k]=a[k];
}
for(int k=low;k<=high;k++)
{
if(i>mid)
a[k]=aux[j++];
else if(j>high)
a[k]=aux[i++];
else if(aux[i]<aux[j])
a[k]=aux[i++];
else
a[k]=aux[j++];
}
}
void mergeSort(int *list,int low,int high)
{
if(high<=low)return ;
int mid=(low+high)/2;
mergeSort(list,low,mid);
mergeSort(list,mid+1,high);
merge(list,low,mid,high);
}