Java 十大排序算法之希尔排序刨析

Java 十大排序算法之希尔排序刨析

目录希尔排序原理希尔排序的API设计希尔排序的代码实现

希尔排序是插入排序的一种，又称"缩小增量排序”，是插入排序算法的一种更高效的改进版本。

希尔排序原理

1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组。

2.对分好组的每一组数据完成插入排序。

3.减小增长量，最小减为1，重复第二步操作。

希尔排序的API设计

类名

Shell

构造方法

Shell():创建Shell对象

成员方法

1.public static void sort(Comparable[] a):对数组内的元素进行排序

2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w

3.private static void exchange(Comparable[] a,int i,int j):交换a数组中，索引i和索引j处的值

希尔排序的代码实现

public class Shell {

//对数组a中的元素进行排序

public static void sort(Comparable[] a){

int N=a.length;

//确定增长量h的最大值

int h=1;

while(h

h=2*h+1;

}

//当增长量h小于1，排序结束

while(h>=1){

//找到待插入的元素

for(int i=h;i

//a[i]就是待插入的元素

//把a[i]插入到a[i-h],a[i-2h],a[i-3h]...序列中

for(int j=i;j>=h;j-=h){

//a[j]就是待插入的元素，依次和a[j-h],a[j-2h],a[j-3h]进行比较，如果a[j]小，

wnovEEbqMu // 那么交换位置，如果不小于，a[j]大，则插入完成

if(greater(a[j-h],a[j])){

exchange(a,j,j-h);

}else{

break;

}

}

}

h/=2;

}

}

//比较v元素是否大于w元素

private static boolean greater(Comparable v,Comparable w){

return v.compareTo(w)>0;

}

//数组元素i和j交换位置

private static void exchange(Comparable[] a,int i,int j){

Comparable t=a[i];

a[i]=a[j];

a[j]=t;

}

}

class Test{

public static void main(String[] args) {

Integer[] a={9,1,2,5,7,4,8,6,3,5};

Shell.sort(a);

System.out.println(Arrays.toString(a));

}

}

测试结果：

由于增量h没有固定的值，希尔排序的时间复杂度较为复杂，但在处理大批量数据时，希尔排序的性能高于插入排序！

h=2*h+1;

}

//当增长量h小于1，排序结束

while(h>=1){

//找到待插入的元素

for(int i=h;i

//a[i]就是待插入的元素

//把a[i]插入到a[i-h],a[i-2h],a[i-3h]...序列中

for(int j=i;j>=h;j-=h){

//a[j]就是待插入的元素，依次和a[j-h],a[j-2h],a[j-3h]进行比较，如果a[j]小，

wnovEEbqMu // 那么交换位置，如果不小于，a[j]大，则插入完成

if(greater(a[j-h],a[j])){

exchange(a,j,j-h);

}else{

break;

}

}

}

h/=2;

}

}

//比较v元素是否大于w元素

private static boolean greater(Comparable v,Comparable w){

return v.compareTo(w)>0;

}

//数组元素i和j交换位置

private static void exchange(Comparable[] a,int i,int j){

Comparable t=a[i];

a[i]=a[j];

a[j]=t;

}

}

class Test{

public static void main(String[] args) {

Integer[] a={9,1,2,5,7,4,8,6,3,5};

Shell.sort(a);

System.out.println(Arrays.toString(a));

}

}

测试结果：

由于增量h没有固定的值，希尔排序的时间复杂度较为复杂，但在处理大批量数据时，希尔排序的性能高于插入排序！

//a[i]就是待插入的元素

//把a[i]插入到a[i-h],a[i-2h],a[i-3h]...序列中

for(int j=i;j>=h;j-=h){

//a[j]就是待插入的元素，依次和a[j-h],a[j-2h],a[j-3h]进行比较，如果a[j]小，

wnovEEbqMu // 那么交换位置，如果不小于，a[j]大，则插入完成

if(greater(a[j-h],a[j])){

exchange(a,j,j-h);

}else{

break;

}

}

}

h/=2;

}

}

//比较v元素是否大于w元素

private static boolean greater(Comparable v,Comparable w){

return v.compareTo(w)>0;

}

//数组元素i和j交换位置

private static void exchange(Comparable[] a,int i,int j){

Comparable t=a[i];

a[i]=a[j];

a[j]=t;

}

}

class Test{

public static void main(String[] args) {

Integer[] a={9,1,2,5,7,4,8,6,3,5};

Shell.sort(a);

System.out.println(Arrays.toString(a));

}

}

测试结果：

由于增量h没有固定的值，希尔排序的时间复杂度较为复杂，但在处理大批量数据时，希尔排序的性能高于插入排序！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。