本文共 871 字，大约阅读时间需要 2 分钟。

1099: 希尔排序算法实现

题目描述

10

50 36 41 19 23 4 20 18 12 22

样例输出

4 20 18 12 22 50 36 41 19 23

思路：

• 希尔排序：也是一种插入排序的方法，实际上是一种分组插入的方法。先定一个小于n的整数gap1作为第一个增量，把表的全部记录分成gap1个组,所有距离为gap1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量gap2(＜d1),重复上述的分组和排序,直至所取的增量gapt=1(gapt<gapt-1<…<gap2<gap1),即所有记录放在同一组中进行直接插入排序为止。
• 这里给出一个希尔排序的视频：
  【B站】https://www.bilibili.com/video/BV1j84y1c78o
• 这里再给出一个希尔排序的图片：
  【实例】运用希尔排序将10个数9 1 2 5 7 4 8 6 3 5进行递增排序。

（栗子转载自）

我对希尔排序的浅显理解是进行隔空比较，交换数值，每次所隔之空gap都是上一所隔之空gap的一半，下面是具体的实现步骤：

1. 增量gap置初值，寻找序列长度n，令gap=n/2；
2. while循环直到gap<=0结束（因为是第一趟所以这步可以不用管）
   ① 根据条件进行插入排序（递增小在前大在后，递减则反之。）
   ②减小增量 (因为是第一趟所以这步可以不用管）
3. 输出数据

#include
   
    int main(){
   	int n, data[1000], gap, temp, i;	scanf("%d",&n);//cin >> n;	for(i=0;i
    
     > data[i];	gap=n/2;//第一趟排序,不用while循环	for(i=gap;i
    
   

以上方法仅供参考，欢迎互联网的广大朋友们提出指正。