排序算法-----希尔排序

1959年Shell发明，第一个突破O（n^2）的排序算法，是简单插入排序的改进版，它与插入排序的不同之处在于，他会优先比较距离较远的元素，希尔排序又叫缩小增量排序。

时间复杂度：O（n^1.3）空间复杂度：O（1）稳定性：不稳定 package 排序算法; import java.util.Arrays; //O(n^1.3) public class ShellSort { public static void main(String[] args) { int arr[] ={9,1,8,2,7,3,6,4,5}; shellSort(arr); System.out.println(Arrays.toString(arr)); } private static void shellSort(int[] arr) { int j=0; int e=0; for(int gap=arr.length/2;gap>0;gap=gap/2){ for (int i=gap;i<arr.length;i++){ j=0; e=arr[i]; for (j=i;j-gap>=0&&arr[j-gap]>e;j=j-gap){ arr[j]=arr[j-gap]; } arr[j]=e; } } } }

执行结果

[1, 2, 3, 4, 5, 6, 7, 8, 9]