1.冒泡排序和选择排序

为什么把冒泡排序和选择排序放在一块儿呢？因为我发现他们两个有点像。

冒泡排序是不停的把最大的元素换到数组的最右端。

而选择排序是把最小的元素换到最左端。

看到这儿，你是不是觉得冒泡和选择好像没啥区别啊，把最大换成最小就成了一种新的算法？那我也来一个？

其实，无论换最大还是最小，都无关紧要，就算冒泡变成换最小的元素换到数组的最左端，那它也叫冒泡排序的。

冒泡排序的描述：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到不需要交换，也就是说该数列已经排序完成。

选择排序的描述：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

为了便于描述二者之间的区别，我们把冒泡和排序都换成是把最大元素换到最右端。

他们的最大区别在于

冒泡排序不停比较两个相邻的元素，并不断交换较大的元素，直到数组尾。

选择排序开始只比较不交换，直到数组尾才进行一次交换。

在这里，你可以认为选择排序是冒泡排序的优化，因为选择排序多数时候减少了交换的次数，却实现了相同的效果。

难道冒泡排序多做的那些交换就全是无用功吗？仔细想想，当然不是这样！

仔细看看冒泡排序是怎么说的，“走访数列的工作是重复地进行直到不需要交换”，这个很重要，假如我们加入一个变量，来记录交换次数，当某趟遍历交换次数为零的时候，说明数组已经排序好了，那就可以结束排序了！

比如“1,2,3,4,5,6,7,8,9”，对于这样一个数组，冒泡排序只需要进行一次遍历就ok了，所以对于基本有序的数组，冒泡可以做到O(n)的复杂度。

但是选择排序做不到这一点，一个已经有序的数组和随机排列的数组将花差不多的时间（稍微会少点，因为有序数组不需要交换，只需要比较）。

在这里，我们发现，选择排序并没有利用数组的初始输入状态，而冒泡排序利用了。这是冒泡的优势，在这里，你可能会想，冒泡是如何利用初始状态的呢？当然就是在一次又一次相邻元素的比较上嘛。

最后，由于选择排序会交换不相邻元素，比如直接把a[0]和a[8]交换位置，导致了选择排序的不稳定。而冒泡只会交换相邻元素，所以冒泡是稳定的，我们当然不会蠢到a[0]=1,a[1]=1的时候交换他们的位置是吧。

待会儿我们会分析插入排序和希尔排序，这两个排序的稳定性的因果分析也和是否交换不相邻元素有关。

先到这儿，明天再写。。