for i = 2:n, for (k = i; k > 1 and a[k] < a[k-1]; k--) swap a[k,k-1] → invariant: a[1..i] is sorted end
虽然这是最坏情况下时间为O(n2)的一个基本的排序算法,但是当数据是属于接近排序完的(因为它是自适应)或当问题规模小(因为它有低开销)的时候, 插入排序是合适的算法选择。
由于这些原因并且因为它也是稳定的,插入排序是常被用在递归基础案例(当问题规模小)开销较大的时候、分而治之的排序算法,如归并排序、快速排序。
Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.
Programming Pearls by Jon Bentley. Addison Wesley, 1986.
Quicksort is Optimal by Robert Sedgewick and Jon Bentley, Knuthfest, Stanford University, January, 2002.
Dual Pivot Quicksort: Code and Discussion.
Bubble-sort with Hungarian ("Csángó") folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.
Select-sort with Gypsy folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.
Sorting Out Sorting, Ronald M. Baecker with the assistance of David Sherman, 30 minute color sound film, Dynamic Graphics Project, University of Toronto, 1981. Excerpted and reprinted in SIGGRAPH Video Review 7, 1983. Distributed by Morgan Kaufmann, Publishers. Excerpt.