数据结构|C语言实现插入排序——希尔排序算法希尔排序|C实现希尔排序|C语言

C语言实现希尔排序
文章目录

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; }

运行效果图