(十)数据结构之希尔排序算法实现

太过爱你忘了你带给我的痛 2022-06-08 06:27 204阅读 0赞

## 1、希尔排序 ##

希尔排序是对插入排序的一种改进，插入排序的实现可以参考这篇文章[http://blog.csdn.net/tech\_pro/article/details/78016096][http_blog.csdn.net_tech_pro_article_details_78016096]。希尔排序具体实现如下：

/* 原始希尔排序 */
    void Shell_sort( ElementType A[], int N )
    { 
    	int D, P, i;
    	ElementType Tmp;
    	for ( D=N/2; D>0; D/=2 ) 
    	{ 
    		/* 希尔增量序列*/
    		for ( P=D; P<N; P++ ) 
    		{
    			/* 插入排序*/
    			Tmp = A[P];
    			for ( i=P; i>=D && A[i-D]>Tmp; i-=D )
    				A[i] = A[i-D];
    			A[i] = Tmp;
    		}
    	}
    }

## 2、完整示例代码 ##

/* 原始希尔排序的简单实现 */
    #include <stdio.h>
    
    /* 定义一些辅助数据结构或者类型 */
    typedef int ElementType;
    
    /* 原始希尔排序 */
    void Shell_sort( ElementType A[], int N )
    { 
    	int D, P, i;
    	ElementType Tmp;
    	for ( D=N/2; D>0; D/=2 ) 
    	{ 
    		/* 希尔增量序列*/
    		for ( P=D; P<N; P++ ) 
    		{
    			/* 插入排序*/
    			Tmp = A[P];
    			for ( i=P; i>=D && A[i-D]>Tmp; i-=D )
    				A[i] = A[i-D];
    			A[i] = Tmp;
    		}
    	}
    }
    
    /* 程序入口 */
    int main()
    {
    	int i;
    	ElementType temp;
    	ElementType array[10];
    
    	printf("Input 10 numbers : ");
    	for(i = 0; i < 10; i++)
    	{
    		scanf("%d", &temp);
    		array[i] = temp;
    	}
    
    	/* 原始数据输出 */
    	printf("***********************************Origin************************************\n");
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    
    	/* 希尔排序后输出 */
    	printf("***********************************Shell*************************************\n");
    	Shell_sort(array, sizeof(array)/sizeof(array[0]));
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    
    	return 0;
    }

[http_blog.csdn.net_tech_pro_article_details_78016096]: http://blog.csdn.net/tech_pro/article/details/78016096