衡阳商城网站建设/网络推广方法有哪些

原理：

希尔排序是希尔在插入排序的基础上的改进。
大概是先将待排数组分为gap个数组，每组中的每个数在数组中的间隔为gap，分在在每组中进行插入排序，然后每次gap=gap/2，直到最后gap=1，还原为一个组的数据，这时候数组里面的值就变为大致有序，最后进行一次插入排序，就得到了有序数组。

图示：

代码实现：

public class ShellSort {public void sort(int[] arr,int n){int i,j,gap,k;//依次设置gap步长，同时也是分组数量for(gap=n/2;gap>0;gap/=2 ){//每一个I代表一个组for(i=0;i<gap;i++){//开始每组的插入排序，从无序的第一个数开始for(j=i+gap;j<n;j+=gap){//只有前面那个数大于这个数的时候才有必要查找位置，因为前面的是有序的if(arr[j]<arr[j-gap]){int temp = arr[j];//开始将前面的大于temp数向后移动for(k=j-gap;k>=0;k-=gap){if(arr[k]>temp){arr[k+gap]=arr[k];}//遇到比temp小的数就可以退出循环了else break;}arr[k+gap]= temp;}}}}}public static void main(String[] args) {int[] a = {80,35,210,40,20,0,50,29};new SelectSort().sort(a,a.length);System.out.println(Arrays.toString(a));}
}

时间复杂度

希尔排序的时间复杂度与增量(即，步长gap)的选取有关。例如，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)，而Hibbard增量的希尔排序的时间复杂度为O(N3/2)。

希尔排序不是稳定算法。

学习链接