希尔排序
2022/8/4 22:13:00admin2725 阅读0 点赞0 评论
最近在全面学习数据结构，常用算法记录：希尔排序，基本思想是选定一个增量 d<nd<n，将元素按此增量分组（所有相距 dd 的元素为一组），然后在各个子序列内进行插入排序，完成后缩小增量 d′(d′<d)d'(d'<d)，如此反复操作，直到增量 d=1d = 1 为止，此时就成了标准的插入排序，但此时大部分元素已经有序，只需要少量操作，甚至不用操作即可完成排序。该排序算法为不稳定排序。
希尔排序还是比较绕的，需要多看看，多画一画。
最坏时间复杂度：O(n2)O(n^2)
nn 在某范围内可达：O(n1.3)O(n^{1.3})
目前无法用数学手段证明确切的时间复杂度。
TEXT
#include <iostream>
using namespace std;
void shellSort(int arr[], int n);
int main()
{
int arr[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11};
int length = (int)(sizeof(arr) / sizeof(int)); //数组长度
shellSort(arr, length);
for (int i = 1; i < length; i++)
cout << arr[i] << " ";
return 0;
}
void shellSort(int arr[], int n)
{
int d, i, j;
//arr[0]为暂存单元
for (d = n / 2; d > 0; d /= 2) //d为步长
{
for (i = d + 1; i <= n; i++) //从子表中第二个元素开始
if(arr[i] < arr[i - d]) //小于子序列前一项
{
arr[0] = arr[i]; //暂存待插入元素
for (j = i - d; j > 0 && arr[0] < arr[j]; j -= d)
arr[j + d] = arr[j]; //向后移动，为待插入元素腾出空位
arr[j + d] = arr[0]; //插入暂存元素
}
}
}
