希尔排序

希尔排序相当于直接插入排序的升级(分组插入排序),又称缩小增量排序,同属于插入排序类,不是稳定的排序算法。
比直接插入排序快的原因:

  1. 刚开始的时候间隔较大, 每个组里面的数据较少,排序很快
  2. 当分隔加大的时候, 每组的数据变多, 但是因为已经有了前面的工作,数据接近于有序, 所以也很快

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

C++代码

/**********************************/
/***********希尔排序***************/
/**********************************/
void ShellSort(ElemType a[],int n)
{
	int i,j;
	int increment = n;
	do
	{
		increment = increment/3+1;//增量序列
		for(i = increment+1;i<=n;i++)
		{
			if(a[i] < a[i-increment])
			{
				int tmp = a[i];
				for(j = i-increment;j > 0 && tmp < a[j];j -= increment)
					a[j+increment] = a[j];
				a[j+increment] = tmp;
			}
		}
	}
	while(increment > 1);
}

Python代码

#--------------#
#--Shell sort--#
#--------------#
def shell_sort(arr):
		increment = len(arr);

		while increment > 1:
				increment = increment/3+1
				shell_pass(arr,increment)

def shell_pass(arr,increment):
		arrlen = len(arr)
		#for every subsequence which interval is increment
		for i in range(increment,arrlen):
				#keep value of arr[i],later may be changed by arr[i-increment]
				tmp = arr[i]
				k = i
				while k >= increment and arr[k-increment] > tmp:
						arr[k] = arr[k - increment]
						k -= increment
				arr[k] = tmp

希尔排序复杂度分析:
增量大小对效率影响非常大,现选用increment=increment/3+1的增量,时间复杂度为O(n^3/2),增量序列的最后一个增量值必须等于1.

 

Leave a Reply

Your email address will not be published. Required fields are marked *