直接插入排序

浏览数：17 / 时间：2015年06月08日

直接插入排序：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

第一趟比较前两个数，然后把第二个数按大小插入到有序表中；第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序属于稳定的排序，最坏时间复杂性为O(n^2)，空间复杂度为O(1)。-------------摘自百度百科

图解：①第一次排序比较第二和第一个数，如果第一个数大于第二个数，则交行位置。否则不处理。这时，第一第二个数已经是一个排好序的队列。57,68

②第二次排序先比较第三个数和第二个数，59小于68，交行位置，59大于57不交换位置。则此时有序队列为57,59,68

③同②，为52找到合适位置。

 1 import java.util.Arrays;
 2 
 3 /**
 4  * 直接选择排序
 5  * 时间复杂度O(n2)
 6  * @author Administrator
 7  *
 8  */
 9 public class InsertSort {
10 
11     public void sort(int[] arr) {
12         System.out.println("排序前: " + Arrays.toString(arr));
13         for (int i = 1; i < arr.length; i++) {
14             for (int j = i; j > 0; j--) {
15                 if (arr[j-1] > arr[j]) {
16                     int temp = arr[j-1];
17                     arr[j-1] = arr[j];
18                     arr[j] = temp;
19                 }else {
20                     break;
21                 }
22             }
23             System.err.println("第" + i + "次排序：" + Arrays.toString(arr));
24         }
25     }
26     
27     public static void main(String[] args) {
28         // TODO Auto-generated method stub
29         InsertSort obj = new InsertSort();
30         int[] arr = {123,6,7,56,83,99,1000,101,4,3,2,1,14,53};
31         obj.sort(arr);
32         System.out.println(Arrays.toString(arr));
33     }
34 }