Java插入排序（1、直接插入排序2、希尔排序）

比眉伴天荒 2022-06-16 05:48 87阅读 0赞

**一、直接插入排序**  
         直接插入排序是排序中最简单的方法，类似于玩纸牌时整理手中纸牌的过程。其基本思想是：依次将待排序序列中的每一个记录插入到一个已经排好的序列中，直到全部记录都排好序。  
                                用一组数据模拟排序过程：  
                                                         初始序列： 12 15 9 20 6 31 24  
 第一次排序：【12 15】 9 20 6 31 24  
 第二次排序：【9 12 15】20 6 31 24  
 第三次排序：【9 12 15 20】 6 31 24  
 第四次排序：【6 9 12 15 20】31 24  
 第五次排序：【6 9 12 15 20 31 】24  
 第六次排序：【6 9 12 15 20 24 31】  
        根据上面的排序过程可以简便的理解为：将整个待排序的记录序列分为有序与无序两部分，将无序的每个元素插入到有序中的合适位置。

下面给出Java实现代码：

public void insertionsort(int[] data)
    	{
    		int temp;
    		int i,j;
    		for(i = 1; i<data.length;i++)
    		{
    			temp = data[i];
    			for(j = i; j > 0&& temp < data[j-1]; j--)           //寻找合适的位置，交换数据位置
    			{
    				data[j] = data[j-1];
    			}
    			data[j] = temp;
    		}
    	}

**      在效率上，直接插入排序方法的时间复杂度为O(n2),当序列的记录基本有序或者带排序记录较少时候，它是最佳的。相反数据量大，无规则性高时，效率就会降低。**

**二、希尔排序**  
        希尔排序是对直接插入排序的改进。思想：将待排序序列分为若干子序列分别进行插入排序，待整个序列基本有序，再整体做一次直接的差入排序。然而在这之中分成几组子序列则是一个问题，具体的取值方法在后面介绍。

用一组数据模拟排序过程：

初始序列：10  8  6  20  4  3  22  1  0  15  16

每隔5元素的子序列：【10,3】 【8,22】【6,1】【20,0】【4,15】

分别排序后的序列：3  8  1  0  4  10  22  6  20  15  16

再每隔3个元素序列：【3，0】【8,4】【1,10】【22,15】【6,16】

分别排序后的序列：0  4  1  3  6  10  15  8  20  22  16

最后整体做一次差入排序：0  1  3  4  6  8  10  15  16  20  22

其中涉及了一个取增量的问题：h1 = 1;

hi+! = 3hi + 1；

下面给出Java实现代码，可以根据代码更好的理解算法：

void shellsort(Object []data)
    	{
    		int i,j,k,h,hCnt,increments[] = new int[20];
    		Comparable tmp;
    		for(h = 1,i = 0;h < data.length;i++)
    		{
    			increments[i] = h;
    			h = 3*h + 1;
    		}
    		for(i--;i >= 0;i--)
    		{
    			h = increments[i];
    	        for(hCnt = h;hCnt < 2*h;hCnt++)
    	        {
    	        	for(j = hCnt;j < data.length;)
    	        	{
    	        		tmp = (Comparable)data[j];
    	        		k = j;
    	        		while(k-h >= 0 && tmp.compareTo(data[k-h]) < 0)
    	        		{
    	        			data[k] = data[k-h];
    	        			k-=h;
    	        		}
    	        		data[k] = tmp;
    	        		j += h;
    	        	}
    	        }
    		}
    	}

希尔排序的效率始终要好于直接插入排序！