9 6 3 7 5 4
第一遍： 1次比较 1次比较 9 | 6 3 7 5 4 6 9 | 3 7 5 4
第2遍： 1次比较 1次比较 6 9 | 3 7 5 4 3 6 9 | 7 5 4
第3遍： 1次比较 1次比较 3 6 7 9 | 5 4
第4遍： 1次比较 1次比较 3 6 7 9 | 5 4 3 4 5 6 7 | 9 tmp=4
第一遍： 1次比较 1次比较 2 | 6 3 7 5 4
第二遍： 2次比较 1次比较 2 3 | 6 7 5 4 v=3
第三遍： 3次比较 1次比较 2 3 6 | 7 5 4 v=7
第四遍： 4次比较 1次比较 2 3 5 6 | 7 4 v=5
第i遍： i次比较 1次比较 /*
第一遍是将a[1]插入到a[0]
第二遍是将a[2]插入到a[0],a[1] 第三遍是将a[3]插入到 a[0],a[1],a[2] ...
第i遍是将a[i]插入到 a[0],...,a[i-1] ...
第n-1遍是将a[n-1]插入到 a[0],...,a[n-2]
insert(a,i):
将a[i]插入到a[0],...,a[i-1]中 */ 代码：
void insertion(int a[],int n){ int i;
for(i=1;i insert(a,i);//n-1遍 } void insert(int a[],int i){ //将a[i]插入到a[0],...,a[i-1]中 int v=a[i]; while(i>0 && v a[i]=v; } 插入方法：直接插入， 三、折半插入:从中间向两边走 O(n*log n) a0,a1 , ... ai, | ai+1 h l 0 1 2 3 4 5 6 7 8 9 10 11 2 3 4 5 6 7 8 9 10 11 12 13 | 4.5 m=(l+h)/2=(0+11)/2=5 h=m-1 m=(0+4)/2=2 l=m+1 m=(3+4)/2=3 h=m-1=2 4.5在5前面 n-1遍,比较次数 第1遍 log 1 第2遍 log 2 第3遍 log 3 第4遍 log 4 第i遍 log i 第n-1遍 log n-1 ---------------- log 1 +log 2+ log3 +.. +log(n-1) =log (n-1)! <=O(n*log n) 四、选择排序：O(n*n) 1、选择最小关键字者， 放在原来数组里头，与a[0]交换 2、选择次小关键字者 放在原来数组里头，与a[1]交换 ..... 共选n-1次， 第1次从n个里面选，a[0]到a[n-1] n-1 第2次从n-1个里面选，a[1]到a[n-1] n-2 第3次从n-2个里面选，a[2]到a[n-1] ... 第i次从n-i+1个里面选，a[i-1]到a[n-1] ... 第n-1次从2个里面选，a[n-2]到a[n-1] 如何选择最小者？ 记录当前最小元素的下标 代码： int mini(int a[],int i,int n){ //从a[i]到a[n-1]中选出最小元素下标 int j,min=i; //min是到现在为止最小元素的下标 for(j=i+1;j for(i=0;i //从a[i]到a[n-1]中选出最小者a[j] 交换a[i]和a[j]; } } n-1+n-2+...+2+1=O(n*n) 五、快速排序: 最好平均O(n*log n) 最坏O(n*n) 不稳定 l ...... r a[l] ...... a[r] v=a[r] 另外开2个数组（浪费空间） b 放比v小的 c 放比v大的 在同一个数组内划分，增加难度 v=a[r]基准元素 最后放在a[i]处 [l.... i-1] < i < [i+1 ... r] 第一部分 第二部分 第三部分 挑选基准元素会导致最好、最坏 方案1: a[l] .. a[r] L ...... r v=a[r] i j 代码： int partition(int a[],int L,int r){ //将a[L]..a[r]分成三个部分，v=a[r] //v在中间，v左边的比v小，v右边的比v大 //v最后所在的下标存储在变量i中 int i=L-1;j=r;int v=a[r]; for(;;){//O(n) while(a[++i] while(a[--j]>v)if(j==L)break; if(i>=j)break; 交换(a[i],a[j]); }//两头夹攻，中间会师，就停止。 //O(n) ，i往后，j往前 交换(a[i],a[r]); return i; } L r v=a[r]=4 1 2 3 4 5 6 7 i j 方案2: a[L] .. a[r] L ...... r v=a[L] i j 代码： int partition(int a[],int L,int r){ //将a[L]..a[r]分成三个部分，v=a[L] //v在中间，v左边的比v小，v右边的比v大 //v最后所在的下标存储在变量j中 int i=L;j=r+1;int v=a[L]; for(;;){//O(n) while(a[++i] while(a[--j]>v)if(j==L)break; if(i>=j)break; 交换(a[i],a[j]); }//两头夹攻，中间会师，就停止。 //O(n) ，i往后，j往前 交换(a[j],a[L]); return j; } void QuickSort(int a[],int L,int r){ if(L>=r)return;//处理边界情况 i=partition(a,L,r);//O(n) QuickSort(a,L,i-1);//v左边进行排序 自己调用自己 QuickSort(a,i+1,r);//v右边进行排序 } main(){ int a[]={2,5,1,7,9}； QuickSort(a,0,4); } T(n):快速排序时间复杂度 最好：T(n)=n+2*T(n/2) T(n/2)=n/2+2*T(n/4) T(n)=n+2*T(n/2) =n+2*(n/2+2*T(n/4)) =n+n+4*T(n/4) =n+n+n+8*T(n/8) =n* log n =O(n*log n) 最坏：T(n)=n+T(n-1) =n+(n-1)+T(n-2) =n+n-1+n-2+T(n-3)=O(n*n) 六、堆排序：在二叉树中讲 七、归并排序 内部排序：在内存中进行 外部排序：在内存和外存中进行， 因为元素太多，无法一次全部装 入内存，只好借助外存。 比如归并排序用于外部排序 n个 b2 b3 b4 b5 b6 b7 a2 a3 a4 a5 m个 a1 b1 O(n+m) a1 a2 b1 涉及题目： 08年 15,17,20 07年 1,8 06年 一(2,8)，三(22)，四(26) 05年 三(2)，四(3) 第七章 树 线性表：先后 树：上下 图：没先没后，没上没下 一、基本概念：度（孩子个数）， 叶子节点，内部节点，树根， 高度（层数） 有序树，无序树，二叉树 二、性质p131 定理：如果二叉树的叶结点数为n0， 则具有双分支的结点数n2=n0-1 证明：假设二叉树结点总数为n, 单分支（度为1）的结点数n1 于是n=n0+n1+n2 （1） 假设二叉树边总数为b, 往上看，每条边是一个结点的天线 只有一个结点（根）没有天线， 其他结点都只有一个天线 所以b=n-1 （2） 往下看，每条边是一个结点的地线 叶子无地线，单分支结点有一条地线 双分支结点有两条地线 b=0*n0+1*n1+2*n2 （3） =n1+2*n2 b=n-1= n0+n1+n2-1=n1+2*n2 n0+n1+n2-1=n1+2*n2 n2=n0-1 [证毕] 三、二叉树节点数与高度关系 1、树的高度=h 至少h个结点 四世同堂：至少要四个人 爷爷 | 爸爸 | 儿子 | 孙子 1、树的高度=h 最多能有_______个结点？ 满二叉树的概念 1 A 当前层1个节点 总共2^1=2-1个节点 / \\ 2 B C 当前层2个节点 总共2^2=4-1个节点 / \\ / \\ 3 D E F G 当前层4个节点 总共2^3=8-1个节点 ... .... ... h 当前层2^(h-1)个节点 总共2^h-1个节点 高度=h 四、完全二叉树 满二叉树右下角开始， 从右到左，从下到上， 删除一些结点。 涉及题目： 08年 4 五、父亲数组表示法 1 / \\ 2 3 / \\ / \\ 4 5 9 10 / | \\ 6 7 8 下标 0 1 2 3 4 5 6 7 8 9 10 数组a ? 0 1 1 2 2 5 5 5 3 3 给定i,求i的父亲=a[i] 给定i,打印i的儿子 六、左儿子右兄弟表示法 =一般树存储在二叉链表中 关键：把一般树转换成二叉树： 将父亲管理儿子方式改为 父亲管理大儿子， 大儿子管理二儿子 （二儿子变成大儿子的右孩子）