java简单排序算法之插入排序

插入排序

简介

	插入排序的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序
	列，对于未排序数据，在已排序的序列中从后向前扫描，找到相依的插入位置。插
	入排序在实现上，通常采用in-place排序（即只需用到O（1）的额外空间的排序），
	因而再从后像前扫描的过程中，需要反复把已排序的元素逐步向后挪位，为最新的
	元素提供插入空间。

描述过程

	1.从第一个元素开始，该元素可以认为已经被排序。
	2.取出下一个元素，在已排序的元素序列中从后向前扫描。
	3.如果该元素（宝库已排序）大于新的元素，该元素移动到下一个位置。
	4.重复第3步，直到找到已排序的元素小于或者等于新元素的位置。
	5.将新元素插入到该位置后，重复2~5步。

演示图

第一步：默认是第一个数已排序

第二步 44比3大就默认已排序到第二的位置

第三步 取出38从后向前对比

第四步：从后向前对比，放入第2个位置

第5步：依次类推

大白话理解

	一个数组中，默认第一个元素已经被排序了。取出第二个元素跟第一个元素比较大
	小。大的就原地插入，小就向前插入。取出第三个元素从后向前依次比较。比第二
	元素小就继续跟第一个元素比较。比第二元素大就原地插入。依次类推，直到所有
	元素比较完，排序就完成了。

代码演示

/**
 *  插入排序
 * @author Mr.qian
 */
public class InsertSort {
	
	public static void main(String[] args) {
		int[] arr = {8,1,9,2,7,4,5,3,6};
		sort(arr);
	}
	
	public static void sort(int[] arr) {
		//1.判空
		if(arr == null || arr.length <= 1) {
			return ;
		}
		//2.设置当前元素
		int current;                                                   
		for(int i = 0; i < arr.length -1; i++) {                            
			current =  arr[i+1]; // 当前元素下标;                         
			int preIndex = i;    // 上一元素下标;                                              
			//3.如果当前元素小于上一个元素
			while(preIndex >= 0 && current < arr[preIndex]) {            
				//需要将上一个元素下标进行下移
				arr[preIndex+1] = arr[preIndex];                        
				//4 .保证从后向前完全遍历比较											
				preIndex --;                                               
			}
			
			arr[preIndex +1] = current;                               
		}
		System.out.println(Arrays.toString(arr));
	}
}

结论

插入排序
平均时间复杂度	O(n²)
最好情况	O(n)
最坏情况	O(n²)
空间复杂度	O(1）
排序方式	In-place （内排序）
稳定性	Y