【算法】希尔排序

 导读 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

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

JavaScript

```function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap  0; gap = Math.floor(gap/3)) {
for (var i = gap; i = 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  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  0 {
for i := gap; i = 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 = 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  0; \$gap = floor(\$gap / 3)) {
for (\$i = \$gap; \$i = 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 = 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 = 1) {
for (int i = h; i = h && array[j]```