uc官网网站开发者中心,网站一年了百度不收录,长沙圭塘网站建设公司,网站维护什么情况7.8希尔排序
7.8.1简单插入排序存在的问题
我们看简单的插入排序可能存在的问题. 数组 arr {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是#xff1a; {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} 结论: 当需要插入的数…7.8希尔排序
7.8.1简单插入排序存在的问题
我们看简单的插入排序可能存在的问题. 数组 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} 结论: 当需要插入的数是较小的数时后移的次数明显增多对效率有影响.
7.8.2希尔排序法介绍
希尔排序是希尔Donald Shell于1959年提出的一种排序算法。希尔排序也是一种插入排序它是简单插入排序经过改进之后的一个更高效的版本也称为缩小增量排序。
7.8.3希尔排序法基本思想
希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至1时整个文件恰被分成一组算法便终止
7.8.4希尔排序法的示意图 7.8.5希尔排序法应用实例:
有一群小牛, 考试成绩分别是 {8,9,1,7,2,3,5,4,6,0} 请从小到大排序. 请分别使用
希尔排序时 对有序序列在插入时采用交换法, 并测试排序速度.希尔排序时 对有序序列在插入时采用移动法, 并测试排序速度代码实现
交换法
推导过程的代码
import java.text.SimpleDateFormat;
import java.util.Date;/*** 希尔排序(交换法)*/
public class ShellSort {public static void main(String[] args) {int[] 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组for (int i 5; i arr.length; i) {//遍历各组中所有的元素共5组每组有2个元素步长5for (int j i - 5; j 0; j - 5) {//如果当前元素大于加上步长后的那个元素说明交换if (arr[j] arr[j 5]) {temp arr[j];arr[j] arr[j 5];arr[j 5] temp;}}}System.out.println(希尔排序1轮后 Arrays.toString(arr));//希尔排序的第2轮排序//因为第2轮排序是将10个数据分成了5 /2 2组for (int i 2; i arr.length; i) {//遍历各组中所有的元素共5组每组有2个元素步长5for (int j i - 2; j 0; j - 2) {//如果当前元素大于加上步长后的那个元素说明交换if (arr[j] arr[j 2]) {temp arr[j];arr[j] arr[j 2];arr[j 2] temp;}}}System.out.println(希尔排序2轮后 Arrays.toString(arr));//希尔排序的第3轮排序//因为第3轮排序是将10个数据分成了2 /2 1组for (int i 1; i arr.length; i) {//遍历各组中所有的元素共5组每组有2个元素步长5for (int j i - 1; j 0; j - 1) {//如果当前元素大于加上步长后的那个元素说明交换if (arr[j] arr[j 1]) {temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}System.out.println(希尔排序3轮后 Arrays.toString(arr));}}
希尔排序-交换法(代码)
import java.text.SimpleDateFormat;
import java.util.Date;/*** 希尔排序(交换法)*/
public class ShellSort {public static void main(String[] args) {int[] 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) {for (int i gap; i arr.length; i) {//遍历各组中所有的元素共gap组每组有2个元素步长gapfor (int j i - gap; j 0; j - gap) {//如果当前元素大于加上步长后的那个元素说明交换if (arr[j] arr[j gap]) {temp arr[j];arr[j] arr[j gap];arr[j gap] temp;}}}System.out.println(希尔排序 (count) 轮后 Arrays.toString(arr));}}}
希尔排序-交换法(测试效率代码)
import java.text.SimpleDateFormat;
import java.util.Date;/*** 希尔排序(交换法)*/
public class ShellSort {public static void main(String[] args) {//测试一希尔排序(交换法) 给80000个数据 测试int arr[] new int[80000];for (int i 0, size arr.length; i size; i) {arr[i] (int) (Math.random() * 80000);//生成一个【080000)数}long startTime System.currentTimeMillis();shellSort(arr);long endTime System.currentTimeMillis();SimpleDateFormat dateFormat new SimpleDateFormat(yyyy-MM-dd HH:mm:ss);String start dateFormat.format(new Date(startTime));String end dateFormat.format(new Date(endTime));System.out.println(排序前时间 start);// 2023-08-20 20:53:19System.out.println(排序后时间 end);// 2023-08-20 20:53:25}//希尔排序(交换法)//思路算法》代码public static void shellSort(int[] arr) {int temp 0;int count 0;//根据前面的逐步分析使用循环处理for (int gap arr.length / 2; gap 0; gap / 2) {for (int i gap; i arr.length; i) {//遍历各组中所有的元素共gap组每组有2个元素步长gapfor (int j i - gap; j 0; j - gap) {//如果当前元素大于加上步长后的那个元素说明交换if (arr[j] arr[j gap]) {temp arr[j];arr[j] arr[j gap];arr[j gap] temp;}}}}}}
移动法
import java.text.SimpleDateFormat;
import java.util.Date;/*** 希尔排序(移位法)*/
public class ShellSort2 {public static void main(String[] args) {//测试一希尔排序(移位法) 给80000个数据 测试int arr[] new int[80000];for (int i 0, size arr.length; i size; i) {arr[i] (int) (Math.random() * 80000);//生成一个【080000)数}long startTime System.currentTimeMillis();shellSort(arr);long endTime System.currentTimeMillis();SimpleDateFormat dateFormat new SimpleDateFormat(yyyy-MM-dd HH:mm:ss);String start dateFormat.format(new Date(startTime));String end dateFormat.format(new Date(endTime));System.out.println(排序前时间 start);// 2023-08-20 21:03:10System.out.println(排序后时间 end);// 2023-08-20 21:03:10}//希尔排序(移位法)public static void shellSort(int[] arr) {int count 0;//增量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]) {//移动arr[j] arr[j - gap];j - gap;}}//当退出while后就给temp找到插入的位置arr[j] temp;}}}}
