微信号:grzlwx

介绍:光荣之路官方资讯

八大种必知排序算法(二) 选择排序,插入排序,希尔算法(续)

2015-09-01 22:59 光荣之路

三、希尔算法

1、基本思想:

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

2、操作方法:

  1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;

  2. 按增量序列个数k,对序列进行k 趟排序;

  3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

希尔排序的示例:


3、算法实现:

/**希尔排序的原理:根据需求,如果你想要结果从大到小排列,它会首先将数组进行分组,然后将较大值移到前面,较小值
* 移到后面,最后将整个数组进行插入排序,这样比起一开始就用插入排序减少了数据交换和移动的次数,可以说希尔排序是加强
* 版的插入排序
* 拿数组5, 2, 8, 9, 1, 3,4来说,数组长度为7,当increment为3时,数组分为两个序列
* 5,2,8和9,1,3,4,第一次排序,9和5比较,1和2比较,3和8比较,4和比其下标值小increment的数组值相比较
* 此例子是按照从大到小排列,所以大的会排在前面,第一次排序后数组为9, 2, 8, 5, 1, 3,4
* 第一次后increment的值变为3/2=1,此时对数组进行插入排序,
*实现数组从大到小排
*/

public static void shellSort(int[] data)
{
int j = 0;
int temp = 0;
//每次将步长缩短为原来的一半
for (int increment = data.length / 2; increment > 0; increment /= 2)
{
for (int i = increment; i < data.length; i++)
{
temp = data[i];
for (j = i; j >= increment; j -= increment)
{
if(temp > data[j - increment])//如想从小到大排只需修改这里
{
data[j] = data[j - increment];
}
else
{
break;
}

}
data[j] = temp;
}

}
}


4、效率

 时间复杂度:O(n^2). 

4、各种算法的时间复杂度

冒泡排序、快速排序可查看:http://www.cnblogs.com/0201zcr/p/4763806.html

归并排序、堆排序可查看:http://www.cnblogs.com/0201zcr/p/4764705.html

  致谢:感谢您的耐心阅读!

(作者:WhyWin 来源:http://www.cnblogs.com/0201zcr/p/4764427.html)


 
            
 
            
 
            
 
           
 
           
 
           
 
           
 
           
 
           
 
           
 
           
 
           
 
           

一字一句当思来之不易,感谢作者,传播测试知识、技能与正能量!

光荣之路软件测试培训

官网:http://www.gloryroad.cn/

微信公众号:gloryroadtrain

性能测试QQ群:415987441
软件测试招聘QQ群: 203715128
自动化3群QQ: 371211499


 
光荣之路 更多文章 今天晚上的 linux 公开课- Awk 编程 7月28日(今天)晚上的 linux 公开课- shell编程 8月4日(今天)晚上的 linux 公开课- shell编程 9月1日(本周一)晚8点半,光荣之路Web自动化系列基础课—javascript第二讲 推荐本好书《与机器赛跑》
猜您喜欢 树莓派是什么(waht is reapberry pi) ​iOS 中的设计模式 (Swift 版本) 从一个简单的C++程序学起 利用python进行数据分析案例一(一见钟情对python) 探讨下DevOPS