在此讨论的都是内排序，在内存中进行的
一，直接插入排序
分两个区，有序区和无序区，无序区的第一个元素插入到有序区，有序区不是全局有序的。
直接插入排序最好的时间复杂度为O(n)
直接插入排序的最坏时间复杂度为O(n^2)
直接插入排序总的平均时间复杂度为O(n^2)
敲代码吧，仅此一次
void InsertSort(RecType R[],int n)
{int i,j,tmp;
for(i=1;i<n,i++)
{if (R[i].key<R[i-1].key)
{tmp=R[i];
j=i-1;
do
{
R[j+1]=R[j];
j--;
} while (j>=0&&R[i].key>tmp.key);
R[j+1]=tmp;
}
}
}
看懂什么意思了吗？对无序区R[0..n-1]，插入到有序区。拿R[i]先和R[i-1]（有序区的最后一个元素）进行比较，然后呢，在和R[i-2],R[i-3]比较。最好情况就是正序的时候，只比较，不移动。
二，折半插入排序
和折半查找的思想一样，减少了关键字的比较次数，从中间折半比较，每次都是折半，比直接插入排序要一个个元素都要比较一下明显优化了算法。稳定。
三，希尔排序
分组插入方法
先把一列数分为若干个组，组内先比较，排好序，再分组，再排序，分组按照总的数目除以2，向下取整得组数。
希尔排序是全局有序的，但它不是一种稳定的排序算法，数据的相对位置会因为移动而发生改变。
四，冒泡排序
一定是全局有序，性能比直接插入排序要差，很稳定，C语言已经学过很多遍了，都是一样的。
最好的时间复杂度为O(n)
最坏时间复杂度为O(n^2)
总的平均时间复杂度为O(n^2)
五，快速排序特点：任意取一个元素作为基准，小的放它前面，大的放它后面，快速排序可类比于三叉树，
它的最坏情况就是，它的左子树或者右子树是空的。它也是一种不稳定的排序算法，关键字的位置会改变。
六，简单选择排序
初始有序区为空，就是从无序区找到最小的放到有序区，它一共有四个辅助变量i,j,k,tmp。它也是一种不稳定的排序方法。因为你会发现两个同样的数，他们经过选择排序之后，先后位置会发生变化，这就说明不稳定。
七，堆排序
把关键字序列看作完全二叉树，主要以大根堆为主，以根节点大于左右节点来写程序。不稳定的排序算法。
八，归并排序
二路归并排序
要新开辟存储空间，最后再释放掉，所以空间复杂度O（n）
这个就是1，2，4，8，16.组内元素*2的增加（因为合并了组，这个合并方式和那个希尔排序是不一样的），组与组是局部有序的。这样排起来还是很快的。