Java求职面试准备之常见算法

  1 package carl;
  2 
  3 import org.junit.Test;
  4 
  5 /**
  6  * 本类中总结了常用的几种算法
  7  * @author Administrator
  8  *
  9  */
 10 public class TestAlgorithms {
 11 
 12     /**
 13      * 插入排序
 14      * 插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小
 15      * 插入前面已经排序的文件中适当位置上，直到全部插入完为止。
 16      * @param list
 17      * @return
 18      */
 19     public void insertSort(int[] list){
 20         for(int i=1;i<list.length;i++){
 21             int tmp = list[i];
 22             int j=i-1;
 23             for(; j>=0 && list[j] >tmp; j--){
 24                 list[j+1]=list[j];
 25             }
 26             list[j+1]=tmp;
 27         }
 28         
 29     }
 30     
 31     
 32      /**
 33       * 希尔排序:dk为1的时候就是插入排序
 34       * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
 35       * 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
 36       * @param list
 37       * @param start
 38       * @param dk
 39       */
 40     public void shellInsert(int[] list, int start, int dk) {
 41         int i,j;
 42         for(i = start+dk; i < list.length;  i = i + dk){
 43             j = i-dk;
 44             int tmp = list[i];
 45             
 46             for (;j >= 0 && list[j] > tmp;j -= dk) {
 47                 list[j + dk] = list[j];
 48             }
 49             list[j + dk] = tmp;
 50         }
 51         
 52      }
 53     
 54     
 55      /**
 56       * 冒泡排序
 57       * 它重复地走访过要排序的数列，一次比较两个元素，
 58       * 如果他们的顺序错误就把他们交换过来。走访数列的工作是
 59       * 重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
 60       * 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。
 61       * @param list
 62       */
 63     public void bubbleSort(int[] list) {
 64         for (int i = 0; i < list.length; i++) {
 65             for (int j = 0; j < list.length - i - 1; j++) {
 66                 if (list[j] > list[j + 1]) {
 67                  int temp = list[j];
 68                  list[j] = list[j + 1];
 69                  list[j + 1] = temp;
 70                 }
 71             }
 72         }
 73      }
 74     
 75      // 字符串反转
 76      public String reverse(String str) {
 77          String str1 = "";
 78          for (int i = str.length(); i > 0; i--) {
 79              str1 += str.substring(i - 1, i);
 80          }
 81           return str1;
 82      }
 83      
 84      /**
 85       * 编码实现字符串转整型的函数（实现函数atoi的功能）。
 86       * 如将字符串”+123”->123, ”-0123”->-123,“123CS45”->123,“123.45CS”->123, “CS123.45”->0
 87       * @param str1
 88       * @return
 89       */
 90     public int str2Int(String str1) {
 91       char[] str = str1.toCharArray();
 92       int i = 0, sign = 1, value = 0;
 93       if (str != null && str[0] > ‘9‘ && str[0] < ‘0‘) {
 94        value = 0; // 如果第一个元素为字母，直接赋值零
 95       } else {
 96        if (str != null && str[0] == ‘-‘ || str[0] == ‘+‘) {
 97         // 判断是否存在符号位
 98         i = 1;
 99         sign = (str[0] == ‘-‘ ? -1 : 1);
100        }
101        for (; str[i] >= ‘0‘ && str[i] <= ‘9‘; i++)
102         value = value * 10 + (str[i] - ‘0‘);
103       }
104       return sign * value;
105      }
106     
107     /**
108      * 根据字节对字符串拆分，要注意若是GBK编码，则中文字符占用两个字节
109      * 如“123我是谁”，拆分4个字节，程序要求的结果为“123我”，而不是“123?”
110      * @param str
111      */
112     public String splitChinese(String str,int index){
113         String tmp = "";
114         for(int i=1;i<=str.length();i++){
115             tmp = str.substring(0, i);
116             if(tmp.getBytes().length >= index){
117                 return tmp;
118             }
119         }
120         System.out.println(tmp.getBytes().length);
121         
122         return "";
123     }
124     
125 }

 1 package carl;
 2 
 3 import java.io.UnsupportedEncodingException;
 4 
 5 import org.junit.Test;
 6 
 7 public class JunitTestAlgorithms {
 8     TestAlgorithms ta = new TestAlgorithms();
 9     
10     public void pintList(int[] target){
11         int len = target.length;
12         System.out.println("length:"+len);
13         for(int i = 0; i < len; i++){
14             System.out.print(target[i]+ (i==(len-1)?"":","));
15         }    
16     }
17     
18     @Test
19     public void insertSortTest(){
20         int[] list = {1,2,3,4,7,5,6,10,22};
21         ta.insertSort(list);
22         System.out.println("\n------------insertSortTest-----------");
23         this.pintList(list);            
24     }
25     
26     @Test
27     public void shellInsertTest(){
28         int[] list = {1,2,3,4,7,5,6,10,22};
29         int i = 0, w = 2;
30         while (i < w) {
31            ta.shellInsert(list, i, w);
32            i++;
33         }
34         ta.shellInsert(list, 0, 1);
35         System.out.println("\n-----------shellInsertTest-----------");
36         this.pintList(list);
37     }
38     
39     @Test
40     public void bubbleSortTest(){
41         int[] list = {1,2,3,4,7,5,6,10,22};
42         ta.bubbleSort(list);
43         System.out.println("\n------------bubbleSortTest---------");
44         this.pintList(list);
45     }
46     
47     @Test
48     public void reverseTest(){
49         String str = "abcdefg";
50         String tmp = ta.reverse(str);
51         System.out.println("\n----------reverseTest------------");
52         System.out.println(tmp);
53     }
54     
55     @Test
56     public void str2IntTest(){
57         int str2Int = ta.str2Int("-123.4CS4546");
58         System.out.println("\n----------str2IntTest------------");
59         System.out.println(str2Int);
60     }
61     
62     @Test
63     public void splitChineseTest(){
64         String str="123我是谁";
65         System.out.println("\n----------splitChineseTest------------");
66         try {
67             //因为我的java文件编码是GBK，所以getBytes()默认的编码是GBK
68             System.out.println("\"123我是谁\".getBytes(\"GBK\").length:"+str.getBytes("GBK").length);
69             System.out.println("\"123我是谁\".getBytes().length:"+str.getBytes().length);
70         } catch (UnsupportedEncodingException e) {
71             e.printStackTrace();
72         }
73         String resultStr = ta.splitChinese(str,4);
74         System.out.println(resultStr);
75     }
76     
77 
78 
79 }