排序算法-希尔排序法（ShellSort）

 排序算法-希尔排序法ShellSort

1、说明

我们知道当原始记录的键值大部分已排好序的情况下插入排序法非常有效因为它不需要执行太多的数据搬移操作。希尔排序法是D.L.Shell在1959年7月发明的一种排序法可以减少插入排序法中数据搬移的次数以加速排序的进行。排序的原则是将数据区分成特定间隔的几个小区块以插入排序法排完区块内的数据后再渐渐减少区间的距离。

2、算法分析

1. 任何情况下时间复杂度为。
2. 希尔排序和插入排序法一样都是稳定排序法。
3. 因为只需一个额外的空间所以空间复杂度为最佳。
4. 这种排序法适用于大部分数据都已排序的情况。

3、C++代码 

#include<iostream>
using namespace std;

int main() {

	const int size = 6;
	int data[size] = { 9,7,5,3,4,6 };

	cout << "原始数据" << endl;
	for (int i = 0; i < size; i++) {
		cout << data[i] << "  ";
	}
	cout << endl;

	int i;				//循环次数
	int j;				//需要排序的元素索引
	int temp;			//需要排序的元素暂存数据
	int jump = size/2;	//间隔
	while (jump != 0) {
		//第1次
		//3  4  5  9  7  6
		//第2次
		//3  4  5  6  7  9
		for (i = jump; i < size; i++) {
			temp = data[i];
			j = i - jump;
			//temp > data[j]	从大到小排序的条件
			//temp < data[j]	从小到大排序的条件
			while (temp < data[j] && j >= 0) {
				data[j + jump] = data[j];
				j -= jump;
			}
			data[j + jump] = temp;
		}
		jump /= 2;
	}

	cout << "最终数据" << endl;
	for (int i = 0; i < size; i++) {
		cout << data[i] << "  ";
	}
	cout << endl;

	return 0;
}

输出结果