插入排序算法

插入排序是排序算法中一种经典的排序算法，该算法的时间复杂度最好时为O(n),最差时为O(n^2)，空间复杂度为O(1)，该算法也是一种稳定的排序算法。该种算法较适合大部分已有序时的排序问题。相比较而言，冒泡排序则更适合较小的序列排序。

该排序算法的思想是：不断地将当前数字插入到一个有序序列中，直到最后一个数字插入有序序列为止；初始时以第一个数字自成一个序列。

该算法的一种如下（Java版）：

 1 /**
 2  * 插入排序
 3  * @author JiaJoa
 4  * 从第一个元素开始，该元素可以认为已经被排序
 5  * 取出下一个元素，在已经排序的元素序列中从前向后扫描 
 6  * 如果该元素（已排序）大于新元素，将该元素移到下一位置 （和新元素的位置互换）
 7  * 将新元素插入该位置
 8  * 
 9  */
10 public class Algorithm_InsertSort {
11 
12     public static void main(String[] args) {
13         // TODO Auto-generated method stub
14         int[] data = new int[]{13,8,4,2,3,5,11,9,7};
15         Algorithm_InsertSort.insertSort(data);
16     }
17     
18     public static void insertSort(int[] data){
19         int size = data.length;
20         for(int i=0;i<size;i++){
21             int temp=data[i]; //保存已排序的最后一个数值
22             int j = i;  //保存最后一个数值的下标，从后向前搜索
23             while(j>=1&&temp<data[j-1]){
24                 data[j] = data[j-1];
25                 j--;
26             }
27             data[j] = temp;
28         }
29         
30         StringBuilder build  = new StringBuilder();
31         for(int i:data){
32             build.append(i+" ");
33         }
34         System.out.println(build.toString());
35     }
36 
37 }