排序算法(希尔排序)

排序算法(希尔排序),第1张

排序算法(希尔排序) 希尔排序(shellSort)

介绍:

​ 希尔排序又叫缩小增量排序,是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减少至1时,整个数组恰好被分为一组,算法终止。

缩小增量后可以采用两种排序法:交换(冒泡)、位移(插入) 后者效率更高。

代码:

public class shellSort {
    public static void main(String[] args) {
        int[] nums = {8,9,1,7,2,3,5,4,6,0};
        shellSort(nums);
        //shellShort2(nums);
    }

    //交换法 增量shell排序
    public static void shellSort(int[] nums){
        int count = 0; //计数器
        int temp = 0; //交换用
        for (int gap = nums.length / 2; gap > 0 ; gap /= 2) {
            for (int i = gap; i < nums.length ; i++) {
                //遍历各组中的所有元素 步长为gap
                int j = i;
                while(j - gap >= 0 && nums[j] < nums[j-gap]){
                    temp = nums[j];
                    nums[j] = nums[j - gap];
                    nums[j - gap] = temp;
                    j -= gap;
                }
            }
            count++;
            System.out.println("希尔排序第"+count+"轮排序后:"+ Arrays.toString(nums));
        }
    }

    //移位式希尔排序 (增量分组后采用插入排序)
    public static void shellShort2(int[] nums){
        int count = 0;
        //增量gap,逐步缩小增量
        for (int gap = nums.length/2 ; gap > 0 ; gap /= 2) {
            //从第gap元素,逐个对其所在的组直接插入
            for (int i = gap; i < nums.length ; i++) {
                int j = i;
                int temp = nums[j]; //待插入的元素
                if (nums[j] < nums[j - gap]){
                    while(j - gap >=0 && temp < nums[j - gap]){
                        //移动
                        nums[j] = nums[j - gap];
                        j -= gap;
                    }
                    //当退出while循环时,找到插入位置了
                    nums[j] = temp;
                }
            }
            count++;
            System.out.println("希尔排序第"+count+"轮排序后:"+ Arrays.toString(nums));
        }
    }
}


时间复杂度

时间复杂度为O(n^1.5),要好于直接排序的O(n ^ 2),需要注意的是增量序列的最后一个增量值必须是1.另外由于记录跳跃式的移动,希尔排序并不是一种稳定的排序方法。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5697104.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-18

发表评论

登录后才能评论

评论列表(0条)

保存