[TOC]
# 算法思想
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。
#### 解题步骤
1. 分解问题：将要解决的问题划分为若干个子问题
2. 求解问题：当子问题划分的足够小时，对子问题进行求解
3. 合并：对所求子问题的结果进行合并，找到原问题的解
# 二分搜索（BinarySearch）
# 归并排序（MergeSort）
#### 算法思想
#### 代码实现-1
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* merge sorted arrays a1 and a2, putting result in out */
void
merge(int n1, const int a1[], int n2, const int a2[], int out[])
{
int i1;
int i2;
int iout;
i1 = i2 = iout = 0;
while(i1 < n1 || i2 < n2) {
if(i2 >= n2 || ((i1 < n1) && (a1[i1] < a2[i2]))) {
/* a1[i1] exists and is smaller */
out[iout++] = a1[i1++];
} else {
/* a1[i1] doesn't exist, or is bigger than a2[i2] */
out[iout++] = a2[i2++];
}
}
}
/* sort a, putting result in out */
/* we call this mergeSort to avoid conflict with mergesort in libc */
void
mergeSort(int n, const int a[], int out[])
{
int *a1;
int *a2;
if(n < 2) {
/* 0 or 1 elements is already sorted */
memcpy(out, a, sizeof(int) * n);
} else {
/* sort into temp arrays */
a1 = malloc(sizeof(int) * (n/2));
a2 = malloc(sizeof(int) * (n - n/2));
mergeSort(n/2, a, a1);
mergeSort(n - n/2, a + n/2, a2);
/* merge results */
merge(n/2, a1, n - n/2, a2, out);
/* free the temp arrays */
free(a1);
free(a2);
}
}
#define N (20)
int
main(int argc, char **argv)
{
int a[N];
int b[N];
int i;
for(i = 0; i < N; i++) {
a[i] = N-i-1;
}
for(i = 0; i < N; i++) {
printf("%d ", a[i]);
}
putchar('\n');
mergeSort(N, a, b);
for(i = 0; i < N; i++) {
printf("%d ", b[i]);
}
putchar('\n');
return 0;
}
```
# 快速排序（QuickSort）
#### 算法思想
#### 代码实现-1
