希尔排序

希尔排序是Shell在1959年提出的一种排序算法,它出现的重要意义在于,之前的排序算法基本都是O(n²),希尔算法是突破这个时间复杂度的第一批算法之一,所以它绝对值得我们了解掌握!

希尔排序的基本思想是:
把记录按increment(增量)分组,对每组记录采用直接插入排序方法进行排序。
随着增量逐渐减小,所分成的组包含的记录越来越多,当增量的值减小到 1 时,整个数据合成为一组,构成一组有序记录,则完成排序。

案例分析

假设我们要对一个数组进行希尔排序
这里写图片描述

分析:

这里写图片描述

第一轮:我们设置增量increment = 9/3+1,注意第6步,还要跟第一位相比较,结果为:2,1,4,6,3,7,5,8,9
第二轮:增量为缩小为2,距离为2的元素分为一组,结果为:2,1,3,6,4,7,5,8,9
第三轮:增量缩小为1,距离为1的元素分为一组,此时的排序已经完成,结果为:1,2,3,4,5,6,7,8,9

具体代码

>r[i]; 
    L->r[i] = L->r[j]; 
    L->r[j] = temp; 
} 
//希尔排序关键代码 
void shellSort(SqList *L){ 
    int i,j; 
    int increment = L->length; 
    do{ 
        increment = increment/3+1; //4 
        for(i=increment+1;i<=L->length;i++){ 
            if(L->r[i] < L->r[i - increment]){ 
                L->r[0] = L->r[i]; 
                //交换 L->r[i] 和 L->r[i - increment]的位置,这一步很关键 
                for(j = i - increment; j > 0 && L->r[0] < L->r[j]; j-=increment){ 
                    L->r[j+increment] = L->r[j]; 
                }  
                L->r[j+increment] = L->r[0]; 
            } 
        }  
    }while(increment > 1); 
} 
//初始化数组 
void initSort(SqList *L){ 
    L->length = MAXSIZE; 
    L->r[0] = 0; 
    int a[9] = {9,1,5,8,3,7,4,6,2} ; 
    for(int i = 1; i<MAXSIZE; i++){ 
        L->r[i] = a[i-1]; 
    } 
} 
//查询数组 
void searchSort(SqList *L){ 
    for(int i = 1; i < MAXSIZE; i++){ 
        printf("%d", L->r[i]); 
    } 
} 
 
int main(){ 
    SqList *L = new SqList; 
    initSort(L); 
    searchSort(L); 
    printf("\n"); 
    shellSort(L); 
    searchSort(L); 
    return 0; 
}

结果如下:

这里写图片描述

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

经典排序算法:冒泡排序(Bubble Sort)详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。