京东2017校园招聘笔试真题（希尔排序）

对关键字{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时，整个文件恰被分成一组，算法便终止。

JAVA代码实现

实现方式一：

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){ 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]+" "); } } }