第7章 排序
  7.1排序的基本概念
  （1）排序：就是重新排列表中的元素，使表中的元素满足按关键字递增或递减的过程
  （2）算法稳定性：若待排序表中有两个元素R1和R2,其对应的关键字key1=key2，且在排序前R1在R2的前面，若使用某一排序算法排序后，R1仍然在R2的前面，则称这个排序算法是稳定，否则称排序算法是不稳定。
  7.2插入排序
  插入排序的基本思想：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成
  7.2.1直接插入排序
  （1）直接插入排序的基本思想：
  要将元素L(i)插入到已有序的子序列L[1…i-1]，需要执行以下操作：
  1）查找出L(i)在L[1…i-1]中的插入位置k。
  2）将L[k…i-1]中所有元素全部后移一个位置
  3）将L(i)复制到L(k)
  为了实现对L[1…n]的排序，将L(2)~L(n)依次插入到前面已排好序的子序列中，初始假定L[1]是一个已经排好序的子序列。上述操作执行n-1次得到一个有序的表。
  （2）直接插入排序的分析
  空间复杂度：O(1)
  时间复杂度：最好情况O(n)、平均情况O(
  )、最坏情况O(
  )
  稳定性：稳定
  适用性：线性表为顺序存储、链式存储
  
  （3）例题：给出关键字序列{4,5,1,2,6,3}的直接插入排序过程
  初始序列：4，5，1，2，6，3
  第一趟：4，5，1，2，6，3（将5插入{4}）
  第二趟：1，4，5，2，6，3（将1插入{4，5}）
  第三趟：1，2，4，5，6数据结构插入排序-【数据结构】第7章 排序-插入排序，3（将2插入{1，4，5}）
  第四趟：1，2，4，5，6，3（将6插入{1，2数据结构插入排序，4，5}）
  第五趟：1，2，3，4，5，6（将3插入{1，2，4，5，6}）
  【分析】直接插入排序每趟排序后不能确定一个元素的最终位置，只有最后一趟结束后才能得到元素的最终位置。
  （4）代码：
<p><pre class="has">#include
using namespace std;

define ElemType int

int main()
{  
    int i;
    void InsertSort(ElemType A[],int n);    //直接插入排序函数
    ElemType A[10]={1,3,5,7,9,2,4,6,8,0};
    InsertSort(A,10);          //直接插入排序 
    for(i=1;i