网站域名过期怎么办,网页制作电脑软件,建设银行银行号查询网站,郴州网课算法说明 希尔排序是插入排序的优化版。 插入排序的最坏时间复杂度是O(n2)#xff0c;但如果要排序的数组是一个几乎有序的数列#xff0c;那么会降低有效的减低时间复杂度。 希尔排序的目的就是通过一个increment#xff08;增量#xff09;来对数列分组进行交换排序…算法说明 希尔排序是插入排序的优化版。 插入排序的最坏时间复杂度是O(n2)但如果要排序的数组是一个几乎有序的数列那么会降低有效的减低时间复杂度。 希尔排序的目的就是通过一个increment增量来对数列分组进行交换排序最终使数列几乎有序最后再执行插入排序统计出结果。 通过incrementn/2 也就是如果9个数的话增量为421。 如果是20个数的话增量就是10521。 当increment为1时其实对几乎有序的数列进行插入排序啦啦。 时间复杂度 O(n2/3) 空间复杂度 O(1) 代码 使用的是Java /** 希尔排序*/
public class ShellSort {public static void main(String[] args) {int[] arrayData { 5, 9, 6, 7, 4, 1, 2, 3, 8 };ShellSortMethod(arrayData);for (int integer : arrayData) {System.out.print(integer);System.out.print( );}}public static void ShellSortMethod(int[] arrayData) {int i, j, temp 0;int increment arrayData.length;do {increment increment / 2; //增量for (i increment; i arrayData.length; i) {if (arrayData[i] arrayData[i - increment]) { //判断是否要进行插入排序temp arrayData[i]; //将要插入的值存放在临时变量中//这里其实做的就是插入排序将以增量为步长往后移动。 //temp arrayData[j] 这个是要注意的只会移动比要插入的值小的数字for (j i - increment; j 0 temp arrayData[j]; j - increment) {arrayData[j increment] arrayData[j];}arrayData[j increment] temp;}}} while (increment 0);}
}结果 9 8 7 6 5 4 3 2 1
