排序是将集合中的元素按照某种顺序排列的过程。比如，一个单词列表可以按照字母或长度排序，一个城市可以按人口、面积或邮编排序。
排序算法有很多，对它们的分析也已经很透彻了。排序算法的效率与待处理元素的数目有关，对小型集合， 采用复杂的排序算法可能得不偿失；对于大型集合，需要尽可能充分利用各种改善措施。再次会讨论各种排序技巧，并比较它们的运行时间。
在讨论具体的算法之前，思考下我们要从那几个上面衡量排序算法的优劣：
- 总的比较次数是衡量排序的一个最常用指标
- 总的交换次数也是衡量排序效率的一个很重要的指标。
- 稳定性：对于集合中重复的元素，经过排序后，重复元素的相对位置是否依然保持一致，一致则认为该算法是稳定的。
下图是大样查找资料为大家罗列的十种常见排序算法：
非线性时间比较类排序: 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序
非线性时间比较类排序
冒泡排序 Bubble Sort
冒泡排序多次遍历列表。它比较相邻的元素，将不合顺序的交换。每一轮遍历都将下一个最大值放到正确的位置上。本质上，每个元素通过“冒泡”找到自己所属的位置。
原理
冒泡排序的第一轮遍历过程。深色的是正在比较的元素。如果列表中有 n 个元素，那么第一轮遍历要比较 n–1 对。注意，最大的元素会一直往前挪，直到遍历过程结束。
第二轮遍历开始时，最大值已经在正确位置上了。还剩 n–1 个元素需要排列，也就是说要比较 n–2 对。既然每一轮都将下一个最大的元素放到正确位置上，那么需要遍历的轮数就是 n–1。完成 n–1 轮后，最小的元素必然在正确位置上，因此不必再做处理。
代码实现
效率问题
在分析冒泡排序算法时要注意，不管一开始元素是如何排列的，给含有 n 个元素的列表排序总需要遍历 n–1 轮。表 5-6 展示了每一轮的比较次数。总的比次数是前 n–1 个整数之和。由于前 n 个整数之和是 ，因此前 n–1 个整数之和就是，即 。这表明，该算法的时间复杂度是 O(n2)。
冒泡排序通常被认为是效率最低的排序算法，因为在确定最终位置之前必须交换元素。“多余”的交换操作代价很大。上面的代码中用到了标记变量的思想，如果后续的列表元素是有序的，则不在进行对后面进行排序，提高了代码效率。这种排序通常被称为短冒泡。
选择排序Selection Sort
选择排序在冒泡排序的基础上做了改进，每次遍历列表时只做一次交换。
要实现这一点，选择排序在每次遍历时寻找最小值，并在遍历完之后将它放到正确位置上。第一次遍历后，最小的元素就位；第二次遍历后，第二小的元素就位，依此类推。若给 n 个元素排序，需要遍历 n–1 轮，这是因为最后一个元素要到 n–1 轮遍历后才就位。
算法分析
可以看出，选择排序算法和冒泡排序算法的比较次数相同，所以时间复杂度也是O(n2).但是，由于减少了交换次数，因此选择排序算法更快。
同时，选择排序是不稳定的，例如
nums = [7, 2, 7, 4, 1] 在对nums第一轮排序中，会将第一个7和后面1进行互换，那么就改变了两个7的相对位置。简单插入排序 Insertion Sort
插入排序的时间复杂度也是 O(n2) ，但原理稍有不同。它在列表较低的一端维护一个有序的子列表，并逐个将每个新元素“插入”这个子列表.
原理
- 从数组nums第二个元素开始遍历, 遍历len(nums)-1
- 先拿到index为1的待插入元素, 如果nums[1]>nums[0], 则跳过,否则将前面一个元素前移, 然后再讲待插入元素插入前面一个元素位置
- 以此类推, 遍历到最后一个元素, 如果该元素为nums中最小值, 则将前面的元素依次都要前移一位, 然后才将该元素插入到nuns的起始位置.
实现
算法分析
在最坏情况下，插入排序算法的比较次数是前 n–1 个整数之和，对应的时间复杂度是 O(n2) 。在最好情况下（列表已经是有序的），每一轮只需比较一次。
移动操作和交换操作有一个重要的不同点。总体来说，交换操作的处理时间大约是移动操作的 3 倍，因为后者只需进行一次赋值。在基准测试中，插入排序算法的性能很不错。
希尔(插入)排序 Shell's Sort
希尔排序也称递减增量排序(Diminishing Increment Sort)，是插入排序的一种更高效的改进排序算法，将列表分成数个子列表，并对每一个子列表应用插入排序。如何切分列表是希尔排序的关键——并不是连续切分，而是使用增量i（有时称作步长）选取所有间隔为 i 的元素组成子列表.
归并排序
拆分 归并 递归 双指针
- 归并: 归并是指将两个较小的有序列表归并为一个有序列表的过程
- 如果列表为空或只有一个元素，那么从定义上来说它就是有序的
归并排序是一种采用分治策略的递归算法。当列表长度大于1时，就将列表一分为二，并对两部分都递归调用归并排序。当两部分都有序后，就进行归并这一基本操作。
图a 展示了示例列表被拆分后的情况， 图 b 给出了归并后的有序列表.
实现
算法分析
分析 mergeSort 函数时，要考虑它的两个独立的构成部分。首先，列表被一分为二。在学习二分搜索时已经算过，当列表的长度为 n 时，能切分 log2n 次。第二个处理过程是归并。列表中的每个元素最终都得到处理，并被放到有序列表中。所以，得到长度为 n 的列表需要进行 n 次操作。由此可知，需要进行 logn 次拆分，每一次需要进行 n 次操作，所以一共是 n n log 次操作。也就是说，归并排序算法的时间复杂度是 O n n ( log ) 。
有一点要注意： mergeSort 函数需要额外的空间来存储切片操作得到的两半部分。当列表较大时，使用额外的空间可能会使排序出现问题。
快速排序
和归并排序一样， 快速排序也采用分治策略，但不使用额外的存储空间。不过，代价是列表可能不会被一分为二。出现这种情况时，算法的效率会有所下降。