首页 / 算法 / 算法基础之希尔排序

算法基础之希尔排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法基础之希尔排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1448字，纯文字阅读大概需要3分钟。

内容图文

希尔排序的实质就是分组插入排序, 是对直接插入排序的改进。 时间复杂度为O(nlongn), 跟快速排序， 堆排序的时间复杂度相同， 是一种较为快速的排序方式。

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的 元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为 直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

希尔排序的C语言实现如下：

 

             1
            void Swap(int a[], int j, int gap) 
 2{
 3int temp = a[j];
 4     a[j] = a[j+gap];
 5     a[j+gap] = temp;
 6}
 7 8/* 希尔排序算法的C语言实现 */ 910void shell_sort(int a[], int n)
11{
12int i, j, gap;
13for (gap = n / 2; gap > 0; gap /= 2)
14       {
15for (i = gap; i < n; i++)
16            {
17for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
18                {
19                    Swap(a, j, gap);
20                }
21            }
22       }
23 }

一个简单的测试用例，代码如下：

技术分享 技术分享 
#include<stdio.h>

#define MAXSIZE 10

void Swap(int a[], int j, int gap) 
{
    int temp = a[j];
    a[j] = a[j+gap];
    a[j+gap] = temp;
}

/* 希尔排序算法的C语言实现 */void shell_sort(int a[], int n)
{
       int i, j, gap;
       for (gap = n / 2; gap > 0; gap /= 2)
       {
            for (i = gap; i < n; i++)
            {
                for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
                {
                    Swap(a, j, gap);
                }
            }
       }
}



int main()
{
    int a[MAXSIZE];
    int i;
    printf("Please input the num:\n");
    for(i=0; i<MAXSIZE; i++)
    {
        scanf("%d",&a[i]);
    }
    printf("before the sort:\n");
    for(i=0; i<MAXSIZE; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    
    shell_sort(a, MAXSIZE);

    printf("after the sort:\n");
    for(i=0; i<MAXSIZE; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}
View Code

 

原文：http://www.cnblogs.com/beyond-Acm/p/4354761.html

内容总结

以上是互联网集市为您收集整理的算法基础之希尔排序全部内容，希望文章能够帮你解决算法基础之希尔排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1214311.html

来源：【匿名】