讨厌算法的程序员 插入排序知识分享 光环大数据
什么是算法
在说插入排序之前，我们了解下《算法导论》对算法的从两种不同角度的定义。
一般性解释：
算法是定义良好的计算过程，它取一个或一组值作为输入，并产生出一个或一组值作为输出。
基于应用的解释：
算法是一种工具，用来解决一个具有良好规格说明的计算问题。该问题的描述可以用通用的语言，来规定所需的输入/输出关系。与之对应的算法则描述了一个特定的计算过程，用于实现这一输入/输出关系。
后一种解释在告诉我们，我们不必对于每个问题都去重新设计、证明和实现算法，而是有能力将实际问题转换成已知算法问题，然后选取合适的解法。而这种能力就是学习算法的目的所在。这要求我们不仅要积累算法知识，还要在更高的抽象层次上理解算法的方法论。
排序问题的形式定义
排序问题是算法要解决的一个基本问题。它的形式化定义如下：
输入：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
原著中的伪码无可挑剔，就沿用了。做一些说明：
-
算法名称INSERT-SORT；
-
A是一个长度为n的要排序的数组，用A.length表示n；
-
把待排序数组A逻辑上分为两个数组，排好序的（手中的牌），未排序的（桌上待摸的牌）；
-
排好序的数组起始只有一个元素，就是原数组A的第一个元素（摸出的第一张牌无需排序），循环变量用i表示；
-
未排序的数组起始，从原数组A的第二个元素一直到最后一个元素，所以外层的遍历是“2 to A.length”，循环变量用j表示；
-
外层遍历过程中，每个当前元素A[j]都暂存至key变量中；
-
key要加入排序好的数组，会从该排序好数组的最末i(j-1)开始进行比较，如果A[i]大于key，A[i]移动到A[i+1]，i自减，继续与key比较，如果此时i ≤ 0 或者 A[i] ≤ key，循环条件不成立跳出，将key存入A[i+1]。
算法工作例子
插入算法如何工作
说明：
-
(a)~(e)是循环迭代，(f)是最终排好的数组；
-
数组上方是数组的下标；
-
黑色块表示每次外层迭代，待插入左侧数组的数A[j]；
-
灰色块表示参与和A[j]比较的数；
-
黄色箭头是伪码第6行表达的移动；
-
蓝色大箭头是伪码第8行表达的移动；
Java实现
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下载。
大数据分析、大数据分析师的培训，大数据分析培训哪家好，大数据分析培训就业，就选光环大数据！
大数据培训、人工智能培训、Python培训、大数据培训机构、大数据培训班、数据分析培训、大数据可视化培训，就选光环大数据！光环大数据，聘请专业的大数据领域知名讲师，确保教学的整体质量与教学水准。讲师团及时掌握时代潮流技术，将前沿技能融入教学中，确保学生所学知识顺应时代所需。通过深入浅出、通俗易懂的教学方式，指导学生更快的掌握技能知识，成就上万个高薪就业学子。 更多问题咨询，欢迎点击------>>>>在线客服！
