#include <iostream>
using namespace std;?
void shellSort(int arr[], int n)
{
?? ?int tmp = 0;
?? ?int step = n / 2;
?? ?while (step)
?? ?{
?? ??? ?for (int i = step; i < n; i++)
?? ??? ?{
?? ??? ??? ?tmp = arr[i];
?? ??? ??? ?int j = i;
?? ??? ??? ?while (j >= step && tmp < arr[j - step]) ? //采用直接插入排序
?? ??? ??? ?{
?? ??? ??? ??? ?arr[j] = arr[j - step];
?? ??? ??? ??? ?j -= step;
?? ??? ??? ?}
?
?? ??? ??? ?arr[j] = tmp;
?? ??? ?}
?
?? ??? ?step = step / 2;
?? ?}
}
?
int main()
{
?? ?int arr[]{ 3, 14, 25, -22, -3, 87, 126, 34, 64, -70, 15, 17, 78 };
?? ?int n = sizeof(arr) / sizeof(arr[0]);
?? ?shellSort(arr, n);
?? ?for (int i = 0; i < n; i++)
?? ??? ?cout << arr[i] << " ";
?
?? ?system("pause");
? ? return 0;
}

復雜度分析

當增量為1（step = 1）時，希爾排序退化成了直接插入排序，此時的時間復雜度為O(N²)；

Hibbard增量的希爾排序的時間復雜度O(n^3/2)；

關于希爾排序的問題分析

排序算法之希爾排序及時間復雜度分析

希爾排序

算法思想：將整個待排序列分割成若干個子序列（由相隔增量個元素組成），分別進行直接插入排序，然后依次縮小增量再進行排序，待整個序列中的元素基本有序時，再對全體元素進行一次直接插入排序。

希爾排序的實現(xiàn)應該由三個循環(huán)完成

（1）第一次循環(huán)，將增量d依次折半，直到增量d=1

（2）第二三層循環(huán)，也就是直接插入排序所需要的兩次循環(huán)。

算法實現(xiàn)：

#include <stdio.h>
#define N 9
int main(void)
{
	int arr[N] = {9,1,5,8,3,7,4,6,2};
	int d = N / 2; //增量先取一半
	int i,j,insertVal;
	//希爾排序三層循環(huán)
	while(d>=1) //當增量大于等于1,不斷進行插入排序
	{
		//一下兩層for循環(huán)是直接插入排序代碼
		for(i=d; i<N; i++)
		{
			insertVal = arr[i];
			j = i - d;
			while(j>=0 && arr[j]>insertVal)
			{
				arr[j+d] = arr[j];
				j = j - d;
			}
			arr[j+d] = insertVal;
		}
		d = d / 2;
	}
	for(i=0; i<N; i++)
	{
		printf("%d ",arr[i]);
	}
	return 0;
}

由如上代碼知，希爾排序的關鍵并不是隨便分組后各自排序，而是將相隔某個增量的記錄組成一個子序列，實現(xiàn)跳躍式移動，使得排序的效率高。