Shell sorting
希尔排序可以看作是对插入排序的优化。其时间复杂度为O()，或者更小。准确的平均时间复杂度很难得到。
在Robert<算法>里提到间隔序列为1，4，13... 更优。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main() {
int n;
int tmp;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = n/2; i >= 1; i=i/2) {
for (int j = i; j < n; j++) {
for (int k = j; k >= i; k = k - i)
{
if (a[k-i] > a[k])
{
tmp = a[k];
a[k] = a[k-i];
a[k-i] = tmp;
}
}
}
}
for (int i = 0; i < n; ++i) {
cout << a[i] << ' ';
}
}原文地址：https://blog.csdn.net/awesomeray/article/details/136150151
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！