希尔排序

希尔排序的时间复杂度,最好的情况下仍然是正序时,可达到O(n),平均复杂度为O(nlogn)。

算法思想:

采用跳跃式处理数组,使得数组粗粒度的实现基本有序。在进行细粒度的处理,最终使得网络在跳越数为1时,实现基本有序的排序,以减少插入排序的复杂度。

主要程序:

void shellSort(int *arr,int length){
    int i,j,k;
    int increment = length;
    while(increment>0){
        if(increment != 1)
            increment = increment/3+1;
        else
            break;
        for(i = increment; i<length; i++){
            if(arr[i] < arr[i-increment]){
                k = arr[i];
                for(j=i-increment; j>=0 && k < arr[j] ; j-=increment){
                    arr[j+increment] = arr[j];
                }
                arr[j+increment] = k;
            }
        }
    }
}

全部代码:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int arrtest1[10] = {3,4,7,8,0,9,1,2,6,5};
int arrtest2[10] = {0,1,2,3,4,5,6,7,8,9};
int arrtest3[10] = {9,8,7,6,5,4,3,2,1,0};
void copy(int *from,int *arr,int length);
void print(int *arr,int length);
void shellSort(int *arr,int length);
int main(){
    clock_t start,end;
    int Arr[10];
    int i;
    copy(arrtest1,Arr,10);
    print(Arr,10);
    shellSort(Arr,10);
    print(Arr,10);
    start = clock();
    for(i=0;i<100000;i++){
        copy(arrtest1,Arr,10);
        //print(Arr,10);
        shellSort(Arr,10);
        //print(Arr,10);
    }
    end = clock();
    printf("first test:%d\n",end-start);

    start = clock();
    for(i=0;i<100000;i++){
        copy(arrtest2,Arr,10);
        //print(Arr,10);
        shellSort(Arr,10);
        //print(Arr,10);
    }
    end = clock();
    printf("first test:%d\n",end-start);

    start = clock();
    for(i=0;i<100000;i++){
        copy(arrtest3,Arr,10);
        //print(Arr,10);
        shellSort(Arr,10);
        //print(Arr,10);
    }
    end = clock();
    printf("first test:%d\n",end-start);
    
    getchar();
    return 0;
}
void shellSort(int *arr,int length){
    int i,j,k;
    int increment = length;
    while(increment>0){
        if(increment != 1)
            increment = increment/3+1;
        else
            break;
        for(i = increment; i<length; i++){
            if(arr[i] < arr[i-increment]){
                k = arr[i];
                for(j=i-increment; j>=0 && k < arr[j] ; j-=increment){
                    arr[j+increment] = arr[j];
                }
                arr[j+increment] = k;
            }
        }
    }
}
void copy(int *from,int *arr,int length){
    int i;
    for(i=0;i<length;i++){
        arr[i] = from[i];
    }
}

void print(int *arr,int length){
    int i;
    for(i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
}

运行示例:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏十月梦想

多个Promise对象的处理

如果某件事情需要依照多个对象完成后才能执行,那么我们可以使用Promise.all来管理,将这些状态全部执行完毕后才执行下一个!

18510
来自专栏前端儿

使用BEM命名规范来组织CSS代码

在本规范中,以双下划线 __ 来作为块和元素的间隔,以单下划线 _ 来作为块和修饰器 或 元素和修饰器 的间隔,以中划线 - 来作为 块|元素|修饰器 名称中多...

17250
来自专栏同步博客

PHP定义字符串的四种方式

  我们在使用php进行开发的时候,大多数使用双引号、单引号进行定义字符串。既然有这两种方式,那么他们之间肯定是有区别的。

10620
来自专栏前端小叙

vue路由跳转报错解决

20340
来自专栏木子昭的博客

Javascript常用API备忘录

Bom常见API 获取浏览器信息 var ua = navigator.userAgent if (ua.indexOf('Chrome')){ co...

32730
来自专栏JAVA后端开发

vue解决字段类型为数字导致单选不正确的问题

最近在研究vue,也试着写一些Vue页面。 vue中,我返回一个值,"sex":0, 单选框代码为

83950
来自专栏自由而无用的灵魂的碎碎念

转: 细说HTML元素的ID和Name属性的区别

可以说几乎每个做过Web开发的人都问过,到底元素的ID和Name有什么区别阿?为什么有了ID还要有Name呢?! 而同样我们也可以得到最classical的答案...

14130
来自专栏向治洪

React 之props属性

React 里有一个非常常用的模式就是对组件做一层抽象。组件对外公开一个简单的属性(Props)来实现功能,但内部细节可能有非常复杂的实现。 可以使用 JSX ...

23750
来自专栏前端迷

头条秋招面试题以及答案

答案: 定义 3D 转换,只是用 Z 轴的值。 拓展: transform 属性向元素应用 2D 或 3D 转换。该属性允许我们对元素进行旋转、缩放、移动或倾斜...

14030
来自专栏互联网杂技

js事件

1.document.write(""); 输出语句 2.JS中的注释为// 3.传统的HTML文档顺序是:document->html->(head,body...

434110

扫码关注云+社区

领取腾讯云代金券