栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【希尔排序】十大排序算法之希尔排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【希尔排序】十大排序算法之希尔排序

【希尔排序】十大排序算法之希尔排序,属于不稳定的排序。

目录

一、希尔排序基本思想

二、希尔排序代码实现

2.1、希尔排序【折半缩小增量】

(1)实现代码一

(2)实现代码二

2.2、希尔排序【Sedgewick增量序列】


一、希尔排序基本思想
  • 希尔排序,也叫做:【缩小增量排序】,属于直接插入排序的升级版。
  • 希尔排序,属于插入类排序。
  • 希尔排序,时间复杂度:【O(n*log(n))】,最好情况下,可以达到【O(n^3/2)】(需要根据增量序列决定)。

什么是稳定的排序???

稳定排序:

  • 如果排序数组中,存在相同的元素,假设存在两个元素【3】。
  • 为了标识两个元素【3】的先后顺序,我们假设给她命名为:【3(1)】、【3(2)】。
  • 其中括号里面的表示元素3出现的先后顺序。
  • 如果结果排序之后,两个元素还是保持相同的顺序,即:【3(1)、3(2)】,那么我们就称这个排序是稳定的,否则就是不稳定的排序。

希尔排序基本思想

希尔排序,最关键的在于每次缩小移动增量,将每次相差增量距离的元素进行直接插入排序,直到最后增量等于1的时候,结束最后一次插入排序,此时希尔排序完成。

希尔排序基本思路:

  1. 第一次:选择【n/2】作为增量,将相差【n/2】的每个元素看作是一组序列,采用直接插入排序,将各组序列排序完成。
  2. 第二次:选择【n/2/2】作为量,将相差【n/2/2】的每个元素看作是一组序列,采用直接插入排序,将各组序列排序完成。
  3. 直到最后增量等于【1】,完成最后一次直接插入排序,此时希尔排序结束。

为什么说希尔排序是不稳定的排序呢???

我们知道,直接插入排序是【稳定】的排序,并且希尔排序也是属于【插入类】排序,那为什么希尔排序属于不稳定的排序呢???

这是因为一次插入排序确实是稳定的排序,但是希尔排序需要进行多次插入排序,那么在多次插入排序里面,就有可能导致排序是不稳定的情况,下面举个栗子看看。

  • 假设有待排序数组:【7,9(1),9(2),1】。
  • 我们首先采用增量【d=2】,进行一次希尔排序,此时需要将数组变成:【7,1,9(2),9(1)】。
  • 可以看到,我们上面的排序过程,已经将两个相同的数字【9】,改变了它们原先的先后顺序,所以希尔排序是不稳定的。
  • 判断一个排序算法是不是稳定,你就看排序过程中,会不会把两个相同的数字改变出现的先后顺序,也可以找个特殊的案例试一试。

下面给出希尔排序大致过程思想。

 可以从这个网站查看希尔排序的过程【数据结构和算法动态可视化 (Chinese) - VisuAlgo】。

二、希尔排序代码实现

2.1、希尔排序【折半缩小增量】

希尔排序基本思路:

  • 外层循环:控制增量大小【d】,从【d = n/2】开始,每次缩小一半,直到【d = 1】为止。
  • 内层循环:根据增量大小【d】,将数组中相差增量【d】的元素分为一组,对该组元素采用直接插入排序。
  • 循环结束,希尔排序完成。

(1)实现代码一
public class ShellSort {
    
    public static void shellSort(int[] nums) {
        // 外层循环: 控制增量大小
        for (int gap = nums.length / 2; gap >= 1; gap >>= 1) {
            // 内层循环: 有多少组元素需要进行直接插入排序
            for (int j = 0; j < gap; j++) {
                // 这层循环: 对每一组元素进行直接插入排序
                for (int k = j + gap; k < nums.length; k += gap) {
                    // 前一个位置
                    int index = k - gap;
                    // 比较数组前后两个元素大小, 满足条件则交换数组元素
                    while (index >= 0 && nums[index] > nums[index + gap]) {
                        int temp = nums[index];
                        nums[index] = nums[index + gap];
                        nums[index + gap] = temp;
                        index -= gap;
                    }
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] nums = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
        System.out.println(Arrays.toString(nums));
        shellSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

上面排序算法运行结果如下所示:

(2)实现代码二
public class ShellSort {
    
    public static void shellSort(int[] nums) {
        // 外层循环: 控制增量大小
        for (int gap = nums.length / 2; gap >= 1; gap >>= 1) {
            // 内层循环: 有多少组元素需要进行直接插入排序
            for (int index = gap; index < nums.length; index++) {
                // 保存当前元素
                int temp = nums[index];
                // 找到插入的位置
                int pos;
                for (pos = index; pos >= index && nums[pos - gap] > temp; pos -= gap) {
                    nums[pos] = nums[pos - gap]; // 移动数组元素,前一个元素覆盖当前元素
                }
                // 将当前元素插入正确位置
                nums[pos] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] nums = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
        System.out.println(Arrays.toString(nums));
        shellSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

2.2、希尔排序【Sedgewick增量序列】

Sedgewick增量序列:采用这个增量序列,据说平均情况下可以达到【O(N^7/6)】,最坏情况下,可以达到【O(N^4/3)】。

Sedgewick增量序列取值:【0,1,5,19,41,109,209,505,929】

public class ShellSort {
    
    public static void shellSort(int[] nums) {
        // 增量序列
        int[] sedgewick = {929, 505, 209, 109, 41, 19, 5, 1, 0};
        // 判断初始增量: 初始增量不能大于数组长度
        int d = 0; // 增量
        while (sedgewick[d] >= nums.length) {
            d++;
        }
        // 开始希尔排序
        for (int gap = sedgewick[d]; gap > 0; gap = sedgewick[++d]) {
            for (int i = gap; i < nums.length; i++) {
                int temp = nums[i]; // 保存当前元素
                // 找到插入位置
                int k;
                for (k = i; k >= gap && nums[k - gap] > temp; k -= gap) {
                    nums[k] = nums[k - gap]; // 向后移动元素
                }
                // 把当前元素插入正确位置
                nums[k] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] nums = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
        System.out.println(Arrays.toString(nums));
        shellSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

 综上,就是希尔排序相关思想,以及代码实现。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/946332.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号