【算法-希尔排序】
对关键字{10,20,8,25,35,6,18,30,5,15,28}序列进行希尔排序，取增量d =5时，排序结果为（ ）
A. {6,18,8,5,15,10,20,30,25,35,28} B. {10,18,8,5,15,6,20,30,25,35,28} C. {10,20,8,5,15,6,18,30,25,35,28} D. {10,20,30,5,8,6,15,18,25,28,35}
【算法定义】
希尔排序
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
【代码实现】
方式一：
package com.liuy;
public class ShellSortDemo1 {
public static void main(String[] args) {
int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1 };
System.out.println("排序之前：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
// 希尔排序
int d = a.length;
while (true) {
for (int i = 0; i < d; i++) {
for (int j = i; j + d < a.length; j += d) {
int temp;
if (a[j] > a[j + d]) {
temp = a[j];
a[j] = a[j + d];
a[j + d] = temp;
}
}
}
if (d == 1) {
break;
}
d--;
}
System.out.println();
System.out.println("排序之后：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}方式二：
package com.util;
public class ShellSort {
public static void main(String [] args)
{
int[]a={49,38,65,97,76,13,27,49,78,34,12,64,1};
System.out.println("排序之前：");
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+" ");
}
//希尔排序
int d=a.length;
while(true)
{
d=d/2;
for(int x=0;x<d;x++)
{
for(int i=x+d;i<a.length;i=i+d)
{
int temp=a[i];
int j;
for(j=i-d;j>=0&&a[j]>temp;j=j-d)
{
a[j+d]=a[j];
}
a[j+d]=temp;
}
}
if(d==1)
{
break;
}
}
System.out.println();
System.out.println("排序之后：");
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+" ");
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录