【基础算法】希尔排序法&C++实现|[实例过程详细分析]-创新互联

目录

●希尔排序法

1.简要介绍

2.图形化演示

3.代码如下

4.结果如下 

  希尔排序算法是基于插入排序法的思想，其又被称为希尔排序或者缩小增量排序。它的具体流程如下：（结合希尔排序算法代码段理解）

for (int r = n / 2; r >= 1; r /= 2)  //化组排序
	{
		for (int i = r; i< n; i++)
		{
			int temp = arr[i];
			int j = i - r;
			while (j >= 0 && temp< arr[j])
			{
				arr[j + r] = arr[j];
				j -= r;
			}
			arr[j + r] = temp;
		}
	}

  ①将有n个元素的数组分成n/2个数字序列（化组操作）。进行第一次循环：第1个数据和第n/2+1个数字序列为一个比较对，判断是否执行while循环，若执行则进行循环操作（插入排序思想）；反之，则将n/2+1数字放回原位。进行第二次循环：第2个数据和第n/2+2个数字序列为一个比较对，判断是否执行while循环，若执行则进行循环操作（插入排序思想）；反之，则将n/2+2数字放回原位。操作如上......（插入排序法：http://t.csdn.cn/ukSxu）

  ②一整次循环使每一个序列对排好顺序

  ③然后，再将这有n个元素的数组分成n/4个序列（化组操作），再次进行排序

  ④不断重复上述流程，随着序列减少，直到变为一个序列对，也就完成了整个排序过程

（在下面的图中，虚线表示不符合while循环判断，实线表示符合并执行while循环判断，实线下面的数字符号为执行了几次的while循环。红色箭头的temp在每次的while判断语句中为每一个数字序列比较对中的值，它在每次循环中是进行后移的。结合代码和输出结果对下面的过程进行理解）

初始状态：

第一次化组： 

第二次化组： 

第三次化组：

结束状态：

#includeusing namespace std;
#define size 10
class shellsort {
public:
	void shellsort_1();
	void showresult();
	int arr[size];
};
void shellsort::shellsort_1()
{   
	int x=0;
	for (int r = size / 2; r >= 1; r /= 2)  //化组排序
	{
		for (int i = r; i< size; i++)
		{
			int temp = arr[i];
			int j = i - r;
			while (j >= 0 && temp< arr[j])
			{
				arr[j + r] = arr[j];
				j -= r;
			}
			arr[j + r] = temp;
		}
		//测试代码
		x++;
		cout<< "第"<< x<< "步排序的结果:";
		for (int i = 0; i< size; i++)
		{
			cout<< arr[i]<< " ";
		}
		cout<< endl;
	}
}
void shellsort::showresult()
{
	for (int i = 0; i< size; i++)
	{
		cout<< arr[i]<< " ";
	}
	cout<< endl;
}
void text()
{
	shellsort ss;
	cout<< "请输入要排序的10个数："<< endl;
	for (int i = 0; i< size; i++)
	{
		cin >>ss.arr[i];
	}
	ss.shellsort_1();
	cout<< "排序后的10个数为："<< endl;
	ss.showresult();
}
int main()
{
	text();
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧