搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 谓戒 > 算法基础--选择排序

算法基础--选择排序

谓戒 2018-10-29


希尔排序(Shell Sort)是插入排序的一种,也是缩小增量排序,是直接排序算法的一种更高效的改进版。希尔排序是非稳定算法。

基本思想:

将元素进行分组,然后对每组元素进行排序,在每组元素都有序之后,就可以对所有的分组利用插入排序进行最后一次排序,这样可以显著减少交换的此时,以达到加快排序速度的目的。

(1)先去一个小于n的整数d1作为第一个增量,把全部元素分成d1组,所有距离为d1的倍数的元素放在同一个组中,

(2)先在各组内进行直接插入排序,然后,取第二个增量d2<d1,重复上述的分组和排序,直到所取的增量dt=1(dt < dt-1 < ... < d1),即所有元素放在同一个组中进行直接排序插入排序为止。

时间复杂度分析:

(1)当元素初态基本有序时,直接插入排序所需的比较和交换次数均比较少,此时时间复杂度为O(n);

(2)当所有元素都是反序时,此时的比较和交换次数是最多的,时间复杂度O(n^2);

(3)所以平均时间复杂度O(n^3/2);

实例:

public static void shellSort(int[] arr){

    if(arr == null)  return ;

    int j = 0;

    int temp = 0 ;

    int len = arr.length /2;

    for(int increment = len ; increment > 0 ; increment /= 2){

        for(int i = increment ; i <arr.length; i++){

            temp = arr[i];

            for(j = i ; j >= increment ; j -= increment){

                if(temp < arr[j - increment]){

                    arr[j] = arr[j - increment];

                }else{

                    break;

                }

            }

            arr[j] = temp;

        }

    }

}



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《算法基础--选择排序》的版权归原作者「谓戒」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注谓戒微信公众号

谓戒微信公众号:gh_ea4fbd548cd2

谓戒

手机扫描上方二维码即可关注谓戒微信公众号

谓戒最新文章

精品公众号随机推荐