排序算法--shell排序

排序算法–shell排序

shell排序是优化后的插入排序，它是按照增量将数组逐渐划分为有序状态，数据慢慢趋于游戏，为缩减增量排序；

先取一个增量序列（例如：5,3,1）将一串需排序的数列先按照5分组，每组三个数。对每组三个数进行排序。接下来按照3分组，每组五个数。对每组五个数进行排序。接下来是1 也就是进行直接插入排序。

Shell排序的执行时间依赖于增量序列。

好的增量序列的共同特征:

① 最后一个增量必须为1;

② 应该互素。（ 应该尽量避免序列中的值(尤其是相邻的值）互为倍数的情况）

接下来我们来演示下增量排序模型–shell排序

第一步：

第二步：

第三步：

如果数组量大的情况下，我们可以明显的看出数组逐渐的趋于有序状态 ；希望大家可以自己学习学习
每次分组后的排序都适用于直接插入排序（直接插入排序适用于数组量小的情况）

下面给出代码示例：

#include <iostream>

using namespace std;

void Print(int arr[],int len)
{
	int i=0;
	for(i;i<len;i++)
	{
		cout<<arr[i]<<" ";
	}
	cout<<endl;
}

void Shell(int arr[],int len,int dk)
{
	//直接插入排序--将已经分好组的成员
	int tmp=0;
	//i为待排序部分 j已排序部分
	//第一组的元素为 3 4--》 
	//3的位置下标为0  4的下标为5（dk的位置）
	int j=dk;
	int i=j-dk;

	for(j=dk;j<len;j++)
	{
		tmp=arr[j];
		for(i=j-dk;i>=0 && arr[i]>tmp;)
		{
			arr[i+dk]=arr[i];
			i=i-dk;
		}
		arr[i+dk]=tmp;
	}
}
void ShellSort(int arr[],int len)
{
	//设置增量模型
	int dk[]={5,3,1};
	int length=sizeof(dk)/sizeof(int);
	int i=0;
	for(i;i<length;i++)
	{
		Shell(arr,len,dk[i]);
	}
}
int main()
{
	int arr[]={3,1,7,5,2,4,9,6};
	int len=sizeof(arr)/sizeof(int);

	Print(arr,len);
	ShellSort(arr,len);
	Print(arr,len);


	return 0;
}

Shell排序的时间性能优于直接插入排序

希尔排序的时间性能优于直接插入排序的原因：

①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。

②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n）和最坏时间复杂度0(n^2）差别不大。

③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

因此，希尔排序在效率上较直接插入排序有较大的改进。

稳定性分析：Shell排序算法的时间复杂度分析比较复杂，实际所需的时间取决于各次排序时增量的个数和增量的取值。研究证明，若增量的取值比较合理，Shell排序算法的时间复杂度约为O（n（ldn）2）。由于Shell排序算法是按增量分组进行的排序，所以Shell排序算法是一种不稳定的排序算法。

欢迎大家批评指正！