java实现排序算法之插入排序（直接插入排序、折半插入、shell排序）

插入排序主要包括直接插入排序、shell排序和折半插入等几种排序。这篇文章主要说明直接插入排序、shell排序和折半插入三种排序的java实现。
一、直接插入排序
　直接插入排序(straight insertion sort)的作法是：
　　每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
　　第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
　　直接插入排序属于稳定的排序，时间复杂性为o(n^2)，空间复杂度为O(1)。
　　直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。
　　值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。

//定义一个数据包装类
public class DataWrap implements Comparable<DataWrap>  
{
	int data;
	String flag;
	public DataWrap(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}
	public String toString()
	{
		return data + flag;
	}
	//根据data实例变量来决定两个DataWrap的大小
	public int compareTo(DataWrap dw)
	{
		return this.data > dw.data ? 1 
			: (this.data == dw.data ? 0 : -1);
	}
}

public class InsertSort
{
	public static void insertSort(DataWrap[] data) 
	{
		System.out.println("开始排序：\n");
		int arrayLength = data.length;
		for (int i = 1 ; i < arrayLength ; i++ )
		{
			//当整体后移时，保证data[i]的值不会丢失
			DataWrap tmp = data[i];
			//i索引处的值已经比前面所有值都大，表明已经有序，无需插入
			//（i-1索引之前的数据已经有序的，i-1索引处元素的值就是最大值）
			if (data[i].compareTo(data[i - 1]) < 0)
			{
				int j = i - 1;
				//整体后移一格
				for ( ; j >= 0 && data[j].compareTo(tmp) > 0 ; j--)
				{
					data[j + 1] = data[j];
				}
				//最后将tmp的值插入合适位置
				data[j + 1] = tmp;
			}
			System.out.println(java.util.Arrays.toString(data));
		}
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(9 , ""),
			new DataWrap(-16 , ""),
			new DataWrap(21 , "*"),
			new DataWrap(23 , ""),
			new DataWrap(-30 , ""),
			new DataWrap(-49 , ""),
			new DataWrap(21 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(30 , "")
		};
		System.out.println("排序之前：\n"
			+ java.util.Arrays.toString(data));
		insertSort(data);
		System.out.println("排序之后：\n" 
			+ java.util.Arrays.toString(data));
	}
}

二、折半插入排序
折半插入排序的基本思想是:设在顺序表中有一个对象序列V[0],V[1],…,V[n-1]。其中，V[0],V[1],…,V[i-1]是已经排好序的对象。在插入V[i]时,利用折半查找法寻找V[i]的插入位置。

public class BinaryInsertSort
{
	public static void binaryInsertSort(DataWrap[] data)
	{
		System.out.println("开始排序：\n");
		int arrayLength = data.length;
		for(int i = 1 ; i < arrayLength ; i++)
		{
			//当整体后移时，保证data[i]的值不会丢失
			DataWrap tmp = data[i];
			int low = 0;
			int high = i - 1;
			while(low <= high)
			{
				//找出low、high中间的索引
				int mid = (low + high) / 2;
				//如果tmp值大于low、high中间元素的值
				if(tmp.compareTo(data[mid]) > 0)
				{
					//限制在索引大于mid的那一半中搜索
					low = mid + 1;
				} 
				else
				{
					//限制在索引小于mid的那一半中搜索
					high = mid - 1;
				}
			}
			//将low到i处的所有元素向后整体移一位
			for(int j = i ; j > low ; j--)
			{
				data[j] = data[j - 1];
			}
			//最后将tmp的值插入合适位置
			data[low] = tmp;
			System.out.println(java.util.Arrays.toString(data));
		}
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(9 , ""),
			new DataWrap(-16 , ""),
			new DataWrap(21 , "*"),
			new DataWrap(23 , ""),
			new DataWrap(-30 , ""),
			new DataWrap(-49 , ""),
			new DataWrap(21 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(30 , "")
		};
		System.out.println("排序之前：\n"
			+ java.util.Arrays.toString(data));
		binaryInsertSort(data);
		System.out.println("排序之后：\n" 
			+ java.util.Arrays.toString(data));
	}
}

三、shell排序
希尔排序基本思想
　　  先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
　　该方法实质上是一种分组插入方法。
算法步骤
　　Step1 将n个元素个数列分为5个小组，在每个小组内按直接插入法排序；
　　step2 在第i步，分组个数取 di+1 =（di +1）/2 {9，5，3，2，1}；相临两组之间的对应元素进行比较，如果ai>aj，则交换它们的位置；
　　Step3 当dK = 1的循环过程完成后，排序过程结束。
Shell排序的时间性能优于直接插入排序
　　希尔排序的时间性能优于直接插入排序的原因：
　　①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
　　②当n值较小时，n和n的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n)差别不大。
　　③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
　　因此，希尔排序在效率上较直接插人排序有较大的改进。
稳定性
　　希尔排序是不稳定的。

public class ShellSort
{
	public static void shellSort(DataWrap[] data) 
	{
		System.out.println("开始排序：");
		int arrayLength = data.length;
		//h变量保存可变增量
		int h = 1;
		//按h * 3 + 1得到增量序列的最大值
		while(h <= arrayLength / 3)
		{
			h = h * 3 + 1;
		}
		while(h > 0)
		{
			System.out.println("===h的值:" + h + "===");
			for (int i = h ; i < arrayLength ; i++ )
			{
				//当整体后移时，保证data[i]的值不会丢失
				DataWrap tmp = data[i];
				//i索引处的值已经比前面所有值都大，表明已经有序，无需插入
				//（i-1索引之前的数据已经有序的，i-1索引处元素的值就是最大值）
				if (data[i].compareTo(data[i - h]) < 0)
				{
					int j = i - h;
					//整体后移h格
					for ( ; j >= 0 && data[j].compareTo(tmp) > 0 ; j-=h)
					{
						data[j + h] = data[j];
					}
					//最后将tmp的值插入合适位置
					data[j + h] = tmp;
				}
				System.out.println(java.util.Arrays.toString(data));
			}
			h = (h - 1) / 3;
		}
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(9 , ""),
			new DataWrap(-16 , ""),
			new DataWrap(21 , "*"),
			new DataWrap(23 , ""),
			new DataWrap(-30 , ""),
			new DataWrap(-49 , ""),
			new DataWrap(21 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(30 , ""),
		};
		System.out.println("排序之前：\n"
			+ java.util.Arrays.toString(data));
		shellSort(data);
		System.out.println("排序之后：\n" 
			+ java.util.Arrays.toString(data));
	}
}