算法学习之算法导论理解

算法是学习程序开发必不可少的一环。我们不仅仅能去用好，而且更重要的是理解，变成自己的东西才是根本。

算法导论 第2章 算法基础

2.1 插入排序

概念：插入排序是将一个数据插入到一个已经排好序的有序数据中.简单来说就是带排序的数据插入有序数据中。 时间复杂度：O(n^2)

伪代码： 按照伪代码提示， 1.for循环从数据A的第二个元素开始到数据长度最后一个元素截止 2.把数组j位置对应的值赋值给中间变量key 3.// 4.把变量j-1赋给变量i(i就是j的前一个变数) 5.while 循环 条件：如果i>0并且A[i]>key 执行{ 6. A[i+1]=A[i]；//把i+1 对应位置的值替换为A[i] 7. i–;//i自减 } 8. A[i+1]=key//把i+1位置对应值替换为key值

如果按照伪代码直接用永远得不到正确答案 为什么呢？ 我们都知道数组元素的下标为最小为0，所以代码需要改成如下：

for (int j = 1; j < A.length; j++) { String key = A[j]; int i = j-1; while (i>-1&&Integer.valueOf(A[i])>Integer.valueOf(key)){ A[i+1] = A[i]; i--; } A[i+1] = key; }

大家可能疑惑 while在此处有什么作用？

while作用就是如果条件成立 i+1对应着替换为i当前值 i自减直到i=-1时退出while循环 然后剩下的第i+1位值替换为key 简单讲就是值移位加排序。