最近在求职面试，整理一下常见面试算法：
对TestAlgorithms.java中方法的测试见JunitTestAlgorithms.java(引入了junit4)
1.TestAlgorithms.java
package carl; import org.junit.Test; /**
* 本类中总结了常用的几种算法
* @author Administrator
*
*/
public class TestAlgorithms { /**
* 插入排序
* 插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小
* 插入前面已经排序的文件中适当位置上，直到全部插入完为止。
* @param list
* @return
*/
public void insertSort(int[] list){
for(int i=1;i<list.length;i++){
int tmp = list[i];
int j=i-1;
for(; j>=0 && list[j] >tmp; j--){
list[j+1]=list[j];
}
list[j+1]=tmp;
} } /**
* 希尔排序:dk为1的时候就是插入排序
* 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
* 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
* @param list
* @param start
* @param dk
*/
public void shellInsert(int[] list, int start, int dk) {
int i,j;
for(i = start+dk; i < list.length; i = i + dk){
j = i-dk;
int tmp = list[i]; for (;j >= 0 && list[j] > tmp;j -= dk) {
list[j + dk] = list[j];
}
list[j + dk] = tmp;
} } /**
* 冒泡排序
* 它重复地走访过要排序的数列，一次比较两个元素，
* 如果他们的顺序错误就把他们交换过来。走访数列的工作是
* 重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
* 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。
* @param list
*/
public void bubbleSort(int[] list) {
for (int i = 0; i < list.length; i++) {
for (int j = 0; j < list.length - i - 1; j++) {
if (list[j] > list[j + 1]) {
int temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
}
}
}
} // 字符串反转
public String reverse(String str) {
String str1 = "";
for (int i = str.length(); i > 0; i--) {
str1 += str.substring(i - 1, i);
}
return str1;
} /**
* 编码实现字符串转整型的函数（实现函数atoi的功能）。
* 如将字符串”+123”->123, ”-0123”->-123,“123CS45”->123,“123.45CS”->123, “CS123.45”->0
* @param str1
* @return
*/
public int str2Int(String str1) {
char[] str = str1.toCharArray();
int i = 0, sign = 1, value = 0;
if (str != null && str[0] > '9' && str[0] < '0') {
value = 0; // 如果第一个元素为字母，直接赋值零
} else {
if (str != null && str[0] == '-' || str[0] == '+') {
// 判断是否存在符号位
i = 1;
sign = (str[0] == '-' ? -1 : 1);
}
for (; str[i] >= '0' && str[i] <= '9'; i++)
value = value * 10 + (str[i] - '0');
}
return sign * value;
} /**
* 根据字节对字符串拆分，要注意若是GBK编码，则中文字符占用两个字节
* 如“123我是谁”，拆分4个字节，程序要求的结果为“123我”，而不是“123?”
* @param str
*/
public String splitChinese(String str,int index){
String tmp = "";
for(int i=1;i<=str.length();i++){
tmp = str.substring(0, i);
if(tmp.getBytes().length >= index){
return tmp;
}
}
System.out.println(tmp.getBytes().length); return "";
} }
2.JunitTestAlgorithms.java
package carl;
import java.io.UnsupportedEncodingException;
import org.junit.Test;
public class JunitTestAlgorithms {
TestAlgorithms ta = new TestAlgorithms();
public void pintList(int[] target){
int len = target.length;
System.out.println("length:"+len);
for(int i = 0; i < len; i++){
System.out.print(target[i]+ (i==(len-1)?"":","));
}
}
@Test
public void insertSortTest(){
int[] list = {1,2,3,4,7,5,6,10,22};
ta.insertSort(list);
System.out.println("\n------------insertSortTest-----------");
this.pintList(list);
}
@Test
public void shellInsertTest(){
int[] list = {1,2,3,4,7,5,6,10,22};
int i = 0, w = 2;
while (i < w) {
ta.shellInsert(list, i, w);
i++;
}
ta.shellInsert(list, 0, 1);
System.out.println("\n-----------shellInsertTest-----------");
this.pintList(list);
}
@Test
public void bubbleSortTest(){
int[] list = {1,2,3,4,7,5,6,10,22};
ta.bubbleSort(list);
System.out.println("\n------------bubbleSortTest---------");
this.pintList(list);
}
@Test
public void reverseTest(){
String str = "abcdefg";
String tmp = ta.reverse(str);
System.out.println("\n----------reverseTest------------");
System.out.println(tmp);
}
@Test
public void str2IntTest(){
int str2Int = ta.str2Int("-123.4CS4546");
System.out.println("\n----------str2IntTest------------");
System.out.println(str2Int);
}
@Test
public void splitChineseTest(){
String str="123我是谁";
System.out.println("\n----------splitChineseTest------------");
try {
//因为我的java文件编码是GBK，所以getBytes()默认的编码是GBK
System.out.println("\"123我是谁\".getBytes(\"GBK\").length:"+str.getBytes("GBK").length);
System.out.println("\"123我是谁\".getBytes().length:"+str.getBytes().length);
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
}
String resultStr = ta.splitChinese(str,4);
System.out.println(resultStr);
}
}
输出结果：
----------splitChineseTest------------
"123我是谁".getBytes("GBK").length:9
"123我是谁".getBytes().length:9
123我
------------insertSortTest-----------
length:9
1,2,3,4,5,6,7,10,22
----------str2IntTest------------
-123
-----------shellInsertTest-----------
length:9
1,2,3,4,5,6,7,10,22
----------reverseTest------------
gfedcba
------------bubbleSortTest---------
length:9
1,2,3,4,5,6,7,10,22