本文来自http://blog.csdn.net/liuxian13183/ ，引用必须注明出处！
从小白晋升，一路走来；从helloworld，到JFrame，再到Android；从城外小子，到内城的阶梯，站在高耸入云的阶梯上向前望；从迷茫的时代，到苦逼的时代，再到自信的时代；这些路有些艰难，有些坎坷，但--还算顺利；有过困惑，有过烦恼，有过委屈，但一路向前，风雨无阻；前言是遥远的，前方是未知的，前方是广阔的，前方是美好的；我要呼吁广大IT同胞们，让我们向着更遥远、更广阔、更美好的充满未知的未来出发吧！去贪婪的吮吸每一滴“蜜露”，用知识的精髓武装自己，斗志昂扬一如既往的用兴趣开路，去探寻属于自己的一片天地！
今天冒昧给大家讲讲算法的故事。
在从简单的逻辑写起，从完成一个控件、多个控件，走了一条线程、一条进程；到完成一个模块、若干模块，实现界面之间的交互、控件自定义；再到缓存、数据库、网络交互，内存管理、系统调优、架构扩展；最后又回归逻辑、研究算法，研究层与层之间的调用、依赖，抽象、继承、接口、反射等一些基础的概念；简而言之，把最简单的东西做到极致，那牛逼了！
百度解释：算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。）
接下来依次讲几个算法，冒泡、选择……
冒泡算法原理：两个两个的比较，其中较大的与较小的换位，每次都能排出剩下数中的最大数，放剩下数的最后；最终排出整齐的数列。
时间复杂度:倒序最大,Cmax=n*(n-1)/2,为T(n^2)；正序最小，Cmin=n,为T（n）；按实际情况来算。
空间复杂度为：最坏情况，每两个就要换一回，则为n/2+(n-1)/2+……+2/2=n(n+1)/4，Omax=O(n^2)；最好情况，已排好，则为O(0)。
代码如下：
public void testBubbleSort() {
int[] sortArray = { 4, 7, 9, 3, 6, 8,11 };
for (int i = 0; i < sortArray.length-1 ; i++) {
boolean isSort = false;
for (int j = 0; j < sortArray.length -1-i; j++) {
if (sortArray[j] > sortArray[j + 1]) {
int temp = sortArray[j];
sortArray[j] = sortArray[j + 1];
sortArray[j + 1] = temp;
isSort = true;
}
}
if (!isSort)
break;
}
System.out.println(Arrays.toString(sortArray));
}
选择排序原理：第一次，首个与后面的进行比较，把最小的放首位；第二次，次个与后面的进行比较，把次小的放次位；依次进行。
与冒泡的区别在于：选择排序找出最小的下标，然后与此次开始位置数字置换，冒泡需要两个两个的换位置；从这个意义上来说，选择排序占用内存更少，拥有更小的空间复杂度。
时间复杂度：最坏情况，n(n+1)/2，为Tmax=T(n^2)；最好情况，已排好，则为T(n)。
空间复杂度；最坏情况为O(n)，最好为O(0)，分别为正好相反或已排好。
代码如下：
public void testChooseSort() {
int min;
for (int i = 0; i < sortArray.length - 1; i++) {
min = i;
for (int j = i + 1; j < sortArray.length - 1 - i; j++) {
if (sortArray[min] > sortArray[j]) {
min = j;
}
}
if(min!=i){
int temp=sortArray[min];
sortArray[min]=sortArray[i];
sortArray[i]=temp;
}
}
System.out.println(Arrays.toString(sortArray));
}
快速排序：从第2个开始，如果第2个比第1个大，则两者交换；第3个，放在前2个已经排序的队列中，合适的位置；第4个放在前3个已经排序的队列中，合适的位置；继续，最终直接排出有顺序的队列。
构建队列，计算二叉树叶子值的和
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
/**
* 1 2 3 4 5 6 7
*
* @param root
* @return
*/
public static void buildTree(TreeNode root) {
if (root.val >= 4) {
return;
}
TreeNode left = new TreeNode(root.val + 1);
TreeNode right = new TreeNode(root.val + 2);
root.left = left;
root.right = right;
buildTree(root.left);
buildTree(root.right);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
buildTree(root);
int sum = 0;
System.out.println(sumTree(root, sum));
}
public static int sumTree(TreeNode root, int sum) {
if (root == null)
return sum;
sum += root.val;
sum = sumTree(root.left, sum);
sum = sumTree(root.right, sum);
return sum;
}
贪心算法：
1、给分数不同的小朋友分糖果
2、旁边分数高的要比分数低的分的多
3、求最少糖果数
public static int candy(int[] ratings) {
if (ratings == null || ratings.length == 0)
return 0;
int[] candies = new int[ratings.length];
for (int i = 0, size = ratings.length; i < size; i++) {
if (i == 0) {
candies[i] = 1;
continue;
}
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
} else {
candies[i] = 1;
}
}
int sum = candies[ratings.length - 1];
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
sum += candies[i];
}
return sum;
}
public static void main(String[] args) {
int[] candy = new int[] { 4, 2, 3, 4, 1 };
System.out.println(candy(candy));
}
拓展学习：Java科普之加密算法
