排序4:希尔排序_初始步长为4的希尔排序

一.概述

希尔排序: 又称缩小增量排序，对一组数据按照间隔分组后，对每一组数据进行 【直接插入排序】，它也是插入排序的一种—加强版本。

 

二.算法思想

(1)间隔 Gap计算 ： 设一组无序数列的长度为 len ,Gap也就是说这组数据分几组。

设gap[] = {gap1,gap2,gap….,1}

gap1 = len /2 ； 求整

gap2 = gap1 /2 ; 继续往后

要求，最有一位必须为 1

(2) 把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。

(3)随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

(4) 设一组无序数据：9 1 2 5 7 5 8 6 3 5，进行希尔排序

Len = 10 ;

Gap 1 = 10 /2 = 5 ; 分为五组，每组两个元素之间 下标之差为 5

Gap2 = 5 / 2 = 2 余 1 （余数不用管） 分为2组，每组两个元素之间 下标之差为2

Gap3 = 2 /2 =1 ; 当模值为1，说明取到了最后一位。同上

具体过程如下所示

 

三.代码实现

 

#include<stdio.h>
//希尔排序
//对元素进行分组  gap 间隔   数据元素/2  取整    第二次  新的元素/2  取整
//每个间隔组内进行  【 直接插入排序 】
 
void shell(int *arr,int len ,int gap)
{
	int temp = 0;
	int j  = 0;
	for(int i = gap ;i<len;++i)  //相对而言每组的第一个开始
	{
		temp = arr[i];
		for( j =i-gap;j>=0;j=j-gap)
		{
			if(arr[j]>temp)
			{
				arr[j+gap] = arr[j];
			}
			else
			{
				break;
			}
		}
		arr[j+gap] = temp;
	}
 
}
 
void shellsort(int*arr,int len)
{
	//计算好的数值放进GapArr里面，而不要用户手动输入gap每次的值
	int GapArr[4] = {0}; //初始化一个数组里面放每次的Gap
	int GapLen = 0;
	 int num = len;
	for(int i = 0; i <4 ;++i)
	{
		 num/=2;  //gap = len /2  的 模 的值 
		 if(num !=1)
		 {
			 GapArr[i] = num;
			 ++GapLen;
		 }
		 else
		 {
			 GapArr[i] = 1;  //结束位为1  所以当遇到gap==1后，  设置最后一个Gap为 1，length++ ； 跳出循环 
			 ++GapLen;
			 break;
		 }
	}
 
	for(int i = 0;i<GapLen;++i)
	{
		shell(arr,len,GapArr[i]);
	}
}
 
 
void show(int *arr,int len)
{
	for(int i =0;i<len;++i)
	{
		printf("%d\t",arr[i]);
	}
}
 
int main()
{
	int brr[] = {1,2,3,4,5,6,100,200,42};
	int len = sizeof(brr)/sizeof(brr[0]);
	shellsort(brr,len);
	show(brr,len);
	getchar();
	return 0;
}

 

四.时间复杂度与空间复杂度

                                                    希尔排序相等位置可能会交换位置，因此是一种不稳定的排序方法。