插入排序
基本思想：每次将一个待排序的元素，按其关键字的大小插入到前面已经排好序的子文件的适当位置，直到全部记录插入完成为止。
直接插入排序
直接插入排序的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
(直接)插入排序.gif
插入排序示例:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 状态 |
|---|---|---|---|---|---|---|---|---|
| 49 | 38 | 65 | 97 | 76 | 13 | 27 | 49' | 初始状态 |
| 38 | 49 | 65 | 97 | 76 | 13 | 27 | 49' | 第一趟 |
| 38 | 49 | 65 | 97 | 76 | 13 | 27 | 49' | 第二趟 |
| 38 | 49 | 65 | 97 | 76 | 13 | 27 | 49' | 第三趟 |
| 38 | 49 | 65 | 76 | 97 | 13 | 27 | 49' | 第四趟 |
| 13 | 38 | 49 | 65 | 76 | 97 | 27 | 49' | 第五趟 |
| 13 | 27 | 38 | 49 | 65 | 76 | 97 | 49' | 第六趟 |
| 13 | 27 | 38 | 49 | 49' | 65 | 76 | 97 | 第七趟 |
代码：
public static void main(String[] args) {
int[] s = { 49, 38, 65, 97, 76, 13, 27, 49 };
new InsertSort().insert_Sort(s);
for (int i = 0; i < s.length; i++) {
System.out.printf("%d ", s[i]);
}
}
void insert_Sort(int s[]) {
if (s.length < 2) {
System.out.println("数组长度小于2");
return;
}
for (int i = 1; i < s.length; i++) {
int temp = s[i];
for (int j = i - 1; j >= 0; j--) {
if (s[j] > temp) {
s[j + 1] = s[j];
} else {
s[j + 1] = temp;
break;
}
if (j == 0) {
s[0] = temp;
}
}
}
}
输出:
13 27 38 49 49 65 76 97
插入排序的效率分析
| 排序算法 | 平均时间性能 | 最好时间性能 | 最坏时间性能 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 |  |
 |
|
 |
稳定 |
首先从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。从时间分析，首先外层循环要进行n-1次插入, 每次插入最少比较一次 (正序), 移动0次;最多比较i次(s[0]的比较),移动i＋1次(逆序)(i=2,3,…,n)。
因此，直接插入排序的时间复杂度为：
