经典算法之希尔排序

​

前言：

✌ 作者简介：游坦之 ✌

🏆 大学软件工程在读，希望学到真本领，经世致用 🏆

📫 如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步👀

💬 人生格言：丑且益坚，病当益壮💬

🔥 如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

@​​TOC​​

希尔排序

什么是希尔排序？

希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

简单的说，是先设置好一个长度（一般是元素长度的一半），然后将其划分为一组，先对这一组进行排序。然后缩小范围（一般是长度/2）,在分组排序，直到长度变为1。

示例演示

声明:以下图片来自菜鸟教程

（1）初始增量第一趟 gap = length/2 = 4

（2）第二趟，增量缩小为 2

（3）第三趟，增量缩小为 1,得到最终排序结果

牛刀小试

对{7,6,9,3,1,5,2,4}进行排序

#include <iostream>
using namespace std;
int a[8]={7,6,9,3,1,5,2,4};
int gap;
int length = 8;
int temp;
int main()
{
  int j;
  for(gap = length/2;gap>0;gap/=2)
  {
    for(int i=gap;i<length;i++)
    {
      temp = a[i];
      for(j = i;j>=gap&&temp<a[j-gap];j-=gap)
      {
       a[j] = a[j-gap];
      }
      a[j] = temp;
    } 
  }
  for(int i=0;i<length;i++)
  {
    cout<<a[i]<<" ";
  }
  return 0;
}      

结果：

✨

👍

⭐️

✏️