排序算法（排序算法的应用场景）

[数据结构与算法系列]排序算法(一)

　　排序算法对大家来说肯定都不陌生吧，作为最基础且最重要的算法之一，经典排序算法在面试中常常占有很大的比重。可是排序算法实在是太多了(见下图)，有些名字你我可能名字都没听说过，比如鸡尾酒排序，侏儒排序，煎饼排序等。 所以在这个系列里我会讲解众多排序算法中最经典的部分，也是大家最熟悉的部分，包括冒泡排序、插入排序、选择排序、归并排序、计数排序、基数排序、桶排序、希尔排序、堆排序。希望能够帮助到有需要的朋友，同时也会利用一些手绘图来帮助大家更好地理解。

　　声明:在下面所有的算法讲解中，我们默认我们需要对待处理数组进行升序排序，即排序好的数组中，左边的元素要小于右边的元素。

　　在正式开始讲解各种各样的排序算法之前，我还希望大家思考一个问题。什么样的排序算法才是一个好的算法，各种各样的排序算法它们的应用场景又有什么不同？希望大家带着这些问题来和我一起学习排序算法。

　　# 1.算法分析

　　要想学好排序算法，我们不应该仅仅了解它的算法原理，然后背下代码就完事，我们还要学会如何分析和评价一个排序算法。那么对于一个排序算法来说，我们应该关注它的哪些方面呢？

　　分析一个算法的好坏，第一个当然就是应该分析该算法的时间复杂度。排序算法需要对一组数据进行排序，在实际的工程中，数据的规模可能是10个、100个，也可能是成千上万个。同时，对于要进行排序处理的数据，可能是接近有序的，也可能是完全无序的。因此，在分析其时间复杂度时，不仅要考虑平均情况下的时间复杂度，还要分析它在最好情况以及最坏情况下代码的执行效率。

　　对于一个常见的排序算法来说，执行过程中往往会涉及两个操作步骤，一个是进行元素的比较，二是对元素进行交换或者移动。所以在分析排序算法的时间复杂度时，也要注意算法实现过程中不同的元素比较和交换(或移动)的次数。

　　这里先引入一个新的概念，原地排序。原地排序就是指在排序过程中不必申请额外的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的排序算法。换句话说，原地排序不会产生多余的内存消耗。

　　对于一般的算法，我们一般只需要分析它的时间复杂度和空间复杂度，但是对于排序算法来说，我们还有一个非常重要的分析指标，稳定性。

　　稳定性是指，在需要进行排序操作的数据中，如果存在值相等的元素，在排序后，相等元素之间的排列顺序不发生改变。

　　大家可能会想，反正都是相等的元素，通过排序后谁在前谁在后有什么不一样呢？对排序算法进行稳定性分析又有什么实际意义呢？

　　其实，在学习数据结构与算法的过程中，我们解决的问题基本上都是对简单的数字进行排序。这时，我们考虑其是否稳定似乎并没有什么意义。

　　但是在实际应用中，我们面对的数据对象往往都是复杂的，每个对象可能具有多个数字属性且每个数字属性的排序都是有意义的。所以在排列时，我们需要关注每个数字属性的排序是否会对其他属性进行干扰。

　　举个例子，假如我们要给大学中的学生进行一个排序。每个学生都有两个数字属性，一个是学生所在年级，另一个是学生的年龄，最终我们希望按照学生年龄大小进行排序。而对于年龄相同的同学，我们希望按照年级从低到高的顺序排序。那么要满足这样的需求，我们应该怎么做呢？

　　第一个想到的，当然是先对学生的年龄进行排序，然后再在相同年龄的区间里对年级进行排序。这种办法很直观且似乎没什么问题，但是仔细一想，会发现如果我们要进行一次完整的排序，我们需要采用5次排序算法。那么我们有没有更好地解决办法呢？

　　如果我们利用稳定性的排序算法，这个问题就会更轻松地解决了。我们先按照年级对学生进行排序(先是年级)，然后利用稳定的排序算法，按年龄进行排序。这样，只需要运用两次排序，我们就完成了我们的目的。

　　这是因为，稳定的排序算法能够保证在排序过程中，相同年龄的同学，在排序之后，他们的顺序不发生改变。由于第一次我们已经将学生按年级排序好了，于是在第二次排序时，我们运用稳定的排序算法，相同年龄的学生依旧按年级保持顺序。

　　了解如何分析排序算法后，接下来就可以开始各种排序算法的学习了。

　　在讲解插入排序之前，我们先来回顾一下在一个有序数组中，我们是如何插入一个新的元素并使数组保持有序的呢？

　　我们需要遍历整个数组，直到找到该元素应该插入的位置，然后将后面相应的元素往后移动，最后插入我们的目标元素。(如下图)

　　插入排序其实就是借助的这样的思想，首先我们将数组中的数据分为两个区间，一个是已排序区间，另一个是未排序区间，同时这两个区间都是动态的。开始时，假设最左侧的元素已被排序，即为已排序区间，每一次将未排序区间的首个数据放入排序好的区间中，直达未排序空间为空。

　　最好情况: 即该数据已经有序，我们不需要移动任何元素。于是我们需要从头到尾遍历整个数组中的元素O(n)

　　最坏情况: 即数组中的元素刚好是倒序的，每次插入时都需要和已排序区间中所有元素进行比较，并移动元素。因此最坏情况下的时间复杂度是O(n^2)

　　平均时间复杂度:类似我们在一个数组中插入一个元素那样，该算法的平均时间复杂度为O(n^2)

　　从原理中可以看出，在排序过程中并不需要额外的内存消耗，也就是说，插入排序是一个原地排序算法

　　其实，我们在插入的过程中，如果遇到相同的元素，我们可以选择将其插入到之前元素的前面也可以选择插入到后面。所以，插入排序可以是稳定的也可能是不稳定的。

　　选择排序和插入排序类似，也将数组分为已排序和未排序两个区间。但是在选择排序的实现过程中，不会发生元素的移动，而是直接进行元素的交换。

　　选择排序的实现过程: 在未排序的区间中找到最小的元素，将其放入已排序区间的尾部。

　　最好情况，最坏情况：都需要遍历未排序区间，找到最小元素。所以都为O(n^2)

　　平均复杂度也为O(n^2)

　　与插入排序一样，选择排序没有额外的内存消耗，为原地排序算法。

　　答案是否定的，因为每次都要在未排序区间找到最小的值和前面的元素进行交换，这样如果遇到相同的元素，会使他们的顺序发生交换。

　　比如下图的这组数据，使用选择排序算法来排序的话，第一次找到最小元素 1，与第一个2 交换位置，那前面的 2 和后面的 2 顺序就变了，所以就不稳定了。

　　冒泡排序和插入排序和选择排序不太一样。冒泡排序每次只对相邻两个元素进行操作。每次冒泡操作，都会比较相邻两个元素的大小，若不满足要求，就将它俩交换。每一次冒泡，会将一个元素移动到它相应的位置，该元素就是未排序元素中最大的元素。

　　如果我们仔细观察冒泡排序算法，我们会注意到在第一遍中，我们将最大的元素移到末尾（假设排序以递增顺序进行）。在第二遍中，我们将第二大元素移至倒数第二个位置，以此类推。

　　递归思路:

　　如果数组大小为1，则返回。

　　每进行一次冒泡排序，可修复当前数组的最后一个元素。

　　对于除当前数组的最后一个元素之外的所有元素，均重复执行。

　　最好情况:我们只需要进行一次冒泡操作，没有任何元素发生交换，此时就可以结束程序，所以最好情况时间复杂度是 O(n)

　　最坏情况: 要排序的数据完全倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n^2)。

　　平均复杂度也为O(n^2)

　　冒泡的过程只涉及相邻数据之间的交换操作而没有额外的内存消耗，故冒泡排序为原地排序算法。

　　在冒泡排序的过程中，只有每一次冒泡操作才会交换两个元素的顺序。所以我们为了冒泡排序的稳定性，在元素相等的情况下，我们不予交换，此时冒泡排序即为稳定的排序算法。

　　要想分析和评价一个排序算法，除了需要分析其时间复杂度和空间复杂度，我们还需要考虑它的内存消耗和是否稳定。

　　本文讲的冒泡排序，选择排序，插入排序这三种排序算法，理解实现代码都非常简单，对于小规模的数据，用起来非常高效。但是这三种排序算法的时间复杂率都是O(n^2),在处理大规模的数据时，这三种排序算法明显就不是我们应该首选的了，所以下一篇文章我们将讨论更高效的一些排序算法。

　　未完待续……

　　如果喜欢我的文章，欢迎扫描下方二维码关注公众号《从0到CODE》了解更多算法知识以及LeetCode题解思路！

　　http://weixin.qq.com/r/vToxKbzEPuFBrfhK92_v (二维码自动识别)