数组希尔排序

我与梦想有个约会

发布于 2023-10-20 17:22:59

3060

希尔排序是建立在插入排序的基础之上的，只不过是将数据中做插入排序之前做了一次分组，他的分组是根据用户输入的一个数字来决定分多少组的，比如有如下数据：

49 58 65 97 26 13 27 49 55 4

按下图表示的方法进行三次分组，对每次分组出来的数据执行插入排序，最后得出有序的数组，乍一看来这岂不是多了一步画蛇添足的步骤？实际并不是这样，因为先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前三种方法有较大提高。

【实现代码】

void shell_sort(int *arr, int len)
{
int value = len;
int temp = 0;
int index = 0;
do
{
// 业界统一实验的 平均最好情况 经过若干次后,收敛为1
value = value / 3 + 1;
// 一次跳 value 个
for (int idx = 0; idx < value; idx++)
{
// 对分组后的数据进行排序，每一次跳过整个长度
for (int i = value; i < len; i += value)
{
index = i;
temp = arr[i];
for (int j = i - value; j >= 0 && arr[j] > temp; j -= value)
{
arr[j + value] = arr[j];
index = j;
}
arr[index] = temp;
}
}
} while (value > 1);
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2015-06-07，如有侵权请联系 cloudcommunity@tencent.com 删除

基础