归并和快速排序.cpp

可以实现快速排序和归并排序的小程序

#include"iostream.h"
 #include <stdio.h>
#define MAXSIZE 20

typedef struct
{ int r[MAXSIZE+1];
  int length;
}List;

/* 初始化 */
void Initial(List &L,int num[],int n)
{ for(int i=0;i<n;i++)
    L.r[i]=num[i];
  L.length=n-1;
}

/* 输出结果 */
void Print(List L)
{ for(int i=1;i<=L.length;i++)
    printf("%d ",L.r[i]);
  printf("\n");
}


/* 快速排序 */
int Partition(List &L,int low,int high)
{ L.r[0]=L.r[low];
  while(low<high)
  { while(low<high && L.r[high]>=L.r[0]) high--;
    L.r[low]=L.r[high];
    while(low<high && L.r[low]<=L.r[0]) low++;
    L.r[high]=L.r[low];
  }
  L.r[low]=L.r[0];
  return low;
}

void QuickSort(List &L,int low,int high)
{ if(low<high)
  { int piv;
    piv=Partition(L,low,high);
    QuickSort(L,low,piv-1);
    QuickSort(L,piv+1,high);
  }
}/* 快速排序 */


/* 归并排序 */
void Merge(List L,List &T,int l,int m,int h)
{ int i=l,j=m+1,k=l;
  while(i<=m && j<=h)
    if(L.r[i]<=L.r[j]) T.r[k++]=L.r[i++];
    else T.r[k++]=L.r[j++];
  while(i<=m) T.r[k++]=L.r[i++]; //原来if改为while 
  while(j<=h) T.r[k++]=L.r[j++]; //原来if改为while
}

void MergeSort(List L,List &T,int s,int t)
{ if(s==t) T.r[s]=L.r[s];
  else
  { int m=(s+t)/2;
    List S;
    MergeSort(L,S,s,m);
    MergeSort(L,S,m+1,t);
    Merge(S,T,s,m,t);
  }
}/* 归并排序 */


void main()
{
  List L;
  int num[9];//={0,49,38,65,97,76,13,27,49};
  int dlta[3]={5,3,1};
  for(int q=1;q<=8;q++)
	  cin>>num[q];
  Initial(L,num,9);
  printf("原来的数据为:");
  Print(L);
  Initial(L,num,9);
  printf("快速排序 :");
  QuickSort(L,1,L.length);
  Print(L);
  Initial(L,num,9);
  printf("归并排序 :");
  MergeSort(L,L,1,L.length);
  Print(L);
}