分治法

分治法

将一个规模为n的大问题，分解为k个独立且与原结构相同问题求解。 1、分解； 2、解决；递归解决子问题 3、合并。

排序算法（升序）

1、二路归并排序 分解：每次分两组，一直分到一个元素一组； 归并：相邻两（组）元素合并到一组并排序，直到完成。

2、快速排序

#include "stdafx.h" #include "stdio.h" int partition(int *a,int left,int right){ int i = left,j = right+1;//left是标兵 do{ do i++; while(a[i] < a[left]); do j--; while(a[j] > a[left]); if(i < j) { int t = a[i]; a[i] = a[j]; a[j] = t; } }while(i < j); int t = a[left]; a[left] = a[j]; a[j] = t; return j; } void quickSort(int *a,int x,int y){ if(x<y){ int m = partition(a,x,y); quickSort(a,x,m-1); quickSort(a,m+1,y); } } int _tmain(int argc, _TCHAR* argv[]) { int a[8]={12,11,23,56,43,66,78,23}; quickSort(a,0,7); for(int i =0;i<8;i++){ printf("%d\n",a[i]); } getchar(); return 0; }

查找算法

1、折半查找（有序） 2、选择算法（无序）