写排序方法之前还是先介绍一下排序相关的概念：
排序：将任一资源（内存中的数据或文件等等）通过某种方式整理成 按关键字 有序排列的过程 叫排序。
排序的稳定性： 对序列中的两个或两个以上的相等的数据（Ri = Rj ， i != j）, 排序前 Ri 先于 Rj ， 排序后Ri 仍然先于 Rj ，则称该排序是稳定的。否则称为该排序是不稳定的。
比较算法的评判标准： 时间复杂度、控件复杂度、算法的稳定性。
排序的分类：
1、内部排序： 所有数据元素都加载到内存中。
2、外部排序：待排序数据元素太多，无法全部加载到内存中，排序过程中必须在内、外存之间进行数据交换 。
直接插入排序：
直接插入排序的思想是，对于待排序元素集合 Rs={R1，R2 ， ... Rn} , 将集合划分为已排好序的Rs1={R1,R2, ... Ri-1} ，和Rs2={Ri ，Ri+1， ... Rn} ,即将进行排序的元素Ri，插入到已经排好序的序列Rs1中，直到所有的元素都插入完为止。显然，R1是有序的。下面给一个序列Rs={37 , 40 , 38 , 42 , 461 , 5 , 7 , 9 , 12}，
| 初始序列 | 37 | 40 | 38 | 42 | 461 | 5 | 7 | 9 | 12 |
| 第一趟排序结果 | {37 | 40} | |||||||
| 第二趟排序结果 | {37 | 38 | 40} | ||||||
| 第三趟排序结果 | {37 | 38 | 40 | 42} | |||||
| 第四趟排序结果 | {37 | 38 | 40 | 42 | 461} | ||||
| 第五趟排序结果 | {5 | 37 | 38 | 40 | 42 | 461} | |||
| 第六趟排序结果 | {5 | 7 | 37 | 38 | 40 | 42 | 461} | ||
| 第七趟排序结果 | {5 | 7 | 9 | 37 | 38 | 40 | 42 | 461} | |
| 第八趟排序结果 | {5 | 7 | 9 | 12 | 37 | 38 | 40 | 42 | 461} |
以下为该算法的Java实现版：
public static void insertSort(int[] collection) {
if (null == collection || collection.length == 0)
return;
int temp, j;
for (int i = 1; i < collection.length; i++) {
temp = collection[i];
j = i - 1;
while (j >= 0 && temp < collection[j]) {
collection[j + 1] = collection[j];
j--;
}
collection[j + 1] = temp;
}
}
该方法使用一个额外空间存储当前待插入的元素，空间复杂度为O(N)，而每次插入元素都有可能移动一排好序的元素，其时间复杂度为O(n^2).
二分插入排序是在查找插入位置时使用二分搜索算法，减少关键字的比较次数，但是却不能减少数据元素移动的次数。关于二分查找方法请参见另一篇文章二分查找 ， 二分插入排序的一个Java实现版本：
public static void binInsertSort(int[] collection) {
if (null == collection || collection.length == 0)
return;
int temp, j, l, h, m;
for (int i = 1; i < collection.length; i++) {
l = 0;
h = i ;
m = -1;
temp = collection[i];
while (l < h) {
m = (l + h) >> 1;
if (temp > collection[m]) {
l = m +1;
} else {
h = m -1;
}
}
j = i - 1;
if (m != -1) {
while (j >= m && temp < collection[j]) {
collection[j + 1] = collection[j];
j--;
}
}
collection[j+1] = temp;
}
}
直接插入排序就写到这里。