首页 / 算法 / 希尔排序—高效排序算法
希尔排序—高效排序算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了希尔排序—高效排序算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1583字，纯文字阅读大概需要3分钟。
内容图文
在前面文章中介绍的直接插入排序，它对于已经基本有序的数据进行排序，效率会很高，而如果对于最初的数据是倒序排列的，则每次比较都需要移动数据，导致算法效率降低。
希尔排序的基本思想就是：将需要排序的序列划分为若干个较小的序列，对这些序列进行直接插入排序，通过这样的操作可使需要排序的数列基本有序，最后再使用一次直接插入排序。
在希尔排序中首先要解决的是怎样划分序列，对于子序列的构成不是简单地分段，而是采取将相隔某个增量的数据组成一个序列。一般选择增量的规则是：取上一个增量的一半作为此次子序列划分的增量，一般初始值元素的总数量。
-
算法步骤：
初始化数组：
|
|
(1) 使用元素总数量的一半（8）作为增量，将数屈打成招划分为8个序列，对这8个序列分别进行排序
|
|
(2) 将增量缩小一半（值为4），重新划分子序列，得到4个子序列，对这4个子序分别进行排序，得到第2遍排序后的结果。
|
|
(3) 缩小增量为2，得到如下结果：
|
|
(4) 第4遍增量为1,得到最终的排序结果：
|
|
-
代码实现：
|
public class ShellSort {
public static void main(String[] args ) { int arr []={32,24,95,45,75,22,95,49,3,76,56,11,37,58,44,19,81}; System. out .println( " 排序前： " +Arrays.toString( arr )); sort( arr ); System. out .println( " 排序后： " +Arrays.toString( arr )); } public static void sort( int arr []) { int d = arr . length /2; int x , j , k =1; while ( d >=1) { for ( int i = d ; i < arr . length ; i ++) { x = arr [ i ]; j = i - d ; // 直接插入排序，会向前找所适合的位置 while ( j >=0 && arr [ j ]> x ) { // 交换位置 arr [ j + d ]= arr [ j ]; j = j - d ; } arr [ j + d ]= x ; } d = d /2; System. out .println( " 第 " + k ++ + " 趟： " +Arrays.toString( arr )); } } } |
|
排序前： [32, 24, 95, 45, 75, 22, 95, 49, 3, 76, 56, 11, 37, 58, 44, 19, 81] 第 1 趟： [3, 24, 56, 11, 37, 22, 44, 19, 32, 76, 95, 45, 75, 58, 95, 49, 81] 第 2 趟： [3, 22, 44, 11, 32, 24, 56, 19, 37, 58, 95, 45, 75, 76, 95, 49, 81] 第 3 趟： [3, 11, 32, 19, 37, 22, 44, 24, 56, 45, 75, 49, 81, 58, 95, 76, 95] 第 4 趟： [3, 11, 19, 22, 24, 32, 37, 44, 45, 49, 56, 58, 75, 76, 81, 95, 95] 排序后： [3, 11, 19, 22, 24, 32, 37, 44, 45, 49, 56, 58, 75, 76, 81, 95, 95] |
原文：http://blog.51cto.com/13733462/2114341
内容总结
以上是互联网集市为您收集整理的希尔排序—高效排序算法全部内容，希望文章能够帮你解决希尔排序—高效排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。