内部排序：排序记录放在计算机存储器里面进行的。
内部排序分三类：
1.简单排序，时间复杂度O(n^2);
2.先进排序方法，时间复杂度O(nlogn);
3.基数排序，时间复杂度O(d·n);
插入排序1.1直接插入排序
void InsertSort(SqList &L){
//对顺序表L作直接插入排序
for(i=2;i
先把第一个看成有序，然后从第二个开始循环
箭头就是插入。
优化（时间复杂度不变）
折半插入（二分插入）
减少比较移动，在一个有序表里面插入。
2.2-路插入排序
减少排序过程中的移动次数，但需要牺牲辅助空间。
取第一个为起始，放在第一位，构造两个指针，first和final。最开始指针都是指向第一个数，然后开始读取关键字比较， 比第一个大，放在第一个后面，final=final->next，比第一个小，放在第一个前面，因为第一个前面没有空间，然后做循环链表，first=比第一个小那个数位置
3.表插入。
改变指针数据
希尔排序
也叫缩小增量排序，也是插入排序的一种。时间复杂度O（n）。但是不稳定。
第一趟，搁x位为一组，大在右边
第二趟，搁小于x的y位一组。。。
快速排序
冒泡：
冒泡思想
第一趟：n个里面最大的交换到右边
第二：n-1个里面最大的交换到右边
快速排序对冒泡的改进
通过一趟排序把待排分成两部分，其中一部分关键字均比另外一部分小，分别对两部分排序。任选一个数做枢纽，比他大在一边，小在一边，分成两部分，对那两部分递归，分别选一个数，在那两部分里面比他大在一边，小一边。。。。。。
先high比，如果发生交换，又从low开始，交换再到high。
为什么交换过去为空，已经存储了减少赋值次数。
选择排序
1.1 简单选择
1.2 树形选择排序
构造一个n个叶结点完全二叉树。
完全二叉树：从上到下，从左到右排，满二叉是他的一种。
1.3 堆排序
构造完全二叉树。
根小于左子小于右子叫小顶堆，反之叫大顶堆。
出顶后，二叉树最后一个元素作为顶，然后进行大顶小顶判断，符合条件后，再次出顶，再从选最后一个（没出）为顶。
时间复杂度O（nlogn）
归并排序
类似2-路插入
基数排序
多关键字。链式基数排序。
比较
