「排序」插入类排序—(折半)插入排序、希尔排序

「排序」插入类排序—(折半)插入排序、希尔排序

首页休闲益智人群排序更新时间:2024-08-03

前言

在数据结构和算法中,排序是非常重要的一环,并且排序也是渗透编程的方方面面

在这里插入图片描述


你或许在写一个sql的order by按照某组进行排序,又或者你在刷一道题时候、常常遇到贪心 自定义排序求解的思路题,或者变态的面试官让你手写快排,又或者是app的姓氏升降序列 - - -

然而在实际的排序算法的实现上,方式是众多的,不同算法对不同的特征数据的效率也是不同的,并且不同算法的时间复杂度、空间复杂度也不同

对于排序,一般认为有八大排序(也有九大)。但是在分配的大类中,我们常常分为 基于插入排序(插入排序、希尔排序);基于交换的排序(冒泡排序、快速排序);基于选择的排序(简单选择排序、堆排序),归并排序和基数排序

插入排序


插入排序在所有排序算法中的思想算得上是最简单的了。和我们上学时候 从前往后、按高矮顺序排序。那么,一堆高低无序的人群中,从第一个开始,如果前面有比自己高的,就直接插入到合适的位置。一直到队伍的最后一个完成插入整个队列才能满足有序。

虽然在思想上是很简单的,或许你认为它的实现、次数也很简单,每个同学插入到合适的位置就好了。但事实你这么想错了。你实质一眼看到确切的位置在脑海中已经默默经过pass、pass、pass。。。计算机每次只能进行一次计算,所以每个他要确定他要插入到那,他必须一个一个往前比较。所以这个时间复杂度是O(n2)的。如果数据很大的话其实效率还是很低的。

插入排序的具体步骤:


在具体实现上有一下的需要注意:

折半插入排序

折半插入排序和插入排序有什么关联
首先,折半插入排序的本质依然是插入排序,仅仅是对插入排序进行了部分优化。而优化的部分就是向前查找比较的部分。其实它就是将查找从暴力枚举一一遍历变为二分查找


对于二分查找,这里不做详细介绍,我将在另一篇博文中再做详细介绍,因为没进行一次插入,前面的序列都是有序的。如果序列很长的话,那么一个个查找比较可能会占用过多的次数。而我们从序列中间试探二分夹逼的话可以用log级别完成查找。序列越长那么查找减少的次数就越多。

当然很遗憾的是,折半插入虽然可以降低查找次数,但是无法改变整个算法的时间复杂度(数组实现)。因为在每个元素的插入过程中,虽然查找可以降到log'n,但是在顺序表的向前移动交换依然还是得一个一个移动啊。折半插入可以理解为对于每个位置的平均时间复杂度从O(N)查找 O(N)交换移动变成O(logN)查找 O(n)交换移动。所以,整个时间复杂度依然是O(n2).但是,别太小看那点优化,在数据大、链式存储的情况下其实还是节省很大时间的!

希尔排序

因为上述的基于排序的算法中大部分都是适合于数据量不大、或者有序的情况才能达到较好的效果。无数牛逼的人物在不断想方设法的优化和解决这个难题。终于,有个叫希尔的牛逼人物终于研究出来一种排序算法——希尔排序。考虑到了数据量和有序性两个方面纬度来设计算法。同时,希尔排序是一组插入排序的组合。百科如下定义:

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法.
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

在这里插入图片描述

首先插入排序在两个情况下效率还可以。

有序序列,因为如果有序的话每个元素很容易找到前面一直比自己大的几个或0个元素,这种情况时间复杂度比现行级别稍微高那么一丢丢。元素较少。你强任你强,很少的元素再怎么平方在计算机面前也是小菜。


而希尔排序刚好巧妙的运用,分割。利用了上面的优点。对于一个长串,希尔首先将序列分割(非线性分割)而是按照某个数模(取余这个类似报数1、2、3、4. 1、2、3、4)这样形式上在一组的分割先降低长度分别进行插入排序,这样很小的数在后面可以通过较少的次数移动到相对考前的位置。然后慢慢合并变长,再稍稍移动。。。。。因为每次这样小插入都会使得序列变得更加有序,稍微有序序列执行插入成本并不高。所以这样能够在合并到最终的时候基本小的在前,大的在后。这样希尔排序下来一般还是能够减少很多时间的。

前面的分组取余相当于按照这个规则预处理。到最后一次就变得很有大小规则了(至少奇偶数分别有序),这样整个插入排序的复杂度大大降低,很少出现需要移动很大幅度的数字。

虽然希尔排序看起来多了那么几次排序。但是在数据较长的串面前多几次比起平方指数级别还是弟弟的。虽然希尔排序的证明是个问题,并且分割的取值也并没有理论证明最好。但是一般从n/2一直到1.马克思曾说:实践是检验真理的唯一标准。实践检验它好它就是好!

实现代码

package 八大排序; import java.util.Arrays; public class 直接插入 { public static void main(String[] args) { // TODO Auto-generated method stub int a[]= {21,25,8,7,45,2,8,18,9,88,3}; int b[]=new int[10]; a=insertsort(a); System.out.println(Arrays.toString(a)); System.out.println(); b=shellsort(a); System.out.println(Arrays.toString(a)); } static int [] insertsort (int a[]) { int team=0; for(int i=1;i<a.length;i ) { System.out.println(Arrays.toString(a)); team=a[i]; for(int j=i-1;j>=0;j--) { if(a[j]>team) { a[j 1]=a[j]; a[j]=team; } else { break; } } } return a; } static int [] shellsort (int a[]) { int d=a.length; int team=0;//临时变量 for(;d>=1;d/=2) for(int i=d;i<a.length;i ) { System.out.println(Arrays.toString(a)); team=a[i]; for(int j=i-d;j>=0;j-=d) { if(a[j]>team) { a[j d]=a[j]; a[j]=team; } else { break; } } } return a; } }

输出结果:

[21, 25, 8, 7, 45, 2, 8, 18, 9, 88, 3]
[21, 25, 8, 7, 45, 2, 8, 18, 9, 88, 3]
[8, 21, 25, 7, 45, 2, 8, 18, 9, 88, 3]
[7, 8, 21, 25, 45, 2, 8, 18, 9, 88, 3]
[7, 8, 21, 25, 45, 2, 8, 18, 9, 88, 3]
[2, 7, 8, 21, 25, 45, 8, 18, 9, 88, 3]
[2, 7, 8, 8, 21, 25, 45, 18, 9, 88, 3]
[2, 7, 8, 8, 18, 21, 25, 45, 9, 88, 3]
[2, 7, 8, 8, 9, 18, 21, 25, 45, 88, 3]
[2, 7, 8, 8, 9, 18, 21, 25, 45, 88, 3]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
空格
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]
[2, 3, 7, 8, 8, 9, 18, 21, 25, 45, 88]

最后,如果感觉可以的话欢迎点赞呗!后面持续分享

欢迎关注笔者公众号:bigsai

头条号:一直码农一直爽

欢迎交流!IT圈不嫌多一个朋友,笔者也希望能成为你的朋友,共同学习,共同进步

查看全文
大家还看了
也许喜欢
更多游戏

Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved