排序算法--------Shell排序(希尔排序/缩小增量排序)

浅浅的花香味﹌ 2022-04-23 01:58 135阅读 0赞

Shell排序(希尔排序/缩小增量排序)

  • 1.简介
  • 2.改进了什么?
  • 3.思想的体现
  • 4.算法复杂度的分析
  • 5.举个例子
  • 6.java代码实现
  • 7.对比直接插入排序

1.简介

希尔排序是非稳定排序算法。 希尔排序因DL.Shell于1959年提出而得名。 是对直接插入排序的一个优化。

2.改进了什么?

由于直接插入排序是一步一步移动的而,我们不希望它是一步一步的移动,而是大步大步的移动。所以为了达到这个条件希尔排序就被发明出来了,它也是当时打破效率 O(n^2)的算法之一。

3.思想的体现

(1) 由于直接插入排序复杂度是O(n^2),因此用Gap分组后,每组的数据量变少,则每组的直接插入排序耗时就会大幅降低;

(2) 不管选用几次Gap,只要最后一次Gap=1,总能完成排序;

(3) 显然,最终的排序耗时是和Gap的选择策略有关的。

4.算法复杂度的分析

希尔排序的关键并不是随便分组后各自排序,而是将相隔某个“增量”的记录组成一个字序列,实现跳跃式的移动,使得排序的效率提高。这的“增量”选取就非常关键了。我们采用的是arr.lenght/2的方式选取。可究竟选取一个什么样的值,最好呢?目前1还是数学难题(有兴趣可以参考:https://en.wikipedia.org/wiki/Shellsort)
在这里插入图片描述

5.举个例子

在这里插入图片描述

(1)第一趟: 选择gap=5,则共得到5组数据(相同颜色为一组),为每一组分别使用直接插入排序;

(2)第二趟选择gap=2,则共得到2组数据(相同颜色为一组),为每一组分别使用直接插入排序;

(3)第三趟: 选择gap=1,对所有数据使用一次直接插入排序。

注 :图中有两个相等数值的元素 5 和 下划线5 在排序过程中,两个元素位置交换了 ==》不稳定性的体现。

6.java代码实现

  1. package com.lsl.datastructure;
  2. public class ShellSort {
  3. public static void main(String[] args) {
  4. int[] array = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
  5. System.out.println("排序前:");
  6. ShellSort.printAll(array);
  7. System.out.println("排序后:");
  8. ShellSort.shellSort(array);
  9. }
  10. public static void shellSort(int[] arr){
  11. if (arr == null || arr.length == 0) {
  12. //判断数组是否为空
  13. System.out.println("该数组为空!");
  14. } else {
  15. int len = arr.length;
  16. for (int gap = len / 2; gap > 0; gap /= 2) {
  17. for (int i = gap; i < len; i++) {
  18. //从第gap个元素,逐个对其所在组进行直接插入排序操作
  19. int j = i;
  20. while (j - gap >= 0 && arr[j] < arr[j - gap]) {
  21. int temp = arr[j];
  22. arr[j] = arr[j - gap];
  23. arr[j - gap] = temp;
  24. //插入排序采用交换法
  25. j -= gap;
  26. }
  27. }
  28. }
  29. ShellSort.printAll(arr);
  30. }
  31. }
  32. private static void printAll(int[] list) {
  33. for (int value : list) {
  34. System.out.print(value + "\t");
  35. }
  36. System.out.println();
  37. }
  38. }

运行结果:
在这里插入图片描述

7.对比直接插入排序

  1. 直接插入排序是稳定的;而希尔排序是不稳定的。
  2. 直接插入排序更适合于原始记录基本有序的集合。
  3. 希尔排序的比较次数和移动次数都要比直接插入排序少,当N越大时,效果越明显。
  4. 在希尔排序中,增量序列gap的取法必须满足:最后一个步长必须是 1
  5. 直接插入排序也适用于链式存储结构;希尔排序不适用于链式结构

版权声明:本博客为记录本人自学感悟,转载需注明出处!
https://me.csdn.net/qq_39657909

发表评论

表情:
评论列表 (有 0 条评论,135人围观)

还没有评论,来说两句吧...

相关阅读

    相关 排序算法——排序

    前言 希尔排序又称缩小增量排序,是时间效率较高的插入排序方法。 算法的基本思想:先确定一个增量d(也叫间隙gap),然后按照增量的倍数所对应的数组下标值,从待排序序列中

    相关 排序算法排序

    一、前言     希尔(Shell)排序又称为缩小增量排序,它是一种插入排序。它是直接插入排序算法的一种威力加强版。     希尔排序,也称递减增量排序算法,以其设计