排序算法（一）

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

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

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

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