一般直接插入排序的时间复杂度为O ( n^2 ) ，但是当数列基本有序时，如果按照有数列顺序排时，时间复杂度将改善到O( n )，另外，因直接插入排序算法简单，如果待排序列规模不很大时效率也较高。
在已经排好序的序列中查找待插入的元素的插入位置，并将待插入元素插入到有序列表中的过程。
将数组分成两部分，初始化时，前部分数组为只有第一个元素，用来存储已排序元素，我们这里叫 arr1 ；后部分数组的元素为除第一个元素的所有元素，为待排序或待插入元素，我们这里叫 arr2 。
排序时使用二层循环：第一层对 arr2 进行循环，每次取后部分数组（待排序数组）里的第一个元素（我们称为待排序元素或称待插入元素） e1 ，然后在第二层循环中对 arr1 （已排好序的数组）从第一个元素往后进行循环，查到第一个大于待插入元素（如果是升序排列）或第一个小于待插入元素（如果是降序排列） e2 ，然后对 arr1 从 e2 元素开始往后的所有元素向后移，最后把 e1 插入到原来 e2 所在的位置。这样反复地对 arr2 进行循环，直到 arr2 中所有的待插入的元素都插入到 arr1 中。
Java代码
1. package sort; 2.
3. import java.util.Comparator; 4. 5. /**
6. * 直接插入排序算法 7. * @author jzj 8. * @date 2009-12-5 9. *
10. * @param 11. */
12. public class InsertSort> extends Sort { 13. 14. /**
15. * 排序算法的实现，对数组中指定的元素进行排序 16. * @param array 待排序的数组 17. * @param from 从哪里开始排序 18. * @param end 排到哪里 19. * @param c 比较器 20. */
21. public void sort(E[] array, int from, int end, Comparator c) { 22. 23. /*
24. * 第一层循环：对待插入（排序）的元素进行循环
25. * 从待排序数组断的第二个元素开始循环，到最后一个元素（包括）
止
26. */
27. for (int i = from + 1; i <= end; i++) { 28. /*
29. * 第二层循环：对有序数组进行循环，且从有序数组最第一个元
素开始向后循环
30. * 找到第一个大于待插入的元素
31. * 有序数组初始元素只有一个，且为源数组的第一个元素，一个
元素数组总是有序的
32. */
33. for (int j = 0; j < i; j++) {
34. E insertedElem = array[i];//待插入到有序数组的元素 35. //从有序数组中最一个元素开始查找第一个大于待插入的元素 36. if (c.compare(array[j], insertedElem) > 0) {
37. //找到插入点后，从插入点开始向后所有元素后移一位 38. move(array, j, i - 1); 39. //将待排序元素插入到有序数组中 40. array[j] = insertedElem; 41. break; 42. } 43. } 44. } 45.
46. //=======以下是java.util.Arrays的插入排序算法的实现 47. /*
48. * 该算法看起来比较简洁一j点，有点像冒泡算法。
49. * 将数组逻辑上分成前后两个集合，前面的集合是已经排序好序的
元素，而后面集合为待排序的
50. * 集合，每次内层循从后面集合中拿出一个元素，通过冒泡的形式，
从前面集合最后一个元素开
51. * 始往前比较，如果发现前面元素大于后面元素，则交换，否则循
环退出
52. *
53. * 总感觉这种算术有点怪怪，既然是插入排序，应该是先找到插入
点，而后再将待排序的元素插
54. * 入到的插入点上，那么其他元素就必然向后移，感觉算法与排序
名称不匹，但返过来与上面实
55. * 现比，其实是一样的，只是上面先找插入点，待找到后一次性将
大的元素向后移，而该算法却
56. * 是走一步看一步，一步一步将待排序元素往前移 57. */ 58. /*
59. for (int i = from; i <= end; i++) {
60. for (int j = i; j > from && c.compare(array[j - 1], array[j]) > 0; j--) { 61. swap(array, j, j - 1);
62. } 63. } 64. */ 65. } 66. 67. /** 68. * 测试
69. * @param args 70. */
71. public static void main(String[] args) {
72. Integer[] intgArr = { 5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7 }; 73. InsertSort insertSort = new InsertSort(); 74. Sort.testSort(insertSort, intgArr); 75. Sort.testSort(insertSort, null); 76. } 77. } 78.
插入排序算法对于大数组，这种算法非常慢。但是对于小数组，它比其他算法快。其他算法因为待的数组元素很少，反而使得效率降低。在Java集合框架中，排序都是借助于java.util.Arrays来完成的，其中排序算法用到了插入排序、快速排序、归并排序。插入排序用于元素个数小于7的子数组排序，通常比插入排序快的其他排序方法，由于它们强大的算法是针对大数量数组设计的，所以元素个数少时速度反而慢。
希尔排序
希尔思想介绍
希尔算法的本质是缩小增量排序，是对直接插入排序算法的改进。一般直接插入排序的时间复杂度为O ( n^2 ) ，但是当数列基本有序时，如果按照有数列顺序排时，时间复杂度将改善到O( n )，另外,因直接插入排序算法简单,如果待排序列规模不很大时效率也较高，Shell 根据这两点分析结果进行了改进，将待排记
录序列以一定的增量间隔h 分割成多个子序列，对每个子序列分别进行一趟直接插入排序, 然后逐步减小分组的步长h ，对于每一个步长h 下的各个子序列进行同样方法的排序,直到步长为1 时再进行一次整体排序。
因为不管记录序列多么庞大,关键字多么混乱,在先前较大的分组步长h 下每个子序列的规模都不大，用直接插入排序效率都较高。 尽管在随后的步长h 递减分组中子序列越来越大，但由于整个序列的有序性也越来越明显，则排序效率依然较高。这种改进抓住了直接插入排序的两点本质，大大提高了它的时间效率。 希尔增量研究
综上所述：
(1) 希尔排序的核心是以某个增量h 为步长跳跃分组进行插入排序，由于分组的步长h 逐步缩小，所以也叫“缩小增量排序”插入排序。其关键是如何选取分组的步长序列ht ,. . . , hk ,. . . , h1 , h0 才能使得希尔方法的时间效率最高； (2) 待排序列记录的个数n 、跳跃分组步长逐步减小直到为1时所进行的扫描次数T、增量的和、记录关键字比较的次数以及记录移动的次数或各子序列中的反序数等因素都影响希尔算法的时间复杂度：其中记录关键字比较的次数是重要因素，它主要取决于分组步长序列的选择；
(3) 希尔方法是一种不稳定排序算法，因为其排序过程中各趟的步长不同，在第k 遍用hk作为步长排序之后，第k +1 遍排序时可能会遇到多个逆序存在，影响排序的稳定性。
试验结果表明,SHELL 算法的时间复杂度受增量序列的影响明显大于其他因素，选取恰当的增量序列能明显提高排序的时间效率，我们认为第k 趟排序扫描的增量步长为 2^k - 1 ,即增量序列为. . . 2^k - 1 ,. . . ,15 ,7 ,3 ,1时较为理想，但它并不是唯一的最佳增量序列，这与其关联函数目前尚无确定解的理论结果是一致的。