第八章 排序 三、希尔排序

目录

 一、算法思想

二、例子

三、代码实现

五、验证

六、空间复杂度

七、时间复杂度

八、稳定性

---

 一、算法思想

先追求表中元素部分有序，在逐渐逼近表中元素全部有序。

二、例子

1、我们要升序排列此表

2、取一个差值作为子表的划分的条件，希尔本人建议d=n/2，在本例题中表示为d=8/2=4

于是，我们将相距为4的元素分配到一个子表。

3、分别对它们进行插入排序

4、将d除以2，得到新的间距，并得到新的子表

5、再次进行插入排序

6、再次缩小d的值，此时d为1，将整个表整合，并进行插入排序，得到最后结果

三、代码实现

#include "bits/stdc++.h"
using namespace std;
 
void ShellSort(int a[],int n){
    int d,i,j,temp;
    for (d = n/2; d >= 1; d=d/2) {//每次的步长不一样
        for (i = d; i <=n ; ++i) {//从第一个d开始
            if (a[i]//如果此数小于它前面的数
                temp=a[i];//将此数存入缓存变量
                for (j = i-d; j >=0 && temp//设初始值为当前值的前d个值
                    a[j+d] = a[j];//用它们作比较，若比它大则将数前移d位
                }
                a[j+d] = temp;//最后把数插入比它的的最后一个数后面
            }
        }
    }
}
 
int main(){
    int count,arr[10];
    scanf("%d",&count);//输入数组长度
    for (int i = 0; i < count; ++i) {
        scanf("%d",&arr[i]);//输入数组
    }
    ShellSort(arr,count);//调用排序函数
    for (int i = 0; i < count; ++i) {
        printf("%d ",arr[i]);//输出数组
    }
    return 0;
}

五、验证

六、空间复杂度

O（1）；

七、时间复杂度

八、稳定性