史志部门建设网站 说明软件开发职业学校

算法学习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;//注意：需要+1if(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.浮点数

---

总结

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