李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构和算法学习--希尔排序
Leefs
2020-02-02 PM
1381℃
0条
# 数据结构和算法学习--希尔排序 ### 一、简单插入排序存在的问题 我们看简单的插入排序可能存在的问题. 数组 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} **结论**: 当需要插入的数是较小的数时,后移的次数明显增多,对效率有影响. ### 二、希尔排序法介绍 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种**插入排序**,它是简单插入排序经过改进之后的一个**更高效的版本**,也称为缩小增量排序。 ### 三、希尔排序法基本思想 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量的逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止 ### 四、希尔排序法的示意图 ![17.希尔排序算法01.png][1] ### 五、希尔排序法应用实例 有一群小牛,考试成绩分别是{8,9,1,7,2,3,5,4,6,0}请从小到大排序,请分别使用 (1)希尔排序时,对有序序列在插入时采用交换法,并测试排序速度。 (2)希尔排序时,对有序序列在插入时采用移动法,并测试排序速度。 **代码实现** ```java public class ShellSort { public static void main(String[] args) { int[] arr = {8,9,1,7,2,3,5,4,6,0}; // shellSort(arr); shellSort2(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
=0;j-=gap){ //如果当前元素大于加上步长后的那个元素,说明交换 if(arr[j]>arr[j+gap]){ temp=arr[j]; arr[j]=arr[j+gap]; arr[j+gap]=temp; } } } } System.out.println(Arrays.toString(arr)); } //对交换式的希尔排序进行优化->移位法 public static void shellSort2(int[] arr){ //增量gap,并逐步的缩小增量 for(int gap=arr.length/2;gap>0;gap/=2){ //从第gap个元素,逐个对其所在的组进行直接插入排序 for(int i=gap;i
=0 && temp < arr[j-gap]){ //移动 arr[j]=arr[j-gap]; j-=gap; } //当退出while后,就给temp找到插入的位置 arr[j]=temp; } } } System.out.println(Arrays.toString(arr)); } } ``` **全部代码** ```java public class BubbleSort2{ public static void main(String[] args) { // int arr[] = {3, 9, -1, 10, 20}; // // System.out.println("排序前"); // System.out.println(Arrays.toString(arr)); //为了容量理解,我们把冒泡排序的演变过程,给大家展示 //测试一下冒泡排序的速度O(n^2), 给80000个数据,测试 //创建要给80000个的随机的数组 int[] arr = new int[80000]; for(int i =0; i < 80000;i++) { arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数 } Date data1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(data1); System.out.println("排序前的时间是=" + date1Str); //测试冒泡排序 bubbleSort(arr); Date data2 = new Date(); String date2Str = simpleDateFormat.format(data2); System.out.println("排序后的时间是=" + date2Str); //System.out.println("排序后"); //System.out.println(Arrays.toString(arr)); /* // 第二趟排序,就是将第二大的数排在倒数第二位 for (int j = 0; j < arr.length - 1 - 1 ; j++) { // 如果前面的数比后面的数大,则交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } System.out.println("第二趟排序后的数组"); System.out.println(Arrays.toString(arr)); // 第三趟排序,就是将第三大的数排在倒数第三位 for (int j = 0; j < arr.length - 1 - 2; j++) { // 如果前面的数比后面的数大,则交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } System.out.println("第三趟排序后的数组"); System.out.println(Arrays.toString(arr)); // 第四趟排序,就是将第4大的数排在倒数第4位 for (int j = 0; j < arr.length - 1 - 3; j++) { // 如果前面的数比后面的数大,则交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } System.out.println("第四趟排序后的数组"); System.out.println(Arrays.toString(arr)); */ } // 将前面额冒泡排序算法,封装成一个方法 public static void bubbleSort(int[] arr) { // 冒泡排序 的时间复杂度 O(n^2), 自己写出 int temp = 0; // 临时变量 boolean flag = false; // 标识变量,表示是否进行过交换 for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { // 如果前面的数比后面的数大,则交换 if (arr[j] > arr[j + 1]) { flag = true; temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } //System.out.println("第" + (i + 1) + "趟排序后的数组"); //System.out.println(Arrays.toString(arr)); if (!flag) { // 在一趟排序中,一次交换都没有发生过 break; } else { flag = false; // 重置flag!!!, 进行下次判断 } } } } ``` [1]: https://lilinchao.com/usr/uploads/2020/02/3550032508.png
标签:
数据结构和算法
,
排序
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://www.lilinchao.com/archives/536.html
上一篇
数据结构和算法学习--插入排序
下一篇
数据结构和算法学习--归并排序
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
47
标签云
微服务
RSA加解密
Jenkins
Redis
JavaScript
Sentinel
JavaSE
线程池
SpringCloudAlibaba
Linux
链表
排序
正则表达式
MySQL
SpringBoot
数学
国产数据库改造
Golang基础
Quartz
BurpSuite
MyBatis
MyBatis-Plus
GET和POST
Python
容器深入研究
Typora
二叉树
并发线程
Nacos
Tomcat
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞