月份：2016年9月

public static void quickSort(int[] array, int start, int end) {
	if (start < end) {
		int middle = getMiddle(array, start, end);
		quickSort(array, 0, middle - 1);
		quickSort(array, middle + 1, end);
	}
}

private static int getMiddle(int[] array, int start, int end) {
	int baseVal = array[start];
	while (start < end) {
		while (start < end && array[end] >= baseVal) {
			end--;
		}
		array[start] = array[end];
		while (start < end && array[end] <= baseVal) {
			start++;
		}
		array[end] = array[start];
	}
	array[start] = baseVal;
	return start;
}

递归方法：

public static int search(int[] array, int start, int end, int val) {
	int mid = (end + start) / 2;
	if (array[mid] == val) {
		return mid;
	}
	if (array[mid] > val) {
		end = mid - 1;
	}
	if (array[mid] < val) {
		start = mid + 1;
	}
	int r = search(array, start, end, val);
	if (r >= 0) {
		return r;
	}
	return -1;
}

非递归：

public static int search2(int[] array, int val) {
	int start = 0;
	int end = array.length - 1;
	while (end >= start) {
		int mid = (end + start) / 2;
		if (array[mid] == val) {
			return mid;
		}
		if (array[mid] > val) {
			end = mid - 1;
		}
		if (array[mid] < val) {
			start = mid + 1;
		}
	}
	return -1;
}

装货问题
隔壁老王开着顺丰的标配货车（限载5吨，含5吨，不考虑限高）,想要一次性拿走尽可能重的货物，这些货有红木沙发，有钢材等等。

货物编号   货物重量(单位:kg)
1         509
2         838
3         924
4         650
5         604
6         793
7         564
8         651
9         697
10        649
11        747
12        787
13        701
14        605
15        644

背包算法递归定义最优解的方程式:

大概解释一下:
i 代表第几个货物，j表示当前容量，w(i)表示第i个货物的重量，v(i)表示第i个货物的价值，m(i,j)表示第i个货物,容量为j的最优解
转态转移的时候有两种情况：
1.可以装下一个 j>= w(i)，这种情况可以装入这个物品，比较装入后和没有装入的最优解，决定是否装入
2.不可以装下一个 0<=j<=w(i), 这种情况不能装入这个物品，最优解不变

代码实现：

public static int knapsack(int val[], int wt[], int W) {
	int N = wt.length;
	
        //构造一个二维数组
	int[][] V = new int[N + 1][W + 1];
        //初始化数组数据
	for (int col = 0; col <= W; col++) {
		V[0][col] = 0;
	}
         
	for (int row = 0; row <= N; row++) {
		V[row][0] = 0;
	}

	for (int item = 1; item <= N; item++) {
		for (int weight = 1; weight <= W; weight++) {
			if (wt[item - 1] <= weight) {
                //可以装入
				V[item][weight] = Math.max(val[item - 1] + V[item - 1][weight - wt[item - 1]], V[item - 1][weight]);
			} else {
                //不能装入
				V[item][weight] = V[item - 1][weight];
			}
		}

	}

	// 计算选择结果
	int j = W;
	int length = N;
	StringBuilder stringBuilder = new StringBuilder();
	for (int i = length; i > 0; --i) {
		//转态转移的时候记录
		if (V[i][j] > V[i - 1][j]) {
			stringBuilder.append(i).append("-");
			j = j - wt[i-1];
		}
	}
	String result = stringBuilder.toString();
	System.out.println("选择的序号 : " + result.substring(0, result.length()-1));
	
	//打印表
	for (int[] rows : V) {
	      for (int col : rows) {
		System.out.format("%5d", col);
	       }
	      System.out.println();
	}

	return V[N][W];
}