今天上最后一节史纲课，老师说不管什么学科，最重要的就是思想。我觉得很有道理。
好吧，不扯了。原谅我看书选择了速读策略，中间有很多感觉目前还很难看懂，以后有时间再细细学习。把略过去的在这里记一下。
一、矩阵乘法算法。复杂度从n^3优化到了n^2.81 （数字比较神奇）。因为还没学线性代数，所以以后学了再看。
二、递归复杂度的计算和估计。这部分看起来有些复杂，好像需要比较高的数学水平，有空研究一下。
三、堆排序。这个以前已经写过了。http://www.cnblogs.com/itlqs/p/4750162.html
四、快速排序。
以前一直用C语言库里自带的qsort函数。今天自己写了一下。（膜拜算法导论的整洁代码）思想还是递归（为什么高效的排序总要递归。。），大体思想是这样。我如果有一个函数
int partition(int *a,int l,int r); 功能是让a[l..r]以其中某个数a[k]为基准，a[k]左边的都比它小，右边的都比它大，并且返回k的值。不妨把这个过程称作一次分割。
那么对于我想排序a[1..n]（从小到大）只需要分割一下，然后递归左边，递归右边。就ok了。
代码如下：
#include<stdio.h>int partition(int *a,int l,int r) {int x=a[r];int i=l-1;int j;for (j=l;j<=r-1;j++) {if (a[j]<=x) {i++;int temp=a[i];a[i]=a[j];a[j]=temp;}}x=a[i+1];a[i+1]=a[r];a[r]=x;return i+1; }void qsort(int *a,int l,int r) {if (l<r) {int k=partition(a,l,r);qsort(a,l,k-1);qsort(a,k+1,r);} }int main() {int n;scanf("%d",&n);int a[11]={};int i;for (i=1;i<=n;i++) {scanf("%d",&a[i]);}qsort(a,1,n);for (i=1;i<=n;i++) {printf("%d |",a[i]);}return 0; }
书中也提到了，这个版本的partition并不是最初版本的，最初版本的我在假期也写过了：http://www.cnblogs.com/itlqs/p/4750049.html
但是我目前还没有办法验证这个方法的正确性。。所以以后提升提升再研究一下，目前先用这个版本比较放心。
另外书中还提出了三数取中划分的优化，不过只影响nlgn前面的常数项。
