首页 > 系统相关 >【希尔排序ShellSort算法详解】Java/Go/Python/JS/C不同语言实现

【希尔排序ShellSort算法详解】Java/Go/Python/JS/C不同语言实现

时间：2023-03-10 17:55:50浏览次数：78  
标签：arr 排序 Java Python gap current int 步长 JS

【希尔排序算法详解】Java/Go/Python/JS/C不同语言实现

 

说明

希尔排序（Shell Sort）是插入排序的一种改进版，也称递减增量排序算法（Diminishing Increment Sort），其实质是将数列分组，然后再按插入算法分别排序，因DL．Shell于1959年提出而得名。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时效率较高，可以达到线性排序的效率。
  • 但插入排序对于一般不规则数列来说是低效的，因为插入排序每次只能挪动一位数据。
    步长序列：n/2i 最坏情况复杂度：O(n2)
    步长序列：2k-1 最坏情况复杂度：O(n3/2)
    步长序列：2i3j 最坏情况复杂度：O(nlog2n)

 

实现过程

  1. 定义一个分组间隔（步长），分组规则可以是1/2数组长度或其他。
  2. 按步长间隔取出数字组成子序列，针对子序列按照插入算法进行排序。
  3. 步长按照分组规则缩量递减，继续新一轮子序列的插入排序。
  4. 待步长为1时，再对全体元素进行一次插入排序，排序完成。

步长间隔怎么取呢？在希尔的原稿中建议的初始步长是N/2，就是将每一次排序分成两半，这样取步长在大多数情况下会比插入排序好，但也不是最好。

 

示意图

 

 

性能分析

平均时间复杂度：O(Nlog2N)
最佳时间复杂度：
最差时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
复杂性：较复杂

 

代码

 

Java

 

// java希尔排序算法
class ShellSort {

  /* 1. 希尔排序标准版，基于插入排序进行分组排序，步长按1/2缩减。 */
  static int[] shellSort1(int arr[]) {
    int len = arr.length;
    // 设置分组增量值（步长）为1/2的数组长度
    int gap = len / 2;

    // 根据步长得到子序列如果间隔大于0，则表示还可以继续分组
    while (gap > 0) {
      for (int i = gap; i < len; i++) {
        int current = arr[i];
        int j = i;
        // 根据步长得到子序列，对子序列按照插入排序
        while (j >= gap && current < arr[j - gap]) {
          System.out.println("gap=" + gap + " i=" + i + " j=" + j + " arr:" + Arrays.toString(arr));
          arr[j] = arr[j - gap];
          j -= gap;
        }
        // 交换当前项
        arr[j] = current;
      }
      // 缩短一半步长
      gap = gap / 2;
    }
    return arr;
  }

  /* 2. 希尔排序，基于插入排序进行分组排序，步长按3倍递减。 */
  public static int[] shellSort2(int[] arr) {

    int len = arr.length;
    int gap = 1;
    // 初始步长按3倍递增，小于1/3数组长度
    while (gap < len / 3) {
      gap = gap * 3 + 1;
    }

    // 如果间隔大于0，则表示还可以继续分组
    while (gap > 0) {
      for (int i = gap; i < len; i++) {
        int current = arr[i];
        int j = i - gap;
        // 根据步长得到子序列，对子序列按照插入排序
        for (; j >= 0 && arr[j] > current; j -= gap) {
          System.out.println("gap=" + gap + " i=" + i + " j=" + j + " arr:" + Arrays.toString(arr));
          arr[j + gap] = arr[j];
        }
        arr[j + gap] = current;
      }
      // 步长按3倍缩减
      gap /= 3;
    }

    return arr;
  }

 

 

Python

 

# python希尔排序算法
# 1. 希尔排序标准版，基于插入排序进行分组排序，步长按1/2缩减。
def shell_sort1(arr):
    size = len(arr)
    # 设置分组增量值（步长）为1/2的数组长度
    gap = size // 2

    # 根据步长得到子序列，如果间隔大于0，则表示还可以继续分组
    while gap > 0:
        for i in range(gap, size):
            current = arr[i]
            j = i
            # 对子序列按照插入排序
            while j >= gap and current < arr[j - gap]:
                print('gap=' + str(gap) + ' i=' + str(i) + ' j-gap=' +
                      str(j - gap) + ' j=' + str(j))
                arr[j] = arr[j - gap]
                j -= gap
            # 交换当前项
            arr[j] = current
        # 调整步长为1/2
        gap = gap // 2
    return arr


# 2. 希尔排序，基于插入排序进行分组排序，步长按3倍递减。
def shell_sort2(arr):
    size = len(arr)
    gap = 1
    # 初始步长按3倍递增，小于1/3数组长度
    while gap < (size // 3):
        gap = gap * 3 + 1

    # 根据步长得到子序列，如果间隔大于0，则表示还可以继续分组
    while (gap > 0):
        for i in range(gap, size):
            current = arr[i]
            j = i - gap
            # 对子序列按照插入排序s
            while j >= 0 and arr[j] > current:
                print('gap=' + str(gap) + ' i=' + str(i) + ' j=' + str(j) + ' j+gap=' + str(j + gap))
                arr[j + gap] = arr[j]
                j -= gap

            # 还原当前位置
            arr[j + gap] = current

        # 步长按3倍缩减
        gap = gap // 3

    return arr

 

Go

 

// go语言希尔排序算法
// 1. 希尔排序标准版，基于插入排序进行分组排序，步长按1/2缩减。
func shellSort1(arr []int) []int {
  var arrLen int = len(arr)
  //  设置分组间隔
  var gap int = (arrLen / 2)
  // 如果间隔大于0，则表示还可以继续分
  for gap > 0 {
    for i := 0; i < arrLen; i++ {
      var current = arr[i]
      var j = i
      // 分组按照插入排序
      for j >= gap && current < arr[j-gap] {
        fmt.Println("gap=", gap, "i=", i, " j-gap=", j-gap, " j=", j)
        arr[j] = arr[j-gap]
        j -= gap
      }
      // 交换当前项
      arr[j] = current
      // 调整步长为1/2
    }
    gap = (gap / 2)
  }
  return arr
}

// 2. 希尔排序，基于插入排序进行分组排序，步长按3倍递减。
func shellSort2(arr []int) []int {
  var arrLen int = len(arr)
  //  设置分组间隔
  var gap int = 1
  // 初始步长按3倍递增，小于1/3数组长度
  for gap < (arrLen / 3) {
    gap = gap*3 + 1
  }
  // 如果间隔大于0，则表示还可以继续分
  for gap > 0 {
    for i := gap; i < arrLen; i++ {
      var current = arr[i]
      var j = i - gap
      // 对子序列按照插入排序
      for ; j >= 0 && arr[j] > current; j -= gap {
        fmt.Println("gap=", gap, "i=", i, " j=", j, " j+gap=", (j + gap))
        arr[j+gap] = arr[j]
      }
      arr[j+gap] = current
    }
    // 步长按3倍缩减
    gap = (gap / 3)
  }
  return arr
}

 

JS

 

// js希尔排序算法
/* 1. 希尔排序标准版，基于插入排序进行分组排序，步长按1/2缩减。 */
function shellSort1(arr) {
  const len = arr.length
  // 设置分组增量值（步长）为1/2的数组长度
  let gap = Math.floor(len / 2)
  // 根据步长得到子序列，如果间隔大于0，则表示还可以继续分组
  while (gap > 0) {
    for (let i = 0; i < len; i++) {
      const current = arr[i]
      let j = i
      // 对子序列按照插入排序
      while (j >= gap && current < arr[j - gap]) {
        console.log('gap=' + gap + ' i=' + i + ' j=' + j + ' (j - gap)=' + (j - gap), 'arr:', arr)
        arr[j] = arr[j - gap]
        j -= gap
      }
      // 交换当前项
      arr[j] = current
    }
    // 调整步长为1/2
    gap = Math.floor(gap / 2)
  }
  return arr
}

/* 2. 希尔排序，基于插入排序进行分组排序，步长按3倍递减。 */
function shellSort2(arr) {
  const len = arr.length
  let gap = 1
  // 初始步长按3倍递增，小于1/3数组长度
  while (gap < Math.floor(len / 3)) {
    gap = gap * 3 + 1
  }
  // 根据步长得到子序列，如果间隔大于0，则表示还可以继续分组
  while (gap > 0) {
    for (let i = gap; i < len; i++) {
      const current = arr[i]
      let j = i - gap
      // 对子序列按照插入排序
      for (; j >= 0 && arr[j] > current; j -= gap) {
        console.log('gap=' + gap + ' i=' + i + ' j=' + j + ' (j + gap)=' + (j + gap), 'arr:', arr)
        arr[j + gap] = arr[j]
      }
      arr[j + gap] = current
    }
    // 步长按3倍缩减
    gap = Math.floor(gap / 3)
  }
  return arr
}

 

TS

 

// TS希尔排序算法
// 1. 希尔排序，基于插入排序进行了分组排序
class ShellSort {
  shellSort1(arr: number[]): number[] {
    const len = arr.length
    // 设置分组增量值（步长）为1/2的数组长度
    let gap = Math.floor(len / 2)
    // 根据步长得到子序列，如果间隔大于0，则表示还可以继续分组
    while (gap > 0) {
      for (let i = 0; i < len; i++) {
        const current = arr[i]
        let j = i
        // 对子序列按照插入排序
        while (j >= gap && current < arr[j - gap]) {
          console.log(
            'gap=' + gap + ' i=' + i + ' j=' + j + ' (j - gap)=' + (j - gap),
            'arr:',
            arr
          )
          arr[j] = arr[j - gap]
          j -= gap
        }
        // 交换当前项
        arr[j] = current
      }
      // 调整步长为1/2
      gap = Math.floor(gap / 2)
    }
    return arr
  }

  /* 2. 希尔排序，基于插入排序进行分组排序，步长按3倍递减。 */
  shellSort2(arr: number[]): number[] {
    const len = arr.length
    let gap = 1
    // 初始步长按3倍递增，小于1/3数组长度
    while (gap < Math.floor(len / 3)) {
      gap = gap * 3 + 1
    }
    // 根据步长得到子序列，如果间隔大于0，则表示还可以继续分组
    while (gap > 0) {
      for (let i = gap; i < len; i++) {
        const current = arr[i]
        let j = i - gap
        // 对子序列按照插入排序
        for (; j >= 0 && arr[j] > current; j -= gap) {
          console.log(
            'gap=' + gap + ' i=' + i + ' j=' + j + ' (j + gap)=' + (j + gap),
            'arr:',
            arr
          )
          arr[j + gap] = arr[j]
        }
        arr[j + gap] = current
      }
      // 步长按3倍缩减
      gap = Math.floor(gap / 3)
    }
    return arr
  }
}

 

C

 

// C语言希尔排序算法
/* 1. 希尔排序标准版，基于插入排序进行分组排序，步长按1/2缩减。 */
float *shell_sort1(float arr[], int len)
{
  // 设置分组增量值（步长）为1/2的数组长度
  int gap = len / 2;
  // 根据步长得到子序列，如果间隔大于0，则表示还可以继续分组
  while (gap > 0)
  {
    for (int i = 0; i < len; i++)
    {
      float current = arr[i];
      int j = i;
      // 对子序列按照插入排序
      while (j >= gap && current < arr[j - gap])
      {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      // 交换当前项
      arr[j] = current;
    }
    // 调整步长为1/2
    gap = gap / 2;
  }
  return arr;
}

/* 2. 希尔排序标准版，基于插入排序进行分组排序，步长按1/2缩减。 */
int *shell_sort2(int arr[], int len)
{
  // 设置分组增量值（步长）为1/2的数组长度
  int gap = 1;
  // 初始步长按3倍递增，小于1/3数组长度
  while (gap < len / 3)
  {
    gap = gap * 3 + 1;
  }
  // 根据步长得到子序列，如果间隔大于0，则表示还可以继续分组
  while (gap > 0)
  {
    for (int i = 0; i < len; i++)
    {
      int current = arr[i];
      int j = i - gap;
      // 对子序列按照插入排序
      for (; j >= 0 && arr[j] > current; j -= gap)
      {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = current;
    }
    // 步长按3倍缩减
    gap = (gap / 3);
  }
  return arr;
}

 

 

链接

希尔排序算法源码：https://github.com/microwind/algorithms/tree/master/sorts/shellsort

其他排序算法源码：https://github.com/microwind/algorithms

标签：arr,排序,Java,Python,gap,current,int,步长,JS
From： https://www.cnblogs.com/letjs/p/17204308.html

相关文章

  • java-IO-字节流复制文本文件
          ......
  • js装饰器作用
    JavaScript装饰器（Decorator）是一种语法特性，可以用于修改类和类的属性或方法。它是ES2017引入的新特性，在Vue3和Angular等现代框架中广泛使用。装饰器可以让我们在不......
  • java学习日记20230310-排序
    排序 指将一组数据按照指定的顺序排列的过程分类：内部排序：指将需要处理的所有数据都加载到内存储存器中，进行排序，包括交换排序法，选择排序法，插入排序法外部排序：......
  • python+ddt+pymsql实现数据驱动自动化测试
    程序结构：   1，首先连接数据库（mysql.py）并获取到数据库里面的数据importpymysql#创建链接数据库的方法deflianSql(host,user,password,database):""......
  • python pandas DataFrame,Series进一步理解
     更进一步学习和理解DataFrame,Series多个Series拼凑成一个dict,然后将dict转为DataFrame结构#!/usr/bin/evnpythonimportnumpyasnpimportpandasaspd......
  • java-IO-字节流读数据(一次读一个字节数据)
              ......
  • python_2
    importRPi.GPIOasGPIOimporttimeGPIO.setmode(GPIO.BCM)led=21bt=20GPIO.setup(led,GPIO.OUT)GPIO.setup(bt,GPIO.IN,pull_up_down=GPIO.PUD_UP)ledSt......
  • python
    importRPi.GPIOasGPIOimporttimeGPIO.setmode(GPIO.BCM)led=21bt=20GPIO.setup(led,GPIO.OUT)GPIO.setup(bt,GPIO.IN,pull_up_down=GPIO.PUD_UP)ledStatus=Fals......
  • JAVA WEB项目文件夹上传下载源代码
    ​ 一、功能性需求与非功能性需求要求操作便利，一次选择多个文件和文件夹进行上传；支持PC端全平台操作系统，Windows,Linux,Mac支持文件和文件夹的批量下载，断点续传。刷......
  • 1_JAVAEE简介
    什么是JavaEEJavaEE（JavaEnterpriseEdition），Java企业版，是一个用于企业级web开发平台。最早由Sun公司定制并发布，后由Oracle负责维护。JavaEE平台规范了在开发企业级web应用......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99