希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由希尔 1959 年公布。一些老版本教科书和参考手册把该算法命名为 Shell-Metzner，即包含 Marlene Metzner Norton 的名字，但是根据 Metzner 本人的说法，“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1．插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2．但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
1. 算法步骤
1、选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
2、按增量序列个数 k，对序列进行 k 趟排序；
3、每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
2. 动图演示
3. 时间复杂度
不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为O()，希尔排序时间复杂度的下界是n*log2n。希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比
复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法. 本质上讲，希尔排序算法是直接插入排序算法的一种改进，减少了其复制的次数，速度要快很多。 原因是，当n值很大时数据项每一趟排序需要移动的个数很少，但数据项的距离很长。当n值减小时每一趟需要移动的数据增多，此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。Shell算法的性能与所选取的分组长度序列有很大关系。只对特定的待排序记录序列，可以准确地估算关键词的比较次数和对象移动次数。想要弄清关键词比较次数和记录移动次数与增量选择之间的关系，并给出完整的数学分析，今仍然是数学难题。
4. 算法实现
希尔排序C语言
#include<stdio.h>
#include<math.h>
#define MAXNUM 10
void main()
{
void shellSort(int array[],int n,int t);//t为排序趟数
int array[MAXNUM],i;
for(i=0;i<MAXNUM;i++)
scanf("%d",&array[i]);
shellSort(array,MAXNUM,(int)(log(MAXNUM+1)/log(2)));//排序趟数应为log2(n+1)的整数部分
for(i=0;i<MAXNUM;i++)
printf("%d ",array[i]);
printf("\n");
}
//根据当前增量进行插入排序
void shellInsert(int array[],int n,int dk)
{
int i,j,temp;
for(i=dk;i<n;i++)//分别向每组的有序区域插入
{
temp=array[i];
for(j=i-dk;(j>=i%dk)&&array[j]>temp;j-=dk)//比较与记录后移同时进行
array[j+dk]=array[j];
if(j!=i-dk)
array[j+dk]=temp;//插入
}
}
//计算Hibbard增量
int dkHibbard(int t,int k)
{
return (int)(pow(2,t-k+1)-1);
}
//希尔排序
void shellSort(int array[],int n,int t)
{
void shellInsert(int array[],int n,int dk);
int i;
for(i=1;i<=t;i++)
shellInsert(array,n,dkHibbard(t,i));
}
//此写法便于理解，实际应用时应将上述三个函数写成一个函数。
希尔排序C++
template <typename _RIter>
void insert_sort(_RIter st, _RIter ed, int delta) {
for(_RIter i = st + delta; i < ed; i += delta) {
for(_RIter j = i; j > st; j -= delta)
if(*j < *(j - delta)) std::swap(*j, *(j - delta));
else break;
}
}
template <typename _RIter>
void shell_sort(_RIter st, _RIter ed) {
for(int delta = ed - st; delta; delta /= 2)
for(int i = 0; i < delta; i++)
insert_sort(st + i, ed, delta);
}
希尔排序PHP
function shell_sort(&$arr) {
if(!is_array($arr)) return;
$n = count($arr);
for ($gap = floor($n/2); $gap > 0; $gap = floor($gap/=2)) {
for($i = $gap; $i < $n; ++$i) {
for($j = $i - $gap; $j >= 0 && $arr[$j + $gap] < $arr[$j]; $j -= $gap) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + $gap];
$arr[$j + $gap] = $temp;
}
}
}
}
希尔排序JAVA
public static void main(String[] args){
int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1};
System.out.println("排序之前：");
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
//希尔排序
int gap = array.length;
while (true) {
gap /= 2; //增量每次减半
for (int i = 0; i < gap; i++) {
for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序
int k = j - gap;
while (k >= 0 && array[k] > array[k+gap]) {
int temp = array[k];
array[k] = array[k+gap];
array[k + gap] = temp;
k -= gap;
}
}
}
if (gap == 1)
break;
}
System.out.println();
System.out.println("排序之后：");
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
}
希尔排序JavaScript
var arr = [49, 38, 65, 97, 76, 13, 27, 49, 55, 04];
var len = arr.length;
for (var fraction = Math.floor(len / 2); fraction > 0; fraction = Math.floor(fraction / 2)) {
for (var i = fraction; i < len; i++) {
for (var j = i - fraction; j >= 0 && arr[j] > arr[fraction + j]; j -= fraction) {
var temp = arr[j];
arr[j] = arr[fraction + j];
arr[fraction + j] = temp;
}
}
}
console.log(arr);
希尔排序C#语言
using System;
using System.Collections.Generic;
namespace Demo
{
class Program
{
public static List<int> ShellSort(List<int> data)
{
for (int gap = data.Count / 2; gap > 0; gap = gap / 2) {
for (var i = gap; i < data.Count; i++) {
var j = i;
var current = data[i];
while (j - gap >= 0 && current < data[j - gap]) {
data[j] = data[j - gap];
j = j - gap;
}
data[j] = current;
}
}
return data;
}
public static void Main(String[] args)
{
var iArray = new List<int> { 1, 5, 3, 6, 10, 55, 55, 100, 9, 2, 87, 12, 34, 75, 33, 47 };
var newArray = ShellSort(iArray);
Console.WriteLine(string.Join(",", newArray));
}
}
}
希尔排序vb.net
Function Shell(Byval lines() As Integer) As Integer() dim c() As Integer=lines.clone,div,i,j,k As Integer,Data As Integer if UBound(c)=1 then return lines For div=len/2 To 1 div/=2 For i=0 To div Step 1 For j=i To len-div For k=j to len Step div If(data[j]>data[k]) swapInt(data+j,data+k) End If Next Next Next Next End Function
希尔排序Objective-C
+ (NSArray *)shellSort:(NSArray *)unsortDatas {
NSMutableArray *unSortArray = [unsortDatas mutableCopy];
int len = (int)unSortArray.count;
for (int gap = floor(len / 2); gap > 0; gap = floor(gap/2)) {
for (int i = gap; i < len; i++) {
for (int j = i - gap; j >= 0 && [unSortArray[j] integerValue] > [unSortArray[j+gap] integerValue]; j-=gap) {
NSNumber *temp = unSortArray[j];
unSortArray[j] = unSortArray[gap+j];
unSortArray[gap+j] = temp;
}
}
}
return [unSortArray copy];
}
希尔排序Python3.x
def shell(lis): n = len(lis) gap = int(n / 2) while gap > 0: for i in range(gap, n): temp = lis[i] j = i - gap while j >= 0 and lis[j] > temp: lis[j + gap] = lis[j] j = j - gap lis[j + gap] = temp gap = int(gap / 2) return lis
希尔排序AS3
//需要排序的数组
var arr:Array = [7, 5, 8, 4, 0, 9];
var small:int;//最小下标
var temp:int;
for(var i:int = 0; i < arr.length; i++){
small = i;
for(var j:int = i + 1; j < arr.length + 1; j++){
if(arr[j] < arr[small]){
small = j;
}
}
if(small != i){
temp = arr[i];
arr[i] = arr[small];
arr[small] = temp;
}
trace(arr[i]);
}
希尔排序RUBY
def shell_sort(array) gap = array.size while gap > 1 gap = gap / 2 (gap..array.size-1).each do |i| j = i while j > 0 array[j], array[j-gap] = array[j-gap], array[j] if array[j] <= array[j-gap] j -= gap end end end array end
希尔排序Kotlin
fun sort(arr: IntArray) {
var gap = arr.size / 2
while (1 <= gap) {
for (i in gap..arr.size - 1) {
var j = i - gap
val tmp = arr[i]
while (j >= 0 && tmp < arr[j]) {
arr[j + gap] = arr[j]
j -= gap
}
arr[j + gap] = tmp
}
gap /= 2
}
}
希尔排序Go语言
func ShellSort(nums []int) []int{
//外层步长控制
for step := len(nums) / 2; step > 0; step /= 2 {
//开始插入排序
for i := step; i < len(nums); i++ {
//满足条件则插入
for j := i - step; j >= 0 && nums[j+step] < nums[j]; j -= step {
nums[j], nums[j+step] = nums[j+step], nums[j]
}
}
}
return nums
}
希尔排序PASCAL
const size=12;
type arr=array[1..size]ofinteger;
var a:arr; i,j,k,t:integer;
procedure DataInput;//生成随机数列
begin
randomize;
for i:=1 to size do
begin
a[i]:=random(99)+1;
write(a[i]:3);
end;
writeln;
end;
procedure DataOutput;//输出
begin
for i:=1 to size do write(a[i]:3);
end;
procedure insertionsort(var a:arr);
begin
for i:=2 to size do
begin
t:=a[i];
j:=i-1;
while (j>0) and (t<a[j]) do
begin
a[j+1]:=a[j];
j:=j-1;
end;
a[j+1]:=t;
end;
end;
begin
DataInput;
k:=size;
while k>1 do
begin
k:=k div 2;
for j:=k+1 to size do
begin
t:=a[j];
i:=j-k;
while (i>0) and (a[i]>t) do
begin
a[i+k]:=a[i];
i:=i-k;
end;
a[i+k]:=t;
end;
end;
DataOutput;
end.