当前位置：首页 > news >正文

网站建设费1万多入什么科目山东省住房和建设网站首页

news 2025/9/17 17:25:47

网站建设费1万多入什么科目,山东省住房和建设网站首页,做网站要学一些什么,广州建设银行保安招聘网站目录 1.希尔排序( 缩小增量排序 ) 2.动图编辑 3.代码实现预排序实现子序列排列实现单趟排序实现对整组数进行子排序希尔排序代码代码测试时间复杂度分析希尔排序的特性总结： 1.希尔排序( 缩小增量排序 ) 基本思想： 1.先选定一个…

1.希尔排序( 缩小增量排序 )

2.动图编辑

3.代码实现

预排序实现

子序列排列实现

单趟排序实现

对整组数进行子排序

希尔排序代码

代码测试

时间复杂度分析

希尔排序的特性总结：

1.希尔排序( 缩小增量排序 )

基本思想：

1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

2.动图

3.代码实现

思路：

预排序实现

插入排序

预排序实现

根据当前增量，数组被分为若干子序列，这些子序列的元素在原数组中间隔着固定的增量。对每个子序列应用插入排序。

假设最初增量为5

d越大，数据挪动得越快；d越小，数据挪动得越慢。前期让d较大，可以让数据更快得移动到自己对应的位置附近，减少挪动次数。

注：一般情况下，取序列的一半作为增量，然后依次减半，直到增量为1（也可自己设置）。

完成了一轮希尔排序，此时整个数组并不完全有序，但是已经比原始的数组更接近有序了。然后减小增量，通常是将原来的增量除以2（或者除以3+1），现在选择下一个增量为 2，按照此排序规则继续预排序即可，直到增量为1时，则为直接插入排序，此时则排序完成。

子序列排列实现

//子序列int gap;int end；int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + 3] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;

这里只需要在插入排序的基础上修改一下即可。end的所加所减都为gap;

单趟排序实现

int gap;//单趟排序实现for (int i = 0; i < n - gap; i += gap){//子序列int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + 3] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}

这里的 n-gap 和插入排序中的 n-1 一样是为了防止越界

对整组数进行子排序

int gap;for (int j = 0; j < gap; j++){//单趟排序实现for (int i = 0; i < n - gap; i += gap){//子序列int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + 3] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}

外层循环（for (int j = 0; j < gap; j++)）意在对每个以gap为间隔的分组进行遍历。

这里进行一下优化：

三层代码的循环是每一组子排序排完再进行下一组，直到排完整个数组。

下面这组代码优化后效率并没有很大的提升，只是代码更为简洁。

这组代码是齐头并进，排完第一组的前n个就排下一组了，并没有把第一组全部排完。

int gap;for (int i = 0; i < n - gap; i++){//子序列int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + 3] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}

希尔排序代码

分析

gap越大，大的值更快调到后面，小的值更快调到前面，越不接近有序。
gap越小，大的值更慢调到后面，小的值更慢调到前面，越接近有序。
当gap为1，就是直接插入排序。

所以我们这里的gap值应该是在变化的，一般我们随n变化，取gap = gap/3+1，或者gap = gap/2;

void ShellSort(int* a,int n)
{int gap = n;while (gap>1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){//子序列int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

这里无论gap是奇数还是偶数，这里gap最终都会除以到值为1。