希尔排序解析实例实现

一、什么是希尔排序

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

二、动图演示

*动图来自菜鸟教程

举个例子，
对于{1,2,3,4,5,6,7,8,9,10}
选取d为3，那么我们就对{1,4,7,10}{2,5,8}{3,6,9}这三个逻辑上的组进行一次直接插入排序
然后下一次d取为2…
d取为1…整个文件恰被分成一组，算法便终止
这也就是希尔排序又称为"缩小增量排序"的原因

建议看这个视频：https://www.bilibili.com/video/BV1wW411h7Wt?from=search&seid=12358979021121049993

三、实现方式

先将排序表分割成 d 个形如 $L[i,i+d,i+2d,...,i+kd]$的“特殊”子表，分别进行直接插入排序，当整个表中的元素已呈“基本有序时”，再对全体记录进行一次直接插入排序。

四、关于希尔排序的性能参数

1、时间复杂度

最坏：$O(n^2)$
某些情况下：$O(n^{1.3})$

2、空间复杂度

$O(1)$

3、是否稳定

不稳定

4、适用于何类型存储

顺序存储

五、代码实现

对于d这个增量的取值，我采用的是Shell的方法：

希尔排序第1趟的增量：$d_1=lfloor n/2rfloor $
希尔排序第$i$躺的增量：$d_{(i+1)}=lfloor d_i/2rfloor $
直到最后一个$d_k=1$

1、算法

void ShellSort(int A[],int n){	// 存放所有元素的数组A[],数组大小n
//dk:增量
//根据步长进行循环
for(int dk=n/2;dk>=1;dk=dk/2)
{
// 从头到尾
for (int i = 0; i < n; ++i)
{
// 
for (int j = i + dk; j < n; j = j + dk)
{
if (A[j-dk] > A[j])
swap(A[j], A[j-dk]);
}
}
}
}

2、实例实现

/*
* @Descripttion:
* @version:
* @Author: edisonhuang
* @Date: 2020-03-12 12:21:15
* @LastEditors: edisonhuang
* @LastEditTime: 2020-04-03 13:03:28
*/
#include <iostream>
void Print(int A[], int len);
void ShellSort(int A[],int n);
using namespace std;
int main()
{
int arr[] = {13, 14, 8, 100, 25, 75, 9, 64, 12};
int len = (int) sizeof(arr) / sizeof(*arr);
Print(arr,len);
ShellSort(arr,len);
Print(arr,len);
return 0;
}
void ShellSort(int A[],int n){
// 存放所有元素的数组A[],数组大小n
//dk:增量
//根据步长进行循环
for(int dk=n/2;dk>=1;dk=dk/2)
{
// 从头到尾
for (int i = 0; i < n; ++i)
{
//
for (int j = i + dk; j < n; j = j + dk)
{
if (A[j-dk] > A[j])
swap(A[j], A[j-dk]);
}
}
}
}
void Print(int A[], int len)
{
for (int i = 0; i < len; i++)
{
cout << A[i] << " ";
}
cout << endl;
}

最后

以上就是呆萌洋葱为你收集整理的希尔排序解析实例实现的全部内容，希望文章能够帮你解决希尔排序解析实例实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。