在手机上怎么赚钱,seo优化技术,创办一个公司需要什么条件,wordpress 插件编写访问www.tomcoding.com网站#xff0c;学习Oracle内部数据结构#xff0c;详细文档说明#xff0c;下载Oracle的exp/imp#xff0c;DUL#xff0c;logminer#xff0c;ASM工具的源代码#xff0c;学习高技术含量的内容。
如果你在网上搜一下希尔排序#xff0c;都会告…访问www.tomcoding.com网站学习Oracle内部数据结构详细文档说明下载Oracle的exp/impDULlogminerASM工具的源代码学习高技术含量的内容。
如果你在网上搜一下希尔排序都会告诉你希尔排序也是一种插入排序它是简单插入排序经过改进之后的一个更高效的版本也称为缩小增量排序。然后列一些图标或动画演示最后给出一个算法函数。你看了以后还是不知道什么是希尔排序里面的图太复杂你看上好几遍也不能抓住重点。
我们来看一下希尔排序算法要解决的问题都说希尔算法是插入排序的改进版那么为什么要改进呢原因是插入排序要进行大量的元素交换位置移动在完全升序排列的数组中算法最高效不需要进行交换在完全降序的数组中算法效率最低。为了改善这种情况希尔排序把数组中的元素先进行多个分组然后把每个分组按照插入排序算法升序排列然后减少分组的个数再进行插入排序最后预排序的数组不再分组进行最后一次插入排序。预排序的目的就是把数组中数值小的元素尽量放到数组前面减少最后一次排序元素交换的次数。
那么怎样分组呢最容易想到的就是第一次分组使得两个元素一组那么如果有n个元素就有n/2个分组如果n不能被2整除那么留下一个元素不分组。第二次分组把第一次分组的个数再减半依次类推直到再减半就是0了说明是最后一次分组了那么把最后一次分组进行一次插入排序数组中的元素就按升序排列好了。这里数组元素个数为单数时最后一个元素不参与分组排序直到最后一次插入排序时才参与。
看一下程序。
static void shell_sort(int *ai, int n)
{ int i, j; int gap, ne; int *t; /* gap是间隙表示每隔gap值的元素分为一组 * ne是每一组中包含多少个元素 * 在这里先分配跟原数组大小一样的数组用于分组 */ if ((t (int *)malloc(n*sizeof(int))) NULL) return; /* 起始gap取元素个数的半数值这样每一组只包含两个元素 * gap每次循环后减半直到为1退出循环进行最后一次插入排序 */ for (gap n/2, ne n/gap; gap 1; gap / 2, ne n/gap) { /* 把原数组ai中的元素分组分完组后进行插入排序 */ for (i 0; i gap; i) { /* 下面的循环完成后生成了一个分组 */ for (j 0; j ne; j) t[i*nej] ai[ij*gap]; /* 对刚生成的分组排序 */ insertion_sort(t[i*ne], ne); } /* 每一次分组排序结束后把排序后的元素恢复到原来数组的位置上 */ for (i 0; i gap; i) { for (j 0; j ne; j) ai[ij*gap] t[i*nej]; } } /* gap1进行最后一次排序这时如果元素个数是单数最后一个元素也会参与排序 */ insertion_sort(ai, n); /* 释放掉分配的内存 */ free(t);
} 上面实现的这个排序算法看起来臃肿还需要辅助的数组但直观的表现了希尔算法是分组插入排序算法的本质。
其实每个组都是相同间隔的元素组成的还是在同一个数组中这样把插入排序算法揉进分组里去就能简化代码看一下整合后的函数。
void shell_sort(int *ai, int n) { int i, j; int gap, t; for(gap n/2; gap 0; gap / 2) { for(i gap; i n; i) { for(j i - gap; j 0 ai[j] ai[jgap]; j - gap) { /* 交换元素位置 */ t ai[j]; ai[j] ai[jgap]; ai[jgap] t; } } }
}
