【算法系列】——Java实现插入&&希尔排序

痛定思痛。 2022-06-10 06:17 121阅读 0赞

# 插入排序 #

##    定义 ##

将一个数据插入到已经排好序的**有序数据**中，插入排序巧用之前的序列，从而简化排序的过程，提高效率。

## 图解插入排序 ##

![Center][]

## 程序代码实现 ##

/**  
      * @Title:  insertSort.java
      * @Package cn.xiaojia.test
      * @Description: 
      * @author 贾文静
      * @date  2017年8月11日 下午8:58:02
      * @version V1.0  
      * Update Logs:
    * ****************************************************
    * Name:
    * Date:
    * Description:
    ******************************************************
    */
    package cn.xiaojia.test;
    
    public class insertSort {
    	public static void main(String[] args) {
    		int[] a = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
    		System.out.print("排序原始数据:");
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i]+" ");
    		}
    		System.out.println();
    		insert(a);
    		System.out.print("排序结果展示:");
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i]+" ");
    		}
    	}
    	public static void insert(int[] a){
    		for (int i = 1; i < a.length; i++) {
    			int currentValue = a[i];
    			int position = i;
    			for (int j = i-1; j >=0; j--) {
    				if (a[j]>currentValue) {
    					//比当前值大，坐标向后移动一位
    					a[j+1]=a[j];
    					//此时比较的坐标向前移动，该坐标位的数据已经被记录
    					position--;
    				}else {
    					break;
    				}
    				a[position]=currentValue;
    			}
    			System.out.print("排序过程第"+i+"趟");
    			for (int j = 0; j < a.length; j++) {
    				System.out.print(a[j]+" ");
    			}
    			System.out.println();
    		}
    	}
    }

## 根据代码结果分析 ##

![Center 1][]

插入排序的有序区和无序区其实和选择排序是一致。

# 希尔排序    #

##    定义 ##

希尔排序又称为缩小增量排序。把数据按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

## 图解希尔排序 ##

![Center 2][]

## 程序代码实现 ##

/**  
      * @Title:  shellSort.java
      * @Package cn.xiaojia.test
      * @Description: 
      * @author 贾文静
      * @date  2017年8月8日 下午6:55:24
      * @version V1.0  
      * Update Logs:
    * ****************************************************
    * Name:
    * Date:
    * Description:
    ******************************************************
    */
    package cn.xiaojia.test;
    
    import javax.xml.transform.Templates;
    
    public class shellSort {
    	public static void main(String[] args) {
    		int[] a = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
    		System.out.print("排序原始数据:");
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i]+" ");
    		}
    		System.out.println();
    		shelltest(a);
    		System.out.print("排序结果展示:");
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i]+" ");
    		}
    	}
    	public static void shelltest(int[] data){
    		int j,temp;
    		int num=0;
    		//定义分组，插入中默认为1，所以不要少一层定义的过程
    		for (int increment = data.length / 2; increment > 0; increment /= 2){
    			//按分组间距比较数据大小
    			for (int i = increment; i < data.length; i+=increment) {
    				//与插入排序一样，均有在其前的数比较，在插入间距固定，默认从i=1开始，
    //				  在希尔中间距是动态的，故用i替代
    				 temp=data[i];
    				for (j = i-increment; j >=0; j-=increment) {
    					if (temp<data[j]) {
    						data[j+increment]=data[j];
    					}else {
    						break;
    					}
    				}
    				data[j+increment]=temp;
    			}
    			num+=1;
    			System.out.print("分组间距为"+increment+"排序过程第"+num+"趟:");
    			for (int i = 0; i < data.length; i++) {
    				System.out.print(data[i]+" ");
    			}
    			System.out.println();
    		} 
    
    	}
    	
    }

## 根据代码分析 ##

![Center 3][]

发现序列再经过前两次排序后，基本符合正向序列，相比直接插入排序，效率有了明显的提高。

# 【总结】 #

根据排序的思想，以及程序的实现代码，很明显希尔是插入排序的优化，所以在学习的借助基础会变得很容易。一开始的时候直接敲的希尔，很难实现，后来终于开窍了，也明白了为什么希尔中如何融入了插入排序，一步步的都是需要经历的！

PS：如有理解偏颇之处，欢迎各位拍砖，不胜感激！

[Center]: /images/20220610/1799e36c7fba4d9d99f9533993526950.png
[Center 1]: /images/20220610/e10b001cec474ff9957a6a56f6cc4e3c.png
[Center 2]: /images/20220610/cbab3e71e804449b89d43c5dba181897.png
[Center 3]: /images/20220610/cd83004e13c1405babec297d77132ed5.png