c语言希尔排序

void ShellInsertSort(int a[], int n, int dk)  

{  

    for(int i= dk i<n ++i){  

        if(a[i] < a[i-dk]){          //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入  

            int j = i-dk     

            int x = a[i]           //复制为哨兵，即存储待排序元素  

            a[i] = a[i-dk]         //首先后移一个元素  

 扒族           while(x < a[j]){     //查找在有序表的插入位置  

                a[j+dk] = a[j]  

                j -= dk             //元素后移  

            }  

            a[j+dk] = x            //插入到正确位置  

        }    

    }  

      

}  

  

/** 

 * 先按增春段弊量d（n/2,n为要排序数的个数进行希尔排序 

 * 

 */  

void shellSort(int a[], int n){  

  

    int dk = 燃念n/2  

    while( dk >= 1  ){  

        ShellInsertSort(a, n, dk)  

        dk = dk/2  

    }  

}

.example-btn{color:#fffbackground-color:#5cb85cborder-color:#4cae4c}.example-btn:hover{color:#fffbackground-color:#47a447border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%color:#000background-color:#f6f4f0background-color:#d0e69cbackground-color:#dcecb5background-color:#e5eeccmargin:0 0 5px 0padding:5pxborder:1px solid #d4d4d4background-image:-webkit-linear-gradient(#fff,#e5eecc 100px)background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4emwidth:98%background-color:#fffpadding:5pxborder:1px solid #d4d4d4font-size:110%font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospaceword-break:break-allword-wrap:break-word}div.example_result{background-color:#fffpadding:4pxborder:1px solid #d4d4d4width:98%}div.code{width:98%border:1px solid #d4d4d4background-color:#f6f4f0color:#444padding:5pxmargin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px autofont:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospacewhite-space:pre-wrapword-break:break-allword-wrap:break-wordborder:1px solid #dddborder-left-width:4pxpadding: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 = gapi arr.Lengthi++) { 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 个相等键值的顺序和排序之前它们的顺序相同

---