排序算法

排序语言是最简单的算法，了解排序算法，有助我们初步理解计算机语言，加强思路与逻辑。
日本程序员norahiko，写的一个的动画演示，可以直观看到各个排序算法的演示

冒泡排序 （泡沫排序）

工作原理：比较相邻的元素。如果第一个比第二个大，就交换他们两个。
这个算法是最简单了解和实现的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。
延伸：鸡尾酒排序（定向冒泡排序）是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向来回比较在序列中进行排序。

选择排序

工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

插入排序

工作原理：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
   重复步骤2~5

ps：如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序。
延伸：希尔排序（递减增量排序算法）：通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

归并排序

工作原理：先将元素分割为个体，再用树状图合并的方式，两两比较后合并，如果每组有多个元素，则每次比较第一个数，小（大）的放入下方树组，再次比较，直到所有元素合并在一起

快速排序（划分交换排序）

工作原理：

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区操作。
3. 递归把小于基准值元素的子数列和大于基准值元素的子数列排序。