算法学习 之排序

 

/***********直接插入排序***************/
void InsertSort ( Elem R[ ], int n) 
{  // 对记录序列R[1..n]作直接插入排序。
for ( i=2; i<=n; ++i ) 
{
if( R[i] <= R[i-1] )
{   R[0] = R[i];   // 复制为监视哨
    R[i] = R[i-1]      
for ( j=i-2; R[0] < R[j]; --j )
R[j+1] = R[j];        // 记录后移
R[j+1] = R[0];        // 插入到正确位置
}  //if
}
} // InsertSort

/***********折半插入排序***************/

void BiInsertSort (Elem R[ ]， int n) 
{  // 对记录序列R[1..n]作折半插入排序。
for ( i=2; i<=n; ++i ) 
{
R[0] = R[i];   // 将R[i]暂存到R[0]
low = 1;    high = i-1;
while (low<=high)
{  //在R[low..high]中折半查找插入的位置
m = (low+high)/2;  // 折半
if (R[0] < R[m])
high = m-1; // 插入点在低半区
else low = m+1; // 插入点在高半区
}  //while
for ( j=i-1; j>=high+1; --j )
R[j+1] = R[j]; // 记录后移
R[high+1] = R[0]; // 插入
} // BinsertSort

/***********希尔插入排序***************/
void ShellInsert ( Elem R[ ], int dk ) 
{  // 对待排序列R作一趟希尔插入排序。本算法对直接插入算法作了以下
// 修改：1. 前后记录位置的增量是dk，而不是1；
//       2. r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。
for ( i=dk+1; i<=n; ++i )
if ( R[i]< R[i-dk]) 
{  // 需将R[i]插入有序增量子表
R[0] = R[i];     // 暂存在R[0]
for (j=i-dk; j>0 && R[0]< R[j]; j-=dk)
R[j+dk] = R[j];   // 记录后移，查找插入位置
R[j+dk] = R[0];      // 插入
}
} // ShellInsert

void ShellSort (Elem R[ ], int d [ ], int t)
{  // 按增量序列d [0..t-1]对顺序表L作希尔排序。
for (k=0; k<t; ++t)
ShellInsert(R, d[k]); // 一趟增量为d [k]的插入排序
} // ShellSort

评论

5 楼 sblig 2012-05-07  

/*二叉排序树*/
BiTree SearchBST ( BiTree T , KeyType key)
{  //在T为根的二叉排序树中查找key，若查找成功，返回
  //指向该元素结点的指针，否则返回空指针
    if ( T==NULL)   return(NULL);      //空树，查找不成功
    else if( T->data== key )   return ( T ) ;   //查找成功
    else if( key < (T->data))
         return ( SearchBST ( T->lchild, key));
    else 
         return ( SearchBST ( T->rchild, key)); 
}
/*改后的  SearchBST 能够返回插入位置*/
BiTree SearchBST(BiTree T , KeyType key，BiTree f，BiTree &p)
{ /*在指针T所指的二叉排序树中寻找关键字等于key的数据元素，若查找成功，则p指向该结点，并返回TRUE,否则p指向查找路径上访问的最后一个结点并返

回FALSE，f指向T的双亲*/
   if ( T==NULL)  {  p=f;    return(FALSE);   }
   else if  (T->data== key)  {  p=T;   return (TRUE) ;}
   else if (key < (T->data))
         return ( SearchBST (T->lchild， key，T，p) );
   else
         return ( SearchBST ( T->rchild， key，T，p) ); 
}
Status InsertBST ( BitTree T , KeyType key)
{ /*若在二叉排序树中不存在关键字等于key的元素， 插入该元素并返回TRUE，否则返回FALSE*/
    if( !SearchBST(T，key，NULL，p) ) //查找不成功
    {  s = (BitTree) malloc (sizeof( BitNode)); 
     s->data = key;  s->lchild=NULL;  s->rchild=NULL;    if ( !p ) T = s;   //被插结点为新的根结点
       else if(key < T->data)  p->lchild=s //将s插入左子树
       else                    p->rchild=s; //将s插入右子树
    }  //if
    else return FALSE;
}
Status DeleteBST (BiTree &T, KeyType key ) 
{  /*若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点p，并返回TRUE；否则返回FALSE*/
    if (!T) return FALSE; // 不存在关键字等于key的数据元素
    else 
   {
          if (key==T->data) ) Delete (T);
                  // 找到关键字等于key的数据元素
          else if (key< T->data )
                         DeleteBST ( T->lchild, key );
          else           DeleteBST ( T->rchild, key );
          return TRUE;
     }
} // DeleteBST

4 楼 sblig 2012-05-07  

//上面的二叉树用到
void Delete ( BiTree &p )
{ //从二叉排序树中删除结点p，并重接它的左或右子树
    if (!p->rchild)        // 右子树空则只需重接它的左子树
    {     q = p;   p = p->lchild;   free(q); } 
    else if (!p->lchild)      // 只需重接它的右子树
    {     q = p;   p = p->rchild;   free(q); }
    else     // 左右子树均不空
    {     q = p;   s = p->lchild;
          while (s->rchild) {  q = s;    s = s->rchild; }
          p->data = s->data;         // s指向被删结点的前驱
          if (q != p )  q->rchild = s->lchild; 
          else q->lchild = s->lchild;     // 重接*q的左子树
          free(s); 
     }
} // Delete 

3 楼 sblig 2012-05-07  

/******************起泡排序******************/
void BubbleSort(Elem R[], int n)
{ // i 指示无序序列中最后一个记录的位置
i = n;
while (i >1) 
{   lastExchangeIndex = 1;
for (j = 1; j < i; j++)
if (A[j+1] < A[j]) 
{   Swap(A[j],A[j+1]);
lastExchangeIndex = j;
} //if
i = lastExchangeIndex;
} // while
} // BubbleSort

/******************快速排序******************/
int Partition (Elem R[], int low, int high)
{ // 交换记录子序列R[low..high]中的记录，使枢轴记录到位，并返回其所
// 在位置，此时，在它之前（后）的记录均不大（小）于它
pivotkey = R[low];   // 用子表的第一个记录作枢轴记录
while (low<high) 
{ // 从表的两端交替地向中间扫描
while (low<high && R[high]>=pivotkey) 
--high;
R[low]←→R[high];  // 将比枢轴记录小的记录交换到低端
while (low<high && R[low]<=pivotkey) 
++low;
R[low]←→R[high];  // 将比枢轴记录大的记录交换到高端
} //while
return low; // 返回枢轴所在位置
} // Partition
容易看出，调整过程中的枢轴位置并不重要，因此，为了减少记录的移动次数，应先将枢轴记录“移出”，待求得枢轴记录应在的位置之后(此时low=high),再将枢轴记录到位。
将上述“一次划分”的算法改写如下：
int Partition (Elem R[], int low, int high) 
{  // 交换记录子序列R[low..high]中的记录，使枢轴记录到位，并返回其所
// 在位置，此时，在它之前（后）的记录均不大（小）于它
R[0] = R[low];   // 用子表的第一个记录作枢轴记录
pivotkey = R[low]; // 枢轴记录关键字
while (low<high)
{ // 从表的两端交替地向中间扫描
while(low<high && R[high]>=pivotkey)
--high;
R[low] = R[high];  // 将比枢轴记录小的记录移到低端
while (low<high && R[low]<=pivotkey) 
++low;
R[high] = R[low];  // 将比枢轴记录大的记录移到高端
}
R[low] = R[0]; // 枢轴记录到位
return low; // 返回枢轴位置
} // Partition

void QSort (Elem R[], int low, int high) 
{  // 对记录序列R[low..high]进行快速排序
if (low < high) 
{ // 长度大于1
pivotloc = Partition(L, low, high); // 将L.r[low..high]一分为二
QSort(L, low, pivotloc-1); // 对低子表递归排序，pivotloc是枢轴位置
QSort(L, pivotloc+1, high);// 对高子表递归排序
}
} // Qsort

void QuickSort ( Elem R[ ], int n) 
{  // 对记录序列进行快速排序
QSort(R, 1, n);
} // QuickSort

2 楼 sblig 2012-05-07  

/******************归并排序******************/
void Merge (Elem SR [ ], Elem TR [ ], int i, int m, int n)
{ // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
    for (j=m+1, k=i; i<=m && j<=n; ++k) 
    { // 将SR中记录由小到大地并入TR
       if ( SR[i] <= SR[j] )  TR[k] = SR[i++];
       else                 TR[k] = SR[j++];
    }
    if (i<=m) TR[k..n] = SR[i..m];//将剩余的SR[i..m]复制到TR
    if (j<=n) TR[k..n] = SR[j..n];//将剩余的SR[j..n]复制到TR
} // Merge

void Msort ( Elem SR[], Elem &TR1[], int s, int t ) 
{ // 将SR[s..t]进行2-路归并排序为TR1[s..t]。
if (s==t) TR1[s] = SR[s];
else
{   m = (s+t)/2;
// 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
Msort (SR, TR2, s, m);
// 递归地将SR[s..m]归并为有序的TR2[s..m]
Msort (SR, TR2, m+1, t);
//递归地SR[m+1..t]归并为有序的TR2[m+1..t]
Merge (TR2, TR1, s, m, t);
// 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
} //else
} // Msort

void MergeSort (Elem R[]) 
{  // 对记录序列R[1..n]作归并排序。
MSort(R, R, 1, n);
} // MergeSort

1 楼 sblig 2012-05-07  

/******************简单选择排序******************/
void  SelectSort ( Elem  R[ ]，int n )   
{  
  for ( i=1; i<= n-1; i++)  //选择第i小的记录，并交换到位
  {  k=i； 
     for ( j=i+1 ; j<= n ; ++j) 
        if ( R[j] < R[k] )   k=j；
     if ( k != i) Swap(R[i], R[k] );  
  } //for
} //SelectSort

/********************堆排序*********************/
void HeapAdjust (Elem R[ ], int s, int m)   //一次筛选
{  // 已知R[s..m]中记录的关键字除R[s]之外均满足堆的定义，
// 本函数调整R[s] 的关键字，使R[s..m]成为一个大顶堆
rc = R[s];
for ( j=2*s; j<=m; j*=2 )
{  // 沿key较大的孩子结点向下筛选
if ( j<m && R[j]<R[j+1] ) ++j;// j为key较大的记录的下标
if ( rc >= R[j] ) break; // rc应插入在位置s上
R[s] = R[j];    s = j;
}
R[s] = rc; // 插入
} // HeapAdjust

void HeapSort ( Elem R[ ], int n )
{   // 对记录序列R[1..n]进行堆排序。
for ( i=n/2; i>0; --i )  // 把R[1..n]建成大顶堆
HeapAdjust ( R, i, n );
for ( i=n; i>1; --i ) 
{   R[1]←→R[i]; // 将堆顶记录和当前未经排序子序列
//R[1..i]中最后一个记录相互交换
HeapAdjust(R, 1, i-1); // 将R[1..i-1] 重新调整为大顶堆
}
} // HeapSort