第十章  内部排序               

10.1 概述
一、什么是排序
将一个数据元素(或记录)的任意序列, 重新排列成一个按关键字有序的一个序列.
二、排序的分类 （1）内部排序 （2）个部排序
三、排序的稳定性
四、涉及的操作  （1）比较  （2）移动
五、数据结构 （key, info）

10.2 插入排序
一.排序策略 :将一个记录插入到已排序好的有序表中, 并使它仍有序.
二.直接插入排序
for ( i=2;i<=n;++i)
  { r[0]=r;  j=i-1;  x=r.key;
while ( x<r[j].key ) { r[j+1]=r[j]; j=j-1; }
r[j+1]=r[0];  //r插入在r[j+1]的位置上  
  }
三.折半插入排序、二路插入排序、表插入排序
四.shell 排序
  // 对r[1..n]进行SHELL排序，记录位置的增量是d，r[0]是暂存单元
  d=n/2;  //取d1=n/2,di=di-1/2
  while ( d>=1) {
    for(i=d+1;i<=n;i++){
   r[0]=r;
   j=i-d;
    while (j>0)&&(r[0].key<r[j]key)) {
    { r[j+d]=r[j]; //记录后移，查找插入位置
      j=j-d;
    }
    r[j+d]=r[0]; //插入
}
d=d/2;
   }



10.3 快速排序
一.排序策略 :两两比较，将较小换到前面，大的交换到后面。
二.冒泡排序 (直接交换排序)
  j=1;
  do { swap=0; //未交换
   for ( i=1;i<=n-j;i++)
    if ( r.key>r[i+1].key ){ r<-->r[j+1];}
    //交换r和r[i+1], swp=1进行过交换
   j=j+1;}
   while (j<=n && swap!=0)  //排序n-1趟 或 排序至无交换为止
三.快速排序
void qkpass(listtp &r, int s,t, &i);
  i=s; j=t; x=r.key;//选r[s]为 轴记录rp
  while ( i<j )
{ while (i<j && r[j].key>=x) j--; r=r[j];
  //自尾端起找到第一个<x的记录r[j]和rp交换
   while (i<j && r.key<=x)  i++;r=r[j];
}
} //qkpass
void qksort(listtype &r,int s,t){ // 本算法对r[s..t]中记录进行快速排序
  if ( s<t  ) { qkpass(r,s,t,k);  
      qksort(r,s,k-1);
      qksort(r,k+1,t)；  
     }
}
例一: 给定关键字(1<j<n), 要求在无序记录a[1..n]中找到关键字从小到大排序的第j位上的记录.
    s=1; t=n; qkpass(a,s,t,k);
    while j!=k do
    if  (k<j)  { s=k+1; qkpass(a,s,t,k); }  else {t=k-1; qkpass(a,s,t,k); }
    return(a[j])
例二: 由1,2,3组成的序列, 排序
  i=1； while a!=2 do i++; a[1]<->a;
  qkpass(a,1,n,k) //[1….1]2[2323323…]
  while a!=3 do i++; a[1]<->a;
qkpass(a,k+1,n,i) //[1….1]2[2….2]3[3…3]
10.4 选择排序
一.        选择排序策略: 在待排序数据中每次选择最小元
二.简单选择排序
for ( i=1;i<=n-1;++i)
   { k=i;
   for ( j=i+1;j<+n;++j) if ( r[j].key<r[k].key)  k=j;
    //k指示关键字最小的记录
   if ( k<>i)  r <--> r[k] //r为r[i..n]中关键字最小的记录  
   }
三.堆排序
1.什么是堆  
n个元素的序列{k1,k2,…,kn},当且仅当 满足 ki<=k2i,  ,
                ki<=k2i+1 i=1,2,……n/2
2.堆的特点  堆顶元素最小, 从根到叶子是序(或降序)  3.问题  (1) 如何由一个无序序列建成一个堆?(2) 如何在输出堆顶元素之后, 调整剩余元素成为一个堆?  4.调整堆  void sift( listtp &r, int k,m) {
  i=k; j=2*i; x=r[k].key;  t=r[k]; //暂存"根"记录r[k]
  while ( j<=m )
{ if (j<m && r[j].key<r[j+1])  j=j+1;
  //若存在右自树,且右子树根的关键子小,则沿右分支"筛选"
  if ( X<=r[j].key) break;  //筛选完毕
  else { r=r[j]; i=j; j=2*i; }  //继续筛选   }
r=t  //r[k]填入恰当位置
  }
5.构造椎
for ( i=n/2;i<=1;--i)  sift(r,i,n); //自第i个记录开始进行筛选建堆
for ( i=n;i>=2,--i) {  r[1]←→r;        sift(r,1,i-1)        //调整r[1]使r[1..i-1]