Java数据结构与算法-插入排序与希尔排序详解及代码

插入排序与希尔排序

一，插入排序

1. 插入排序的原理‘
2. 插入排序的特点
3. 插入排序的代码实现

（1），插入排序的原理
插入排序（InsertionSorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

（2），插入排序是一个内部排序，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

（3），核心代码实现

public static void insertSort(int[]a){
	//从第二位开始进行插入
	for(int i = 1;i<a.length;i++){
	
		int insertval = a[i];
		int index = i-1;
		
		while(index>=0&&insertval<a[index]){
			a[index+1] = a[index];
			index--;
		}
		//判断一下是不是本身的那个位置，如果是就没必要在赋值
		if(index+1!=i){
			a[index+1] = insertval
		}
		
	}

}

我们看简单的插入排序可能存在的问题.数组arr={2,3,4,5,6,1}
这时需要插入的数1(最小)
这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}

结论:当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响

二，希尔排序

1. 希尔排序的原理
2. 希尔排序的特点
3. 希尔排序的代码实现
4. 希尔排序的优化版

（1），希尔排序的原理

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

（2），特点

（3），核心代码实现（直接交换）

public static void insertSort(int[]a){

	for(int gap = a.length/2;gap>0;gap/=2){
	
		for(int i = gap ;i<a.length;i++){
		
			for(int j = i-gap;j>=0;j-=gap){
			
				if(a[j]>a[j+gap]){
					int temp = a[j];
					a[j] = a[j+gap];
					a[j+gap] = temp; 
				}
			}
		}
	}
}

（4），核心代码（移动法）

public static void insertSort(int[]a){
	
	for(int gap = a.length/2;gap>0;gap/=2){
		
		for(int i = gap ,i<a.length;i++){
			int insert = a[i];
			int index = i;
			if(a[index-gap>a[index]]){
				while(index-gap>=0&&a[index-gap]>insert){
					a[index] = a[index-gap];
					index-=gap;				
				}
				a[index] = insert;
			}
		}
	}

}

假如对八万个随机数进行排序比较两者的排序时间
直接交换：

移动法：

二者的时间相差还是很多的。

注：测试用的完整代码如下：

package com.atxiaopeng.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
import java.util.Random;

public class ShellSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a ={28,19,39,20,2,14,45,68,90,32};
		//shellSort(a);
		int[]a1 = new int[80000];
		for (int i = 0; i < a1.length; i++) {
			a1[i] = (new Random().nextInt()+1)*80000;
		}
		Date date1 = new Date();
		SimpleDateFormat s1 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		System.out.println(s1.format(date1));
		shellSort2(a1);
		
		Date date2 = new Date();
		SimpleDateFormat s2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		System.out.println(s2.format(date2));
		
		
		
	}
	public static void shellSort(int[] a) {
		int gap = a.length;
		int temp = 0;
		for (int i = gap/2; i > 0;i/=2 ) {
		
			for (int m = i; m < a.length; m++) {				
			
				for (int j = m-i; j >= 0; j-=i) {
					//a[j+i]而不用a[m],因为a[m]到a[0]之间可能有多个a[j]
					if (a[j]>a[j+i]) {
						temp = a[j+i];
						a[m] = a[j];
						a[j] = temp;
					}
				}
			}
		}
		//System.out.print(Arrays.toString(a)+" ");
	}
	public static void shellSort2(int[] a) {
		for (int gap = a.length/2; gap>0; gap/=2) {
			for (int i = gap; i < a.length; i++) {
				int j = i;
				int s = a[j];
				//运用的方法和插入法类似
				if (a[j]<a[j-gap]) {
					while (j-gap>=0&&s<a[j-gap]) {
						a[j] = a[j-gap];
						j-=gap;
					}
					a[j] = s;
				}
			}
		}
		
	}
	
}

欢迎指正！