良许Linux教程网 干货合集 详解希尔排序

详解希尔排序

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

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

  1. 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
  2. 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;

希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录”基本有序”时,再对全体记录进行依次直接插入排序。

算法步骤

选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;

按增量序列个数 k,对序列进行 k 趟排序;

每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

动图演示

什么是希尔排序?什么是希尔排序?

代码实现

JavaScript

实例

function shellSort(arr) {
   var len = arr.length,
       temp,
       gap = 1;
   while(gap for (gap; gap > 0; gap = Math.floor(gap/3)) {
       for (var i = gap; i for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
               arr[j+gap] = arr[j];
           }
           arr[j+gap] = temp;
       }
   }
   return arr;
}

Python

实例

def shellSort(arr):
   import math
   gap=1
   while(gap while gap > 0:
       for i in range(gap,len(arr)):
           temp = arr[i]
           j = i-gap
           while j >=0 and arr[j] > temp:
               arr[j+gap]=arr[j]
               j-=gap
           arr[j+gap] = temp
       gap = math.floor(gap/3)
   return arr

Go

实例

func shellSort(arr []int) []int {
       length := len(arr)
       gap := 1
       for gap for gap > 0 {
               for i := gap; i for j >= 0 && arr[j] > temp {
                               arr[j+gap] = arr[j]
                               j -= gap
                       }
                       arr[j+gap] = temp
               }
               gap = gap / 3
       }
       return arr
}

Java

实例

public static void shellSort(int[] arr) {
   int length = arr.length;
   int temp;
   for (int step = length / 2; step >= 1; step /= 2) {
       for (int i = step; i while (j >= 0 && arr[j] > temp) {
               arr[j + step] = arr[j];
               j -= step;
           }
           arr[j + step] = temp;
       }
   }
}

PHP

实例

function shellSort($arr)
{
   $len = count($arr);
   $temp = 0;
   $gap = 1;
   while($gap $len / 3) {
       $gap = $gap * 3 + 1;
   }
   for ($gap$gap > 0; $gap = floor($gap / 3)) {
       for ($i = $gap$i $len; $i++) {
           $temp = $arr[$i];
           for ($j = $i - $gap$j >= 0 && $arr[$j] > $temp$j -= $gap) {
               $arr[$j+$gap] = $arr[$j];
           }
           $arr[$j+$gap] = $temp;
       }
   }
   return $arr;
}

C

实例

void shell_sort(int arr[], int len) {
       int gap, i, j;
       int temp;
       for (gap = len >> 1; gap > 0; gap >>= 1)
               for (i = gap; i for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                               arr[j + gap] = arr[j];
                       arr[j + gap] = temp;
               }
}

C++

实例

template
void shell_sort(T array[], int length) {
   int h = 1;
   while (h while (h >= 1) {
       for (int i = h; i for (int j = i; j >= h && array[j] 

以上就是良许教程网为各位朋友分享的Linux系统相关内容。想要了解更多Linux相关知识记得关注公众号“良许Linux”,或扫描下方二维码进行关注,更多干货等着你 !

img
本文由 良许Linux教程网 发布,可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。
良许

作者: 良许

良许,世界500强企业Linux开发工程师,公众号【良许Linux】的作者,全网拥有超30W粉丝。个人标签:创业者,CSDN学院讲师,副业达人,流量玩家,摄影爱好者。
上一篇
下一篇

发表评论

邮箱地址不会被公开。 必填项已用*标注

联系我们

联系我们

公众号:良许Linux

在线咨询: QQ交谈

邮箱: yychuyu@163.com

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

关注微博
返回顶部