首页 > 代码库 > 希尔排序

希尔排序

2024-07-10 15:38:10   220人阅读

希尔排序

通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。所以希尔排序也叫缩小增量排序。希尔排序使用一个序列h1，h2，....，hn，叫做增量序列，只要h1=1，任何增量序列都是可以的，不过有些增量序列比另外一些增量序列更好。在使用增量hk的一趟排序后，对于每一个i，我们有A[i] <= A[i+hk]，即所有相隔hk的元素都被排序，此时和排序文件是hk-排序的。希尔排序的一个重要性质是：一个hk-排序的文件保持它的hk-排序性。如果情况不是这样的话，希尔排序也就没有意义了。

hk-排序的一般做法是：对于hk，hk+1，...，N-1中的每一个位置i，把其上的元素放到i，i-hk，i-2*hk....中间的正确位置上。一趟hk排序的作用就是对hk个独立的子数组执行一次插入排序。

希尔排序的运行时间依赖于增量序列，但最坏情形下的运行时间为O(N^2)，但对于有些增量序列，其时间可减少到O(N^1.2)。以下是以增量序列：1，2，4，N/2的一种实现：

Shellsort.c

#include<stdio.h>typedef int ElementType;ElementType arr[10]={2,87,39,49,34,62,53,6,44,98};ElementType arr1[11]={0,2,87,39,49,34,62,53,6,44,98};void Shellsort(ElementType A[], int N){    int i, j, Increment;    ElementType Tmp;    for (Increment = N / 2; Increment > 0; Increment /= 2){        for (i = Increment; i < N; ++i){            Tmp = A[i];            for (j = i; j >= Increment; j -= Increment){                if(Tmp < A[j-Increment])                    A[j] = A[j - Increment];                else                    break;            }            A[j] = Tmp;        }    }}void Print(ElementType A[],int N){    int i;    for(i=0;i<N;i++)    {        printf(" %d ",A[i]);    }}int main(){    Print(arr,10);    printf("\n");    Shellsort(arr,10);    Print(arr,10);    printf("\n");    return 0;}

 

 


联系
我们