数据结构与算法day19-希尔排序算法

希尔排序：简单插入排序存在的问题：我们看简单的插入排序可能存在的问题数组 arr = {2, 3, 4, 5, 6, 1} 这时需插入的数1(最小)，这样的过程是：{2, 3, 4, 5, 6, 6}{2, 3, 4, 5, 5, 6}{2, 3, 4, 4, 5, 6}{2, 3, 3, 4, 5, 6}{2, 2, 3, 4, 5, 6}{1, 2, 3, 4, 5, 6}结论：当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。希尔排序介绍：希尔排序是希尔(DonaldShell)于1995年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进后一个高效版本，也称为缩小增量排序。希尔排序法基本思想：希尔排序是记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键字越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

希尔排序图解：

希尔排序总结：经过上面的"分组插入排序"，整个数组的实现了基本的有序化。此时仅仅需要对以上数组简单微调，无需大量移动操作即可完成整个数组的排序希尔排序应用实例：有一群牛，考试成绩分别为{8, 9, 1, 7, 2, 3, 5, 4, 6, 0}，请从小到大排序，请分别使用1)希尔排序时，对有序序列在插入时采用交换法，并测试排序速度2)希尔排序时，对有序序列在插入时采用移动法，并测试排序速度

希尔排序(交换法)笨代码如下：推导代码

package sort2;import java.util.Arrays;public class ShellSort {public static void main(String[] args) {// TODO Auto-generated method stubint[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};shellSort(arr);}// 使用逐步推导的方式编写希尔排序public static void shellSort(int[] arr) {int temp = 0;// 希尔排序的第1轮排序// 因为第1轮排序，是将10个数据分成了5组--> 10/2for (int i = 5; i < arr.length; i++) {// 遍历各组中所有的元素(共5组，每组有2个元素)，步长为5for (int j = i-5; j >= 0; j -= 5) {// 为什么此处-=5会退出，因为每组数据只有2个数据，比较完就退出了// 如果当前元素大于加上步长后的那个元素，要交换if (arr[j] > arr[j+5]) {temp = arr[j];arr[j] = arr[j+5];arr[j+5] = temp;}}}// 3 5 1 6 0 8 9 4 7 2System.out.println("希尔排序1轮后："+Arrays.toString(arr));// 希尔排序的第2轮排序// 因为第2轮排序，是将10个数据分成了2组--> 10/5/2for (int i = 2; i < arr.length; i++) {// 此处不断增量，代表初始最大比较位置不断变化// 遍历各组中所有的元素(共2组，每组有5个元素)，步长为2// 步长是2，但是要从下标0开始// 第1次 j=2-2，比较的是 arr[0] arr[0+2] 第1组// 第2次 j=3-2，比较的是 arr[1] arr[1+2] 第2组// 第3次 j=4-2，比较的是 arr[2] arr[2+2] 第1组// 第4次 j=5-2，比较的是 arr[3] arr[3+2] 第2组// 第5次 j=6-2，比较的是 arr[4] arr[4+2] 第1组// ....依次类推，将2组中的每组5个元素都分别比较完for (int j = i-2; j >= 0; j -= 2) {// -=2这个步长设置的作用，是分组数据的作用// 遍历的目的是，当不断比较的时候，每组中需要比较// 的数据需要每次在当前循环中所有数据进行遍历比较// 如果当前元素大于加上步长后的那个元素，要交换if (arr[j] > arr[j+2]) {temp = arr[j];arr[j] = arr[j+2];arr[j+2] = temp;}}}// 0 2 1 4 3 5 7 6 9 8System.out.println("希尔排序2轮后："+Arrays.toString(arr));// 希尔排序的第3轮排序// 因为第3轮排序，是将10个数据分成了1组--> 10/5/2/2for (int i = 1; i < arr.length; i++) {for (int j = i-1; j >= 0; j--) {// 如果当前元素大于加上步长后的那个元素，要交换if (arr[j] > arr[j+1]) {temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9System.out.println("希尔排序3轮后："+Arrays.toString(arr));}}

希尔排序(交换法)通用代码如下：速度比移步法慢 本质是分组+冒泡排序

package sort2;import java.util.Arrays;public class ShellSort {public static void main(String[] args) {// TODO Auto-generated method stubint[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};shellSort(arr);}public static void shellSort(int[] arr) {int temp = 0;int count = 0;// 根据前面的逐步分析，使用循环处理for (int gap = arr.length/2; gap > 0; gap /= 2) {// 此处是分组的作用// 遍历各组中所有的元素(共gap组，每组有n个元素)，步长为gap// 外层for用于递增找到所有的元素// 内层for用于递减步长比较所有元素for (int i = gap; i < arr.length; i++) {for (int j = i-gap; j >= 0; j -= gap) {// 如果当前元素大于加上步长后的那个元素，要交换if (arr[j] > arr[j+gap]) {// +gap的目的是为了分组内元素进行比较temp = arr[j];arr[j] = arr[j+gap];arr[j+gap] = temp;}}}System.out.println("希尔排序"+(++count)+"轮后："+Arrays.toString(arr));}}}

希尔排序(移位法)代码如下：通用代码 本质是分组+插入排序

package sort2;import java.util.Arrays;public class ShellSort {public static void main(String[] args) {// TODO Auto-generated method stubint[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};shellSort(arr);System.out.println(Arrays.toString(arr));}// 使用逐步推导的方式编写希尔排序// 对交换式的希尔排序进行优化--> 移位法public static void shellSort(int[] arr) {// 增量gap，并逐步缩小增量for (int gap = arr.length/2; gap > 0; gap /= 2) {// 从gap个元素开始，逐个对其所在的组进行直接插入排序for (int i = gap; i < arr.length; i++) {int j = i;int temp = arr[j];if (arr[j] < arr[j-gap]) {while(j - gap >= 0 && temp < arr[j-gap]) {// 为什么此处用temp而不用arr[j]// 移动arr[j] = arr[j-gap];j -= gap;}// 当退出while循环时，就给temp找到插入的位置arr[j] = temp;}}}}}