经典算法之希尔排序

活动地址：CSDN21天学习挑战赛

前言

再长的路，一步一步也能走完，再短的路是，不迈开双脚也无法到达。

一、什么是希尔排序

希尔排序法也叫做缩小增量法，属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。

二、希尔排序的过程

将n个待排序元素的序列，取一个小于n的整数m作为间隔，将全部的n个元素分为m个子序列，所有距离为m的元素放在同一个子序列中，在每个子序列中分别进行直接插入排序，然后，缩小间隔m，比如取m=m/2，重复划分子序列和排序；直到m==1为止(即所有元素放在同一个子序列中排序）。

三、希尔排序的算法实现

• 输入

n个数的序列，通常直接存放在数组中，可能是任何顺序。

• 输出

输入序列的一个新排列，满足从小到大的顺序（默认讨论升序，简单的修改就可实现降序排列。

例如：

• 首先输入10个元素：5，2，3，4，9，7，1，8，0，6。
• 分组后在组内进行直接插入排序，依然在原数据结构上进行，串位时以d为时间间隔进行操作。
• 第一次分组：取d=5，数据被分为5组，每组分2个元素。
• 第二次分组：取d=2,数据被分为2组，每组5个元素。
• 第三次分组：取d=1，数据被分为1组，组内10个元素。

四，希尔排序图解

五、希尔排序步骤

1. 第一轮：组内排序，分间隔4排序
2. 第二轮：组内排序，分间隔2排序
3. 第三轮：组内排序，分间隔1排序

六、代码实现

#include<iostream>
using namespace std;
const int n = 10;
void Print(int a[], int n);//该函数实现打印的功能
void ShellSort(int a[], int n);//该函数实现希尔排序功能
int main()
{
	int array[n] = { 10,54,13,64,78,95,45,51,23,36 };
	cout << "未排序前数组的元素为："<<endl;
	for (int i = 0; i < n; i++)
	{
		cout << array[i]<<" ";
	}
	cout << endl;
	cout << "排序后的数组元素为：" << endl;
	Print(array, n);
	ShellSort(array, n);
}
void Print(int a[], int n)
{
	for (int m = 0; m < n; m++)
	{
		cout << a[m]<<" ";
	}
	cout << endl;
}
void ShellSort(int a[], int n)
{
	int k, j, inc, key;//k,j控制循环，inc是增量，key是插入的时候临时保存的变量
	//初始增量n/2，每趟之后除以二；
	for (inc = n / 2; inc > 0; inc /= 2)
	{
		//每一趟采用插入排序
		for (k = inc; k < n; k++)
		{
			key = a[k];
			for (j = k; j >= inc && key < a[j - inc]; j -= inc)
				a[j] = a[j - inc];
			a[j] = key;
		}
		Print(a, n);
	}
}

七、希尔排序的优缺点

优点：算法简单，代码短，需要的空间小，速度可以，适合情况复杂，以及中小规模的排序。
缺点：速度偏慢，不够智能，不适合情况简单的排序，不适合大规模排序。