排序 一种重要操作，将数据元素(记录)的任意序列，排列成按关键字有序的序列。 待排序记录数量不同，将排序方法分为内部排序、外部排序 内部排序分类：插入排序、交换排序、选择排序、归并排序、计数排序
插入排序 直接插入排序 算法思想： 将待排序的记录Ri，插入到已排好序的记录表R1, R2 ,…., Ri-1中，得到一个新的、记录数增加1的有序表。 直到所有的记录都插入完为止。 排序过程演示
算法实现
算法分析 空间复杂度：O(1) 时间复杂度： 在最好的情况下（待排序记录已经有序，即正序），此时每次循环中只需要比较关键字，次数为n-1次，而不需要移动元素 在最坏的情况下（待排序记录逆序），比较次数和移动元素的次数均达最大值，约为n*n(n-1) 插入排序的时间复杂度为O(n2)
希尔排序 又称“缩小增量排序”，对直接插入排序进行改进的方法 基本思想：将整个待排序列分割成若干子序列分别进行直接插入排序，最后在全体进行排序。
希尔排序演示
希尔排序是将相隔的某个增量的记录组成一个子序列，每次完成后增量减半
快速排序 借以交换进行的排序----起泡排序 快速排序是对起泡排序的改进 基本思想：通过一趟排序将记录分割两部分，其中一部分记录的关键字比另一部分小，分别进行排序。
快速排序示例
快速排序算法 结合此算法加深理解
void quickSort（int a[] ,int low,int high） { int i,j,m; i=low; j=high; m=a[low]; while(i<j) { while(i<j&&m<=a[j]) { j–; } if(i<j) { a[i]=a[j]; i++; }
while(i<j&&a[i]<m) { i++; } if(i<j) { a[j]=a[i]; j–; }
} a[i]=m; if(low<i) quickSort(a,low,i-1）； if（i<high）quickSort(a,i+1,high); }
选择排序 基本思想： 每趟在n-i+1个记录中选取最小关键字记录做有序列的第i个记录 包括简单选择排序、树形选择、堆排序
堆排序：只需一个记录大小的辅助空间 堆排序演示
最小堆（从小到大排）、最大堆（从大到小排）的建堆过程即自堆顶到叶子的调整过程。
不基于比较的排序----基数排序 上述几种排序过程都是基于比较实现的，基数排序完全不需要比较就能实现，借助多关键字思想排序。
排序示例
类似堆栈的定义，堆栈中元素是可以先入后出的，而这里排序借助了桶排序，数据是先入先出，从而实现有序。
线性表的查找
分为顺序查找、二分查找、分块查找三个方法。 顺序查找思路：从表一端开始，顺序扫描。将扫描到的关键字与k值相比。 操作性能：确定记录在查找表的位置，需要知道平均查找长度。（课本217页说明）
二分查找 查找思路：先确定待查记录所在范围，在逐步缩小范围直到找到该记录
结合代码理解
性能分析：效率高于顺序查找，但只适用于有序表，限于顺序存储结构
分块查找 又称索引顺序查找，建立索引表查找。
分块查找示例
动态查找表 二叉排序树、平衡二叉树 二叉排序树：左子树不空，左子树所有节点小于根结点值，右子树反之。 平均查找长度： ASL成功=结点所在层数*查找次数/总结点个数 ASL失败=补空结点所在层数 *查找该结点次数/补空结点个数
二叉排序树结点删除 练习
