【数据结构与算法】【排序】希尔排序的代码实现

系统管理员 2022-08-13 14:46 142阅读 0赞

希尔排序是一种插入排序。

前提：数组元素a\[0\]用作哨兵或临时变量，a\[1\]~a\[n\]存放n个待排序的元素。

基本思想是：将待排序元素进行跳跃分割，对分割后的子序列分别进行简单插入排序；而后将跳跃分割的增量进行缩小，最后增量为1时完成排序。

代码实现：

<span style="font-family:SimSun;font-size:18px;">// Filename: shell_sort.c
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include "public.h"
    
    // 希尔排序（直接插入排序优化版）
    // n个元素序列的各元素下标：[1, 2, ..., n-1, n], a[0]作为临时变量
    // 将待排序元素进行跳跃分割，对分割后的子序列分别进行简单插入排序；而后将跳跃分割的增量进行缩小，最后增量为1时完成排序。
    // 入参n是待排序元素个数，下表从1开始
    void ShellSort(int a[], int n)
    {
        int i, j;
        int gap = n;
    
        while (gap > 1)
        {
            gap = gap / 3 + 1;
    
            for (i = gap + 1; i <= n; i++)
            {
                // 已经有序的情况下，无需插入，处理下一个
                if (a[i] >= a[i - gap])
                {
                    continue;
                }
    
                // 作为哨兵和临时变量，保存待插入元素，以防前面元素向后移动时覆盖
                a[0] = a[i];
    
                // 找到需要插入的位置，进行插入操作
                for (j = i - gap; j > 0 && a[j] > a[0]; j -= gap)
                {
                    a[j + gap] = a[j];
                }
                a[j + gap] = a[0];
            }
        }
    
        return;
    }
    
    // 直接插入排序主函数
    int ShellSortMain()
    {
        int a1[12] = {0xFF, 3, 4, 5, 8, 9, 7, 6, 1, 0, 2, -1};
    
        printf("希尔排序演示(a[0]是哨兵, 不参与排序): \n");
    
        printf("排序前：\n");
        printf("a1: ");
        PrintArray(a1, sizeof(a1) / sizeof(int));
        printf("\n");
    
        // 将从a1[1]到a1[10]共10个元素进行排序
        ShellSort(a1, 10);
    
        printf("排序后：\n");
        printf("a1: ");
        PrintArray(a1, sizeof(a1) / sizeof(int));
        printf("\n");
    
        return 0;
    }
    </span>