希尔排序

学习之后,自己练习手写一下排序算法,加深印象

原理:将相距某个“增量”的记录组成一个子序列,在各个子序列内分别进行直接插入排序后得到基本有序的结果。所谓基本有序,就是小的关键字在前面,大的基本在后面,不大不小的基本在中间,比如{2,1,3,6,4,7,5,8,9}就可以称为基本有序

#define MAXSIZE 10
#include <stdio.h>
struct a{
    int array[MAXSIZE];    //数组用于存储排序数据 
    int length;           //用于存储数组长度信息, 
};

void init_array(struct a *L){   //初始化数组 
    int i;
    L->length = MAXSIZE;
    for (i=1;i<L->length;i++){     //索引为0的项留作备用 
        scanf("%d",&(L->array[i]));
    }
}

void swap(struct a *L,int i,int j){   //交换数组项 
    int temp = L->array[i];
    L->array[i] = L->array[j];
    L->array[j] = temp;
}

void print(struct a *L){    //打印数组项 
    int i;
    for (i=1;i<L->length;i++){
        printf("%d ",L->array[i]);
    }
}

void ShellSort(struct a *L){   //排序算法 
    int i,j;
    int increment = L->length;   //增量初始化为序列的长度 
    do{
        increment = increment/2;    //增量减半 
        for (i=increment+1;i<L->length;i++){   //从第一个序列的第二个数开始,接着是第二个序列的第二个数 
            if (L->array[i] < L->array[i-increment]){  //如果第二个数比已排好序的序列最后一个数还要小,就执行插入操作 
                L->array[0] = L->array[i];  //暂存在索引为0的位置 
                for (j=i-increment;L->array[0] < L->array[j] && j > 0;j-=increment){  //寻找插入位置 
                    L->array[j+increment] = L->array[j];   //依次后移记录位置 
                }
                L->array[j+increment] = L->array[0];  //插入记录 
                printf("\n");
                print(L);    
            }
        }
    }while(increment > 1); //当增量为1时,排序完成 
} 

int main(){
    struct a List;
    init_array(&List);
    printf("排序前:");
    print(&List);
    ShellSort(&List);
    printf("\n排序后:");
    print(&List);
    return 0;
}

这里写图片描述

  • 可以看到,第一次循环时,增量为5,序列{9,1,5,8,3,7,4,6,2}被划分为{9,7},{1,4},{5,6},{8,2},{3},第一次循环结束后,子序列{9,7}和{8,2}被排序,最终整个序列为{7,1,5,2,3,9,4,6,8}。
  • 接着增量减半,变为2,整个序列又被重新划分为{7,5,3,4,8},{1,2,9,6},在第二次循环后变为{3,4,5,7,8},{1.2,6,9}也就是{3,1,4,2,5,6,7,9,8}。
  • 最后增量变为1,变成相邻元素之间的交换,排序完成。

算法时间复杂度:O(n3/2),增量的选取至关重要

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值