算法导论学习
之前的算法学习更多的是为面试准备，具有很强的目的性。现在的出发点是进一步理解和掌握基本的算法，并静下心来领会算法中思考和解决问题的方式，书中复杂度部分的学习暂时略过。
主要学习资料：算法导论 第三版
代码地址：Github
算法基础
算法是解决问题的步骤
插入排序
《算法导论》中对插入排序举了一个非常恰当的列子：大家斗地主时，边摸牌边对手中的牌排序，这实际上就是一个插入排序的过程，保证手中的牌始终是有序的。
将如我们要对数组[1,3,7,-1,11,2,23,0,1]排序，要求结果为升序，用插入排序的写法如下：
public static void myInsertSort(int[] sequence) {
for (int j = 1; j < sequence.length; j++) {
int i = 0;
int temp = sequence[j];
while (i < j && sequence[i] < temp) {
i++;
}
for (int k = j; k > i; k--) {
sequence[k] = sequence[k - 1];
}
sequence[i] = temp;
}
}
我的做法是从前往后找插入位置，而书中的做法是从后往前找，其写法如下：
public static void bookInsertSort(int[] sequence) {
for (int j = 1; j < sequence.length; j++) {
int temp = sequence[j];
int i = j - 1;
while (i > 0 && sequence[i] > temp) {
sequence[i + 1] = sequence[i];
i--;
}
sequence[i + 1] = temp;
}
}
两者时间性能差别不大，书上的写法显得更加简洁。
分治策略
分治策略(Divide and Conquer)寻求的是递归的求解子问题，把规模大的问题分解成规模更小的问题去解决，在每个递归中有如下三个步骤：
- 分解(Divide)：将问题划分为规模更小的子问题，问题的本质与原问题一致
- 解决(Conquer)：递归的求解出子问题，如果子问题的规模已经足够小，则停止递归，求解并返回具体值
- 合并(Combine)：步骤将子问题的解组合成原问题的解
分治的方法往往可以用递归式子来表示，能写出递归式，问题基本就已经解决了，剩下的就是敲出代码，比如Merge Sort的递归式如下：
T(n)=O(1) (n=1)
T(n)=2T(n/2)+O(n) (n>1)
求解可得T(n)=O(nlgn)，即为归并排序的时间复杂度
最大连续子数组和
问题描述：
求数组{13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7}的和最大的最大连续子数组。
解法一：暴力搜索
private static void violentSearch(int[] array) {
int maxSum = 0;
for (int i = 0; i < array.length; i++) {
int temp = 0;
for (int j = i; j < array.length; j++) {
temp += array[j];
if (temp > maxSum) {
maxSum = temp;
}
}
}
System.out.println("maxSum:" + maxSum);
}
输出结果是43，很明显这是一种时间复杂度较高的做法。
解法二：分治策略
运用分治策略的话，我们可以把数组中分，然后问题变为，求左子数组的最大连续和，右子数组的最大连续和，以及跨越中分点的最大连续后，然后求出三者中的最大值。
private static int divideAndConquer(int[] array, int start, int end) {
if (start == end) {
return array[start];
} else {
int mid = (start + end) / 2;
int max_right = divideAndConquer(array, mid + 1, end);
int max_left = max_right;
if (start < mid - 1) {
max_left = divideAndConquer(array, start, mid - 1);
}
int max_mid = findMaxCrossingMid(array, start, mid, end);
if (max_left < max_right) {
max_left = max_right;
}
if (max_left < max_mid) {
max_left = max_mid;
}
return max_left;
}
}
private static int findMaxCrossingMid(int[] array, int start, int mid, int end) {
int result = array[mid];
int left = findMaxBackward(array, mid - 1, start);
int right = findMaxForward(array, mid + 1, end);
if (left > 0) {
result += left;
}
if (right > 0) {
result += right;
}
return result;
}
private static int findMaxForward(int[] array, int start, int end) {
if (start > end) {
return 0;
}
int sum = array[start];
int max = array[start];
for (int i = start + 1; i <= end; i++) {
sum += array[i];
if (sum > max) {
max = sum;
}
}
return max;
}
private static int findMaxBackward(int[] array, int start, int end) {
if (start < end) {
return 0;
}
int sum = array[start];
int max = array[start];
for (int i = start - 1; i >= end; i--) {
sum += array[i];
if (sum > max) {
max = sum;
}
}
return max;
}
结果为43，与书上不同，这里我专门写了findMaxForward()和findMaxBackWard()两个小方法，虽然导致代码较长，但我个人认为这样的写法更加清晰，出了问题好发现。