C语言实现插入排序——希尔排序算法

发布时间:2023-02-12 15:00

C语言实现希尔排序

文章目录

  • 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 
#include 

//希尔排序算法
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};

\"在这里插入图片描述\"

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号