C语言实现希尔排序

希尔排序算法

//希尔排序算法
void ShellSort(int arr[], int len) {
          
   
    int d, i, j;
    //arr[0]只是暂存单元，不是哨兵，当j<=0时，表示到达插入位置
    for (d = len / 2; d >= 1; d /= 2) {
          
            //步长变化，每次取一半
        for (i = d + 1; i <= len; ++i) {
          
           //从每个子表的第二个元素开始进行直接插入排序
            if (arr[i] < arr[i - d]) {
          
             //将arr[i]插入有序增量表
                arr[0] = arr[i];                //将arr[i]暂存在arr[0]中
                for (j = i - d; j > 0 && arr[0] < arr[j]; j -= d)
                    arr[j + d] = arr[j];        //记录后移，查找插入位置
                arr[j + d] = arr[0];            //插入
            }
        }
    }
}

项目完整代码

//插入排序————希尔排序（不稳定，空间复杂度为O(1)，最坏时间复杂度为O(n^2)）
#include <stdio.h>
#include <stdlib.h>

//希尔排序算法
void ShellSort(int arr[], int len) {
          
   
    int d, i, j;
    //arr[0]只是暂存单元，不是哨兵，当j<=0时，表示到达插入位置
    for (d = len / 2; d >= 1; d /= 2) {
          
            //步长变化，每次取一半
        for (i = d + 1; i <= len; ++i) {
          
           //从每个子表的第二个元素开始进行直接插入排序
            if (arr[i] < arr[i - d]) {
          
             //将arr[i]插入有序增量表
                arr[0] = arr[i];                //将arr[i]暂存在arr[0]中
                for (j = i - d; j > 0 && arr[0] < arr[j]; j -= d)
                    arr[j + d] = arr[j];        //记录后移，查找插入位置
                arr[j + d] = arr[0];            //插入
            }
        }
    }
}

int main() {
          
   
    //数组中第0号位置的值不是有效值！
    int arr[] = {
          
   0, 49, 38, 65, 97, 76, 13, 27, 49};
    int len = sizeof(arr) / sizeof(int);
    //希尔排序
    ShellSort(arr, len);
    //将已排序的结果逐个输出
    printf("希尔排序结果为：");
    for (int i = 1; i < len; ++i) {
          
   
        printf("%d ", arr[i]);
    }
    return 0;
}

运行效果图

int arr[] = {
          
   0, 49, 38, 65, 97, 76, 13, 27, 49};