`

算法学习 之排序

    博客分类:
  • c++
 
阅读更多

 

/***********直接插入排序***************/
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



相关推荐

    数据结构学习笔记排序算法:基数排序

    数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数...

    快速排序算法和冒泡排序效率对比

    快速排序和冒泡排序是两种常见的排序算法,它们在计算机科学中扮演着重要的角色,特别是在数据处理和优化程序性能方面。...同时,这也为我们提供了深入学习其他高级排序算法,如归并排序、堆排序等的基础。

    python常用排序算法汇总

    该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 ...该排序算法把每次的排序结果都列出来,可供初学者学习。 self.arr存放的是待排序列表,可改成自己的数据

    排序算法编程 堆排序 快速排序

    在IT领域,排序算法是计算机科学中的基础但至关重要的部分,尤其对于编程和算法设计而言。本主题将深入探讨四种常见的...在学习过程中,亲自编译运行这些排序算法的代码是非常有益的实践,可以加深理解和提升动手能力。

    8种排序算法(选择排序 冒泡排序 快速排序等~)

    在计算机科学中,排序算法是用于对一组数据进行排列的算法。这里有8种常见的排序算法,包括选择排序、冒泡排序和快速...在学习和实践中,结合具体需求灵活运用这些排序算法,能够帮助我们编写出更高效、更优化的代码。

    MoreWindows白话经典算法之七大排序第2版(高清)

    本书《更多Windows白话经典算法之七大排序第2版》是一部深入浅出讲解七种经典排序算法的著作,旨在帮助读者理解并掌握冒泡排序、直接插入排序、直接选择排序、希尔排序、归并排序、快速排序以及堆排序等基本概念和...

    算法分析之排序算法 排序算法

    当然,为了学习和理解,我们也可以自己编写这些基本排序算法的C++代码。 例如,快速排序的C++实现可能如下: ```cpp void quickSort(int arr[], int left, int right) { if (left ) { int pivotIndex = ...

    学习排序算法之冒泡排序及其优化笔记.pdf

    冒泡排序算法是一种简单的排序算法,基本思想是通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的大小,若发现...在排序算法的学习过程中,冒泡排序可以作为认识和掌握其他更复杂排序算法的起点。

    Java数据结构与算法学习笔记之排序

    Java数据结构与算法学习笔记之排序,主要探讨了六种常见的排序算法:冒泡排序、选择排序、插入排序、希尔排序、归并排序和快速排序。这些排序算法是计算机科学的基础,无论是在日常开发还是面试中都经常遇到。现在...

    白话经典算法之七大排序

    冒泡排序是最简单的排序算法之一,它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的...

    数据结构与算法之排序

    本文将深入探讨“数据结构与算法之排序”,重点关注内部排序和外部排序。 首先,我们理解一下数据结构。数据结构是组织和存储数据的方式,它决定了数据的访问效率和操作复杂度。常见的数据结构有数组、链表、栈、...

    舞动的排序算法 快速排序

    舞动的排序算法 快速排序 通过动画演示快速排序,很好的学习,课程资源。

    算法与数据结构的排序算法

    通过阅读和理解这段代码,我们可以深入学习排序算法的内部机制,并从中获取优化算法性能的灵感。实际编程时,结合实际场景对这些算法进行调整和优化,可以进一步提高程序的运行效率。 总结,排序算法是计算机科学中...

    排序算法的PPT文档

    《排序算法详解》 排序,是计算机科学中最基础且至关重要的操作之一,它涉及将一组数据按照特定规则进行重新排列...通过对各种排序算法的深入学习和实践,我们可以更好地应对各种数据处理挑战,提高代码的效率和质量。

    经典C语言排序算法,冒泡排序,选择排序,插入法排序.

    经典C语言排序算法是指使用C语言实现的各种排序算法,这些算法都是计算机科学中最基本和最重要的算法之一。排序算法的主要目的是将一组无序的数据按照一定的顺序排列,例如从小到大或从大到小。以下我们将详细介绍三...

    白话经典算法之七大排序(高清版)

    《白话经典算法之七大排序》是一本专为初学者设计的算法教程,旨在通过简单易懂的语言,帮助读者深入浅出地理解并...通过阅读《白话经典算法之七大排序》高清版,读者可以轻松愉快地学习这些算法,并通过实践加深理解。

    MoreWindows白话经典算法之七大排序(高清版)

    ### 白话经典算法之七大排序 #### 一、冒泡排序 冒泡排序是一种简单直观的排序算法,它的基本思想是从第一个元素开始...通过学习这些算法,不仅可以提高数据处理能力,还可以为后续更高级的算法学习打下坚实的基础。

    Android-Android图形化展示排序算法

    在Android开发中,将排序算法以图形化的方式展示出来,不仅可以帮助开发者更好地理解和记忆各种排序算法的工作原理,还可以为教学和学习提供直观的工具。"Android-Android图形化展示排序算法"项目,就是这样一个旨在...

    java排序算法效率比较

    在Java编程语言中,排序算法是数据结构与算法学习中的重要组成部分。本实验通过生成大量随机数并写入文件,然后使用四种不同的排序算法进行排序,以比较它们的效率。以下是对这四种排序算法的详细解释: 1. **冒泡...

Global site tag (gtag.js) - Google Analytics