希尔排序算法

拒绝头秃从我做起

1038人浏览 · 2024-11-06 22:27:11

拒绝头秃从我做起 · 2024-11-06 22:27:11 发布

1、基本思想

希尔排序也称缩小增量排序，是插入排序的一种更高效的改进版本。它的基本思想是先将待排序的数组元素按照一定的间隔（称为增量）分成若干个子序列，分别对这些子序列进行插入排序，随着迭代的进行，逐渐减小这个间隔，直到最后间隔为1时，对整个数组进行一次插入排序。通过这种方式，让元素能够在相对较远的位置上快速移动到大致合适的位置，使得后续在间隔较小的插入排序时，元素的移动次数减少，从而提高排序效率。

2、算法步骤

2.1、算法步骤描述：

        1.根据实际情况选择增量序列，增量序列的形式为h1，h2，h3……hn，序列满足h1>h2>h3>……>hn=1，通常h1=N/2，N为待排序数组的长度，常见的增量选取可以按照hi+1=hi/2，也可以按照实际进行其他选择。

        2.根据当前增量将待排序数组分成若干个子序列，每个子序列同等位置的间隔为hi 。例：以数组a[10]={a0,a1,a2,a3,a4,a5,a6,a7,a8,a9},以h1=N/2，hi+1=hi/2进行增量选取，那么第一轮划分中，增量为5，数组arr将被分成如下两个子序列:{a[0],a[5]},{a[1],a[6]},{a[2],a[7]},{a[3],a[8]},{a[4],a[9]}。第二轮划分中，增量为2，数组arr将被分成如下序列:{a[0],a[2],a[4],a[6],a[8]},{a[1],a[3],a[5],a[7],a[9]},增量为1时进行最后一次划分……

        3、对于步骤2中每一轮划分得到的子序列，每个子序列分别进行插入排序。插入排序的过程就是在子序列中，将每个元素与其前面已排好序的元素依次比较并移动到合适位置，使得子序列有序。

        4、当增量减小到1时，对整个数组进行最后一次插入排序，此时数组就完成了排序。

2.2、希尔排序算法动态演示图：

3、代码实现

c语言代码实现如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10
void sort(int arr[])
{
   int gap = N;
   while(gap != 1)
   {
   gap = gap/2; //确定本轮排序增量
   for(int i = 0; i < gap; i++)//增量决定这一轮进行插入排序的次数
   {
       for(int j = i; j + gap < N ;j = j + gap)//对根据增量分成的其中一组进行插入排序
       {
           int end = j;//重置本轮扫描位置
           int insert = arr[end+gap];//本轮要插入的数据
           while(insert < arr[end] && end >= i)
            {
                arr[end+gap] = arr[end];//移动
                end = end - gap;//改变下次开始扫描位置
            }
           arr[end+gap] = insert;//插入
       }
   }
   }

}
int main(int argc, char *argv[])
{
    srand(time(NULL));
    int a[N];
    int i;

    puts("排序前数组为：");
    for(i = 0; i < N; i++)
    {
        a[i] = rand()%100;//为数组随机赋值
        printf("%d ",a[i]);//输出排序之前数组值
    }
    puts("");

    sort(a);//排序

    puts("排序后的数组为：");
    for(i = 0; i < N; i++)
    {
        printf("%d ",a[i]);//输出排序之后的数组值
    }
    puts("");

    return 0;
}