请选择 进入手机版 | 继续访问电脑版
开启左侧

八大排序算法(二)

[复制链接]
lhjmy 发表于 2020-5-18 15:00:30 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
本帖最后由 lhjmy 于 2020-5-18 15:04 编辑

默认标题_公众号封面首图_2019-11-09-0.png


我们继续来探讨八大排序算法,首先来回顾一下本文章节目录:

QQ图片20200518145327.png

今天我们讲的是第3,4章节部分。



插入类排序法

插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。
插入排序一般意义上有两种:直接插入排序和希尔排序,下面分别介绍。


插入排序— 直接插入排序(Straight InsertionSort)
基本思想:
最基本的操作是将第i个记录插入到前面i-1个以排好序列的记录中。具体过程是:将第i个记录的关键字j依次与其前面的i-1个已经排好序列的记录进行比较。将所有大于j的记录依次向后移动一个位置,直到遇到一个关键字小于或等于j的记录,此时它后面的位置必定为空,则将j插入。
1.jpg

2.png
算法分析:
如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)^2次。插入排序的赋值操作是比较操作的次数加上(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用,在STL的sort算法和stdlib的qsort算法中,都将插入排序作为快速排序的补充,用于少量元素的排序(通常为8个或以下)。
时间复杂度:          O()
最优时间复杂度:   O()
平均时间复杂度:   O()
空间复杂度:         O(n)total  O(1)auxiliary(辅助)



插入排序— 希尔排序(Shell Sort)
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。

基本思想:
     ① 先取一个正整数d1(d1<n)作为第一个增量,将全部n个记录分成d1组,把所有相隔d1的记录放在一组中,即对于每个k(k=1, 2,  … d1),R[k], R[d1+k], R[2d1+k] , …分在同一组中,在各组内进行直接插入排序。这样一次分组和排序过程称为一趟希尔排序;
② 取新的增量d2<d1,重复①的分组和排序操作;直至所取的增量di=1为止,即所有记录放进一个组中排序为止。

  该方法实质上是一种分组插入方法。
举例:
假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 4527 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:
13 14 94 33 8225 59 94 65 2345 27 73 25 3910
然后我们对每列进行排序:
10 14 73 25 2313 27 94 33 3925 59 94 65 8245
将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:
10 14 7325 23 1327 94 3339 25 5994 65 8245排序之后变为:10 14 1325 23 3327 25 5939 65 7345 94 8294
最后以1步长进行排序(此时就是简单的插入排序了)。
3.png



算法分析
希尔排序的时间性能优于直接插入排序的原因:
当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
当n值较小时,n和n^2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n^2)差别不大。
在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。
因此,希尔排序在效率上较直接插人排序有较大的改进。
希尔排序是不稳定的。

时间复杂度
Shell排序算法时间复杂度分析比较复杂,实际所需的时间取决于各次排序时增量的个数和增量的取值。
研究证明,若增量的取值比较合理,Shell排序算法的时间复杂度约为O(n log2 n)。由于Shell排序算法是按增量分组进行的排序,所以Shell排序算法是一种不稳定的排序算法。

时间复杂度:           根据步长序列的不同而不同。已知最好的:O(n log2 n){\displaystyle O(n\log ^{2}n)}
最优时间复杂度:   O(n)
平均时间复杂度:   根据步长序列的不同而不同。
空间复杂度:           O(n)




选择类排序法

选择排序(Selection Sort)的基本思想是:每次从当前待排序的记录中选取关键字最小的记录表,然后与待排序的记录序列中的第一个记录进行交换,直到整个记录序列有序为止。

选择排序— 简单选择排序(Simple Selection Sort)

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。选择排序是不稳定的排序方法(比如序列[5, 5, 3]第一次就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)。
4.jpg

5.png

算法分析:
整个算法是二重循环:外循环控制排序的趟数,对n个记录进行排序的趟数为n-1趟;内循环控制每一趟的排序。
最坏情况下,即待排序记录初始状态是按第一条记录最大,之后的记录从小到大顺序排列,则需要移动记录的次数最多为3(n-1)。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时,需进行n-1次比较;当i=2时,需进行n-2次比较;依次类推,共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2,即进行比较操作的时间复杂度为O(n^2),进行移动操作的时间复杂度为O(n)。
简单选择排序是不稳定排序。

时间复杂度:           O()
最优时间复杂度:   O()
平均时间复杂度:   O()
空间复杂度:           O(n)total  O(1)auxiliary(辅助)



选择排序— 堆排序(Heap Sort)
堆的性质
①  堆是一棵采用顺序存储结构的完全二叉树, k1是根结点;
②  堆的根结点是关键字序列中的最小(或最大)值,分别称为小(或大)根堆;
③  从根结点到每一叶子结点路径上的元素组成的序列都是按元素值(或关键字值)非递减(或非递增)的;
①  堆中的任一子树也是堆。
利用堆顶记录的关键字值最小(或最大)的性质,从当前待排序的记录中依次选取关键字最小(或最大)的记录,就可以实现对数据记录的排序,这种排序方法称为堆排序。

堆排序思想:
①  对一组待排序的记录,按堆的定义建立堆;
②  将堆顶记录和最后一个记录交换位置,则前n-1个记录是无序的,而最后一个记录是有序的;
③  堆顶记录被交换后,前n-1个记录不再是堆,需将前n-1个待排序记录重新组织成为一个堆,然后将堆顶记录和倒数第二个记录交换位置,即将整个序列中次小关键字值的记录调整(排除)出无序区;
④  重复上述步骤,直到全部记录排好序为止。
结论:排序过程中,若采用小根堆,排序后得到的是非递减序列;若采用大根堆,排序后得到的是非递增序列。
6.jpg

7.png

8.png
算法分析:
堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。
平均性能:O(N*logN)。
其他性能
由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序,辅助空间为O(1).
它是不稳定的排序方法。(排序的稳定性是指如果在排序的序列中,存在前后相同的两个元素的话,排序前和排序后他们的相对位置不发生变化)

时间复杂度:           O(nlogn)
最优时间复杂度:   O(nlogn)
平均时间复杂度:   O(nlogn)
空间复杂度:           O(n)total  O(1)auxiliary(辅助)


-完-


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题
阅读排行 更多
广告位
0351-8210788
周一至周日 9:00-18:00
意见反馈:mind@unigress.com
关注我们

扫一扫关注我们

Powered by Discuz! X3.4 Licensed  © 2001-2013 Comsenz Inc.( 晋ICP备12005011 )