C/C++教程

排序算法-希尔排序(Shellsort)-C

本文主要是介绍排序算法-希尔排序(Shellsort)-C,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

思路:

希尔排序又称缩小增量排序(diminishing increment sort),

首先选择一个增量序列(increment sequence),h_{1},h_{2},...,h_{t},其中,h_{1}>h_{2}h_{t}=1

按增量序列的个数 t ,执行 t 趟排序;

对于每一趟排序,将h_{t},h_{t}+1,...,N-1 中的每一个位置i,把其上的元素放到i,i-h_{t},i-2h_{t},...中间的正确位置上,可以看出,对于一趟h_{t}增量的排序,就是对h_{t}个独立的子数组执行一次插入排序。

希尔排序一般的增量序列是,h_{1}=N/2,h_{2}=h_{1}/2,....,h_{t}=1

时间复杂度:

平均,O(n^{1.3});最好,O(n) ;最坏 ,O(n^{2})   (取决于选择的增量序列)

程序:

void shell_sort(int array[],int array_size)
{
    int increment,i,j,tmp;
    for(increment=array_size/2;increment>0;increment/=2)
    {   
        for(i=increment;i<array_size;i++)
        {   
            tmp=array[i];
            for(j=i;j-increment>=0 && tmp<array[j-increment];j-=increment)
            {   
                array[j]=array[j-increment];
            }   
            array[j]=tmp;   
        }   
    }   
}
#include <stdio.h>

int main()
{
    int i;  
    int array[]={100,96,88,75,63,52,41,36,28,19,6,0,-19,-105};
    int array_size=sizeof(array)/sizeof(int);
    printf("Original array:\n");
    for(i=0;i<array_size;i++)
        printf(" %d, ",array[i]);
    printf("\n");
    shell_sort(array,array_size);
    printf("Sorted array:\n");
    for(i=0;i<array_size;i++)
        printf(" %d, ",array[i]);
    printf("\n");
    return 0;
}

参考:

https://www.runoob.com/w3cnote/shell-sort.html

这篇关于排序算法-希尔排序(Shellsort)-C的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!