希尔排序

1. 希尔排序

综述

希尔排序是一种类直接插入排序的算法

初始化一个整数步长gap=n/2，先将间隔为gap的子表直接插入排序

然后缩减步长，将步长gap/=2，再来一遍，最终落在gap=1。

Ref：

• 旧金山大学可视化算法演示
• Shell Sort-Geeks for Geeks

分析

稳定性

直接插入排序是不稳定的排序算法

时间复杂度

• O(n^2)

空间复杂度

O(1)

C++代码实现

// 希尔排序
void shellSort(vector<int>& nums) {
	int n = nums.size();
	// 初始间隔为n/2，最终间隔为1，每次间隔/2
	for (int gap = n / 2; gap >= 1; gap/=2) {
		// 从间隔开始，向上循环遍历数组
		for (int i = gap; i < n; i += 1) {
			// 临时变量为当前值
			int temp = nums[i];
			int j;
			// 从当前值开始，向前循环遍历，如果看到有比当前值大的就交换，每次的步长为gap的数值
			for (j = i; j >= gap && nums[j - gap] > temp; j -= gap) {
				nums[j] = nums[j - gap];
			}
			// 把当前的值插入到最终的地方;
			nums[j] = temp;
		}
	}
}

int main() {
	vector<int> nums = { 9,8,7,6,5,4,3,2,1 };
	shellSort(nums);
	for (int n : nums) {
		cout << n << endl;
	}
	return 0;
}