这里是引用
1.插入排序:
(1).直接插入排序：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的序列
(2).折半插入排序：在将一个元素插入已排好序的数组的过程中，寻找插入点，将待插入区域的首元素设为a[low],末元素设为a[high],则轮比较时将待插入元素与a[mid]相比较，其中mid=(low+high)/2,如果比a[mid]
小，则选择a[low]到amid-1为新的插入区域，否则选择amid+1到a[high]为新的插入区域，直到low<=high不成立，即将此位置（包括low）之后所有元素后移一位，并将新元素插入a[low]
(折半插入排序是对直接插入排序的一种改进，减少了比较次数)
(3).二路插入排序：另设一个和待排数组arr同类型的数组brr，首先将arr[1]赋值给brr[1]，并将brr[1]看成
是在排好序的序列中处于中间位置的记录，然后从arr中第二个记录开始依次插入到brr[1]之前或之后的有序序列
中。先将待插记录的关键字和brr[1]的关键字进行比较，若arr[i].key<brr[1].key,则将arr[i]插入到brr[1]之前的有序表中。反之，则将arr[i]插入到brr[1]之后的有序表中。在实现算法时，可将brr看成一个循环变量(数组首尾循环)，并设两个指针first和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在brr中的位置。
（二路插入排序是对折半插入排序的改进，减少了交换的次数）
(4).希尔排序:先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序，
然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
（希尔排序是对直接插入排序的高效改进，减少了其复制的次数（基本有序，交换次数也少））
2.选择排序
（1).直接选择排序:第一次从R[0]_{R[n-1]中选取最小值，与R[0]交换，第二次从R[1]}R[n-1]中选取最小值，与R[1]交换，第i次从R[i-1]_{R[n-1]中选取最小值，与R[i-1]交换，第n-1次从R[n-2]}R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大的有序序列
(2).堆排序：1.根据序列，构建一个初始堆（大根堆或者小根堆）
2.交换堆的第一个和最后一个元素
3.排除最后一个元素，将序列第一个元素到倒数第二个重新整理成堆
4.再次交换堆的第一个和倒数第二个元素
5.重复第3步，直到完成排序
大根堆的构造：第一次创建大根堆从中间节点开始(节点起始值为1)，依次到第一个节点，除过第一次，以后创建大根堆，都从第一个节点开始（这样只需考虑左孩子或者右孩子）【所有父亲都大于它的孩子】
3.交换排序:
(1).冒泡排序
(2).快速排序：是一种排序二叉树结构的交换排序方法，也是对冒泡排序的一种改进。
基本思想:任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序组合分割成两子序 列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右 子序列重复该过程，直到所有元素都排列在相应位置上为止。
（划分方式有：hoare版本，挖坑法，前后指针版本）

4.归并排序
归并排序是一种高效、通用、稳定、基于比较的排序算法。其思想如下：
(1).将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表
(2).将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是
排好序的线性表。
归并排序有两种实现方法：
(1).自顶向下：以数组A[8]={6,3,2,7,1,5,8, 4}为例

(2).自底向上：直接从线性表中的单个元素开始，进行两两合并，然后再以每两个元素为单位，进行两两合并，直到最后只剩下一个线性表。

二者比较：采用自顶向下的归并排序要用到递归，这种方法的好处是代码容易理解，能比较直观地描述算法思想。但在排序过程中会占用大量计算机内部的栈空间，
如果线性表过长，可能会造成栈溢出，从而使程序崩溃，而自底向上的迭代不会出现这种问题。