李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构和算法学习--希尔排序
Leefs
2020-02-02 PM
1317℃
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://lilinchao.com/archives/536.html
上一篇
数据结构和算法学习--插入排序
下一篇
数据结构和算法学习--归并排序
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
43
标签云
Elastisearch
栈
ClickHouse
JavaWeb
Flink
数据结构和算法
NIO
工具
Java
Stream流
锁
Shiro
算法
nginx
VUE
Linux
机器学习
Elasticsearch
CentOS
二叉树
持有对象
JavaWEB项目搭建
Java阻塞队列
Spring
JavaSE
Netty
Docker
队列
字符串
Quartz
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞