希尔排序的原理、特点和完整代码实现。

希尔排序（Shell Sort）

原理

先将待排序表分割成若干形如L[i, i+d, i+2d, … , i+kd]的特殊子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d = 1为止。

特点

• 空间复杂度：O(1)
• 时间复杂度：未知，但优于直接插入排序
• 稳定性：不稳定
• 适用性：仅可用于顺序表

高频题型：给出增量序列，分析每一趟排序后的状态

完整代码实现

#include<iostream>
#include<string>

using namespace std;

/* 希尔排序 */
void ShellSort(int A[], int len)
{
	int d,i,j;
	//A[0]为暂存单元，当j<=0时，就到插入位置了
	for (d = len/2; d >=1; d=d/2)//步长变化
	{
		for (i = d+1; i <= len; i++)
		{
			if (A[i]<A[i-d]) {//需将A[i]插入有序增量子表
				A[0] = A[i];  //暂存在A[0]
				for(j = i-d; j >0 && A[0]<A[j]; j-=d)
				{
					A[j + d] = A[j];  //记录后移，查找插入位置
				}
				A[j + d] = A[0];  //插入
			}
		}
	}
}

int main()
{
	//哨兵是用来判断程序何时结束的
	//有暂存单元的数组，第一个是暂存单元
	int A[] = {0,3,5,2,6,1,4,9,8 };
	ShellSort(A, 8);
	cout << "希尔排序后：" << endl;
	for (int i = 1; i <= 8; i++)
	{
		cout << A[i];
		if (i == 8)
		{
			cout <<endl;;
		}
		else
		{
			cout << ",";
		}
	}
	system("pause");
	return 1;
}