插入排序

2020-03-29

插入排序

插入排序，实质上是向一组已经有序的数组里面插入元素。举个栗子，就像打扑克牌起牌一样，你手上已经有一堆牌，并且你已经排好序，这时候你又起一张牌，并且要将他插入“合适的位置”。如果待插入的元素比最后一个元素大，那么直接插入即可，如果比最后一个元素小，那么他将向左移，继续比较。直到他比那个元素大，那么将其插入。当然，我们要备份插入的那个元素，以免比它大的元素在后移过程中，破坏了该元素。

public class Main {
	public static void main(String[] args) {
		int arr[]= {1,5,3,15,41,34,76,52,11,2,10};
		for(int i=1;i<arr.length;i++){
			int cur=i;
			//先将cur位置的元素备份出来
			int elements=arr[cur];
			//如果待插入的元素比cur前一个位置元素小，就让该元素往后移
			while( cur>0 && elements<arr[cur-1]) {
				arr[cur]=arr[cur-1];
				cur--;
			}
			//此时再将待插入的元素插进去。
			arr[cur]=elements;
		       }
		for(Integer nums:arr) {
			System.out.println(nums);
		}
		}
}

通过以上的分析，我们发现插入排序的时间复杂度是O(n^2) 那么这样一来也与冒泡排序和选择排序也没差别了。接下来我们就想到一种优化思路，如果能减少寻找插入位置的次数，可以适当优化。这时候我们想到了二分查找法。二分查找法的思想，就是通过对搜索数组进行折半，如果该元素比中间元素大，那么我们去右半部分查找。如果比中间元素小，我们去左半部分查找。

/**
	 * 
	 * 查找number在有序数组arr中的位置
	 * @param arr
	 * @param number
	 * @return
	 */
	public static  int search(int arr[],int number) {
		int begin=0;
		int end=arr.length;
		while(begin<end) {
			int mid=(begin+end)/2;
			if(number==arr[mid])
				return mid;
			else if(number>arr[mid]) {
				begin=mid+1;
			}
			else if(number<arr[mid]) {
				end=mid;
			}	
		}
		return -1;
		
	}

但是这样就暴露了一个弊端，如果该数组中没有我们需要插入的元素，我们返回的索引值是-1，这样就违背了我们的初衷，我们是需要找到一个合适的位置来插入元素，这时候我们改进我们的二分搜索算法，我们查找第一个大于该元素(上文中的number)的位置.

/**
	 * 
	 * 查找number在有序数组arr中的插入位置 
	 * 第一个大于number的元素位置
	 * @param arr
	 * @param number
	 * @return
	 */
	public static int newSearch(int arr[],int number) {
		int begin=0;
		int end=arr.length;
		while(begin<end) {
			int mid=(begin+end)/2;
			if(number<arr[mid]) {
				end=mid;
			}else {
				begin=mid+1;
			}
		}
		return begin;
	}

通过以上的方法，我们可以减少比较次数，从而找到第一个大于该元素的索引。大致实现思路还是与之前的插入排序一样，我们通过后移元素，来腾出待插入位置。

public class Main {
	static int arr[]= {1,5,3,15,41,34,76,52,11};
	/**
	 * 找到index位置元素待插入的位置
	 * 已经排好序数组的区间范围是[begin,end)
	 * @param index
	 * @return
	 */
	private static  int search(int index) {
		int number=arr[index];
		int begin=0;
		int end=index;
		
		while(begin<end) {
			int mid=(begin+end)/2;
			if(number<arr[mid]) {
				end=mid;
			}else {
				begin=mid+1;
			}
			
		}
		return begin;
	}
	public static void main(String[] args) {
		for(int i=1;i<arr.length;i++) {
			//先备份待插入的元素
			int temp=arr[i];
			int insertIndex=search(i);
			//将【insertIndex,i)位置的元素都向后挪一位
			for(int j=i;j>insertIndex;j--) {
				arr[j]=arr[j-1];
			}
			arr[insertIndex]=temp;
			
		}
		
		for(Integer nums:arr) {
			System.out.println(nums);
		}
		
	}

}

这样以来，我们改进版的插入排序也就实现啦！！！