教育培训机构微网站模板,如何建设一个视频小网站,北京住房城乡建设部网站八大员,航天基地规划建设局网站引言 排序在我们生活中十分常见#xff0c;无论是购物软件中的商品推荐还是名次、排名都与排序算法息息相关。希尔排序是排序中较快的一种#xff0c;而希尔排序实现的基础是插入排序。
排序的实现
插入排序#xff08;以升序为例#xff09; 插入排序的原理是从第二个数…
引言 排序在我们生活中十分常见无论是购物软件中的商品推荐还是名次、排名都与排序算法息息相关。希尔排序是排序中较快的一种而希尔排序实现的基础是插入排序。
排序的实现
插入排序以升序为例 插入排序的原理是从第二个数开始与前面的数相比较如果比前面的数大则与其交换并且此移动过程会一直持续直到前kk为此次刚开始移动的数的位置个数达到有序为止否则不会移动。代码如下
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];--end;}else{break;}}a[end 1] tmp;}} 我们将一直要改变的那个数设为tmp,将它与前面的数end比较如果tmp较小则进行交换先将啊a[end] 覆盖a[end 1],再--end达到tmp继续与前一个数比较的效果最后达到效果.
希尔排序 希尔排序分为两步预排序与插入排序.
预排序
预排序的目的是先让数组接近有序将所有数据分为gap组其代码与插入排序十分类似。 以该图为例改预排序的流程是5与9比较如果比9小则将9放到原来5的位置 再将8与9相比较并与5比较8比9小再将9放到8的位置8比5大所以再停止 最后将最后的5进行排序即可.
再嵌套一层循环使其达到排三组循环的效果 9--5--8--5
1--7--6
2--4--3
代码如下
void ShellSort(int* a, int n)
{int gap 3;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 gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
} 我们也可以只用两层循环实现即分组排序的顺序改为
9--5,1--7,2--4,5--8,7--6,4--3,8--5.实现代码如下
//Shell排序的双层循环的写法void ShellSort(int* a, int n)
{int gap 3;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一般取整个数组的数量除以三为保证最后一次一定是1我们将其设为gap gap / 3 1,这样最后就可以由一个插入排序对预排序后的数组进行总排序.并且我们每次预排序都会使数组更加有序代码如下
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;}}
}
希尔排序的速度
在release环境下测试100,000个数据其结果如下
我们发现希尔排序的速度是与堆排序是一个数量级的而插入排序的速度也是比冒泡排序要快一个量级的.
测试1,000,000个数据 测试10,000,000个数据 堆排序的时间复杂度是O(),所以希尔排序的速度算是非常快的有实践意义。
希尔排序的时间复杂度是 O().
