希尔排序(Java) 2022.01.01

希尔排序也是一种插入排序,它是简单插入排序经过改进后的更高效的排序,也成为缩小增量排序

希尔排序的基本思想为:希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

希尔排序执行结果如图:

希尔排序(Java) 2022.01.01

具体代码如下:

package DataStructures.sort;

import java.util.Arrays;

/*
    希尔排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] nums = {8,9,1,7,2,3,5,4,6,0};
        System.out.println("原始数组为:"+Arrays.toString(nums));
        shellSort(nums);
    }

    public static void shellSort(int[] nums){

        int count = 0;
        //设置增量,并逐渐缩小增量
        for( int gap = nums.length / 2; gap > 0; gap /= 2 ){
            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;
                }
            }
            System.out.println("第"+(++count)+"轮希尔排序:"+ Arrays.toString(nums));
        }
    }
}

 

上一篇:数据结构--排序


下一篇:剑指offer61:扑克牌中的顺子