利用Java实现一个希尔排序的方法?针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。一、希尔排序(shell Sort)希尔排序(Shell Sort)是一种插入排序算法,因D
利用Java实现一个希尔排序的方法?针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。
一、希尔排序(shell Sort)
希尔排序(Shell Sort)是一种插入排序算法,因D.L.Shell于1959年提出而得名。
Shell排序又称作缩小增量排序。
二、希尔排序的基本思想
希尔排序的中心思想就是:将数据进行分组,然后对每一组数据进行排序,在每一组数据都有序之后,就可以对所有的分组利用插入排序进行最后一次排序。这样可以显著减少交换的次数,以达到加快排序速度的目的。
希尔排序的中心思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
shell排序的算法实现:
void ShellPass(SeqList R,int d) {//希尔排序中的一趟排序,d为当前增量 for(i=d+1;i<=n;i++) //将R[d+1..n]分别插入各组当前的有序区 if(R[i].key<R[i-d].key){ R[0]=R[i];j=i-d; //R[0]只是暂存单元,不是哨兵 do {//查找R[i]的插入位置 R[j+d];=R[j]; //后移记录 j=j-d; //查找前一记录 }while(j>0&&R[0].key<R[j].key); R[j+d]=R[0]; //插入R[i]到正确的位置上 } //endif } //ShellPass void ShellSort(SeqList R) { int increment=n; //增量初值,不妨设n>0 do { increment=increment/3+1; //求下一增量 ShellPass(R,increment); //一趟增量为increment的Shell插入排序 }while(increment>1) } //ShellSort
--结束END--
本文标题: 利用Java实现一个希尔排序的方法
本文链接: https://www.lsjlt.com/news/227094.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0