直接插入排序

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

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(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 }

欢迎大家留言评论指点一二,共同进步。O(∩_∩)O

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。