第10章 排序
排序的基本概念\r插入排序\r选择排序\r交换排序归并排序\r基数排序\r性能比较
主要知识点
10.1 排序的基本概念
排序是对数据元素序列建立某种有序排列的过程,是把一个数据元素序列整理成按关键字递增（或递减）排列的过程。\r关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的。\r主关键字:数据元素值不同时该关键字的值也一定不同，是能够惟一区分各个不同数据元素的关键字;不满足主关键字定义的关键字称为次关键字。\r内部排序是把待排数据元素全部调入内存中进行的排序。\r外部排序是因数量太大，把数据元素分批导入内存，排好序后再分批导出到磁盘和磁带外存介质上的排序方法。
比较排序算法优劣的标准: \r(1)时间复杂度:它主要是分析记录关键字的比较次数和记录的 移动次数\r(2)空间复杂度 :算法中使用的内存辅助空间的多少 \r(3)稳定性:若两个记录A和B的关键字值相等，但排序后A、B的 先后次序保持不变，则称这种排序算法是稳定的
10.2插入排序
插入排序的基本思想是：每步将一个待排序的数据元素，按其关键码大小，插入到前面已经排好序的一组数据元素的适当位置上，直到数据元素全部插入为止。
1.直接插入排序
常用的插入排序有直接插入排序和希尔排序两种。
其基本思想是：\r 顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。
算法如下：\rvoid InsertSort (DataType a[], int n)\r//用直接插入法对a[0]--a[n-1]排序\r{\r int i, j;\r DataType temp;\r for(i=0; i