赞
踩
算法基础: 开始回顾下基础算法中的经典排序算法
算法思想:希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至一时,整个文件恰被分成一组,算法便终止。重点是分组,然后排序
ublic class 希尔排序 { /** * @Description 希尔排序 从小到大 * 初始 4, 5, 6, 3, 2, 1, 9, 8, 10 * 步长 = n/2,每次都步长结束,都除以2 ,直到1为止 * 初始长度为 9 第一次步长为 4,那么分组即: 4-2,5-1,6-9,3-8,2-10, * 比较之后交换:交换后的顺序为 2, 1, 6, 3, 4, 5, 9, 8, 10 * 第二次步长为 2 那么分组即: 2-6,1-3,6-4,3-5,4-9,5-8,9-10 * 比较之后交换:交换后的顺序为 2, 1, 4, 3, 6, 5, 9, 8, 10 * ...................... * @Author 寂寞旅行 * @Date 10:26 2022/2/26 * @Param [args] **/ public static void main(String[] args) { int[] arr = {4, 5, 6, 3, 2, 1, 9, 8, 10}; int buchang = arr.length / 2; int index = 0; while (buchang >= 1) { index++; for (int i = 0; i < arr.length; i++) { int temp; for (int j = buchang + i; j < arr.length; j += buchang) { if (arr[i] > arr[j]) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } buchang = buchang / 2; System.out.println("第" + index + "次" + Arrays.toString(arr)); } /** * 第1次[2, 1, 6, 3, 4, 5, 9, 8, 10] * 第2次[2, 1, 4, 3, 6, 5, 9, 8, 10] * 第3次[1, 2, 3, 4, 5, 6, 8, 9, 10] **/ } }
可以看到希尔排序的核心思想是分组,然后排序;例如长度为n
第一次 步长 = n/2 ,也就是将元素进行分组,将所有i+=步长 分为一组,然后进行组内排序;
第二次 步长= 步长/2 ,再次将所有元素分组,将所有i+=步长 分为一组,然后进行组内排序;
…
直到步长为1,相当于所有元素都在同一组内,然后进行排序,至此循环结束;完成排序;
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。