这个世界需要秩序——认识排序算法（一）

今天我们来介绍几种常见的排序算法。

现在我们手上有一些杂乱的数据，看看这些排序算法是如何工作的。

选择排序

一句话来概括选择排序算法：从需要排序的数中选出最小的那一个，把它与最左边的数字交换。然后对剩下的数据重复这一步骤即可。在寻找最小值的时候，用的是线性查找。

我们来看如何对上面例子中的数进行排序。

先找到最小值1，然后将它与最左边的3交换。

此时1已经排序完成，找到剩余数的最小值2，将它与左边未排序的第一个值3进行交换

此时1、2都已完成排序。重复上面的步骤，直至排序完成。

我们来看看算法完成所需要的步骤。考虑最极端的情况，第一轮寻找最小值需要n-1步；第二轮需要n-2步；因此一共需要(n-1)+(n-2)+···+2+1=n(n-1)/2=(n^2-n)/2个步骤。

我们的大O表示法仅考虑最高次项，而且忽略常数。所以选择排序的时间复杂度（大O表示法）记为O(n^2)。

冒泡排序

一句话来解释冒泡排序：将数列最右边的数a与左边相邻的数b进行比较，如果a<b，则交换a、b的位置。当最小的数移到最左边时，视为一轮结束。然后在剩下的几轮中重复上面的步骤，直至所有的数据排序完成。

还是使用上面的例子：

找到右边的数字6，与左边相邻的数字7进行比较，6<7，因此交换二者的位置。

然后再将6与其左边的2进行比较，6>2，无需交换二者的位置。接下来，从2开始，将它与左边的位置比较。重复上面的步骤，直至最小值1到达最左边：

此时最小值1到达最左边，第一轮比较就结束了。然后，再从数列的末尾开始，依次与左边进行比较。在几轮过后，最终完成排序。

在冒泡排序中，我们还是考虑最极端的情况。那么第一轮需要n-1步，第二轮需要n-2步，总共需要(n-1)+(n-2)+···+2+1=n(n-1)/2=(n^2-n)/2步，跟选择排序所需的步骤相同。因此，冒泡排序的时间复杂度也可以记为O(n^2)。

插入排序

冒泡排序是从右边开始进行比较，而插入排序是从左边开始比较。插入排序将数列左边第2个数字b与左边第1个数字a比较，如果b<a，则交换a、b的位置。然后从第3个数字开始，重复上面的步骤，直到排序完成。

还是上面的例子：

这里我们假设第一个数字已经排序完成，然后从第二个数字1开始，与左边的3进行比较，1<3，因此交换1和3的位置。

然后看剩余的数字，第3位是9，与左边相邻的数字3进行比较，9>3，因此保留现有位置。重复上述步骤，直至数列按从小到大的顺序完成排列。

回顾整个插入排序算法，我们还是考虑最极端的情况。如果右边的数字比左边的数字都要小，那么它就要一直移动到最左边。因此，第n轮最多需要n-1次比较。那么插入排序的时间复杂度跟之前我们介绍的都一样，都是O(n^2)。

排序算法还有很多，下一篇我们再继续介绍。