常用算法

选择排序

1. 基本概念

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

 

2. 排序过程：
【示例】：
 初始关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 ［38 65 97 76 49 27 49]
第二趟排序后 13 27 ［65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序结果 13 27 38 49 49 76 76 97

 

3.具体算法

 

void selectionSort(Type* arr,long len)
{
      long i=0,j=0;/*iterator value*/
      long maxPos;
      assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n");
      for(i=len-1;i>=1;i--)
      {
             maxPos=i;
             for(j=0;j<i;j++)
                    if(arr[maxPos]<arr[j])maxPos=j;
             if(maxPos!=i)swapArrData(arr,maxPos,i);
      }
}

 

 

选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换.

 

 

冒泡排序

1.基本概念

 

冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数放在后面。即首先比较第1个和第2个数，将大数放前，小数放后。然后比较第2个数和第3个数，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前，小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将大数放前，小数放后，一直比较到最小数前的一对相邻数，将大数放前，小数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。如此下去，直至最终完成排序。

 

由于在排序过程中总是大数往前放，小数往后放，相当于气泡往上升，所以称作冒泡排序。

 

用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i, j的值依次为1,2,...10-i。

 

2.排序过程
设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。

 

 

3.算法示例
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97

 

#include <iostream.h>
void BubbleSort(int* Arr,int Count)
{
int iTemp;
for(int i=1;i<Count;i++)
{
 for(int j=Count-1;j>=i;j--)
 {
  if(Arr[j]<Arr[j-1])
  {
   iTemp = Arr[j-1];
   Arr[j-1] = Arr[j];
   Arr[j] = iTemp;
  }
 }
}
}

 

快速排序

1.基本概念
快速排序的实现基于分治法，具体分为三个步骤。假设待排序的序列为L[m..n]。
分解：序列L[m .. n]被划分成两个可能为空的子序列L[m .. pivot-1]和L[pivot+1 .. n]，使L[m .. pivot-1]的每个元素均小于或等于L[pivot]，同时L[pivot+1.. n]的每个元素均大于L[pivot]。其中L[pivot]称为这一趟分割中的主元（也称为枢轴、支点）。
解决：通过递归调用快速排序，对子序列L[m .. pivot-1]和L[pivot+1 .. r]排序。
合并：由于两个子序列是就地排序的，所以对它们的合并不需要操作，整个序列L[m .. n]已排好序。

 

2.排序过程

 

 

3.算法示例

void  quicksort(int* arr,int count){
int i, j, pivot, temp;
i = 0;
j = count;
pivot = arr[(i+j) / 2];
 
do
 while (arr[ i ]<pivot)   i++;    //找左边比他大的
 while (arr[j]>pivot)   j--;  //找右边比他小的
 
 if (i<=j) {  //交换
  temp = arr[ i ];
  arr[i] = arr[j];
  arr[j] = temp;
  i++;  j--;
 }   
while (i>j);

 

if (0<j)  qsort(s,j);
if (i<count)  qsort(i,t);
}

堆排序

1.基本概念
　　树形选择排序(锦标赛排序)，1964年威洛姆斯(J.Willioms)提出了进一步改正的排序方法，即堆排序(heap sort)。
堆是n个元素的有限序列{ K1,K2,…,Kn }，它当且仅当满足如下关系：
             
　　这是一个上小、底大的堆。若是一个上大、底小的堆，只需把“ <= ”改为“ >= ”即可。堆是一种数据元素之间的逻辑关系，常用向量做存储结构。对于满二叉树，当对它的结点由上而下，自左至右编号之后，编号为 i 的结点是编号为 2i 和 2i+1 结点的双亲。反过来讲，结点 2i 是结点 i 的左孩子，结点 2i+1 是结点 i 的右孩子。图 9.7 表示完全二叉树和它在向量中的存储状态。结点编号对应向量中的下标号。
　　用堆的概念分析向量中的数据，它显然满足（上小、底大）堆的关系。不难看出满足堆的逻辑关系的一组数据，可画成二叉树的形状，并且它是一棵完全二叉树树形。因此，也可借助完全二叉树来描述堆的概念。若完全二叉树中任一非叶子结点的值小于等于（或大于等于）其左、右孩子结点的值，则从根结点开始按结点编号排列所得的结点序列就是一个堆。在图 9.8 中 (a) 、 (c) 是堆， (b) 、 (d) 不是堆。

 

2.算法思想
   堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
（1）用大根堆排序的基本思想
　　① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
　　② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
　　③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
    ……
 直到无序区只有一个元素为止。
（2）大根堆排序算法的基本操作：
　　① 初始化操作：将R[1..n]构造为初始堆；
　　② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
 注意：
　　①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
　　②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。

 

3.具体算法

template<class T>
 heapsort(T r[],int n)   //n为文件的实际记录数，r[0]没有使用
 { int i,m;node x;
   for(i=/2;i>=1;i--)heappass(r,i,n);   //初建堆
 //以下for语句为输出堆顶元素、调整堆操作
   for(m=n-1;m>=1;m--)//逻辑堆尾下标m不断变小
      { cout<<r[1].key<<" ";
         x=r[1];r[1]=r[m+1];r[m+1]=x;    //堆顶与堆尾元素对换
         heappass(r,1,m);//恢复堆
      }
    cout<<r[1].key<<endl;
 } //heapsort

 

 

二叉树建立与遍历

1．算法思想
//先定义数据类型
＃typedef struct BiTNode{
char data;   //data你想用什么类型自己变就行了
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

 

//建树也用递归
void createTree(char data,BiTree &T)//用引用
{
char c;
c = getchar();
 
if(c!=NULL){
 T = (BiTree)malloc(sizeof(BiTNode);
 T->data = c;
 createTree(data,lchild);
 createTree(data,rchild);
} else {
 T=NULL;
}
}//这是先序建树，中序和后序只是变变顺序

 

//遍历，这是后序，也是递归
void traverse(BiTree T)
{
if(T){
 traverse(T->lchild);
 traverse(T->rchild);
 printf(T->data);
}
}//还是那样，先序和中序变一变这三句的顺序就行。

 

typedef struct tree {
struct tree *left;
int date;
struct tree *right;
}treenode,*b_tree;

 

///////插入节点/////////////////////
b_tree insert(b_tree root,int node) {
b_tree newnode;
b_tree currentnode;
b_tree parentnode;

 

newnode=(b_tree)malloc(sizeof(treenode));
newnode->date=node;
newnode->right=NULL;
newnode->left=NULL;

 

if(root==NULL)  return newnode;
else {
 currentnode=root;
 while(currentnode!=NULL)  {
  parentnode=currentnode;
  if(currentnode->date>node)
   currentnode=currentnode->left;
  else
   currentnode=currentnode->right;
 }
 
 if(parentnode->date>node)  parentnode->left=newnode;
 else   parentnode->right=newnode;
}
return root;
}

 

//////建立树///////////////////
b_tree creat(int *date,int len) {
b_tree root=NULL;
int i;
for(i=0;i<len;i++)   root=insert(root,date[i]);
return root;
}

 

//////中序打印////////////////
void print1(b_tree root) {
if(root!=NULL) {
 print1(root->left);
 printf("%d->",root->date);
 print1(root->right);
}
}

 

//////后序打印////////////////
void print2(b_tree root) {
if(root!=NULL)  {
 print2(root->left);
 print2(root->right);
 printf("%d->",root->date);
}
}

 

//////前序打印////////////////
void print3(b_tree root) {
if(root!=NULL)  {
 printf("%d->",root->date);
 print3(root->left);
 print3(root->right);
}
}

 

//////////在二叉树中查找给定关键字 ////////////
b_tree lookfor(b_tree root,int e) {
b_tree p1,p2;
if(root!=NULL)  {
 if(root->date==e)    return root;
 else
  p1=lookfor(root->left,e);

 

 p2=lookfor(root->right,e);
 
 if(p1!=NULL)   return p1;
 else  if(p2!=NULL)   return p2;
 else    return NULL;
}
else return NULL;
}