1.代码模板
// 希尔排序（Shell Sort）
void ShellSort(SqList *L)
{
int i, j;
int increment = L->length; // 先让增量初始化为序列的长度
do {
increment = increment / 3 + 1; // 计算增量的值
for (i = increment + 1; i <= L->length; i ++ ) {
if (L->arr[i] < L->arr[i - increment]) { // 如果L->[i]需要插入有序增量子表
L->arr[0] = L->arr[i]; // 暂存在哨兵位
for (j = i - increment; j > 0 && L->arr[0] < L->arr[j]; j -= increment) { // 遍历增量子表，寻找插入位置
L->arr[j + increment] = L->arr[j];
}
L->arr[j+increment] = L->arr[0]; // 插入
}
}
} while (increment > 1);
}
2.算法介绍
希尔排序，又叫缩小增量排序，算法属于插入类排序的进阶算法，采取跳跃分割的策略，将关键字较小的元素跳跃式的往前挪，大大减小了交换比较的次数。使得序列整体基本有序 ，即大的元素基本在后面，小的元素基本在前面，不大不小的元素基本在中间。
希尔排序的关键在于将序列中相隔某个“增量”的元素组成一个子序列，且序列的最后一个增量必须为1，这样才能保证最后的结果是有序且正确的。但增量如何选择为最佳，至今仍无定论。且由于元素是跳跃式移动的，所有希尔排序是一个不稳定的排序算法，其时间复杂度受到增量选择的影响，最好为O(n^1.3) , 最坏为O(n*n)。
3.实例
#include <iostream>
using namespace std;
const int N = 100;
typedef struct
{
int arr[N]; // 存储待排序的序列
int length; // 存储序列的长度
} SqList;
void ShellSort(SqList *L)
{
int i, j;
int increment = L->length;
do {
increment = increment / 3 + 1;
for (i = increment + 1; i <= L->length; i ++ ) {
if (L->arr[i] < L->arr[i - increment]) {
L->arr[0] = L->arr[i];
for (j = i - increment; j > 0 && L->arr[0] < L->arr[j]; j -= increment)
L->arr[j + increment] = L->arr[j];
L->arr[j + increment] = L->arr[0];
}
}
} while (increment > 1);
}
int main()
{
SqList L;
L.arr[1] = 50;
L.arr[2] = 10;
L.arr[3] = 90;
L.arr[4] = 30;
L.arr[5] = 70;
L.arr[6] = 40;
L.arr[7] = 80;
L.arr[8] = 60;
L.arr[9] = 20;
L.length = 9;
ShellSort(&L);
for (int i = 1; i <= L.length; i ++ )
cout << L.arr[i] << " ";
}
到此这篇关于C++实现希尔排序算法实例的文章就介绍到这了,更多相关C++希尔排序算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
