在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。
一般性解释:
算法是定义良好的计算过程,它取一个或一组值作为输入,并产生出一个或一组值作为输出。
基于应用的解释:
算法是一种工具,用来解决一个具有良好规格说明的计算问题。该问题的描述可以用通用的语言,来规定所需的输入/输出关系。与之对应的算法则描述了一个特定的计算过程,用于实现这一输入/输出关系。
后一种解释在告诉我们,我们不必对于每个问题都去重新设计、证明和实现算法,而是有能力将实际问题转换成已知算法问题,然后选取合适的解法。而这种能力就是学习算法的目的所在。这要求我们不仅要积累算法知识,还要在更高的抽象层次上理解算法的方法论。
排序问题是算法要解决的一个基本问题。它的形式化定义如下:
输入:n个数的一个序列[a1, a2, ..., an]。
输出:输出序列的一个排列[a1', a2', ..., an'], 满足a1' ≤ a2' ≤ ... ≤ an'。
插入排序算法,对于少量元素的排序问题,是一个有效的算法。
扑克
即便是玩过扑克牌的小孩子,其实都对插入排序算法了然于胸。
想让计算机听懂上述的算法,需要将其进行翻译。
INSERTION-SORT(A)
1 for j = 2 to A.length
2 key = A[j]
3 // Insert A[j] into the sorted sequence A[1..j-1].
4 i = j - 1
5 while i > 0 and A[i] > key
6 A[i + 1] = A[i]
7 i = i - 1
8 A[i + 1] = key
原著中的伪码无可挑剔,就沿用了。做一些说明:
插入算法如何工作
说明:
public class InsertionSort {
public static void sortInASC(int[] numbers){
for(int j = 1; j < numbers.length; j++){
int key = numbers[j];
int i = j - 1;
while(i >= 0 && numbers[i] > key){
numbers[i + 1] = numbers[i];
i = i - 1;
}
numbers[i + 1] = key;
}
}
}
InsertSort.java下载。