数据结构---排序算法
内部排序 : 数据记录在内存中进行排序;
外部排序 : 数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短;
1：直接插入排序**
思路：从前往后遍历，默认最后形成的结果就是从小到大，对于每次选择的数，要选择向前插入的位置（维持前面是有序的），如果这个数大于前面的数，说明都是有序的，不进行操作，如果这个数小于前面的，则需要进行插入，把这个数拿出来放入temp中，然后开始从后到前便利，如果这个数比temp大，往后移动，则最终将temp数据插入的空缺位置即可。
2：快速排序
(时间复杂度：O(nlogn)，最坏：O(n2))
2.1：递归版
思路：[2,4,6,1,3,7,5]，以最后一个为哨兵，第一个为指针，然后循环，发现有比最后一个小的，将此值与指针前的数据交换，然后继续往前，最后再把哨兵数据与指针前数据交互即可，返回索引。
2.2：非递归版
利用栈的思想，将需要继续排序的首尾下标存入栈中，不断弹栈进行分区操作。
3：堆排序(topN)
概念1：完全二叉树：
就是每层都满，如果不满是从左到右填补。
概念2：最大堆最小堆：
大根堆：每个结点的值都大于或等于左右孩子结点
小根堆：每个结点的值都小于或等于左右孩子结点
数组下标即为节点下标，根节点为I,左子树2i，右子树为2i+1.最大堆是上面大
（i>2i,i>2i+1），最小堆是上面小。
思路：现在有个数组，我先把他排成最大堆，然后取出最大值，最后一个节点补上，然后破坏了最大堆结构，再进行最大堆修补。
1：如何把一个序列构造出一个大根堆
2：输出堆顶元素后，如何使剩下的元素构造出一个大根堆
建立最大堆：就是在原数组上建立一个最大堆，从N/2节点处，以此往上去调用子最大堆程序，这样就能使整个数组为最大堆。相当于对每个有子节点，都使其大值往上浮。
维护最大堆：就是输入一个数组及节点索引，我需要保证这个节点为最大堆。
复杂度：O(n*logn),不稳定。
第一步：大根堆调整(max_heapify)：
**注意前两个if的技巧，判断父节点左右三个节点最大值，那么先去左判断，大的话就赋值左节点为最大，然后判断右与最大索引的节点判断。然后再交换，让最大值放上面。
第二步：建立大根堆(build_max_heap)：
注意从2分之一处开始调用。
第三步：堆排序(heap_sort)：
4：归并排序
时间复杂度：
最好最坏都是 O( n log n )
稳定性：
只要在关键码相同时采用左序列元素先行的原则，就能保证算法的稳定性。
缺点：
每次拆分数组都要开心的数组，每次合并数组都要开新数组，空间复杂度很大，所以它的空间复杂度为O(n)，这是归并排序的主要弱点，牺牲了空间复杂度来换取时间复杂度的减少
思想：
写个归并排序，写完后说能不用辅助数组吗？(貌似原地归并排序，面完查的。。)
原地归并排序所利用的核心思想便是“反转内存”的变体，即“交换两段相邻内存块”，对于反转内存的相关文章，曾在文章“关于反转字符串(Reverse Words)的思考及三种解法”中对一道面试题做了分析。这一思想用到的地方很多，在《编程珠玑》中被称为“手摇算法”。通过手摇算法的交换内存的思想来进行原地归并又有不少变种，我们举例分析一种比较常见的情况，不同的方法还有基于二分查找的方法来确定交换的内存块，在《计算机编程艺术》中也有不同的思路提供，感兴趣见本文参考资料。
5：冒泡排序
思想：想到冒泡排序就立刻想到泡泡从下到上，即大的数跑上面，每次冒泡一个最大的到上面，那么所活动的区域越来越小，第一次是[1,n]第二次就[1,n-1]，所以双循环的里层就不断减小，每次遍历相当于把最大跑到上面，即每次对比，发现遍历点比右边的大，就交换，即这趟可以将所活动区域中最大值泡到右边。