第三天
排序查找是我自己觉得最头疼的算法了,常搞混去的啊.不知道各位学得如何,如果不错,还请告诉我一些经验!
查找
一、 知识点 /静态查找->数组 1、 什么是查找
\\动态查找->链树 ●顺序查找，时间复杂度 O(n)
●折半查找：条件：有序；时间复杂度 O(nlog2n) (时间复杂度实际上是查找树的高度)
●索引查找：条件：第I+1块的所有元素都大于第Ｉ块的所有元素。 算法：根据index来确定X所在的块（i） 时间复杂度：m/2 在第Ｉ块里顺序查找X 时间复杂度：n/2 总的时间复杂度：(m+n)/2
●二叉排序树 1）定义：左子树键值大于根节点键值；右子树键值小于根的键值，其左右子树均为二叉排序树。
2）特点：中序遍历有序->（删除节点用到此性质）
3）二叉排序树的查找：如果根大于要查找的树，则前左子树前进，如果根小于要查找的树，则向右子树前进。
4）结点的插入->二叉排序树的构造方法
5）结点删除（难点） 1、右子树放在左子树的最右边 2、左子树放在右子树的最左边 ●avl树（二叉平衡树）：左右子树高度只能差１层，即｜h｜<=1其子树也一样。
●B树：n阶B树满足以下条件 1）每个结点（除根外）包含有N～2N个关链字。 2）所有叶子节点都在同一层。 3）B树的所有子树也是一棵B树。 特点：降低层次数，减少比较次数。
排序
一、知识点
1、排序的定义
/内排序：只在内存中进行 2、排序的分类
\\外排序：与内外存进行排序 内排序： /直接插入排序 1）插入排序
\\shell排序 /冒泡排序 2）交换排序
\\快速排序
/简单选择排序 3）选择排序 堆
\\ 锦标赛排序 4）归并排序（二路）
5）基数排序（多关链字排序）
3、时间复杂度（上午题目常考，不会求也得记住啊兄弟姐妹们！）
* * * * * * 15 * * * 15 * * *
/稳定 * * * * * * * * 15 15 * * * *(前后不变) 排序
\\ 不稳定 * * * * * * * * 15 15 * * * *(前后改变)
经整理得:选择、希尔、堆、快速排序是不稳定的；直接插入、冒泡、合并排序是稳定的。
●锦标赛排序方法： 13 16 11 18 21 3 17 6 \\ / \\ / \\ / \\ / 13 11 3 6 \\ / \\ / 11 3 \\ /
3（胜出，将其拿出，并令其为正无穷&Go On）
●归并排序方法： 13 16 11 18 21 3 17 6 \\ / \\ / \\ / \\ / 13,16 11,18 3,21 6,17 \\ / \\ / 11,13,16,18 3,6,17,21 \\ / 3,6,11,13,16,17,18,21
●shell排序算法：1）定义一个步长（或者说增量）数组D[m]；其中：D[m-1]=1(最后一个增量必须为1，否则可能不完全) 2）共排m趟，其中第i趟增量为D[i],把整个序列分成D[i]个子序列，分别对这D[i]个子序列进行直接插入排序。 程序如下： for(i=0;i {对第i个子序列进行直接插入排序； 注意：下标之差为D[i]; } } ●快速排序 ( smaller )data ( bigger ) d[] i-> 13 16 11 18 21 3 17 6 24 8 <-j 先从后往前找，再从前往后找。 思想：空一个插入一个，i空j挪，j空i挪（这里的i,j是指i,j两指针所指的下标）。 一次执行算法：1）令temp=d[0](枢纽)，i=0,j=n-1; 2）奇数次时从j位置出发向前找第一个比temp小的元素，找到后放到i的位置(d[i]=d[j];i++;) i往后挪。 3）偶数次时从i开始往后找第一个比temp大的数，（d[j]=d[i];j--;) 4）当i=j时，结束循环。d[i]=temp； 再用递归对左右进行快速排序，因为快速排序是一个典型的递归算法。 ●堆排序 定义：d[n]满足条件：d[i] 调整(重点) 程序: flag=0; while(i<=n-1) { if(d[i] { if(d[2*i+1]>d[2*i+2]) 8 24 {d[i]<->d[2*i+1]; 24 21 -> 8 21 i=2*i+1; else { d[i]<->d[2*i+2]; i=2*i+2; } } else flag=1; //是堆 } 堆排序过程： ●基数排序(多关键字排序) 扑克: 1) 大小->分配 2) 花色->分配,收集 思想:分配再收集. 构建链表:链表个数根据关键字取值个数有关. 例:将下面九个三位数排序: 321 214 665 102 874 699 210 333 600 定义一个有十个元素的数组: a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 第一趟(个位): 210 321 102 333 214 665 699 600 874 结果: 210 600 321 102 333 214 874 665 699 第二趟(十位): 600 210 321 333 665 874 699 102 214 结果: 600 102 210 214 321 333 665 874 699 第三趟(百位): 102 210 321 600 874 214 333 665 699 结果: 102 210 214 321 333 600 665 699 874(排序成功) 最近在看一位程序员的笔记,也挺不错的啊.这应当是他的网站.他总说他的网站人气不够,现在顺便就帮他宣传一下啦！http://zhgpa.vicp.net/bbs，大家有时间多去去哦，呵呵!谢谢大伙支持！另外,还向大家推荐一个网站：http://kaowang.com/，挺不错的一个考试网站。学到不少东东啊！ 八大类算法 程序员考试下午试题最后一道一般是八大类算法里头的.大家尤其要注意的是递归，因为近几年都考了，而且有的还考两题。可以说如果我们不掌握递归就没有掌握C，况且递归是C里的难点。为了控制合格率，程序员考试不会让我们轻松过关的，为了中国软件业，我想也应该这样啊。 /数据结构(离散) 迭代 \\数值计算(连续) 枚举 策略好坏很重要 递推 递归 回溯 分治 贪婪 动态规划 其中：递推、递归、分治、动态规划四种算法思想基本相似。都是把大问题变成小问题，但技术上有差别。 第四天 枚举: 背包问题: 枚举策略：1)可能的方案：2N 2)对每一方案进行判断. 枚举法一般流程： while(还有其他可能方案) { 按某种顺序可难方案; 检验方案; if(方案为解) 保存方案; } } 枚举策略: 例：把所有排列枚举出来 P6=6!. Min:123456 Max:654321 a1a2a3a4a5a6=>?(下一排列)=>? 比如:312654的下和种情况=>314256 递归 递归算法通常具有这样的特征：为求解规模为N的问题，设法将它分解成一些规模较小的问题，然后从这些较小问题的解能方便地构造出题目所需的解。而这些规 模较小的问题也采用同样的方法分解成规模更小的问题，通过规模更小的问题构造出规模校小的问题的解，如此不断的反复分解和综合，总能分解到最简单的能直接 得到解的情况。 因此,在解递归算法的题目时,要注意以下几点: 1) 找到递归调用的结束条件或继续递归调用条件. 2) 想方设法将处理对象的规模缩小或元素减少. 3) 由于递归调用可理解为并列同名函数的多次调用,而函数调用的原则是一层一层调用,一层一层返回.因此,还要注意理解调用返回后的下一个语句的作用.在一些 简单的递归算法中,往往不需要考虑递调用返回后的语句处理.而在一些复杂的递归算法中,则需要考虑递归调用返回后的语句处理和进一步的递归调用. 4) 在读递归程序或编写递归程序时,必须要牢记递归函数的作用,这样便于理解整个函数的功能和知道哪儿需要写上递归调用语句.当然,在解递归算法的题目时,也需要分清递归函数中的内部变量和外部变量. 表现形式: ●定义是递归的(二叉树,二叉排序树) ●存储结构是递归的(二叉树,链表,数组) ●由前两种形式得出的算法是递归的 一般流程: function(variable list(规模为N)) { if(规模小,解已知) return 解; else { 把问题分成若干个部分; 某些部分可直接得到解; 而另一部分(规模为N-1)的解递归得到; } } 例1：求一个链表里的最大元素. 大家有没想过这个问题用递归来做呢?