Go语言视频零基础入门到精通

javalearner

1. [b]
2. 直接插入排序：依次将每个记录插入到一个有序的子序列中。[/b]
3. 
   
4. 直接插入排序属于稳定的排序，时间复杂性为[img]http://img.javaxxz.com/2014/10/28/235737781.gif[/img]，空间复杂度为O(1)。
5. 
   
6. 直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。
7. 内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与
8. 它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数
9. 值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将
10. 待比较数值置入其后一位置，结束该次循环。值得注意的是，我们必需用一
11. 个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待
12. 比较数值置入比它小的数值的后一位。我刚开始做时，就因为没有特地声明
13. 一个空间出了错，用了很长时间才发现这个问题。
14. 
    
15.                     

复制代码

  

  


   程序代码
  
  
  package junesky.org.sort;

/**
* @author hiswing
* <p>
* <b>explain:<b>直接插入排序
* 每步将一个待排序的记录按其关键字大小，
* 插到前面已经排序的序列中适当位置，
* 直到全部记录插入完毕为止。
* @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;
// 前一个值
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("
");
}
}
       public static void main(String args[]){
      int a[];
      a=new int[10];
      Random random = new Random();
      for(int i = 0; i < 10; i++)
        a=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>
  

  
  
   
   

     
   

     
   
  



源码下载：http://file.javaxxz.com/2014/10/28/235737843.zip