[数据结构与算法]java数组的插入排序以及时间复杂度

插入排序的思想是把前面的排好依次往下进行遍历，发现比最后一个数小的把它插入排好序的最后一个数的前面，此时排好的数组可能已经不再有序，就对它进行维护,以此重复上述操作

具体步骤：定义一个指针i,再定义一个指针j,i最开始指向数组的第二个数，j指向i的前一个数，然后让j和他后面的数进行比较，如果后面的数比j小就让他俩交换（如果不交换说明前面已经排好序），然后再让指针j指到j的前一个数，在让j和j后面的数进行比较如果比j指针指向的数大就再进行交换，以此循环直到j后面的数比j大或j指向数组的第一个数，就让指针i指向下一个数，以此循环直到i指向数组最后一个数。排序完成。

数组按插入排序全过程如下图：

?

?

?

?

?

插入排序代码如下：

public class Insertsort {
	public static void main(String[] args) {
        //定义无序数组
		int[] arr= {23,43,1,22,67,123,88,99,90,15};
		sort(arr);
	}

	private static void sort(int[] arr) {
        //第一次for循环，即对每个数都进行遍历，i就是上面所说的i指针
		for(int i=1;i<arr.length;i++) {
            //第二次for循环，每次j开始都是i的前一个数，然后向前走以维护前面已排好序的数组即j--
			for(int j=i-1;j>=0;j--) {
                //判断如果j比后面数大就进行交换，然后j--进行维护
				if(arr[j]>arr[j+1]) {
					arr[j]^=arr[j+1];
					arr[j+1]^=arr[j];
					arr[j]^=arr[j+1];
				}else{//j比后面数小此层for循环结束，因为没必要继续遍历以减小时间频率，
                    break;
                }
			}	
		}
		System.out.println(Arrays.toString(arr));	
	}
	
}

结果如下：

?时间复杂度：外层for循环时间复杂度是O（n）最坏情况里层需要每次遍历到数组的第一个数即里层时间复杂度是O（n）,所以最坏情况下插入排序的时间复杂度是o(n^2)

这也是插入排序的弊端所以产生一个希尔排序来降低它的时间复杂度。