参考资料：http://web.jobbole.com/87968/

算法的时空

• 时间复杂度: 一个算法执行所耗费的时间。
• 空间复杂度: 运行完一个程序所需内存的大小。

以下都是左小右大的排序要求

要点

• 计算机的排序算法，根据内存的使用形式，分成了内存排序（仅仅使用了内存）和外存排序（内存+外存都使用了）
• 目前来看，基本都是内存排序
• 内存排序细分
• 稳定的排序算法有：
  基数/桶/冒泡/插入/归并/计数
• 不稳定的排序算法有：
  选择/希尔/堆/快速
  1.选择排序
  //堆排序，简单选择排序
  2.交换排序
  //冒泡排序，快速排序
  3.插入排序
  //希尔排序就是插入排序的升级
  4.归并排序
  5.基数排序
  //基数排序，桶排序

---

冒泡排序

1.让数组相邻两数比较大小，根据大小关系交换位置
2.重复第1步骤来遍历数组，就可以得出一个最大或最小值
3.重复第2个步骤，数组有多少个数，就遍历多少次，就可以得出一个完整的排序数组

快速排序

1.任意选数组内一个数为基准
2.用基准和数组里面的数，逐一比较。根据大小关系分成大小两个数组分别放在基准的左右两侧
//执行完这一步，基准数的位置在排序中的位置就确定下来了
3.在分裂出来的两个数组上，重复进行第1和第2个步骤，以此循环，就可以得到一个完整的排序数组
//这是最典型的分治算法，不断分裂，速度都是指数级的，因为速度极快，所以叫快速排序，

选择排序

1.逐一比较数组内的数，找出最大或最小的值，放在数组最靠边的位置
//这样就可以确定一个数的位置了
2.不断重复第1个步骤，整个数组就排序完成了

插入排序

1.任意选一个数作为基数数组
//就等于排序好的数组，即使只有一个数
2.挑选下一个数，进入基数数组，组成新的数组，根据大小关系排序
不断重复第1-2步骤，整个数组的排序就完成了

堆排序

要了解堆首先得了解一下二叉树，在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
树和二叉树的三个主要差别：
树的结点个数至少为 1，而二叉树的结点个数可以为 0
树中结点的最大度数没有限制，而二叉树结点的最大度数为 2
树的结点无左、右之分，而二叉树的结点有左、右之分
二叉树又分为完全二叉树（complete binary tree）和满二叉树（full binary tree）

• 二叉树又分为完全二叉树和满二叉树，完全二叉树的优点是除了最底层，其他层都是满的
• 完全二叉树的优点使得他可以选择数组这样的数据结构来存数据，其他树一般都是链表这样的数据结构
• 满二叉树的优点是枝干都是满的
• 3. 堆排序原理
     堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：
     最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
     创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
     堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
• 最大堆的形式就是根节点是最大的，最小堆形式就是根节点是最小的

---

堆排序

• 树形状的数据结构分为普通树和二叉树，二叉树又分为完全二叉树和满二叉树，完全二叉树的特点就是除了最底一层，其他都是满的，这个特点可以使得，二叉树中的完全二叉树的下标和各个节点之间存在固定的数学公式，我们可以通过数学公式来调整树节点和树叶保存的数据位置，这是堆排序的理论基础
• 完全二叉树，根据根节点时最小或者时最大的特征可以把堆分为最大堆和最小堆
• 把一组无序的数组放进完全二叉树机构里面，并且按照最大堆形式展示，利用数学公式找出最大堆的根节点，也就是最大数，然后把他和树的末梢调换位置，不断重复这个动作，那么一个数组就排序成功了

希尔排序//就是把分治法思想加入到插入排序然后优化

1.两个一组分治，每个分支用插入排序排好，
2.四个一组，每个分支又用插入排序排好
3.以此类推，不断分治直到整个数组排序完成

归并排序

分治法的典型案例，先把数组分成若干个小数组，各个分支的小数组排序好，然后把各个小数组合成若干个稍微大一点的数组，再排序，如此反复多次直到最后重新排序整个大数组~//感觉就是碰运气，博小数组的排序在大数组中的顺序也正确

鸡尾酒排序

鸡尾酒排序是冒泡排序的轻微变形。不同的地方在于，鸡尾酒排序是从低到高然后从高到低来回排序，而冒泡排序则仅从低到高去比较序列里的每个元素。他可比冒泡排序的效率稍微好一点，原因是冒泡排序只从一个方向进行比对(由低到高)，每次循环只移动一个项目。

猴子排序

猴子排序 (Bogo Sort) 是个既不实用又原始的排序算法，其原理等同将一堆卡片抛起，落在桌上后检查卡片是否已整齐排列好，若非就再抛一次。其名字源自 Quantum bogodynamics，又称 bozo sort、blort sort 或猴子排序（参见无限猴子定理）。并且在最坏的情况下所需时间是无限的。

桶排序

桶排序 (Bucket sort)或所谓的箱排序的原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。

基数排序

排序过程：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

感悟：

• 好像每个算法都时先确定一个数的位置，然后重复这样的操作，n个数，就操作n次，这样就完成了整个数组的排序
• 以前学算法之前，关注的是数据的大小关系，学了排序算法之后才知道，原来排序的核心就写在字面上，‘排序’，注重的是数据的位置，大小关系只是排序的要求，比如说我不要求大小了，单数排前面，双数排后面。这样的数组也是是一种排序数组，即使他的依附关系不是大小关系