数据结构排序系列详解之二 希尔排序
希尔排序:通过比较相距一定间隔的元素来工作;各趟比较所用的距离(增量)随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。是插入排序的一种,是针对直接插入排序算法的改进。
算法思想:先将要排序的序列按某个增量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)复杂度的算法快得多。并且希尔排序非常容易实现,算法代码短而简单。 此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏的情况下执行的效率会非常差。
补充:软件开发 , C语言 ,