算法学习01：排序&&二分

算法学习01：排序&&二分

前言

需要记忆的模版：

快速排序

void quick_sort(int q[], int l, int r)
{
	if(l >= r) return;
	
	int x = q[l]; i = l - 1; j = r + 1; 
	while(l < r) {
		do i++; while(q[i] < x);//注意1：do_while至少执行一次 
		do j--; while(q[j] > x);//直到不满足条件才出来 
	}
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);	
}

归并排序：

void merge_sort(int q[] , int l, int r)
{
	if(l >= r) return;
	
	int mid = l + r >> 2;
	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);
	
	int k = 0, i = l, j = mid + 1;
	while(i <= mid && j <= r) 
		if(q[i] <= q[j]) temp[k ++ ] = q[i ++ ];
		else temp[k ++ ] = q[j ++ ];
	while(i <= mid) temp[k ++ ] = q[i ++ ];//注意1：考虑有多有少的情况 
	while(j <= r) temp[k ++ ] = q[j ++ ];
	
	//注意2：将temp数组复制到原数组q 
	for(int i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];	
 } 

整数二分：

int l = 0, r = n - 1; 
while(l < r)
{
	int	mid = (l + r) / 2;
	if(q[mid] >= x) r = mid;//右边 
	else l = mid + 1;
}

while(l < r)
{
	int mid = (l + r + 1) / 2;//注意：需要+1
	if(q[mid] <= x) l = mid;//左边
	else r = mid - 1;
}

浮点数二分

double l = 0, r = x;
while(r - 1 > le-8)//注意1：精度问题 
{
	double mid = (l + r) / 2;
	if(mid * mid >= x) r = mid;
	else l = mid;//注意不是mid + 1
 } 

提示：以下是本篇文章正文内容：

一、排序

1.快速排序

2.归并排序：

二、二分

1.整数

2.浮点数

总结

提示：这里对文章进行总结：
记忆模版！！！