计算机二级公基知识8-排序

排序算法。本部分内容对OIer同样适用。

这应该是公基知识中数据结构与算法部分的最后一篇文章了。


排序也是数据处理中的一个重要的操作。排序的过程其实就是一个整理的过程。它将一个无序序列按照一定的原则整理为有序的序列。

可以对很多不同的数据结构进行排序,这里主要说对线性表的排序。

讲的可能会比较粗略,只介绍一下思路和复杂度。

交换类排序

这是一类排序方法,它的原理是借助数据元素之间的互相交换。

1.冒泡排序

冒排是最简单的一种交换类排序。它通过相邻元素之间的交换逐步将无序变成有序。这里讲改进后的冒泡排序。

基本过程如下。假设我们要升序排序。

从表头开始往后扫描线性表,在扫描过程中逐次比较相邻两个元素的大小,如果在两个相邻的元素之间,前边的元素大于后边的元素,则将它们互换位置。显然,在扫描过程中,不断地将两个相邻元素中较小的向前移动,最后会得到一个升序序列。此时,在数组最右边的元素一定是最大的元素。因为通过之前的移动,最大的元素会被一直交换到最右边。然后我们从倒数第二位开始从后往前扫,扫到两者较小的数就往前移动,同理,这一趟排序下来最小的元素就会被放在第一位。然后再从正数第二位开始从前往后扫……这样一直扫到左界与右界重合,就完成了排序。

如果线性表的长度位n,那么在最坏情况下,冒泡排序需要n/2遍的从前往后的扫描与n/2遍的从后往前的扫描,需要的比较次数为n(n-1)/2,展开,得到时间复杂度为O(n2)。

2.快速排序

冒泡排序在扫描过程中只对相邻的两个元素进行比较,因此,每次互换相邻两个元素只能消除一个逆序。实际上,通过一些改进,我们可以通过一次交换消除多个逆序。快速排序就是这样的。

它的基本思路如下:

从线性表中取一个元素,让该线性表中所有比它小的元素移动到它前面,所有比它大的元素移动到它的后面。实际上是一个分割的过程,以我们所取的元素为分界点,最后使得该元素之前的元素都比它小,之后的元素都比它大。与此同时,我们需要再对分割后的两个线性表再次使用这个操作,一直到所有的元素都排列好。可以看出,这也是一个递归的过程。

实际上,在选取元素的过程中,我们常选取中间元素。我们设置两个指针i和j,分别指向线性表中的开始位置和结束位置,然后反复操作下面两个步骤:

1.j逐渐减小,并且逐次比较线性表第j项与选取的元素的大小,直到找到一个这个第j项小于我们选取的元素。然后把这个元素与第i个元素互换。

2.i逐渐增大,并且逐次比较线性表第i项与选取的元素的大小,直到找到一个这个第i项大于我们选取的元素。然后把这个元素与第j个元素互换。

上述两个操作交替进行,直到i=j为止。

在快速排序过程中,随着对各个子表不断地递归地进行分割,划分出的表会越来越多,由于是递归进行,所以系统会使用栈来进行存储所有的表。在对某个表进行分割后,可以将分割出的后一个子表的第一个元素与最后一个元素的位置入栈。当分割出的子表为空时,可以从栈中退出一个子表进行分割。直到栈空为止。

快速排序的平均时间复杂度是O(nlogn),但是在最坏情况下会退化成O(n2)。

插入类排序法

1.插入排序

所谓插入排序,实际上是指将无序序列中的各个元素依次插入到已经有序的线性表中。类似于现实中的摸牌,在把牌摸到手里的同时会立即把它放在对应的位置那样。

不难得出,如果表中只有一个元素,那么它一定是有序的(这不是废话么)。假设目前有n-1个元素已经按顺序排好,我现在有第n个元素,我该怎么做?

想一下你摸牌后是怎么整理牌的。对线性表来说,要从第n-1个元素起,向左找,挨个比对,所有大于这第n个元素的元素都要后移一位。

在一次操作中,只能最多“消除一个逆序”。因此,它的时间复杂度与冒泡排序相同,是O(n2)。

2.希尔排序

希尔排序也属于插入类排序。但它相对普通的插入排序做了一些改进。

(NOIP2017考过希尔排序,但我用快排用习惯了,完全不知道这是什么鬼东西)

它的基本思想是将整个无序序列分割成若干的小子序列进行插入排序。既然用到了子序列,那么一定是要先分割出子序列。我们设一个改变量(增量)大小为h,那么每相隔h我们就划分一次,构成许多子序列。在各个子序列内直接进行插入排序。在排序过程中,要让这个h不断减小,最后当h减小到1时,进行一次插入排序,就可以了。

增量序列一般取h = n/2k(k = 1,2,……,[log2n]),其中n代表原无序序列长度。

一般的,初次取序列的一半为增量,以后每次减半,直到增量为1。在最坏情况下,它的比较次数为O(n3/2)。

选择类排序法

1.选择排序

扫描整个线性表,从中选出最小的元素,将它交换到表的最前面,然后再从线性表的第二个位置开始,从中选出最小的元素,将它交换到表的最前面……依此类推。直到剩下没排的表空为止。该排序算法并不难理解。它的时间复杂度也是O(n2)。

2.堆排序

先来说一下什么是堆。堆的基本定义是:一个具有n个元素的序列(n1,n2,……,nk),当且仅当满足:{ni ≥ n2i,ni ≥ n2i+1} 或者{ni ≤ n2i,ni ≤ n2i+1}时,称之为堆。当满足前者的条件时称之为大根堆,满足后者的条件时称之为小根堆。

可能细心的读者能发现,这个数据结构其实就是一个完全二叉树……拿大根堆举例来说,所有的非叶节点值都不小于其左子树或右子树的根节点值。

所谓堆排序,其实就是调整结点的问题。我们可以把一个无序序列看成一棵完全二叉树,这棵完全二叉树是无序的,我们要通过变换结点把它调整为一个堆,就完成了排序。 在调整建堆的过程中,总是将根节点的值与左、右子树的根节点值进行比较, 如果不满足条件,则将左右子树的根节点的值中的较大的那个与根节点进行交换。一直做到所有的子树都变成了堆,排序就完成了。

堆排序对于规模较小的线性表并不适合,但是如果线性表规模较大,它的优势就会变得比较明显。即使是最坏情况,它的时间复杂度也是很优秀的O(nlogn)。


-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:计算机二级公基知识8-排序

文章作者:Shawn Zhou

发布时间:2018年08月13日 - 20:08

最后更新:2018年12月09日 - 18:12

原始链接:http://yoursite.com/2018/08/13/国考计算机二级公共基础知识-Part-8/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。