您好、欢迎来到现金彩票网!
当前位置:秒速牛牛投注 > 桶链算法 >

排序算法总结及Java实现

发布时间:2019-06-07 07:54 来源:未知 编辑:admin

  排序大的分类可以分为两种,内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。主要需要理解的都是内排序算法:

  稳定性:就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。即如果Ai== Aj,Ai原来在Aj位置前,排序后Ai仍然是在Aj位置前。

  稳定:冒泡排序、直接插入排序、二分法插入排序,归并排序和基数排序都是稳定的排序算法。

  快速排序是目前基于比较的内部排序中最好的方法, 其次是归并和希尔,堆排序在数据量很大时效果明显。当数据是随机分布时快速排序的平均时间最短。

  解释:n: 数据规模;k:“桶”的个数;In-place: 占用常数内存,不占用额外内存;Out-place: 占用额外内存。

  (2)数据无序时,对稳定性不作要求宜用简单选择排序,对稳定性有要求宜用插入或冒泡

  (1)完全可以用内存空间,序列杂乱无序,对稳定性没有要求,快速排序,此时要付出log(N)的额外空间。

  基本思想:依次遍历元素,在已排序的序列中找到合适的位置将当前遍历的元素插入,直到所有元素都已排序。

  最好的情况下:正序有序(从小到大),这样只需要比较n次,不需要移动。因此时间复杂度为O(n)

  最坏的情况下:逆序有序,这样每一个元素就需要比较n次,共有n个元素,因此实际复杂度为O(n2)

  稳定性:稳定。由算法思想易知,反向遍历已排序元素,若已排序元素小于等于当前元素,则将当前元素插入该已排序元素后的位置,因此相对顺序不变,插入排序是稳定的。

  二分法查找基本思想:对于一个有序的待查序列,定义三个指针low、high、mid,分别指向待查序列所在范围的下界、上界及区间中间位置,即mid=(low+high)/2。对比待查数据与mid所指的值,若相等则查找成功并返回mid,若待查数小于mid值,则令high=mid-1,否则令low=mid+1,得到新的需要查找的区间,如此循环直到找出或找不到。如下示例:

  二分排序:从第二个数开始往后遍历,用二分法查找合适的插入位置。当lowhigh条件不成立时说明找到合适位置,将low及之后元素后移

  时间复杂度:二分插入排序的比较次数与待排序记录的初始状态无关,仅依赖于记录的个数。当n较大时,比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数。算法的移动次数与直接插入排序算法的相同,最坏的情况为n2/2,最好的情况为n,平均移动次数为O(n2)。

  基本思想:希尔排序也是一种插入排序方法,实际上是一种分组插入方法。先取定一个小于n的整数d1作为第一个增量,这样可以把表的全部记录分成d1个组:所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序;然后,取第二个增量d2(<d1),重复上述的分组和排序,直至所取的增量dt=1(dtdt-1d2d1),即所有记录放在同一组中进行直接插入排序为止。

  希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。

  最好情况:由于希尔排序的好坏和步长d的选择(di到di+1的选择策略)有很多关系,因此,目前还没有得出最好的步长如何选择(现在有些比较好的选择了,但不确定是否是最好的)。所以,不知道最好的情况下的算法时间复杂度。

  稳定性:由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同趟的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。(有个猜测,方便记忆:一般来说,若存在不相邻元素间交换,则很可能是不稳定的排序。)

  解释:就是将增量(d)为1的直接插入排序,增量改为从d到1的递减。不再是相邻元素间的对比,而是以d为间隔的对比插入。

  基本思想:通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。

  稳定性:稳定。排序过程中只交换相邻两个元素的位置。因此,当两个数相等时,是没必要交换两个数的位置的。所以相对位置并没有改变,冒泡排序算法是稳定的!

  冒泡排序改进1:设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。因为上一轮冒泡的最后一次交换说明该交换的元素是其位置以前的所有元素中最大的(毕竟是自己冒上来的)。下一趟找最大元素的冒泡从该位置开始即可,不必从头开始两两交换

  基本思想:由冒泡排序改进而来的。在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位)。

  核心思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

  最好的情况:因为每次都将序列分为两个部分(一般二分都复杂度都和logN相关),故为 O(N*logN)

  最坏的情况:基本有序时,退化为冒泡排序,几乎要比较N*N次,故为O(N*N)

  稳定性:不稳定。由于每次都需要和中轴元素(不一定相邻)交换,因此原来的顺序就可能被打乱。快速排序是不稳定的。

  快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

  2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

  3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

  基本思想:首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。具体做法是:选择最小的元素与未排序部分的首部交换,使得序列的前面为有序。

  最好情况:交换0次,但是每次都要找到最小的元素,因此大约必须遍历N*N次,因此为O(N*N)。减少了交换次数!

  稳定性:不稳定。由于每次都是选取未排序序列A中的最小元素x与A中的第一个元素交换,因此跨距离了,很可能破坏了元素间的相对位置,因此选择排序是不稳定的!

  算法描述:n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。

  2.第i趟排序(i=1,2,3...n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;

  基本思想:堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或者最小)的记录。也就是说,以最小堆为例,根节点为最小元素,较大的节点偏向于分布在堆底附近。

  时间复杂度:O(nlogn)。最坏情况下,接近于最差情况下:O(N*logN),因此它是一种效果不错的排序算法。

  最好情况:一趟归并需要n次,总共需要logN次,因此为O(N*logN)

  稳定性:归并排序最大的特色就是它是一种稳定的排序算法。归并过程中是不会改变元素的相对位置的。

  基本思想:它是一种非比较排序。它是根据位的高低进行排序的,也就是先按个位排序,然后依据十位排序以此类推。示例如下:

  时间复杂度:分配需要O(n),收集为O(r),其中r为分配后链表的个数,以r=10为例,则有0~9这样10个链表来将原来的序列分类。而d,也就是位数(如最大的数是1234,位数是4,则d=4),即分配-收集的趟数。因此时间复杂度为O(d*(n+r))

  适用情况:如果有一个序列,知道数的范围(比如1~1000),用快速排序或者堆排序,需要O(N*logN),但是如果采用基数排序,则可以达到O(4*(n+10))=O(n)的时间复杂度。算是这种情况下排序最快的!!

http://duchtech.com/tongliansuanfa/137.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有