[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
