排序算法(一)

通过前面的知识,我们已经知道,有序的数据在查找时有极大的性能提升。很多查找都基于有序数据,但并不是所有的结构都能像二叉排序树一样,在插入数据时就已经排好序,很多时候往往是无序的数据,需要我们使用时再进行排序,这就意味着我们需要寻找高效率的排序算法。接下来,我们对当下使用较为普遍的几个算法逐一进行分析。这里推荐一个可以查看算法运行动态过程的网站,加深对算法原理的理解,地址是https://www.cs.usfca.edu/~galles/visualization/Algorithms.html。

基础知识

排序定义

假设含有n个记录的序列为,其相应的关键字分别为,需确定1, 2, …, n的一种排列p1, p2, …, pn,使其相应的关键字满足kp1≤kp2≤…≤kpn(非递减或非递增) 关系,即使得序列成为一个按关键字有序的序列 , 这样的操作就称为排序。

稳定性

假设ki=kj( 1≤i≤n, 1≤j≤ n, i≠j ) ,且在排序前的序列中 ri领先于 rj(即i

简单来说,就是对于原数据中相等的数据,排序前后如果相对位置没有改变,就是稳定的。

内排序与外排序

内排序是在排序整个过程中,待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多,不能同时放置在内存,整个排序过程需要在内外存之间多次交换数据才能进行。本文先介绍内排序算法,外排序以后再来分析。

冒泡排序

冒泡排序(Bubble Sort)是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

冒泡排序可能是我们最熟悉的排序算法了,它的核心在于两两交换,代码代码:

它的最坏时间复杂度是1+2+…+(n-1) = n(n-1)/2,也就是O(n2),这个复杂度相对还是比较高的,所以只适合小量数据排序。因为冒泡排序每次遍历后,最后的数据一定是有序的,所以当初始数据部分有序时,还可以对它进行优化。比如数组为,当第一次遍历后,数组就是有序的,这时后续的循环遍历都是没有用的,优化后的算法如下:

使用一个flag标记是否有数据交换,冒泡排序如果没有数据交换,则意味着后边的数据一定是有序的,这样一来可以有效地提高冒泡排序的性能。但总体而言,冒泡排序还是不适合大数据量、数据比较乱的情况。

简单选择排序

选择排序的思想是每一趟从待排序的记录中选出最小的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕。简单选择排序就基于此思想,除此之外还有树型选择排序和堆排序也是基于此思想。

简单选择排序法就是通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第 i (0≤i≤n)个记录交换。

它的实现如下:

总体来看,简单排序算法的最坏时间复杂度也是O(n2),但是它交换数据的次数明显比冒泡排序要少很多,所以性能也比冒泡排序略优。

直接插入排序

直接插入排序和我们排序扑克牌的道理一致,就是把新的一张牌插入到已经排好序的牌中,它的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。它的代码实现如下:

它的最坏时间复杂度依然是O(n2)。

我们介绍了三种最简单,最容易理解的算法,但是它们的效率也确实较低。在数据量小的时候影响不大,然而现实是我们更多地要对大量数据进行排序。在排序算法(二)中介绍的几种算法属于改进算法,它们的效率都较为高一些,也是使用最多的算法。

更多文章正在火速连载中,感谢您的关注!

扫描一下二维码就可以关注哦

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181031G0AX5A00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券