分治算法中排序的完整代码

发布网友 发布时间：2022-04-23 09:55

我来回答

共1个回答

热心网友 时间：2023-07-05 08:02

快速排序
#include<windows.h>
#include<time.h>
#include<stdio.h>

#define MAX 10

void InitData(int a[],int len)
{//随机初始化待排序数据
int i;
srand(time(NULL));
for(i=0;i<len;i++) a[i]=rand()%1000;//随机初始化待排序数据
}

void Print(int a[],int from,int to)
{//输出a[from]到a[to]范围内所有数据，并换行
int i;
for(i=0;i<from;i++) printf(" ");//控制对齐，看出解决子问题的顺序
for(i=from;i<=to;i++) printf("%4d",a[i]);
printf("\n");
}

int part(int A[ ], int from, int to)
{int i=from+1, j=to, temp;
while( i<=j){ while(i<=to && A[i]<=A[from]) i++;
while(j>=from && A[j]>A[from]) j--;
if(i<j) {temp=A[i];A[i]=A[j];A[j]=temp;} //A[j]与A[j]交换
}
temp=A[j]; A[j]=A[from]; A[from]=temp;//A[j]与A[from]交换
return j;
}

void QuickSort(int A[ ], int from, int to) //快速排序的分治思想表达
{
if(from<to){ int position=part(A, from, to);
QuickSort(A,from,position-1);
QuickSort(A, position+1, to);
}
Print(A,from,to);
}

void main(void)
{
int A[MAX];
InitData(A,MAX);
Print(A,0,MAX-1);
QuickSort(A,0,MAX-1);
getch();
}

归并排序
#include<windows.h>
#include<stdio.h>

#define MAX 17

void InitData(int a[],int len)
{int i;
for(i=0;i<len;i++) a[i]=rand()%1000;//随机初始化待排序数据
}

void Print(int a[],int from,int to)
{
int i;
for(i=0;i<from;i++) printf(" ");//控制对齐，看出解决子问题的顺序
for(i=from;i<=to;i++) printf("%4d",a[i]);
printf("\n");
}

void Merge(int A[ ], int from, int to)
{
int *t=(int *)malloc(sizeof(int)*(to-from+1));
int i=from, mid=(to+from)/2, j=mid+1,k=0;
if(from>=to) return ;
Merge (A, from, mid);
Merge (A, mid+1, to); /*递归解决2个子问题*/
while(i<=mid && j<=to)
if(A[i]<A[j]) t[k++]=A[i++];
else t[k++]=A[j++];
while(i<=mid) t[k++]=A[i++];
while(j<=to) t[k++]=A[j++];
i=from;k=0;
while(i<=to) A[i++]=t[k++];//合并两个有序子表，即分别A[from~mid],A[mid+1~to];
//if(to-from>0)
Print(A,from,to); //合并子问题之后，将其打印出来
}

void main(void)
{
int a[MAX];
InitData(a,MAX);
Print(a,0,MAX-1);
Merge(a,0,MAX-1);
getch();
}