冒泡排序：

基本思想是重复的进行整个数组的排序，一次比较两个元素(两两排序)，如果它们顺序不符合就交换，重复这样直到数列没有再需要交换的数为止(结束条件)。

因为它就好像气泡一样，轻的气泡会往上漂浮，在不断漂浮的过程中，发生了两两交换过程，所以叫冒泡排序。

应对面试排序的口诀记忆法：

N个数字来排序，

两两比较小靠前；

外层循环n-1,

内层循环n-1-i;

冒泡排序的效率：

排序算法的效率按照比较次数来测量。

在冒泡排序中，通道1内有n – 1 次比较，通道2中有n – 2 次比较，依此类推。

比较总数= (n – 1) (n – 2) (n – 3) … 3 2 1 = n(n – 1)/2 。

n(n – 1)/2 是O(n2) 阶的级数。 因此，冒泡排序算法是阶O(n2)的算法。

插入排序：

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入,类似于《赌神》中的整扑克牌。

在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。

• 稳定
  空间复杂度O(1)
  时间复杂度O(n2)
  最差情况：反序，需要移动n*(n-1)/2个元素
  最好情况：正序，不需要移动元素
• 数组在已排序或者是“近似排序”时，插入排序效率的最好情况运行时间为O(n)；
• 插入排序最坏情况运行时间和平均情况运行时间都为O(n2)。

桶排序和归并排序

关于桶排序先做几点说明：

1）桶排序是稳定的；
2）桶排序是常见排序算法中最快的一种，大多数情况下比快排和归并排序还要快 ；
3）桶排序非常快但是也非常消耗空间，典型的以空间换时间，基本上是最耗内存的一种排序算法；

桶排序中：无序数组有个要求,就是成员隶属于固定(有限的)的区间,如范围为0-9