记录一些基本排序算法，并尝试加上一些自己的理解
时间复杂度与空间复杂度
1.时间复杂度：
将算法中基本操作的执行次数作为算法时间复杂度的度量。
时间复杂度不是执行完一段程序的总时间，而是其中基本操作的总次数。
对一个算法进行时间复杂度分析的要点，是明确算法中哪些操作是基本操作。
问题规模：n,基本操作所执行的次数是n的一个函数f(n)
取出f(n)中随n增大而增长最快的项，然后将其系数变为1，作为时间复杂度的度量，记为：
T(n)=O(f(n)中增长最快的项/此项的系数)
有时算法复杂度不仅跟初始输入的数据规模n有关，还和数据本身有关，如一些排序算法数据初始有序性不同，通常将最坏的情况作为算法时间复杂度的度量
实际程序分析中将循环次数设为未知数，构造等式关系进而求解
2.空间复杂度：
算法在执行时所需存储空间的度量，主要考虑临时占用的存储空间的大小，以数量级的形式给出。
经典排序算法
分类记忆
插入类的排序：直接插入排序、折半插入排序、希尔排序
在已经有序的部分基础上找位置插入新关键字，之前不能保证任何关键字归到最后的绝对正确位置。
1.直接插入排序
按照第一个关键字有序，从他后面的关键字依次开始，进行n-1趟，每趟找到待排关键字在有序序列的位置，方法是前面的给后面的让位置。
- 稳定
- 时间：有序最好O(n)；逆序最坏O($n^2$)
- 空间：O(1)
2.折半插入排序
与直接插入类似，只是查找插入位置的方法不同，采用折半查找法来查找插入位置。折半查找法要满足序列已经有序。
- 稳定
- 时间：最好O(n$log_2n$)；最坏O($n^2$)；平均O($n^2$)
- 空间：O(1)
3.希尔排序（缩小增量排序）
交换类的排序：冒泡排序、快速排序
核心是交换，每趟排序都通过一系列的“交换”动作，让一个关键字排到最终位置上。时间复杂度都与数据初始有序性有关
1.冒泡排序
每一趟，两两比较，大的换到后面，进行n-1趟，设置标志，结束条件为一趟排序过程中没有发生关键字交换
- 稳定
- 时间：有序最好O(n)；逆序最坏O($n^2$)
- 空间：O(1)
2.快速排序
每一趟选择当前子序列的一个关键字（通常第一个）作为枢纽，双指针法，分别从序列两端往中间扫描，分别将小的换到枢纽前面，大的放他后面，两端指针不断靠近最终相遇从而确定枢纽的位置，完成一趟划分，得到更短的子序列，用相同的方式处理子序列（把所有子序列都划分完毕成为一趟划分）。由其算法基本思想可知，用到递归。
- 不稳定
- 时间：无序最好O(n$log_2n$)；有序O($n^2$)；平均O(n$log_2n$)
- 空间：O($log_2n$)
选择类的排序：简单选择排序、堆排序
核心为“选择”，选出最大，与末位交换。
1.简单选择排序：
无序部分从头到尾扫描，选出最小的放到前面，即有序部分。
- 不稳定
- 时间：与初始序列无关O($n^2$)
- 空间：O(1)
2.堆排序（重要）：
什么是堆？看成一棵完全二叉树，满足：任何一个非叶结点的值都不大与其左右孩子结点的。即大顶堆，父亲大孩子小。
基本思想：堆的根结点最大，因此将一个无序序列调整成一个堆，就能找出最大的元素，然后把他交换到序列的最后，这样，有序加一，无序减一，对新的无序序列重复这样的操作，就实现了排序。
关键操作：将序列调整为堆
堆排序执行过程描述：
- 无序序列对应完全二叉树，从第一个非叶子结点开始，从右至左，从下至上，进行调整得到大顶堆
- 首位交换，无序减一，有序加一。这是新换的首位可能不满足定义，继续调整。
- 重复2），直到只剩下一个关键字，排序结束
实际实现过程中要注意几个点：
- 找到第一个非叶子结点开始调整
- 调整过程中注意要下移动调整，相当于走了一条当前结点到叶子结点的路径
- 不稳定
- 时间：与初始序列无关O(n$log_2n$)
- 空间：O(1)
适用情况：数量级大，规模大的排序，例如从一万个关键字挑出前10个最小的
扩展：面试海量数据处理？10亿个数如何找到TOP10?
归并类的排序：二路归并
分治：整个序列分成两半，每一半分别进行归并排序，有序后合并，用递归。
- 稳定
- 时间：与初始序列无关O(n$log_2n$)
- 空间：O(n)需要转存整个待排序列
基数类的排序：基数排序
O(n$log_2n$)