Java数据结构与经典算法——高手必会.doc

《Java数据结构与经典算法——高手必会.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、大O表示法：粗略的量度方法即算法的速度是如何与数据项的个数相关的2排序2优先级队列6队列8栈9链表10单链表12双端链表16有序链表18双向链表20实现二叉树前序遍历迭代器24迭代器27合并搜索算法30希尔排序34快速排序35二叉树37经典算法的Java实现42（1）河内塔问题：42（2）费式数列44（3）巴斯卡（Pascal）三角形44（4）蒙地卡罗法求PI46（5）最大公因数、最小公倍数47（6）阿姆斯壮数48（7）最大访客数48（8）洗扑克牌（乱数排列）50（9）约瑟夫问题（JosephusProblem）51（10）排列组合53（

2、11）得分排行54（12）选择、插入、气泡排序56（13）快速排序（一）59（14）快速排序（二）61（15）快速排序（三）62（16）合并排序63（17）基数排序64（18）循序查找法（使用卫兵）66（20）插补查找法68（21）费式查找法69（22）稀疏矩阵72（23）多维矩阵转一维矩阵73（24）上三角、下三角、对称矩阵74（25）奇数魔方阵76（26）4N魔方阵77（27）2(2n+1)魔方阵79大O表示法：粗略的量度方法即算法的速度是如何与数据项的个数相关的算法大O表示法表示的运行时间线性查找O(N)二分查找O(logN)无序数

3、组的插入O(1)有序数组的插入O(N)无序数组的删除O(N)有序数组的删除O(N)O(1)是最优秀的,O(logN)良好,O(N)还可以,O(N2)稍差(在冒泡法中见到)排序publicclassJWzw{//插入排序publicvoidinsertArray(Integer[]in){inttem=0;intnum=0;intupnum=0;for(inti=0;i=0;j--){num++;if(in[j+1]

4、];in[j]=tem;upnum++;}else{break;}}}for(inti=0;i

5、ray(Integer[]in){inttem=0;intnum=0;intupnum=0;for(inti=0;i

6、tem.out.println();System.out.println("选择排序循环次数:"+num);System.out.println("移动次数："+upnum);System.out.print("");}//冒泡排序publicvoidefferArray(Integer[]in){inttem=0;intnum=0;intupnum=0;for(inti=0;i

7、n[j+1];in[j+1]=in[i];in[i]=tem;upnum++;}}}for(inti=0;i

8、dprintMulti(){for(intj=1;j<10;j++){for(inti=1;i<=j;i++){System.out.print(i+"*"+j+"="+j*i+"t");}