EEPW论坛

1、希尔排序简介

希尔排序，是插入排序的一种进阶排序算法，通过一个不断缩小的增量序列，对无序序列反复的进行拆分并且对拆分后的序列使用插入排序的一种算法，所以也叫作“缩小增量排序”或者“递减增量排序”。

既然希尔排序也是使用插入排序进行序列排序操作的，为什么会有希尔排序呢？

这是基于插入排序的两点性质而来：

第一：对一个“几乎”已经排好序的无序序列，插入排序的效率是很高的，可以达到线性排序的效率。比如，当序列中只有一位元素没有在适当的位置，那么整个序列只需要移动该序列的位置即可达到完成排序的任务。

第二：但是一般的无序序列不是一个“几乎”已经排好序的序列，所以插入排序是低效的。因为它每次只能移动一位元素。

基于以上两点出现了希尔排序，那么希尔排序到底如何利用了这两个性质呢？

2、希尔排序的步骤

首先根据初始序列的长度，选定一个递减增量序列t1，t2，t3......tk，其中ti>tj，tk = 1。

根据选定的增量序列元素个数k，对初始序列进行k趟排序。

根据增量序列的值ti，每趟排序会把初始序列划分成若干个元素的子序列，然后对这些子序列使用插入排序，因为这是递减增量序列，所以第一趟的排序，增量值最大，那么划分的子序列数量也就最多，每个子序列的元素也就越少，可以看做是一个“几乎”已经排好序的序列，当增量值越来越小的时候，子序列数量也就越少，每个子序列的元素也就越多，但是，基于前几次的排序，这些子序列虽然元素多，但是已经是一个“几乎”排好序的序列了，当最后一次排序的时候，即增量序列的值为1时，就是对整个无序序列进行排序，这时整个序列已经是一个“几乎”排好序的序列了。

讲了那么多理论知识，可能感觉比较枯燥，下面是代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int shell_sort(int arr[],int n)
{
    register int i, j, tmp;
    int step;
    for(step = n/2; step > 0;step /= 2)/*增量步长*/
    {
        /*step = 4 2 1*/
        for(i = step; i < n; i++)
        {
            tmp = arr[i];
            j = i - step;
            for(;j >= 0 && tmp < arr[j];)
            {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = tmp;
        }
    }
}
#define LENGTH 8
int main( int argc, int *argv[])
{
    int i;
    int arr[LENGTH] = {6,5,3,1,8,7,2,4};
    for(i=0;i<LENGTH;i++)
    printf("%d ",arr[i]);printf("\n");
    shell_sort(arr,LENGTH);
    for(i = 0;i < LENGTH;i++)
    printf("%d ", arr[i]);printf("\n");
}

今天就到这了，下次再见！