java算法之插入排序

package test.base.sort;

/**
 * 插入排序
 * 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，
 * 从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，
 * 时间复杂度为O(n^* 2)。是稳定的排序方法 。
 * 插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，
 * 但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，
 * 再把这个最后元素插入到此刻已是有序的第一部分里的位置。
 * 
 * @author sky
 * 
 */
public class InsertionSorting {
	//两层for循环方式
	public static int[] insertSort(int[] arr) {
		//子数组初始大小为1
		for (int i = 1; i < arr.length; i++) {
			//把要插入的数据倒序前移，直到移到合适位置
			for (int j = i - 1; j >= 0 && arr[j + 1] < arr[j]; j--) {
				int tmp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = tmp;
			}
		}
		return arr;
	}
	
	//分离两层for循环方式
	public static int[] _insertSort(int[] arr){
		for(int i = 1; i < arr.length; i++){
			compareOne(arr, i);
		}
		return arr;
	}
	//每一次插入  要在arr的index之前的合适位置插入index对应的元素
	public static void compareOne(int[] arr, int index){
		int data = arr[index];
		for(int i = index - 1; i >= 0 && data < arr[i]; i--){
			arr[i + 1] = arr[i];
			arr[i] = data;
		}
		
	}

	public static void traverse(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}

	public static void main(String[] args) {
		int[] arr = new int[] { 9, 5, 1, 7, 3, 2, 4, 6 };
		traverse(_insertSort(arr));
	}
}