小小千想和您聊一聊

当前位置: 首页> 技术分享> 5分钟了解希尔排序

5分钟了解希尔排序

  前言

  希尔排序(shell sort)是插入排序的一种,它是简单插入排序经过改进之后的一个更高效的算法,这个排序方法又称为缩小增量排序。

  希尔排序思想介绍

  简单来说,希尔排序是将较大的数据集合逻辑上分割成若干个小的集合,然后对每个分组分别进行插入排序。

  例如,假设待排序元素序列有n个元素,首先取一个整数increment(小于n)作为间隔将全部元素分为increment个子序列,在每一个子序列中分别实行直接插入排序。然后缩小间隔increment,重复上述子序列划分和排序工作。直到最后取increment=1,将所有元素放在同一个子序列中排序为止。

  算法说明:

  待排序数据:12,1,6,7,4,10,5,9

  第一次的增量为数组元素的长度/2,即increment=4,得到四个分组:

  分组一:12, 4

  分组二: 1, 10

  分组三: 6, 5

  分组四: 7, 9

  对这四个分组分别进行插入排序,最终得到:

  4,1,5,7,12,10,6,9

  第二次比较,increment取上次值的一半,即increment=2,得到两个分组:

  分组一:4, 5, 12, 6

  分组二: 1, 7, 10, 9

  对这两个分组分别进行插入排序,最终得到:

  4, 1, 5,7, 6,9,12,10

  第三次比较,increment=1,即只有一个分组:

  分组一:4,1,5,7,6,9,12,10

  对其进行插入排序,最终得到:

  1,4,5,6,7,9,10,12

  希尔排序的代码实现

1.	public static void shellSort(int[] arr){  
2.	    int temp = 0;  
3.	    int j = 0;  
4.	    //增量初始值是长度的一半,增量每次变为原来的一半  
5.	    for(int inc = arr.length/2 ; inc >= 1 ; inc /= 2){  
6.	        for(int i = inc ; i < arr.length; i++){  
7.	            temp = arr[i];  
8.	            //将当前数与减去增量之后位置的数进行比较,如果大于,则后移  
9.	            for(j = i - inc; j >=0; j -= inc){  
10.	                if(arr[j] > temp){  
11.	                    arr[j + inc] = arr[j];  
12.	                }else{  
13.	                    break;  
14.	                }  
15.	            }  
16.	            arr[j + inc]=temp;  
17.	        }  
18.	    }  
19.	}  

  总结

  希尔排序是插入排序的改进,但是希尔排序中使用到了多次插入排序,在不同的插入排序过程中,相同的元素在各自的插入排序中可能会移动,造成排序的稳定性被打乱,所以希尔排序是不稳定的。

上一篇:HTML5工具初识之网页编辑器

下一篇:Activiti使用指南

QQ技术交流群

千锋Java开发官方①群
811099962

加入群聊