各种排序算法实现
排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。
第一类：插入排序
基本原理，每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。
1.直接插入排序(Insert Sort)
基本思想：
当插入第i个对象时，前面的V[1],V[2],…,V[i-1]已经排好序，此时，用v[i]的关键字与V[i-1], V[i-2],…的关键字顺序进行比较，找到插入位置即将V[i]插入，原来位置上对象向后顺移。
算法实现：
伪代码
说明
直接插入排序是一种稳定的排序方法。
原理：
关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。
2.希尔排序(Shell Sort)
基本思想：
在插入排序中，只比较相邻的结点，一次比较最多把结点移动一个位置。如果对位置间隔较大距离的结点进行比较，使得结点在比较以后能够一次跨过较大的距离，这样就可以提高排序的速度。
设待排序的对象序列有n个对象，首先取一个整数gap<n作为间隔，将全部对象分为gap个子序列，所有距离为gap的对象放在同一个序列中，在每一个子序列中分别施行直接插入排序，然后缩小间隔gap，如取gap=gap/2，重复上述的子序列划分和排序工作，直到最后取gap为1为止。
算法实现c
因为直接插入排序在初态为正序时所需时间最少，实际上，初态为基本有序时直接插入排序所需的比较和移动次数均较少。另一方面，当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大。在shell排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但组内元素已经过多次排序，数组已经比较接近有序状态，所以新的一趟排序过程也较块。
算法实现
基于c的伪码
算法时间复杂度分析
考虑关键字的比较次数和对象移动次数
1、在最好情况下，初始状态是递增有序的，一趟扫描就可完成排序，关键字的比较次数为n-1，没有记录移动。
2、若初始状态是反序的，则需要进行n-1趟扫描，每趟扫描要进行n-i次关键字的比较，且每次需要移动记录三次，因此，最大比较次数和移动次数分别为：
2.快速排序(Quick Sort)
快速排序法是一种所需比较次数较少，目前在内部排序中速度较快的方法。
其思想是取待排序的结点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位置，使得这个位置的左边的所有结点的值都小于等于这个控制值，而这个位置的右边的所有结点的值都大于等于这个控制值。
算法实现：
c版本伪代码
算法时间复杂度分析：
考虑关键字的比较次数和对象移动次数
1、最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分前后无序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数为
2、最好情况是每次所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左右两个无序子区的长度大致相等。
设C(n)表示对长度为n的序列进行快速排序所需的比较次数，显然，它应该等于对长度为n的无序区进行划分所需的比较次数n-1，加上递归地对划分所得的左右两个无序子区进行快速排序所需的比较次数。假设文件长度n=2k ，k=log2n，因此有：
快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为O(nlog2n)。
可以证明，快速排序的平均时间复杂度也是O(nlog2n)。
快速排序是不稳定的排序方法。
第三类：选择排序
基本原理: 将待排序的结点分为已排序(初始为空)和未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。
选择排序:
1.直接选择排序
在一组对象V[i]到V[n-1]中选择具有最小关键字的对象
若它不是这组对象中的第一个对象，则将它与这组对象中
的第一个对象对调。
删除具有最小关键字的对象，在剩下的对象中重复第(1)、
(2)步，直到剩余对象只有一个为止。
算法实现：
c语言版本实现
算法复杂度分析：
1、无论初始状态如何，在第i趟排序中选择最小关键字的记录，需做n-i次比较，因此总的比较次数为：
2、当文件为正序时，移动次数为0，文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。
直接选择排序是不稳定的排序方法。
2.堆排序(待续)
