冒泡排序
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序是与插入排序拥有相等的运行时间，但是两种算法在需要的交换次数却很大地不同。
在最好的情况，冒泡排序需要O(n^2)次交换，而插入排序只要最多O(n)交换。
冒泡排序的实现通常会对已经排序好的数列拙劣地运行（O(n^2)），而插入排序在这个例子只需要O(n)个运算。
因此很多现代的算法教科书避免使用冒泡排序，而用插入排序替换之。
冒泡排序如果能在内部循环第一次运行时，使用一个旗标来表示有无需要交换的可能，也可以把最好的复杂度降低到O(n)。
在这个情况，已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序反过来，也可以稍微地改进效率。
有时候称为鸡尾酒排序，因为算法会从数列的一端到另一端之间穿梭往返。
鸡尾酒排序
鸡尾酒排序，也就是定向冒泡排序，是冒泡排序的一种变形。
此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。
插入排序
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置中
- 重复步骤2~5
快速排序
- 从数列中挑出一个元素，称为 “基准”（pivot），
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。 - 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
排序效果：
归并排序
归并排序是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用
步骤：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
堆排序
堆积排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
选择排序
- 首先在未排序序列中找到最小元素，存放到排序序列的起始位置，
- 然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。
- 以此类推，直到所有元素均排序完毕。
希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
- 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位>
梳排序
梳排序是改良自冒泡排序和快速排序。
在冒泡排序算法中，只比较阵列中相邻的二项，即比较的二项的间距(Gap)是1，
梳排序提出此间距其实可大于1，改自插入排序的希尔排序同样提出相同观点。
梳排序中，开始时的间距设定为阵列长度，并在循环中以固定比率递减，通常递减率设定为1.24。
在一次循环中，梳排序如同冒泡排序一样把阵列从首到尾扫描一次，比较及交换两项，不同的是两项的间距不固定于1。
如果间距递减至1，梳排序假定输入阵列大致排序好，并以冒泡排序作最后检查及修正。
