java培训一.doc

排序算法1. 插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。2. 选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。3. 冒泡排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。4. 快速排序实质上和冒泡排序一样，都是属于交换排序的一种应用。所以基本思想和上面的冒泡排序是一样的。void bubbleSort(int numlist)/ 冒泡排序算法 7 C! q. C1 x7 L) f int temp; for(int j=1;jnumlist.length;j+) for(int i=0;inumlisti+1)2 _1 R9 I) |_8 # v0 g temp =numlisti+1; g, Y n! S/ a. numlisti+1 = numlist;: 1 m T( N$ % h/ _7 N numlist = temp; 3 C0 y& O$ ; x ( N. a2 B1 u7 L3 ? * B7 G) m; B! T $ g. e: x7 u* A( R void selectionSort (int numlist) /选择排序算法L! E6 i; H5 IE$ W2 N int temp; for(int i=0;inumlist.length-1;i+) for(int j=i+1;jnumlistj) temp = numlistj;! Z( O8 h8 g( Y+ x; X4 q; s numlistj = numlist;& g: h- Q1 U _! B( d. R numlist = temp; 3 z. L t8 k6 y2 W/ L X % n n2 D4 ; R( ( e7 G5 U7 f# Z4 u: 4 d void insertSort (int numlist) /插入排序算法 % b5 W% a# n T, k- k int temp,in,out;1 F: d9 d: R9 w8 + t1 B for(out=1;out0 & numlistin-1=temp) numlistin=numlistin-1; -in; numlistin=temp;+ ( |( m o6 H8 D: _ f 6 _/ - Z8 1 Q% i8 搜索算法1. 题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求：4不能在第三位，3与5不能相连。2. 基本思路： 1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，所有结点的遍历路径就是最后对这6个数字的排列组合结果集。 2 显然这个结果集还未达到题目的要求。从以下几个方面考虑： 1. 3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。 2. 不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果 3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。 采用二维数组定义图结构，最后的代码是：3. import java.util.Iterator;4. import java.util.TreeSet;5.6. public class TestQuestion 7.8. private String b = new String1, 2, 2, 3, 4, 5;9. private int n = b.length;10. private boolean visited = new booleann;11. private int a = new intnn;12. private String result = ;13. private TreeSet set = new TreeSet();14.15. public static void main(String args) 16. new TestQuestion().start();17. 18.19. private void start() 20.21. / Initial the map a22. for (int i = 0; i n; i+) 23. for (int j = 0; j n; j+) 24. if (i = j) 25. aij = 0;26. else 27. aij = 1;28. 29. 30. 31.32. / 3 and 5 can not be the neighbor.33. a35 = 0;34. a53 = 0;35.36. / Begin to depthsearch.37. for (int i = 0; i n; i+) 38. this.depthFirstSearch(i);39. 40.41. / Print result treeset.42. Iterator it = set.iterator();43. while (it.hasNext() 44. String string = (String) it.next();45. / 4 can not be the third position.46. if (string.indexOf(4) != 2) 47. System.out.println(string);48. 49. 50. 51.52. private void depthFirstSearch(int startIndex) 53. visitedstartIndex = true;54. result = result + bstartIndex;55. if (result.length() = n) 56. / Filt the duplicate value.57. set.add(result);58. 59. for(int j = 0; j n; j+) 60. if (astartIndexj = 1 & visitedj = false) 61. depthFirstSearch(j);62. else 63. continue;64. 65. 66.67. / restore the result value and visited value after listing a node.68. result = result.substring(0, result.length() -1);69. visitedstartIndex = false;70. 71. 2.一个nn（1=nn)，现在允许用量杯从水缸里取水或将水倒回水缸里，而且两个量杯中的水也可以相互倾倒，试设计计算机程序求出在m升的量杯中准确量得k升(Nknm)所需的最少操作步数。 (每一个取水或倒水都算一个操作步数)【习题】【八数码问题】 九宫格中有8个数码，其中只有一个空，规则是只能把一个数码移动到空的格子中，要求从一个初始状态移动到一个目标状态所要花费的最少步数。如下图初始状态28316475目标状态12386475【算法分析】 解决此类问题的办法是宽度搜索，深度搜索耗时太大无法接受。当需要移动的步数很多时，普通的宽度搜索仍旧无法满足需要，需要对其进行优化【习题】【染色问题】 给定一张无向图，要求对图进行染色，有边相连的点不能染同一种颜色。求最少需要几种颜色可以染完。递归1.写一个方法，输入任意一个整数，返回它的阶乘6 2 * x: X& y4 M7 uJava code % Q3 W3 v7 t0 d6 1 f; R /*& I4 e. $ j. Q- | *获得任意一个整数的阶乘 *param n4 y7 W/ * _; m5 m2 s) ) E+ ?- ( C *returnn! f ?, E1 2 4 $ _# D* 7 x */8 ! k3 s2 | w) V- H public int factorial(int num)1 R d; p* W1 q, c/ w1 J+ s . O7 J4 g1 z- s /递归2 A. R( z- n& z if(num = 1)+ 6 T7 w8 G0 i+ p 8 r U7 D p0 - g+ _ return 1;! c Q0 x& K1 L: T) s % K6 t3 w9 z) ?# h return num*factorial(num-1); ( w8 i! |$ S: f+ Q+ K6 . Pt2. 2.写一个方法，用二分查找法判断任意整数在任意整数数组里面是否存在，若存在就返回它在数组中的索引位置，不存在返回-1* *二分查找特定整数在整型数组中的位置(递归)?8 e. J+ j0 R4 t) G6 Y *param dataset *param data *param beginIndexR R9 M4 f7 r6 S8 Q8 D( f3 o *param endIndex7 p; N5 x$ t) Z8 k *return index */ l) W7 L% r$ E, B, k& b4 | public int binarySearch(int dataset,int data,int beginIndex,int endIndex) int midIndex = (beginIndex+endIndex)/2; /如果查找的数要比开始索引的数据要小或者是比结束索引的书要大，或者开始查找的索引值大于结束的索引值返回-1没有查到& ; C0 V# i1 q$ _# k if(data datasetendIndex|beginIndexendIndex) return -1; if(data datasetmidIndex) S9 K# J. |6 w& e: z+ o return binarySearch(dataset,data,midIndex+1,endIndex); else w& h! + - J+ D4 # l9 a return midIndex;+ e1 3 Y; n3 z* & Gd E9 g ( I1 I1 N4 n: 8 r; v. o- h+ w * P2 q1 h4 B% u3 c8 H /* *二分查找特定整数在整型数组中的位置(非递归)K- i, a8 D- *param dataset, I6 ?$ X4 N V2 S/ Y *param data! U# t+ ?( $ m R0 ibq# 3 b *return index */, M# O5 h6 k9 b public int binarySearch(int dataset ,int data)1 Z* d8 w# W2 4 P+ g int beginIndex = 0;/ E& j9 + p# X int endIndex = dataset.length - 1;6 bz* 1 O/ x# b int midIndex = -1; if(data datasetendIndex|begin