什么是希尔排序法

基本思想：
将整个无序序列分割成若干小的子序列分别进行插入排序。
序列分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。增量序列一般采用：ht=2t-1,1≤t≤[log2n]，其中n为待排序序列的长度。
void prshl(p,n)
int n;double p[];
{
int k,j,i;
double t;
k=n/2;
while(k>0)
{
for(j=k;j<=n-1;j++)
{
t=p[j];i=j-k;
while((i>=0)&&(p[i]>t))
{
p[i+k]=p[i];i=i-k;
}
p[i+k]=t;
}
k=k/2;
}
return;
}
希尔排序(缩小增量法)
属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序
排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序 *** 作；直至di=1，即所有记录放进一个组中排序为止

初始：d＝5
49 38 65 97 76 13 27 49 55 04
|---------------|
38 27
|--------------|
65 49
|--------------|
97 55
|---------------|
|76-------------04|
一趟结果

d=3 13 27 4955 04 49 38 65 97 76
|--------|--------|----------|
27 04 65
|--------|-------|
49 49 97
|--------|---------|
二趟结果
13 04 4938 27 49 66 65 97 76
d=1
三趟结果
04 13 27 38 4949 55 65 76 97

希尔排序的算法思想 先将整个待排序元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的），分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。 希尔排序算法 void ShellInsert(SqList &L,int dk) {//对顺序表L作一趟希尔排序 for(i = 2; i <= Length; i++) if (Lr[i]key < Lr[i-1]key) { Lr[0] = Lr[i]; Lr[i] = L[i-1]; for(j = i - 2; Lr[0]key < Lr[j]key]; j--) Lr[j+1] = Lr[j]; Lr[j+1] = Lr[0]; }//if } //ShellInsertSort void ShellInsert(SqList &L,int dk) {//对顺序表L作一趟希尔排序 } //ShellInsertSort void ShellSort(SqList &L,int dlta[],int t) { //按增量序列dlta[0t-1]进行希尔排序 for(k = 0; k < t; k++) ShellInsert(L,dlta[k]); //一趟增量为dlta[k]的希尔排序 } //ShellInsertSort

既然议论纷纷我就说下我得见解

｛9,38,65,36,76,13,27,49,11,4｝一共10个数，一般取10/2=5为增量

分为5个组：(s1,s6),(s2,s7),(s3,s8),(s4,s9),(s5,s10)

其中每一组中分别进行比较大小，左边大于右边的就互换，反之不变

如图

那么增量为5的排序结果为：9 27 49 11 4 13 38 65 36 76

其他趟分别使增量减1进行比较，直到全部集中在一组就行了，不赘述了

example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}example-btn:active{background-image:none}divexample{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}divexample_code{line-height:14em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}divexample_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}divcode{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}divcode div{font-size:110%}divcode div,divcode p,divexample_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是希尔排序算法：

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

希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据 *** 作时，效率高，即可以达到线性排序的效率； 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
1 算法步骤
选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 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 < length / 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 ] 0) { for (int i = gap; i arrLength; i++) { int tmp = arr[i]; int j = i - gap; while (j >= 0 && arr[j] > tmp) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = tmp; } gap /= 3; } } 以上为希尔排序算法详细介绍，插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点，用一张图概括：
关于时间复杂度

平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

n：数据规模

k："桶"的个数

In-place：占用常数内存，不占用额外内存

Out-place：占用额外内存

稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。我们来通过演示图，更深入的理解一下这个过程。

希尔排列

希尔排序又叫递减增量排序算法，它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的；希尔排序是一种不稳定的排序算法。希尔排序由唐纳德·希尔（Donald Shell）发明并于1959年公布，因此得名希尔排序。

希尔算法

---