1，排序原理
希尔排序，也称递减增量排序算法，是直接插入排序算法的一种高速而稳定的改进版本。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
2，原理图
?
?3，实现代码：
#include "stdafx.h"
#include<iostream>
//测试数组 正确顺序维 2，3,7,12,15,31,34，45,54,64,86
int data[] = { 12,45,2,64,54,31,86,34,15,3,7 };
void ShellInsert(int data[],int count) {
//分别按5,3,1 增量分组排序
int delta[] = { 5,3,1 };
for (int m = 0; m < 3; m++) {
for (int n = 0; n < delta[m]; n++) {
for (int i = n + delta[m]; i < count; i += delta[m]) {
int tem = data[i];
for (int j = i - delta[m]; j >= 0; j -= delta[m]) {
if (tem< data[j]) {
data[j + delta[m]] = data[j];
data[j] = tem;
}
}
}
}
std::cout << "递增"<< delta[m] << "排列： ";
for (int i = 0; i <11; i++) {
std::cout << data[i] << " ";
}
std::cout << " " << std::endl;
}
}
int main()
{
std::cout << "原始数据 " << " ";
for (int i = 0; i <11; i++) {
std::cout << data[i] << " ";
}
std::cout << " " << std::endl;
ShellInsert(data, 11);
std::cout << "排序数据 " << " ";
for (int i = 0; i <11; i++) {
std::cout << data[i] << " ";
}
std::cout << " " << std::endl;
system("echo 按回车继续...&pause>nul");
return 0;
}
运行结果：
4，时间复杂度和空间复杂度
?空间复杂度为O(1)
时间复杂度：最坏情况下为O(n^2)，平均时间复杂度为O(n^1.3)；
5，是否稳定
不稳定算法
举例说明：
两个12顺序发生了变化，所以是不稳定排序。
?
