[数据结构与算法]排序算法(冒泡、选择、插入、快速、归并、堆)

排序算法的稳定性：
在待排序的数组中，如果有值相同的数据，排序过程中如果无论如何都不会改变它们俩的前后顺序，则认为该排序算法是稳定的
注意：算法的时间复杂度并不能完全地代表算法的实际执行时间，有些时候看似复杂度高的算法反而速度快
冒泡：

数据左右进行比较，把最大的数据交换到最后，特点是该算法对数据的有序性敏感，在排序过程中如果发现有序可以立即停止，如果待排序的数据基本有序时，冒泡排序的效率非常高。
时间复杂度：最优：O(n)  平均：O(n^2)
稳定的

选择：

假定最开始的位置是最小值并记录下标min，然后与后面的数据比较，如果有比min下标的数据小，则更新min，最后如果min的值发生变化，则交换min为下标的数据与最开始位置的数据
虽然时间复杂度挺高的，但是特点是交换次数少，因此实际的运行速度并不慢
是冒泡排序的一种变种，但是对数据的有序性不敏感，因此数据较混乱时比冒泡快
时间复杂度：O(n^2)
不稳定的    【10 10 1】

插入：

是插入排序的升级版，由于插入排序时，数据移动的数据比较慢，所以增加了增量的概念，以此提高排序的速度，数据量越多，比插入的速度越快。
时间复杂度：O(n^2)
不稳定的

快速：

找到一个标杆，备份标杆的值，一面从左边找比标杆值大的数据，然后把找到的数据赋值给标杆位置，更新标杆的位置到左标杆处，再从右边找比标杆值小的数据，如果找到也把数据赋值给标杆位置，更新标杆的位置到右标杆处，重复以上过程，直到左右标杆相遇，最后在遇到处还原标杆的值，最终达到标杆左右两边整体有序，然后按照同样的方法排序左右部分，最终全部有序。
它的综合性能最高，因此叫做快速排序，笔试中考得比较多的排序算法。
时间复杂度：O(nlogn)
不稳定的
83  86  77  15  93  35  86  92  49  21  :排序前
83  86  77  15  [93]  35  86  92  49  21
83  86  77  15  21  35  86  92  49  93
83  86  77  15  [21]  35  86  92  49  93
15  21  77  86  83  35  86  92  49  93
77  86  83  [35]  86  92  49
15  21  35  86  83  35  86  92  49  93
86  83  [77]  86  92  49
15  21  35  49  77  86  86  92  83  93
86  [86]  92  83
15  21  35  49  77  86  83  86  92  93
[86]    83
15  21  35  49  77  83  86  86  92  93  :排序后

归并：

先把待排序的数据拆分成单独的个体，然后按照从小到大的顺序合并复制到临时内存中，最终全部合并结束后再从临时内存赋值给原内存。
由于需要使用额外的内存空间，因此避免数据交换时的耗时，也是一种典型的用空间换时间的算法。
时间复杂度：O(nlogn)
稳定的

堆：

把数据当作完全二叉树，然后把树调整成大顶堆，再把根节点的数据交换到最后，然后数量-1，然后剩余部分重新调整成大顶堆，重复以上步骤，直到数量为1时结束。