void InsertSort(ElemType A[],int n){
 int i,j;
 for(i=2;i<=n;i++) 
  if(A[i].key<A[i-1].key){ 
   A[0]=A[i];  //复制为哨兵，A[0]不存放元素
   for(j=i-1;A[0].key<A[j].key;--j)
    A[j+1]=A[j]; //所有比待插入元素值大的都往后移一位，腾出空位
   A[j+1]=A[0];     //复制到插入位置 
  }
}

void InsertSort(ElemType A[],int n){
 int i,j,low,high,mid;
 for(i=2;i<=n;i++){ //i记录的是待插入的元素下标，也就是说i-1之前的元素都是有序的 
  A[0]=A[i]; //保存待插入的值   
  low=1;high=i-1; 
  while(low<=high){  //折半查找 
   mid=(low+high)/2; 
   if(A[mid].key>A[0].key) high=mid-1; 
   else low=mid+1; 
  }
                              //找到了待插入的位置 接下来从后往前依次后移元素腾出位置
  for(j=i-1;j>=high+1;--j)A[j+1]=A[j];  
  A[high+1]=A[0]; //因为此时high指向的是待插入位置的前一位  
 }
}

void ShellSort (ElemType A[],int n){
               int i,j;
 for(dk=n/2;dk>=1;dk=dk/2)     //初始增量为总长度的一半，之后依次除2且向下取整，
                                                               //且最后一次要为1
  for(i=dk+1;i<=n;++i)
   if(A[i].key<A[i-dk].key){  //A[i].key是待插入的关键字，i-dk之前的都是有序的，如          //果待插入的比有序序列最后一个小， 则需要进行排序(进入if语句块)，如果大则不需要(跳出if语句块)
    A[0]=A[i];       //待插入关键字暂存在A[0]
    for(j=i-dk;j>0&&A[0].key<A[j].key; j-=dk)
                            //待插入关键字之前以dk为增量的关键字只要比待插入关键字大的都往后移动dk位
     A[j+dk]=A[j];  
    A[j+dk]=A[0]; //找到了待插入的位置，就将待插入关键字插入这个位置   
   }
}

void BubbleSort(ElemType A[],int n){
 for(i=0;i<n-1;i++){
  bool flag=false; //tips:当整个序列都有序的时候，标志位是不发生修改的，从而表示已经排好了 
  for(j=n-1;j>i;j--)   //一趟冒泡过程
   if(A[j-1].key>A[j].key){ //如果前面的元素比后面的大，则需要做交换
    ElemType temp=A[j-1].key;
                                                           A[j-1].key=A[j].key;
                                                           A[j].key=temp; 
    flag=true; //发生了数据交换 修改标志位
   }
  if(flag==false)return ; //本趟遍历后没有发生交换，说明表已经有序
 }
}

int Partition(ElemType A[],int low,int high){  //low是当前待排序的序列起始下标，high是末尾下标
 ElemType pivot=A[low]; //第一个元素作为枢轴
 while(low<high){  
  while(low<high&&A[high]>=pivot) --high;//先从末尾往前找到第一个比枢轴小的元素
  A[low]=A[high];  //用high的元素替换low的元素
  while(low<high&&A[low]<=pivot) ++low; //再从开头往后找到第一个比枢轴大的元素
  A[high]=A[low];  //用low的元素替换high的元素
 }
 A[low]=pivot;   //枢轴元素存放到最终位置
 return  low;    //返回存放枢轴的最终位置
}

void QuickSort(ElemType A[],int low,int high){
 if(low<high){   //low和high值要合法   
  int pivotpos=Partition(A,low,high); 
  QuickSort(A,low,pivotpos-1); //分治递归左半部分 
  QuickSort(A,pivotpos+1,high); //分治递归右半部分
 }
}

void SelectSort(ElemType A[],int n){
 for(i=0;i<n-1;i++){   //依次从后面序列中选择当前最小的元素作为第i个元素 最后一个元素不需要排序
        min=i;                    //min存的是当前最小元素所在下标，初值设为第i个
        for(j=i+1;j<n;j++)             //从第i个元素往后找，一直要找到最后一个元素
             if(A[j]<A[min]) min=j;    //如果这个值更小，则更新min值为这个更小的元素所在下标
        if(min!=i) {                        //如果第i个元素不是剩下元素最小的，则和最小的进行交换
                           ElemType temp=A[i];
                           A[i]=A[min];
                           A[min]=temp;
                    }  
 }
}

void BuildMaxHeap(ElemType A[],int len){
 for(int i=len/2;i>0;i--) AdjustDown(A,i,len); //由数组下标高处往低处 从第一个可能需要调整的非叶结点
                                                                             // 开始检查，直到根结点(注意根结点下标不是0，是从1开始存储)
}
void AdjustDown(ElemType A[],int k,int len){ //A是存储堆的数组,k是需要检查的结点下标,len是堆中结点个数
 A[0]=A[k];              //A[0]暂存这个需要检查的结点值
 for(i=2*k;i<=len;i*=2){  //从这个结点的左孩子开始往下比较，
                                                                          // 如果发生交换，对交换过的结点继续和它的孩子比较
  if(i<len&&A[i]<A[i+1])i++; //如果右孩子大一些，就只要考虑和右孩子比较
  if(A[0]>=A[i])  break; //如果这个结点的值不小于它的较大孩子结点值 则不需要交换
  else{ 
   A[k]=A[i]; //如果这个结点的值小于它的较大孩子
                                                                          //结点值则将较大的孩子结点值赋值给该结点 
   k=i;  //i赋值给k也就是从i开始继续往下检查 直到所有结点检查结束 
  }
 }
 A[k]=A[0]; //检查到最后k的值就是最后一轮交换过的结点位置下标 将该结点换过去  
}

void HeapSort(ElemType A[],int len){
 BuildMaxHeap(A,len);  //初始建堆
 for(i=len;i>1;i--){   //n-1趟的交换和建堆过程
  //输出堆顶元素(和堆底元素交换)
                              ElemType temp=A[i];
                              A[i]=A[1];
                              A[1]=temp;
                              printf(A[i]);
  AdjustDown(A,1,i-1); //把剩余的i-1个元素整理成堆
 }
}

ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType)); //辅助数组B(动态分配内存)

void Merge(ElemType A[],int low,int mid,int high){
//表A的两段A[low…mid]和A[mid+1…high]各自有序，将它们合并成一个有序表
 for(int k=low;k<=high;k++)B[k]=A[k];  //将A中所有元素复制到B中
 for(int i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){  k是归并之后数组的下标计数器
  if(B[i]<=B[j])      //比较B的左右两段中的元素
   A[k]=B[i++];   //将较小值复制到A中
  else
   A[k]=B[j++];
 }
 while(i<=mid) A[k++]=B[i++]; //若第一个表未检测完，直接将剩下的部分复制过来
 while(j<=high) A[k++]=B[j++]; //若第二个表未检测完，直接将剩下的部分复制过来
}

void MergeSort(ElemType A[],int low,int high){
 if(low<high){
  int mid=(low+high)/2;  //从中间划分两个子序列
  MergeSort(A,low,mid);  //对左侧子序列进行递归排序
  MergeSort(A,mid+1,high);                //对右侧子序列进行递归排序
  Merge(A,low,mid,high);  //归并
 }
}