排序算法排序是根据一个或一些关键字的大小，以递增或递减的顺序排列一系列记录的操作。
分类
计算机科学中使用的排序算法通常分为：
计算复杂度(最差、平均和最佳性能)取决于列表的大小(n)。一般来说，表现好的是o(n log n)，表现不好的是 (N2)。排序的理想性能是O(n)。仅使用一个抽象关键字比较的排名算法平均总是需要至少 (n log n)。
内存使用(和其他计算机资源的使用)
稳定性：稳定的排序算法会根据相等的键(换句话说，值)维护记录的相对顺序。也就是说，一个排序算法是稳定的，即当有两个键相等的记录R和S，并且R在原始序列中出现在S之前时，R也会在排序后的序列中出现在S之前。
一般方法：插入、交换、选择、合并等。交换排序包括冒泡排序和快速排序。选择排序包括摇床排序和堆排序。
当相等的元素无法区分时，例如整数，稳定性不是问题。但是，假设以下数字对将按其第一个数字排序。
(4, 1) (3, 1) (3, 7) (5, 6)
在这种情况下，可能会产生两种不同的结果，一种是根据相等的键值保持相对顺序，而另一种则不是：
(3，1) (3，7) (4，1) (5，6)(维持秩序)
(3、7) (3、1) (4、1) (5、6)(次序已改变)
不稳定的排序算法可能会改变相等键值中记录的相对顺序，但稳定的排序算法永远不会。不稳定的排序算法尤其可以被认为是稳定的。一种方法是手动扩展键值的比较，这样在其他方面具有相同键值的两个对象之间的比较将决定使用原始数据顺序中的条目作为相同的最终结果。但是，请记住，这种顺序通常会带来额外的空间负担。
排名算法列表
在该表中，n是要排序的记录数，k是不同键值的数量。
稳定的
气泡排序)—氧(n2)
鸡尾酒种类(双向泡沫种类)-O (N2)
插入排序—0(N2)
桶排序—0(n)；需要额外的内存。
计数排序(计数排序)—O(n k)；需要额外的内存。
合并排序)—O(n log n)；需要额外的内存。
就地合并排序-o (N2)
二叉树排序)—O(n log n)；需要额外的内存。
分类排序—O(n k)；需要额外的内存。
基数排序—0(n ^ k)；需要额外的内存。
侏儒排序—0(N2)
具有高概率的库sort-o (n log n)需要(1 )n个额外内存。
易变的
选择排序—0(N2)
外壳排序)— O(n log n)如果使用了最佳的当前版本
梳状排序—0(对数n)
堆-0(对数n)
平滑排序—0(对数n)
快速排序— O(n log n n)预期时间，O(n2)最坏情况；一般认为这是已知的最快速的大型随机序列号分类。
内含子排序—0(对数n)
耐心排序——O(n log n k)额外时间需要额外的O(n k)空间，也需要找到最长的递增子序列。
不切实际的排序算法
Bogo sort-o (n n！)预期时间，无尽最坏情况。
愚蠢的种类——O(n3)；递归版本需要O(n2)个额外内存。
珠子排序—O(n)或O(n)，但需要特殊硬件。
Bakesorting-o (n)，但需要特殊的硬件。
基于的排序算法
排序算法很多，空间要求和时间效率不同。下面列出了一些常见的排序算法。插入排序和冒泡排序也称为简单排序。它们不需要太多空间，但时间效率不稳定。与简单排序相比，后三种排序需要多一点空间，但时间效率可以稳定在较高水平。基数排序是一种针对小范围关键词的排序算法。
插入排序
> 冒泡排序选择排序
快速排序
堆排序
归并排序
基数排序
希尔排序
插入排序
插入排序是这样实现的：
首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。
从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。
重复2号步骤，直至原数列为空。
插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。
冒泡排序
冒泡排序是这样实现的：
首先将所有待排序的数字放入工作列表中。
从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。
重复2号步骤，直至再也不能交换。
冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。
选择排序
选择排序是这样实现的：
设数组内存放了n个待排数字，数组下标从1开始，到n结束。
i=1
从数组的第i个元素开始到第n个元素，寻找最小的元素。
将上一步找到的最小元素和第i位元素交换。
如果i=n－1算法结束，否则回到第3步
选择排序的平均时间复杂度也是O(n²)的。
快速排序
现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。
堆排序
堆排序与前面的算法都不同，它是这样的：
首先新建一个空列表，作用与插入排序中的"有序列表"相同。
找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。
重复2号步骤，直至原数列为空。
堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。
看起来似乎堆排序与插入排序有些相像，但他们其实是本质不同的算法。至少，他们的时间复杂度差了一个数量级，一个是平方级的，一个是对数级的。
平均时间复杂度
插入排序 O(n2)
冒泡排序 O(n2)
选择排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
归并排序 O(n log n)
基数排序 O(n)
希尔排序 O(n1.25)
冒泡排序
654
比如说这个，我想让它从小到大排序，怎么做呢？
第一步：6跟5比，发现比它大，则交换。564
第二步：5跟4比，发现比它大，则交换。465
第三步：6跟5比，发现比它大，则交换。456