一、算法的概念

（1）算法（Algorithm） 是将一组输入转化成一组输出的一系列计算步骤，其中每个步骤必须能在有限时间内完成。

（2）

二、插入排序

1.用玩扑克的方式解释插入排序

要点在于：
（1）前提：每次插入新的值时，前面的序列都是有序的

（2）但和插入扑克牌有一点不同，不可能在两个相邻的存储单元之间再插入一个单元，因此要将插入点之后的数据依次往后移动一个单元。

2.插入排序的算法如下：

（1）运行结果如下：

（2）如何严格证明这个算法是正确的？

总结：

• 这里的第一条就相当于递归的Base Case
• 第二条就相当于递归的递推关系。这再次说明了递归和循环是等价的

3.算法的时间复杂度分析

（1）比较评价算法的好坏，一个重要的标准就是算法的时间复杂度

这里有一个问题，m不是个常数，也不取决于输入长度n，而是取决于具体的输入数据。
（a）在最好情况下
数组 a 的原始数据已经排好序了， while 循环一次也不执行，总的执行时间是(c1+c2+c5)*n-(c1+c2+c5)，可以表示成an+b的形式，是n的线性函数（Linear Function）。

（b）在最坏情况（Worst Case） 下
所谓最坏情况是指数组 a 的原始数据正好是从大到小排好序的

（c）平均情况（Average Case）

（2）在分析算法的时间复杂度时，我们更关心最坏情况而不是最好情况

（3）如何证明是2n^2+3lgn和 n ^2是同一量级的？

（4）几种常见的时间复杂度函数按数量级从小到大的顺序

（5）Small-O notation和Big-O notation

四、归并排序：分而治之

1.插入排序与归并排序的区别

2.归并排序的步骤

（1）代码如下

（2）执行结果如下

（3）代码解释如下：
首先是sort函数：
sort 函数把a[start…end]平均分成两个子序列，分别是a[start…mid]和a[mid+1…end]，对这两个子序列分别递归调用 sort 函数进行排序，然后调用 merge 函数将排好序的两个子序列合并起来。

接着是merge函数：
合并的过程很简单，每次循环取两个子序列中最小的元素进行比较，将较小的元素取出放到最终的排序序列中，如果其中一个子序列的元素已取完，就把另一个子序列剩下的元素都放到最终的排序序列中

（4）归并排序的调用过程如下：

（5）归并排序的复杂度
merge函数的时间复杂度为

sort函数的时间复杂度为

总的时间的复杂度为：

五、快速排序：分而治之

define N 某个数;
int a[N];

int partition(int start,int end)
{
	int i=start;
	int j=end;
	int base=a[i];
	while (i!=j){
		while (a[j]>=base &&i<j)
			j--;
		while (a[i]<=base && i<j)
			i++;
		if (i<j){
			int t;
			t=a[start]
			a[start]=a[end];
			a[end]=t;
		}
	}
	if(i==j){
		a[start]=a[i];
		a[i]=base;
	}
	return i;
}

void quicksort(int start,int end)
{
	int mid;
	if(end>start){
		mid=partition(start,end);
		quicksort(start,mid-1);
		quicksort(mid+1,end);
	}
}

1.快排的核心思想

先找到一个基数（若是最左边的为基数，升序排列），从右边开始寻找小于基数的数字，然后从左边开始寻找大于基数的数，找到了就交换，直到这两端遍历的i和j碰头为止。

2.时间复杂度

N：需要排序的元素个数
最差时间复杂度O(N^2);
平均时间复杂度O(NlogN),这里的log是以2为底