精华内容
下载资源
问答
  • 希尔排序C语言实现

    2014-02-18 21:50:16
    希尔排序C语言实现完整代码,可在VC6平台上运行。
  • 希尔排序C语言

    2016-02-18 19:14:25
    希尔排序C语言实现,这里提供给大家,很好用!
  • 希尔排序c语言实现

    千次阅读 2017-10-18 11:48:48
    希尔排序c语言实现

    希尔排序 希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。直接插入排序 有一个问题如果待排序列中,顺序恰好是逆序,如果用直接插入排序,那将耗费大量的代价,每次都要移动大量 数据,付出非常惨重的代价。 因此 就诞生了 希尔排序, 这个排序方法,可以算是对 插入的一种改进。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。


    排序思想: 先把 待排序列 分成若干组,对这若干组进行 插入排序,这样就 一部分 就先有序了, 之后 对这个组 在重新 划分 更小的若干组,进行插入排序, 直到组为1 的时候,退化为  直接插入排序。 




    初始时,有一个大小为 15 的无序序列。
    (1)在第一趟排序中,我们不妨设 gap1 = N / 2 = 7,即相隔距离为 7 的元素组成一组,可以分为 5 组。
    (2)接下来,按照直接插入排序的方法对每个组进行排序。
    在第二趟排序中,我们把上次的 gap 缩小一半,即 gap2 = gap1 / 2 = 3 (取整数)。这样每相隔距离为 2 的元素组成一组,可以分为 2 组。
    (3)按照直接插入排序的方法对每个组进行排序。
    (4)在第三趟排序中,再次把 gap 缩小一半,即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组,即只有一组。
    (5)按照直接插入排序的方法对每个组进行排序。此时,排序已经结束。

    下面 看一个例子:

    int arr[]={1,34,6,21,98,31,7,4,36,16,47,67,37,25,2}
    len=15 ,  gap=len/2
    相同颜色代表一组.

    1    4  2

    34   36

    6    16

    21   47

    98   67 

    31   37

    7    25
     
     

    先 组内 排序 为: {1 2 4},{34 36},{6 16},{21 47},{67 98},{31 37},{7 25}

    
    




    下面看代码:

    第一种实现 如下:

    d  就是 gap  这个变量 


    #include "stdio.h"
    #include "stdlib.h"
    #include "string.h"
    
    void printArray(int array[], int len)
    {
        int i = 0;
        for(i=0; i<len; i++)
        {
            printf("%d ", array[i]);
        }
    
        printf("\n");
    }
    
    
    
    void  shell_sort(int array[], int len){
        int d = len;
        while (1){
            d = d/2;
            for (int x=0;x<d;x++){
                for (int i = x+d; i < len; i=i+d)
                {
                    
                    int  k = i ;
                    int temp = array[k];
                    for (int j = i-d;j>=0 && array[j]>temp;j =j-d)
                    {
                       array[j+d] =array[j];
                       k = j ;
                    }
                    array[k] = temp ;
                }
                
            }
            if (d ==1)//gap==1,跳出循环  
            {
                break;
            }
        }
    }
    
    
    int main()
    {
        
       
        int array[]={1,34,6,21,98,31,7,4,36,25,2};
        int len = sizeof(array) / sizeof(*array); 
    
        //printArray(array, len);
        shell_sort(array, len);
        printArray(array, len);
    
        system("pause");
        return 0;
    }

    看看第二种实现

    把 组内排序 写成一个函数 ,这样看的更清楚一些。

    #include "stdio.h"
    #include "stdlib.h"
    
    void printArray(int array[], int len)
    {
    	int i = 0;
    	for(i=0; i<len; i++)
    	{
    		printf("%d ", array[i]);
    	}
    
    	printf("\n");
    }
    
    
    void group_sort(int  array[], int len, int d,int x){
        /*
            array 数组的指针
            len   数组的长度
            d     组的步长 gap 
    	x     组的起始位置
        */
        for (int i = x+d; i < len; i=i+d)
        {
            int  k = i ;
            int temp = array[k];
            for (int j = i-d;j>=0 && array[j]>temp;j=j-d)
            {
               array[j+d] =array[j];
               k = j ;
            }
            array[k] = temp ;
        }
    
    }
    
    
    
    
    /*
     * 希尔排序
     *
     * 参数说明:
     *     array -- 待排序的数组
     *     len -- 数组的长度
     */
    void shell_sort(int array[], int len)
    {
        int i,gap;
    
        // gap为步长,每次减为原来的一半。
        for (gap = len / 2; gap > 0; gap /= 2)
        {
            // 共gap个组,对每一组都执行直接插入排序
            for (i = 0 ;i < gap; i++){
    	    group_sort(array, len,  gap,i);
    	}
            
        }
    }
    
    
    
    int main()
    {
    	int array[]={1,34,6,21,98,31,7,4,36,25,2};
    	int len = sizeof(array) / sizeof(*array); 
    	//printArray(array, len);
    	shell_sort(array, len);
    	printArray(array, len);
    
    	system("pause");
    	return 0;
    }
    

    结果如下:




    总结: 希尔排序 在一定程度 上减少了 交换次数, 但是这个和d 的递减因子有关。非常牛逼的算法,在此记录一下,如果有疑问可以一起讨论,交流。


    参考文档:

    c语言实现 shell 排序 
    http://www.cnblogs.com/denglw/p/6785654.html
    希尔排序算法(排序详解) java 实现 
    http://blog.csdn.net/qq845579063/article/details/51447404
    希尔排序详解
    http://blog.csdn.net/z3881006/article/details/61922109
    http://www.cnblogs.com/chengxiao/p/6104371.html  
    希尔排序 http://blog.csdn.net/MoreWindows/article/details/6668714   
    白话shell排序 http://www.cnblogs.com/skywang12345/p/3597597.html#a1




           分享快乐,留住感动。           2017年 10月 18日 星期三 12:21:13   ----biaoge             

    展开全文
  • 希尔排序C语言实现(源代码)

    千次阅读 2020-10-18 20:49:49
    对一个元素个数为20个的随机数组进行希尔排序 #include <stdio.h> #include <stdlib.h> #include <time.h> void swap(int &a, int &b){ int tmp = a; a = b; b = tmp; } void ...

    希尔排序

    对一个元素个数为20个的随机数组进行希尔排序

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    void swap(int &a, int &b){
        int tmp = a;
        a = b;
        b = tmp;
    }
    
    void Display(int *a, int n){
    	for (register int i = 0; i < n; i++){
    		printf("%d ", a[i]);
    	}
    	printf("\n");
    }
    void shellsort(int *a, int n){
    	register int i, j, k;
    	int cur, gap;
    	for (gap = n / 2; gap > 0; gap /= 2){//步长的选取
    		printf("希尔排序的步长为:%d\n", gap);
            for (i = 0; i < gap; i++){
    			//接下来就是插入排序
                for (j = i + gap; j < n; j += gap){//每次加上步长
                    if (a[j] < a[j - gap]){
                        cur = a[j];
                        k = j - gap;
                        while (k >= 0 && a[k] > cur){//记录后移,查找插入位置
                            a[k + gap] = a[k];
                            k -= gap;
                        }
                        a[k + gap] = cur;//找到位置插入
                    }
            	}
    			printf("第%d次插入排序:   ", i + 1);
    			Display(a, n);	
            }
            //Display(a, n);
        }
    }
    
    int main() {
        int a[20];
    	//生成一个有20个元素的随机数组
    	srand((unsigned int)time(0));//修改种子
    	for (register int i = 0; i < 20; i++){	
    		a[i] = rand();
    	}
        printf("排序之前数组:   ");
       	Display(a, 15);
       	printf("\n");
        //希尔排序
        shellsort(a, 15);
        printf("\n希尔排序后数组:  ");
        Display(a, 15);
    	return 0;
    }
    

    如有不足,欢迎各位大佬指正

    展开全文
  • 希尔排序 C语言实现

    千次阅读 2020-11-19 18:37:52
    希尔排序 希尔排序( Shell’s Sort)又称“缩小增量排序”( Diminishing Increment Sort),是插入排序的一种, 因D.L.Shell 于1959 年提出而得名。 直接插人排序,当待排序的记录个数较少且待排序序列的关键字基本...

    希尔排序

    希尔排序( Shell’s Sort)又称“缩小增量排序”( Diminishing Increment Sort),是插入排序的一种, 因D.L.Shell 于1959 年提出而得名。
    直接插人排序,当待排序的记录个数较少且待排序序列的关键字基本有序时,效率较高。希尔排序基于以上两点,从“减少记录个数”和“序列基本有序”两个方面对直接插入排序进行了改进。

    基本思想:

    先将整个待排记录序列分割成若干子序列,分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。

    希尔排序算法,特点:

    1)缩小增量
    2)多遍插入排序

    算法步骤:

    希尔排序实质上是采用分组插人的方法。先将整个待排序记录序列分割成几组,从而减少参与直接插入排序的数据量,对每组分别进行直接插人排序,然后增加每组的数据量,重新分组。这样当经过几次分组排序后,整个序列中的记录“基本有序”时,再对全体记录进行一次直接插人排序。
    希尔对记录的分组,不是简单地“逐段分割”,而是将相隔某个“增量”的记录分成一组。

    (1)第一趟取增量 d 1 d_1 d1 ( d 1 d_1 d1<n)把全部记录分成 d 1 d_1 d1个组,所有间隔为 d 1 d_1 d1的记录分在同一组,在各个组中进行直接插人排序。
    (2)第二趟取增量 d 2 d_2 d2 ( d 2 d_2 d2< d 1 d_1 d1), 重复上述的分组和排序。
    (3)依次类推,直到所取的增量 d t d_t dt=1 ( d t d_t dt< d t − 1 d_{t-1} dt1<…< d 2 d_2 d2< d 1 d_1 d1), 所有记录在同一组中进行直接插入排序为止。
    在这里插入图片描述
    时间复杂度

    O( n 1.3 n^{1.3} n1.3)

    空间复杂度

    O(1)

    稳定性

    不稳定 (如图中“上划线49”和“49”的相对位置在排序前后变了,故不稳定)

    完整代码如下:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXSIZE 100  //顺序表最大容量,可以自行加大 
    
    typedef struct 
    {
    	int key;//关键字项 
    	char *otherinfo;//其他数据项 
    }ElemType;//记录类型 
    typedef struct
    {
    	ElemType Data[MAXSIZE+1];//静态顺序表的数据域,这里Data[0]为空闲或者为哨兵单元 
    	int length;//顺序表的长度 
    }SqList;//顺序表 
    
    void InitList(SqList &L)//顺序表的初始化 
    {
    	L.length = 0;//使顺序表长度归0,便是顺序表的初始化 
    }
    
    void CreateList(SqList &L)//顺序表的创建 
    {
    	printf("请输入:"); 
    	while(1)//建立一个死循环,循环终止条件是按了enter键 
    	{
    		L.length++;//顺序表长度加一 
    		if(L.length>MAXSIZE)//判断是否超出最大容纳量 
    		{
    			printf("顺序表已满!\n");
    			return ;
    		}
    		scanf("%d",&L.Data[L.length].key);//顺序表数据的输入 
    		if(getchar() == '\n')//循环终止条件 
    			break;
    	}
    }
    
    void InputList(SqList L)//顺序表的输出 
    {
    	int i;//记录次数 
    	if(L.length == 0)//判断顺序表是否为空 ,若为空结束该函数 
    	{
    		printf("顺序表是空的!\n");
    		return ;
    	}
    	printf("打印为:");
    	for(i=1;i<=L.length;i++)//利用循环打印顺序表中的数据 
    		printf("%d ",L.Data[i].key);	
    }
    
    void ShellInsert(SqList &L,int dk)//对顺序表L做一趟增量是dk的希尔插入排序 ,当dk==1时为直接插入排序 
    {
    	int i,j;//i和j为数据位置 
    	for(i=dk+1;i<=L.length;i=i+dk)//利用循环将Data[i]逐个插入到有序子表 
    	{
    		if(L.Data[i].key < L.Data[i-dk].key)//判断第i个和i-dk个数据的大小,若小于,需将Data[i]插入有序子表中 
    		{
    			L.Data[0] = L.Data[i];//将待插入的记录在监视哨中 
    			L.Data[i] = L.Data[i-dk];//Data[i-dk]后移 
    			for(j=i-2*dk;j>0&&L.Data[0].key<L.Data[j].key;j=j-dk)//从后往前寻找插入位置
    				L.Data[j+dk] = L.Data[j];//记录逐个后移,直到找到插入位置 
    			L.Data[j+dk] = L.Data[0];//将Data[0]即Data[i],插入到正确位置 
    		}
    	}
    }
    void SSort(SqList &L,int dt[],int t)//按增量序列dt[0…t-1]对顺序表L作t趟希尔排序 
    {
    	int k;//次数 
    	for(k=0;k<t;k++)//共t趟,t次循环 
    		ShellInsert(L,dt[k]);//一趟增量为dt[k]的希尔排序 
    }
    void ShellSort(SqList &L)//对顺序表做希尔排序 
    {
    	int t = 3,//排序的趟数,可更改 
    		dt[] = {5,3,1};//各趟排序的增量序列,可更改 
    	SSort(L,dt,t);//进入增量序列dt[0…t-1]对顺序表L作t趟希尔排序 
    } 
    
    int main()
    {
    	SqList L;
    	InitList(L);//初始化顺序表 
    	CreateList(L);//创建顺序表 
    	ShellSort(L);//希尔排序 
    	InputList(L);//打印排序后结果 
    	return 0;
    }
    
    

    在这里插入图片描述
    (完)

    展开全文
  • 附件提供的是C语言实现的希尔排序的代码,同时提供了代码实现的结果
  • 希尔排序C语言描述

    2021-05-31 11:47:34
    希尔排序: #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<string.h> #include<stdlib.h> #include<time.h> #include<sys/timeb.h> #define MAX 10 long ...

    希尔排序:

    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<time.h>
    #include<sys/timeb.h>
    #define MAX 10
    long getSystemTime()
    {
            struct timeb tb;
            ftime(&tb);
            return tb.time * 1000 + tb.millitm;
    }
    //交换函数
    void Swap(int *a, int* b)
    {
            int temp = *a;
            *a = *b;
            *b = temp;
    }
    //打印函数
    void PrintArray(int arr[], int length)
    {
            for (int i = 0; i < length; i++)
            {
                   printf("%d ", arr[i]);
            }
            printf("\n");
    }
    //从小到大     希尔排序
    void ShellSort(int arr[], int length)
    {
            int increasement = length;
            int i,j,k;
            do
            {
                   //确定分组的增量
                   increasement = increasement / 3 + 1;
                   for (i = 0; i < increasement; i++)
                   {
                           for (j = i + increasement; j < length; j += increasement)
                           {
                                  if (arr[j] < arr[j - increasement])
                                  {
                                          int temp = arr[j];
                                          for (k = j - increasement; k >= 0 && temp < arr[k];  k -= increasement)
                                          {
                                                 arr[k + increasement] = arr[k];
                                          }
                                          arr[k + increasement] = temp;
                                  }
                           }
                   }
            } while (increasement > 1);
    }
    int main()
    {
            int arr[MAX];
            srand((unsigned int)time(NULL));
            for (int i = 0; i < MAX; i++)
            {
                   int randNum = rand() % MAX;
                   arr[i] = randNum;
            }
            PrintArray(arr, MAX);
            ShellSort(arr, MAX);
            PrintArray(arr, MAX);
            return EXIT_SUCCESS;
    }
    
    展开全文
  • 程序实现希尔排序C语言入门程序,适合C语言课程入门的小练习。 程序实现希尔排序C语言入门程序,适合C语言课程入门的小练习。 程序实现希尔排序C语言入门程序,适合C语言课程入门的小练习。
  • 【算法】希尔排序C语言实现

    万次阅读 多人点赞 2015-02-06 14:20:13
    上一篇文章我们一起学习了直接插入排序,它的原理就是把前i个长度的序列变成有序序列,然后循环迭代,直至整个序列都变为有序的.但是说来说去它还是一个时间复杂度为(n^2)的算法,难道就不能再进一步把时间复杂度降低...
  • 希尔排序c语言

    2013-07-04 23:24:45
    排序类型 希尔排序 c语言 数据结构 使用方便简洁
  • 希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即...
  • 希尔排序(C语言简单实现)

    千次阅读 2020-11-29 17:32:40
    希尔排序(C语言简单实现) 希尔排序是直接插入排序的升级版,直接插入排序每次增量是1,但希尔排序的增量increment比1大,也就是说直接插入排序是一个一个比较的,但是希尔排序是跳着来的,从而实现顺序表的基本有序...
  • 希尔排序C语言详解

    2020-03-29 11:08:58
    编译环境:vc6.0 /* 给数组a[]排序,a[0]空着,作为整理牌时的临时存储空间,类似于swap...//*************************希尔排序****************** void ShellSort(int a[]) { int i, j; int increment = 11; ...
  • 希尔排序 希尔排序(Shellsort),也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 1.插入排序在对几乎已经排好序的...
  • 希尔排序(C语言)

    千次阅读 2020-06-12 18:13:51
    希尔排序 希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而...
  • 希尔排序(C语言实现)

    万次阅读 多人点赞 2018-01-21 10:52:46
      希尔排序是特殊的插入排序,直接插入排序每次插入前的遍历步长为1,而希尔排序是将待排序列分为若干个子序列,对这些子序列分别进行直接插入排序,当每个子序列长度为1时,再进行一次直接插入排序时,结果一定是...
  • 希尔排序 C语言

    2014-03-08 23:17:42
    C语言希尔排序算法完成代码,欢迎交流讨论
  • 希尔排序算法(C语言实现)

    万次阅读 热门讨论 2018-03-19 15:45:20
    希尔排序算法demo
  • 希尔排序C语言实现)算法思想程序 算法思想 见:2. 插入排序—希尔排序(Shell`s Sort) 程序 //从大到小排序 void ShellSort(int a[], int n) { int i, j, increment, tem; //序列分割成若干子序列 for ...
  •  希尔排序的排序效率和选择步长序列有直接关系,从length逐步减半,这还不算最快的希尔,有几个增量在实践中表现更出色,具体可以看weiss的数据结构书,同时里面有希尔排序复杂度的证明,但是涉及组合数学和数论,...
  • 希尔排序(C语言版)

    2019-08-23 17:19:07
    1.希尔排序( 缩小增量排序 ) 希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个 组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复...
  • #include<...直至跳数为1,也就是对所有数据进行一次插入排序(因为经过前面的操作,全体数据已变的基本有序),从而缩短时间 */ #define MAX 10 void Shell_sort(int a[], int length) { int step = le
  • 希尔排序C语言代码

    千次阅读 2013-01-04 10:06:45
     *希尔排序  */ #include #include #include #define LEN 10 typedef int dataType; //初始化数组,赋值整数随机数 void initArr(dataType arr[], int len); //希尔排序 void shellSort(dataType arr[],...
  • C语言实现希尔排序

    2020-04-15 22:42:29
    希尔排序 它是通ag过比较相距一定间隔的元素来工作的,各趟比较所用的的距离随着算法的进行而减小,知道只比较相邻元素的最后一趟排序为止。由于这个原因,希尔排序有时也叫做缩小增量排序。 希尔排序使用一个序列...
  • 1) 至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文件中。 2) 统计每一种排序方法的性能(以上机...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,582
精华内容 2,232
关键字:

希尔排序c语言

c语言 订阅