基础算法复习篇（一）——插入排序算法

经过一个假期对基础算法知识的学习，总算在近期告一段落，正好在刚开学的这一段冷却期，为了加深对算法的记忆与理解，准备对假期所学习的算法知识进行一定的总结与分析，算是对前一阶段所学知识的总结吧，也许在这期间还能发掘出当初没有想到的想法，算是很随性的总结吧，那么从今天开始，便由浅入深的对基本的算法进行一定的复习。

在这篇文章中将介绍一个非常简单的排序算法—插入排序算法（Insertionsort）。插入排序的算法的核心便在于原地排序。所谓原地排序指的是，在算法的运行过程中，在待排序对象的容器外仅仅有确定个数的对象。就像我们在桌子上放了一副扑克牌，我们想把每张牌按照牌上数字的大小按照非降序顺序排列之后堆叠在桌上，那么什么叫原地排序呢，我们把放牌堆的桌子认为是盛放牌的容器，我们的双手认为是牌堆之外的空间，我们在排序的过程中，每次仅仅在牌堆里面取得1张牌和牌堆里面的扑克牌进行比较后找到其应当所在的位置之后放回牌堆，然后再取下一张牌~~~如此反复，在算法的每一步在手中牌的数目是一定的，当然不一定非要是一张啦。这么做的好处便是能够有效的节省内存的占用，如果系统的内存资源紧张，这么做的意义是非常明显的。

那么我们首先对算法的具体步骤进行介绍，该算法的代码实现如下：

public class InsertionsortTest {
	/**
	 * 插入排序算法实现
	 * 
	 * @param tempNumbers 待排序数组
	 * @return
	 */
	public static int[] insertionSort(int[] tempNumbers){
		
		for(int index = 1; index < tempNumbers.length; index++){//从待排序数组第二个元素开始向前作比较
			int target = tempNumbers[index];//取得目标元素
			int targetIndex = index - 1;//待比较元素初始化位目标元素前一个
			
			while(targetIndex >= 0 && target < tempNumbers[targetIndex]){//当待比较元素未越界且待比较元素大于目标元素
				tempNumbers[targetIndex + 1] = tempNumbers[targetIndex];//将待比较元素向后移动一位
				targetIndex --;//把前一个元素作为下一个待比较元素
			}
			tempNumbers[targetIndex + 1] = target;//当待比较元素小于目标元素时，讲目标元素插入至待比较元素之后
		}
		
		return tempNumbers;//返回已排列好的数组
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] tempNumbers = {4,1,7,13,11,57,14,6,58};
		int[] targetNumbers = InsertionsortTest.insertionSort(tempNumbers);
		System.out.println(Arrays.toString(targetNumbers));

	}

}

算法的运行过程很简单，具体步骤的意义已经在注释中进行了解释，总体的运行过程就像给扑克排序一样，把元素容器的第二个元素开始的元素作为目标元素，把目标元素与之前的元素进行比较，把之前的元素作为待比较元素若待比较元素大于目标元素便把待比较元素后移一位，并把它原来的前一个元素作为新的待比较元素，直到待比较元素小于目标元素，便把目标元素插入至待比较元素之后。在算法的整个过程中在元素容器之外的元素只有一个当前的目标元素，因此这种排序方法是原地的，能够有效的节省内存的使用。

然而这种算法也有其缺点，那就是只适合小规模数据的排序，对于大规模数据的排序效率便不令人满意了，因为其时间复杂度是O（n2）级别的，既然是n方级别的，那么随着输入数据数量级的增长，其排序所需时间的增长过于巨大，效率不能令人满意。在处理小规模数据的过程中效率还是可观的，因此，有人的想法便是利用分治法将大规模的数据分解成小规模的数据集，进行排序之后再进行排序。

虽说算法的效率不算太高，不过毕竟是入门算法，而且实现简单，在平时数据量很小时还是能很好的解决问题的，至于比较高效的算法，实现复杂度也会相应的提高，那么我们应该在以后的文章中能够见到。