《算法基础:打开算法之门》一3.3 插入排序
本节书摘来自华章出版社《算法基础:打开算法之门》一书中的第3章,第3.3节,作者 [美]托马斯 H 科尔曼(Thomas H Cormen),更多章节内容可以访问云栖社区“华章计算机”公众号查看
3.3 插入排序
尽管插入排序和选择排序有些相似,但它们还是有点不同。在选择排序中,当我们决定要把哪本书放在第i个位置上时,35当下前i个位置的书是书架中所有书按照作者姓名排序的前i本书。插入排序中,前i个位置的书仍然是初始时刻在前i个位置的书,但现在是按照作者名字顺序对这i本书进行了重排操作。
例如,假设放在前4个位置的书已经按照作者名字排好序了,并且按照顺序,它们分别是Charles Dickens、Herman Melville、Jonathan Swift和Leo Tolstoy所写的书。现在第5个位置处的书是Sir Walter S