自学内容网 自学内容网

希尔排序算法

目录

ShellSort希尔排序

整体思路

图解分析

【1】预排序

单组排序

多组并排

【2】直接插入排序

关于gap取值 

总代码实现

时间复杂度


ShellSort希尔排序

希尔排序法又称缩小增量法。

  • 希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个 组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工 作。当到达=1时,所有记录在统一组内排好序。 
  • 希尔排序=预排序+直接插入排序
  • 预排序:让大的数值更快的到达后面,小的数值更快的到达前面。(达到一个让数组元素接近顺序的效果)
  • gap是间距值❗
  • 直接插入排序相当于gap==1,希尔排序相当gap存在值了。

希尔排序的特性总结:

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就 会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 稳定性:不稳定 

4. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的 希尔排序的时间复杂度都不固定:

《数据结构(C语言版)》--- 严蔚敏

《数据结构-用面相对象方法与C++描述》--- 殷人昆

整体思路

  • gap是数值之间的间距值❗
  • 直接插入排序相当于gap==1,希尔排序相当gap存在值了。
  • gap是几,就可以把整体分为几组。(除去gap = n的情况)(gap=gap/2或者gap=gap/3+1)
  • 分组和每组里面的元素个数的关系
  1. gap = n(gap随着n的变换而变化,gap的值不固定)
  2. gap/2(每次gap组,每组里面的元素个数:2,4,8......)*2 【n/2,n/4,n/8....】
  3. gap/3+1 (每次gap组,每组里面的元素个数:3,9,27...)*2【n/3,n/9,n/27....】
  4. 随着gap的变小,组数会变小,每组里面的数值个数会变大。

    gap的值

  • 一个数无论是奇数还是偶数/2 最后都等于1
  • gap的值不是固定的,可以是gap/2或者gap/3+1
  • gap值无论是/2 /3,最后都必须==1 ,最后要直接插入排序
  • gap>1时时预排序,目的是让整体数值更加接近有序
  • gap == 1的时候就是直接插入排序,目的是让整体值有序。
  • gap的值越大,大的值更快的调到后面,小的值可以更快的调到前面,越不接近有序。
  • gap的值越小,大的值更慢的调到后面,小的值可以慢的调到前面,越接近有序。
  • gap的值不是固定的,gap的值是随着整体n的大小变化而变化的。
  • 随着gap的变小,组数会变小,每组里面的数值个数会变大。
  • 预排序gap的上一个值排完之后会对下一个值得排序调整次数产生影响。

  • 整体思路

  • 一趟:类似直接插入排序的一趟,间距从1变为gap
  • 一组:加入循环,完成一组的排序(类似直接插入排序整体)
  • 多组:加入三层嵌套循环/多组并排。(完成多组排序)(gap是多少就有多少组)
  • 整体:完成整个数组的排序(多次预排序直到最后插入排序gap=1)(n个值)gap=n(gap=gap/2或者gap=gap/3+1)

图解分析

  • gap是数值之间的间距值❗
  • gap=n(n是整个的数值个数)
  • gap=gap/2
  • gap=10/2=5
  • gap=5/2=2
  • gap=2/2=1
  • 注意:无论gap用gap/2或者gap/3+1或者其他最后gap的值必须为1,因为最后要进行直接插入排序,完成整体的排序。 

【1】预排序

为了理解,这里我们先把gap理解为固定值gap == 3是一个固定值。 假设n=11

单组排序

  • 一组一组排序
  • 三个嵌套循环
  • 控制起始位置i=j(0/1/2)
  • i=0(0/3/6)
  • i=1(1/4/7)
  • i=2(2/5)
  • i=0/3/6/1/4/7/2/5
  • 控制数组元素下标,防止越界i<n-gap(i<11-3=8)

//升序
//写法1:三层嵌套循环
void ShellSort(int* a, int n)
{
//多组
int gap = 3;
for (int j = 0; j < gap; j++)
{
        //每组
for (int i = j; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
//一趟
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else//<=
{
break;
}
}
a[end + gap] = tmp;
}
}
}

多组并排

  • 多组并排
  • 两个嵌套循环
  • 控制起始位置i=0/1/2
  • i=0/1/2/3/4/5/6/7
  • 控制数组元素下标,防止越界i<n-gap(i<11-3=8)

//写法2
//多组并排
void ShellSort(int* a, int n)
{

//多组
int gap = 3;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
//一趟
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else//<=
{
break;
}
}
a[end + gap] = tmp;
}
}

【2】直接插入排序

实际上如果整体的数量过大,gap为3是非常不合适的。所以,gap不可能为固定值,gap的取值是随着n变化的,所以gap有两种方式去取值。

关于gap取值 

  • gap=gap/2
  • gap=gap/3+1
  • 注意:无论gap用gap/2或者gap/3+1或者其他。最后gap的值必须为1,因为最后要进行直接插入排序,完成整体的排序。 
  • gap是几,就可以把整体分为几组。(除去gap = n的情况)(gap=gap/2或者gap=gap/3+1)
  • 分组和每组里面的元素个数的关系
  • gap = n(gap随着n的变换而变化,gap的值不固定)
  • gap/2(每次gap组,每组里面的元素个数:2,4,8......)*2 【n/2,n/4,n/8....】
  • gap/3+1 (每次gap组,每组里面的元素个数:3,9,27...)*2【n/3,n/9,n/27....】
  • 随着gap的变小,组数会变小,每组里面的数值个数会变大。
void ShellSort(int* a, int n)
{
//整体
int gap = n;
while (gap > 1)
{
//每组
//gap = gap / 2;
gap = gap / 3 + 1;
        //..........
}
}
}

总代码实现

void ShellSort(int* a, int n)
{
//整体
int gap = n;
while (gap > 1)
{
//每组
//gap = gap / 2;
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
//一趟
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else//<=
{
break;
}
}
a[end + gap] = tmp;
}
}
}

时间复杂度

  • 希尔排序的时间复杂度O(N^1.3)
  • O(N^1.3)比O(N*logN)略慢,效率略低一点。
  • 希尔排序VS直接插入排序(秒入过万VS分入过万)
  • 预排序gap的上一个值排完之后会对下一个值得排序调整次数产生影响。
  • O(N^1.3)需要套用数学模型,统计学来计算,这里只是近似计算。记住最后结论即可。

🙂感谢大家的阅读,若有错误和不足,欢迎指正。下篇选择排序&堆排序。大家新年快乐!! 


原文地址:https://blog.csdn.net/m0_74841364/article/details/136137748

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!