介绍:
希尔排序又叫缩小增量排序,是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减少至1时,整个数组恰好被分为一组,算法终止。
缩小增量后可以采用两种排序法:交换(冒泡)、位移(插入) 后者效率更高。
代码:
public class shellSort { public static void main(String[] args) { int[] nums = {8,9,1,7,2,3,5,4,6,0}; shellSort(nums); //shellShort2(nums); } //交换法 增量shell排序 public static void shellSort(int[] nums){ int count = 0; //计数器 int temp = 0; //交换用 for (int gap = nums.length / 2; gap > 0 ; gap /= 2) { for (int i = gap; i < nums.length ; i++) { //遍历各组中的所有元素 步长为gap int j = i; while(j - gap >= 0 && nums[j] < nums[j-gap]){ temp = nums[j]; nums[j] = nums[j - gap]; nums[j - gap] = temp; j -= gap; } } count++; System.out.println("希尔排序第"+count+"轮排序后:"+ Arrays.toString(nums)); } } //移位式希尔排序 (增量分组后采用插入排序) public static void shellShort2(int[] nums){ int count = 0; //增量gap,逐步缩小增量 for (int gap = nums.length/2 ; gap > 0 ; gap /= 2) { //从第gap元素,逐个对其所在的组直接插入 for (int i = gap; i < nums.length ; i++) { int j = i; int temp = nums[j]; //待插入的元素 if (nums[j] < nums[j - gap]){ while(j - gap >=0 && temp < nums[j - gap]){ //移动 nums[j] = nums[j - gap]; j -= gap; } //当退出while循环时,找到插入位置了 nums[j] = temp; } } count++; System.out.println("希尔排序第"+count+"轮排序后:"+ Arrays.toString(nums)); } } }
时间复杂度
时间复杂度为O(n^1.5),要好于直接排序的O(n ^ 2),需要注意的是增量序列的最后一个增量值必须是1.另外由于记录跳跃式的移动,希尔排序并不是一种稳定的排序方法。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)