排序 Sorting
排序算法的性质
- 稳定的（stable）：保证相同“大小”的值的先后顺序时不变的。比如张三和李四的个子都是1米7，张三本来站在李四前面，排完序之后，张三还是站在李四前面。这点的应用例如Excel表格中，依多个列进行排序。
- 适应的（adaptive）：输入的有序性可以减少排序的时间复杂度。
- 时间复杂度：一般平均都是O(nlog(n))
- 空间复杂度
各算法
垃圾们
选择排序 Selection Sort
最直觉的算法？就是每次找出（“选择”）剩下来最小的那个。最好、坏、平均时间都是O(n^2)。
不用额外空间，因因为是原地swap的。比较次数是n^2，swap次数是0到n-1，写入次数是swap次数两倍，写入次数在排序算法中算比较少的（但几乎没有太多应用场景，且有写入次数更少的）。
数组实现，是不稳定的。
直接选择排序算法,不稳定性,举个简单的例子,就知道它是否稳定..例如:(7) 2 5 9 3 4 [7] 1...当我们利用直接选择排序算法进行排序时候,(7)和1调换,(7)就跑到了[7]的后面了,原来的次序改变了,这样就不稳定了.
冒泡排序 Bubble Sort
冒泡排序，两两比较。
由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。
还行的
插入排序 Insertion Sort
语言实现
Python
Python的sorted()和list.sort()保证是稳定的。Python的排序实现是timsort，结合了merge sort和insertion sort。 TODO