登陆 注册

java算法实现之希尔排序

守望者 2020-04-24 140人围观 ,发现0个评论 java

     所谓希尔排序本质来说是插入排序的增强版(java算法实现之插入排序),它是一种增量式排序,在插入排序的基础上做出了一些改进。

    这个做出的改进简单说就是,将数组划分为gap(增量值/步长值)个小的数组,然后在这些小数组里面使用插入排序,随着gap值的缩小,这些小数组的个数也随之缩小,同时他们的元素个数变长,最终合并为一个数组完成最终排序。


    算法实现过程:


首先,得到一个gap值,gap = arr.lenth/2 (一般初始值为数组长度的一半),

然后每隔gap个数组下标抓取一个数组元素划分到一个小的数组,

后面对这个小数组进行插入排序。

然后,gap = gap/2。


重复以上步骤(循环),直至gap=1时,即所有小数组合并到一个数组时完成数组的最终排序,退出循环,结束。


例如:

     这样一个数组有10个元素:10,9,8,7,6,5,4,3,2,1


第一轮:gap = 10/2 =5 .

   表示每隔5个元素划分为一个小组,则一共有5个小组,分别如下:

   第一组:10,5

    第二组:9,4

    第三组:8,3

    第四组:7,2

    第五组:8,1


第二轮,gap = gap/2, 此时取整数,gap=2, 则有两个小组:

    第一组:10,8,6,4,2,

    第二组:9,7,5,3,1

    

第三轮:gap = gap/2, 此时取整数,gap=1, 则有一个小组,即整个数组的最终排序结果:

     1,2,3,4,5,6,7,8,9,10


QQ截图20200424110702.jpg


希尔排序函数代码如下:

public static void shellSort(int[] array) {
		 //希尔排序
        int gap = array.length;
        while (gap>1) {    
            gap /= 2;   //增量(步长)每次减半    
            for (int i = 0; i < gap; i++) {        
                for (int j = i + gap; j < array.length; j += gap) {//对每个分组进行插入排序            
                    int temp = array[j];            
                    int k = j - gap;            
                    while (k >= 0 && array[k] > temp) {                
                        array[k + gap] = array[k];                
                        k -= gap;            
                    }            
                    array[k + gap] = temp;        
                }    
            }              
        }
	}


    转发请附上本文链接:https://tufeng.xyz/java/51.html,谢谢合作!

上一篇:网站介绍 下一篇:友链申请
请发表您的评论
请关注微信公众号
微信二维码