经典排序算法之希尔排序|c++代码实现||什么是希尔排序|如何代码实现

引言

排序算法c++实现系列第4弹——希尔排序

算法介绍

希尔排序（Shell Sort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。该排序算法的基本思想是将原始序列分成若干个子序列，分别对每个子序列进行直接插入排序，然后逐步缩小子序列的间隔，直到整个序列变成一个有序序列。

算法步骤

选择增量序列：选择一个增量序列（即代码中的gap），通常以2为基数，逐步缩小增量的值（即希尔增量序列）。增量序列的选择对希尔排序的性能影响很大，常见的增量序列包括希尔增量序列、Hibbard增量序列、Sedgewick增量序列等。
1. 希尔增量序列（Shell's Increment Sequence）：希尔增量序列是希尔排序的名字来源之一。希尔增量序列是通过h_k = n / 2^k计算得到的，其中(n)为序列长度，(k)为增量的序号。希尔增量序列的第一个增量通常为序列长度的一半，随后的增量依次减半，直到增量为1。希尔增量序列的优点是简单易于实现，但其性能较差，不如其他增量序列。
2. Hibbard增量序列： Hibbard增量序列是由Donald Hibbard于1963年提出的一种增量序列。Hibbard增量序列的计算公式为(h_k = 2^k - 1)，其中(k)为增量的序号。Hibbard增量序列的特点是每个增量都是连续的奇数，并且增量递减非常快。Hibbard增量序列的性能相对较好，但增量之间的差异较大，可能导致不稳定的性能。
3. Sedgewick增量序列： Sedgewick增量序列是由Robert Sedgewick于1986年提出的一种增量序列。：Sedgewick增量序列的特点是增量之间的差异较小，性能稳定，并且在实际应用中表现优秀。（在代码中也已实现）
分组排序：根据选定的增量序列，将原始序列分成若干个子序列，对每个子序列进行直接插入排序。
缩小增量：逐步缩小增量的值，重复第二步的分组排序过程，直到增量为1。
最终排序：当增量为1时，即对整个序列进行一次直接插入排序，最终得到排序好的序列。

举例说明：如代码中的数组arr = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62}；我们假设此时gap为2，那么原数据就将被分为

子序列1：{61, 29, 34, 72, 50, 62}；子序列2：{17, 22, 60, 21, 1}；分别对上述两个子序列进行直接插入排序后得到全部数据序列为：{29, 1, 34, 17, 50, 21, 61, 22, 62, 60, 72}；

接下来，可以使gap为1，相当于对{29, 1, 34, 17, 50, 21, 61, 22, 62, 60, 72}整体做一次直接插入排序，即得到最终结果

时间复杂度

希尔排序的时间复杂度取决于增量序列的选择，最坏情况下的时间复杂度为 O(n2)，平均情况下为 O(nlog2n)。

代码实现

#include<bits/stdc++.h>
using namespace std;
template<typename T>
void shell_sort(T arr[], int len) {
//	// 希尔增量序列
//	int gap = len / 2;
//	while (gap) {
//		for (int i = gap; i < len; i++) {
//			int j = i - gap;
//			T k = arr[i];
//			while ((j >= 0) && (arr[j] > k)) {
//				arr[j + gap] = arr[j];
//				j -= gap;
//			}
//			arr[j + gap] = k;
//		}
//		gap /= 2;
//	}
	// Sedgewick增量序列
	int gap = 1;
	while (gap < len / 3) {
		gap = 3 * gap + 1;
	}
	while (gap) {
		for (int i = gap; i < len; i++) {
			T key = arr[i];
			int j = i - gap;
			while (arr[j] > key && (j >= 0)) {
				arr[j + gap] = arr[j];
				j -= gap;
			}
			arr[j + gap] = key;
		}
		gap /= 3;
	}

}
int main() {
	int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
	int len = (int) sizeof(arr) / sizeof(*arr);
	shell_sort(arr, len);
	for (int i = 0; i < len; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;

	float arrf[] = {17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.7, 5.4};
	int lenf = sizeof(arrf) / sizeof(*arrf);
	shell_sort(arrf, lenf);
	for (int i = 0; i < lenf; i++) {
		cout << arrf[i] << " ";
	}
	return 0;
}

运行结果展示：