算法： 希尔排序

算法步骤

选择一个增量序列 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  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 < gap/3 {                 gap = gap*3 + 1         }         for gap > 0 {                 for i := gap; i < length; i++ {                         temp := arr[i]                         j := i - gap                         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 = 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]