首页 > 开发 > Java > 正文

java数据结构与算法之希尔排序详解

2024-07-13 10:07:26
字体:
来源:转载
供稿:网友

本文实例讲述了java数据结构与算法之希尔排序。分享给大家供大家参考,具体如下:

这里要介绍的是希尔排序(缩小增量排序法)。

希尔排序:通过比较相距一定间隔的元素来工作;各趟比较所用的距离(增量)随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。是插入排序的一种,是针对直接插入排序算法的改进。

算法思想:先将要排序的序列按某个增量d分成若干个子序列,对每个子序列中全部元素分别进行直接插入排序,然后再用一个较小的增量对它进行分组,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。注意:增量的取值——一般的初次取序列的一半为增量,以后每次减半,直到增量为1。

算法实现代码如下:

package exp_sort;public class ShellSort {  public static void shell(int array[]) {    int j;    int average;    //设置增量的值    for (average = array.length / 2; average > 0; average /= 2) { //步长      for (int i = average; i < array.length; i++) { //子序列进行直接插入排序        int temp = array[i];        for (j = i; j >= average && temp < array[j - average]; j -= average) {          array[j] = array[j - average];        }        array[j] = temp;      }    }    for (int i = 0; i < array.length; i++) {      System.out.print(array[i] + " ");    }    System.out.println("/n");  }  public static void main(String[] args) {    // TODO Auto-generated method stub    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };    shell(array);  }}

算法分析:该算法是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比O(n^2)好一些,为O(n^1.5)排序效率比插入排序高很多。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。希尔排序没有快速排序算法快 O(N*(logN)),因此对中等大小规模的数据排序比较适用,对规模非常大的数据排序不是最优选择。但是比O(N^2)复杂度的算法快得多。并且希尔排序非常容易实现,算法代码短而简单。 此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏的情况下执行的效率会非常差。

希望本文所述对大家java程序设计有所帮助。


注:相关教程知识阅读请移步到JAVA教程频道。
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表