常见内部排序算法之插入排序

常见内部排序算法之插入排序
今天来写写插入排序算法，包括直接插入，折半插入，希尔排序（Shell）。
插入插入，就是将数组分成已排序，未排序，然后将未排序中的第一个插入已排序中的适合位置，这样，未排序越来越少，直到没有就算排序完成！而默认开始则是第一个是已排序，剩下的则是未排序。
直接插入算法：

package test.aglorith;

import java.util.Arrays;

public class InsertSort {
	public static void sort(int[] data) {
		int data_len=data.length;
		for (int i = 1; i < data_len; i++) {//默认第一个（下标是0）是已排序，从未排序中的第二个（下标是1）开始
			int temp=data[i];
			int j = i-1;
			while (j >=0&&temp<data[j]) {
				data[j+1]=data[j];
				j--;
			}
			data[j+1]=temp;
			System.out.println(Arrays.toString(data));
		}
	}
	public static void main(String[] args) {
		int[] data=new int[]{10,9,8,7,6,5,4,3,2,1};
		System.out.println("排序之前"+Arrays.toString(data));
		sort(data);
	}

}

折半插入算法：

package test.aglorith;
import java.util.Arrays;

public class InsertSortBinary {
	public static void sort(int[] data) {
		int data_len=data.length;
		for (int i = 1; i < data_len; i++) {
			int temp=data[i];
			int mid=getMid(data, i);
			swapPass(data, i, mid);
			data[mid]=temp;
			System.out.println(Arrays.toString(data));
		}
	}
	public static int getMid(int[] data,int i) {
		int temp=data[i];
		int low=0;
		int hight=i-1;
		while (low<=hight) {
			int mid=(low+hight)/2;
			if (temp<data[mid]) {
				hight=mid-1;
			}else {
				low=mid+1;
			}
		}
		return low;//无论如何都是返回low，折中折中，无非最后只剩下两个的时候，选择谁作为被替代者
	}
	public static void swapPass(int[] data,int i,int mid) {
		for (int j = i; j > mid; j--) {
			data[j]=data[j-1];
		}
	}
	public static void main(String[] args) {
		int[] data=new int[]{11,10,9,8,7,6,5,4,3,2,1};
		System.out.println("排序之前"+Arrays.toString(data));
		sort(data);
	}
}

希尔排序算法：又称缩小增量排序
由于插入排序需要大量的移动数据，因此效率会受到影响。而在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量increment逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按increment*+3作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。

package test.aglorith;
import java.util.Arrays;
public class ShellSort {
	//通过增量increment分组进行排序
	public static void sortByIncrement(int[] data,int increment) {
		int data_len=data.length;
		for (int i = increment; i <data_len; i++) {
			int temp=data[i];
			int j=i-increment;
			while (j>=0&&temp<data[j]){
				data[j+increment]=data[j];
				j=j-increment;
			}
			data[j+increment]=temp;
		}
		System.out.println(Arrays.toString(data));
	}
	//不同的increment分组排序，直到increment=1（相当于直接插入排序，但是由于前面的排序已经使得数组基本上处于有序状态）
	public static void sort(int[] data) {
		int increment=data.length;
		while (increment>1) {
			increment=(increment-1)/3;
			sortByIncrement(data,increment);
		}
	}
	public static void main(String[] args) {
		int[] data=new int[]{13,12,11,10,9,8,7,6,5,4,3,2,1};
		System.out.println("排序之前"+Arrays.toString(data));
		sort(data);
	}
}