第八章排序三、希尔排序

一、算法思想

二、例子

三、代码实现

五、验证

六、空间复杂度

七、时间复杂度

八、稳定性

一、算法思想

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

二、例子

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]<a[i-d]){//如果此数小于它前面的数temp=a[i];//将此数存入缓存变量for (j = i-d; j >=0 && temp<a[j] ; j-=d) {//设初始值为当前值的前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;
}