深入浅出排序算法（上）

前言

排序指的是按照某种顺序（升序或降序）排列序列元素的一种算法，在实际工作中用得非常多，也是面试中经常被问到的知识点。本文将为大家介绍常见的几种排序算法的思想，并用Java语言进行实现，在文末附有源码地址，有需要的朋友可以自行下载。

冒泡排序

冒泡排序是最简单的一种排序算法了。其基本思想是迭代地对输入序列中相邻的2个元素进行两两比较，如果比较的结果与排序的次序相反则对它们进行交换，否则不做处理。因为经过每一次迭代之后，都能将该次迭代中的最小或最大元素移动到序列顶端，就像“冒泡”一样一个个地冒出来，所以才称此排序算法为“冒泡排序”。接下里我们用Java语言实现“冒泡排序”，为了简单起见，我们统一组数组进行升序排序，下文的例子也是如此。

代码比较简单，就不做解释了。我们来分析下冒泡排序的时间复杂度。第一次迭代，即“冒出”最大的那个元素的过程，总共需要比较(n-1)次，“冒出”第二大的那个元素需要比较(n-2)次，以此类推，排序完所有元素总共需要比较的次数是(n-1)+(n-2)+(n-3)+……+2+1=O(n^2)，所以冒泡排序的时间复杂度是O(n^2)。此外，冒泡排序是稳定排序，因为其在排序的过程中不会改变原来相等的元素的相对位置。

选择排序

选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。因为每次都从未排序序列中挑选出最小（大）元素，所以才被称为“选择排序”。选择排序与冒泡排序的区别是：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。接下来看代码实现：

简单解释一下代码，在每次循环中，我们都记录下本次循环的最小元素的下标，然后再把该次循环中的最小元素与已排序序列之后的那个元素进行交换，以此类推，从而使得整个序列有序。接下来说一下选择排序的时间复杂度，找出最小的那个元素的过程需要比较(n-1)次，找出第二小的那个元素的时候需要比较(n-2)次，以此类推，排序完整个序列总共需要比较的次数是(n-1)+(n-2)+(n-3)+……+2+1=O(n^2)，所以选择排序的时间复杂度是O(n^2)。需要注意的是，选择排序是不稳定的排序，因为其在交换的过程中有可能会改变原先相等的元素的性对位置。

插入排序

插入排序的思想跟玩扑克牌类似。在每次重新发牌的时候，大部分人会对手中的牌进行排序，每拿到一张新的牌，就将它插入到手中已有的排好序的牌中的正确位置，插入排序排序的过程也与其类似，每次我们都把一个未排序的元素插入到已经排好序的序列中的正确位置，依次迭代下去，直到整个序列都有序。接下来看看Java语言实现：

简单解释一下代码，每一次我们都将一个未排序的元素与已排序序列的每个元素从小到达进行比较，如果有遇到违反排序规则的，就将违反排序规则的元素后面的元素都往后移动，然后将新元素插入到该元素的位置，从而形成一个新的有序序列，依此迭代下去，直至整个序列有序。接下来讲一下插入排序的时间复杂度，最坏的情况下，插入第一个元素需要移动0次，插入第二个元素需要移动1次，以此类推，插入最后一个元素需要移动(n-1)次，所以总的移动次数是(n-1)+(n-2)+(n-3)+……+2+1=O(n^2)，故插入排序的时间复杂度是O(n^2)。插入排序是稳定排序，因其在插入的过程中不会改变原先相等的元素的相对位置。

由于篇幅所限，今天就先介绍这几种比较简单的算法。