</td> </tr> </table>
直接插入排序：依次将每个记录插入到一个有序的子序列中。
直接插入排序属于稳定的排序，时间复杂性为，空间复杂度为O(1)。
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。
内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与
它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数
值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将
待比较数值置入其后一位置，结束该次循环。值得注意的是，我们必需用一
个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待
比较数值置入比它小的数值的后一位。我刚开始做时，就因为没有特地声明
一个空间出了错，用了很长时间才发现这个问题。
package junesky.org.sort;
/**
* @author hiswing
*
* explain:直接插入排序
* 每步将一个待排序的记录按其关键字大小，
* 插到前面已经排序的序列中适当位置，
* 直到全部记录插入完毕为止。
* @version 1.0 2006-1-4
*/
public class StraightSort implements Sort {
public void go(int[] r) {
// 从第2个开始比较
for (int i = 1; i < r.length; i++) {
// 用来存放比较值的空间
int c = r[i];
// 前一个值
int j = i - 1;
// 如果前一个值大于0并且大于比较的值
while (j >= 0 && r[j] > c) {
/* 这里值得注意：如果我们没有为待比较数值声明
存储空间，那个在做这一步时，会将待比较数值覆盖。*/
// 将后一个值变为前一个值
r[j + 1] = r[j];
// 向前移动继续比较
j--;
}
// 将当前值改为比较用的值
r[j + 1] = c;
// 打印每次排序后的顺序
for (int n = 0; n < r.length; n++) {
System.out.print(r[n] + ",");
}
System.out.print("\n");
}
}
public static void main(String args[]){
int a[];
a=new int[10];
Random random = new Random();
for(int i = 0; i < 10; i++)
a[i]=Math.abs(random.nextInt()) % 100;
StraightSort s=new StraightSort();
s.go(a);
}
}
下面是两次运行结果：
C:\java>java StraightSort
10,54,99,17,23,99,85,76,43,93,
10,54,99,17,23,99,85,76,43,93,
10,17,54,99,23,99,85,76,43,93,
10,17,23,54,99,99,85,76,43,93,
10,17,23,54,99,99,85,76,43,93,
10,17,23,54,85,99,99,76,43,93,
10,17,23,54,76,85,99,99,43,93,
10,17,23,43,54,76,85,99,99,93,
10,17,23,43,54,76,85,93,99,99,
C:\java>java StraightSort
66,72,55,57,42,13,14,68,41,95,
55,66,72,57,42,13,14,68,41,95,
55,57,66,72,42,13,14,68,41,95,
42,55,57,66,72,13,14,68,41,95,
13,42,55,57,66,72,14,68,41,95,
13,14,42,55,57,66,72,68,41,95,
13,14,42,55,57,66,68,72,41,95,
13,14,41,42,55,57,66,68,72,95,
13,14,41,42,55,57,66,68,72,95,
C:\java>
↑返回目录
前一篇: 对象克隆
后一篇: java中的String池